對照前面介紹過的核心通知鍊、連結清單，本章我們将要介紹的哈希表的初始化和定義也是如出一轍的：
點選(此處)折疊或打開
定義并初始化一個名為name的哈希連結清單表頭
#define HLIST_HEAD(name) struct hlist_head name = { .first = NULL }
初始化一個已經定義好的哈希連結清單，其中ptr指向哈希表頭的位址
#define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)
其中，HLIST_HEAD_INIT一般這麼用：
struct hlist_head myhlist;
HLIST_HEAD_INIT(&myhlist);
對于哈希表中的每一個hlist_node節點，通常情況下都要調用初始化函數INIT_HLIST_NODE()來初始化：
static inline void INIT_HLIST_NODE(struct hlist_node *h)
{
h->next = NULL;
h->pprev = NULL;
}
一個給定的哈希節點，判斷它是否已經被插入到某條哈希連結清單裡hlist_unhashed()：
static inline int hlist_unhashed(const struct hlist_node *h)
return !h->pprev;
這裡我們可以看到，hlist_node裡的pprev完成了這個功能，即如果一個hlist_node的pprev為NULL，則說明該節點目前并未加入任何哈希連結清單。
下面這個接口就沒啥好說的，用于判斷是一個給定哈希表是否為空(即不包含任何哈希節點)。注意，該接口入參為hlist_head類型而非hlist_node類型：
static inline int hlist_empty(const struct hlist_head *h)
return !h->first;
剩下的其他接口，也都非常簡單，這裡不再一一贅述。下面我們看幾個宏定義：
#define hlist_entry(ptr, type, member) container_of(ptr,type,member)
該宏和前面介紹過的list_entry()的實作、作用完全一樣
#define list_entry(ptr, type, member) container_of(ptr,type,member)
對照list的學習過程，可想而知，下面這幾組結構，其作用也就不言而喻了：
哈希表
連結清單
hlist_for_each(pos,
head)
list_for_each(pos,
hlist_for_each_safe(pos,
n, head)
list_for_each_safe(pos,
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_*的學習過程：
hlist_for_each_entry(tpos, pos, head, member)
其中tpos，是hlist_node所屬宿主結構體類型的指針，pos是hlist_node類型的指針，tpos和pos都充當的遊标的作用。例如：
typedef struct student
char m_name[MAX_STRING_LEN];
char m_sex;
int m_age;
struct list_head m_list; /*把我們的學生對象組織成雙向連結清單，就靠該節點了*/
struct hlist_node m_hlist; /*把我們的學生對象組織成哈希連結清單，就靠該節點了*/
}Student;
HLIST_HEAD(myhlist);
Student *st;
struct hlist_node *i;
hlist_for_each_entry(st, i, &myhlist, m_hlist)
//To do something here…
//通常情況，開發者在這裡僅需要關注、使用st變量就可以，不需要關心i
同樣地，在使用hlist_for_each_entry_safe(tpos, pos, n, head,
member)時，tpos也是宿主結構體類型的一個指針變量，當遊标使用，n是一個hlist_node類型的另一個指針，這個指針指向pos所在元素的下一個元素，它由hlist_for_each_entry_safe()本身進行維護，開發者不用修改它：
struct hlist_node *i,*j;
hlist_for_each_entry_safe(st, i, j, &myhlist, m_hlist)
//i和j都不需要開發者關注，僅使用st就可以了
另外，還有一組宏：
hlist_for_each_entry_continue(tpos, pos, member)
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結構體的改造了。最終的完整代碼如下所示：
頭檔案修改：
/*student.h*/
#ifndef __STUDENT_H_
#define __STUDENT_H_
#include linux/list.h>
#define MAX_STRING_LEN 32
#define MAX_HLIST_COUNT 2 //隻有“男”、“女”兩條哈希連結清單
char m_name[MAX_STRING_LEN];
char m_sex;
int m_age;
struct list_head m_list; /*把我們的學生對象組織成雙向連結清單，就靠該節點了*/
struct hlist_node m_hlist; /*把我們的學生對象組織成哈希連結清單，就靠該節點了*/
#endif
源檔案修改：
#include linux/module.h>
#include linux/kernel.h>
#include linux/init.h>
#include "student.h"
MODULE_LICENSE("Dual BSD/GPL");
MODULE_AUTHOR("Koorey Wung");
static int dbg_flg = 0;
LIST_HEAD(g_student_list);
// 其中g_stu_hlist[0]代表男生；g_stu_hlist[1]代表女生
struct hlist_head g_stu_hlist[MAX_HLIST_COUNT];
//初始化男、女學生的哈希連結清單
static void init_hlists(void)
int i = 0;
for(i=0;i MAX_HLIST_COUNT;i++){
INIT_HLIST_HEAD(&g_stu_hlist[i]);
}
static int add_stu(char* name,char sex,int age)
Student *stu,*cur_stu;
list_for_each_entry(cur_stu,&g_student_list,m_list){ //僅周遊是否有同名學生，是以用該接口
if(0 == strcmp(cur_stu->m_name,name))
{
printk("Error:the name confict!\n");
return -1;
}
stu = kmalloc(sizeof(Student), GFP_KERNEL);
if(!stu)
{
printk("kmalloc mem error!\n");
return -1;
memset(stu,0,sizeof(Student));
strncpy(stu->m_name,name,strlen(name));
stu->m_sex = sex;
stu->m_age = age;
INIT_LIST_HEAD(&stu->m_list); //初始化宿主結構裡的雙向連結清單節點m_list
INIT_HLIST_NODE(&stu->m_hlist); //初始化宿主結構裡的哈希節點m_hlist
if(dbg_flg)
printk("(Add)name:[%s],\tsex:[%c],\tage:[%d]\n",stu->m_name,stu->m_sex,stu->m_age);
list_add_tail(&stu->m_list,&g_student_list); //将新學生插入到連結清單尾部，很簡單吧
return 0;
EXPORT_SYMBOL(add_stu); //導出該函數，後面我們要在其他子產品裡調用，為了便于測試，下面其他幾個接口類似
static int del_stu(char *name)
Student *cur,*next;
int ret = -1;
list_for_each_entry_safe(cur,next,&g_student_list,m_list){ //因為要删除連結清單的節點，是以必須有帶有“safe”的宏接口
if(0 == strcmp(name,cur->m_name))
{
list_del(&cur->m_list);
printk("(Del)name:[%s],\tsex:[%c],\tage:[%d]\n",cur->m_name,\
cur->m_sex,cur->m_age);
kfree(cur);
cur = NULL;
ret = 0;
break;
}
}
return ret;
EXPORT_SYMBOL(del_stu);
static void dump_students(void)
Student *stu;
int i = 1;
printk("===================Student List================\n");
list_for_each_entry(stu,&g_student_list,m_list){ //同樣，也僅周遊連結清單而已
printk("(%d)name:[%s],\tsex:[%c],\tage:[%d]\n",i++,stu->m_name,\
stu->m_sex,stu->m_age);
printk("===============================================\n");
EXPORT_SYMBOL(dump_students);
static void dump_hlist(int id)
struct hlist_node *i;
struct hlist_head *head;
int count = 1;
if(!(id>=0 && id MAX_HLIST_COUNT)){
printk("Invalid id[%d] !\n",id);
return;
head = &g_stu_hlist[id];
printk("===================%s List===================\n",((id == 0)?"Boy":"Girl"));
//因為該接口隻周遊哈希表，并不會插入、删除節點，是以用hlist_for_each_entry()，注意四個入參的類型、作用和意義
hlist_for_each_entry(stu, i, head,m_hlist){
printk("(%d)name:[%s],\tsex:[%c],\tage:[%d]\n",count++,stu->m_name,\
printk("==============================================\n");
EXPORT_SYMBOL(dump_hlist);
//分别列印男女學生，各自哈希連結清單上的情況
static void dump_hlists(void)
dump_hlist(0);
dump_hlist(1);
EXPORT_SYMBOL(dump_hlists);
//按照性别對學生進行分類
static void classify_stu(void)
int id = 0;
list_for_each_entry_safe(cur,next,&g_student_list,m_list){
//将從cur從g_student_list連結清單上移下來，但并不會釋放cur學生的記憶體空間，同時對其m_list成員重新初始化
list_del_init(&cur->m_list);
if('m' == cur->m_sex){
id = 0;
else if('f' == cur->m_sex){
id = 1;
else{
printk("Get error!\n");
return;
//根據id，以m_hlist将學生按性别組織成哈希表
hlist_add_head(&(cur->m_hlist),&(g_stu_hlist[id]));
printk("Finished!\n");
EXPORT_SYMBOL(classify_stu);
static void init_system(void)
//初始化男、女學生哈希連結清單頭
init_hlists();
/*系統啟動初始化時，向連結清單g_student_list裡添加6個學生*/
add_stu("Tom",'m',18);
add_stu("Jerry",'f',17);
add_stu("Alex",'m',18);
add_stu("Conory",'f',18);
add_stu("Frank",'m',17);
add_stu("Marry",'f',17);
/*釋放所有哈希連結清單上的記憶體空間*/
static void clean_up_hlist(void)
int i;
Student *stu;
struct hlist_node *cur,*next;
for(i=0;i MAX_HLIST_COUNT;i++){
printk("===================%s List================\n",((i == 0)?"Boy":"Girl"));
hlist_for_each_entry_safe(stu, cur, next, &(g_stu_hlist[i]), m_hlist){
hlist_del(&(stu->m_hlist));
printk("Destroy [%s]\n",stu->m_name);
kfree(stu);
printk("===========================================\n");
}
/*釋放雙向表上的記憶體空間*/
static void clean_up_list(void)
Student *stu,*next;
printk("===========Unclassified Student List===========\n");
list_for_each_entry_safe(stu,next,&g_student_list,m_list){
list_del(&stu->m_list);
printk("Destroy [%s]\n",stu->m_name);
kfree(stu);
/*因為沒有資料庫，是以當我們的子產品退出時，需要釋放記憶體。*/
static void clean_up(void)
clean_up_list();
clean_up_hlist();
/*子產品初始化接口*/
static int student_mgt_init(void)
printk("Student Managment System,Initializing...\n");
init_system();
dbg_flg = 1; //從此以後，再調用add_stu()時，都會有有核心列印資訊，詳見執行個體訓練
dump_students();
return 0;
static void student_mgt_exit(void)
clean_up();
printk("System Terminated!\n");
module_init(student_mgt_init);
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-svn解除安裝與安裝[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)