btree.c

sourceforge历史版本完整下载: http://sourceforge.net/project/showfiles.php?group_id=202044 提供了基于b树索引算法的文件数据数据

			btree_mgr_ref_node(parent);

			node->parent = parent;
		}

		node->idx_in_parent_cellarray = idx_in_parent;
	}
	else
	{
		assert(!(node->node_flag & e_btree_page_flag_leaf) || NULL == node->parent);

		if(node->parent)
			btree_mgr_release_node(node->parent);

		node->idx_in_parent_cellarray = 0;
		node->parent = NULL;
	}

	assert(PageHeadGetUserDataSize(pg) == sizeof(*node));

	/* 如果已经初始化过了,不用再做这些操作 */
	if(node->init_flag)
		return node;

	node->pg = pg;
	node->pg_no = pgno;

	node->read_buf = (unsigned char *)PageHeadMakeReadable(pg);
	node->btree_mgr = btree_mgr;

	assert(node->read_buf);
	assert(PagePtrIsInpage(node->pg, node->read_buf));

	btree_mgr_init_node(node, b_new);

	node->init_flag = 1;

	return node;
}

/**
 * @brief 获取一个节点
 */
#define btree_mgr_get_node_new(__btr_mgr, __pgno, __parent, __idx_in_parent) \
	btree_mgr_get_node_aux(__btr_mgr, __pgno, __parent, __idx_in_parent, 0, 1)

/**
 * @brief 获取一个节点
 */
#define btree_mgr_get_node(__btr_mgr, __pgno, __parent, __idx_in_parent) \
	btree_mgr_get_node_aux(__btr_mgr, __pgno, __parent, __idx_in_parent, 0, 0)

/**
 * @brief 获取一个缓存中节点,不在缓存中,则失败返回
 */
#define btree_mgr_get_cached_node(__btr_mgr, __pgno, __parent, __idx_in_parent) \
	btree_mgr_get_node_aux(__btr_mgr, __pgno, __parent, __idx_in_parent, 1, 0)

/**
 * @brief 销毁一个节点,对这个节点的承载页引用计数减少1
 */
static __INLINE__ int btree_mgr_delete_node(btree_node * node)
{
	unsigned int pgno = 0;
	assert(node && node->pg_no);
	assert(node->btree_mgr && node->btree_mgr->hpgr);

	pgno = node->pg_no;
	btree_mgr_release_node(node);

	if(0 != PagerReleasePageNo(node->btree_mgr->hpgr, pgno))
		return -1;

	return 0;
}

/**
 * @brief 向pager申请一页,创建一个新的节点
 */
static __INLINE__ btree_node * btree_mgr_new_node(btree_mgr_t * btree_mgr, btree_node * parent, int idx_in_parent, unsigned char node_flag)
{
	unsigned int pgno = 0;
	btree_node * node = NULL;

	assert(btree_mgr && btree_mgr->hpgr);

	pgno = PagerGetPageNo(btree_mgr->hpgr);
	if(0 == pgno)
		return NULL;

	node = btree_mgr_get_node_new(btree_mgr, pgno, parent, idx_in_parent);

	assert(btree_mgr->pg_sz - BTREE_HDR_SZ == node->nfree);
	assert(0 == node->ncell);

	if(NULL == node)
	{
		PagerReleasePageNo(btree_mgr->hpgr, pgno);
		return NULL;
	}

	if(0 != btree_mgr_set_nodeflag(node, node_flag))
	{
		btree_mgr_delete_node(node);
		return NULL;
	}

	return node;
}

/**
 * @brief 将游标加入链表
 */
static __INLINE__ int btree_mgr_add_to_cursor_list(btree_mgr_t * btree_mgr, btree_cursor * cursor)
{
	assert(btree_mgr && cursor);
	assert(btree_mgr == cursor->btree_mgr);
	assert(NULL == cursor->cursor_next && NULL == cursor->cursor_prev);

	if(NULL == btree_mgr->cursor_lst)
	{
		btree_mgr->cursor_lst = cursor;
		return 0;
	}

	cursor->cursor_next = btree_mgr->cursor_lst;
	btree_mgr->cursor_lst->cursor_prev = cursor;

	btree_mgr->cursor_lst = cursor;

	return 0;
}

/**
 * @brief 将游标从链表中脱离
 */
static __INLINE__ int btree_mgr_out_of_cursor_list(btree_mgr_t * btree_mgr, btree_cursor * cursor)
{
	assert(btree_mgr && cursor);
	assert(btree_mgr == cursor->btree_mgr);
	assert(cursor->cursor_next || cursor->cursor_prev || cursor == btree_mgr->cursor_lst);

	if(cursor == btree_mgr->cursor_lst)
		btree_mgr->cursor_lst = cursor->cursor_next;

	if(cursor->cursor_prev)
		cursor->cursor_prev->cursor_next = cursor->cursor_next;

	if(cursor->cursor_next)
		cursor->cursor_next->cursor_prev = cursor->cursor_prev;

	cursor->cursor_prev = NULL;
	cursor->cursor_next = NULL;

	return 0;
}

/**
 * @brief 创建的一个游标
 */
static __INLINE__ int btree_mgr_release_cursor(btree_cursor * cursor)
{
	assert(cursor && cursor->btree_mgr);

	if(cursor->cur_node)
		btree_mgr_release_node(cursor->cur_node);

	/* 从链表中脱离 */
	assert(cursor->cursor_next || cursor->cursor_prev || cursor == cursor->btree_mgr->cursor_lst);
	btree_mgr_out_of_cursor_list(cursor->btree_mgr, cursor);

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

	return 0;
}

/**
 * @brief 创建的一个游标
 */
static __INLINE__ btree_cursor * btree_mgr_alloc_cursor(btree_mgr_t * btree_mgr,
														XCOMPARE cmp,
														const void * context, unsigned int context_sz)
{
	btree_cursor * cursor = NULL;
	assert(btree_mgr);

	cursor = MyMemPoolMalloc(btree_mgr->hm, sizeof(*cursor));
	if(NULL == cursor)
		return NULL;

	cursor->btree_mgr = btree_mgr;

	cursor->context = (void *)context;
	cursor->context_sz = context_sz;
	cursor->key_cmp = cmp;
	assert(cursor->key_cmp);

	cursor->cursor_next = NULL;
	cursor->cursor_prev = NULL;

	cursor->root_pgno = 0;
	cursor->idx = 0;
	cursor->cur_node = NULL;

	cursor->err = 0;

	/* 加入游标链表 */
	btree_mgr_add_to_cursor_list(btree_mgr, cursor);

	return cursor;
}

/**
 * @brief 将游标移至根节点
 */
static int btree_mgr_move_to_root(btree_cursor * cursor)
{
	btree_node * root_node = NULL;

	assert(cursor && cursor->btree_mgr);
	assert(cursor->root_pgno && cursor->cur_node);

	if(cursor->root_pgno == cursor->cur_node->pg_no)
	{
		assert(NULL == cursor->cur_node->parent);
		assert(cursor->cur_node->init_flag);

		return 0;
	}

	root_node = btree_mgr_get_node(cursor->btree_mgr, cursor->root_pgno, NULL, 0);
	if(NULL == root_node)
		return -1;

	btree_mgr_release_node(cursor->cur_node);

	cursor->cur_node = root_node;

	cursor->idx = 0;

	return 0;
}

/**
 * @brief 销毁btree管理器
 */
static int btree_mgr_destroy(btree_mgr_t * btree_mgr)
{
	btree_cursor * cursor;

	assert(btree_mgr);

	/* 释放所有游标 */
	cursor = btree_mgr->cursor_lst;
	while(cursor)
	{
		btree_mgr_release_cursor(cursor);
		cursor = btree_mgr->cursor_lst;
	}

	/* 销毁pager */
	if(btree_mgr->hpgr)
		PagerDestruct(btree_mgr->hpgr);

	/* 释放自己 */
	MyMemPoolFree(btree_mgr->hm, btree_mgr);

	return 0;
}

/**
 * @brief 去除ovfl信息
 */
#define btree_mgr_clear_ovfl(__n) do{\
		(__n)->has_cell_ovfl = 0;\
		MyBufferDestruct((__n)->cell_ovfl.cell_buf);\
		(__n)->cell_ovfl.cell_buf = NULL;\
	}while(0)

/**
 * @brief 页析构回调函数 
 */
static int btree_page_release(HPAGE_HEAD pg)
{
	btree_node * node = NULL;

	/* LOG_DEBUG(("btree_page_release")); */

	/* 引用计数为一定为零 */
	assert(PagerGetPageRefCount(pg) == 0);
	assert(sizeof(*node) == PageHeadGetUserDataSize(pg));

	node = PageHeadGetUserData(pg);
	assert(node);

	if(!node->init_flag)
	{
		assert(NULL == node->parent);
		assert(NULL == node->cell_ovfl.cell_buf);
		return 0;
	}

	/* 取消对父节点的引用 */
	if(node->parent)
	{
		btree_node * parent = node->parent;
		node->parent = NULL;
		btree_mgr_release_node(parent);
	}

	/* cell_ovfl里的buffer要释放,因为没有引用了,否则会造成内存泄漏 */
	btree_mgr_clear_ovfl(node);

	/* 初节点的初始化标志置成0 */
	node->init_flag = 0;

	return 0;
}

/**
 * @brief 页重新载入回调函数
 */
static int btree_page_reload(HPAGE_HEAD pg)
{
	btree_node * node = NULL;

	LOG_DEBUG(("btree_page_reload"));

	assert(sizeof(*node) == PageHeadGetUserDataSize(pg));

	node = PageHeadGetUserData(pg);

	assert(node);

	/* 将节点页里的信息重新读一遍 */
	if(node->init_flag)
		btree_mgr_init_node(node, 0);

	return 0;
}


/**
 * @brief 创建btree
 * @param pg_sz:btree 的 page size,可为0
 * @param cache_pg_count:btree页缓存最大值,可为0;
 * @param sector_sz:OS扇区的大小,可为0
 * @param rand_seed:随机数初始化种子
 * @param rand_seed_sz:rand_seed所指缓冲区的大小
 * @param user_rate:页文件使用率,可为0
 */
HBTREE_MGR btreeMgrConstruct(HMYMEMPOOL hm,
							 const char * page_file_name,
							 unsigned int pg_sz,
							 unsigned int cache_pg_count,
							 unsigned int sector_sz,
							 void * rand_seed,
							 unsigned int rand_seed_sz)
{
	btree_mgr_t * btree_mgr = NULL;
	if(NULL == page_file_name)
		return NULL;

	btree_mgr = MyMemPoolMalloc(hm, sizeof(*btree_mgr));
	if(NULL == btree_mgr)
		return NULL;

	memset(btree_mgr, 0, sizeof(*btree_mgr));

	btree_mgr->hm = hm;
	btree_mgr->pg_sz = pg_sz;
	btree_mgr->hpgr = PagerConstruct(hm,
		page_file_name,
		btree_page_release, btree_page_reload,
		sizeof(btree_node), cache_pg_count, &(btree_mgr->pg_sz),
		rand_seed, rand_seed_sz,
		sector_sz);

	if(NULL == btree_mgr->hpgr)
		goto btreeMgrConstruct_end_;

	/*
	* 记录溢出时,在本页存储的大小上限与下限
	* max_local应为page_sz的1/10,
	*/
	assert(btree_mgr->pg_sz / BTREE_PERCENT > (BTREE_CELL_PTR_SIZE + BTREE_CELL_HDR_SZ));

	btree_mgr->max_local = (((btree_mgr->pg_sz - BTREE_HDR_SZ) / BTREE_PERCENT 
		- (BTREE_CELL_PTR_SIZE + BTREE_CELL_HDR_SZ)) / SYS_ALIGNMENT) * SYS_ALIGNMENT;
	btree_mgr->min_local = ((btree_mgr->max_local / 2) / SYS_ALIGNMENT) * SYS_ALIGNMENT;

	btree_mgr->pg_min_fill_sz = ((btree_mgr->pg_sz - BTREE_HDR_SZ) * BTREE_FILL_RATE) / BTREE_PERCENT;
	assert(btree_mgr->pg_min_fill_sz > BTREE_HDR_SZ + btree_mgr->max_local);

	assert(btree_mgr->max_local >= 2 * BTREE_CELL_MIN_SZ);
	assert(btree_mgr->min_local >= 2 * BTREE_CELL_MIN_SZ);

	/* 游标链表头置空 */
	btree_mgr->cursor_lst = NULL;
	return btree_mgr;

btreeMgrConstruct_end_:

	btree_mgr_destroy(btree_mgr);
	return NULL;
}

/**
 * @brief 销毁btree
 */
int btreeMgrDestruct(HBTREE_MGR hbtreeMgr)
{
	if(hbtreeMgr)
		return btree_mgr_destroy(hbtreeMgr);

	return -1;
}

/**
 * @brief 释放游标 与btreeMgrGetCursor是对偶操作
 */
int btreeMgrReleaseCursor(HBTREE_CURSOR hcur)
{
	if(NULL == hcur || NULL == hcur->btree_mgr)
		return -1;

	btree_mgr_release_cursor(hcur);
	return 0;
}

/**
 * @brief 从cell里取出data
 */
static __INLINE__ int btree_mgr_cell_get_data(btree_node * node,
											  btree_cellinfo * cell_info,
											  unsigned char * data, unsigned int data_sz)
{
	unsigned int key_sz_left = 0;
	unsigned int pgno_ovfl = 0;
	HPAGE_HEAD pg_ovfl = NULL;
	const unsigned char * rb = NULL;

	assert(cell_info);

	if(!(node->node_flag & e_btree_page_flag_hasdata))
		return 0;

	assert(data && data_sz >= cell_info->data_sz);
	data_sz = cell_info->data_sz;

	/* 如果没有发生溢出,拷贝返回 */
	if(cell_info->local_sz == cell_info->payload_sz)
	{
		assert(((sizeof(unsigned int)) * ((node->node_flag & e_btree_page_flag_leaf) ? 0 : 1 ) + 
			4 * ((node->node_flag & e_btree_page_flag_hasdata) ? 1 : 0) + 4) == cell_info->head_sz);

		memcpy(data, 
			cell_info->cell + cell_info->head_sz + cell_info->key_sz * ((node->node_flag & e_btree_page_flag_intkey) ? 0 : 1),
			cell_info->data_sz);

		return 0;
	}

	assert(node && node->btree_mgr);

	if(cell_info->key_sz > cell_info->local_sz && !(node->node_flag & e_btree_page_flag_intkey))
	{
		key_sz_left = cell_info->key_sz - cell_info->local_sz;

		pgno_ovfl = cell_info->overflow_pgno;

		/* 跳过key所占有的区域 */
		while(key_sz_left)
		{
			assert(NULL == pg_ovfl);
			pg_ovfl = PagerGetPage(node->btree_mgr->hpgr, pgno_ovfl);
			if(NULL == pg_ovfl)
				goto btree_mgr_cell_get_data_err_;
			
			rb = PageHeadMakeReadable(pg_ovfl);
			if(NULL == rb)
				goto btree_mgr_cell_get_data_err_;

			if(key_sz_left > BTREE_OVERFLOW_PAYLOAD(node->btree_mgr))
			{
				array_to_uint_as_big_endian(rb, BTREE_OVERFLOW_HDR_SZ, pgno_ovfl);
				PagerReleasePage(pg_ovfl);
				pg_ovfl = NULL;

				key_sz_left -= BTREE_OVERFLOW_PAYLOAD(node->btree_mgr);
			}
			else
			{
				if(key_sz_left < BTREE_OVERFLOW_PAYLOAD(node->btree_mgr))
				{
					assert(data_sz >= key_sz_left);

					memcpy(data, rb + BTREE_OVERFLOW_HDR_SZ + key_sz_left, key_sz_left);
					data += key_sz_left;
					data_sz -= key_sz_left;
				}