Linux 内核中 hlist_head 与 hlist_node 设计

 

linux 内核中的hlist_head和hlist_node结构被用于hash表，定义如下：

struct hlist_head {
   struct hlist_node *first;
};
struct hlist_node {
   struct hlist_node *next, **pprev;
};

hlist_node的pprev域开始没看明白为什么是hlist_node的二级指针，但看到代码中对它的使用是让它指向前一个节点的next域（对于第一个节点，指向表头的first域）。为什么要设计成这样？
一般的单链表通常定义如下：

struct node {
   struct node *next;
};

对于这样的链表，在指定节点pCur后插入节点pNode很容易：

pNode->next = pCur;
pCur->next  = pNode;

但是要在指定节点pCur前插入pNode则很麻烦, 必须找到pCur的前一个结点pPre,然后执行操作：

pPre->next = pNode;
pNode->next = pCur;

也就是花费一定的时间用来搜索pCur的前一个节点, linux 为了提高执行效率， 采用了大家熟知的以空间换时间的方案， 添加pprev域， 指向前一个节点的next域，在执行前向插入时无需搜索， 只需执行如下操作就可以了：

*(pCur->ppre) = pNode;
pNode->next = pCur;

Linux 的确是在很多地方都注意提高效率。