当前位置: IT大杂烩 > Ubuntu  > Linux内核hlist数据结构分析

Linux内核hlist数据结构分析

www.someabcd.com  网友分享于:Jun 8, 2018 6:08:01 PM

标签:hlist_head   hlist_node   hlist_for_each_entry   哈希表   


     在内核编程中哈希链表hlist使用非常多,比如在openvswitch中流表的存储中就使用了(见[1])。 hlist的表头仅有一个指向首节点的指针,而没有指向尾节点的指针,这样在有很多个buckets的HASH表中存储的表头就能减少一半的空间消耗。
     和hlist相关的数据结构如下,桶中存储的 hlist_head 是具有相同hash值的entry构成的链表,每个entry包含一个 hlist_node 成员,通过它链入到这个哈希链表中。
struct  hlist_head {
       struct  hlist_node *  first ;
};

//next指向下一个节点
// pprev指向前一个节点的next域
struct  hlist_node {
       struct  hlist_node *  next , **  pprev ;
};

结构图为:
bubuko.com,布布扣

由于头结点和其他节点的类型不一致,这样就不能使用普通的prev指针指向前一个节点(否则处理的时候还要讨论是否是第一个节点,没有通用性),这里设计者的巧妙之处就是pprev指针指向前一个节点的next,统一了后续所有的节点。

一些有用的宏:
//头结点初始化
#define  HLIST_HEAD_INIT { .first = NULL }
//构造一个名为name的头结点
#define  HLIST_HEAD(name)  struct  hlist_head name = {  .first = NULL }

//初始化头指针,链表指针
#define  INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)
#define  INIT_HLIST_NODE(ptr) ((ptr)->next = NULL, (ptr)->pprev = NULL)

1.删除节点
next得到当前节点的下一个节点,pprev是前一个节点的next字段的地址,那么*pprev就指向的是当前这个节点,那么  *pprev=next 就把当前节点更新为下一个节点了,如果n不是最后一个节点,还要设置next->pprev.
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;
}

2.插入节点
(1)头插入:让插入的节点成为链表的第一个节点,依次更新相应的指针,示意图如下。
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 ;
}
(2)在已知节点next之前/之后插入,通过自己画图,很容易理解清楚。
/* next must be != NULL */
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;
}

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 ;

       if (next->  next )
          next->  next ->  pprev   = &next->  next ;
}

3.通过看一个节点h的pprev是否为空,判断其是否在哈希链表中。
static   inline  int  hlist_unhashed ( const  struct  hlist_node *h)
{
       return  !h->  pprev ;
}

4.哈希链表的遍历(iterate)相关代码
//通过一个字段member的地址 ptr,得到包含它的容器的地址
#define  hlist_entry(ptr, type, member) container_of(ptr,type,member)

//用 pos作为游标来遍历这个链表, prefetch是数据预取
#define  hlist_for_each(pos, head) \
       for  (pos = (head)->first; pos && ({ prefetch(pos->next); 1; }); \
          pos = pos->next)

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

//通用的哈希链表遍历,其中 pos指向当前节点, tpos指向的包含hlist_node的当前结构体的指针
#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)

/**
 * hlist_for_each_entry_continue - iterate over a hlist continuing after existing point
 * @ tpos: the type * to use as a loop counter.
 * @ pos:  the &struct hlist_node to use as a loop counter.
 * @member:   the name of the hlist_node within the struct.
 */
#define  hlist_for_each_entry_continue(tpos, pos, member)           \
       for  (pos = (pos)->next;                          \
          pos && ({ prefetch(pos->next); 1;}) &&           \
          ({ tpos = hlist_entry(pos,  typeof  (*tpos), member); 1;}); \
          pos = pos->next)

/**
 * hlist_for_each_entry_from - iterate over a hlist continuing from existing point
 * @ tpos: the type * to use as a loop counter.
 * @ pos:  the &struct hlist_node to use as a loop counter.
 * @member:   the name of the hlist_node within the struct.
 */
#define  hlist_for_each_entry_from(tpos, pos, member)            \
       for  (; pos && ({ prefetch(pos->next); 1;}) &&              \
          ({ tpos = hlist_entry(pos,  typeof  (*tpos), member); 1;}); \
          pos = pos->next)

/**
 * hlist_for_each_entry_safe - iterate over list of given type safe against removal of list entry
 * @ tpos: the type * to use as a loop counter.
 * @ pos:  the &struct hlist_node to use as a loop counter.
 * @n:        another &struct hlist_node to use as temporary storage
 * @head: the head for your list.
 * @member:   the name of the hlist_node within the struct.
 */
#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)





Linux内核hlist数据结构分析,布布扣,bubuko.com

Linux内核hlist数据结构分析

标签:hlist_head   hlist_node   hlist_for_each_entry   哈希表   

发布此文章仅为传递网友分享,不代表本站观点,若侵权请联系我们删除,本站将不对此承担任何责任。
Copyright ©2018  IT大杂烩  版权所有  京ICP备11030978号-1 网站地图