实验报告
课程名称： TCP/IP协议栈分析与实现
实验项目名称：Linux内核通用哈希链表的使用 学生姓名：苟伟
专业：信息工程
学号：201005010710
同组学生姓名：
指导老师：刘飚
实验地点：6c601
实验日期：2013年3 月28日
一、实验目的和要求：
学习Linux内核的通用哈希链表的设计原理，熟练掌握Linux内核通用哈希链表的使用。
二、实验内容
1.掌握Linux通用哈希链表的创建
2.掌握通用哈希表增加元素、查找元素的方法。
三、实验要求
1.待创建的哈希表头数组为structhlist_headuser_hash[16]，要求对哈希表宿主元素的 name成员的值进行散列，并将散列值作为哈希表宿主元素的key。
2.作为哈希表元素的宿主节点类型定义如下：
structusermap{
structhlist_nodehlist;
unsignedcharname[8];
};
3.针对上述user_hash哈希表，要求向其中添加3个类型为structusermap的宿主元素， 并要求这3个宿主元素的name成员分别为\"smith\",\"john\",\"bob\"。
4.向哈希表user_hash中添加第4个宿主元素。若新宿主元素的name成员已经存在 （例如\"john\"），则提示已经存在该用户，否则向哈希表中添加该宿主元素。
四、实现原理
Linux的内核源文件list.h提供了哈希表各类操作接口及其实现。其中创建具有16
个key值的哈希表的方法如下：
structhlist_headuser_hash[16];
在上述user_hash数组的16个元素中存放的哈希表头元素定义如下：
structhlist_head{
structhlist_node*first;
};
哈希表节点元素定义如下：
structhlist_node{
structhlist_node*next,**pprev;
};
本实验对哈希表宿主元素节点的name值进行散列的算法如下：
unsignedintBKDRHash(unsignedchar*str)
{
unsignedintseed=131;
unsignedinthash=0;
while(*str){
hash=hash*seed+(*str++);
}
return(hash&0x7FFFFFFF); // 返回此*str所对应的哈希值
}
于是，本实验中对一个字符串name求最终哈希值hash的方法如下：
unsignedinthash=BKDRHash(name)&15
内核源文件list.h中定义了以下若干接口，用于对哈希表进行各类操作：
1) 在指定的哈希表头h所指向的链表头插入新节点
//@n:要添加的新哈希表节点
//@h:在此哈希表头节点后添加
hlist_add_head(structhlist_node*n,structhlist_head*h);
2) 根据当前哈希表节点指针ptr获得哈希表宿主节点指针
//*@ptr: structhlist_node类型的指针
//*@type:哈希表节点所在的宿主节点的类型
//*@member:嵌入宿主的哈希表节点的变量名
hlist_entry(ptr,type,member)
3) 遍历哈希表中某个key所对应的链表
//@tpos: 哈希表宿主节点指针
//@pos: 哈希表节点指针
//@head: 哈希表中某key所对应的链表的头指针
//@member:嵌在哈希表宿主节点中哈希表节点的变量名
hlist_for_each_entry(tpos,pos,head,member)
五、实现代码和运行结果
请打印本实验的程序代码和程序运行截图，并作为附件附在本实验报告后。
1 #include28 for(i=0;i
2 #include29hash=BKDRHash(name[i])&15;3 #include\"list.h\"30printf(\"name is %s ,and hash4 #include code is %d.\\n\",name[i],hash);
531strcpy(a[i].name,name[i]);
6 unsigned intBKDRHash(unsigned char32structhlist_head *ph;
*str){33ph=&user_hash[hash];
7unsigned int seed=131;34hlist_add_head(&(a[i].hlist),ph);8unsigned int hash=0;35
9while(*str){ p=hlist_entry(&(a[i].hlist),typeof(*p),hlist);10hash=hash*seed+(*str++);36printf(\"is%s\\n\",p->name);11}37}
12return (hash&0x7FFFFFFF);38structhlist_node *pp;
13}39char addname[8];
14 intmain(){40printf(\"printnameadd\\n\");15inti;41scanf(\"%s\",addname);
16structhlist_headuser_hash[16];42int frag=1;
17structusermap{ 43hash=BKDRHash(addname)&15;18structhlist_nodehlist;44
19unsigned char name[8]; hlist_for_each_entry(p,pp,&user_hash[hash], 20}a[100]; hlist){
21for(i=0;i
23INIT_HLIST_NODE(&a[i].hlist);46
24} if(strcmp(addname,p->name)==0){
25char47frag=0;
name[3][8]={\"smith\",\"jhon\",\"bob\"};48printf(\"%s26structusermap *p; yicunzai\\n\",addname);
27unsigned int hash;49}}
50if(frag)59
51{ hlist_for_each_entry(p,pp,&user_hash[i],hlist 52)
hash=BKDRHash(addname)&15;60printf(\" hash code %d all53is%s\\n\",i,p->name);
strcpy(a[3].name,addname);61hlist_for_each(pp,&user_hash[i])5462{
hlist_add_head(&(a[3].hlist),&user_hash[hash 63
]); p=hlist_entry(pp,typeof(*p),hlist);
5564
p=hlist_entry(&(a[3].hlist),typeof(*p),hlist); is%s\\n\",p->name);
5665}
printf(\"is%s\\n\",p->name);66}
57}67return 0;
58for(i=0;i
运行结果：
root@gouwei-virtual-machine://home/gouwei/shiyan# ./shiyan2
name is smith ,and hash code is 7.
imith
name is jhon ,and hash code is 1.
isjhon
name is bob ,and hash code is 1.
isbob
printnameadd
gouwei
isgouwei
hash code 1 allisbob
hash code 1 allisjhon
***isbob
***isjhon
hash code 2 allisgouwei
***isgouwei
hash code 7 allimith
***imith
root@gouwei-virtual-machine://home/gouwei/shiyan# printf(\" ***
