Linux内核中的通用双向循环链表
开发中接触Linux越来越多,休息放松之余,免不了翻看翻看神秘的Linux的内核。看到双向链表时,觉得挺有意思的,此文记下。
作为众多基础数据结构中的一员,双向循环链表在各种“教科书”中的实现是相当的标准和一致的。
大概就是下面这个样子:
1 typedef struct node_tag{ 2 //T data; 3 struct node_tag *prev; 4 struct node_tag *next; 5 }node;
当你需要某种类型的链表时,把数据成员之类的往节点里塞就是了。比如菜谱链表,里面就可以有宫爆鸡丁,酸辣粉,地三鲜,水煮鱼,麻辣鸡翅。。。
嗯,当你需要另外一种链表时,接着如法炮制,只要功夫深,几十上百也不是问题。有一部分人善于解决这类问题,它们叫做CP程序员(Copy-Paste),
不要问我为什么知道。C++模板在这点上能实现通用特性,但不在本次内容之列了。
有着极客精神的Linux,在内核中肯定不会像上面这么做的。内核中有大量的数据结构需要使用双向链表,诸如进程、模块、文件。
难道要人去维护各种类型的双向链表?而且还是不能复用的链表。我想没多少人愿意把时间花在这种事情上吧。维护一种通用的不就好了。
链表节点,作为一个“连接件”,最本质的内容就是把一些对象链接起来,至于对象内部存储的数据,是可以不用知道的。
在include/linux/list.h文件中,就有使用这样的一个"连接件“:
struct list_head { struct list_head *next, *prev; };
和node_tag相比,少了数据部分。
list_head作为独立变量时,充当的是链表头的角色;如果作为结构体成员时,则是“连接件”的角色。
在这样的实现方式下,要获得某种类型的链表,只需在宿主结构中声明一个list_head成员,还可以任意的取名;
关键是,链表操作只需以list_head为对象进行实现;剩下唯一的问题是,在遍历链表时,该如何获取宿主结构的首地址?
毕竟链表是用来装内容用的。这里利用编译器的一个小技巧就可以算出地址偏移
#define offsetof(s,m) (size_t)&(((s *)0)->m)
有了list_head相对宿主结构首地址的偏移,和自身地址来个加减就可以得到宿主的首地址,接下该怎么操作就怎么操作了。
个人觉得这里面有面向对象的意思。抽取出共同的“连接件” list_head,链表操作也以list_head为对象进行设计,
除了要具体访问操作宿主结构之外,全部都是共性的东西。
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。