C/C++中链表的三种设计方案

http://http://blog.csdn.net/jiangnanyouzi/article/details/3164066

1. 一般做法，用具体数据结构封装链表。

1. struct Data
2. {
3. int data;
4. struct Data *next;
5. };

上边这个例子，在Data结构中有个next域，通过这个就可以组成一个链表，这个是我读书时最常用的模式。缺点在于：每种具体的结构都要写一遍链表的增删查改操作，重复了N多。
2. STL的做法：用链表封装具体数据结构。

1. struct Data
2. {
3. int data;
4. float f;
5. };
7. ...
9. list lData;

这种类型用到c++ stl的模板类list<>，之所以用指针，是因为在拷贝的时候不会频繁的调用Data类的拷贝构造函数。在C语言中没有模板，怎么办？我倒是有个办法：

1. struct List
2. {
3. void *data;
4. struct List *next;
5. };
7. void addElem(struct List list, void *data);
8. ...
11. struct  Data
12. {
13. int data;
14. float f;
15. };
17. ...
19. struct Data d;
20. d.data = 5;
21. d.f = 6.0f;
22. List lData;
23. addElem(struct List list, (void *)&d );
24. ...

那个链表List结构体就可以独立于各种类型，到用到的时候再给据情况转回来就可以了。在内核中有一部分代码就是这么做的。
3. 用具体数据结构封装通用链表。（linux内核的通用做法）

1. struct list_head
2. {
3. struct list_head *next, *prev;
4. };
6. #define LIST_HEAD(name) struct list_head name = LIST_HEAD_INIT(name)
8. #define LIST_HEAD_INIT(ptr) /
9. do{(ptr)->next = (ptr); (ptr)->prev = ptr;} while(0)
12. /* 还为这个链表定义一些通用操作和宏 */
14. /* 在链表头部head后面插入新元素 */
15. list_add(struct list_head *new, struct list_head *head);
17. /* 从给定的入口将链表entry删除 */
18. list_del(struct list_head *entry);
20. ...
23. struct Data
24. {
25. int data;
26. float f;
27. struct list_head list;
28. };

好，先说一下上面的宏LIST_HEAD_INIT(ptr)，可能会觉得奇怪，为什么会用这种结构do...while(0)呢，不妨先想想。
。。。
揭底吧：因为这是2条语句，如果这样
  #define LIST_HEAD_INIT(ptr) (ptr)->next = (ptr); (ptr)->prev = ptr;
那在下面的情况下就不能通过。
if(condition)
   LIST_HEAD_INIT(ptr);
else
   ...
这样会编译错误。
如果反过来就更糟糕，虽然编译不错，但运行结果肯定不是你想要的：
if(condition)
   ...
else
   LIST_HEAD_INIT(ptr); 
也许会想到这个样子定义宏，加个大括号：
#define LIST_HEAD_INIT(ptr) { (ptr)->next = (ptr); (ptr)->prev = ptr;}
但是这样的话在上面的语句里面编译一样通不过：
if(condition)
   LIST_HEAD_INIT(ptr);
else
   ...
注意到分号就可以知道它编译通不过，因为那个分号代表if分支的结束，下面那个else语句就无法与上面的if语句匹配。
当然可以限制说这个宏不需要分号，...汗，这样不是限制更多了。那有人记得住什么情况用不用分号啊。所以就只能用这种情形：do...while(0);来封装一堆语句了。
好了，言归正传。下面继续，
上边定义了一个链表结构体：struct Data;
现在假设链表已经建立好，要访问struct Data ld;的下一个节点。怎么办？
这还不简单，看：
struct list_head *pNode = ld.list.next;
...
然后呢？注意我要反问的是struct Data结构的下一个节点，而不是list_head的下一个节点。
想...想
好，揭底：其实，内核里面的代码有很大的篇幅都是根据偏移量来计算变量的地址的，不向用户程序，通过成员变量名来访问。下面看一下这个宏的基本实现：
#define entry_list(ptr, type, member) /
    (type *)( (char *)ptr - ((char *)&((type *)0)->member) )
其中，ptr 是 链表的一个struct list_head的元素指针，
      type 是 包含struct list_head结构成员的结构体
      member是 用户在type中定义那个struct list_head的成员的名字。
例如,通过pNode来取得它相对应的struct Data结构体：
   struct Data *d = entry_list(&data.list, struct Data, list);
进行一些说明：
以上的宏的实现只是一个基本实现，在linux内核的代码中，那个东西还有一些别的因素要考虑的，因此代码可能更为复杂一些。
宏entry_list的实现当中，是通过计算元素地址的偏移量来取得对应数据结构变量的地址。这在内核中是很常用的。当中的(char *)ptr是链表成员的地址，然后((char *)&((type *)0)->member)是把struct Data放到内存为0处时计算出的member的偏移量，所以相减就可以得到这个struct Data的地址（称为宿主）
由此可见，只要有心，linux内核的代码中处处都是可以学习的东西，大到整体设计，小到一些具体的技巧。都是思维的宝藏。
以上只是粗略的说说，如果要更详细的解释，在google 上搜 “linux 内核 链表"吧，嘿嘿
再说一些题外的东西：
我看linux内核中进程的状态的时候，发现一些数据：
#define TASK_RUNNING 0
#define TASK_INTERRUPTIBLE 1
#define TASK_UNINTERRUPTIBLE 2
#define TASK_STOPPED 4
#define TASK_TRACED 8
#define TASK_ZOMBIE 16
#define TASK_DEAD 32
第一次读这些的时候我没有留意，第二次读的时候我突然间想到，如果是我定义的话，我会将这些宏定义为：0 1 2 3 4 5...那么它为什么要这样定义呢？
这么一想，我注意到这些都是2的冥，也就是说，在二进制中都是某一位为1，剩下的为0.
然后我联想到以前那些c语言的文件调用的状态参数有那么多的或运算符，就大致清楚这些东西的作用了，可以很方便的进行状态的组合，只要把这些状态用'或'运算符即可。
这么一想，使我联系到了前段日子看的《编程之美》的一个章节，问的问题：要测试一个三角形，应该定义测试状态，答案是这个三角形可能是：锐角，钝角，直角，等腰，等边...其中有些状态可以重复，怎么办呢？我以前一般是这样想的，用0，1，2，3，4来定义那些东西，比如等腰是1，直角是2， 等腰直角是3等等，但是这样有一大堆重复的状态，不优雅啊
现在才知道（可见我不大符合做技术，因为总是要看过别人的东西才能联想起，而不能自己进行创新），可以通过把这些状态分割成一组互相独立的状态，比如等腰是1，直角是2，等边是4，等等，都是2的冥，如果测试是等腰直角的话，可以返回 "（等腰） | （直角） " = 1 | 2 = (二进制数的11)，这样就可以很轻松的解决啦。
刚才写的时候，又联想起高中学物理的正交分解了...无语啊，总是看过之后才能想起，其实，这个不就是正交分解在计算机的应用嘛？诶，早就已经知道的东西，却不懂得应用，这就是大师和普通人的区别了吧。可能是？我也许一辈子是一个再也平凡不过的人罢了。
好了，不发牢骚了，呵呵。金刚经有言曰：“应无所住，而生其心”。 懂过了就算了啊，无需执着一切法相。