哈希链表hlist解惑

链表(list)和哈希表(hlist)是内核常用到的两个工具，负责组织内核中很多的数据结构，如在进程管理中用于组织进程，文件系统中的inode节点链表，dentry链表，vfsmount链表等等。

链表使用struct list_head内嵌结构来将其寄生的结构组织成双向循环链表，并且表头跟普通节点的结构相同，非常容易理解。

但哈希表不同，其表头跟普通节点采用不同的数据结构，并且节点的组织也不是按照普通双向循环链表的形式组织的。

 

 

哈希表的表头结构为：

struct hlist_head {

        struct hlist_node *first;

};

 

hlist的表头仅有一个指向首节点的指针，而没有指向尾节点的指针（实现完全的双向循环并无必要），这样在可能是海量的Hash表中存储的表头就能减少一半的空间消耗。

 

哈希表的节点结构为：

struct hlist_node {

        struct hlist_node *next, **pprev;

};

 

next为指向下一个节点的指针，hlist节点的pprev不再是指向前一个节点的指针，而是指向前一个节点（可能是表头）中的next（对于表头则是 first）指针，从而在表头插入的操作可以通过一致的*(node->pprev)访问或修改前节点的next（或first）指针。如hlist_add_before操作，在任意节点前添加节点操作是一致的，即使该节点为表头后的第一个节点。

 

static inline void hlist_add_before(struct hlist_node *n,

                                        struct hlist_node *next)

{

        n->pprev = next->pprev;  //修改n的ppre

        n->next = next;         //修改n的next

        next->pprev = &n->next;  //修改下一个节点的ppre

        *(n->pprev) = n;        //修改前一个节点的next

}

 

 

 

在遍历上，如果使用hlist_hode, list_node指针进行遍历，两者过程大致相似。

 

#define list_for_each(pos, head) \

        for (pos = (head)->next; prefetch(pos->next), pos != (head); \

                pos = pos->next)

 

#define hlist_for_each(pos, head) \

        for (pos = (head)->first; pos && ({ prefetch(pos->next); 1; }); \

             pos = pos->next)

 

如果使用其寄生结构的指针进行遍历，则hlist与list也略有不同，hlist在遍历时需要一个指向hlist_node的临时指针，该指针的引入，一是为了遍历，而list的遍历在list_entry的参数中实现了（红色部分），更主要的目的在于判断结束，因为hlist最后一个节点的next为NULL，只有hlist_node指向NULL时才算结束，而这个NULL不包含在任何寄生结构内，不能通过tpos->member的方式访问到，故临时变量pos的引入时必须的。

 

 

#define list_for_each_entry(pos, head, member) \

        for (pos = list_entry((head)->next, typeof(*pos), member); \

             prefetch(pos->member.next), &pos->member != (head); \

             pos = list_entry(pos->member.next, typeof(*pos), member))

 

#define hlist_for_each_entry(tpos, pos, head, member) \

        for (pos = (head)->first; \

             pos && ({ prefetch(pos->next); 1;}) && \

                ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \

             pos = pos->next)

 

 

另外，list和hlist的遍历都实现了safe版本，因在遍历时，没有任何特别的东西来阻止对链表执行删除操作（通常在使用链表时使用锁来保护并发访问）。安全版本的遍历函数使用临时存放的方法是的检索链表时能不被删除操作所影响。

 

#define list_for_each_safe(pos, n, head) \

        for (pos = (head)->next, n = pos->next; pos != (head); \

                pos = n, n = pos->next)

 

#define hlist_for_each_safe(pos, n, head) \

        for (pos = (head)->first; pos && ({ n = pos->next; 1; }); \

             pos = n)

 

附件：在用户空间使用的list.h头文件