實(shí)驗(yàn)四文件系統(tǒng)

1、實(shí)驗(yàn)四,文件系統(tǒng),Hash,結(jié)構(gòu),文件,?,?,?,?,?,?,?,實(shí)驗(yàn)?zāi)康?實(shí)驗(yàn)內(nèi)容,實(shí)驗(yàn)準(zhǔn)備,實(shí)驗(yàn)設(shè)計(jì),參考代碼,實(shí)驗(yàn)結(jié)果,思考題,實(shí)驗(yàn)?zāi)康??,?,理解,Linux,文件系統(tǒng)的內(nèi)部技術(shù)，掌握,Linux,與文件有關(guān)的系統(tǒng)調(diào)用命令，并在此,基礎(chǔ)上建立面向隨機(jī)檢索的,hash,結(jié)構(gòu)文,件。,Linux,系統(tǒng)保持,UNIX,文件系統(tǒng)的風(fēng)格，提,供流式文件界面，這種結(jié)構(gòu)具有簡(jiǎn)潔靈活,的特點(diǎn)，但并不直接支持記錄式文件和關(guān),鍵字檢索。本實(shí)驗(yàn)是在,Linux,文件系統(tǒng)基礎(chǔ),上，設(shè)計(jì)一組庫(kù)函數(shù)，以提供對(duì)隨機(jī)檢索,的支持。,實(shí)驗(yàn)內(nèi)容,?,?,參考教材中,hash,文件構(gòu)造算法，設(shè)計(jì)一組,hash,文件函數(shù)

2、，包括,hash,文件創(chuàng)建、打,開(kāi)、關(guān)閉、讀、寫(xiě)等。,編寫(xiě)一個(gè)測(cè)試程序，通過(guò)記錄保存、查,找、刪除等操作，檢查上述,hash,文件是否,實(shí)現(xiàn)相關(guān)功能。,實(shí)驗(yàn)準(zhǔn)備,?,?,教程,Hash,文件核心算法，包括記錄保存、記,錄查找、記錄刪除等。,教程,Linux,系統(tǒng)有關(guān)文件的系統(tǒng)調(diào)用命令：,creat,，,open,，,close,，,read,，,write,，,lseek,。,實(shí)驗(yàn)設(shè)計(jì),?,由于在,Linux,系統(tǒng)核心之外模擬實(shí)現(xiàn),hash,文件，,有關(guān),hash,文件的說(shuō)明信息不能保存在,inode,中，,而只能記錄在文件的頭部。這些信息包括,hash,文件標(biāo)志、記錄大小、文件長(zhǎng)度、記錄數(shù)量

3、,等。,可以根據(jù),hash,文件核心算法設(shè)計(jì)內(nèi)部函數(shù)，包,括記錄的保存、查找、刪除等，在此基礎(chǔ)上實(shí),現(xiàn)讀、寫(xiě)等常規(guī)操作。,?,參考代碼,?,?,HashFile.h,HashFile.c,?,?,測(cè)試程序,jtRecord.h,測(cè)試程序,jtRecord.c,HashFile.h,#include ,#define COLLISIONFACTOR 0.5 /Hash,函數(shù)沖,突因子,struct HashFileHeader,int sig; /Hash,文件印鑒,int reclen; /,記錄長(zhǎng)度,int total_rec_num; /,總記錄數(shù),int current_rec_num;

4、 /,當(dāng)前記錄數(shù),;,struct CFTag,char collision; /,沖突計(jì)數(shù),char free; /,空閑標(biāo)志,;,int hashfile_creat(const char *filename,mode_t mode,int reclen,int,recnum);,/int hashfile_open(const char *filename,int flags);,int hashfile_open(const char *filename,int flags, mode_t mode);,int hashfile_close(int fd);,int hashfile_

5、read(int fd,int keyoffset,int keylen,void *buf);,int hashfile_write(int fd,int keyoffset,int keylen,void *buf);,int hashfile_delrec(int fd,int keyoffset,int keylen,void *buf);,int hashfile_findrec(int fd,int keyoffset,int keylen,void *buf);,int hashfile_saverec(int fd,int keyoffset,int keylen,void *

6、buf);,int hash(int keyoffset,int keylen,void *buf,int recnum);,int checkHashFileFull(int fd);,int readHashFileHeader(int fd,struct HashFileHeader *hfh ),HashFile.c,#include ,#include ,#include ,#include ,#include ,#include HashFile.h,int hashfile_creat(const char *filename,mode_t mode,int reclen,int

7、 total_rec_num),struct HashFileHeader hfh;,int fd;,int rtn;,char *buf;,int i=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,/lseek(fd,sizeof(struct HashFileHeader),SEEK_SET);,if

8、(rtn!=-1),buf=(char*)malloc(reclen+sizeof(struct CFTag)*total_rec_num);,memset(buf,0,(reclen+sizeof(struct CFTag)*total_rec_num);,rtn=write(fd,buf,(reclen+sizeof(struct CFTag)*total_rec_num);,free(buf);,close(fd);,return rtn;,else,close(fd);,return -1;,int hashfile_open(const char *filename,int flag

9、s, mode_t mode),int fd=open(filename,flags,mode);,struct HashFileHeader hfh;,if(read(fd,if(hfh.sig=31415926),return fd;,else,return -1;,else,return -1;,int hashfile_close(int fd),return close(fd);,int hashfile_read(int fd,int keyoffset,int keylen,void *buf),struct HashFileHeader hfh;,readHashFileHea

10、der(fd,int offset=hashfile_findrec(fd,keyoffset,keylen,buf);,if(offset!=-1),lseek(fd,offset+sizeof(struct CFTag),SEEK_SET);,return read(fd,buf,hfh.reclen);,else,return -1;,int hashfile_write(int fd,int keyoffset,int keylen,void *buf),return hashfile_saverec(fd,keyoffset,keylen,buf);,/return -1;,int

11、hashfile_delrec(int fd,int keyoffset,int keylen,void *buf),int offset;,offset=hashfile_findrec(fd,keyoffset,keylen,buf);,if(offset!=-1),struct CFTag tag;,read(fd,tag.free=0; /,置空閑標(biāo)志,lseek(fd,offset,SEEK_SET);,write(fd,struct HashFileHeader hfh;,readHashFileHeader(fd,int addr=hash(keyoffset,keylen,bu

12、f,hfh.total_rec_num);,offset=sizeof(struct HashFileHeader)+addr*(hfh.reclen+sizeof(struct CFTag);,if(lseek(fd,offset,SEEK_SET)=-1),return -1;,read(fd,tag.collision-; /,沖突記數(shù)減,1,lseek(fd,offset,SEEK_SET); /,write(fd,hfh.current_rec_num-; /,當(dāng)前記錄數(shù)減,1,lseek(fd,0,SEEK_SET);,write(fd,else,return -1;,int ha

13、shfile_findrec(int fd,int keyoffset,int keylen,void *buf),struct HashFileHeader hfh;,readHashFileHeader(fd,int addr=hash(keyoffset,keylen,buf,hfh.total_rec_num);,int offset=sizeof(struct HashFileHeader)+addr*(hfh.reclen+sizeof(struct CFTag);,if(lseek(fd,offset,SEEK_SET)=-1),return -1;,struct CFTag t

14、ag;,read(fd,char count=tag.collision;,if(count=0),return -1; /,不存在,recfree:,if(tag.free=0),offset+=hfh.reclen+sizeof(struct CFTag);,if(lseek(fd,offset,SEEK_SET)=-1),return -1;,read(fd,goto recfree;,else,char *p=(char*)malloc(hfh.reclen*sizeof(char);,read(fd,p,hfh.reclen);,/printf(Record is %d,%sn,(s

15、truct jtRecord*)p)-key,(struct,jtRecord*)p)-other);,char *p1,*p2;,p1=(char*)buf+keyoffset;,p2=p+keyoffset;,int j=0;,while(*p1=*p2),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)

16、;,p=NULL;,return -1; /,不存在,free(p);,p=NULL;,offset+=hfh.reclen+sizeof(struct CFTag);,if(lseek(fd,offset,SEEK_SET)=-1),return -1;,read(fd,goto recfree;,int hashfile_saverec(int fd,int keyoffset,int keylen,void *buf),if(checkHashFileFull(fd),return -1;,struct HashFileHeader hfh;,readHashFileHeader(fd,

17、int addr=hash(keyoffset,keylen,buf,hfh.total_rec_num);,int offset=sizeof(struct HashFileHeader)+addr*(hfh.reclen+sizeof(struct CFTag);,if(lseek(fd,offset,SEEK_SET)=-1),return -1;,struct CFTag tag;,read(fd,tag.collision+;,lseek(fd,sizeof(struct CFTag)*(-1),SEEK_CUR);,write(fd,while(tag.free!=0) /,沖突，

18、順序探查,offset+=hfh.reclen+sizeof(struct CFTag);,if(offset=lseek(fd,0,SEEK_END),offset=sizeof(struct HashFileHeader);/reach at,end,then rewind,if(lseek(fd,offset,SEEK_SET)=-1),return -1;,read(fd,tag.free=1;,lseek(fd,sizeof(struct CFTag)*(-1),SEEK_CUR);,write(fd,write(fd,buf,hfh.reclen);,hfh.current_rec

19、_num+; /,當(dāng)前記錄數(shù)加,1,lseek(fd,0,SEEK_SET);,return write(fd, /,存入記錄,int hash(int keyoffset,int keylen,void *buf,int,total_rec_num),int i=0;,char *p=(char *)buf+keyoffset;,int addr=0;,for(i=0;ikeylen;i+),addr+=(int)(*p);,p+;,return,addr%(int)(total_rec_num*COLLISIONFACTOR);,int readHashFileHeader(int fd,

20、struct HashFileHeader,*hfh ),lseek(fd,0,SEEK_SET);,return read(fd,hfh,sizeof(struct HashFileHeader);,int checkHashFileFull(int fd),struct HashFileHeader hfh;,readHashFileHeader(fd,if(hfh.current_rec_numhfh.total_rec_num),return 0;,else,return 1;,測(cè)試程序,jtRecord.h,#define RECORDLEN 32,struct jtRecord,i

21、nt key;,char otherRECORDLEN-sizeof(int);,;,#ifdef HAVE_CONFIG_H,#include ,#endif,測(cè)試程序,jtRecord.c,#ifdef HAVE_CONFIG_H,#include ,#endif,#include ,#include ,#include ,#include ,#include ,#include ,#include ,#include HashFile.h,#include jtRecord.h,#define KEYOFFSET 0,#define KEYLEN sizeof(int),#define

22、FILENAME jing.hash,void showHashFile();,int main(int argc, char *argv),struct jtRecord rec6=,1,jing,yuan,;,int j=0;,for(j=0;j6;j+),printf(t,recj.key,hash(KEYOFFSET,KEYLEN,int fd=hashfile_creat(FILENAME,O_RDWR|O_CREAT,RECORDLEN,6);,int i=0;,printf(nOpen ans Save Record.n);,fd=hashfile_open(FILENAME,O

23、_RDWR,0);,for(i=0;i6;i+),hashfile_saverec(fd,KEYOFFSET,KEYLEN,hashfile_close(fd);,showHashFile();,/Demo find Rec,printf(nFind Record.);,fd=hashfile_open(FILENAME,O_RDWR,0);,int offset=hashfile_findrec(fd,KEYOFFSET,KEYLEN,printf(noffset is %dn,offset);,hashfile_close(fd);,struct jtRecord jt;,struct C

24、FTag tag;,fd=open(FILENAME,O_RDWR);,lseek(fd,offset,SEEK_SET);,read(fd,printf(Tag is t,tag.collision,tag.free);,read(fd,printf(Record is %d,%sn,jt.key,jt.other);,/Demo Delete Rec,printf(nDelete Record.);,fd=hashfile_open(FILENAME,O_RDWR,0);,hashfile_delrec(fd,KEYOFFSET,KEYLEN,hashfile_close(fd);,showHashFile();,/Demo Read,fd=hashfile_open(FILENA