链表之 hlist

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).