linux 双链表实现

链表是一种重要的数据结构，应用的非常广泛。链表分为单向链表与双向链表，一般的实现就是在结构体中内嵌指向下一个元素的指针。例如：

struct name ｛
    int num;
    ...;
    struct name *next;
    struct name *prev;
｝

        但是linux内核中的实现确有点特殊他是通过独立定义一个链表结构,通过结构体中内嵌这个结构来完成的，这样就实现了链表的定义与结构体的分离。linux内核中广泛的应用了这种链表，可以这么说，如果没有linux list_head链表就不会有现在linux的强大。本来我就以为只有linux内核用这种链表，但是当我分析完lsusb的代码后，发现这个程序也是用内核链表来组织数据结构的，我想Kroah-Hartman不愧为内核的维护者，连应用程序都带着内核的影子。我就试着在应用程序中使用这种链表，发现他的非常的好用，只要包含list.h，然后在结构体重嵌入这种链表，就能方便的实现数据结构的线性链接。下面我就简单的介绍一下这种链表的实现原理。
        list.h中首先定义了这样一个结构体，这个是链表的基本结构：

struct list_head {
    struct list_head *next, *prev;
};

        我们使用的时候，在自己的结构体中内嵌这个结构就行了，如下;

struct my_struct {
    int a;
    int b;
    ...
    struct list_head list;
}

         这个链表链接起来的不是结构体本身，而是list_head结构。需要一个链表头，这个链表头是list_head结构，不需要内嵌在任何结构中，在使用链表的时候要定义以及初始化这样一个结构。list.h中已经定义了宏用于定义与初始化链表头，如下：

#define LIST_HEAD_INIT(name) { &(name), &(name) }

#define LIST_HEAD(name) \
    struct list_head name = LIST_HEAD_INIT(name)

#define INIT_LIST_HEAD(ptr) do { \
    (ptr)->next = (ptr); (ptr)->prev = (ptr); \
} while (0)

         LIST_HEAD(name)宏用来定义一个链表头，使得他的两个指针都指向自己。我们可以直接在程序的变量声明处，直接调用LIST_HEAD(name)宏，来定义并初始化一个名为name的链表，也可以先声明一个链表，调用INIT_LIST_HEAD来初始化这个链表。从宏定义山看不能直接使用LIST_HEAD_INIT，它只适合声明初始化。
        定义了一个链表后，最重要的操作是向链表添加元素，与删除元素以及遍历链表。下面先说添加元素的操作：

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;
}

static inline void list_add(struct list_head *new, struct list_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);
}

        向链表添加元素只知道链表的头与新的元素地址就可以了，因为链表是双向循环链表，链表头的前一个元素就是这个链表的最后一个元素。list_add是将新元素添加到链表头的后面，而list_add_tail是将心元素添加到链表的尾部，这两个操作如下图所示：

图 1 list_add操作

图 2 list_add_tail操作

        说完了添加元素，下面说一下如何删除链表元素，如下：

static inline void __list_del(struct list_head *prev, struct list_head *next)
{
    next->prev = prev;
    prev->next = next;
}

static inline void list_del(struct list_head *entry)
{
    __list_del(entry->prev, entry->next);
}

        删除链表元素也非常简单，只需要找到前一个元素与后一个元素，将他们链接在一起就可以了。
        list_head链表最重要的特点就是链表操作与结构体分离，用list_head链接的链表结构上如下图所示：

图 3 list_head链表特点

         但是我们使用链表的目的不是链表本身，而是内嵌链表的结构体，我们可以方便的遍历list_head结构，如下：

for ( mylist = mylist_head->next; mylist != mylist_head; mylist = mylist->next);

        但是这样的程序没有什么作用，我们需要的是结构体。所以需要一种技术使得由list_head的地址找到内嵌他的结构提的地址，这个技术就是内核中顶顶大名的container_of宏，这个宏就是list_head链表的精髓，它的初衷是为了实现由结构体的元素的地址而找到结构体首地址。借鉴这种技术就可以实现我们的目的。如下：

#define list_entry(ptr, type, member) \
    ((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))

        这个宏实现非常的简单，但是往往伟大的思想就蕴藏在简单的代码中，我们来分析一下这个宏。首先他是一个带参数的宏，有三个参数第一个参数是一个地址，他是结构体中元素的地址，第二个参数是结构体类型，第三个参数是，元素在结构体中的名字。我们以list_head链表为例来说明。例如有如下结构：

struct my_struct {
    int a;
    char b;
    ...
    strcut list_head list;
}

        我们知道了里面的list_head元素的地址为plist，需要找到类型问struct my_struct结构变量的地址。就需要这样调用宏
struct my_struct *ptr = list_entry(plist, struct my_struct, list);
        list_entry宏实现的非常巧妙，括号比较多，让我们将这个宏分解来看。
((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))
        最外面的一层括号可以去掉，这是为了防止宏扩展的，去掉如下：
(type *) ((char *)(ptr)-(unsigned long)(&((type *)0)->member))
        现在就比较清楚了，首先(type *)是C强制转换操作，就是将后面的的数据转化成type结构的指针。而后面的操作可以再分解
(char *)(ptr) - (unsigned long)(&((type *)0)->member)
        这样就是一个减法的操作，前面是一个指针，我们传过去的结构体元素的指针，这里被转化成指向字符的。而后面是一个长整形，可以再分解
(unsigned long) (&((type *)0)->member)
        显然这个长整形是一个指针转化的，而这个指针又可以再分解，
&((type *)0)->member
       可以看出这个指针是一个变量取地址得到的，这个变量又是什么呢
((type *)0)->member 
       看起来有点奇怪，不过这个操作是整个宏中最精妙的，他将地址0转化成type类型，接下来又取得这个结构的member元素，member就是我们传进来的参数：元素在结构体中的命名。其实((type *)0)->member取的变量是内容是什么一点都不重要，重要的我们要取这个变量的地址。取完这个地址将它转换成unsigned long类型，这样这个数据就是((type *)0)->member相对与地址0的偏移。回到上面的那个减法，将结构体中元素的地址与他与结构体首地址的偏移相减，不就得到了结构体的地址了吗。整个操作如下图所示：

图 4 list_entry 宏

双向链表在Linux内核中的实现

    Linux内核对双向循环链表的设计非常巧妙，链表的所有运算都基于只有两个指针域的list_head结构体来进行。 

[cpp] view plaincopyprint?

1.   
2. struct list_head {  
3.     struct list_head *next, *prev;  
4. };  

    链表的运算（源代码都在linux-2.6.38.8/include/linux/list.h文件中定义，并且假定CONFIG_DEBUG_LIST未定义）：

    （1）、链表头结点的创建

    2.1.1 静态创建 

[cpp] view plaincopyprint?

1. #define LIST_HEAD_INIT(name) { &(name), &(name) }   
2.   
3. #define LIST_HEAD(name) \   
4.     struct list_head name = LIST_HEAD_INIT(name)  

    通过LIST_HEAD宏创建一个list_head结构体变量name，并把name的所有成员（next和prev）都初始化为name的首地址。 

    2.1.2 动态创建 

[cpp] view plaincopyprint?

1. static inline void INIT_LIST_HEAD(struct list_head *list)  
2. {  
3.     list->next = list;  
4.     list->prev = list;  
5. }  

    把list_head结构体变量的首地址传递给INIT_LIST_HEAD函数来对其成员进行初始化。

    （2）、结点的添加

    list_add函数是把新结点new添加到head结点的后面，而list_add_tail函数是把新结点new插入到结点head的前面。

    函数源代码如下： 

[cpp] view plaincopyprint?

1. static inline void __list_add(struct list_head *new,  
2.                   struct list_head *prev,  
3.                   struct list_head *next)  
4. {  
5.     next->prev = new;  
6.     new->next = next;  
7.     new->prev = prev;  
8.     prev->next = new;  
9. }  
10. static inline void list_add(struct list_head *new, struct list_head *head)  
11. {  
12.     __list_add(new, head, head->next);  
13. }  
14. static inline void list_add_tail(struct list_head *new, struct list_head *head)  
15. {  
16.     __list_add(new, head->prev, head);  
17. }  

    图示如下：

 

    （3）、结点的删除

    list_del函数的作用是将结点*entry从链表中移走，并把此结点的两个成员分别初始化为LIST_POISON1和LIST_POISON2。注意，这里的*entry结点所占用的内存并没有被释放。

    list_del_init函数的作用也是将结点*entry从链表中移走，但它把此结点的两个成员初始化为entry。 

[cpp] view plaincopyprint?

1. static inline void __list_del(struct list_head * prev, struct list_head * next)  
2. {  
3.     next->prev = prev;  
4.     prev->next = next;  
5. }  
6. static inline void __list_del_entry(struct list_head *entry)  
7. {  
8.     __list_del(entry->prev, entry->next);  
9. }  
10.   
11. static inline void list_del(struct list_head *entry)  
12. {  
13.     __list_del(entry->prev, entry->next);  
14.     entry->next = LIST_POISON1;  
15.     entry->prev = LIST_POISON2;  
16. }  
17. static inline void list_del_init(struct list_head *entry)  
18. {  
19.     __list_del_entry(entry);  
20.     INIT_LIST_HEAD(entry);  
21. }  

    LIST_POISON1和LIST_POISON2的值定义在linux-2.6.38.8/include/linux/poison.h文件中： 

[cpp] view plaincopyprint?

1. #define LIST_POISON1  ((void *) 0x00100100 + POISON_POINTER_DELTA)   
2. #define LIST_POISON2  ((void *) 0x00200200 + POISON_POINTER_DELTA)  

    其中POISON_POINTER_DELTA的值在CONFIG_ILLEGAL_POINTER_VALUE未配置时为0。

    （4）、结点的替换

    list_replace函数的作用是用结点*new替换掉结点*old，list_replace_init函数的作用与list_replace相同，除了它还会把*old结点的两个成员初始化为old外。 

[cpp] view plaincopyprint?

1. static inline void list_replace(struct list_head *old,  
2.                 struct list_head *new)  
3. {  
4.     new->next = old->next;  
5.     new->next->prev = new;  
6.     new->prev = old->prev;  
7.     new->prev->next = new;  
8. }  
9.   
10. static inline void list_replace_init(struct list_head *old,  
11.                     struct list_head *new)  
12. {  
13.     list_replace(old, new);  
14.     INIT_LIST_HEAD(old);  
15. }  

     （5）、结点的移动

    list_move函数的作用是把*list结点从它所在的链表中移除，然后把它添加到*head结点的后面。list_move_tail函数的作用与list_move相同，但它把*list插入到*head结点的前面。 

[cpp] view plaincopyprint?

1. static inline void list_move(struct list_head *list, struct list_head *head)  
2. {  
3.     __list_del_entry(list);  
4.     list_add(list, head);  
5. }  
6. static inline void list_move_tail(struct list_head *list,  
7.                   struct list_head *head)  
8. {  
9.     __list_del_entry(list);  
10.     list_add_tail(list, head);  
11. }  

    （6）、判断*list是否是链表head的最后一个结点，是则返回1，否则返回0 

[cpp] view plaincopyprint?

1. static inline int list_is_last(const struct list_head *list,  
2.                 const struct list_head *head)  
3. {  
4.     return list->next == head;  
5. }  

    （7）、判断head是否为空表，是则返回1，否则返回0 

[cpp] view plaincopyprint?

1. static inline int list_empty(const struct list_head *head)  
2. {  
3.     return head->next == head;  
4. }  
5. static inline int list_empty_careful(const struct list_head *head)  
6. {  
7.     struct list_head *next = head->next;  
8.     return (next == head) && (next == head->prev);  
9. }  

    （8）、翻转链表 

[cpp] view plaincopyprint?

1. static inline void list_rotate_left(struct list_head *head)  
2. {  
3.     struct list_head *first;  
4.   
5.     if (!list_empty(head)) {  
6.         first = head->next;  
7.         list_move_tail(first, head);  
8.     }  
9. }  

    （9）、判断链表是否只有一个结点，是则返回1，否则返回0 

[cpp] view plaincopyprint?

1. static inline int list_is_singular(const struct list_head *head)  
2. {  
3.     return !list_empty(head) && (head->next == head->prev);  
4. }  

    （10）、切割链表

    list_cut_position函数的功能是将链表head从头结点head（不包含）开始到entry（包含，并且它是链表head中的结点）结点结束之间的所有结点都切割下来，并添加到list上，以组成一个新的链表list。原来的head链表将组成一个新的小链表。 

[cpp] view plaincopyprint?

1. static inline void __list_cut_position(struct list_head *list,  
2.         struct list_head *head, struct list_head *entry)  
3. {  
4.     struct list_head *new_first = entry->next;  
5.     list->next = head->next;  
6.     list->next->prev = list;  
7.     list->prev = entry;  
8.     entry->next = list;  
9.     head->next = new_first;  
10.     new_first->prev = head;  
11. }  
12. static inline void list_cut_position(struct list_head *list,  
13.         struct list_head *head, struct list_head *entry)  
14. {  
15.     if (list_empty(head))  
16.         return;  
17.     if (list_is_singular(head) &&  
18.         (head->next != entry && head != entry))  
19.         return;  
20.     if (entry == head)  
21.         INIT_LIST_HEAD(list);  
22.     else  
23.         __list_cut_position(list, head, entry);  
24. }  

    （11）、合并链表

    list_splice函数的作用是将链表list（不包含结点*list）插入到链表head的head结点后，而list_splice_tail函数的作用是将链表list（不包含结点*list）插入到链表head的head结点前。

    list_splice_init和list_splice_tail_init函数的作用与其相应的函数相同，除了它们都初始化*list结点为list。 

[cpp] view plaincopyprint?

1. static inline void __list_splice(const struct list_head *list,  
2.                  struct list_head *prev,  
3.                  struct list_head *next)  
4. {  
5.     struct list_head *first = list->next;  
6.     struct list_head *last = list->prev;  
7.   
8.     first->prev = prev;  
9.     prev->next = first;  
10.   
11.     last->next = next;  
12.     next->prev = last;  
13. }  
14. static inline void list_splice(const struct list_head *list,  
15.                 struct list_head *head)  
16. {  
17.     if (!list_empty(list))  
18.         __list_splice(list, head, head->next);  
19. }  
20. static inline void list_splice_tail(struct list_head *list,  
21.                 struct list_head *head)  
22. {  
23.     if (!list_empty(list))  
24.         __list_splice(list, head->prev, head);  
25. }  
26. static inline void list_splice_init(struct list_head *list,  
27.                     struct list_head *head)  
28. {  
29.     if (!list_empty(list)) {  
30.         __list_splice(list, head, head->next);  
31.         INIT_LIST_HEAD(list);  
32.     }  
33. }  
34. static inline void list_splice_tail_init(struct list_head *list,  
35.                      struct list_head *head)  
36. {  
37.     if (!list_empty(list)) {  
38.         __list_splice(list, head->prev, head);  
39.         INIT_LIST_HEAD(list);  
40.     }  
41. }  

    （12）、通过成员指针获得整个结构体的指针

    链表操作如果仅仅针对list_head结构体就没有什么意义，所以必须要获得包含它的整个结构体的地址。它们只是对container_of宏的封装，关于container_of宏的使用方法请参考http://blog.csdn.net/npy_lp/article/details/7010752。 

[cpp] view plaincopyprint?

1. #define list_entry(ptr, type, member) \   
2.     container_of(ptr, type, member)  
3. #define list_first_entry(ptr, type, member) \   
4.     list_entry((ptr)->next, type, member)  

    （13）、遍历链表

    list_for_each函数是根据list_head的next成员来遍历整个链表，而list_for_each_prev函数是根据prev成员。其中参数head一般是链表的头结点。 

[cpp] view plaincopyprint?

1. #define list_for_each(pos, head) \   
2.     for (pos = (head)->next; prefetch(pos->next), pos != (head); \  
3.             pos = pos->next)  
4. #define __list_for_each(pos, head) \   
5.     for (pos = (head)->next; pos != (head); pos = pos->next)  
6. #define list_for_each_prev(pos, head) \   
7.     for (pos = (head)->prev; prefetch(pos->prev), pos != (head); \  
8.             pos = pos->prev)  

    list_for_each_safe和list_for_each_prev_safe函数使用list_head结构体变量n作为临时存储变量。 

[cpp] view plaincopyprint?

1. #define list_for_each_safe(pos, n, head) \   
2.     for (pos = (head)->next, n = pos->next; pos != (head); \  
3.         pos = n, n = pos->next)  
4. #define list_for_each_prev_safe(pos, n, head) \   
5.     for (pos = (head)->prev, n = pos->prev; \  
6.          prefetch(pos->prev), pos != (head); \  
7.          pos = n, n = pos->prev)  

    list_for_each_entry和list_for_each_entry_reverse函数的作用是根据head的下一个或前一个结点来遍历整个head链表，并返回包含list_head结构体成员的大结构体指针，member是list_head结构体在大结构体中的成员名。 

[cpp] view plaincopyprint?

1. #define list_for_each_entry(pos, head, member)              \   
2.     for (pos = list_entry((head)->next, typeof(*pos), member);   \  
3.          prefetch(pos->member.next), &pos->member != (head);  \  
4.          pos = list_entry(pos->member.next, typeof(*pos), member))  
5. #define list_for_each_entry_reverse(pos, head, member)          \   
6.     for (pos = list_entry((head)->prev, typeof(*pos), member);   \  
7.          prefetch(pos->member.prev), &pos->member != (head);  \  
8.          pos = list_entry(pos->member.prev, typeof(*pos), member))  

    list_for_each_entry_continue和list_for_each_entry_continue_reverse函数是以pos的下一个或前一个结点开始遍历链表head。 

[cpp] view plaincopyprint?

1. #define list_prepare_entry(pos, head, member) \   
2.     ((pos) ? : list_entry(head, typeof(*pos), member))  
3. #define list_for_each_entry_continue(pos, head, member)         \   
4.     for (pos = list_entry(pos->member.next, typeof(*pos), member);   \  
5.          prefetch(pos->member.next), &pos->member != (head);  \  
6.          pos = list_entry(pos->member.next, typeof(*pos), member))  
7. #define list_for_each_entry_continue_reverse(pos, head, member)     \   
8.     for (pos = list_entry(pos->member.prev, typeof(*pos), member);   \  
9.          prefetch(pos->member.prev), &pos->member != (head);  \  
10.          pos = list_entry(pos->member.prev, typeof(*pos), member))  

    list_for_each_entry_from函数以当前结点pos开始遍历。 

[cpp] view plaincopyprint?

1. #define list_for_each_entry_from(pos, head, member)             \   
2.     for (; prefetch(pos->member.next), &pos->member != (head);    \  
3.          pos = list_entry(pos->member.next, typeof(*pos), member))  

    list_for_each_entry_safe、list_for_each_entry_safe_continue、list_for_each_entry_safe_from和list_for_each_entry_safe_reverse这四个函数中的n参数与pos的数据类型相同，其他功能与它们相应的函数是相同的。 

[cpp] view plaincopyprint?

1. #define list_for_each_entry_safe(pos, n, head, member)          \   
2.     for (pos = list_entry((head)->next, typeof(*pos), member),   \  
3.         n = list_entry(pos->member.next, typeof(*pos), member);  \  
4.          &pos->member != (head);                     \  
5.          pos = n, n = list_entry(n->member.next, typeof(*n), member))  
6. #define list_for_each_entry_safe_continue(pos, n, head, member)         \   
7.     for (pos = list_entry(pos->member.next, typeof(*pos), member),       \  
8.         n = list_entry(pos->member.next, typeof(*pos), member);      \  
9.          &pos->member != (head);                     \  
10.          pos = n, n = list_entry(n->member.next, typeof(*n), member))  
11. #define list_for_each_entry_safe_from(pos, n, head, member)             \   
12.     for (n = list_entry(pos->member.next, typeof(*pos), member);     \  
13.          &pos->member != (head);                     \  
14.          pos = n, n = list_entry(n->member.next, typeof(*n), member))  
15. #define list_for_each_entry_safe_reverse(pos, n, head, member)      \   
16.     for (pos = list_entry((head)->prev, typeof(*pos), member),   \  
17.         n = list_entry(pos->member.prev, typeof(*pos), member);  \  
18.          &pos->member != (head);                     \  
19.          pos = n, n = list_entry(n->member.prev, typeof(*n), member))  

    list_safe_reset_next函数的作用是根据结点pos获得n。 

[cpp] view plaincopyprint?

1. #define list_safe_reset_next(pos, n, member)                \   
2.     n = list_entry(pos->member.next, typeof(*pos), member)