浅谈list.h头⽂件之双向循环链表
这两天看了下/usr/src/linux/list.h⽂件，感受颇多，⾥⾯主要讲了两种链表：双向循环链表和哈希链表，以及他们的⼀些基本的操作！下⾯来和⼤家分享下我的分析过程：（申明：我以下分析基于的内
核版本是：2.6.32-24）
19 struct list_head {
20 struct list_head *next, *prev;
21 };
这⾥定义了⼀个list_head的结构体，它是双向循环链表的节点结构体，⾥⾯并⽆数据成员，就只有两个指向list_head型结构体的指针，分别指向其前驱节点和后继节点，因此，这个结构体的主要作⽤就
是嵌套在其他结构体的定义中起到链接作⽤。例如：
struct student{
int id;
char name[20];
struct list_head member;
};
member是⼀个list_head型的结构体，同时⼜是student型结构体的成员，利⽤member.prev和就可以访问到和与之相连的另外两个student结构体的member成员。
23 #define LIST_HEAD_INIT(name) { &(name), &(name) }
24
25 #define LIST_HEAD(name) \
26 struct list_head name = LIST_HEAD_INIT(name)
这三⾏的意思是利⽤两个宏来定义并初始化⼀个list_head型的结构体name，⾸先来看下⾯这个宏，他定义了name
这个结构体，并利⽤上⾯的宏为其赋值，⽽上⾯的宏的意思是将⼀个结构体⾃⾝赋给它的前驱节点和后
继节点，这样便完成了定义并初始化的功能。
28 static inline void INIT_LIST_HEAD(struct list_head *list)
29 {
30 list->next = list;
31 list->prev = list;
32 }
虽然上⾯的两个宏提供了定义并初始化⼀个list_head类型的结构体的功能。但是系统还是提供了这个单独进⾏初始化的函数。在这⾥我们简单解释下static和inline的意思：
static修饰的函数就是静态函数，是对函数作⽤域的限制，指该函数的作⽤域仅限于本⽂件，不能被其他⽂件使⽤，因此static具有信息隐藏作⽤。
inline修饰的函数的意思是这个函数对编译程序是可见的，编译程序在调⽤这个函数时就⽴即展开该函数，⽽不是保存现场，执⾏调⽤函数，恢复现场等繁琐操作，这样可以提⾼效率。这样的函数⼀般称
之为“内联函数”，但是注意：inline必须和函数定义体放在⼀起才能使函数成为内联函数，⼀般放于头⽂件中。
40 #ifndef CONFIG_DEBUG_LIST
41 static inline void __list_add(struct list_head *new,
42 struct list_head *prev,
43 struct list_head *next)
44 {
45 next->prev = new;
46 new->next = next;
47 new->prev = prev;
48 prev->next = new;
49 }
50 #else
51 extern void __list_add(struct list_head *new,
52 struct list_head *prev,
53 struct list_head *next);
54 #endif
这⼏句是⼀个条件编译的语句，⼤体的意思就是如果没有定义CONFIG_DEBUG_LIST这个宏就编译下⾯static inline void __list_add（）函数，else就使⽤extern声明此函数已经在外部⽂件中定义过了，
防⽌重复定义！
我们来看下这个函数是⼲什么的？其实我的建议是⼤家在看此类链表代码时个草稿本在上⾯⼀边看⼀边花，这样很简单明了，语⾔解释反倒⿇烦，我就不罗嗦了，它的意思就是在原本相连的prev和
next两个节点之间增加⼀个new节点。
64 static inline void list_add(struct list_head *new, struct list_head *head)
65 {
66 __list_add(new, head, head->next);
67 }
78 static inline void list_add_tail(struct list_head *new, struct list_head *head)
79 {
80 __list_add(new, head->prev, head);
81 }
这两个函数由上⾯的
__list_add()函数衍⽣⽽来，其实后⾯很多都是如此，复杂的函数都是由前⾯定义的基本函数组合⽽来。这两个函数也不⽤罗嗦了，⼤概的意思就是分别在head节点的后⾯和前⾯增加⼀个节点new，在head节点后⾯增加即增加在链表
90 static inline void __list_del(struct list_head * prev, struct list_head * next)
91 {
92 next->prev = prev;
93 prev->next = next;
94 }
这⼜是⼀个基本函数，意思是将形参传来的两个节点链接起来。
102 #ifndef CONFIG_DEBUG_LIST
103 static inline void list_del(struct list_head *entry)
104 {
105 __list_del(entry->prev, entry->next);
106 entry->next = LIST_POISON1;
107 entry->prev = LIST_POISON2;
108 }
109 #else
110 extern void list_del(struct list_head *entry);
111 #endif
还是⼀个条件编译语句，我们直接看函数定义，此函数是⼀个删除节点函数，它⾸先利⽤上⾯的基本函数将entry所指的节点的前驱节点和后继节点链接起来，然后将entry节点的前驱指针和后继指针分别指向两个宏：LIST_POISON1，LIST_POISON2，在poison.h⽂件中，到了这两个宏的定义：
22 #define LIST_POISON1 ((void *) 0x00100100 + POISON_POINTER_DELTA)
23 #define LIST_POISON2 ((void *) 0x00200200 + POISON_POINTER_DELTA)
POISON_POINTER_DELTA宏⼜是什么呢？同样在在那个⽂件中：
11 #ifdef CONFIG_ILLEGAL_POINTER_VALUE
12 # define POISON_POINTER_DELTA _AC(CONFIG_ILLEGAL_POINTER_VALUE, UL)
13 #else
14 # define POISON_POINTER_DELTA 0
15 #endif
这样我们就知道POISON_POINTER_DELTA其实就是0，那么LIST_POISON1 ，LIST_POISON2，这两个宏就很轻松理解，其实就是两个固定的地址。
120 static inline void list_replace(struct list_head *old,
121 struct list_head *new)
122 {
123 new->next = old->next;
124 new->next->prev = new;
125 new->prev = old->prev;
126 new->prev->next = new;
127 }
这个函数是实现⽤new节点来替换old节点，但是我们细⼼便会发现它的缺陷，它虽然实现了替换，但是old节点依然在那条链表上，即没有取消old节点的前驱指针和后继指针的指向。
129 static inline void list_replace_init(struct list_head *old,
130 struct list_head *new)
131 {
132 list_replace(old, new);
133 INIT_LIST_HEAD(old);
134 }
因为上⾯的函数存在缺点，所以出现了这个函数，它在实现替换功能后，使⽤了INIT_LIST_HEAD()函数，我们回头看下这个函数的定义，便知道是将old节点的前驱节点和后继节点全部指向⾃⼰！以做到彻底的替换！
140 static inline void list_del_init(struct list_head *entry)
141 {
142 __list_del(entry->prev, entry->next);
143 INIT_LIST_HEAD(entry);
144 }
这个函数是⼀个删除节点的函数，⾸先将entry的前驱节点和后继节点链接起来，再将entry节点的前驱和后继指针分别指向⾃⼰，以做到彻底删除！后⾯的组合函数愈来愈多，我的感受是第⼀次看肯定记不住前⾯那么多函数的功能，那么就即时的回头去看，慢慢就熟悉，记住了。
151 static inline void list_move(struct list_head *list, struct list_head *head)
152 {
153 __list_del(list->prev, list->next);
154 list_add(list, head);
155 }
这个函数就是先将list节点从原链表中删除，然后将其添加到head链表的表头即head节点的下⼀个节点！
162 static inline void list_move_tail(struct list_head *list,
163 struct list_head *head)
164 {
165 __list_del(list->prev, list->next);
166 list_add_tail(list, head);
167 }
类似于上⾯的函数，先将list节点从原链表中删除，在将其添加到head链表的表尾即head的前⼀个节点！（注意理解双向循环链表！）
174 static inline int list_is_last(const struct list_head *list,
175 const struct list_head *head)
176 {
177 return list->next == head;
178 }
这个函数是测试list节点是否为head链表的表尾节点。是返回1，否则返回0.
184 static inline int list_empty(const struct list_head *head)
185 {
186 return head->next == head;
187 }
这个函数是测试head链表是否为空链表。是返回1，否则返回0.（此函数存在缺陷，看下⾯它的仔细版：）
202 static inline int list_empty_careful(const struct list_head *head)
203 {
204 struct list_head *next = head->next;
205 return (next == head) && (next == head->prev);
206 }
看函数名和上⾯的很相似，它完善了上⾯函数的缺陷，它检查空链表时更加”仔细“，它判断空链表有两个条件：
1，上⾯函数的条件，即head的后继节点就是本⾝。
2，head的前驱节点和后继节点相同。
这两个条件⼀起就可以确定此链表是否为空链表。
212 static inline int list_is_singular(const struct list_head *head)
213 {
214 return !list_empty(head) && (head->next == head->prev);
215 }
这个函数判断head链表是否为单节点链表。
217 static inline void __list_cut_position(struct list_head *list,
218 struct list_head *head, struct list_head *entry)
219 {
220 struct list_head *new_first = entry->next;
221 list->next = head->next;
222 list->next->prev = list;
223 list->prev = entry;
224 entry->next = list;
225 head->next = new_first;
226 new_first->prev = head;
227 }
这个函数是将head链表的头结点⾄entry节点之间的节点连在list节点后⾯，即组成以list节点为头结点的新链表。
243 static inline void list_cut_position(struct list_head *list,
244 struct list_head *head, struct list_head *entry)
245 {
246 if (list_empty(head))
247 return;
248 if (list_is_singular(head) &&
249 (head->next != entry && head != entry))
250 return;
251 if (entry == head)
252 INIT_LIST_HEAD(list);
253 else
254 __list_cut_position(list, head, entry);
255 }
这个函数的功能和上⾯的函数相同，但是判断的更加仔细，⾸先它排除了空链表的情况，下来⼜否定了单链表⽽且节点不是entry的情况，然后⼜判断了entry和head指向同⼀节点的情况，这种情况下按照功能，只需要初始化list链表即可。最后在排除晚其他不安全情况后进⾏了“切割移植”操作。
257 static inline void __list_splice(const struct list_head *list,
258 struct list_head *prev,
259 struct list_head *next)
260 {
261 struct list_head *first = list->next;
262 struct list_head *last = list->prev;
263
264 first->prev = prev;
265 prev->next = first;
266
267 last->next = next;
268 next->prev = last;
269 }
这个函数的意思是将list链表的全部节点（头结点list除外）插⼊在prev和next节点之间。
276 static inline void list_splice(const struct list_head *list,
277 struct list_head *head)
278 {
279 if (!list_empty(list))
280 __list_splice(list, head, head->next);
281 }
这个函数的意思就是在list是⾮空链表的情况下，将其插在head链表的头部，即head节点的后⾯。此函数不安全，因为在插⼊后还能通过list节点访问到其余的节点。
288 static inline void list_splice_tail(struct list_head *list,
289 struct list_head *head)
290 {
291 if (!list_empty(list))
292 __list_splice(list, head->prev, head);
293 }
与上⾯的函数类似，在list是⾮空链表的情况下，将其插在head链表的尾部，即head节点的前⾯。不安全，原因同上！
302 static inline void list_splice_init(struct list_head *list,
303 struct list_head *head)
304 {
305 if (!list_empty(list)) {
306 __list_splice(list, head, head->next);
307 INIT_LIST_HEAD(list);
308 }
309 }
这个函数的意思就是在list是⾮空链表的情况下，将其插在head链表的头部，即head节点的后⾯。然后对list节点进⾏初始化，排除不安全因素。
319 static inline void list_splice_tail_init(struct list_head *list,
320 struct list_head *head)
321 {
322 if (!list_empty(list)) {
323 __list_splice(list, head->prev, head);
324 INIT_LIST_HEAD(list);
325 }
326 }
这个函数的意思就是在list是⾮空链表的情况下，将其插在head链表的尾部，即head节点的前⾯。然后对list节点进⾏初始化，排除不安全因素。
334 #define list_entry(ptr, type, member) \
335 container_of(ptr, type, member)
真正精彩的地⽅到了，这个宏以及下⾯的⼏个宏的定义，我感觉很精彩！有些地⽅初次理解起来⽐较费⼒，我在这⾥为⼤家慢慢分享下我的理解，不⼀定对，有错误的地⽅希望⼤家赐教！不罗嗦了，我们看上⾯这个宏，这其实就是⼀个宏定义的转移，利⽤container_of这个宏定义了上句的list_entry这个宏，我们还是不懂意思，不急。我们在kernel.h⾥⾯到container_of这个宏的定义：
653 #define container_of(ptr, type, member) ({ \
654 const typeof( ((type *)0)->member ) *__mptr = (ptr); \
655 (type *)( (char *)__mptr - offsetof(type,member) );})
这个⾥⾯⼜⽤到了offsetof的宏定义，我们在stddef.h⾥⾯到它的定义：
24 #define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
下来，我们来综合分析下，我们⾸先分析offsetof的意思：我们再看⼀遍它的定义，((size_t) &((TYPE *)0)->MEMBER)
最外⾯的括号⾥⾯分为两部分：(size_t) 和 & ((TYPE *)0)->MEMBER，我们⾸先看& ((TYPE *)0)->MEMBER，它由两部分组成，&和 ((TYPE *)0)->MEMBER，我们先看后者((TYPE *)0)-
>MEMBER，他⾸先将0强制类型转换成指向TYPE类型的结构体的指针，然后引⽤其MEMBER成员。可能有些⼈不懂，这样，我们来随便定义⼀个TYPE类型的结构体：
struct TYPE {
int a；
char b；
int c;
struct list_head MEMBER;
container什么意思};
这样看起来是不是⼀⽬了然，现在我们来看offsetof的意思，很简单就是：⾸先将0强制类型转换成指向TYPE类型的结构体的指针，然后取其MEMBER成员的地址，最后再强制类型转换成size_t⾏，即（unsi
gned int）型！那么有⼈会问了，为什么要使⽤0呢？要它的MEMBER成员的地址有什么⽤呢？⽤处很⼤，⽽且很巧！我们需要慢慢品尝：
⾸先，我们回顾下，什么叫指针？指针就是⼀个内存单元的地址！那么好，我们上⾯说到了，将0强制转换成TYPE类型结构体的指针，那么我们来说说，这个所指的结构体的起始地址是多少？理所当然是0.那么很好，既然它的起始地址是0，那么它的MEMBER成员的地址，其实就是它在这个结构体的偏移量！理解了吗？OK！offsetof(TYPE, MEMBER)的意义我们知道了，就是求TYPR类型的结构体中MEMBER成员的偏移量！它的作⽤，我们继续往下看：
知道了offsetof的作⽤，我们返回去看container_of这个宏的定义：
#define container_of(ptr, type, member) ({ \
const typeof( ((type *)0)->member ) *__mptr = (ptr); \
(type *)( (char *)__mptr - offsetof(type,member) );})
它的定义分两句话，先看第⼀句：const typeof( ((type *)0)->member ) *__mptr = (ptr)；我们从左开始慢慢看，⾸先看typeof（）⾥⾯的东西：((type *)0)->member ，它什么意思呢？相⽐⼤家都知道了，它就是以0为起始地址的type类型的结构体的member成员（还没理解的，分析过程见上⾯的offsetof分析过程！
）。那么typeof的含义是什么呢？
typeof的含义都能看出来，就是提取类型的意思！那么等号左⾯const typeof( ((type *)0)->member ) *__mptr的意思就是：定义⼀个指向以0为起始地址的type类型的结构体的member成员的类型的指针_mptr，那么第⼀句的意思很明了，就是定义这么⼀个指针，并将ptr指针的值赋给它！那么ptr是什么呢？根据这个宏的形参，我们知道它是指向type类型结构体中member成员的指针，那么现在_mptr也指向了type类型结构体中member成员。
好，我们看下⼀句：(type *)( (char *)__mptr - offsetof(type,member) );offsetof宏的定义我们知道了，-mptr
的意思我们也知道了，那么这句话应该不难，就是先将指针_mptr强制类型转换成（char *），再⽤他减去type类型的结构体中member成员的偏移量，最后将结果强制转换成（type *）类型！可能有些⼈不理解这句话背后的意思，别急，我们慢慢分析，由于_mptr是指向type类型结构体中member成员的指针，那么她的值就是type类型结构体中member成员的地址，⽽offsetof(type,member)的意思是type类型的结构体中member成员的偏移量，那么⽤它的地址减去它的偏移量，是什么结果呢？这是个数学问题！⽤⼀个结构体中⼀个成员的地址减去它在这个结构体中的偏移量，等于？很简单，等于这个结构体的起始地址！好!那么有⼈会问，为什么要转换成（char *）类型再减呢？
这是⼀个关于指针加减的问题！就是如果前⾯的指针不是（char *）等单字节类型，假设是（int *）类型，那么⽤它家去⼀个偏移量，就等于减去了（偏移量*sizeof(int)个单元，这是为什么呢？因为指针在进⾏加减时是以减数类型的⼤⼩为基准进⾏加减的，就是说如果是（int *）类型，那么它实际会以int类型为单元减去偏移量个！不就是减去了（偏移量*sizeof(int)个单元吗？这样就错了！为此我专门写了⼀个简单的函数进⾏验证：
1 #include<stdio.h>
2 int main()
3 {
4 struct student
5 {
6 int a;
7 char b;
8 int c;
9 int d;
10 };
11 struct student *p;
12 struct student q;
13 p=&q; //⽤p指向这个结构体！
14 printf("&struct=%u\n",(unsigned long)p); //打印这个结构体的地址！
15 printf("&q.d =%u\n",(unsigned long)&(q.d)); //打印这个结构体中d变量的地址
16 printf(" true=%u\n",(unsigned long)(char *)&(q.d)-12); //打印d变量转换成（char *）后减去它的偏移量到的结构体的地址！（是正确的！）
17 printf(" false=%u\n",(unsigned long)(&(q.d)-12)); //打印没有转换进⾏减法得到的值，是错误的！⽽且正是我们分析的减了偏移量*sizeof(int)，所以是错的！
18 }
运⾏结果是：(有编译警告，先不管！直接运⾏！)
[wjl@wjl-desktop ~/c/test 21:38:58 #27]$ ./test
&struct=3213925676
&q.d =3213925688
true=3213925676 //3213925688-12
false=3213925676 //3213925676-12*4
⼤家仔细观察这个程序便会发现指针加减的问题！验证我上⾯的说法！ok！
那么到此为⽌，我们分析接近尾声了，container_of(ptr, type, member)宏的意思出来了，就是已知指向type类型的结构体中member成员的指针ptr的情况下，我们求出了这个结构体的起始地址！要这个地址有什么⽤呢？很多⼈可能都想到了，指针！好，我们往下看！
345 #define list_first_entry(ptr, type, member) \
346 list_entry((ptr)->next, type, member)
这个宏的意思是不是很简单了，就是已知type类型的结构体中member成员的指针后，我们可以求得它所在的链表的下⼀个指针所指的member所在的type类型的结构体的起始地址！
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论