Linux内核双链表

1 定义

双链表的定义在文件<include/linux/list.h>中。

00019: struct  list_head{

00020:       structlist_head*next,*prev;

00021: };

2 初始化头结点

00023: #defineLIST_HEAD_INIT(name){&(name),&(name)}

00024:

00025: #defineLIST_HEAD(name)\

00026:       structlist_head name=LIST_HEAD_INIT(name)

00027:

00028: staticinlinevoid INIT_LIST_HEAD(structlist_head*list)

00029: {

00030:       list–>next= list;

00031:       list–>prev= list;

00032: }

宏LIST_HEAD_INIT(name)是将变量name初始化，把prev，next都指向自身，如图4所示。

                                                                                                图1 LIST_HEAD_INIT(name)

宏LIST_HEAD(name)为定义struct list_head结构变量name（注意，这里只是结构变量，而非指针变量），并调用宏LIST_HEAD_INIT(name)初始化该变量。

宏INIT_LIST_HEAD(ptr)初始化struct list_head结构指针ptr，next和prev都指向自身。

宏INIT_LIST_HEAD(ptr)和宏LIST_HEAD_INIT(name)的区别是后者初始化结构型变量，前者初始化指针型变量。

3 插入和删除结点

00064: staticinlinevoid list_add(structlist_head*new,structlist_head*head)

00065: {

00066:       __list_add(new,head,head–>next);

00067: }

00068:

00041: staticinlinevoid __list_add(structlist_head*new,

00042:                           structlist_head*prev,

00043:                           structlist_head*next)

00044: {

00045:       next–>prev= new;

00046:       new–>next= next;

00047:       new–>prev= prev;

00048:       prev–>next= new;

00049: }

   在结点prev，next之间插入新结点new。

                                                                                                      图2 __list_add()示意图

00078: staticinlinevoid list_add_tail(structlist_head*new,structlist_head*head)

00079: {

00080:       __list_add(new,head–>prev,head);

00081: }

                                                                                                        图3 list_add()示意图

                                                                                                    图4 list_add_tail()示意图

00103: staticinlinevoid list_del(structlist_head*entry)

00104: {

00105:       __list_del(entry–>prev,entry–>next);

00106:       entry–>next= LIST_POISON1;

00107:       entry–>prev= LIST_POISON2;

00108: }

00090: staticinlinevoid __list_del(structlist_head* prev,structlist_head* next)

00091: {

00092:       next–>prev= prev;

00093:       prev–>next= next;

00094: }

00095:

list_del()是对__list_del()的封装，参数为要删除的结点。

list_del_init()为将entry结点删除后，并将entry结点初始化称为一个独立结点，它的prev和next指针都指向自身。

                                                                                                       图5 __list_del()示意图

大家可能会对结点删除函数的操作产生疑问：删除一个结点仅仅是改变指针，而没有释放被删除结点的内存空间，这样岂不是导致内存泄漏？事实上，Linux内核中的双链表仅仅是将相关数据结构组织起来，而不去关心内存空间是否已经分配和释放内存空间。

4 链表遍历

这里我们不必关心prefetch()函数的意义，简单理解成空操作即可。宏list_for_each(pos,head)的含义为除头结点外，遍历所有的结点。前面提到Linux内核中的双链表是带头结点的双循环链表，头结点和其他结点的数据类型往往不一致，故遍历时并不遍历头结点。

宏list_for_each_prev(pos, head)是反向（从尾结点开始）遍历整个链表。

00362: /**

00363:  *list_for_each   –      iterateoveralist

00364:  *@pos:the&structlist_headtouseasaloopcursor.

00365:  *@head:    theheadforyourlist.

00366:  */

00367: #definelist_for_each(pos,  head)\

00368:       for(pos=(head)–>next;prefetch(pos–>next),pos!=(head);\

00369:               pos=pos–>next)

00370:

00381: #define__list_for_each(pos,  head)\

00382:       for(pos=(head)–>next;pos!=(head);pos=pos–>next)

00383:

00384: /**

00385:  *list_for_each_prev  –      iterateoveralistbackwards

00386:  *@pos:the&structlist_headtouseasaloopcursor.

00387:  *@head:    theheadforyourlist.

00388:  */

00389: #definelist_for_each_prev(pos,  head)\

00390:       for(pos=(head)–>prev;prefetch(pos–>prev),pos!=(head);\

00391:               pos=pos–>prev)

00392:

00393: /**

00394:  *list_for_each_safe-iterateoveralistsafeagainstremovaloflistentry

00395:  *@pos:the&structlist_headtouseasaloopcursor.

00396:  *@n:         another&structlist_headtouseastemporarystorage

00397:  *@head:    theheadforyourlist.

00398:  */

00399: #definelist_for_each_safe(pos,  n,  head)\

00400:       for(pos=(head)–>next,n=pos–>next;pos!=(head);\

00401:               pos=n,n=pos–>next)

00402:

00403: /**

00404:  *list_for_each_prev_safe-iterateoveralistbackwardssafeagainstremovaloflistentry

00405:  *@pos:the&structlist_headtouseasaloopcursor.

00406:  *@n:         another&structlist_headtouseastemporarystorage

00407:  *@head:    theheadforyourlist.

00408:  */

00409: #definelist_for_each_prev_safe(pos,  n,  head)\

00410:       for(pos=(head)–>prev,n=pos–>prev;\

00411:            prefetch(pos–>prev),pos!=(head);\

00412:            pos=n,n=pos–>prev)