Linux内核中linked list的实现与应用.txt

/////////////////////////////////////////////
//Linux内核中链表的实现与应用
//
//参考资料：Linux操作系统原理与应用（第2版）    陈莉君、康华 编著
/////////////////////////////////////////////

循环双向链表是Linux内核中最简单、最常用的一种数据结构。
       
       1、链表的定义
            struct list_head {
                struct list_head *next, *prev;
            }
            //这个不含数据域的链表,可以嵌入到任何数据结构中,例如如下定义含有数据域的链表：
            struct my_list {
                void  * mydata;
                struct list_head  list;
            } ;

       2、链表的声明和初始化宏
            struct list_head 只定义了链表结点, 并没有专门定义链表头. 那么一个链表结点是如何建立起来的？
            内核代码 list.h 中定义了两个宏:
            #defind  LIST_HEAD_INIT(name)    { &(name), &(name) }                       //仅初始化
            #defind  LIST_HEAD(name)     struct list_head  name = LIST_HEAD_INIT(name)  //声明并初始化
           
            如果要声明并初始化链表头mylist_head，则直接调用：LIST_HEAD(mylist_head)，之后， mylist_head的next、prev指针都初始化为指向自己。这样，就有了一个带头结点的空链表。

             判断链表是否为空的函数：
             static inline int list_empty(const struct list_head  * head) {    //返回1表示链表为空，0表示不空
                  return head->next  ==  head;
             }

      3、在链表中增加一个结点
            static inline void   __list_add(struct list_head *new, struct list_head *prev, struct list_head *next)
            {
                     next -> prev = new ;
                     new -> next = next ;
                     new -> prev = prev ;
                     prev -> next = new ;
            }  
          
            list.h 中增加结点的两个函数为: （链表是循环的，可以将任何结点传递给head，调用这个内部函数以分别在链表头和尾增加结点）
            static inline void list_add(struct list_head *new, struct llist_head *head)
            {
                    __list_add(new, head, head -> next) ;
            }
            static inline void list_add_tail(struct list_head *new, struct list_head *head)
            {
                     __list_add(new, head -> prev, head) ;
            }
            附：给head传递第一个结点，可以用来实现一个队列，传递最后一个结点，可以实现一个栈。

            
    4、 遍历链表
           list.h 中定义了如下遍历链表的宏：
           #define   list_for_each(pos, head)    for(pos = (head)-> next ;  pos != (head) ;  pos = pos -> next)  
           这种遍历仅仅是找到一个个结点的当前位置，那如何通过pos获得起始结点的地址，从而可以引用结点的域？
           
           list.h 中定义了 list_entry 宏：
           #define   list_entry( ptr, type, member )  \
              ( (type *) ( (char *) (ptr)  - (unsigned long) ( &( (type *)0 )  ->  member ) ) )
              
           分析：(unsigned long) ( &( (type *)0 )  ->  member ) 把 0 地址转化为 type 结构的指针，然后获取该
                结构中 member 域的指针，也就是获得了 member 在type 结构中的偏移量。其中  (char *) (ptr) 求
                出的是 ptr 的绝对地址，二者相减，于是得到 type 类型结构体的起始地址，即起始结点的地址。

   5、链表的应用
         一个用以创建、增加、删除和遍历一个双向链表的Linux内核模块

#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/slab.h>
#include <linux/list.h>

#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); //初始化头结点

    //建立N个结点，依次加入到链表当中
    for (i=0; i<N; i++) {
        listnode = (struct numlist *)kmalloc(sizeof(struct numlist), GFP_KERNEL);
        if (listnode != NULL) {
            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;
    int i;

    //依次删除N个结点
    i = 1;
    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);
MODULE_LICENCE("GPL");