hash.cpp

数据库索引技术中的可扩充线性哈希表visual C++实现

			loc=htable[loc].next;
			htable[loc].data[htable[loc].count][0]=b.id;
			htable[loc].data[htable[loc].count][1]=b.rid;
			htable[loc].count++;
			flag=1;
			if(b.rid==2802)cout<<"loc"<<loc<<"count"<<htable[loc].count<<endl;
			break;
		}
		loc=htable[loc].next;
	}
	if(htable[loc].next==-1&&htable[loc].count==tablesize&&flag==-1){
		htable[loc].next=table_count++;
		loc=htable[loc].next;
		htable[loc].data[htable[loc].count][0]=b.id;
		htable[loc].data[htable[loc].count][1]=b.rid;
		htable[loc].count++;
		flag=1;
		if(b.rid==2802)cout<<"loc"<<loc<<"count"<<htable[loc].count<<endl;
	}
	else if(htable[loc].count!=tablesize&&flag==-1){
		htable[loc].data[htable[loc].count][0]=b.id;
		htable[loc].data[htable[loc].count][1]=b.rid;
		htable[loc].count++;
		flag=1;
	}
	return flag;
}

int find(int id,hash_entry *he){
	int key=id%HASH;
	int flag=-1;
	if(he->entry[key]==-1)return flag;
	int loc=he->entry[key];
	if(htable[loc].next==-1){
		for(int i=0;i<tablesize;i++){
			if(htable[loc].data[i][0]==id)return htable[loc].data[i][1];
		}
	}
	while(htable[loc].next!=-1){
		for(int i=0;i<tablesize;i++){
			if(htable[loc].data[i][0]==id)return htable[loc].data[i][1];
		}
		loc=htable[loc].next;
	}
}


/*
//linear hashing
//insert, handle split
hash_entry* insert(book b,hash_entry *he){//return updated hash entry
	if(entry_pointer==entry_size){//ask for a new entry array
		hash_entry *he1=he;
		he=new hash_entry(2*he->size);//careful
		for(int i=0;i<entry_size;i++){
			he->entry[i]=he1->entry[i];//copy to new hash entry
			if(he->entry[i]==-1){
				he->entry[i]=ask_free();
				htable[he->entry[i]].local=1;
			}
		}
		entry_pointer=0;
		global++;
		delete he1;
	}
	if(he->entry[entry_size+entry_pointer]==-1&&he->entry[entry_pointer]!=-1)
		he->entry[entry_size+entry_pointer]=he->entry[entry_pointer];
	int key=b.id%hashf[global-1];
	//find a proper buckit to insert
	if(he->entry[key]==-1){//first in an entry,allocate a direction
		//see if there is free block
		he->entry[key]=ask_free();
		htable[he->entry[key]].local=1;
	}
	int loc=he->entry[key];//hashed into ith bukit
	while(htable[loc].next!=-1){//find a bukit
		if(htable[loc].count<tablesize)break;
		loc=htable[loc].next;
	}
	int local=htable[loc].local;
	int count=htable[loc].count;
	if(global<local)cout<<"!depth error inserting htable ["<<loc<<"]"<<endl;
	if(count<tablesize){//still has free space
		int i=0;
		while(htable[loc].data[i][0]!=-1){
			i++;//find a hole
			if(i>tablesize){
				cout<<"!count eror inserting htable ["<<loc<<"]"<<endl;
			}
		}
		htable[loc].data[i][0]=b.id;
		htable[loc].data[i][1]=b.rid;
		htable[loc].count++;
		entry_pointer++;
		return he;
		//if(pointer>he->size)pointer=0;
	}
	else if(count==tablesize){//may need split
		htable[loc].next=ask_free();
		htable[htable[loc].next].local=htable[loc].local;
		loc=htable[loc].next;
		htable[loc].data[0][0]=b.id;
		htable[loc].data[0][1]=b.rid;
		htable[loc].count++;

		if(htable[he->entry[entry_pointer]].next!=-1){//split the one with pointer

			
			if(local+1>global)global=local+1;//set global depth
			int loctemp=he->entry[entry_pointer];

			if(loctemp!=-1){
				while(htable[loctemp].next!=-1){//reallocate
					//int local=htable[loc].local;
					for(int i=0;i<tablesize;i++){
						//not -1
						int k=htable[loctemp].data[i][0]%(hashf[local+1]);//&*#&#@&#^#
						int j=htable[loctemp].data[i][0]%(hashf[local]);
						if(htable[loctemp].data[i][0]!=-1&&k!=j){

			
								if(he->entry[k]==-1){
									he->entry[k]=ask_free();
								}
								int destination=he->entry[k];
								move(loctemp,i,destination);
								while(htable[destination].next!=-1){//set local depth
									htable[destination].local=local+1;
									destination=htable[destination].next;
								}
						
						}
					}
					loctemp=htable[loctemp].next;
				}
				int loctemp=he->entry[entry_pointer];
				int l=compact(loctemp,-1,loctemp,-1);
				if(l==-1)cout<<"error compact"<<loctemp<<endl;
				free_table(loctemp);
				while(htable[loctemp].next!=-1){//set local depth
						htable[loctemp].local=local+1;
						loctemp=htable[loctemp].next;
					}
			}
		}
		entry_pointer++;
		return he;
	}
}
*/

int get_int(char st[]){
	int temp[4];
	int id;
	for(int i=0;i<4;i++)
		temp[i]=(unsigned char)st[i];
	return id=(temp[0]<<24)+(temp[1]<<16)+(temp[2]<<8)+temp[3];
}
/*
void foutput(book& b,fstream &fs){
	if(b.rid<0) fs<<"not found!"<<endl;
	cout<<"rid:"<<left<<setw(10)<<b.rid<<"ID:"<<left<<setw(10)<<b.id<<'|'<<left<<setw(30)<<b.name<<'|'<<"YEAR:"<<left<<setw(15)<<b.year<<'|'<<left<<setw(20)<<b.press<<'|'<<b.author<<endl;
}

void output(book b){
	if(b.rid<0) cout<<"not found!"<<endl;
	cout<<"rid:"<<left<<setw(10)<<b.rid<<"ID:"<<left<<setw(10)<<b.id<<'|'<<left<<setw(30)<<b.name<<'|'<<"YEAR:"<<left<<setw(15)<<b.year<<'|'<<left<<setw(20)<<b.press<<'|'<<b.author<<endl;
}
*/

//根据rid，直接定位到文件，获取返回book
book get_book(int rid){
	//if(rid<1||rid>tuple) return NULL;
	book temp_book;
	temp_book.rid=rid;
	int p=0;
	char temp_id[5];
	char temp_year[5];
	fp.clear();
	fp.seekg(0,ios_base::beg);
	fp.seekg((rid-1)*128,ios_base::cur);
	int current=fp.tellg();
	//0-3 ID(int)  4-59 name (char) 60-63 year(int)  64-95 press(char) 96-127 author(char)
	for(int i=0;i<4;i++){
		temp_id[i]=fp.get();//直接用fp.get(temp_id,5) 会有问题。。莫名其妙地碰到10就跳过去，而且文件状态出错。。。
	}
		fp.clear();
		fp.seekg(current,ios_base::beg);
		fp.seekg(4,ios_base::cur);


//  cout<<fp.tellg()<<endl;
	fp.get(temp_book.name,56+1);
//	cout<<fp.tellg()<<endl;
	fp.get(temp_year,4+1);
//	cout<<fp.tellg()<<endl;
	fp.get(temp_book.press,32+1);
//	cout<<fp.tellg()<<endl;
	fp.get(temp_book.author,32+1);
//	cout<<fp.tellg()<<endl;
	temp_book.id=get_int(temp_id);
	temp_book.year=get_int(temp_year);
	return temp_book;
}
void output(book b){
	cout<<"rid: "<<b.rid<<" |";
	cout<<"ID: "<<b.id<<" |";
	for(int i=0;i<16;i++)
		cout<<b.name[i];
	cout<<" |";
	cout<<b.year;
	cout<<" |";
	for(i=0;i<15;i++)
		cout<<b.press[i];
	cout<<" |";
	for(i=0;i<15;i++)
		cout<<b.author[i];
	cout<<endl;
}
void foutput(book b){
	ofstream fout("result.txt");
	fout<<"rid: "<<b.rid<<" |";
	fout<<"ID: "<<b.id<<" |";
	for(int i=0;i<16;i++)
		fout<<b.name[i];
	fout<<" |";
	fout<<b.year;
	fout<<" |";
	for(i=0;i<15;i++)
		fout<<b.press[i];
	cout<<" |";
	for(i=0;i<15;i++)
		fout<<b.author[i];
	fout<<endl;
}

int range_search(int id1,int id2, hash_entry *he){
	int k=-1;
	for(int i=id1;i<=id2;i++){
		k=find(i,he);
		if(k!=-1){
			book b=get_book(k);
			output(b);
			foutput(b);
			/*
			int rid;
			int id;
			char name[57];
			int year;
			char press[33];
			char author[33];
			*/
			//foutput(b,fo);
		}
	}
	return 1;
}

/*
bool create_hash(){
	book temp;
	for(int i=0;i<MAXN;i++){
		temp=get_book(i);
		insert(temp,he);
	}
}
*/

void main(){
	/*create hash
	int k=0;
	hash_entry *he=new hash_entry(3600);
	for(int i=1;i<=MAXN;i++){
		k=insert(get_book(i),he);
		if(k==1)cout<<i<<endl;
	}
	write_entry(he);
	write_hash();
	*/
	//find
	hash_entry *he=read_entry();
	read_hash();
	//int i=find(13,he);
	range_search(1,10,he);
}

	/*extenable hash
	//initializing
	hash_entry *he=new hash_entry(2);
	global=1;
	//entry_size=1;
	int i;
	hashf[0]=1;
	for(i=0;i<32;i++){
		hashf[i+1]=2*hashf[i];
	}
	for(i=1;i<=100;i++){
		he=insert(get_book(i),he);
		write_entry(he);
		write_hash();
	}
	*/
	/*testing hash table
	hash_table *ht=new hash_table(4);
	cout<<ht.global_depth<<endl;
	ht.table[1]=1;
	cout<<ht.table[1];
	*/
	//hash_entry he=read_entry();
	/*
	//test compact
    hash_table *ht;
	bool a=read_hash();
	cout<<a<<endl;
//	for(int i=0;i<9;i++){
	int b=compact(0,-1,0,-1);
	cout<<"compact "<<b<<endl;
	free_table(0);
//	}
//	cout<<"freehead: "<<freehead<<"freetail: "<<freetail<<endl;
//	move(3,2,2);
	bool c=write_hash();
	cout<<c<<endl;
	*/