10 hlist扩展

转自:

精益求精的Linux链表设计者(因为list.h没有署名,所以很可能就是Linus
Torvalds)认为
双头(next、prev)的双链表对于HASH表来说”过于浪费”,因而另行设计了一套用于HASH表
应用的hlist数据结构–单指针表头双循环链表,从上图可以看出,hlist的表头仅有一个指
向首节点的指针,而没有指向尾节点的指针,这样在可能是海量的HASH表中存储的表头就能
减少一半的空间消耗。

操作系统:ubuntu10.04

struct hlist_head
澳门新萄京官方网站,{
    struct hlist_node
*first;
};

前言:
    在稍微大点的项目中,基本都会遇到算法问题,特别是大数据的查找。
    在当前项目中,使用到了哈希链表。

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

一,概述
   
实现思路:用数组保存哈希桶的关键信息,再用链表链接数据到对应的哈希桶中。
        如:管理很多字符串。以a~z,?为哈希桶。
    澳门新萄京官方网站 1

 
这个数据结构与一般的hash-list数据结构定义有以下的区别:
1)
首先,hash的头节点仅存放一个指针,也就是first指针,指向的是list的头结点,没有tail
指针也就是指向list尾节点的指针,这样的考虑是为了节省空间–尤其在hash
bucket很大的
情况下可以节省一半的指针空间.

二,实现
    1,结构

2)
list的节点有两个指针,但是需要注意的是pprev是指针的指针,它指向的是前一个节点的
next指针(见下图).

点击(此处)折叠或打开

现在疑问来了:为什么hlist要使用pprev这样的指向前一个节点的next指针的设计呢?

  1. struct    hlist_node     

  2. {

  3.     struct hlist_node     *next;    //
    指向下一个结点的指针

  4.     struct hlist_node    **pprev;//
    指向上一个结点的next指针的地址

  5. };

  6. struct     hlist_head    

  7. {

  8.     struct hlist_node *first;    // 指向每一个hash桶的第一个结点的指针

  9. };

    +——–+                    ——-
    |        |                   ( hlist )
    |        |                    ——-
    +——–+
    |        |    +—+—-+     +—+—-+    +—+—-+
    |    +—+—>| | | +–+—->| | |  +-+—>| | |    |
    |    |   |    +-+-+-+–+     +-+-+–+-+    +-+-+—-+
    +——–+      |   |          |    |        |
    |    |   |      |   |          |    |        |
    |    +—+——+   +———-+    +——–+
    |        |
    +——–+
   ———–
  (   散列表  )
   ———–

   
2,初始化哈希桶

 
主要是基于以下几个考虑:
1)
hash-list中的list一般元素不多(如果太多了一般是设计出现了问题),即使遍历也不需要
太大的代价,同时需要得到尾结点的需求也不多.

点击(此处)折叠或打开

2)
如果对于一般节点而言,prev指向的是前一个指针,而对于first也就是hash的第一个元素
而言prev指向的是list的尾结点,那么在删除一个元素的时候还需要判断该节点是不是first
节点进行处理.而在hlist提供的删除节点的API中,并没有带上hlist_head这个参数,因此做这
个判断存在难度.

  1. // 初始化hash桶的头结点

  2. #define    INIT_HLIST_HEAD(ptr)    ((ptr)->first
    = NULL)

3)
以上两点说明了为什么不使用prev,现在来说明为什么需要的是pprev,也就是一个指向指
针的指针来保存前一个节点的next指针–因为这样做即使在删除的节点是first节点时也可以
通过*pprev =
next;直接修改指针的指向.来看删除一个节点和修改list头结点的两个API:

    澳门新萄京官方网站 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; 
       //
此时n是hash的first指针,因此它的pprev指向的是hash的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;
        // pprev指向的是前一个节点的next指针,
        // 而当该节点是first节点时指向自己,
        // 因此两种情况下不论该节点是一般的节点
        //
还是头结点都可以通过这个操作删除掉所需删除的节点
    if (next)
        next->pprev = pprev;
}

点击(此处)折叠或打开

 

  1. // 初始化hash桶的普通结点

  2. static    inline    void    INIT_HLIST_NODE(struct hlist_node *node)

  3. {

  4.     node->next    =
    NULL;

  5.     node->pprev    =
    NULL;

  6. }

    澳门新萄京官方网站 3

    4,添加节点到哈希桶中

点击(此处)折叠或打开

  1. /**

  2.  * hlist_add_head

  3.  * @n:
    the element to add to the
    hash list.

  4.  * @h:
    the list to add to.

  5.  */

  6. static    inline    void    hlist_add_head(struct hlist_node *n,struct
    hlist_head *h)    

  7. {

  8.     struct hlist_node    *first
    = h->first;

  9.     n->next        =
    first;

  10.     if (first)

  11.         first->pprev    =
    &n->next;

  12.     h->first     = n;

  13.     n->pprev    =
    &h->first;

  14. }

    澳门新萄京官方网站 4
    澳门新萄京官方网站 5    

    5,把节点插入到指定节点前面

点击(此处)折叠或打开

  1. /* next must
    be !=
    NULL */

  2. /*
    n:要添加的新的节点。

  3.  * next:在next节点之前添加n。

  4.  *
    在next节点的前面添加一个新的节点n,在使用这个函数中要特别注意,next不能为NULL。

  5.  */

  6. static    inline    void    hlist_add_before(struct hlist_node *n,

  7.                         struct hlist_node *next)

  8. {

  9.     n->pprev    =
    next->pprev;

  10.     n->next        =
    next;

  11.     next->pprev    =
    &n->next;

  12.     *(n->pprev)    = n;

  13. }

网站地图xml地图