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)康睦斫釲inux文件系統(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ù)，包括hash文件創(chuàng)建、打開(kāi)、關(guān)閉、讀、寫(xiě)等。編寫(xiě)一個(gè)測(cè)試程序，通過(guò)記錄保存、查找、刪除等操作，檢查上述hash文件是

2、否實(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ù)量等?？梢愿鶕?jù)hash文件核心算法設(shè)計(jì)內(nèi)部函數(shù)，包括記錄的保存、查找、刪除等，在此基礎(chǔ)上實(shí)現(xiàn)讀、寫(xiě)等常規(guī)操作。 參考代碼 HashFile.h HashFile.c測(cè)試程序jtRecord.h測(cè)試程序jtRecor

3、d.cHashFile.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; /當(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);

4、/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_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 keyof

5、fset,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 *buf);int hash(int keyoffset,int keylen,void *buf,int recnum);int checkHashFileFull(int fd);int readHashFileHeader(int fd,struct HashFileHeader *hfh )

6、HashFile.c#include #include #include #include #include #include HashFile.hint hashfile_creat(const char *filename,mode_t mode,int reclen,int 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.curren

7、t_rec_num=0; /fd=open(filename,mode); fd=creat(filename,mode); if(fd!=-1) rtn=write(fd,&hfh,sizeof(struct HashFileHeader); /lseek(fd,sizeof(struct HashFileHeader),SEEK_SET); if(rtn!=-1) buf=(char*)malloc(reclen+sizeof(struct CFTag)*total_rec_num); memset(buf,0,(reclen+sizeof(struct CFTag)*total_

8、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 flags, mode_t mode) int fd=open(filename,flags,mode); struct HashFileHeader hfh; if(read(fd,&hfh,sizeof(struct HashFileH

9、eader)!=-1) lseek(fd,0,SEEK_SET); 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; readHashFileHeader(fd,&hfh); int offset=hashfile_findrec(fd,keyoffs

10、et,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 hashfile_delrec(int fd,int keyoffset,int keyle

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

12、r=hash(keyoffset,keylen,buf,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,sizeof(struct CFTag); tag.collision-; /沖突記數(shù)減1 lseek(fd,offset,SEEK_SET); / write(fd,&tag,sizeof(struct CFTag);hf

13、h.current_rec_num-; /當(dāng)前記錄數(shù)減1lseek(fd,0,SEEK_SET);write(fd,&hfh,sizeof(struct HashFileHeader); else return -1; int hashfile_findrec(int fd,int keyoffset,int keylen,void *buf) struct HashFileHeader hfh; readHashFileHeader(fd,&hfh); int addr=hash(keyoffset,keylen,buf,hfh.total_rec_num); int off

14、set=sizeof(struct HashFileHeader)+addr*(hfh.reclen+sizeof(struct CFTag); if(lseek(fd,offset,SEEK_SET)=-1) return -1; struct CFTag tag;read(fd,&tag,sizeof(struct CFTag); char count=tag.collision; if(count=0) return -1; /不存在recfree: if(tag.free=0) offset+=hfh.reclen+sizeof(struct CFTag); if(lseek(

15、fd,offset,SEEK_SET)=-1) return -1; read(fd,&tag,sizeof(struct CFTag); goto recfree; else char *p=(char*)malloc(hfh.reclen*sizeof(char); read(fd,p,hfh.reclen); /printf(Record is %d,%sn,(struct jtRecord*)p)-key,(struct jtRecord*)p)-other); char *p1,*p2; p1=(char*)buf+keyoffset; p2=p+keyoffset; int

16、 j=0;while(*p1=*p2)&(j=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,sizeof(struct CFTag); tag.free=1; lseek(fd,sizeof(struct CFTag)*(-1),SEEK_CUR); write(fd,&tag,sizeof(struct CFTag); write(fd

17、,buf,hfh.reclen); hfh.current_rec_num+; /當(dāng)前記錄數(shù)加1 lseek(fd,0,SEEK_SET); return write(fd,&hfh,sizeof(struct HashFileHeader); /存入記錄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%

18、(int)(total_rec_num*COLLISIONFACTOR);int readHashFileHeader(int fd,struct HashFileHeader *hfh ) lseek(fd,0,SEEK_SET); return read(fd,hfh,sizeof(struct HashFileHeader);int checkHashFileFull(int fd) struct HashFileHeader hfh; readHashFileHeader(fd,&hfh); if(hfh.current_rec_numhfh.total_rec_num) re

19、turn 0; else return 1; 測(cè)試程序jtRecord.h #define RECORDLEN 32struct jtRecord int 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

20、#define KEYOFFSET 0#define KEYLEN sizeof(int)#define FILENAME jing.hashvoid showHashFile();int main(int argc, char *argv) struct jtRecord rec6= 1,jing ,2,wang,3,li,4,zhang,5,qing,6,yuan ; int j=0; for(j=0;j6;j+) printf(t,recj.key,hash(KEYOFFSET,KEYLEN,&recj,6); int fd=hashfile_creat(FILENAME,O_R

21、DWR|O_CREAT,RECORDLEN,6); int i=0; printf(nOpen ans Save Record.n); fd=hashfile_open(FILENAME,O_RDWR,0); for(i=0;i6;i+) hashfile_saverec(fd,KEYOFFSET,KEYLEN,&reci); hashfile_close(fd); showHashFile(); /Demo find Rec printf(nFind Record.); fd=hashfile_open(FILENAME,O_RDWR,0); int offset=hashfile_

22、findrec(fd,KEYOFFSET,KEYLEN,&rec4); printf(noffset is %dn,offset); hashfile_close(fd); struct jtRecord jt; struct CFTag tag; fd=open(FILENAME,O_RDWR); lseek(fd,offset,SEEK_SET); read(fd,&tag,sizeof(struct CFTag); printf(Tag is t,tag.collision,tag.free); read(fd,&jt,sizeof(struct jtRecord

23、); 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,&rec2); hashfile_close(fd); showHashFile(); /Demo Read fd=hashfile_open(FILENAME,O_RDWR,0); char buf32; memcpy(buf,&rec1,KEYLEN); hashfile_read(fd,KEYOFFSET,KEYLEN,buf); printf(nRead Record is