Linux內核數據結構之鏈表

1、前言

　　 最近寫代碼需用到鏈表結構，正好公共庫有關於鏈表的。第一眼看時，覺得有點新鮮，和我之前見到的鏈表結構不一樣，只有前驅和後繼指針，而沒有數據域。後來看代碼注釋發現該代碼來自linux內核，在linux源代碼下include/Lish.h下。這個鏈表具備通用性，使用非常方便。只需要在結構定義一個鏈表結構就可以使用。

2、鏈表介紹

　　鏈表是非常基本的數據結構，根據鏈個數分為單鏈表、雙鏈表，根據是否循環分為單向鏈表和循環鏈表。通常定義定義鏈表結構如下：

typedef struct node
{
     ElemType data;      //數據域
     struct node *next;  //指針域
}node, *list;

鏈表中包含數據域和指針域。鏈表通常包含一個頭結點，不存放數據，方便鏈表操作。單向循環鏈表結構如下圖所示：

雙向循環鏈表結構如下圖所示：

　　這樣帶數據域的鏈表降低了鏈表的通用性，不容易擴展。linux內核定義的鏈表結構不帶數據域，只需要兩個指針完成鏈表的操作。將鏈表節點加入數據結構，具備非常高的擴展性，通用性。鏈表結構定義如下所示：

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

鏈表結構如下所示：

　　需要用鏈表結構時，只需要在結構體中定義一個鏈表類型的數據即可。例如定義一個app_info鏈表，

1 typedef struct application_info
2 {
3     uint32_t  app_id;
4     uint32_t  up_flow;
5     uint32_t  down_flow;
6     struct    list_head app_info_head;  //鏈表節點
7 }app_info;

定義一個app_info鏈表，app_info app_info_list;通過app_info_head進行鏈表操作。根據C語言指針操作，通過container_of和offsetof，可以根據app_info_head的地址找出app_info的起始地址，即一個完整ap_info結構的起始地址。可以參考： http://www.linuxidc.com/Linux/2016-12/137930.htm 。

3、linux內核鏈表實現

　　內核實現的是雙向循環鏈表，提供了鏈表操作的基本功能。

（1）初始化鏈表頭結點

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

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

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

LIST_HEAD宏創建一個鏈表頭結點，並用LIST_HEAD_INIT宏對頭結點進行賦值，使得頭結點的前驅和後繼指向自己。

INIT_LIST_HEAD函數對鏈表進行初始化，使得前驅和後繼指針指針指向頭結點。

（2）插入節點

 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 
11 static inline void list_add(struct list_head *new, struct list_head *head)
12 {
13     __list_add(new, head, head->next);
14 }
15 
16 static inline void list_add_tail(struct list_head *new, struct list_head *head)
17 {
18     __list_add(new, head->prev, head);
19 }

　　插入節點分為從鏈表頭部插入list_add和鏈表尾部插入list_add_tail，通過調用__list_add函數進行實現，head->next指向之一個節點，head->prev指向尾部節點。

（3）刪除節點

 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 
 7 static inline void list_del(struct list_head *entry)
 8 {
 9     __list_del(entry->prev, entry->next);
10     entry->next = LIST_POISON1;
11     entry->prev = LIST_POISON2;
12 }

　　從鏈表中刪除一個節點，需要改變該節點前驅節點的後繼結點和後繼結點的前驅節點。最後設置該節點的前驅節點和後繼結點指向LIST_POSITION1和LIST_POSITION2兩個特殊值，這樣設置是為了保證不在鏈表中的節點項不可訪問，對LIST_POSITION1和LIST_POSITION2的訪問都將引起頁故障

/*
 * These are non-NULL pointers that will result in page faults
 * under normal circumstances, used to verify that nobody uses
 * non-initialized list entries.
 */
#define LIST_POISON1  ((void *) 0x00100100 + POISON_POINTER_DELTA)
#define LIST_POISON2  ((void *) 0x00200200 + POISON_POINTER_DELTA)

（4）移動節點

 1 /**
 2  * list_move - delete from one list and add as another's head
 3  * @list: the entry to move
 4  * @head: the head that will precede our entry
 5  */
 6 static inline void list_move(struct list_head *list, struct list_head *head)
 7 {
 8     __list_del(list->prev, list->next);
 9     list_add(list, head);
10 }
11 
12 /**
13  * list_move_tail - delete from one list and add as another's tail
14  * @list: the entry to move
15  * @head: the head that will follow our entry
16  */
17 static inline void list_move_tail(struct list_head *list,
18                   struct list_head *head)
19 {
20     __list_del(list->prev, list->next);
21     list_add_tail(list, head);
22 }

move將一個節點移動到頭部或者尾部。

（5）判斷鏈表

 1 /**
 2  * list_is_last - tests whether @list is the last entry in list @head
 3  * @list: the entry to test
 4  * @head: the head of the list
 5  */
 6 static inline int list_is_last(const struct list_head *list,
 7                 const struct list_head *head)
 8 {
 9     return list->next == head;
10 }
11 
12 /**
13  * list_empty - tests whether a list is empty
14  * @head: the list to test.
15  */
16 static inline int list_empty(const struct list_head *head)
17 {
18     return head->next == head;
19 }

list_is_last函數判斷節點是否為末尾節點，list_empty判斷鏈表是否為空。

（6）遍歷鏈表

 1 /**
 2  * list_entry - get the struct for this entry
 3  * @ptr:    the &struct list_head pointer.
 4  * @type:    the type of the struct this is embedded in.
 5  * @member:    the name of the list_struct within the struct.
 6  */
 7 #define list_entry(ptr, type, member) \
 8     container_of(ptr, type, member)
 9 
10 /**
11  * list_first_entry - get the first element from a list
12  * @ptr:    the list head to take the element from.
13  * @type:    the type of the struct this is embedded in.
14  * @member:    the name of the list_struct within the struct.
15  *
16  * Note, that list is expected to be not empty.
17  */
18 #define list_first_entry(ptr, type, member) \
19     list_entry((ptr)->next, type, member)
20 
21 /**
22  * list_for_each    -    iterate over a list
23  * @pos:    the &struct list_head to use as a loop cursor.
24  * @head:    the head for your list.
25  */
26 #define list_for_each(pos, head) \
27     for (pos = (head)->next; prefetch(pos->next), pos != (head); \
28             pos = pos->next)

宏list_entity獲取鏈表的結構，包括數據域。list_first_entry獲取鏈表第一個節點，包括數據源。list_for_each宏對鏈表節點進行遍歷。

4、測試例子

編寫一個簡單使用鏈表的程序，從而掌握鏈表的使用。

自定義個類似的list結構如下所示：mylist.h

 1 # define POISON_POINTER_DELTA 0
 2 
 3 #define LIST_POISON1  ((void *) 0x00100100 + POISON_POINTER_DELTA)
 4 #define LIST_POISON2  ((void *) 0x00200200 + POISON_POINTER_DELTA)
 5 
 6 //計算member在type中的位置
 7 #define offsetof(type, member)  (size_t)(&((type*)0)->member)
 8 //根據member的地址獲取type的起始地址
 9 #define container_of(ptr, type, member) ({          \
10         const typeof(((type *)0)->member)*__mptr = (ptr);    \
11     (type *)((char *)__mptr - offsetof(type, member)); })
12 
13 //鏈表結構
14 struct list_head
15 {
16     struct list_head *prev;
17     struct list_head *next;
18 };
19 
20 static inline void init_list_head(struct list_head *list)
21 {
22     list->prev = list;
23     list->next = list;
24 }
25 
26 static inline void __list_add(struct list_head *new,
27     struct list_head *prev, struct list_head *next)
28 {
29     prev->next = new;
30     new->prev = prev;
31     new->next = next;
32     next->prev = new;
33 }
34 
35 //從頭部添加
36 static inline void list_add(struct list_head *new , struct list_head *head)
37 {
38     __list_add(new, head, head->next);
39 }
40 //從尾部添加
41 static inline void list_add_tail(struct list_head *new, struct list_head *head)
42 {
43     __list_add(new, head->prev, head);
44 }
45 
46 static inline  void __list_del(struct list_head *prev, struct list_head *next)
47 {
48     prev->next = next;
49     next->prev = prev;
50 }
51 
52 static inline void list_del(struct list_head *entry)
53 {
54     __list_del(entry->prev, entry->next);
55     entry->next = LIST_POISON1;
56     entry->prev = LIST_POISON2;
57 }
58 
59 static inline void list_move(struct list_head *list, struct list_head *head)
60 {
61         __list_del(list->prev, list->next);
62         list_add(list, head);
63 }
64 
65 static inline void list_move_tail(struct list_head *list,
66                       struct list_head *head)
67 {
68         __list_del(list->prev, list->next);
69         list_add_tail(list, head);
70 }
71 #define list_entry(ptr, type, member) \
72     container_of(ptr, type, member)
73 
74 #define list_first_entry(ptr, type, member) \
75     list_entry((ptr)->next, type, member)
76 
77 #define list_for_each(pos, head) \
78     for (pos = (head)->next; pos != (head); pos = pos->next)

mylist.c如下所示：

 1 /**@brief 練習使用linux內核鏈表，功能包括：
 2  * 定義鏈表結構，創建鏈表、插入節點、刪除節點、移動節點、遍歷節點
 3  *
 4  *@auther Anker @date 2013-12-15
 5  **/
 6 #include <stdio.h>
 7 #include <inttypes.h>
 8 #include <stdlib.h>
 9 #include <errno.h>
10 #include "mylist.h"
11 //定義app_info鏈表結構
12 typedef struct application_info
13 {
14     uint32_t  app_id;
15     uint32_t  up_flow;
16     uint32_t  down_flow;
17     struct    list_head app_info_node;//鏈表節點
18 }app_info;
19 
20 
21 app_info* get_app_info(uint32_t app_id, uint32_t up_flow, uint32_t down_flow)
22 {
23     app_info *app = (app_info*)malloc(sizeof(app_info));
24     if (app == NULL)
25     {
26     fprintf(stderr, "Failed to malloc memory, errno:%u, reason:%s\n",
27         errno, strerror(errno));
28     return NULL;
29     }
30     app->app_id = app_id;
31     app->up_flow = up_flow;
32     app->down_flow = down_flow;
33     return app;
34 }
35 static void for_each_app(const struct list_head *head)
36 {
37     struct list_head *pos;
38     app_info *app;
39     //遍歷鏈表
40     list_for_each(pos, head)
41     {
42     app = list_entry(pos, app_info, app_info_node);
43     printf("ap_id: %u\tup_flow: %u\tdown_flow: %u\n",
44         app->app_id, app->up_flow, app->down_flow);
45 
46     }
47 }
48 
49 void destroy_app_list(struct list_head *head)
50 {
51     struct list_head *pos = head->next;
52     struct list_head *tmp = NULL;
53     while (pos != head)
54     {
55     tmp = pos->next;
56     list_del(pos);
57     pos = tmp;
58     }
59 }
60 
61 
62 int main()
63 {
64     //創建一個app_info
65     app_info * app_info_list = (app_info*)malloc(sizeof(app_info));
66     app_info *app;
67     if (app_info_list == NULL)
68     {
69     fprintf(stderr, "Failed to malloc memory, errno:%u, reason:%s\n",
70         errno, strerror(errno));
71     return -1;
72     }
73     //初始化鏈表頭部
74     struct list_head *head = &app_info_list->app_info_node;
75     init_list_head(head);
76     //插入三個app_info
77     app = get_app_info(1001, 100, 200);
78     list_add_tail(&app->app_info_node, head);
79     app = get_app_info(1002, 80, 100);
80     list_add_tail(&app->app_info_node, head);
81     app = get_app_info(1003, 90, 120);
82     list_add_tail(&app->app_info_node, head);
83     printf("After insert three app_info: \n");
84     for_each_app(head);
85     //將第一個節點移到末尾
86     printf("Move first node to tail:\n");
87     list_move_tail(head->next, head);
88     for_each_app(head);
89     //刪除最後一個節點
90     printf("Delete the last node:\n");
91     list_del(head->prev);
92     for_each_app(head);
93     destroy_app_list(head);
94     free(app_info_list);
95     return 0;
96 }

測試結果如下所示：