漫谈Linux内核哈希表(2)

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

点击(此处)折叠或打开

1. 定义并初始化一个名为name的哈希链表表头
   
2. #define HLIST_HEAD(name) struct hlist_head name = { .first = NULL }
   
3. 
   
4. 初始化一个已经定义好的哈希链表，其中ptr指向哈希表头的地址
   
5. #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_node的pprev为NULL，则说明该节点目前并未加入任何哈希链表。

   下面这个接口就没啥好说的，用于判断是一个给定哈希表是否为空(即不包含任何哈希节点)。注意，该接口入参为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. 
   
10. HLIST_HEAD(myhlist);
    
11. Student *st;
    
12. struct hlist_node *i;
    
13. hlist_for_each_entry(st, i, &myhlist, m_hlist)
    
14. {
    
15.     //To do something here…
    
16.     //通常情况，开发者在这里仅需要关注、使用st变量就可以，不需要关心i
    
17. }

    
   同样地，在使用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)

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

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

   头文件修改：

点击(此处)折叠或打开

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

   
   源文件修改：

点击(此处)折叠或打开

1. #include <linux/module.h>
   
2. 
   
3. #include <linux/kernel.h>
   
4. #include <linux/init.h>
   
5. 
   
6. #include "student.h"
   
7. 
   
8. MODULE_LICENSE("Dual BSD/GPL");
   
9. MODULE_AUTHOR("Koorey Wung");
   
10. 
    
11. static int dbg_flg = 0;
    
12. 
    
13. LIST_HEAD(g_student_list);
    
14. // 其中g_stu_hlist[0]代表男生；g_stu_hlist[1]代表女生
    
15. struct hlist_head g_stu_hlist[MAX_HLIST_COUNT];
    
16. 
    
17. //初始化男、女学生的哈希链表
18. static void init_hlists(void)
    
19. {
    
20.     int i = 0;
    
21.     for(i=0;i< MAX_HLIST_COUNT;i++){
    
22.         INIT_HLIST_HEAD(&g_stu_hlist[i]);
    
23.     }
    
24. }
    
25. 
    
26. static int add_stu(char* name,char sex,int age)
    
27. {
    
28.     Student *stu,*cur_stu;
    
29. 
    
30.     list_for_each_entry(cur_stu,&g_student_list,m_list){ //仅遍历是否有同名学生，所以用该接口
    
31.         if(0 == strcmp(cur_stu->m_name,name))
    
32.         {
    
33.             printk("Error:the name confict!\n");
    
34.             return -1;
    
35.         }
    
36.     }
    
37. 
    
38.     stu = kmalloc(sizeof(Student), GFP_KERNEL);
    
39.     if(!stu)
    
40.     {
    
41.         printk("kmalloc mem error!\n");
    
42.         return -1;
    
43.     }
    
44. 
    
45.     memset(stu,0,sizeof(Student));
    
46.     strncpy(stu->m_name,name,strlen(name));
    
47.     stu->m_sex = sex;
    
48.     stu->m_age = age;
    
49.     INIT_LIST_HEAD(&stu->m_list);    //初始化宿主结构里的双向链表节点m_list
    
50.     INIT_HLIST_NODE(&stu->m_hlist);  //初始化宿主结构里的哈希节点m_hlist
    
51. 
    
52.     if(dbg_flg)
    
53.         printk("(Add)name:[%s],\tsex:[%c],\tage:[%d]\n",stu->m_name,stu->m_sex,stu->m_age);
    
54. 
    
55. 
    
56.     list_add_tail(&stu->m_list,&g_student_list); //将新学生插入到链表尾部，很简单吧
    
57. 
    
58.     return 0;
    
59. }
    
60. EXPORT_SYMBOL(add_stu); //导出该函数，后面我们要在其他模块里调用，为了便于测试，下面其他几个接口类似
    
61. 
    
62. static int del_stu(char *name)
    
63. {
    
64.         Student *cur,*next;
    
65.         int ret = -1;
    
66.         list_for_each_entry_safe(cur,next,&g_student_list,m_list){ //因为要删除链表的节点，所以必须有带有“safe”的宏接口
    
67.                 if(0 == strcmp(name,cur->m_name))
    
68.                 {
    
69.                         list_del(&cur->m_list);
    
70.                         printk("(Del)name:[%s],\tsex:[%c],\tage:[%d]\n",cur->m_name,\
    
71.                                         cur->m_sex,cur->m_age);
    
72.                         kfree(cur);
    
73.                         cur = NULL;
    
74.                         ret = 0;
    
75.                         break;
    
76.                 }
    
77.         }
    
78.         return ret;
    
79. }
    
80. EXPORT_SYMBOL(del_stu);
    
81. 
    
82. static void dump_students(void)
    
83. {
    
84.         Student *stu;
    
85.         int i = 1;
    
86.         printk("===================Student List================\n");
    
87.         list_for_each_entry(stu,&g_student_list,m_list){ //同样，也仅遍历链表而已
    
88.                 printk("(%d)name:[%s],\tsex:[%c],\tage:[%d]\n",i++,stu->m_name,\
    
89.                         stu->m_sex,stu->m_age);
    
90.         }
    
91.         printk("===============================================\n");
    
92. }
    
93. EXPORT_SYMBOL(dump_students);
    
94. 
    
95. static void dump_hlist(int id)
    
96. {
    
97.         Student *stu;
    
98.         struct hlist_node *i;
    
99.         struct hlist_head *head;
    
100.         int count = 1;
     
101. 
     
102.         if(!(id>=0 && id< MAX_HLIST_COUNT)){
     
103.                 printk("Invalid id[%d] !\n",id);
     
104.                 return;
     
105.         }
     
106.         head = &g_stu_hlist[id];
     
107. 
     
108.         printk("===================%s List===================\n",((id == 0)?"Boy":"Girl"));
     
109.         //因为该接口只遍历哈希表，并不会插入、删除节点，所以用hlist_for_each_entry()，注意四个入参的类型、作用和意义
     
110.         hlist_for_each_entry(stu, i, head,m_hlist){
111.                 printk("(%d)name:[%s],\tsex:[%c],\tage:[%d]\n",count++,stu->m_name,\
     
112.                         stu->m_sex,stu->m_age);
     
113.         }
     
114.         printk("==============================================\n");
     
115. }
     
116. EXPORT_SYMBOL(dump_hlist);
     
117. 
     
118. //分别打印男女学生，各自哈希链表上的情况
119. static void dump_hlists(void)
     
120. {
     
121.         dump_hlist(0);
     
122.         dump_hlist(1);
     
123. }
     
124. EXPORT_SYMBOL(dump_hlists);
     
125. 
     
126. 
     
127. //按照性别对学生进行分类
     
128. static void classify_stu(void)
     
129. {
     
130.         Student *cur,*next;
     
131.         int id = 0;
     
132. 
     
133.         list_for_each_entry_safe(cur,next,&g_student_list,m_list){
     
134.                 //将从cur从g_student_list链表上移下来，但并不会释放cur学生的内存空间，同时对其m_list成员重新初始化
     
135.                 list_del_init(&cur->m_list);
     
136.                 if('m' == cur->m_sex){
     
137.                         id = 0;
     
138.                 }
     
139.                 else if('f' == cur->m_sex){
     
140.                         id = 1;
     
141.                 }
     
142.                 else{
     
143.                         printk("Get error!\n");
     
144.                         return;
     
145.                 }
     
146.                 //根据id，以m_hlist将学生按性别组织成哈希表
     
147.                 hlist_add_head(&(cur->m_hlist),&(g_stu_hlist[id]));
     
148.         }
     
149.         printk("Finished!\n");
     
150. }
     
151. EXPORT_SYMBOL(classify_stu);
     
152. 
     
153. 
     
154. static void init_system(void)
     
155. {
     
156.     //初始化男、女学生哈希链表头
     
157.     init_hlists();
     
158. 
     
159.     /*系统启动初始化时，向链表g_student_list里添加6个学生*/
     
160.     add_stu("Tom",'m',18);
     
161.     add_stu("Jerry",'f',17);
     
162.     add_stu("Alex",'m',18);
     
163.     add_stu("Conory",'f',18);
     
164.     add_stu("Frank",'m',17);
     
165.     add_stu("Marry",'f',17);
     
166. }
     
167. 
     
168. /*释放所有哈希链表上的内存空间*/
     
169. static void clean_up_hlist(void)
     
170. {
     
171.     int i;
     
172.     Student *stu;
     
173.     struct hlist_node *cur,*next;
     
174. 
     
175.     for(i=0;i< MAX_HLIST_COUNT;i++){
     
176.         printk("===================%s List================\n",((i == 0)?"Boy":"Girl"));
     
177.         hlist_for_each_entry_safe(stu, cur, next, &(g_stu_hlist[i]), m_hlist){
     
178.             hlist_del(&(stu->m_hlist));
     
179.             printk("Destroy [%s]\n",stu->m_name);
     
180.             kfree(stu);
     
181.         }
     
182.         printk("===========================================\n");
     
183.     }
     
184. }
     
185. 
     
186. /*释放双向表上的内存空间*/
     
187. static void clean_up_list(void)
     
188. {
     
189.         Student *stu,*next;
     
190.         printk("===========Unclassified Student List===========\n");
     
191.         list_for_each_entry_safe(stu,next,&g_student_list,m_list){
     
192.                 list_del(&stu->m_list);
     
193.                 printk("Destroy [%s]\n",stu->m_name);
     
194.                 kfree(stu);
     
195.         }
     
196.         printk("===============================================\n");
     
197. }
     
198. 
     
199. /*因为没有数据库，所以当我们的模块退出时，需要释放内存。*/
     
200. static void clean_up(void)
     
201. {
     
202.         clean_up_list();
     
203.         clean_up_hlist();
     
204. }
     
205. 
     
206. /*模块初始化接口*/
     
207. static int student_mgt_init(void)
     
208. {
     
209.         printk("Student Managment System,Initializing...\n");
     
210. 
     
211.         init_system();
     
212.         dbg_flg = 1; //从此以后，再调用add_stu()时，都会有有内核打印信息，详见实例训练
     
213.         dump_students();
     
214. 
     
215.         return 0;
     
216. }
     
217. 
     
218. static void student_mgt_exit(void)
     
219. {
     
220.         clean_up();
     
221.         printk("System Terminated!\n");
     
222. }
     
223. 
     
224. module_init(student_mgt_init);
     
225. module_exit(student_mgt_exit);
226. 
     

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

    其实可以看到，哈希链表的用法也是蛮简单的。其实内核里诸如通知链、链表、哈希表等等这些基础数据结构，掌握了原理后使用起来都不难。
   未完，待续....