内核链表
在Linux内核中使用了大量的链表结构来组织数据，包括设备列表以及各种功能模块的数据组织。这些链表大多采用在【include/linux/list.h】实现一个相当精彩的链表数据结构。
Linux2.6多了两种功能，链表的读拷贝更新(rcu)和HASH链表(hlist)。这两种功能都是基于list结构的。
1链表的定义
Struct list_head
{
Struct list_head *next, *prev;
};
List_head结构包含两个list_head结构的指针prev和next。由此可见，实际上，通常他们都组织成双向循环链表。这里的list_head没有数据域。在Linux内和链表中，不是在链表结构中包含数据，而是在数据结构中包含链表节点。
在Linux内核链表中，需要用链表组织起来的数据通常都包含一个struct list_head成员。例如在【include/linux/netfilter.h】中定义了了一个nf_socket_ops结构来描述netfilter摸一个协议族准备的getsocket/setsocketopt接口。其中就有一个structlist_head list 成员，各个协议族的nf_sockopt_ops结构都通过这个list成员组织在一个链表中，表头是定义在【net/core/netfilter.c】中的nf_sockopts(struct
list_head)，从下图可以看到,这种通用的链表结避免了为每个数据项类型定义自己链表的麻烦，Linux的简捷实用，不求完美和标准的风格，在这里体现的相当充分。
2
链表的操作接口
2.1声明和初始化
实际上Linux只定义了链表节点，并没有专门定义链表头，那么一个链表结构是如何建立起来的呢？让我们来看看LIST_HEAD()这个宏。
#defineLIST_HEAD_INIT(name) {&(name), &(name)}
#define LIST_HEAD(name)
struct list_headname=LIST_HEAD_INIT(name)
当我们用LIST_HEAD(nf_sockopts)声明一个名为nf_sockopts的链表头时，它的next, prev指针都初始化为指向自己。这样，我没就有个空链表，因为Linux用头指针的next是否指向自己来判断链表是否为空。
Static inline intlist_empty(const struct list_head *head)
{
Return head->next = = head;
}
除了LIST_HEAD()宏在声明的时候初始化一个链表以外，linux还提供了一个INIT_LIST_HEAD宏用于运行时初始化链表。
#defineINIT_LIST_HEAD(ptr) do { \
(ptr)->next = (ptr);
(ptr)->prev= (ptr);
} while(0)
我们用INIT_LIST_HEAD(&nf_sockopts)来使用它。
2.2插入/删除/合并
l 插入
对于链表的插入有两种：在链表头插入和链表尾插入。Linux为此提供了两个接口。
Staticinline void
list_add(struct list_head*new, struct list_head *head);
Staticinline void list_add_tail (struct list_head*new , struct list_head *head);
2.3遍历
l 有链表节点到数据项变量
Linux链表中仅保存了数据项结构中list_head成员变量的地址，我们如何通过这个llist_head成员访问作为它的所有者的节点呢？linux为此提供了list_entry(ptr, type, member)宏，其中ptr是指向该数据中list_head成员的指针，也就是存储在链表中的地址值；type是数据项的类型，member则是数据项类型定义中list_head成员的变量名。
如果我们要访问nf_sockopts链表中首个nf_sockopt_ops变量，则如此调用：
List_entry (nf_sockopts->next,struct nf_sockopt_ops, list);
这里“list”真是nf_sockopt_ops结构中定义的用于链表操作的节点成员变量名。
请看一下下面这段程序码。
|
|
struct HelloWorld { |
|
假设int是4个byte。 那么以下这一行会得到8， 如图5所示
|
|
(unsigned long) (&((struct HelloWorld *)0)->list) |
|
有的人会对这一行程序感到奇怪， (struct HelloWorld*)0不就是一个NULL的指标吗? 怎么可以用0->list去参考list这个栏位呢? 难道不怕造成segmentationfault吗? 请注意一下，
我们在0->list的前面还加上了一个&。 如果没有&， 那上面这一行就会segmentation fault了。 如果你加上了&， 那就没问题棉。 Segmentation fault通常是去参考到不合法的记忆体地址内容所造成的， 如果我们加上了&就表示我们没有要去参考这个不合法地址的内容，我们只是要那个栏位的地址而已， 因此， 不会造成segmentation fault。 其实， 结构的配置在记忆体里是连续的。 所以， 如果我们去读取某个栏位时，像&hello->list。 会先取得hello变数的地址，
再然后再计算HelloWorld结构里list栏位所在的offset， 再将hello的地址加上list栏位的offset，求得list栏位真正的地址。 然后再去读list栏位的内容。 这是compiler帮我们做的。 那我们现在就来看看上面那一行究竟是什么意思。首先， 我们先把上面那一行想象成下面这个样子。
|
|
ptr = 0; |
|
这样是不是容易懂了吗， 就是要取得&ptr->list的地址而已。所以，如果ptr是100的话， 那会得到100+8=108。 因为前面有二个int， 每一个int是4个byte。 经过转型，就得到了(unsigned
long)型态的108。 如果ptr是0的话， 那同理， 我们会得到0+8=8。也就是这个栏位在HelloWorld结构里的offset。
现在， 如果我们已经知道了list在HelloWorld结构中的offset，而且我们现在也知道hello这个变数里list的地址的话， 那有没有办法得到hello本身的地址呢? 可以的， 就像图6一样， 如果我们知道list的地址，
只要将list的地址减8就可以知道了hello的地址了嘛。
|
|
struct list_head *plist = &hello.list; |
|
而这种方式就是list_head的用法， 它是专门用来当作别的结构的栏位，只要我们得到这个栏位的位置和包含这个栏位的结构是那一种，我们可以很轻易的算出包含此栏位的结构地址， 图6就是super block在使用list_head所得到的结果。只要我们知道s_list的地址，
只要呼叫
|
|
list_entry( &sb1.s_list, struct super_block, s_list) |
|
就可以得到其sb1这个super_block结构的地址。