整理一个双向链表list.h

我的程序代码 2.3k 字 次

一直觉得Linux内核的双向链表是十分巧妙的设计，它的实现方式与数据结构课程上讲的完全不同。内核list实现依赖于GCC的扩展，在其它平台不一定能正常运行。在内核中，一般是结构体中使用链表成员，而不是像数据结构课那样在链表结构体中使用数据域。C++中将lsit作为模板，能应用于各种类型数据上，但Linux内核无法使用，因而使用其它手段实现，方便扩展。事实上，内核大量结构体都使用了list。网上有很多关于此方面的介绍，就不展开说了。

最近在研究hostapd，里面用到了双向链表，但与内核实现的有些许不同。就将其抽出，并修改了一下。
完整的list.h头文件如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
/*
 * Doubly linked list
 * Copyright (c) 2016 Late Lee <latelee@163.com>
 *
 * for C&C++, M$ or GNU
 *
 */
 
#ifndef LL__LIST_H
#define LL__LIST_H
 
#ifdef __cplusplus
extern "C" {
#endif
 
struct list_head {
    struct list_head *next;
    struct list_head *prev;
};
 
#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;
}
 
static inline void __list_add(struct list_head *item,
                 struct list_head *prev,
                 struct list_head *next)
{
    prev->next = item;
    item->prev = prev;
    next->prev = item;
    item->next = next;
}
 
static inline void list_add_tail(struct list_head *item,
                    struct list_head *head)
{
    __list_add(item, head->prev, head);
}
 
static inline void list_add_head(struct list_head *item,
                    struct list_head *head)
{
    __list_add(item, head, head->next);
}
 
static inline void list_add(struct list_head *item,
                    struct list_head *head)
{
    __list_add(item, head, head->next);
}
 
static inline void list_add_prev(struct list_head *item,
                    struct list_head *head)
{
    __list_add(item, head->prev, head);
}
 
static inline void list_del(struct list_head *item)
{
    item->next->prev = item->prev;
    item->prev->next = item->next;
    item->next = NULL;
    item->prev = NULL;
}
 
static inline int list_empty(struct list_head *list)
{
    return list->next == list;
}
 
static inline unsigned int list_length(struct list_head *list)
{
    struct list_head *item;
    int count = 0;
    for (item = list->next; item != list; item = item->next)
        count++;
    return count;
}
 
#ifndef offsetof
#define offsetof(type, member) ((long) &((type *) 0)->member)
#endif
 
#ifndef container_of
#define container_of(ptr, type, member) \
    ((type *) ((char *) ptr - offsetof(type, member)))
#endif
 
#define list_entry container_of
 
#define list_first_entry(list, type, member) \
    (list_empty((list)) ? NULL : \
     list_entry((list)->next, type, member))
 
#define list_last_entry(list, type, member) \
    (list_empty((list)) ? NULL : \
     list_entry((list)->prev, type, member))
 
#define list_entry_prev list_last_entry
 
#define list_entry_next list_first_entry
 
#define list_for_each(item, list, type, member) \
    for (item = list_entry((list)->next, type, member); \
         &item->member != (list); \
         item = list_entry(item->member.next, type, member))
 
#define list_for_each_safe(item, n, list, type, member) \
    for (item = list_entry((list)->next,type, member), \
             n = list_entry(item->member.next, type, member); \
         &item->member != (list); \
         item = n, n = list_entry(n->member.next, type, member))
 
#define llist_for_each_reverse(item, list, type, member) \
    for (item = list_entry((list)->prev, type, member); \
         &item->member != (list); \
         item = list_entry(item->member.prev, type, member))
 
#ifdef __cplusplus
}
#endif
 
#endif /* LL__LIST_H */

使用用示例如下(具体见测试代码实现)：

1、定义链表：

1
LIST_HEAD(my_list);

2、插入：

1
list_add_tail(&devinfo->list, &my_list);

3、删除：

1
list_del(&devinfo->list);

注意，list_del只是将要删除的结点的指针置为空，该结点还没有被删除，所以要自行释放。

4、遍历：

1
list_for_each_safe(tdev, tmpdev, &my_list, struct i2c_devinfo, list)

在遍历时使用的list_for_each_safe和内核版本的list_for_each_entry_safe有不同：list_for_each_entry_safe(tdev, tmpdev, &my_list, list)。内核版本list少了结构体的类型struct i2c_devinfo，这是因为使用了typeof关键字，这个关键字有些编译器不支持，所以上面的实现就让使用者明式传递结构体类型。

5、获取链表数据项

1
2
list_entry(my_list.prev, struct i2c_devinfo, list); 
list_entry(my_list.next, struct i2c_devinfo, list);

my_list的prev指针即为最后一个结点，而next是第一个结点。list_first_entry和list_last_entry就是如此实现的。

上述代码基本上实现了链表的插入(包含前插入、后插入 ^_^)、删除、遍历。为了避免使用typeof，个别函数实现与内核的list多了参数，但能在GCC和MS的VS2010环境下编译通过，运行效果一致，达到跨平台的目标。

完整的测试代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
 /**
双向链表示例。演示创建、遍历、删除等操作。
g++ 5.8.4 & VS2010 测试通过
Late Lee <latelee@163.com> http://www.latelee.org
由hostapd的list源码修改而成 
结构示意图：
list_head
   prev ----------------------------------------------- 
      |                                                |
      -<-                                              |
   next |    node1          node2           node3      |
   ^|   |                                              |
   ||   |   data...         data...         data...    |
   ||   --- prev <--------- prev <--------- prev <-----|
   ||-----> next ---------> next ---------> next ------
   |        data...         data...         data...    |
   |-----<----------------------------------------------
   
头结点不使用，无法用list_entry拿到实际数据
list_head的prev指向最后一个结点，next指向第一个结点。
如果一直用next可遍历并循环到开始处，prev亦然。
注：list_add本身在“结点”后添加，如在list_haed“后”添加，则变成在整个链表开头。
如果在node1“后”添加，则在整个链表的node1后新加结点。
运行结果：
show info in the list.
[0] busnum: 10, slave: 0
[1] busnum: 11, slave: 2
[2] busnum: 12, slave: 4
[3] busnum: 13, slave: 6
[4] busnum: 14, slave: 8
prev entry: 14
next entry: 10
first entry: 10
last entry: 14
show info in the list.
[0] busnum: 1, slave: 25
[1] busnum: 10, slave: 0
[2] busnum: 250, slave: 25
[3] busnum: 11, slave: 2
[4] busnum: 250, slave: 25
[5] busnum: 12, slave: 4
[6] busnum: 14, slave: 8
[7] busnum: 65535, slave: 25
after delete...
list empty, nothing to show.
next1 entry: 1
next2 entry: 2
next3 entry: 0(0x0)
next4 entry: 1
next5 entry: 2
*/
 
#include <stdio.h>
#include <stdlib.h>
 
#include "list.h"
 
struct i2c_devinfo
{
    struct list_head list;
    int busnum;
    int slave;
};
 
// 定义链表
LIST_HEAD(my_list);
 
void init(int busnum, int slave)
{
    struct i2c_devinfo* devinfo;
    // 分配空间
    devinfo = (struct i2c_devinfo*)malloc(sizeof(struct i2c_devinfo));
    if (devinfo == NULL) return;
 
    // 赋值
    devinfo->busnum = busnum;
    devinfo->slave = slave;
 
    // 添加到链接中
    list_add_tail(&devinfo->list, &my_list);
}
 
void show(void)
{
    struct i2c_devinfo *devinfo;
    int i = 0;
 
    if (list_empty(&my_list))
    {
        printf("list empty, nothing to show.\n");
        return;
    }
    printf("show info in the list.\n");
    // 解释：从全局链表my_list中拿到devinfo信息，其中list为devinfo类型的一个成员变量
    //list_for_each(devinfo, &my_list, struct i2c_devinfo, list)
    list_for_each(devinfo, &my_list, struct i2c_devinfo, list)
    {
        printf("[%d] busnum: %d, slave: %d\n", i++, devinfo->busnum, devinfo->slave);
    }
}
 
void delete_list(void)
{
    struct i2c_devinfo *devinfo, *tdev;
    //　注：当要删除链表数据时，要使用*_safe，同时要额外增加一个临时变量
    list_for_each_safe(devinfo, tdev, &my_list, struct i2c_devinfo, list)
    {
        list_del(&devinfo->list);
        free(devinfo);
    }
}
 
void list_misc(void)
{
    struct i2c_devinfo* devinfo, *tdev, *tmpdev;
 
    struct i2c_devinfo* n;
    n = list_entry(my_list.prev, struct i2c_devinfo, list);
    printf("prev entry: %d\n", n->busnum);
    n = list_entry(my_list.next, struct i2c_devinfo, list);
    printf("next entry: %d\n", n->busnum);
 
    // 获取第一个、最后一个
    n = list_first_entry(&my_list, struct i2c_devinfo, list);
    printf("first entry: %d\n", n->busnum);
    n = list_last_entry(&my_list, struct i2c_devinfo, list);
    printf("last entry: %d\n", n->busnum);
    
    // 
    devinfo = (struct i2c_devinfo*)malloc(sizeof(struct i2c_devinfo));
    devinfo->busnum = 1;
    devinfo->slave = 25;
    list_add(&devinfo->list, &my_list); // 在my_list后添加，变成在链表的头部 // note1
    
    devinfo = (struct i2c_devinfo*)malloc(sizeof(struct i2c_devinfo));
    devinfo->busnum = 65535;
    devinfo->slave = 25;
    list_add_tail(&devinfo->list, &my_list); // 在末尾
    
    // 中途插入、删除
    //list_for_each(tdev, &my_list, struct i2c_devinfo, list)
    list_for_each_safe(tdev, tmpdev, &my_list, struct i2c_devinfo, list)
    {
        if (tdev->busnum == 10) // 在此节点后插入
        {
            devinfo = (struct i2c_devinfo*)malloc(sizeof(struct i2c_devinfo));
            devinfo->busnum = 250;
            devinfo->slave = 25;
            list_add(&devinfo->list, &tdev->list); // note2
        }
        if (tdev->busnum == 12) // 在此节点前插入
        {
            devinfo = (struct i2c_devinfo*)malloc(sizeof(struct i2c_devinfo));
            devinfo->busnum = 250;
            devinfo->slave = 25;
            list_add_prev(&devinfo->list, &tdev->list);
        }
        if (tdev->busnum == 13) // 删除此节点
        {
            list_del(&tdev->list);
        }
    }
}
 
// 遍历示例
void list_misc1(void)
{
    LIST_HEAD(my_list);
    struct i2c_devinfo* devinfo;
    
    devinfo = (struct i2c_devinfo*)malloc(sizeof(struct i2c_devinfo));
    devinfo->busnum = 1;
    devinfo->slave = 25;
    list_add_tail(&devinfo->list, &my_list);
    devinfo = (struct i2c_devinfo*)malloc(sizeof(struct i2c_devinfo));
    devinfo->busnum = 2;
    devinfo->slave = 25;
    list_add_tail(&devinfo->list, &my_list);
    
    
    struct i2c_devinfo* n;
    n = list_entry(my_list.next, struct i2c_devinfo, list); // 第一个结点
    printf("next1 entry: %d\n", n->busnum);
    n = list_entry(my_list.next->next, struct i2c_devinfo, list);   // 第二个结点
    printf("next2 entry: %d\n", n->busnum);
    n = list_entry(my_list.next->next->next, struct i2c_devinfo, list); // 回到my_list，此时数据无效
    printf("next3 entry: %d(0x%x)\n", n->busnum, n->busnum);
    n = list_entry(my_list.next->next->next->next, struct i2c_devinfo, list);   // 第一个结点
    printf("next4 entry: %d\n", n->busnum);
    n = list_entry(my_list.next->next->next->next->next, struct i2c_devinfo, list); // 第二个结点
    printf("next5 entry: %d\n", n->busnum);
}
 
int main(void)
{
    int i = 0;
    int j = 0;
    for (i = 10; i < 15; i++, j += 2)
    {
        init(i, j);
    }
 
    show();
 
    list_misc();
    show();
 
    printf("after delete...\n");
    delete_list();
    // 删除链表后，已经没有内容了
    show();
 
    list_misc1();
    return 0;
}

这里说一下note1、note2两处代码的list_add的不同表现，list_add是在链表某结点后面插入新结点，相对地，list_add_tail则是在链表最后插入新结点。在note1处，传递的结点为my_list，从上述代码图示中看出，my_list实际上是头结点，它是不包括真正有数据的结点的，在此“结点”的后面插入新结点，就变成了链表的头部数据。所以后面使用list_for_each_safe遍历时，看到新加的结点位于链表开始处，在此情况下，list_add变成了向前插入新结点。但在note2处并不是使用my_list，而是使用已经存在的链表中的一个结点，当然就是在其后插入结点了。
在函数list_misc1中，只使用next指针进行遍历，能证明my_list的确只是一个头结点。
学好数据结构十分重要，不同应用场合要选择适当的数据结构来解决问题，当熟知并掌握数据结构后，就能胸有成竹。但是，本文仅仅是本着“适用”的目的来使用list，如内核list的合并、旋转等——包括哈希链表，有待后续再研究。因为毕竟不是应试。

李迟 2016.10.19 周三 中午休息前