在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可以把该模块从内核中删除掉。