find.c

数据库系统实现

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <io.h>
#include <fcntl.h>
#include <time.h >
#include "linear_hash.h"

extern BUCKET_BUF 		bucket;
extern DATA_BUF			data;
extern NTH_BLOCK_BUF	nth_blk_relation;
extern HASH_INFO 		hash_info;

extern long				DATA_CUR;//记录最后最后读入的数据块号
extern long				NTH_BLK_CUR;//记录最后读入的对应信息块号
extern long				SEARCH_CUR;

extern BUCKET_BUF		buk_buf[BUCKET_BUFFER_SIZE];
extern BUCKET_BUF		buk_over_buf[BUCKET_BUFFER_SIZE];
extern DATA_BUF			dat_buf[DATA_BUFFER_SIZE];
extern NTH_BLOCK_BUF	nth_blk_buf[NTH_BLOCK_BUFFER_SIZE];

void find_data_operate()
{
	long n = 0;
	long m = 0;
	long j = 0;
	long i = 0;
	long add_in = 0;
	long flag = 0;
	long found = 0;
	long power = 0;
	FILE *fp = NULL;
	fp = fopen("find_result.dat", "a");
	power = pow(2, hash_info.hkey_i - 1);

	while( i < DATA_BUFFER_SIZE )
	{
		j = 0;
		while( j < LONG_IN_BLOCK )
		{
			if(dat_buf[i].key[j] != -1)
			{
				add_in = add_in_which(dat_buf[i].key[j], hash_info.hkey_i);
				if( add_in < hash_info.bucket_no)
					flag = add_in;
				else
					flag = add_in - power;
			
				m = 0;
				while( m < BUCKET_BUFFER_SIZE )
				{
					if(flag == buk_buf[m].nth_bucket)
					{
						found = 0;
						while(flag == buk_buf[m].nth_bucket && found == 0)
						{
							n = 0;
							while( n < HASH_SPACE && found == 0)
							{
								if(buk_buf[m].buk.hk_addr[n].hkey == dat_buf[i].key[j])
								{
									fprintf(fp, "%9d found,BUCKET_NO: %4d, PYSICAL_BLOCK: %4d, OFFSET: %4d\n", dat_buf[i].key[j], buk_buf[m].nth_bucket, buk_buf[m].buk.hk_addr[n].to_rcd.blk_no, buk_buf[m].buk.hk_addr[n].to_rcd.offset);
									dat_buf[i].key[j] = -1;
									found = 1;
									goto L;
								}
								n++;
							}
							m++;
						}
						m--;
						if(found == 0)
						{
							fprintf(fp, "%10d Not Found!\n", dat_buf[i].key[j]);
						}
					}
					m++;
				}
			}
			L: j++;
		}
		i++;
	}
	fclose(fp);
}
void find_read_nth_blk()
{
		long j = 0;
		long flag = 0;
		NTH_BLK_CUR = 0;
		while( j < NTH_BLOCK_BUFFER_SIZE )//读入对应关系文件块
		{
			if (nth_blk_buf[j].from_blk_no == -1)
			{
				flag = read_nth_blk("nth_block.dat", NTH_BLK_CUR);
				if(flag == 1)
				{
					nth_blk_buf[j] = nth_blk_relation;
					NTH_BLK_CUR++;
				}
				else
				{
					break;
				}
			}
			j++;
			if( j == NTH_BLOCK_BUFFER_SIZE ) 
			{
				find_scan_in_buf_nth_blk();
				j = 0;
			}
		}
		find_scan_in_buf_nth_blk();
}
void find_scan_in_buf_nth_blk()
{
	long i = 0;
	long j = 0;
	long m = 0;
	long n = 0;
	while( m < NTH_BLOCK_BUFFER_SIZE)//根据读入的对应信息文件 将相应块读入索引缓冲
	{												//可能索引缓冲满了，溢出桶也读入了～可以减少查找的I/O次数
		if(nth_blk_buf[m].from_blk_no != -1)
		{
			while( n < NTH_BLOCK_IN_BLOCK)
			{
				if( nth_blk_buf[m].nth_blk[n].nth_bucket != -1)
				{
					read_idx("hash_table.idx", nth_blk_buf[m].nth_blk[n].nth_bucket, nth_blk_buf[m].nth_blk[n].blk_no);
					while(j < BUCKET_BUFFER_SIZE)
					{	
						i = 0;
						while(bucket.buk.blk_no != -1)//判断当前桶的溢出桶个数
						{
							read_idx("hash_table.idx", nth_blk_buf[m].nth_blk[n].nth_bucket, bucket.buk.blk_no);
							i++;
						}
						
						if( (BUCKET_BUFFER_SIZE - j) >= (i + 1))//将桶和溢出桶读入
						{
							read_idx("hash_table.idx", nth_blk_buf[m].nth_blk[n].nth_bucket, nth_blk_buf[m].nth_blk[n].blk_no);
							buk_buf[j] = bucket;
							j++;
							while(bucket.buk.blk_no != -1)
							{
								read_idx("hash_table.idx", nth_blk_buf[m].nth_blk[n].nth_bucket, bucket.buk.blk_no);
								buk_buf[j] = bucket;
								j++;
							}
							if ( j == BUCKET_BUFFER_SIZE )
							{
								find_data_operate();
								j = 0;
								break;
							}
							else
								break;
						}
						else
						{
							find_data_operate();
							j = 0;
							break;
						}
					}
				}
				n++;
			}
		}
		m++;
	}
	find_data_operate();
	
	for( j = 0; j < NTH_BLOCK_BUFFER_SIZE; j++ )
	{
		nth_blk_buf[j].from_blk_no = -1;
	}
}
void find_key(char *filename)
{
	long flag = 0;
	long p = 0;
	long i = 0;
	long j = 0;

	SEARCH_CUR = 0;
	while(SEARCH_CUR != -1)
	{
		j = 0;
		for(i = 0; i < DATA_BUFFER_SIZE; i++)
		{
			dat_buf[i].from_blk_no = -1;
			for(p = 0; p < LONG_IN_BLOCK; p++)
			{
				dat_buf[i].key[p] = -1;
			}
		}
		while ( j < DATA_BUFFER_SIZE )//读入需要加入的数据块
		{
			if( dat_buf[j].from_blk_no == -1 )
			{
				flag = read_dat(filename, SEARCH_CUR); 
				if(flag != 0)
				{
				dat_buf[j] = data;
				SEARCH_CUR++;
				}
				else
				{
					SEARCH_CUR = -1;
					break;
				}
			}
			j++;
		}
		find_read_nth_blk();
	}
}
void find_single_key(long key)
{
	long power = 0;
	long find_in = -1;
	long flag = 0;
	power = pow(2, hash_info.hkey_i - 1);
	if(key == -1)
		return;
	
	if(key != -1)
	{
		find_in = add_in_which(key, hash_info.hkey_i);
		if( find_in < hash_info.bucket_no)
			flag = find_in;
		else
			flag = find_in - power;
	}
	find_single_read_nth_blk(flag, key);
}

void find_single_read_nth_blk(long fhkey, long key)
{
	long j = 0;
	long i = 0;
	long flag = 0;
	NTH_BLK_CUR = 0;
	while( j < NTH_BLOCK_BUFFER_SIZE )//读入对应关系文件块
	{
		if (nth_blk_buf[j].from_blk_no == -1)
		{
			flag = read_nth_blk("nth_block.dat", NTH_BLK_CUR);
			if(flag == 1)
			{
				nth_blk_buf[j] = nth_blk_relation;
				for( i = 0; i < NTH_BLOCK_IN_BLOCK; i++)
				{
					if(nth_blk_buf[j].nth_blk[i].nth_bucket == fhkey)
					{
						find_single_scan_in_buf_nth_blk(fhkey, key);
						goto ZZ;
					}
				}
				NTH_BLK_CUR++;
			}
			else
			{
				break;
			}
		}
		j++;
	}
	ZZ: ;
}

void find_single_scan_in_buf_nth_blk(long fhkey, long key)
{
	long i = 0;
	long j = 0;
	long m = 0;
	long n = 0;
	while( m < NTH_BLOCK_BUFFER_SIZE)
	{
		if(nth_blk_buf[m].from_blk_no != -1)
		{
			while( n < NTH_BLOCK_IN_BLOCK)
			{
				if( nth_blk_buf[m].nth_blk[n].nth_bucket == fhkey)
				{
					read_idx("hash_table.idx", nth_blk_buf[m].nth_blk[n].nth_bucket, nth_blk_buf[m].nth_blk[n].blk_no);
					while(j < BUCKET_BUFFER_SIZE)
					{	
						i = 0;
						while(bucket.buk.blk_no != -1)//判断当前桶的溢出桶个数
						{
							read_idx("hash_table.idx", nth_blk_buf[m].nth_blk[n].nth_bucket, bucket.buk.blk_no);
							i++;
						}
						
						if( (BUCKET_BUFFER_SIZE - j) >= (i + 1))//将桶和溢出桶读入
						{
							read_idx("hash_table.idx", nth_blk_buf[m].nth_blk[n].nth_bucket, nth_blk_buf[m].nth_blk[n].blk_no);
							buk_buf[j] = bucket;
							j++;
							while(bucket.buk.blk_no != -1)
							{
								read_idx("hash_table.idx", nth_blk_buf[m].nth_blk[n].nth_bucket, bucket.buk.blk_no);
								buk_buf[j] = bucket;
								j++;
							}
							if ( j == BUCKET_BUFFER_SIZE )
							{
								find_single_data_operate(fhkey, key);
								j = 0;
								break;
							}
							else
								break;
						}
						else
						{
							find_single_data_operate(fhkey, key);
							j = 0;
							break;
						}
					}
				}
				n++;
			}
		}
		m++;
	}
	find_single_data_operate(fhkey, key);
	
	for( j = 0; j < NTH_BLOCK_BUFFER_SIZE; j++ )
	{
		nth_blk_buf[j].from_blk_no = -1;
	}
}

void find_single_data_operate(long fhkey, long key)
{
	long 	m = 0;
	long 	n = 0;
	long 	found = 0;
	while( m < BUCKET_BUFFER_SIZE )
	{
		if(fhkey == buk_buf[m].nth_bucket)
		{
			found = 0;
			while(fhkey == buk_buf[m].nth_bucket && found == 0)
			{
				n = 0;
				while( n < HASH_SPACE && found == 0)
				{
					if(buk_buf[m].buk.hk_addr[n].hkey == key)
					{
						printf("%9d found,BUCKET_NO: %4d, PYSICAL_BLOCK: %4d, OFFSET: %4d\n", key, buk_buf[m].nth_bucket, buk_buf[m].buk.hk_addr[n].to_rcd.blk_no, buk_buf[m].buk.hk_addr[n].to_rcd.offset);
						found = 1;
						goto TT;
					}
					n++;
				}
				m++;
			}
			m--;
			if(found == 0)
			{
				printf("%10dNot Found\n", key);
			}
		}
		m++;
	}
	TT: ;
}