linux 实验四 文件系统

/*************************************************************************** * Copyright (C) 2004 by root * * root@simplemepis * * * * This program is free software; you can redistribute it and/or modify * * it under the terms of the GNU General Public License as published by * * the Free Software Foundation; either version 2 of the License, or * * (at your option) any later version. * * * * This program is distributed in the hope that it will be useful, * * but WITHOUT ANY WARRANTY; without even the implied warranty of * * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * * GNU General Public License for more details. * * * * You should have received a copy of the GNU General Public License * * along with this program; if not, write to the * * Free Software Foundation, Inc., * * 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. * ***************************************************************************/ #include <unistd.h> #include <sys/types.h> #include <sys/stat.h> #include <fcntl.h> #include <stdio.h> #include "HashFile.h" int 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.current_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_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) { //return -1; int fd=open(filename,flags); struct HashFileHeader hfh; if(read(fd,&hfh,sizeof(HashFileHeader))!=-1) { if(hfh.sig==20041111) return 1; } else 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 HashFileHeader))!=-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,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 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,sizeof(struct CFTag)); tag.free=0; lseek(fd,offset,SEEK_SET); write(fd,&tag,sizeof(struct CFTag)); struct HashFileHeader hfh; readHashFileHeader(fd,&hfh); int addr=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--; lseek(fd,offset,SEEK_SET); write(fd,&tag,sizeof(struct CFTag)); hfh.current_rec_num--; lseek(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 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,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(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,%s}\n",((struct jtRecord*)p)->key,((struct jtRecord*)p)->other); char *p1,*p2; p1=(char*)buf+keyoffset; p2=p+keyoffset; int j=0; while((*p1==*p2)&&(j<keylen)) { p1++; p2++; j++; } if(j==keylen) { free(p); p=NULL; return (offset);//找到,返回偏移值,此值包括原记录及其前两个INT量,即冲突计数和空闲标志 } else { if(addr==hash(keyoffset,keylen,p,hfh.total_rec_num)) { count--; if(count==0) { free(p); 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,&tag,sizeof(struct CFTag)); goto recfree; } } } int hashfile_saverec(int fd,int keyoffset,int keylen,void *buf) { if(checkHashFileFull(fd)) { return -1; } struct HashFileHeader hfh; readHashFileHeader(fd,&hfh); 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,sizeof(struct CFTag)); tag.collision++; lseek(fd,sizeof(struct CFTag)*(-1),SEEK_CUR); write(fd,&tag,sizeof(struct CFTag)); while(tag.free!=0) { 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,sizeof(struct CFTag)); } tag.free=1; lseek(fd,sizeof(struct CFTag)*(-1),SEEK_CUR); write(fd,&tag,sizeof(struct CFTag)); write(fd,buf,hfh.reclen); hfh.current_rec_num++; 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;i<keylen;i++) { addr+=(int)(*p); p++; } return addr%(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) { /* int oldoffset=lseek(fd,0,SEEK_CUR); lseek(fd,sizeof(struct HashFileHeader),SEEK_SET); struct CF