2010年（22）
分类： LINUX
2010-08-15 17:57:59
Last Update:8/15
9.合并链表
既然我们可以切割链表，那么当然也可以合并了。先看最基本的合并函数，就是将list这个链表（不包括头结点）插入到prev和next两结点之间。这个代码阅读起来不困难，基本上是“见码知意”。
271static inline void __list_splice(const struct list_head *list,
272 struct list_head *prev,
273 struct list_head *next)
274{
275 struct list_head *first = list->next;
276 struct list_head *last = list->prev;
277
278 first->prev = prev;
279 prev->next = first;
280
281 last->next = next;
282 next->prev = last;
283}理解了最基本的合并函数，那么将它封装起来，就可以形成下面两个函数了，分别在head链表的首部和尾部合并。这里的调用过程类似增加，删除功能。
290static inline void list_splice(const struct list_head *list,
291 struct list_head *head)
292{
293 if (!list_empty(list))
294 __list_splice(list, head, head->next);
295}
302static inline void list_splice_tail(struct list_head *list,
303 struct list_head *head)
304{
305 if (!list_empty(list))
306 __list_splice(list, head->prev, head);
307}合并两个链表后，list还指向原链表，因此应该初始化。在上述两函数末尾添加初始化语句INIT_LIST_HEAD(list);后，就安全了。
10.遍历
下面我们要分析链表的遍历。虽然涉及到遍历的宏比较多，但是根据我们前面分析的那样，掌握好最基本的宏，其他宏就是进行“封装”。便利中的基本宏是：
381#define __list_for_each(pos, head) \ 382 for (pos = (head)->next; pos != (head); pos = pos->next)
head是整个链表的头指针，而pos则不停的往后移动。但是你有没有觉得，这里有些奇怪？因为我们在上篇文章中说过，struct list_head结构经常和其他数据组成新的结构体，那么现在我们只是不停的遍历新结构体中的指针，如何得到其他成员？因此我们需要搞懂list_entry这个宏：
348#define list_entry(ptr, type, member) \ 349 container_of(ptr, type, member)
这个宏的作用是通过ptr指针获取type结构的地址，也就是指向type的指针。其中ptr是指向member成员的指针。这个list_entry宏貌似很简单的样子，就是再调用container_of宏，可是当你看了container_of宏的定义后……
443#define container_of(ptr, type, member) ({ \
444 const typeof( ((type *)0)->member ) *__mptr = (ptr); \
445 (type *)( (char *)__mptr - offsetof(type,member) );})是不是让人有点抓狂？别急，我们一点点来分析。
首先这个宏包含两条语句。第一条：const typeof( ((type *)0)->member ) *__mptr = (ptr);首先将0转化成type类型的指针变量（这个指针变量的地址为0x0），然后再引用member成员（对应就是((type *)0)->member )）。注意这里的typeof（x），是返回x的数据类型，那么 typeof( ((type *)0)->member )其实就是返回member成员的数据类型。那么这条语句整体就是将__mptr强制转换成member成员的数据类型，再将ptr的赋给它(ptr本身就是指向member的指针)。
第二句中，我们先了解offsetof是什么？它也是一个宏被定义在：linux/include/stddef.h中。原型为：#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER);这个貌似也很抓狂，不过耐心耐心：((TYPE *)0)->MEMBER)这个其实就是提取type类型中的member成员，那么&((TYPE *)0)->MEMBER)得到member成员的地址，再强制转换成size_t类型（unsigned int）。但是这个地址很特别，因为TYPE类型是从0x0开始定义的，那么我们现在得到的这个地址就是member成员在TYPE数据类型中的偏移量。
我们再来看第二条语句， (type *)( (char *)__mptr - offsetof(type,member) )求的就是type的地址，即指向type的指针。有了这个指针，那么就可以随意引用其内的成员了。关于此宏的更具体了解，不妨亲自动手测试的程序。
好了，现在不用抓狂了，因为了解了list_entry宏，接下来的事情就很简单了。
下面这个宏会得到链表中第一个结点的地址。
359#define list_first_entry(ptr, type, member) \ 360 list_entry((ptr)->next, type, member)
真正遍历的宏登场了，整个便利过程看起来很简单，可能你对prefetch()陌生，它的作用是预取节点，以提高速度。
367#define list_for_each(pos, head) \ 368 for (pos = (head)->next; prefetch(pos->next), pos != (head); \ 369 pos = pos->next)
我们再来看一开始我们举例的那个便利宏。注意它和上述便利宏的区别就是没有prefetch()，因为这个宏适合比较少结点的链表。
381#define __list_for_each(pos, head) \ 382 for (pos = (head)->next; pos != (head); pos = pos->next)
接下来这个遍历宏貌似长相和上面那几个稍有不同，不过理解起来也不困难，倒着（从最后一个结点）开始遍历链表。
389#define list_for_each_prev(pos, head) \ 390 for (pos = (head)->prev; prefetch(pos->prev), pos != (head); \ 391 pos = pos->prev)
下面两个宏是上述两个便利宏的安全版，我们看它安全在那里？它多了一个与pos同类型的n，每次将下一个结点的指针暂存起来，防止pos被释放时引起的链表断裂。
399#define list_for_each_safe(pos, n, head) \ 400 for (pos = (head)->next, n = pos->next; pos != (head); \ 401 pos = n, n = pos->next) 409#define list_for_each_prev_safe(pos, n, head) \ 410 for (pos = (head)->prev, n = pos->prev; \ 411 prefetch(pos->prev), pos != (head); \ 412 pos = n, n = pos->prev)
前面我们说过，用在list_for_each宏进行遍历的时候，我们很容易得到pos，我们都知道pos存储的是当前结点前后两个结点的地址。而通过list_entry宏可以获得当前结点的地址，进而得到这个结点中其他的成员变量。而下面两个宏则可以直接获得每个结点的地址，我们接下来看它是如何实现的。为了方便说明以及便于理解，我们用上文中的结构struct stu来举例。pos是指向struct stu结构的指针；list是一个双链表，同时也是这个结构中的成员，head便指向这个双链表；member其实就是这个结构体中的list成员。
在for循环中，首先通过list_entry来获得第一个结点的地址；&pos->member != (head)其实就是&pos->list!=(head)；它是用来检测当前list链表是否到头了；最后在利用list_entry宏来获得下一个结点的地址。这样整个for循环就可以依次获得每个结点的地址，进而再去获得其他成员。理解了list_for_each_entry宏，那么list_for_each_entry_reverse宏就显而易见了。
420#define list_for_each_entry(pos, head, member) \ 421 for (pos = list_entry((head)->next, typeof(*pos), member); \ 422 prefetch(pos->member.next), &pos->member != (head); \ 423 pos = list_entry(pos->member.next, typeof(*pos), member)) 431#define list_for_each_entry_reverse(pos, head, member) \ 432 for (pos = list_entry((head)->prev, typeof(*pos), member); \ 433 prefetch(pos->member.prev), &pos->member != (head); \ 434 pos = list_entry(pos->member.prev, typeof(*pos), member))
下面这两个宏是从当前结点的下一个结点开始继续（或反向）遍历。
456#define list_for_each_entry_continue(pos, head, member) \ 457 for (pos = list_entry(pos->member.next, typeof(*pos), member); \ 458 prefetch(pos->member.next), &pos->member != (head); \ 459 pos = list_entry(pos->member.next, typeof(*pos), member)) 470#define list_for_each_entry_continue_reverse(pos, head, member) \ 471 for (pos = list_entry(pos->member.prev, typeof(*pos), member); \ 472 prefetch(pos->member.prev), &pos->member != (head); \ 473 pos = list_entry(pos->member.prev, typeof(*pos), member))
与上述宏不同的是，这个宏是从当前pos结点开始遍历。
483#define list_for_each_entry_from(pos, head, member) \ 484 for (; prefetch(pos->member.next), &pos->member != (head); \ 485 pos = list_entry(pos->member.next, typeof(*pos), member))
接下来几个宏又分别是上述几个宏的安全版。安全原因上面已经说过，在此不再赘述。
list_for_each_entry_safe(pos, n, head, member) list_for_each_entry_safe_continue(pos, n, head, member) list_for_each_entry_safe_from(pos, n, head, member) list_for_each_entry_safe_reverse(pos, n, head, member)
以上即是list.h头文件中的大部分内容分析。关于hash表部分在此暂不分析。