Chinaunix首页 | 论坛 | 博客
  • 博客访问: 121415
  • 博文数量: 41
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 22
  • 用 户 组: 普通用户
  • 注册时间: 2013-01-25 16:01
文章分类
文章存档

2015年(6)

2014年(22)

2013年(13)

我的朋友

分类: LINUX

2014-06-04 20:14:45

操作系统:ubuntu10.04

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

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

二,实现
    1,结构

点击(此处)折叠或打开

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

    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;

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

  12.     h->first     = n;
  13.     n->pprev    = &h->first;
  14. }
    
        

    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;

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

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


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

    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.  */

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


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


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



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



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


三,实例

点击(此处)折叠或打开

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

  4. #define        CMD_HASH_HEAD_SIZE        27

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

  12. typedef    struct    _cmd_hash_node
  13. {
  14.     struct    hlist_node        node;
  15.     int8_t                    name[20];
  16. }cmd_hash_node_t;

  17. static    cmd_hash_head_t        cmd_hash[CMD_HASH_HEAD_SIZE];

  18. static    void    cmd_hash_init(void)
  19. {
  20.     int32_t        index = 0;

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

  22.     for(index = 0; index < (CMD_HASH_HEAD_SIZE - 1); index++)
  23.     {
  24.         INIT_HLIST_HEAD(&cmd_hash[index].head);
  25.         cmd_hash[index].count    = 0;
  26.         cmd_hash[index].offset    = index;
  27.         cmd_hash[index].ch        = 'a' + index;
  28.     }    

  29.     index = CMD_HASH_HEAD_SIZE - 1;
  30.     INIT_HLIST_HEAD(&cmd_hash[index].head);
  31.     cmd_hash[index].count    = 0;
  32.     cmd_hash[index].offset    = index;
  33.     cmd_hash[index].ch        = '?';
  34. }

  35. static    void    cmd_hash_show(void)
  36. {
  37.     int32_t        index = 0;

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

  41.     index = CMD_HASH_HEAD_SIZE - 1;
  42.     printf("hash%d,head : %p,count : %d,offset : %d,ch : %c\n",index,
  43.             cmd_hash[index].head,cmd_hash[index].count,cmd_hash[index].offset,cmd_hash[index].ch);
  44. }


  45. static    void    to_lower(int8_t    *str)
  46. {
  47.     int32_t        len     = 0;
  48.     int32_t        index     = 0;

  49.     if (str == NULL)    return;
  50.     len     = strlen((char*)str);

  51.     for (index = 0; index < len; index++)
  52.     {
  53.         str[index] = tolower(str[index]);
  54.     }
  55. }

  56. static    int8_t    node_type(int8_t    *name)
  57. {
  58.     int8_t    ch         = 0x00;
  59.     int8_t    offset     = 0;
  60.     if (name == NULL)    return -1;

  61.     ch    = name[0];
  62.     switch(ch)
  63.     {
  64.         case 'a':
  65.         case 'b':
  66.         case 'c':
  67.         case 'd':
  68.         case 'e':
  69.         case 'f':
  70.         case 'g':
  71.         case 'h':
  72.         case 'i':
  73.         case 'j':
  74.         case 'k':
  75.         case 'l':
  76.         case 'm':
  77.         case 'n':
  78.         case 'o':
  79.         case 'p':
  80.         case 'q':
  81.         case 'r':
  82.         case 's':
  83.         case 't':
  84.         case 'u':
  85.         case 'v':
  86.         case 'w':
  87.         case 'x':
  88.         case 'y':
  89.         case 'z':
  90.             offset = ch - 'a' + 0;
  91.             break;

  92.         default :
  93.             offset = 26;
  94.             break;
  95.     }

  96.     return offset;    
  97. }


  98. //static    cmd_hash_node_t ptr_buffer[100];
  99. static    void    hash_node_init(int8_t    *name)
  100. {
  101.     int8_t        offset = 0;

  102.     cmd_hash_node_t *node_ptr = (cmd_hash_node_t*)calloc(1,sizeof(cmd_hash_node_t));
  103.     

  104.     offset = node_type(name);

  105.     if(offset < 0)    return;

  106.     strlcpy(node_ptr->name, name, strlen((char*)name));
  107.     INIT_HLIST_NODE(&node_ptr->node);
  108.     hlist_add_head(&node_ptr->node,&cmd_hash[offset].head);
  109.     cmd_hash[offset].count++;
  110. }


  111. static    void    cmd_hash_node_init(void)
  112. {
  113.     hash_node_init((int8_t*)"hello");
  114.     hash_node_init((int8_t*)"help");
  115.     hash_node_init((int8_t*)"scan");
  116.     hash_node_init((int8_t*)"???");
  117. }

  118. static    void    cmd_hash_node_show(void)
  119. {
  120.     int32_t        index = 0;
  121.     int16_t        count = 0;
  122.     
  123.     cmd_hash_node_t    *entry = NULL;
  124.     struct hlist_node *ptr = NULL;

  125.     printf("display\n");

  126.     for (index = 0; index < CMD_HASH_HEAD_SIZE; index++)
  127.     {
  128.         count = cmd_hash[index].count;
  129.         if (count > 0)
  130.         {
  131.             printf("hash%d,head : %p,count : %d,offset : %d,ch : %c\n",index,
  132.                 cmd_hash[index].head,cmd_hash[index].count,cmd_hash[index].offset,cmd_hash[index].ch);

  133.             hlist_for_each_entry(entry,ptr, &cmd_hash[index].head, node)
  134.             {
  135.                 printf("    name : %s\n",entry->name);
  136.             }    
  137.         }        
  138.     }
  139. }


  140. static    void    test_hlist_oper(void)
  141. {
  142.     cmd_hash_init();
  143.     cmd_hash_show();
  144.     cmd_hash_node_init();
  145.     cmd_hash_show();
  146.     cmd_hash_node_show();    
  147. }


  148. static    void    test_hlist(void)
  149. {
  150.     test_hlist_oper();
  151. }

  152. /*
  153.  * hlist end
  154.  */

    结果:
    




四,参考
1,linux内核源码



阅读(1266) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~