10 hlist扩展精益求精的Linux链表设计者（因为list.h没有署名，所以很可能就是Linus Torvalds）认为双头（next、prev）的双链表对于HASH表来说"过于浪费"，因而另行设计了一套用于HASH表应用的hlist数据结构--单指针表头双循环链表，从上图可以看出，hlist的表头仅有一个指向首节点的指针，而没有指向尾节点的指针，这样在可能是海量的HASH表中存储的表头就能减少一半的空间消耗。struct hlist_head{　　　 struct hlist_node *first;};struct hlist_node {　　　 struct hlist_no...

8 遍历遍历是链表最经常的操作之一，为了方便核心应用遍历链表，Linux链表将遍历操作抽象成几个宏。在介绍遍历宏之前，我们先看看如何从链表中访问到我们真正需要的数据项。struct list_head *i;list_for_each(i, &(nf_sockopts.list)){ struct nf_sockopts *ops = list_entry(i, struct nf_sockopts, list);} 函数首先定义一个(struct list_head *)指针变量i，然后调用list_for_each(i,&(sockopt.list))进行遍...

4 插入对链表的插入操作有两种：在表头插入和在表尾插入。Linux为此提供了两个接口：static inline void list_add(struct list_head *new, struct list_head *head);static inline void list_add_tail(struct list_head *new, struct list_head *head);因为Linux链表是循环表，且表头的next、prev分别指向链表中的第一个和最末一个节点，所以，list_add和list_add_tail的区别并不大，实际上，Linux分别用__list_ad...

Linux 2.6内核链表数据结构1 链表设计原理这里使用2.6内核，但实际上2.4内核中的链表结构和2.6并没有什么区别。不同之处在于2.6扩充了两种链表数据结构：链表的读拷贝更新（rcu）和HASH链表（hlist）。这两种扩展都是基于最基本的list结构，因此，本文主要介绍基本链表结构，然后再简要介绍一下rcu和hlist。链表数据结构的定义很简单（节选自[include/linux/list.h]，以下所有代码，除非加以说明，其余均取自该文件）：struct list_head { struct list_head *next, *prev;}; list_head结构包含...