linux内核链表.doc

文档介绍：双向循环链表在 LINUX kernel 中的实现
Email:lsl@
blog:http://blog./vincent040
版权声明:版权保留。本文用作其他用途当经作者本人同意,转载请注明作者姓名
All Rights Reserved. If for other use,must Agreed By the this text,please claim the writer's name.
Copyright (C) 2010 vincent lin
如果我们把内核中的用链表表示的数据结构画出来,那将是一盘又复杂又美味的。。。。意大利面。。。就像在之前分析的VFS那样。
内核中的链表经典实现,改造一下,体会一下,玩味一下。
内核的经典双向循环链表结构跟普通教材上教的双向循环链表的实现不大一样,平常我们会把数据存储在节点中,再把节点连接起来形成链表,但是内核中的双向循环链表是用一个独立的结构体来表示的,如下:
struct list_head
{
    struct list_head *prev;
    struct list_head *next;
};
正如你所见,该结构体除了两个指向本身的指针之外别无他物,实际上,它们是用来被“嵌入”其他数据结构中的,以此来将各个节点串起来。
比如,我们可以定义一个这
样的结构体:
struct kool_list
{
    int to;
    struct list_head list;
    int from;
};
这个结构体包含了 list_head,因此我们可以将多个这样的 kool_list 结构体串起来形成一个双向循环链表!下面我们就来通过对一个例子的分析看一下内核是怎么操作这种链表的(由于双向循环链表在内核中使用非常频繁,因此对链表的操作可谓是精益求精,力求高效,我们拭目以待!)
假设现在我想要创建一个包含5个 kool_list 节点的双向循环链表,节点当中的 to 字段和 from 字段随便放两个整数,创建完之后用不同的方式遍历它,然后释放它。如果是内核,她会怎么做呢?
首先不管三七二十八,我们来定义一个 kool_list 结构体,然后初始化它:
struct kool_list  mylist;
INIT_LIST_HEAD(&());
其中宏定义如下:
#define  INIT_LIST_HEAD(ptr)  do {  \
    (ptr)->next = (ptr); \
    (ptr)->prev = (ptr);  \
}while(0)
这相当于把第一个节点 mylist 中的字段 list 里面的两个指针自己指向了自己,构成一个单节点的双向循环链表。
至于宏定义中的do ... while循环是为了能在宏替换语句中使用分号,使其看起来更自然。
好了,有了头结点,我们可以循环地从键盘获取5组数据,分别存储到5个节点当中,连接起来,形成一个双向循环链表:
struct kool_list *tmp;
for(i=5; i!=0; --i)
{
    tmp = (strict kool_list *)malloc(si