摘要：
structhlist_head{structhlist_node*first;};structhlist_node{structhlist_node*next,**pprev;};其内存结构如下：hlist_head结构体仅仅有一个first指针.hlist_node结构体有两个指针，next和ppre。这样的设计显然会造成链表中节点数据结构不一致，如果hlist_node采用的next和pre指针，那么对于第一个节点和其他节点操作必然会使不一致。hlist_node巧妙地将pprev指向上一个节点的next指针的地址，由于hlist_head和hlist_node指向的下一个节点的指针类型相同，这样就解决了通用性。
参考自：https://blog.csdn.net/zhanglei4214/article/details/6767288
一、hlist结构简介
hlist_head 和 hlist_node 是位于linux内核中的数据结构，其设计初衷主要是为了减少Hash表的内存消耗。
structhlist_head { struct hlist_node *first; }; structhlist_node { struct hlist_node *next, **pprev; };
其内存结构如下：
hlist_head 结构体仅仅有一个first指针.
hlist_node 结构体有两个指针，next 和 ppre。其中next指针指向下一个hlist_node,如果该节点为最后一个一个节点，那么next指向NULL。
这样设计的原因在于：通常我们在使用Hash表是为实现快速查找，那么Hash表通常会维护一张相对较大的数组，否则的会带来较大的冲突，而一张较大的数组必然会带来较大的内存消耗。我们知道通常一个Hash表中每一个dentry(每一个具体数元素)会使用两个指针，有其中一个指向尾节点，而我们知道在Hash表中的list通常是非常短（如果过长，说明冲突过多），那么显然这个指向尾节点的指向我们就不那么的必要，Hash表中的每一个denry只用保存一个指针。这样的设计显然会造成链表中节点数据结构不一致，如果hlist_node采用的next和pre指针，那么对于第一个节点和其他节点操作必然会使不一致。hlist_node巧妙地将pprev指向上一个节点的next指针的地址，由于hlist_head和hlist_node指向的下一个节点的指针类型相同，这样就解决了通用性。
二、常用接口
（1）hlist_head 和 hlist_node初始化
#define HLIST_HEAD_INIT { .first = NULL } #define HLIST_HEAD(name) struct hlist_head name = { .first = NULL } #define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL) static inline void INIT_HLIST_NODE(struct hlist_node *h) { h->next =NULL; h->pprev =NULL; }
（2）添加节点
static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h) { struct hlist_node *first = h->first; n->next =first; if(first) first->pprev = &n->next; h->first =n; n->pprev = &h->first; }
（3）删除节点
static inline void __hlist_del(struct hlist_node *n) { struct hlist_node *next = n->next; struct hlist_node **pprev = n->pprev; *pprev =next; if(next) next->pprev =pprev; } static inline void hlist_del(struct hlist_node *n) { __hlist_del(n); n->next =LIST_POISON1; n->pprev =LIST_POISON2; }
（4）遍历节点
#define hlist_for_each_entry(pos, head, member) for (pos = hlist_entry_safe((head)->first, typeof(*(pos)), member); pos; pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))