btree.c

基于btree索引算法的数据库代码

			{
				/* 记录合并后的下一个空闲块的索引 */
				unsigned int cur_free_next = 0;

				get_2byte(&wb[cur_free + BTREE_FREE_BLOCK_SZ_OFFSET], sizeof(unsigned short), next_sz);
				total_sz += next_sz;

				get_2byte(&wb[cur_free + BTREE_FREE_BLOCK_NEXT_OFFSET], sizeof(unsigned short), cur_free_next);
				put_2byte(cur_free_next, &wb[pre_free_store + BTREE_FREE_BLOCK_NEXT_OFFSET], sizeof(unsigned short));
			}

			put_2byte(total_sz, &wb[pre_free_store + BTREE_FREE_BLOCK_SZ_OFFSET], sizeof(unsigned short));

			goto btree_mgr_free_space_end_;
		}
		else
		{
			/* 前一块空闲内存next指向ptr */
			put_2byte(ptr, &wb[pre_free_store + BTREE_FREE_BLOCK_NEXT_OFFSET], BTREE_CELL_PTR_SIZE);
		}
	}
	else
	{
		put_2byte(ptr, &wb[BTREE_HDR_FIRST_FREE_OFFSET], BTREE_CELL_PTR_SIZE);
	}

	if(ptr + sz == cur_free)
	{
		/* 如果可以与下一个空闲块合并 */
		unsigned int cur_next = 0;
		get_2byte(&wb[cur_free + BTREE_FREE_BLOCK_SZ_OFFSET], sizeof(unsigned short), next_sz);
		get_2byte(&wb[cur_free + BTREE_FREE_BLOCK_NEXT_OFFSET], BTREE_CELL_PTR_SIZE, cur_next);
		
		/* 填入下块空闲块,本空闲块的大小 */
		put_2byte(cur_next, &wb[ptr + BTREE_FREE_BLOCK_NEXT_OFFSET], BTREE_CELL_PTR_SIZE);
		put_2byte(sz + next_sz, &wb[ptr + BTREE_FREE_BLOCK_SZ_OFFSET], sizeof(unsigned short));
	}
	else
	{
		/* 不能合并,则ptr的next域指向cur_free, 填入本空闲块的大小 */
		put_2byte(cur_free, &wb[ptr + BTREE_FREE_BLOCK_NEXT_OFFSET], BTREE_CELL_PTR_SIZE);
		put_2byte(sz, &wb[ptr + BTREE_FREE_BLOCK_SZ_OFFSET], sizeof(unsigned short));
	}

btree_mgr_free_space_end_:

#ifdef _DEBUG
memset(&wb[ptr] + BTREE_FREE_BLOCK_MIN_SZ, 0, sz - BTREE_FREE_BLOCK_MIN_SZ);
#endif

	node->nfree += btree_mgr_cal_cell_real_fill_sz(sz);

	assert(node->nfree <= node->btree_mgr->pg_sz - BTREE_CELL_PTR_OFFSET);

	return 0;
}

/**
 * @brief 将一个node所存储的cell置成空
 */
static __INLINE__ int btree_mgr_clear_node(btree_node * node)
{
	/* 将frag置成0,将ncell置成0,将content置到底部,将first free置成零 */
	/* right most置成0 */

	unsigned char * wb = NULL;

	assert(node && node->btree_mgr);

	wb = PageHeadMakeWritable(node->pg);
	if(NULL == wb)
		return -1;

	node->ncell = 0;
	node->nfree = node->btree_mgr->pg_sz - BTREE_CELL_PTR_OFFSET;
	node->idx_changed = 1;
	
	memset(wb, 0, node->btree_mgr->pg_sz);

	wb[BTREE_HDR_NODEFLAG_OFFSET] = node->node_flag;

	btree_mgr_clear_ovfl(node);

	return 0;
}

/**
 * @brief 在页缓存内分配指定大小的存储空间,返回的时空间距离用户页缓存可用地址起始的偏移
 */
static __INLINE__ unsigned int btree_mgr_alloc_space(btree_node * node, unsigned int sz)
{
	/*
	* btree page head define
	*   OFFSET   SIZE     DESCRIPTION
	*      0       1      Flags. 1: intkey, 2: hasdata, 4: leaf
	*      1       1      记录碎片的大小
	*      2       2      byte offset to the first freeblock
	*      4       2      number of cells on this page
	*      6       2      first byte of the cell content area
	*      8       4      Right child (the Ptr(N+1) value).  reserve on leaves.
	*/

	/*
	* 页内空闲块定义
	*    SIZE    DESCRIPTION
	*      2     Byte offset of the next freeblock
	*      2     Bytes in this freeblock
	*/

	unsigned int free_idx = 0;
	unsigned int pc_prev = 0;
	unsigned int block_sz = 0;
	unsigned int ret_alloc = 0;
	unsigned int ret_idx = 0;

	/* cell"指针"的结束 */
	unsigned int cell_ptr_end = 0;
	/* cell content的起始 */
	unsigned int cell_content = 0;
	unsigned char * write_buf = NULL;

	assert(node && sz);
	assert(node->nfree >= sz + BTREE_CELL_PTR_SIZE);
	assert(0 == node->has_cell_ovfl);
	assert(node->read_buf == PageHeadMakeReadable(node->pg));

	write_buf = PageHeadMakeWritable(node->pg);
	if(NULL == write_buf)
		return 0;

	/*
	* 如果存在空间块,则从空间链表里搜索
	* 如果不存在空闲块,则从cell指针数组的未尾与 cell content之间的那段区域获取(以下简称gap)
	* 如果仍然获取不到,则应合并空闲碎片,
	* 从gap里分配需要的存储空间
	*/

	/* 至gap里分配,如果仍然分配不到,此时就需要进行空闲碎片整理 */
	cell_ptr_end = BTREE_CELL_PTR_OFFSET + BTREE_CELL_PTR_SIZE * node->ncell;
	get_2byte(&(write_buf[BTREE_HDR_FIRST_CONTENT]), BTREE_CELL_PTR_SIZE, cell_content);

	/* cell_content为0,说明是一个新的节点 */
	if(0 == cell_content)
		cell_content = node->btree_mgr->pg_sz;

	assert(cell_content >= cell_ptr_end);

	/* 为cell ptr数组的增长预留字节 */
	if((cell_content - cell_ptr_end) < BTREE_CELL_PTR_SIZE)
	{
		if(0 != btree_mgr_defrag_node(node))
			return 0;

		get_2byte(&(write_buf[BTREE_HDR_FIRST_CONTENT]), BTREE_CELL_PTR_SIZE, cell_content);
	}
	else
	{
		get_2byte(&write_buf[BTREE_HDR_FIRST_FREE_OFFSET], sizeof(unsigned short), free_idx);
		pc_prev = (unsigned int)BTREE_HDR_FIRST_FREE_OFFSET;

		assert(((cell_content < node->btree_mgr->pg_sz) && free_idx) || free_idx == 0);

		/* 如果空闲碎片小于BTREE_MAX_FRAG */
		if(write_buf[BTREE_HDR_NFRAG_OFFSET] < BTREE_MAX_FRAG)
		{
			while(free_idx)
			{
				get_2byte(&(write_buf[free_idx + BTREE_FREE_BLOCK_SZ_OFFSET]),
					sizeof(unsigned short),
					block_sz);

				assert(block_sz >= BTREE_FREE_BLOCK_MIN_SZ);

				if(block_sz >= sz)
				{
					if(block_sz < sz + BTREE_FREE_BLOCK_MIN_SZ)
					{
						/*
						* 如果剩余的内存不足4字节,无法形成一个空闲块"链表"节点
						* 则整个空闲块都分配出去,但空闲空间却只扣减相应的sz值,并相应增加nfrag的值
						* 当空闲碎片达到上限,此时进行碎片整理,释放出所有的空闲碎片,供分配使用
						*/
						memcpy(&(write_buf[pc_prev]), 
							&(write_buf[free_idx + BTREE_FREE_BLOCK_NEXT_OFFSET]),
							sizeof(unsigned short));

						assert((block_sz - sz) <= BTREE_FREE_BLOCK_MIN_SZ);

						assert(write_buf[BTREE_HDR_NFRAG_OFFSET] <= BTREE_MAX_FRAG);

						write_buf[BTREE_HDR_NFRAG_OFFSET] += (block_sz - sz);
					}
					else
					{
						/* 扣减相应的sz,返回 */
						put_2byte(block_sz - sz,
							&(write_buf[free_idx + BTREE_FREE_BLOCK_SZ_OFFSET]),
							sizeof(unsigned short));
					}

					/* 从空闲块的底部拿出一块来 */
					ret_idx = free_idx + block_sz - sz;
					goto btree_mgr_alloc_space_end_;
				}

				/* 循环继续 */
				pc_prev = free_idx + BTREE_FREE_BLOCK_NEXT_OFFSET;
				get_2byte(&(write_buf[free_idx + BTREE_FREE_BLOCK_NEXT_OFFSET]),
					sizeof(unsigned short),
					free_idx);
			}
		}
		else
		{
			/* 碎片超过上限了,进行碎片整理 */
			if(0 != btree_mgr_defrag_node(node))
				return 0;

			get_2byte(&(write_buf[BTREE_HDR_FIRST_CONTENT]), BTREE_CELL_PTR_SIZE, cell_content);
		}

		/* 如果仍然分配不到,需要进行空闲碎片整理 */
		if((cell_content - cell_ptr_end) < btree_mgr_cal_cell_real_fill_sz(sz))
		{
			if(0 != btree_mgr_defrag_node(node))
				return 0;

			get_2byte(&(write_buf[BTREE_HDR_FIRST_CONTENT]), BTREE_CELL_PTR_SIZE, cell_content);
		}
	}

	assert((cell_content - cell_ptr_end) >= btree_mgr_cal_cell_real_fill_sz(sz));

	ret_idx = cell_content - sz;
	put_2byte(ret_idx, &(write_buf[BTREE_HDR_FIRST_CONTENT]), BTREE_CELL_PTR_SIZE);

btree_mgr_alloc_space_end_:

	node->nfree -= btree_mgr_cal_cell_real_fill_sz(sz);
	return ret_idx;
}

/**
 * @brief 将一个cell吃进来
 */
static __INLINE__ int btree_mgr_eat_cell(btree_node * node,
										 unsigned int idx,
										 unsigned char * cell, unsigned int cell_sz)
{
	unsigned int ptr = 0;
	unsigned char * wb = NULL;
	unsigned int i = 0;
	unsigned int end = 0;
	unsigned int ins = 0;
	unsigned char * p = NULL;

	assert(node && cell && cell_sz);
	assert(idx <= node->ncell);
	assert(node->nfree >= (cell_sz + BTREE_CELL_PTR_SIZE));

	/* 空间足够,分配空间,存储 */
	ptr = btree_mgr_alloc_space(node, cell_sz);
	if(0 == ptr)
		return -1;

	wb = PageHeadMakeWritable(node->pg);
	if(NULL == wb)
		return -1;

	/* 存储cell内容 */
	memcpy(&wb[ptr], cell, cell_sz);

	/* 更改cell ptr数组 */
	end = BTREE_CELL_PTR_OFFSET + node->ncell * BTREE_CELL_PTR_SIZE;
	ins = BTREE_CELL_PTR_OFFSET + idx * BTREE_CELL_PTR_SIZE;
	for(i = end; i > ins; i -= BTREE_CELL_PTR_SIZE)
	{
		wb[i] = wb[i - 2];
		wb[i + 1] = wb[i - 1];
	}

	put_2byte(ptr, &wb[ins], BTREE_HDR_NCELL_SZ);

	/* 更改标识位idx_change */
	node->idx_changed = 1;

	return 0;
}

/**
 * @brief 将一个打包好的cell添加到指定的位置
 */
static __INLINE__ int btree_mgr_insert_cell(btree_node * node,
											unsigned int idx,
											unsigned char * cell, unsigned int cell_sz)
{
	/*
	* 如果该节点使用的页上的存储空间足够,
	* 则将新的cell拷进去
	* 如果不够,就挂在附加空间上,在之后的平衡过程里再拷贝进去
	*/

	unsigned char * wb = NULL;

	assert(node && cell && cell_sz);
	assert(0 == node->has_cell_ovfl);
	assert(idx <= node->ncell);

	wb = PageHeadMakeWritable(node->pg);
	if(NULL == wb)
		return -1;

	/* 空间不够,挂在cell_ovfl信息里,待balance函数之后再转存至正常的页缓存里 */
	if(node->nfree < (cell_sz + BTREE_CELL_PTR_SIZE))
	{
		if(NULL == node->cell_ovfl.cell_buf)
			node->cell_ovfl.cell_buf = MyBufferConstruct(node->btree_mgr->hm, cell_sz);

		MyBufferSet(node->cell_ovfl.cell_buf, cell, cell_sz);
		node->cell_ovfl.idx = idx;
		node->has_cell_ovfl = 1;

		/* 更改标识位idx_change */
		node->idx_changed = 1;

		assert(node->cell_ovfl.idx <= node->ncell);

		goto btree_mgr_insert_cell_end_;
	}

	if(0 != btree_mgr_eat_cell(node, idx, cell, cell_sz))
		return -1;

btree_mgr_insert_cell_end_:

	/* 更新ncell的值+1 */
	node->ncell += 1;
	put_2byte(node->ncell, &wb[BTREE_HDR_NCELL_OFFSET], BTREE_HDR_NCELL_SZ);

	return 0;
}

/**
 * @brief 将溢出的cell去除,ncell要减1
 */
static __INLINE__ int btree_mgr_throwup_cell_ovfl(btree_node * node)
{
	unsigned char * wb = NULL;

	assert(node->has_cell_ovfl && node->cell_ovfl.cell_buf);
	assert(node && node->ncell);

	wb = PageHeadMakeWritable(node->pg);
	if(NULL == wb)
		return -1;

	btree_mgr_clear_ovfl(node);

	node->ncell -= 1;
	put_2byte(node->ncell, &wb[BTREE_HDR_NCELL_OFFSET], BTREE_HDR_NCELL_SZ);

	return 0;
}

/**
 * @brief 将溢出的cell吃回来
 */
static __INLINE__ int btree_mgr_eat_cell_ovfl(btree_node * node)
{
	unsigned char * cell = NULL;
	unsigned int cell_sz = 0;
	HMYBUFFER hbuf = NULL;
	int ret = 0;

	assert(node);
	assert(node->has_cell_ovfl && node->cell_ovfl.cell_buf);

	hbuf = MyBufferConstruct(node->btree_mgr->hm, 0);

	MyBufferRef(node->cell_ovfl.cell_buf, hbuf);
	btree_mgr_clear_ovfl(node);

	cell = MyBufferGet(hbuf, &cell_sz);

	ret = btree_mgr_eat_cell(node, node->cell_ovfl.idx, cell, cell_sz);

	MyBufferDestruct(hbuf);

	return ret;
}

/**
 * @brief 从节点中删除一个cell
 */
static __INLINE__ int btree_mgr_drop_cell(btree_node * node, unsigned int idx, btree_cellinfo * cell_info)
{
	unsigned int cell_ptr = 0;
	unsigned int cell_sz = 0;
	unsigned char * wb = NULL;
	unsigned int ncell_in = 0;

	assert(node && idx < node->ncell);

	wb = PageHeadMakeWritable(node->pg);
	if(NULL == wb)
		return -1;

	btree_mgr_find_cellptr(node, idx, cell_ptr);

	if(NULL == cell_info)
	{
		btree_cellinfo temp_cell_info;
		btree_mgr_parse_cellptr(node, cell_ptr, &temp_cell_info);
		cell_sz = temp_cell_info.cell_sz;
	}
	else
	{

#ifdef _DEBUG
btree_cellinfo temp_cellinfo;
btree_mgr_parse_idx(node, idx, &temp_cellinfo);
assert(0 == memcmp(&temp_cellinfo, cell_info, sizeof(temp_cellinfo)));
#endif

		assert(PageHeadMakeReadable(node->pg) == node->read_buf);
		assert((cell_info->cell - node->read_buf) == cell_ptr);
		cell_sz = cell_info->cell_sz;
	}

	/* ncell计数减1,并调整cell ptr数组,idx change标识置1 */
	if(0 != btree_mgr_free_space(node, cell_ptr, cell_sz))
		return -1;

	if(node->has_cell_ovfl)
		ncell_in = node->ncell - 1;
	else
		ncell_in = node->ncell;

	/* 将后继的ptr往前整 */
	if(idx < ncell_in - 1)
	{
		unsigned int i;
		unsigned char * ptr;

		ptr = &wb[BTREE_CELL_PTR_OFFSET + idx * BTREE_CELL_PTR_SIZE];
		for(i = 0; i < ncell_in - idx - 1; i ++)
		{
			ptr[i * BTREE_CELL_PTR_SIZE] = ptr[i * BTREE_CELL_PTR_SIZE + 2];
			ptr[i * BTREE_CELL_PTR_SIZE + 1] = ptr[i * BTREE_CELL_PTR_SIZE + 3];
		}
	}

	/* ncell计数减1 */
	node->ncell -= 1;
	put_2byte(node->ncell, &wb[BTREE_HDR_NCELL_OFFSET], BTREE_HDR_NCELL_SZ);

	/* idx change标识置1 */
	node->idx_changed = 1;

	return 0;
}

/**
 * @brief 从节点中删除一条记录,放弃本节点的cell,以及后继的ovfl页(如果有)
 */
static __INLINE__ int btree_mgr_delete_record(btree_node * node, unsigned int idx, btree_cellinfo * cell_info)
{
	unsigned int pgno_ovfl = 0;
	HPAGER hpgr = NULL;

	assert(node && idx < node->ncell);

	if(cell_info)
	{
#ifdef _DEBUG
btree_cellinfo temp_cellinfo;
btree_mgr_parse_idx(node, idx, &temp_cellinfo);
assert(0 == memcmp(&temp_cellinfo, cell_info, sizeof(temp_cellinfo)));
#endif
		pgno_ovfl = cell_info->overflow_pgno;

		if(0 != btree_mgr_drop_cell(node, idx, cell_info))
			return -1;

		assert(((cell_info->data_sz + cell_info->key_sz * ((no