Linux中的鏈表，主要針對頭文件中的鏈表定義以及使用。
在C語言中我們也學過鏈表，對於鏈表的一些定義我就不多說了，這兒主要介紹一下中的鏈表定義。
1、鏈表的定義：
struct list_head{
struct list_head *next,*pre;
};
註意這是一個雙向鏈表並且是不帶數據域的，下面看一個帶數據域的鏈表定義：
struct my_list{
void *mydata;
struct list_head list;
};
以struct list_head為基本對象，對鏈表進行插入、刪除、合並以及遍歷等各種操作。
2、鏈表的聲明和初始化：
struct list_head 只定義了鏈表節點，並沒有專門定義鏈表頭，那麽一個鏈表結構是如何建立起來的？內核代碼list.h中定義了兩個宏：
#define LIST_HEAD_INIT(name){&(name),&(name)}/*僅做初始化*/
#define LIST_HEAD(name) struct list_head name=LIST_HEAD_INIT(name);/*聲明並初始化*/
如果要聲明並初始化自己的鏈表頭mylist_head，則直接調用LIST_HEAD:LIST_HEAD(mylist_head)
調用之後，mylist_head的next,pre指針都指向自己，這樣就有了一個空鏈表,我們可以寫一個簡單的list_empty()函數來判斷它是否為空？
int list_empty(struct list_head mylist_head)
{
if(mylist_head->next==mylist_head->pre){
return 1;
}else{
return 0;
}
}
而在我們初始化鏈表為空時無非就是讓鏈表的頭指針指向自己。註意這是一個循環鏈表。
3、在鏈表中增加一個節點：
在list.h中的定義的函數為：
static inline void list_add();
static inline void list_add_tail();
下面我們可以實現第一個函數:
static inline void __list_add(struct list_head *new,
struct list_head *pre,struct list_head *next)
{
next->pre=new;
new->next=next;
new->pre=pre;
pre->next=new;
}
在內核代碼中，在函數名前面加兩個下劃線表示內部函數，其實上面的函數實現就是雙向循環鏈表的插入節點操作。
調用這個函數可以分別在鏈表頭和尾增加節點：
static inline void list_add(struct list_head *new,struct list_head *head)
{
__list_add(new,head,head->next);
該函數向指定節點後插入節點new.
static inline void list_add_tail(struct list_head *new,struct list_head *head)
{
__list_head(new,head->pre,head);
}
該函數向head節點前插入節點new.
4、遍歷鏈表：
list.h中定義的遍歷鏈表的宏如下所示：
#define list_for_each(pos,head) \
for(pos=head->next;pos!=head;pos=pos->next);
這種遍歷僅僅是找到一個個節點在鏈表中的偏移位置pos,現在的問題是如何通過pos獲得節點的起始地址，從而可以引用節點中的域？於是list.h中又定義了list_entry()宏？
#define list_entry(ptr,type,member)\
((*type)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))
看起來這個長句子，乍一下真的有種想吐的感覺，不過越是這種才越有意思，下面我們慢慢來分析一下這個句子：
首先我們可以看出它最後返回的是type類型的指針，而指針ptr是指向type結構體中的成員變量member的，所以通過ptr,返回結構體type的起始地址。
（unsigned long）(&((type*)0)->member)可以看出首先把0地址轉化為type結構體類型的指針，然後獲取成員變量member的地址，也就是在type結構體裏邊的偏移量知道了。而(char *)ptr求出的是ptr的絕對
地址，二者相減，便得到了阿type類型結構體的起始地址。
接下來我們看一下鏈表的應用：一個Linux內核模塊的例子，更好的理解鏈表：
#include<linux/kernel.h>
#include<linux/module.h>
#include<linux/slab.h>
#include<linux/list.h>
MODULE_LICENSE("GPL");
MODULE_AUTHOR("XIYOU");
#define N 10
struct numlist{
int num;
struct list_head list;
};
struct numlist numhead;
static int __init doublelist_init(void)
{
struct numlist *listnode;
struct list_head *pos;
struct numlist *p;
int i;
printk("doublelist is starting..\n");
INIT_LIST_HEAD(&numhead.list);
for(i=0;i<N;i++)
{
listnode=(struct numlist *)kmalloc(sizeof(struct numlist),GFP_KERNEL);
listnode->num=i+1;
list_add_tail(&listnode->list,&numhead.list);
printk("node %d has added to the doublelist\n",i+1);
}
//遍歷鏈表
i=1;
list_for_each(pos,&numhead.list){
p=list_entry(pos,struct numlist,list);
printk("node %d's data :%d\n",i,p->num);
i++;
}
return 0;
}
static void __exit doublelist_exit(void)
{
struct list_head *pos,*n;
struct numlist *p;
//依次刪除N個節點
int i;
list_for_each_safe(pos,n,&numhead.list)
{
list_del(pos);
p=list_entry(pos,struct numlist,list);
kfree(p);
printk("node %d has removed from the doublelist\n",i++);
}
printk("doublelist is exiting\n");
}
module_init(doublelist_init);
module_exit(doublelist_exit);
這僅僅是一個內核模塊接下來我們要編譯該模塊，為此我們寫一個makefile文件來編譯：
obj-m:=list.o
CURRENT_PATH:=$(shell pwd)
LINUX_KERNEL:=$(shell uname -r)
LINUX_KERNEL_PATH:=/usr/src/linux-headers-$(LINUX_KERNEL)
all:
make -C $(LINUX_KERNEL_PATH) M=$(CURRENT_PATH) modules
clean:
make -C $(LINUX_KERNEL_PATH) M=$(CURRENT_PATH) clean
在命令行下面用"make"命令運行Makefile文件，我們可以生成後綴名 為.ko的文件，接著我們可以把這個文件加載到內核中，使用insmod *.ko命令加載，註意此命令是在超級用戶權限下面運行的。而使用rmmod *.ko可以把該模塊從內核中刪除掉。
文章標籤
全站熱搜
留言列表
