Linux中链表的应用

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