漫谈Linux内核哈希表(2)

13470阅读 3评论2015-05-06 wjlkoorey258
分类:LINUX

    对照前面介绍过的内核通知链、链表,本章我们将要介绍的哈希表的初始化和定义也是如出一辙的:

点击(此处)折叠或打开

  1. 定义并初始化一个名为name的哈希链表表头
  2. #define HLIST_HEAD(name) struct hlist_head name = { .first = NULL }

  3. 初始化一个已经定义好的哈希链表,其中ptr指向哈希表头的地址
  4. #define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)
   
   其中,HLIST_HEAD_INIT
一般这么用:

点击(此处)折叠或打开

  1. struct hlist_head myhlist;
  2. HLIST_HEAD_INIT(&myhlist);

    对于哈希表中的每一个hlist_node节点,通常情况下都要调用初始化函数INIT_HLIST_NODE()来初始化:

点击(此处)折叠或打开

  1. static inline void INIT_HLIST_NODE(struct hlist_node *h)
  2. {
  3.     h->next = NULL;
  4.     h->pprev = NULL;
  5. }

    一个给定的哈希节点,判断它是否已经被插入到某条哈希链表里hlist_unhashed()

点击(此处)折叠或打开

  1. static inline int hlist_unhashed(const struct hlist_node *h)
  2. {
  3.     return !h->pprev;
  4. }
    这里我们可以看到,hlist_node里的pprev完成了这个功能,即如果一个hlist_nodepprevNULL,则说明该节点目前并未加入任何哈希链表。

   
下面这个接口就没啥好说的,用于判断是一个给定哈希表是否为空(即不包含任何哈希节点)。注意,该接口入参为hlist_head类型而非hlist_node类型:

点击(此处)折叠或打开

  1. static inline int hlist_empty(const struct hlist_head *h)
  2. {
  3.     return !h->first;
  4. }
    
   剩下的其他接口,也都非常简单,这里不再一一赘述。下面我们看几个宏定义:

点击(此处)折叠或打开

  1. #define hlist_entry(ptr, type, member) container_of(ptr,type,member)
  2. 该宏和前面介绍过的list_entry()的实现、作用完全一样
  3. #define list_entry(ptr, type, member)  container_of(ptr,type,member)
    
   对照list的学习过程,可想而知,下面这几组结构,其作用也就不言而喻了:
哈希表 链表
hlist_for_each(pos, head)
list_for_each(pos, head)
hlist_for_each_safe(pos, n, head)
list_for_each_safe(pos, n, head)
hlist_for_each_entry(tpos, pos, head, member)
list_for_each_entry(pos, head, member)
hlist_for_each_entry_safe(tpos, pos, n, head, member)
list_for_each_entry_safe(pos, n, head, member)

    区别在于最后两个宏的入参上有些小区别。由于哈希链表,表头和表节点是不同的数据结构,所以才会有这个差异。还是对照着list_for_each_*的学习过程:

点击(此处)折叠或打开

  1. hlist_for_each_entry(tpos, pos, head, member)
    其中tpos,是hlist_node所属宿主结构体类型的指针,pos是hlist_node类型的指针,tpos和pos都充当的游标的作用。例如:

点击(此处)折叠或打开

  1. typedef struct student
  2. {
  3.     char m_name[MAX_STRING_LEN];
  4.     char m_sex;
  5.     int m_age;
  6.     struct list_head m_list; /*把我们的学生对象组织成双向链表,就靠该节点了*/
  7.     struct hlist_node m_hlist; /*把我们的学生对象组织成哈希链表,就靠该节点了*/
  8. }Student;

  9. HLIST_HEAD(myhlist);
  10. Student *st;
  11. struct hlist_node *i;
  12. hlist_for_each_entry(st, i&myhlist, m_hlist)
  13. {
  14.     //To do something here…
  15.     //通常情况,开发者在这里仅需要关注、使用st变量就可以,不需要关心i
  16. }
    
   同样地,在使用hlist_for_each_entry_safe(tpos, pos, n, head, member)时,tpos也是宿主结构体类型的一个指针变量,当游标使用,n是一个hlist_node类型的另一个指针,这个指针指向pos所在元素的下一个元素,它由hlist_for_each_entry_safe()本身进行维护,开发者不用修改它

点击(此处)折叠或打开

  1. HLIST_HEAD(myhlist);
  2. Student *st;
  3. struct hlist_node *i,*j;
  4. hlist_for_each_entry_safe(st, i, j, &myhlist, m_hlist)
  5. {
  6.     //To do something here…
  7.     //i和j都不需要开发者关注,仅使用st就可以了
  8. }
    
   另外,还有一组宏:

点击(此处)折叠或打开

  1. hlist_for_each_entry_continue(tpos, pos, member)    
  2. hlist_for_each_entry_from(tpos, pos, member)
    其参数tpospos意义和类型与前面介绍过的一致,这两个宏的作用分别是:
   
hlist_for_each_entry_continue():从pos节点开始(不包含pos),往后依次遍历所有节点;
   
hlist_for_each_entry_from()     pos节点开始(包含pos),依次往后遍历所有节点;
   
这一组宏是“不安全”的,意思是,在它们里面你只能执行查找遍历的任务、不能插入或者删除节点,因为它们脑门上没有那个“safe”的关键字。

   
最后,还是老生常谈,实际操练一把。把链表章节我们介绍过的学历管理系统拿来,添加一个需求:“按照男、女的分类原则,将所有学生进行分类”。很明显,这里我们就可以用到哈希链表了。怎么实现呢?其实非常简单,前面我们已经见过对Student结构体的改造了。最终的完整代码如下所示:

   头文件修改:

点击(此处)折叠或打开

  1. /*student.h*/

  2. #ifndef __STUDENT_H_
  3. #define __STUDENT_H_

  4. #include <linux/list.h>
  5. #define MAX_STRING_LEN 32
  6. #define MAX_HLIST_COUNT 2 //只有“男”、“女”两条哈希链表
  7. typedef struct student
  8. {
  9.         char m_name[MAX_STRING_LEN];
  10.         char m_sex;
  11.         int m_age;
  12.         struct list_head m_list; /*把我们的学生对象组织成双向链表,就靠该节点了*/
  13.         struct hlist_node m_hlist; /*把我们的学生对象组织成哈希链表,就靠该节点了*/
  14. }Student;
  15. #endif
   
   源文件修改:

点击(此处)折叠或打开

  1. #include <linux/module.h>

  2. #include <linux/kernel.h>
  3. #include <linux/init.h>

  4. #include "student.h"

  5. MODULE_LICENSE("Dual BSD/GPL");
  6. MODULE_AUTHOR("Koorey Wung");

  7. static int dbg_flg = 0;

  8. LIST_HEAD(g_student_list);
  9. // 其中g_stu_hlist[0]代表男生;g_stu_hlist[1]代表女生
  10. struct hlist_head g_stu_hlist[MAX_HLIST_COUNT];

  11. //初始化男、女学生的哈希链表
  12. static void init_hlists(void)
  13. {
  14.     int i = 0;
  15.     for(i=0;i< MAX_HLIST_COUNT;i++){
  16.         INIT_HLIST_HEAD(&g_stu_hlist[i]);
  17.     }
  18. }

  19. static int add_stu(char* name,char sex,int age)
  20. {
  21.     Student *stu,*cur_stu;

  22.     list_for_each_entry(cur_stu,&g_student_list,m_list){ //仅遍历是否有同名学生,所以用该接口
  23.         if(0 == strcmp(cur_stu->m_name,name))
  24.         {
  25.             printk("Error:the name confict!\n");
  26.             return -1;
  27.         }
  28.     }

  29.     stu = kmalloc(sizeof(Student), GFP_KERNEL);
  30.     if(!stu)
  31.     {
  32.         printk("kmalloc mem error!\n");
  33.         return -1;
  34.     }

  35.     memset(stu,0,sizeof(Student));
  36.     strncpy(stu->m_name,name,strlen(name));
  37.     stu->m_sex = sex;
  38.     stu->m_age = age;
  39.     INIT_LIST_HEAD(&stu->m_list);    //初始化宿主结构里的双向链表节点m_list
  40.     INIT_HLIST_NODE(&stu->m_hlist);  //初始化宿主结构里的哈希节点m_hlist

  41.     if(dbg_flg)
  42.         printk("(Add)name:[%s],\tsex:[%c],\tage:[%d]\n",stu->m_name,stu->m_sex,stu->m_age);


  43.     list_add_tail(&stu->m_list,&g_student_list); //将新学生插入到链表尾部,很简单吧

  44.     return 0;
  45. }
  46. EXPORT_SYMBOL(add_stu); //导出该函数,后面我们要在其他模块里调用,为了便于测试,下面其他几个接口类似

  47. static int del_stu(char *name)
  48. {
  49.         Student *cur,*next;
  50.         int ret = -1;
  51.         list_for_each_entry_safe(cur,next,&g_student_list,m_list){ //因为要删除链表的节点,所以必须有带有“safe”的宏接口
  52.                 if(0 == strcmp(name,cur->m_name))
  53.                 {
  54.                         list_del(&cur->m_list);
  55.                         printk("(Del)name:[%s],\tsex:[%c],\tage:[%d]\n",cur->m_name,\
  56.                                         cur->m_sex,cur->m_age);
  57.                         kfree(cur);
  58.                         cur = NULL;
  59.                         ret = 0;
  60.                         break;
  61.                 }
  62.         }
  63.         return ret;
  64. }
  65. EXPORT_SYMBOL(del_stu);

  66. static void dump_students(void)
  67. {
  68.         Student *stu;
  69.         int i = 1;
  70.         printk("===================Student List================\n");
  71.         list_for_each_entry(stu,&g_student_list,m_list){ //同样,也仅遍历链表而已
  72.                 printk("(%d)name:[%s],\tsex:[%c],\tage:[%d]\n",i++,stu->m_name,\
  73.                         stu->m_sex,stu->m_age);
  74.         }
  75.         printk("===============================================\n");
  76. }
  77. EXPORT_SYMBOL(dump_students);

  78. static void dump_hlist(int id)
  79. {
  80.         Student *stu;
  81.         struct hlist_node *i;
  82.         struct hlist_head *head;
  83.         int count = 1;

  84.         if(!(id>=0 && id< MAX_HLIST_COUNT)){
  85.                 printk("Invalid id[%d] !\n",id);
  86.                 return;
  87.         }
  88.         head = &g_stu_hlist[id];

  89.         printk("===================%s List===================\n",((id == 0)?"Boy":"Girl"));
  90.         //因为该接口只遍历哈希表,并不会插入、删除节点,所以用hlist_for_each_entry(),注意四个入参的类型、作用和意义
  91.         hlist_for_each_entry(stu, i, head,m_hlist){
  92.                 printk("(%d)name:[%s],\tsex:[%c],\tage:[%d]\n",count++,stu->m_name,\
  93.                         stu->m_sex,stu->m_age);
  94.         }
  95.         printk("==============================================\n");
  96. }
  97. EXPORT_SYMBOL(dump_hlist);

  98. //分别打印男女学生,各自哈希链表上的情况
  99. static void dump_hlists(void)
  100. {
  101.         dump_hlist(0);
  102.         dump_hlist(1);
  103. }
  104. EXPORT_SYMBOL(dump_hlists);


  105. //按照性别对学生进行分类
  106. static void classify_stu(void)
  107. {
  108.         Student *cur,*next;
  109.         int id = 0;

  110.         list_for_each_entry_safe(cur,next,&g_student_list,m_list){
  111.                 //将从cur从g_student_list链表上移下来,但并不会释放cur学生的内存空间,同时对其m_list成员重新初始化
  112.                 list_del_init(&cur->m_list);
  113.                 if('m' == cur->m_sex){
  114.                         id = 0;
  115.                 }
  116.                 else if('f' == cur->m_sex){
  117.                         id = 1;
  118.                 }
  119.                 else{
  120.                         printk("Get error!\n");
  121.                         return;
  122.                 }
  123.                 //根据id,以m_hlist将学生按性别组织成哈希表
  124.                 hlist_add_head(&(cur->m_hlist),&(g_stu_hlist[id]));
  125.         }
  126.         printk("Finished!\n");
  127. }
  128. EXPORT_SYMBOL(classify_stu);


  129. static void init_system(void)
  130. {
  131.     //初始化男、女学生哈希链表头
  132.     init_hlists();

  133.     /*系统启动初始化时,向链表g_student_list里添加6个学生*/
  134.     add_stu("Tom",'m',18);
  135.     add_stu("Jerry",'f',17);
  136.     add_stu("Alex",'m',18);
  137.     add_stu("Conory",'f',18);
  138.     add_stu("Frank",'m',17);
  139.     add_stu("Marry",'f',17);
  140. }

  141. /*释放所有哈希链表上的内存空间*/
  142. static void clean_up_hlist(void)
  143. {
  144.     int i;
  145.     Student *stu;
  146.     struct hlist_node *cur,*next;

  147.     for(i=0;i< MAX_HLIST_COUNT;i++){
  148.         printk("===================%s List================\n",((i == 0)?"Boy":"Girl"));
  149.         hlist_for_each_entry_safe(stu, cur, next, &(g_stu_hlist[i]), m_hlist){
  150.             hlist_del(&(stu->m_hlist));
  151.             printk("Destroy [%s]\n",stu->m_name);
  152.             kfree(stu);
  153.         }
  154.         printk("===========================================\n");
  155.     }
  156. }

  157. /*释放双向表上的内存空间*/
  158. static void clean_up_list(void)
  159. {
  160.         Student *stu,*next;
  161.         printk("===========Unclassified Student List===========\n");
  162.         list_for_each_entry_safe(stu,next,&g_student_list,m_list){
  163.                 list_del(&stu->m_list);
  164.                 printk("Destroy [%s]\n",stu->m_name);
  165.                 kfree(stu);
  166.         }
  167.         printk("===============================================\n");
  168. }

  169. /*因为没有数据库,所以当我们的模块退出时,需要释放内存。*/
  170. static void clean_up(void)
  171. {
  172.         clean_up_list();
  173.         clean_up_hlist();
  174. }

  175. /*模块初始化接口*/
  176. static int student_mgt_init(void)
  177. {
  178.         printk("Student Managment System,Initializing...\n");

  179.         init_system();
  180.         dbg_flg = 1; //从此以后,再调用add_stu()时,都会有有内核打印信息,详见实例训练
  181.         dump_students();

  182.         return 0;
  183. }

  184. static void student_mgt_exit(void)
  185. {
  186.         clean_up();
  187.         printk("System Terminated!\n");
  188. }

  189. module_init(student_mgt_init);
  190. module_exit(student_mgt_exit);

    验证结果如下:
   我们每调用此classify_stu()就会将目前自由双向链表g_student_list里的学生按照性别进行分类,男生存储到哈希链表g_stu_hlist[0]里,女生存储到哈希链表g_stu_hlist[1]里。而调用add_stu()则是向g_student_list链表里添加学生,以便为后面调用classify_stu()做准备:

    其实可以看到,哈希链表的用法也是蛮简单的。其实内核里诸如通知链、链表、哈希表等等这些基础数据结构,掌握了原理后使用起来都不难。
   未完,待续....
上一篇:漫谈Linux内核哈希表(1)
下一篇:将博客搬至CSDN

文章评论