linux通用hash链表

   与我昨天写的《linux通用链表》类似，主要分析linux提供的头文件代码（linux/list.h）。

一、结构定义及初始化

/* hash头节点定义 */
struct hlist_head {
    struct hlist_node *first;
};
/* hash节点定义 */
struct hlist_node {
    struct hlist_node *next, **pprev;
};
/* 头节点初始化 */
#define HLIST_HEAD_INIT { .first = NULL }
#define HLIST_HEAD(name) struct hlist_head name = {  .first = NULL }
#define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)
/* hash节点初始化 */
#define INIT_HLIST_NODE(ptr) ((ptr)->next = NULL, (ptr)->pprev = NULL)

   这里需要说明两个问题：

1. 头节点为什么只有一个指针成员，难道不能和hash节点同一定义？

2. hash节点中为什么用**pprev，而不和通用链表那样使用*prev？

   hash链表的目的就是解决在大量数据下的查找问题。也就是说一般情况下hash桶会很大，头节点也就会很多。为了节省内存，设计人员就只使用一个指针，指向hash链的第一个节点。这样就导致头节点和hash链节点的数据结构不一致，有为了实现通用性就出现了二级指针**pprev，指向前一个节点的*next域。如何看出通用性的，请看下面是如何删除节点的。

二、删除节点

   这里与通用链表的删除节点接口类似，LIST_POISON1和LIST_POISON2可以参考《linux通用链表》中介绍。

/* 从hash链中删除节点，不需要考虑是否为链中首节点。
 * 如果将**pprev设计为*prev，由于头节点后hash链中节点数据结构不一致，
 * 那就要特殊处理链中首节点的prev，因为它指向的数据结构与其他节点
 * prev指向的不一样。
 */
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;
}
static inline void hlist_del_init(struct hlist_node *n)
{
    if (n->pprev)  {
        __hlist_del(n);    //从hash链中删除节点
        INIT_HLIST_NODE(n);//节点初始化
    }
}

三、添加节点

/* 添加到hash链的头部 */
static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
{
    struct hlist_node *first = h->first;
        /* 将原来的first节点连接到n后面 */
    n->next = first;
    if (first)
        first->pprev = &n->next;
        /* 再将n连接到头结点h */
    h->first = n;
    n->pprev = &h->first;
}
/* 将n添加到next节点前面，但要保证next节点非空 */
static inline void hlist_add_before(struct hlist_node *n,
                    struct hlist_node *next)
{
    n->pprev = next->pprev;
    n->next = next;
    next->pprev = &n->next;
    *(n->pprev) = n;
}
/* 将next添加到n节点后面 */
static inline void hlist_add_after(struct hlist_node *n,
                    struct hlist_node *next)
{
    next->next = n->next;
    n->next = next;
    next->pprev = &n->next;
        /* next不是添加到hash链的尾部，则需要设置下一节点的pprev */
    if(next->next)
        next->next->pprev  = &next->next;
}

四、hash链表遍历

   与标准链表中遍历接口类似，有entry/safe之分。

   先介绍一条语句{ n = pos->next; 1; }。它是复合语句，返回值为最后的一条语句1;。即该语句永远为真。在hlist_for_each函数中，如果pos为空则循环结束，如果pos不为空，那么pos->next可能为空，但该循环还不能结束，所以就使用{ n = pos->next; 1; }确保&&后面为真。

/* 返回hash链中的用户数据结构地址 */
#define hlist_entry(ptr, type, member) container_of(ptr,type,member)
/* 与标准链表类似，该接口内不能添加/删除节点 */
#define hlist_for_each(pos, head)     for (pos = (head)->first; pos;          pos = pos->next)
/* 该循环内可以添加删除节点 */
#define hlist_for_each_safe(pos, n, head)     for (pos = (head)->first; pos && ({ n = pos->next; 1; });          pos = n)
/* 在循环内，可访问用户定义的数据结构（带有entry关键字） */
#define hlist_for_each_entry(tpos, pos, head, member)                for (pos = (head)->first;                              pos &&                  ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;});          pos = pos->next)
/* 从pos的下一个节点开始遍历 */
#define hlist_for_each_entry_continue(tpos, pos, member)             for (pos = (pos)->next;                                pos &&                  ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;});          pos = pos->next)
/* 从pos节点开始遍历 */
#define hlist_for_each_entry_from(tpos, pos, member)                 for (; pos&&                     ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;});          pos = pos->next)
/* 安全模式下遍历，n为循环时使用的临时变量，只能对pos操作 */
#define hlist_for_each_entry_safe(tpos, pos, n, head, member)            for (pos = (head)->first;                              pos && ({ n = pos->next; 1; }) &&                        ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;});          pos = n)

五、其他

/* 判断节点h是否在hash链表中。
   很巧妙使用了pprev，该指针指向前一节点的next域 */
static inline int hlist_unhashed(const struct hlist_node *h)
{
    return !h->pprev;
}
/* 判断hash链表是否为空 */
static inline int hlist_empty(const struct hlist_head *h)
{
    return !h->first;
}

本文出自 “cizyzhang” 博客，请务必保留此出处http://cizyzhang.blog.51cto.com/1529108/1381084

linux通用hash链表,古老的榕树,5-wow.com