分类： LINUX
2012-04-16 16:58:55
hlist
相关数据结构:
struct hlist_head {
struct hlist_node *first;
};
struct hlist_node {
struct hlist_node *next, **pprev;
};
对于list_head，研究内核的想必都非常的熟悉。我们就不多说了。
而对于hlist，其初衷是因为在hash table中使用有两个指针的list_head过于浪费。
hlist_head中只包含一个first的指针，这点是和list_head最大的区别，空间也就是在这里节省出来的。
内核为hlist提供了一系列辅助的宏和函数，详见include/linux/list.h
下面，我们以图表的方式描述hlist_add_head()函数所实现的功能：
首先，我们通过宏INIT_HLIST_HEAD来初始化一个hlist_head:
hlist_head
+----------+ /------\
| *first |------>| NULL |
+----------+ \------/
此时，链表中只有链表头。
接下来，我们用hlist_add_head()向链表中添加一个hlist_node: node_1
/------> node_1
hlist_head | +----------+
+----------+ | /---| **pprev |
/--->| *first |---/ | +----------+ /------\
| +----------+ | | *next |----->| NULL |
| | +----------+ \------/
| |
| |
\-----------------------/
此时链表中有一个表头和一个node
接下来，我们继续用hlist_add_head()向链表中再添加一个hlist_node: node_2
/--------> node_2 /-----> node_1
hlist_head | +----------+ | +----------+
+----------+ | /------| **pprev | | /---| **pprev |
/-->| *first |--/ | +----------+ | | +----------+ /------\
| +----------+ | /-->| *next |---/ | | *next |--->| NULL |
| | | +----------+ | +----------+ \------/
| | | |
\--------------------\ \---------------------/
我们可以看到，node_2被添加到了hlist_head的后面。
这里我们还需要注意的是hlist_node 中的 pprev元素，因为它指向上一个hlist_node（对于第一个hlist_node，它的上一个hlist_node则是hlist_head）的 next元素（对于hlist_head则是first），因为next(或first)的类型是指针，所以pprev的类型是指向指针的指针 (struct hlist_node **pprev).
