文件系统Hash.docx
《文件系统Hash.docx》由会员分享，可在线阅读，更多相关《文件系统Hash.docx（16页珍藏版）》请在冰点文库上搜索。
文件系统Hash
文件系统——Hash
一、实验目的
1、理解linux文件系统的内部技术
2、掌握linux与文件有关的系统调用命令，并在此基础上建立面向随机检索的hash结构文件。
二、实验内容与设计思想
实验内容：
1、参考教程中Hash文件构造算法，设计一组Hash文件函数，包括Hash文件创建、打开、关闭、读、写等。
2、编写测试程序，通过记录保存、查找、删除等操作，检查上述Hash文件是否实现相关功能。
三、实验使用环境
LinuxRedhat4
四、实验结果
实验代码：
HashFile.h
#include
#defineCOLLISIONFACTOR0.5//Hash函数冲突因子
structHashFileHeader
{
intsig;//Hash文件印鉴
intreclen;//记录长度
inttotal_rec_num;//总记录数
intcurrent_rec_num;//当前记录数
};
structCFTag
{
charcollision;//冲突计数
charfree;//空闲标志
};
//函数声明
inthashfile_creat（constchar*filename,mode_tmode,intreclen,intrecnum）;
inthashfile_open（constchar*filename,intflags,mode_tmode）;
inthashfile_close（intfd）;
inthashfile_read（intfd,intkeyoffset,intkeylen,void*buf）;
inthashfile_write（intfd,intkeyoffset,intkeylen,void*buf）;
inthashfile_delrec（intfd,intkeyoffset,intkeylen,void*buf）;
inthashfile_findrec（intfd,intkeyoffset,intkeylen,void*buf）;
inthashfile_saverec（intfd,intkeyoffset,intkeylen,void*buf）;
inthash（intkeyoffset,intkeylen,void*buf,intrecnum）;
intcheckHashFileFull（intfd）;
intreadHashFileHeader（intfd,structHashFileHeader*hfh）;
HashFile.c
#include
#include
#include
#include
#include
#include"HashFile.h"
inthashfile_creat（constchar*filename,mode_tmode,intreclen,inttotal_rec_num）
{
structHashFileHeaderhfh;
intfd;
intrtn;
char*buf;
inti=0;
hfh.sig=31415926;
hfh.reclen=reclen;
hfh.total_rec_num=total_rec_num;
hfh.current_rec_num=0;
//fd=open（filename,mode）;
fd=creat（filename,mode）;
if（fd!
=-1）
{
rtn=write（fd,&hfh,sizeof（structHashFileHeader））;
//lseek（fd,sizeof（structHashFileHeader）,SEEK_SET）;
if（rtn!
=-1）
{
buf=（char*）malloc（（reclen+sizeof（structCFTag））*total_rec_num）;
memset（buf,0,（reclen+sizeof（structCFTag））*total_rec_num）;
rtn=write（fd,buf,（reclen+sizeof（structCFTag））*total_rec_num）;
free（buf）;
}
close（fd）;
returnrtn;
}
else
{
close（fd）;
return-1;
}
}
inthashfile_open（constchar*filename,intflags,mode_tmode）
{
intfd=open（filename,flags,mode）;
structHashFileHeaderhfh;
if（read（fd,&hfh,sizeof（structHashFileHeader））!
=-1）
{
lseek（fd,0,SEEK_SET）;
if（hfh.sig==31415926）
returnfd;
else
return-1;
}
else
return-1;
}
inthashfile_close（intfd）
{
returnclose（fd）;
}
inthashfile_read（intfd,intkeyoffset,intkeylen,void*buf）
{
structHashFileHeaderhfh;
readHashFileHeader（fd,&hfh）;
intoffset=hashfile_findrec（fd,keyoffset,keylen,buf）;
if（offset!
=-1）
{
lseek（fd,offset+sizeof（structCFTag）,SEEK_SET）;
returnread（fd,buf,hfh.reclen）;
}
else
{
return-1;
}
}
inthashfile_write（intfd,intkeyoffset,intkeylen,void*buf）
{
returnhashfile_saverec（fd,keyoffset,keylen,buf）;
//return-1;
}
inthashfile_delrec（intfd,intkeyoffset,intkeylen,void*buf）
{
intoffset;
offset=hashfile_findrec（fd,keyoffset,keylen,buf）;
if（offset!
=-1）
{
structCFTagtag;
read（fd,&tag,sizeof（structCFTag））;
tag.free=0;//置空闲标志
lseek（fd,offset,SEEK_SET）;
write（fd,&tag,sizeof（structCFTag））;
structHashFileHeaderhfh;
readHashFileHeader（fd,&hfh）;
intaddr=hash（keyoffset,keylen,buf,hfh.total_rec_num）;
offset=sizeof（structHashFileHeader）+addr*（hfh.reclen+sizeof（structCFTag））;
if（lseek（fd,offset,SEEK_SET）==-1）
return-1;
read（fd,&tag,sizeof（structCFTag））;
tag.collision--;//冲突记数减1
lseek（fd,offset,SEEK_SET）;//
write（fd,&tag,sizeof（structCFTag））;
hfh.current_rec_num--;//当前记录数减1
lseek（fd,0,SEEK_SET）;
write（fd,&hfh,sizeof（structHashFileHeader））;
}
else
{
return-1;
}
}
inthashfile_findrec（intfd,intkeyoffset,intkeylen,void*buf）
{
structHashFileHeaderhfh;
readHashFileHeader（fd,&hfh）;
intaddr=hash（keyoffset,keylen,buf,hfh.total_rec_num）;
intoffset=sizeof（structHashFileHeader）+addr*（hfh.reclen+sizeof（structCFTag））;
if（lseek（fd,offset,SEEK_SET）==-1）
return-1;
structCFTagtag;
read（fd,&tag,sizeof（structCFTag））;
charcount=tag.collision;
if（count==0）
return-1;//不存在
recfree:
if（tag.free==0）
{
offset+=hfh.reclen+sizeof（structCFTag）;
if（lseek（fd,offset,SEEK_SET）==-1）
return-1;
read（fd,&tag,sizeof（structCFTag））;
gotorecfree;
}
else
{
char*p=（char*）malloc（hfh.reclen*sizeof（char））;
read（fd,p,hfh.reclen）;
//printf（"Recordis{%d,%s}\n",（（structjtRecord*）p）->key,（（structjtRecord*）p）->other）;
char*p1,*p2;
p1=（char*）buf+keyoffset;
p2=p+keyoffset;
intj=0;
while（（*p1==*p2）&&（j{
p1++;
p2++;
j++;
}
if（j==keylen）
{
free（p）;
p=NULL;
return（offset）;//找到,返回偏移值
}
else
{
if（addr==hash（keyoffset,keylen,p,hfh.total_rec_num））
{
count--;//hash值相等而key值不等
if（count==0）
{
free（p）;
p=NULL;
return-1;//不存在
}
}
free（p）;
p=NULL;
offset+=hfh.reclen+sizeof（structCFTag）;
if（lseek（fd,offset,SEEK_SET）==-1）
return-1;
read（fd,&tag,sizeof（structCFTag））;
gotorecfree;
}
}
}
inthashfile_saverec（intfd,intkeyoffset,intkeylen,void*buf）
{
if（checkHashFileFull（fd））
{
return-1;
}
structHashFileHeaderhfh;
readHashFileHeader（fd,&hfh）;
intaddr=hash（keyoffset,keylen,buf,hfh.total_rec_num）;
intoffset=sizeof（structHashFileHeader）+addr*（hfh.reclen+sizeof（structCFTag））;
if（lseek（fd,offset,SEEK_SET）==-1）
return-1;
structCFTagtag;
read（fd,&tag,sizeof（structCFTag））;
tag.collision++;
lseek（fd,sizeof（structCFTag）*（-1）,SEEK_CUR）;
write（fd,&tag,sizeof（structCFTag））;
while（tag.free!
=0）//冲突，顺序探查
{
offset+=hfh.reclen+sizeof（structCFTag）;
if（offset>=lseek（fd,0,SEEK_END））
offset=sizeof（structHashFileHeader）;//reachatend,thenrewind
if（lseek（fd,offset,SEEK_SET）==-1）
return-1;
read（fd,&tag,sizeof（structCFTag））;
}
tag.free=1;
lseek（fd,sizeof（structCFTag）*（-1）,SEEK_CUR）;
write（fd,&tag,sizeof（structCFTag））;
write（fd,buf,hfh.reclen）;
hfh.current_rec_num++;//当前记录数加1
lseek（fd,0,SEEK_SET）;
returnwrite（fd,&hfh,sizeof（structHashFileHeader））;//存入记录
}
inthash（intkeyoffset,intkeylen,void*buf,inttotal_rec_num）
{
inti=0;
char*p=（char*）buf+keyoffset;
intaddr=0;
for（i=0;i{
addr+=（int）（*p）;
p++;
}
returnaddr%（int）（total_rec_num*COLLISIONFACTOR）;
}
intreadHashFileHeader（intfd,structHashFileHeader*hfh）
{
lseek（fd,0,SEEK_SET）;
returnread（fd,hfh,sizeof（structHashFileHeader））;
}
intcheckHashFileFull（intfd）
{
structHashFileHeaderhfh;
readHashFileHeader（fd,&hfh）;
if（hfh.current_rec_numreturn0;
else
return1;
}
jtRecord.h
#defineRECORDLEN32
structjtRecord
{
intkey;
charother[RECORDLEN-sizeof（int）];
};
#ifdefHAVE_CONFIG_H
#include
#endif
jtRecord.c
#ifdefHAVE_CONFIG_H
#include
#endif
#include
#include
#include
#include
#include
#include
#include
#include"HashFile.h"
#include"jtRecord.h"
#defineKEYOFFSET0
#defineKEYLENsizeof（int）
#defineFILENAME"jing.hash"
voidshowHashFile（）;
intmain（intargc,char*argv[]）
{
structjtRecordrec[6]=
{
{1,"jing"},{2,"wang"},{3,"li"},{4,"zhang"},{5,"qing"},{6,"yuan"}
};
intj=0;
for（j=0;j<6;j++）
{
printf（"<%d,%d>\t",rec[j].key,hash（KEYOFFSET,KEYLEN,&rec[j],6））;
}
intfd=hashfile_creat（FILENAME,O_RDWR|O_CREAT,RECORDLEN,6）;
inti=0;
printf（"\nOpenansSaveRecord...\n"）;
fd=hashfile_open（FILENAME,O_RDWR,0）;
for（i=0;i<6;i++）
{
hashfile_saverec（fd,KEYOFFSET,KEYLEN,&rec[i]）;
}
hashfile_close（fd）;
showHashFile（）;
//DemofindRec
printf（"\nFindRecord..."）;
fd=hashfile_open（FILENAME,O_RDWR,0）;
intoffset=hashfile_findrec（fd,KEYOFFSET,KEYLEN,&rec[4]）;
printf（"\noffsetis%d\n",offset）;
hashfile_close（fd）;
structjtRecordjt;
structCFTagtag;
fd=open（FILENAME,O_RDWR）;
lseek（fd,offset,SEEK_SET）;
read（fd,&tag,sizeof（structCFTag））;
printf（"Tagis<%d,%d>\t",tag.collision,tag.free）;
read（fd,&jt,sizeof（structjtRecord））;
printf（"Recordis{%d,%s}\n",jt.key,jt.other）;
//DemoDeleteRec
printf（"\nDeleteRecord..."）;
fd=hashfile_open（FILENAME,O_RDWR,0）;
hashfile_delrec（fd,KEYOFFSET,KEYLEN,&rec[2]）;
hashfile_close（fd）;
showHashFile（）;
//DemoRead
fd=hashfile_open（FILENAME,O_RDWR,0）;
charbuf[32];
memcpy（buf,&rec[1],KEYLEN）;
hashfile_read（fd,KEYOFFSET,KEYLEN,buf）;
printf（"\nReadRecordis{%d,%s}\n",（（structjtRecord*）buf）->key,（（structjtRecord*）buf）->other）;
hashfile_close（fd）;
//DemoWrite
printf（"\nWriteRecord..."）;
fd=hashfile_open（FILENAME,O_RDWR,0）;
hashfile_write（fd,KEYOFFSET,KEYLEN,&rec[3]）;
hashfile_close（fd）;
showHashFile（）;
return0;
}
voidshowHashFile（）
{
intfd;
printf（"\n"）;
fd=open（FILENAME,O_RDWR）;
lseek（fd,sizeof（structHashFileHeader）,SEEK_SET）;
structjtRecordjt;
structCFTagtag;
while
（1）
{
if（read（fd,&tag,sizeof（structCFTag））<=0）
break;
printf（"Tagis<%d,%d>\t",tag.collision,tag.free）;
if（read（fd,&jt,sizeof（structjtRecord））<=0）
break;
printf（"Recordis{%d,%s}\n",jt.key,jt.other）;
}
close（fd）;
}
运行结果：
五、实验小结
通过这次实验，在同学的帮助下学会了如何同时编译多个文件，即在-gcc–o后面同时添加2个文件名便可同时编译成功2个文件了。
六、附录
《网络编程技术与应用》
升级会员 