myrbtree.c

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

}

static __INLINE__ void rbtree_inter_erase(myrbtree_t * rbtree, myrbtree_node_t * node)
{
	assert(node);

	while(node)
	{
		myrbtree_node_t * y = node->left;

		if(node->right)
			rbtree_inter_erase(rbtree, node->right);

		rbtree_inter_destroy_node(rbtree, node);

		node = y;
	}
}

static __INLINE__ int rbtree_inter_realcount(myrbtree_node_t * root)
{
	int left = 0;
	int right = 0;

	if(NULL == root)
		return 0;

	if(root->left)
		left = rbtree_inter_realcount(root->left);

	if(root->right)
		right = rbtree_inter_realcount(root->right);

	return left + right + 1;
}

static __INLINE__ int rbtree_inter_examin(myrbtree_t * rbtree, myrbtree_node_t * node)
{
	int left = 0;
	int right = 0;

	if(NULL == node)
		return 0;

	if(node->left)
	{
		assert(rbtree_inter_compare(rbtree, node->key, node->left->key));
		assert(node->left->parent == node);
		left = rbtree_inter_examin(rbtree, node->left);
	}

	if(node->right)
	{
		assert(rbtree_inter_compare(rbtree, node->right->key, node->key));
		assert(node->right->parent == node);
		right = rbtree_inter_examin(rbtree, node->right);
	}

	assert(left == right);

	if(rbtree_colour_black == node->colour)
		return left + 1;
	else
		return left;
}


/*
*
*创建rb树
*
*/
HMYRBTREE MyRBTreeConstruct(HMYMEMPOOL hm, myrbtree_compare compare)
{
	myrbtree_t * rbtree = NULL;

	rbtree = (myrbtree_t *)MyMemPoolMalloc(hm, sizeof(*rbtree));

	if(NULL == rbtree)
		return NULL;

	rbtree->compare = compare;
	rbtree->hm = hm;
	rbtree->root = NULL;

	return (HMYRBTREE)rbtree;
}

/*
*
*销毁rb树
*
*/
void MyRBTreeDestruct(HMYRBTREE htree)
{
	myrbtree_t * rbtree = (myrbtree_t *)htree;

	if(NULL == rbtree)
		return;

	//遍历树,释放每个节点
	if(rbtree->root)
		rbtree_inter_erase(rbtree, rbtree->root);

	MyMemPoolFree(rbtree->hm, rbtree);
}

/*
*
*删除所有节点
*
*/
void MyRBTreeClear(HMYRBTREE htree)
{
	myrbtree_t * rbtree = (myrbtree_t *)htree;

	if(NULL == rbtree)
		return;

	if(NULL == rbtree->root)
		return;

	//遍历树,释放每个节点
	rbtree_inter_erase(rbtree, rbtree->root);
	rbtree->root = NULL;
}

/*
*
*往rb树中插入一个节点
*
*/
HMYRBTREE_ITER MyRBTreeInsertEqual(HMYRBTREE htree, const void * key, const void * userdata)
{
	myrbtree_t * rbtree = (myrbtree_t *)htree;
	myrbtree_node_t * node_new = NULL;
	myrbtree_node_t * parent = NULL;

	if(NULL == rbtree)
        return NULL;

	rbtree_inter_searchex(rbtree, rbtree->root, key, &parent);

	node_new = rbtree_inter_create_node(rbtree, key, userdata);
	if(NULL == node_new)
		return NULL;

	rbtree_inter_insert(rbtree, &rbtree->root, node_new, parent);

	return (HMYRBTREE_ITER)node_new;
}

/*
*
*往rb树中插入一个节点
*
*/
HMYRBTREE_ITER MyRBTreeInsertUnique(HMYRBTREE htree, const void * key, const void * userdata)
{
	myrbtree_t * rbtree = (myrbtree_t *)htree;

	myrbtree_node_t * parent = NULL;
	myrbtree_node_t * node_new = NULL;

	if(NULL == rbtree)
        return NULL;
	
	node_new = rbtree_inter_searchex(rbtree, rbtree->root, key, &parent);
	if(node_new != NULL)
		return (HMYRBTREE_ITER)node_new;

	node_new = rbtree_inter_create_node(rbtree, key, userdata);
	if(NULL == node_new)
		return NULL;

	rbtree_inter_insert(rbtree, &rbtree->root, node_new, parent);

	return (HMYRBTREE_ITER)node_new;
}

/*
*
*从rb树中删除一个节点 iter失效
*
*/
void MyRBTreeDelIter(HMYRBTREE htree, HMYRBTREE_ITER iter, void ** key, void ** data)
{
	myrbtree_t * rbtree = (myrbtree_t *)htree;
	myrbtree_node_t * node = (myrbtree_node_t *)iter;

	if(NULL == rbtree || NULL == node)
		return;

	assert(rbtree_inter_search(rbtree, rbtree->root, node->key));

	rbtree_inter_del(rbtree, &(rbtree->root), node, key, data);
}

/*
*
*根据键值删除一个节点
*成功删除返回0, 否则返回-1
*
*/
int MyRBTreeDelKey(HMYRBTREE htree, const void * key, void ** key_ret, void ** data_ret)
{
	myrbtree_t * rbtree = (myrbtree_t *)htree;
	myrbtree_node_t * node = NULL;

	if(NULL == rbtree)
		return -1;

	node = rbtree_inter_search(rbtree, rbtree->root, key);

	if(NULL == node)
		return -1;

	rbtree_inter_del(rbtree, &(rbtree->root), node, key_ret, data_ret);

	return 0;
}

/*
*
*获取节点的用户数据
*
*/
void * MyRBTreeGetIterData(const HMYRBTREE_ITER iter)
{
	myrbtree_node_t * node = (myrbtree_node_t *)iter;

	if(NULL == node)
		return NULL;

	return node->data;
}

/*
*
*获取节点的键
*
*/
const void * MyRBTreeGetIterKey(const HMYRBTREE_ITER iter)
{
	myrbtree_node_t * node = (myrbtree_node_t *)iter;

	if(NULL == node)
		return NULL;

	return node->key;
}

/*
*
*查找节点
*
*/
HMYRBTREE_ITER MyRBTreeSearch(const HMYRBTREE htree, const void * key)
{
	myrbtree_t * rbtree = (myrbtree_t *)htree;
	myrbtree_node_t * node = NULL;

	if(NULL == rbtree || NULL == rbtree->compare)
		return NULL;

	node = rbtree_inter_search(rbtree, rbtree->root, key);

	return (HMYRBTREE_ITER)node;
}

/*
*
*计算最大层数
*
*/
int MyRBTreeLayer(const HMYRBTREE htree, int bmax)
{
	myrbtree_t * rbtree = (myrbtree_t *)htree;

	if(NULL == rbtree)
		return 0;

	return rbtree_inter_countlayer(rbtree->root, bmax);
}

/*
*
*"获取第一个节点"
*
*/
HMYRBTREE_ITER MyRBTreeBegin(const HMYRBTREE htree)
{
	myrbtree_t * rbtree = (myrbtree_t *)htree;

	if(NULL == rbtree)
		return 0;

	return (HMYRBTREE_ITER)rbtree_inter_begin(rbtree);
}

/*
*
*"获取最后一个节点"
*
*/
HMYRBTREE_ITER MyRBTreeEnd(const HMYRBTREE htree)
{
	myrbtree_t * rbtree = (myrbtree_t *)htree;

	if(NULL == rbtree)
		return 0;

	return (HMYRBTREE_ITER)rbtree_inter_end(rbtree);
}

/*
*
*获取下一个节点
*
*/
HMYRBTREE_ITER MyRBTreeGetNext(const HMYRBTREE_ITER it)
{
	myrbtree_node_t * node = (myrbtree_node_t *)it;

	if(NULL == node)
		return NULL;

	if(NULL == node->right)
	{
		while(node->parent && node == node->parent->right)
			node = node->parent;

		if(node->parent && node == node->parent->left)
			return (HMYRBTREE_ITER)node->parent;
		else
			return NULL;
	}
	else
	{
		node = node->right;
		while(node->left)
			node = node->left;

		return (HMYRBTREE_ITER)node;
	}
}

/*
*
*获取上一个节点
*
*/
HMYRBTREE_ITER MyRBTreeGetPrev(const HMYRBTREE_ITER it)
{
	myrbtree_node_t * node = (myrbtree_node_t *)it;

	if(node->left)
	{
		node = node->left;
		while(node->right)
			node = node->right;
		return (HMYRBTREE_ITER)node;
	}
	else
	{
		while(node->parent && node == node->parent->left)
			node = node->parent;

		if(node->parent && node == node->parent->right)
			return (HMYRBTREE_ITER)node->parent;
		else
			return NULL;
	}		
}

/*
*
*检查红黑树是否合法
*
*/
int MyRBTreeExamin(const HMYRBTREE htree)
{
	myrbtree_t * rbtree = (myrbtree_t *)htree;

	if(NULL == rbtree)
		return 0;

	return rbtree_inter_examin(rbtree, rbtree->root);
}

/*
*
*获取个数
*
*/
int MyRBTreeGetRealCount(const HMYRBTREE htree)
{
	myrbtree_t * rbtree = (myrbtree_t *)htree;

	if(NULL == rbtree)
		return 0;

	return rbtree_inter_realcount(rbtree->root);
}

#include "mymap.c"

#ifdef WIN32
	#include "MyStringSetEx.c"
#endif