btree.c

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

	}

	/* 打包key_sz */
	uint_to_big_endian(key_sz, cell, sizeof(unsigned int));
	cell += sizeof(sizeof(unsigned int));
	assert((unsigned int)(cell - cell_info->cell) <= cell_sz);

	if(!(node->node_flag & e_btree_page_flag_intkey))
	{
		pSrc = (unsigned char *)key;
		Src_sz = key_sz;
	}
	else if(node->node_flag & e_btree_page_flag_hasdata)
	{
		pSrc = (unsigned char *)data;
		Src_sz = data_sz;
	}
	else
	{
		assert(0 == cell_info->payload_sz);
		assert((unsigned int)(cell - cell_info->cell) == cell_sz);

		/* 打包结束 */
		return 0;
	}

	payload_sz = cell_info->payload_sz;
	if(payload_sz > node->btree_mgr->max_local)
	{
		assert(cell_info->local_sz < payload_sz);

		/* 如果有溢出,为首个溢出页的页号预留存储空间 */
		pPrior = cell;
		pPayload = cell + sizeof(unsigned int);
	}
	else
		pPayload = cell;

	/* 开始接受payload空间剩余为local_sz */
	space_left = cell_info->local_sz;
	btree_mgr = node->btree_mgr;
	assert(btree_mgr);

	/* 拷贝key(如果需要)与data(如果需要)到pPayload指向的存储空间 */
	while(payload_sz)
	{
		unsigned int n = 0;
		if(0 == space_left)
		{
			/* 如果空间不够,分配一页over flow */
			unsigned int pgno = PagerGetPageNo(btree_mgr->hpgr);
			if(0 == pgno)
			{
				ret = -1;
				goto btree_mgr_pack_cell_end_;/* 取消对某些节点的引用 */
			}

			if(pg_ovfl)
				PagerReleasePage(pg_ovfl);

			pg_ovfl = PagerGetPage(btree_mgr->hpgr, pgno);
			if(NULL == pg_ovfl)
			{
				ret = -1;
				PagerReleasePageNo(btree_mgr->hpgr, pgno);
				goto btree_mgr_pack_cell_end_;
			}

			pPayload = (unsigned char *)PageHeadMakeWritable(pg_ovfl);
			if(NULL == pPayload)
			{
				ret = -1;
				PagerReleasePageNo(btree_mgr->hpgr, pgno);
				goto btree_mgr_pack_cell_end_;
			}

			assert(pPrior);
			/* 将溢出页号写入预留的内存空间 */
			uint_to_big_endian(pgno, pPrior, sizeof(unsigned int));
			pPrior = pPayload;

			pPayload += BTREE_OVERFLOW_HDR_SZ;

			space_left = btree_mgr->pg_sz - BTREE_OVERFLOW_HDR_SZ;
		}

		if(Src_sz > space_left)
			n = space_left;
		else
			n = Src_sz;

		memcpy(pPayload, pSrc, n);

		space_left -= n;
		pPayload += n;

		Src_sz -= n;
		pSrc += n;

		payload_sz -= n;

		if(0 == Src_sz && payload_sz)
		{
			Src_sz = data_sz;
			pSrc = (unsigned char *)data;
		}
	}

btree_mgr_pack_cell_end_:

	if(pg_ovfl)
		PagerReleasePage(pg_ovfl);

	if(pPrior)
	{
		assert(pPrior != cell);
		uint_to_big_endian(0, pPrior, sizeof(unsigned int));
	}

	return ret;	
}

/**
 * @brief 游标当前所指的位置的cell信息
 */
static __INLINE__ int btree_mgr_get_cell(btree_cursor * cursor, btree_cellinfo * cellinfo)
{
	assert(cursor && cursor->cur_node && cursor->root_pgno && cellinfo);
	assert(cursor->cur_node->pg && cursor->cur_node->pg_no);

	/* 取出cell"指针" */
	/* 根据cell"指针"取出cell的内容 */
	btree_mgr_parse_idx(cursor->cur_node, cursor->idx, cellinfo);

	return 0;
}

/**
 * @brief 查找cell的回调函数
 *  > 0  表示 key 大于 data
 *  == 0 表示 key 等于 data
 *  < 0  表示 key 小于 data
 *
 * @param key:关键字
 * @param key_sz:关键字的缓冲区大小
 * @param context:用户自定义的上下文数据
 * @param context_sz:用户自定义的上下文数据的长度
 */
static int binarysearch_compare(const void * key, unsigned int key_sz,
								const void * data,
								const void * context, unsigned int context_sz)
{
	unsigned char * cell_key = NULL;

	btree_cursor * cursor = (btree_cursor *)context;
	unsigned int cell_ptr = 0;
	btree_cellinfo cell_info;

	assert(cursor && context_sz == sizeof(*cursor));
	assert(PagePtrIsInpage(cursor->cur_node->pg, data));

	get_2byte((unsigned char *)data, BTREE_CELL_PTR_SIZE, cell_ptr);

	btree_mgr_parse_cellptr(cursor->cur_node, cell_ptr, &cell_info);

	if(cursor->cur_node->node_flag & e_btree_page_flag_intkey)
	{
		btree_mgr_cell_get_key(cursor->cur_node, &cell_info, NULL, 0);

		return cursor->key_cmp(key, key_sz,
			NULL, cell_info.key_sz,
			cursor->context, cursor->context_sz);
	}
	else
	{
		int ret = 0;
		cell_key = MyMemPoolMalloc(cursor->btree_mgr->hm, cell_info.key_sz);
		if(0 != btree_mgr_cell_get_key(cursor->cur_node, &cell_info, cell_key, cell_info.key_sz))
		{
			cursor->err = -1;
			ret = 0;
		}
		else
		{
			ret = cursor->key_cmp(key, key_sz, 
				cell_key, cursor->cell_info.key_sz,
				cursor->context, cursor->context_sz);
		}

		MyMemPoolFree(cursor->btree_mgr->hm, cell_key);

		return ret;
	}
}

/**
 * @brief 获取right most
 */
#define btree_mgr_get_rmost(_n, _rm) do{\
		assert(_n);\
		assert(!(_n->node_flag & e_btree_page_flag_leaf));\
		assert(_n->read_buf == PageHeadMakeReadable(_n->pg));\
		array_to_uint_as_big_endian(&_n->read_buf[BTREE_HDR_MOST_RIGHT_CHILD_OFFSET], sizeof(unsigned int), _rm);\
		assert(_rm);\
	}while(0)

/**
 * @brief 查找关键值
 * @param pres:0表示找到了关键字
 *         大于零:表示没找到关键字
 *         小于零:表示没找到关键字
 *         如果 序列为 1 3 4 查找 2 
 */
static __INLINE__ int btree_mgr_search(btree_cursor * cursor, const void * key, const unsigned int key_sz, int * pres)
{
	int ret = 0;
	unsigned int pgno_child = 0;
	btree_mgr_t * btree_mgr = NULL;
	btree_node * sub_node = NULL;
	btree_cellinfo cell_info;

	assert(cursor && cursor->btree_mgr && cursor->cur_node);
	assert(cursor->cur_node->btree_mgr == cursor->btree_mgr);
	assert(pres);

	btree_mgr = cursor->btree_mgr;

	/* 将游标移至根节点 */
	if(0 != btree_mgr_move_to_root(cursor))
		return -1;

	assert(cursor->cur_node->init_flag);
	assert(cursor->cur_node->pg_no == cursor->root_pgno);

	while(1)
	{
		/* 在当前节点里做二分查找 */
		const unsigned char * rbuf = cursor->cur_node->read_buf;

		assert(PagePtrIsInpage(cursor->cur_node->pg, &rbuf[BTREE_CELL_PTR_OFFSET]));
		assert(PagePtrIsInpage(cursor->cur_node->pg, 
			rbuf + BTREE_CELL_PTR_OFFSET + cursor->cur_node->ncell * BTREE_CELL_PTR_SIZE - 1));

		if(0 == cursor->cur_node->ncell)
		{
			/* 如果没有cell,直接返回即可 */
			assert(NULL == cursor->cur_node->parent);
			assert(cursor->cur_node->node_flag & e_btree_page_flag_leaf);

			*pres = 1;
			return 0;
		}

		/* 如果找到,返回 */
		ret = MyBinarySearch(&rbuf[BTREE_CELL_PTR_OFFSET], cursor->cur_node->ncell, BTREE_CELL_PTR_SIZE,
			key, key_sz, binarysearch_compare,
			&cursor->idx, cursor, sizeof(*cursor));

		if(0 != cursor->err)
		{
			/* 如果出错 */
			cursor->err = 0;
			return -1;
		}

		if(0 == ret)
		{
			/* 如果找到 */
			*pres = 0;
			return 0;
		}

		if(cursor->cur_node->node_flag & e_btree_page_flag_leaf)
		{
			/* 如果当前已经是叶节点,则返回 */
			*pres = ret;
			return 0;
		}

		/* 根据"指针"去取cell信息 */
		if(cursor->idx < cursor->cur_node->ncell)
		{
			btree_mgr_get_cell(cursor, &cell_info);
			pgno_child = cell_info.lchild_pgno;
		}
		else
			btree_mgr_get_rmost(cursor->cur_node, pgno_child);

		assert(pgno_child);

		/* 找不到,进入相应的子分支继续查找 */
		sub_node = btree_mgr_get_node(cursor->btree_mgr,
			pgno_child,
			cursor->cur_node,
			cursor->idx);

		assert(sub_node->parent == cursor->cur_node);

		if(NULL == sub_node)
			return -1;

		btree_mgr_release_node(cursor->cur_node);
		cursor->cur_node = sub_node;

		assert(PagerGetPageRefCount(cursor->cur_node->pg) && PagerGetPageRefCount(cursor->cur_node->parent->pg));
	}

	*pres = ret;
	return 0;
}

/**
 * @brief 整理某一个节点的空闲碎片
 */
static __INLINE__ int btree_mgr_defrag_node(btree_node * node)
{
	/* 记录备份的content存储区域的指针 */
	unsigned char * content_new = NULL;
	unsigned int new_cell_ptr = 0;
	/* 记录整理碎片前的content起始 */
	unsigned int content_begin = 0;
	/* 在回拷过程中的临时变量,记录cell的"指针" */
	unsigned int cell_ptr = 0;
	/* 临时存储某个cell的信息 */
	btree_cellinfo cell_info;

	unsigned char * write_buf = NULL;
	unsigned int i = 0;

	assert(node);

	/*
	* 将节点内的cell content备份起来
	* 轮循cell ptr数组,将里头的内容顺次解析拷贝.
	* 重置相应的值first_free,cell_content,nfrag
	*/

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

	get_2byte(&(write_buf[BTREE_HDR_FIRST_CONTENT]), BTREE_CELL_PTR_SIZE, content_begin);

	content_new = MyMemPoolMalloc(node->btree_mgr->hm, node->btree_mgr->pg_sz);
	if(NULL == content_new)
		return -1;

	/* 开始循环 */
	content_new += node->btree_mgr->pg_sz;
	new_cell_ptr = node->btree_mgr->pg_sz;
	for(i = 0; i < node->ncell; i ++)
	{
		btree_mgr_find_cellptr(node, i, cell_ptr);
		assert(cell_ptr);

		/* 解析相应的cell信息 */
		btree_mgr_parse_cellptr(node,cell_ptr, &cell_info);

		assert(new_cell_ptr > (BTREE_CELL_PTR_OFFSET + node->ncell * BTREE_CELL_PTR_SIZE + node->nfree));

		/* 拷贝回节点页缓存 */
		content_new -= cell_info.cell_sz;
		new_cell_ptr -= cell_info.cell_sz;

		assert(new_cell_ptr);
		assert(cell_ptr >= content_begin);

		memcpy(content_new, &write_buf[cell_ptr], cell_info.cell_sz);

		/* 更新相应的cell ptr */
		put_2byte(new_cell_ptr, &write_buf[BTREE_CELL_PTR_OFFSET + i * BTREE_CELL_PTR_SIZE], BTREE_CELL_PTR_SIZE);
	}

	content_begin = new_cell_ptr;

	/* 所有的free空间应都集中在gap里 */
	assert((content_begin - node->nfree) == BTREE_CELL_PTR_OFFSET + node->ncell * BTREE_CELL_PTR_SIZE);
	assert(content_begin <= node->btree_mgr->pg_sz);

	memcpy(&write_buf[content_begin], content_new, node->btree_mgr->pg_sz - content_begin);

	/*
	* 重置相应的值first_free,cell_content,nfrag
	* 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.
	*/
	write_buf[BTREE_HDR_NFRAG_OFFSET] = 0;
	put_2byte(0, &write_buf[BTREE_HDR_FIRST_FREE_OFFSET], BTREE_CELL_PTR_SIZE);
	put_2byte(content_begin,
		&write_buf[BTREE_HDR_FIRST_CONTENT],
		BTREE_CELL_PTR_SIZE);

	assert(content_new);
	MyMemPoolFree(node->btree_mgr->hm, content_new - content_begin);

	return 0;
}

/**
 * @brief 当指定偏移的页内存储空间归还,与btree_mgr_alloc_space是对偶操作
 */
static __INLINE__ int btree_mgr_free_space(btree_node * node, unsigned int ptr, const unsigned int sz)
{
	/*
	* 如果ptr恰好紧跟在gap之后,则不需要加入free"链表",
	* 顺着链表前进,直到链表时的free_ptr大于ptr为止,将ptr加入链表,此时要注意判断是否可以合差相邻的合闲块
	* 更新nfree值,
	* 根据需要更新first content与first free
	*/
	unsigned int content = 0;
	unsigned int cur_free = 0;
	unsigned int pre_free_store = 0;
	unsigned int next_sz = 0;
	unsigned char * wb = PageHeadMakeWritable(node->pg);

	assert(node && ptr && sz);

	if(NULL == wb)
		return -1;

	get_2byte(&wb[BTREE_HDR_FIRST_CONTENT], BTREE_CELL_PTR_SIZE, content);

	/* 如果ptr紧挨着content,则将它并入content */
	if(ptr == content)
	{
		content = ptr + sz;

		/* 看看是否还可以合并更多的合闲块 */
		get_2byte(&wb[BTREE_HDR_FIRST_FREE_OFFSET], BTREE_CELL_PTR_SIZE, cur_free);
		while(cur_free)
		{
			unsigned int temp;
			unsigned int temp_sz;
			if(content != cur_free)
				break;

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

			get_2byte(&wb[cur_free + BTREE_FREE_BLOCK_NEXT_OFFSET], sizeof(unsigned short), temp);
			cur_free = temp;
		}

		put_2byte(content, &wb[BTREE_HDR_FIRST_CONTENT], BTREE_CELL_PTR_SIZE);
		put_2byte(cur_free, &wb[BTREE_HDR_FIRST_FREE_OFFSET], BTREE_CELL_PTR_SIZE);

		goto btree_mgr_free_space_end_;
	}

	get_2byte(&wb[BTREE_HDR_FIRST_FREE_OFFSET], BTREE_CELL_PTR_SIZE, cur_free);

	/* 寻找ptr应加入的位置 */
	pre_free_store = 0;
	while(cur_free)
	{
		unsigned int temp;
		if(cur_free > ptr)
			break;

		pre_free_store = cur_free + BTREE_FREE_BLOCK_NEXT_OFFSET;
		get_2byte(&wb[cur_free + BTREE_FREE_BLOCK_NEXT_OFFSET], BTREE_CELL_PTR_SIZE, temp);

		cur_free = temp;
	}

	/* 将ptr加入"链表" */
	if(pre_free_store)
	{
		unsigned int pre_sz = 0;
		unsigned int total_sz = 0;
		get_2byte(&wb[pre_free_store + BTREE_FREE_BLOCK_SZ_OFFSET], sizeof(unsigned short), pre_sz);

		if(pre_free_store + pre_sz == ptr)
		{
			/* 可以与前一块合并 */
			total_sz = pre_sz + sz;

			/* 是否可以三块都合并 */
			if(ptr + sz == cur_free && cur_free)