linux内核中的数据结构－－Linked Lists
双向循环链表
和其他实现相比，Linux内核中对于双向循环链表的实现比较特殊，这个结构中没有去包含一个通用指针来支持不同的对象，而是将这个linked list结构本身嵌入到任意的结构中去。
struct list_head {
struct list_head *next, *prev;
};
struct mystruct {
// 其它属性
struct list_head list;
};
所有的检索都是基于struct list_head *类型的指针，那么怎么能够获取相应对象中的其它属性呢？这里使用了一个trick，看看container_of这个宏：
#define container_of(ptr, type, member) ({ \
const typeof(((type *)0)->member) *__mptr = (ptr); \
(type *)((char *)__mptr - offsetof(type, member)); })
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
其实它就是取得了member相对type结构的偏移，然后用ptr减去这个偏移可以得到包含这个指针的对象的地址。
添删查找操作和通常情况一样，可以在 ./include/linux/list.h查看它们的具体实现。
一些有意思的宏：
#define list_for_each(pos, head) \
for (pos = (head)->next; prefetch(pos->next), pos != (head); \
pos = pos->next)
#define list_for_each_safe(pos, n, head) \
for (pos = (head)->next, n = pos->next; pos != (head); \
pos = n, n = pos->next)
第二个宏中多了一个safe，它支持在遍历linked list的过程中对链表节点进行删除。第一个宏没有这种支持。
头节点只含一个指针的双向链表
struct hlist_head {
struct hlist_node *first;
};
struct hlist_node {
struct hlist_node *next, **prev;
};
看看这种链表对象，每个节点包含一个指向下一个对象的指针，以及_一个指向prev节点的next对象的指针_。这种设计使得头节点只需要包含一个指针，通常用于哈希表的实现（如进程pidmap的管理），每个表项相比循环双向linked list都节约了一个指针的空间。
关于 (type) **prev的使用Linus大神曾说过这个是真正core low-level coding。 具体可见陈皓的博客Linus：利用二级指针删除单向链表。
参考
linux kernel development 3rd edition