Chinaunix首页 | 论坛 | 博客

哥本哈根的冬天ChinaUnix博客shanck.blog.chinaunix.net

首页　| 　博文目录　| 　关于我

shanck

  • 博客访问： 1137018
  • 博文数量： 300
  • 博客积分： 37
  • 博客等级： 民兵
  • 技术积分： 772
  • 用 户 组： 普通用户
  • 注册时间： 2012-02-26 04:46
文章分类

全部博文（300）

文章存档

2017年（4）

2016年（7）

2015年（19）

2014年（72）

2013年（71）

2012年（127）

我的朋友
最近访客
推荐博文
相关博文
linux下C语言实现的哈希链表

分类： LINUX

2014-05-29 23:57:38

原文地址：linux下C语言实现的哈希链表 作者：andyhzw

操作系统：ubuntu10.04

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

一，概述
    实现思路：用数组保存哈希桶的关键信息，再用链表链接数据到对应的哈希桶中。
        如：管理很多字符串。以a~z，？为哈希桶。
    

二，实现
    1，结构

点击(此处)折叠或打开

  1. struct    hlist_node     
  2. {
  3.     struct hlist_node     *next;    // 指向下一个结点的指针
  4.     struct hlist_node    **pprev;// 指向上一个结点的next指针的地址
  5. };


  8. struct     hlist_head    
  9. {
  10.     struct hlist_node *first;    // 指向每一个hash桶的第一个结点的指针
  11. };

    2，初始化哈希桶

点击(此处)折叠或打开

  1. // 初始化hash桶的头结点
  2. #define    INIT_HLIST_HEAD(ptr)    ((ptr)->first = NULL)
    

    3，初始化哈希桶中的每一个节点

点击(此处)折叠或打开

  1. // 初始化hash桶的普通结点
  2. static    inline    void    INIT_HLIST_NODE(struct hlist_node *node)
  3. {
  4.     node->next    = NULL;
  5.     node->pprev    = NULL;
  6. }
    

    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;

  11.     if (first)
  12.         first->pprev    = &n->next;

  14.     h->first     = n;
  15.     n->pprev    = &h->first;
  16. }
    
        

    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. }
    


    6，把节点插入到指定节点之后

点击(此处)折叠或打开

  1. /* next must be != NULL */
  2. /* n：要添加的新的节点。
  3.  * next：表示在next节点之后添加n。
  4.  * 在next 节点的后面添加一个新的节点n，这里也要求next不能为NULL
  5.  */
  6. static inline void hlist_add_after(struct hlist_node *n,
  7.                     struct hlist_node *next)
  8. {
  9.     n->next = next->next;
  10.     next->next = n;
  11.     n->pprev = &next->next;

  13.     if(n->next)
  14.         n->next->pprev = &n->next;
  15. }
    

    7，删除节点 

点击(此处)折叠或打开

  1. /* n：要删除的节点。
  2.  * 对于删除操作的话，要注意n是不是末尾节点，如果是末尾节点的话，next就是NULL?
  3.  * 所以就没有指向的pprev，就更不能进行相应的修改了，否则进行修改。
  4.  */
  5. static inline void __hlist_del(struct hlist_node *n)
  6. {
  7.     struct hlist_node *next = n->next;
  8.     struct hlist_node **pprev = n->pprev;
  9.     *pprev = next;
  10.     if (next)    
  11.         next->pprev = pprev;
  12. }


  15. /* n：要删除的节点。
  16.  * 在这个函数中首先删除了n节点，之后将n节点的两个指针指向了LIST_POSION，表示不可使用的地方
  17.  */
  18. static inline void hlist_del(struct hlist_node *n)
  19. {
  20.     __hlist_del(n);
  21.     n->next     = LIST_POISON1;
  22.     n->pprev    = LIST_POISON2;
  23. }

    8，判断节点是否在哈希桶中

点击(此处)折叠或打开

  1. /*
  2.  * 判断一个结点是否已经存在于hash桶中
  3.  * 判断h->prev是不是为空，如果pprev的指向是空的话，表示这个节点没有添加到这个链表当中来，
  4.  * 如果是空，返回true，否则返回false
  5.  */
  6. static inline int hlist_unhashed(const struct hlist_node *h)
  7. {
  8.     return !h->pprev;
  9. }

    9，判断哈希桶是否为空

点击(此处)折叠或打开

  1. // 判断一个hash桶是否为空
  2. /* h：struct hlist_head节点指针（hlist链表的头节点）。
  3.  * 判断hlist链表是不是空链表，如果是，返回true，否则返回false。
  4.  */
  5. static inline int hlist_empty(const struct hlist_head *h)
  6. {
  7.     return !h->first;
  8. }

    10，遍历

点击(此处)折叠或打开

  1. /* ptr：表示struct hlist_node类型的一个地址。
  2.  * type：结构体名
  3.  * member：type结构体中的hlist_node成员变量的名称
  4.  * 表示得到ptr所指地址的这个结构体的首地址
  5.  */

  7. #define hlist_entry(ptr, type, member) container_of(ptr,type,member)


  10. /* pos：struct hlist_node类型的一个指针；
  11.  * head：struct hlist_head类型的一个指针，表示hlist链表的头结点。
  12.  * 这个实际上就是一个for循环，从头到尾遍历链表。
  13.  */
  14. #define hlist_for_each(pos, head) \
  15.     for (pos = (head)->first; pos != NULL ; 1; }); \
  16.      pos = pos->next)


  19. /* 这个实际上就是一个for循环，从头到尾遍历链表。这个和前面的不同的是多了一个n，
  20.  * 这么做是为了遍历过程中防止断链的发生。删除时用这个。
  21.  * pos：struct hlist_node类型的一个指针；
  22.  * n：struct hlist_node类型的一个指针；
  23.  * head：struct hlist_head类型的一个指针，表示hlist链表的头结点。
  24.  */
  25. #define hlist_for_each_safe(pos, n, head) \
  26.     for (pos = (head)->first; pos && ({ n = pos->next; 1; }); \
  27.      pos = n)



  31. /* tops：用来存放遍历到的数据结构的地址，类型是type *；
  32.  * pos：struct hlist_node类型的一个指针；
  33.  * head：hlist链表的头结点；
  34.  * member：struct hlist_node在type结构体中的变量的名称。
  35.  * 在循环中，我们就可以使用tops来指向type类型结构体的任何一个变量了。
  36.  */
  37. /**
  38.  * hlist_for_each_entry    - iterate over list of given type
  39.  * @tpos:    the type * to use as a loop cursor.
  40.  * @pos:    the &struct hlist_node to use as a loop cursor.
  41.  * @head:    the head for your list.
  42.  * @member:    the name of the hlist_node within the struct.
  43.  */
  44. #define hlist_for_each_entry(tpos, pos, head, member)             \
  45.     for (pos = (head)->first;                     \
  46.      (pos != NULL) &&             \
  47.         ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
  48.      pos = pos->next)



  52. /* tops：用来存放遍历到的数据结构的地址，类型是type *；
  53.  * pos：struct hlist_node类型的一个指针；
  54.  * n：struct hlist_node类型的一个指针；
  55.  * head：hlist链表的头结点；
  56.  * member：struct hlist_node在type结构体中的变量的名称。
  57.  * 在循环中，我们就可以使用tops来指向type
  58.  * 类型结构体的任何一个变量了。这个宏函数也是为了防止在遍历的时候删除节点而引入的。
  59.  */
  60. /**
  61.  * hlist_for_each_entry_safe - iterate over list of given type safe against
  62. removal of list entry
  63.  * @tpos:    the type * to use as a loop cursor.
  64.  * @pos:    the &struct hlist_node to use as a loop cursor.
  65.  * @n:        another &struct hlist_node to use as temporary storage
  66.  * @head:    the head for your list.
  67.  * @member:    the name of the hlist_node within the struct.
  68.  */
  69. #define hlist_for_each_entry_safe(tpos, pos, n, head, memsber)          \
  70.     for (pos = (head)->first;                     \
  71.      pos && ({ n = pos->next; 1; }) &&                  \
  72.         ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
  73.      pos = n)


三，实例

点击(此处)折叠或打开

  1. /*
  2.  * hlist begin
  3.  */

  5. #define        CMD_HASH_HEAD_SIZE        27

  7. typedef    struct _cmd_hash_head
  8. {
  9.     struct     hlist_head        head;        // 哈希桶的首地址
  10.     int8_t                    ch;            // 哈希桶的关键字(a~z,?，总共27个)
  11.     int8_t                    offset;        // 这个哈希桶在整个哈希表中的偏移
  12.     int16_t                    count;        // 当前哈希桶中节点的个数
  13. }cmd_hash_head_t;

  15. typedef    struct    _cmd_hash_node
  16. {
  17.     struct    hlist_node        node;
  18.     int8_t                    name[20];
  19. }cmd_hash_node_t;

  21. static    cmd_hash_head_t        cmd_hash[CMD_HASH_HEAD_SIZE];

  23. static    void    cmd_hash_init(void)
  24. {
  25.     int32_t        index = 0;

  27.     memset(cmd_hash,0,sizeof(cmd_hash));

  29.     for(index = 0; index < (CMD_HASH_HEAD_SIZE - 1); index++)
  30.     {
  31.         INIT_HLIST_HEAD(&cmd_hash[index].head);
  32.         cmd_hash[index].count    = 0;
  33.         cmd_hash[index].offset    = index;
  34.         cmd_hash[index].ch        = 'a' + index;
  35.     }    

  37.     index = CMD_HASH_HEAD_SIZE - 1;
  38.     INIT_HLIST_HEAD(&cmd_hash[index].head);
  39.     cmd_hash[index].count    = 0;
  40.     cmd_hash[index].offset    = index;
  41.     cmd_hash[index].ch        = '?';
  42. }

  44. static    void    cmd_hash_show(void)
  45. {
  46.     int32_t        index = 0;

  48.     for (index = 0; index < (CMD_HASH_HEAD_SIZE - 1); index++)
  49.         printf("hash%d,head : %p,count : %d,offset : %d,ch : %c\n",index,
  50.                 cmd_hash[index].head,cmd_hash[index].count,cmd_hash[index].offset,cmd_hash[index].ch);

  52.     index = CMD_HASH_HEAD_SIZE - 1;
  53.     printf("hash%d,head : %p,count : %d,offset : %d,ch : %c\n",index,
  54.             cmd_hash[index].head,cmd_hash[index].count,cmd_hash[index].offset,cmd_hash[index].ch);
  55. }


  58. static    void    to_lower(int8_t    *str)
  59. {
  60.     int32_t        len     = 0;
  61.     int32_t        index     = 0;

  63.     if (str == NULL)    return;
  64.     len     = strlen((char*)str);

  66.     for (index = 0; index < len; index++)
  67.     {
  68.         str[index] = tolower(str[index]);
  69.     }
  70. }

  72. static    int8_t    node_type(int8_t    *name)
  73. {
  74.     int8_t    ch         = 0x00;
  75.     int8_t    offset     = 0;
  76.     if (name == NULL)    return -1;

  78.     ch    = name[0];
  79.     switch(ch)
  80.     {
  81.         case 'a':
  82.         case 'b':
  83.         case 'c':
  84.         case 'd':
  85.         case 'e':
  86.         case 'f':
  87.         case 'g':
  88.         case 'h':
  89.         case 'i':
  90.         case 'j':
  91.         case 'k':
  92.         case 'l':
  93.         case 'm':
  94.         case 'n':
  95.         case 'o':
  96.         case 'p':
  97.         case 'q':
  98.         case 'r':
  99.         case 's':
  100.         case 't':
  101.         case 'u':
  102.         case 'v':
  103.         case 'w':
  104.         case 'x':
  105.         case 'y':
  106.         case 'z':
  107.             offset = ch - 'a' + 0;
  108.             break;

  110.         default :
  111.             offset = 26;
  112.             break;
  113.     }

  115.     return offset;    
  116. }


  119. //static    cmd_hash_node_t ptr_buffer[100];
  120. static    void    hash_node_init(int8_t    *name)
  121. {
  122.     int8_t        offset = 0;

  124.     cmd_hash_node_t *node_ptr = (cmd_hash_node_t*)calloc(1,sizeof(cmd_hash_node_t));
  125.     

  127.     offset = node_type(name);

  129.     if(offset < 0)    return;

  131.     strlcpy(node_ptr->name, name, strlen((char*)name));
  132.     INIT_HLIST_NODE(&node_ptr->node);
  133.     hlist_add_head(&node_ptr->node,&cmd_hash[offset].head);
  134.     cmd_hash[offset].count++;
  135. }


  138. static    void    cmd_hash_node_init(void)
  139. {
  140.     hash_node_init((int8_t*)"hello");
  141.     hash_node_init((int8_t*)"help");
  142.     hash_node_init((int8_t*)"scan");
  143.     hash_node_init((int8_t*)"???");
  144. }

  146. static    void    cmd_hash_node_show(void)
  147. {
  148.     int32_t        index = 0;
  149.     int16_t        count = 0;
  150.     
  151.     cmd_hash_node_t    *entry = NULL;
  152.     struct hlist_node *ptr = NULL;

  154.     printf("display\n");

  156.     for (index = 0; index < CMD_HASH_HEAD_SIZE; index++)
  157.     {
  158.         count = cmd_hash[index].count;
  159.         if (count > 0)
  160.         {
  161.             printf("hash%d,head : %p,count : %d,offset : %d,ch : %c\n",index,
  162.                 cmd_hash[index].head,cmd_hash[index].count,cmd_hash[index].offset,cmd_hash[index].ch);

  164.             hlist_for_each_entry(entry,ptr, &cmd_hash[index].head, node)
  165.             {
  166.                 printf("    name : %s\n",entry->name);
  167.             }    
  168.         }        
  169.     }
  170. }


  173. static    void    test_hlist_oper(void)
  174. {
  175.     cmd_hash_init();
  176.     cmd_hash_show();
  177.     cmd_hash_node_init();
  178.     cmd_hash_show();
  179.     cmd_hash_node_show();    
  180. }


  183. static    void    test_hlist(void)
  184. {
  185.     test_hlist_oper();
  186. }

  188. /*
  189.  * hlist end
  190.  */

    结果：
    




四，参考
1，linux内核源码



阅读(1077) | 评论(0) | 转发(0) |
0

上一篇：《现代操作系统》 --- 虚拟内存

下一篇：C++虚基类的实现

给主人留下些什么吧！~~
关于我们 | 关于IT168 | 联系方式 | 广告合作 | 法律声明 | 免费注册

Copyright 2001-2010 ChinaUnix.net All Rights Reserved 北京皓辰网域网络信息技术有限公司. 版权所有

感谢所有关心和支持过ChinaUnix的朋友们

16024965号-6