construct_idx.c

数据库系统实现

									}
								
									if(yeah == 0)
									{
										fp = fopen("hash_table.idx", "rb+");
										get_blk(fp);
										fclose(fp);
										length++;
										buk_over_buf[m].buk.blk_no = length - 1;
										buk_over_buf[m].change_flag = 1;
										bucket = buk_over_buf[m];
										write_idx("hash_table.idx", bucket.from_blk_no);
										read_idx("hash_table.idx",buk_buf[m].nth_bucket, length - 1);
										bucket.buk.blk_no = -1;
										bucket.buk.rcd_no = 1;
										bucket.buk.hk_addr[0].hkey = dat_buf[i].key[j];
										dat_buf[i].key[j] = -1;
										bucket.buk.hk_addr[0].to_rcd.blk_no = dat_buf[i].from_blk_no;
										bucket.buk.hk_addr[0].to_rcd.offset = sizeof(long) * j;						
										buk_over_buf[m] = bucket;
										buk_over_buf[m].change_flag = 1;
									}
								}
							}
							
							else
							{
								fp = fopen("hash_table.idx", "rb+");
								get_blk(fp);
								fclose(fp);
								length++;
								buk_buf[m].buk.blk_no = length - 1;
								buk_buf[m].change_flag = 1;
								read_idx("hash_table.idx",buk_buf[m].nth_bucket, length - 1);
								bucket.buk.blk_no = -1;
								bucket.buk.rcd_no = 1;
								bucket.buk.hk_addr[0].hkey = dat_buf[i].key[j];
								dat_buf[i].key[j] = -1;
								bucket.buk.hk_addr[0].to_rcd.blk_no = dat_buf[i].from_blk_no;
								bucket.buk.hk_addr[0].to_rcd.offset = sizeof(long) * j;						
								buk_over_buf[m] = bucket;
								buk_over_buf[m].change_flag = 1;
							}
						}
					}
					m++;
				}
			}
			L: j++;
		}
		i++;
	}

	i = 0;
	m = 0;
	n = 0;
	p = 0;
	flag = 0;
	found = 0;
	found_over = 0;
	yeah = 0;
	while( i < hash_info.rcd_no )//将temp中的数据放入相应的桶～ 有可能要增加溢出桶～
	{
		if(temp[i].hkey != -1)
		{
			add_in = add_in_which(temp[i].hkey, 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)
					{
						n = 0;
						while( n < HASH_SPACE )
						{
							if(buk_buf[m].buk.hk_addr[n].hkey == -1)
							{
								buk_buf[m].buk.hk_addr[n] = temp[i];
								temp[i].hkey = -1;
								buk_buf[m].change_flag = 1;
								buk_buf[m].buk.rcd_no++;
								found = 1;
								goto N;
							}
							n++;
						}
						m++;
					}
					if(found == 0)
					{
						m--;
						if(buk_over_buf[m].from_blk_no != -1)
						{
							if( buk_over_buf[m].buk.blk_no != -1)
							{
								bucket = buk_over_buf[m];
								found_over = 0;
								while(bucket.buk.blk_no != -1)
								{
									read_idx("hash_table.idx", buk_buf[m].nth_bucket, bucket.buk.blk_no);
									p = 0;
									while( p < HASH_SPACE )
									{
										if(bucket.buk.hk_addr[p].hkey == -1)
										{
											bucket.buk.hk_addr[p] = temp[i];
											temp[i].hkey = -1;
											bucket.buk.rcd_no++;
											buk_over_buf[m] = bucket;
											buk_over_buf[m].change_flag = 1;
											found_over = 1;
											goto YY;
										}
										p++;
									}
								}
								YY: ;
								if( found_over == 0)
								{
									fp = fopen("hash_table.idx", "rb+");
									get_blk(fp);
									fclose(fp);
									length++;
									buk_over_buf[m].buk.blk_no = length - 1;
									buk_over_buf[m].change_flag = 1;
									bucket = buk_over_buf[m];
									write_idx("hash_table.idx", bucket.from_blk_no);
									read_idx("hash_table.idx",buk_buf[m].nth_bucket, length - 1);
									bucket.buk.blk_no = -1;
									bucket.buk.rcd_no = 1;
									bucket.buk.hk_addr[0] = temp[i];
									temp[i].hkey = -1;								
									buk_over_buf[m] = bucket;
									buk_over_buf[m].change_flag = 1;
								}
							}
							else
							{
								for( p = 0; p < HASH_SPACE; p++ )
								{
									if(buk_over_buf[m].buk.hk_addr[p].hkey == -1)
									{
										buk_over_buf[m].buk.hk_addr[p] = temp[i];
										temp[i].hkey = -1;
										buk_over_buf[m].buk.rcd_no++;	
										buk_over_buf[m].change_flag = 1;
										yeah = 1;
										break;
									}
								}
								
								if(yeah == 0)
								{
									fp = fopen("hash_table.idx", "rb+");
									get_blk(fp);
									fclose(fp);
									length++;
									buk_over_buf[m].buk.blk_no = length - 1;
									buk_over_buf[m].change_flag = 1;
									bucket = buk_over_buf[m];
									write_idx("hash_table.idx", bucket.from_blk_no);
									read_idx("hash_table.idx",buk_buf[m].nth_bucket, length - 1);
									bucket.buk.blk_no = -1;
									bucket.buk.rcd_no = 1;
									bucket.buk.hk_addr[0] = temp[i];
									temp[i].hkey = -1;
									buk_over_buf[m] = bucket;
									buk_over_buf[m].change_flag = 1;
								}
							}
						}
							
						else
						{
							fp = fopen("hash_table.idx", "rb+");
							get_blk(fp);
							fclose(fp);
							length++;
							buk_buf[m].buk.blk_no = length - 1;
							buk_buf[m].change_flag = 1;
							read_idx("hash_table.idx",buk_buf[m].nth_bucket, length - 1);
							bucket.buk.blk_no = -1;
							bucket.buk.rcd_no = 1;
							bucket.buk.hk_addr[0] = temp[i];
							temp[i].hkey = -1;					
							buk_over_buf[m] = bucket;
							buk_over_buf[m].change_flag = 1;
						}
					}
				}
				m++;
			}
		}
		N: i++;
	}
	
	j = 0;
	i = 0;
	while( j < BUCKET_BUFFER_SIZE)//将改动了的索引桶写回
	{
		if(buk_buf[j].change_flag == 1)
		{
			bucket.buk = buk_buf[j].buk;
			write_idx("hash_table.idx", buk_buf[j].from_blk_no);
			buk_buf[j].from_blk_no = -1;
			buk_buf[j].buk.blk_no = -1;
			buk_buf[j].nth_bucket = -1;
			buk_buf[j].change_flag = 0;
			buk_buf[j].buk.rcd_no = 0;
			for( i = 0;i < HASH_SPACE;i++)
				buk_buf[j].buk.hk_addr[i].hkey = -1;
		}
		else
		{
			buk_buf[j].from_blk_no = -1;
			buk_buf[j].buk.blk_no = -1;
			buk_buf[j].nth_bucket = -1;
			buk_buf[j].change_flag = 0;
			buk_buf[j].buk.rcd_no = 0;
			for( i = 0;i < HASH_SPACE;i++)
				buk_buf[j].buk.hk_addr[i].hkey = -1;
		}

		if(buk_over_buf[j].change_flag == 1)
		{
			bucket.buk = buk_over_buf[j].buk;
			write_idx("hash_table.idx", buk_over_buf[j].from_blk_no);
			buk_over_buf[j].from_blk_no = -1;
			buk_over_buf[j].buk.blk_no = -1;
			buk_over_buf[j].nth_bucket = -1;
			buk_over_buf[j].change_flag = 0;
			buk_over_buf[j].buk.rcd_no = 0;
			for( i = 0;i < HASH_SPACE;i++)
				buk_over_buf[j].buk.hk_addr[i].hkey = -1;
		}
		else
		{
			buk_over_buf[j].from_blk_no = -1;
			buk_over_buf[j].buk.blk_no = -1;
			buk_over_buf[j].nth_bucket = -1;
			buk_over_buf[j].change_flag = 0;
			buk_over_buf[j].buk.rcd_no = 0;
			for( i = 0;i < HASH_SPACE;i++)
				buk_over_buf[j].buk.hk_addr[i].hkey = -1;
		}
		j++;
	}

}
	
void add_hash_table_bucket(char *filename, long old_bucket_no)
{
	FILE *fp = NULL;
	long i = 0;
	long j = 0;
	long length = 0;
	long fd = 0;
	fd = open(filename, O_RDWR);
	length = filelength(fd)/BLOCK_SIZE;
	close(fd);
	fp = fopen(filename, "rb+");
	j = hash_info.bucket_no - old_bucket_no;
	if( fp != NULL)
	{
		while( i < j )
		{
			fp = get_blk(fp);
			init_hash_tab(fp);
			renew_nth_blk(old_bucket_no, length);
			old_bucket_no++;
			length++;
			i++;
		}
		fclose(fp);
	}
}

void renew_nth_blk(long nth_bucket, long bucket_no)
{
	long i = 0;
	long j = 0;
	long found = 0;
	long flag = 0;
	FILE *fp = NULL;
	while( i < NTH_BLOCK_BUFFER_SIZE && found == 0) 
	{
		if(nth_blk_buf[i].from_blk_no != -1)
		{
			j = 0;
			while( j < NTH_BLOCK_IN_BLOCK && found == 0)
			{
				if( nth_blk_buf[i].nth_blk[j].nth_bucket == -1)
				{
					nth_blk_buf[i].nth_blk[j].nth_bucket = nth_bucket;
					nth_blk_buf[i].nth_blk[j].blk_no = bucket_no;
					nth_blk_buf[i].change_flag = 1;
					found = 1;
				}
				j++;
			}
		}
		i++;
	}
	
	j = 0;
	i = 0;
	if(found == 0)//在读入缓冲的nth_blk文件块中没有找到可以加入对应信息的地方，必须读入新的对应信息块
	{
		while(j < NTH_BLOCK_BUFFER_SIZE && found == 0)
		{
			if(nth_blk_buf[j].change_flag == 1)
			{
				nth_blk_relation = nth_blk_buf[j];
				write_nth_blk("nth_block.dat", nth_blk_relation.from_blk_no);
				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++;
					while( i < NTH_BLOCK_IN_BLOCK && found ==0 )
					{
						if(nth_blk_buf[j].nth_blk[i].nth_bucket == -1)
						{
							nth_blk_buf[j].nth_blk[i].nth_bucket = nth_bucket;
							nth_blk_buf[j].nth_blk[i].blk_no = bucket_no;
							nth_blk_buf[j].change_flag = 1;
							found = 1;
						}
						i++;
					}
				}
				else
				{
					fp = fopen("nth_block.dat", "rb+");
					get_blk(fp);
					fclose(fp);
					read_nth_blk("nth_block.dat", NTH_BLK_CUR);
					nth_blk_buf[j] = nth_blk_relation;
					NTH_BLK_CUR = 0;
					while( i < NTH_BLOCK_IN_BLOCK && found == 0 )
					{
						if(nth_blk_buf[j].nth_blk[i].nth_bucket == -1)
						{
							nth_blk_buf[j].nth_blk[i].nth_bucket = nth_bucket;
							nth_blk_buf[j].nth_blk[i].blk_no = bucket_no;
							nth_blk_buf[j].change_flag = 1;
							found = 1;
						}
						i++;
					}
				}
			}
			j++;
		}
	}
}
					
void renew_hash_info(long data_volume)
{
	long i = 0;
	hash_info.rcd_no += data_volume;
	i = (long)((float)hash_info.rcd_no/((float)HASH_SPACE*SATURATION_DEGREE)) + 1;
	if( i > hash_info.bucket_no)
		hash_info.bucket_no = i;
	hash_info.hkey_i = renew_hash_info_hkey_i(hash_info.bucket_no);
}

long renew_hash_info_hkey_i(long x)
{
     long i = 0;
	 long j = 0;
	 long k = 0;
     while(1)
     {
		 j = pow(2, i);
		 k = 2 * j;
		if(j <= x && k > x)
		{
			i++;
			break;
		}          
		else
		i++;
     }
     i--;
     if(j == x)
		 return i;
     else
		 return i+1;
}