myttree.c

提供了rbtree ttree avltree list hashtable等常用容器的算法,代码经过uclinux + arm44b0平台验证

		else
		{
			/*
			* 上溢
			* 在合适的位置添加
			* todo:看了其它开源的T树实现,实际上它们不是这么做的,直接将数据插到合适的位置.
			*/
			__vector_inter_add(hv_index, index_info, 0);
			ttree_sort_index_array(ttree, hv_index);

			/* 根据逻辑,这个条件必成立 */
			assert(current_node->avl_node.base.right);
			assert(NULL == current_node->avl_node.base.right->left && NULL == current_node->avl_node.base.right->right);

			{
				int ret = ttree_add_leaf(ttree, (myttree_node_t *)(current_node->avl_node.base.right), __vector_get_tail_data(hv_index));
				assert(ret == 0);
			}

			__vector_inter_del(hv_index, __vector_inter_get_count(hv_index) - 1);

			return 0;
		}
	}
}

/**
 * @brief 在内部节点添加
 */
static __INLINE__ int ttree_add_inter(myttree_t * ttree,
									  myttree_node_t * current_node,
									  const void * index_info)
{
	HMYVECTOR hv_index = NULL;

	assert(ttree && current_node && ttree->compare);
	assert(current_node->avl_node.base.left && current_node->avl_node.base.right);

	hv_index = current_node->key.hv_index;
	assert(hv_index && hv_index->el_array && hv_index->el_array_size && hv_index->el_count);

	if(__vector_inter_get_count(hv_index) < ttree->overflow)
	{
		/*
		* 没有上溢
		* 在合适的位置添加
		* todo:看了其它开源的T树实现,实际上它们不是这么做的,直接将数据插到合适的位置.
		*/
		__vector_inter_add(hv_index, index_info, 0);
		ttree_sort_index_array(ttree, hv_index);

		return 0;
	}
	else
	{
		/* least upper bound */
		myttree_node_t * lub_node = NULL;

		/*
		* 上溢
		* 在合适的位置添加
		* todo:看了其它开源的T树实现,实际上它们不是这么做的,直接将数据插到合适的位置.
		*/
		void * ii = NULL;

		__vector_inter_add(hv_index, index_info, 0);
		ttree_sort_index_array(ttree, hv_index);

		ii = __vector_get_tail_data(hv_index);

		__vector_inter_del(hv_index, __vector_inter_get_count(hv_index) - 1);

		/*
		* 如果出现上溢,取出最大节点,ttree_add(right, max_key);
		* 加入到least upper bound节点里
		*/
		lub_node = (myttree_node_t *)current_node->avl_node.base.right;
		assert(lub_node);

		while(lub_node->avl_node.base.left)
			lub_node = (myttree_node_t *)lub_node->avl_node.base.left;

		if(lub_node->avl_node.base.right)
		{
			int ret = ttree_add_half_leaf(ttree, lub_node, ii);
			assert(0 == ret);
		}
		else
		{
			int ret = ttree_add_leaf(ttree, lub_node, ii);
			assert(0 == ret);
		}

		return 0;
	}
}

/**
 * @brief 添加节点
 */
static __INLINE__ int ttree_add(myttree_t * ttree,
								const void * index_info)
{
	myttree_node_t * parent = NULL;
	myttree_node_t * node = NULL;

	assert(ttree && ttree->root && ttree->compare);

	/*
	* 寻找bound node
	*/
	if(ttree->root->avl_node.base.left || ttree->root->avl_node.base.right)
		node = ttree_search_bound(ttree, ttree->root, index_info, &parent);
	else
		node = ttree->root;

	if(node)
	{
		/*
		* 如果找到
		*/
		HMYVECTOR hv_index = node->key.hv_index;
		size_t index = 0;

		/*
		* 如果在节点中找到关键字,添加失败,并返回
		*/
		if(0 == ttree_search(ttree, hv_index, index_info, &index))
			return -1;

		if(NULL == node->avl_node.base.left && NULL == node->avl_node.base.right)
		{
			/*
			* 在叶节点处添加
			*/
			return ttree_add_leaf(ttree, node, index_info);
		}
		else if(NULL != node->avl_node.base.left && NULL != node->avl_node.base.right)
		{
			/*
			* 在内部节点添加
			*/
			return ttree_add_inter(ttree, node, index_info);
		}
		else
		{
			/*
			* 在半叶节点处添加
			*/
			return ttree_add_half_leaf(ttree, node, index_info);
		}
	}

	assert(parent);
	assert(NULL == parent->avl_node.base.left || NULL == parent->avl_node.base.right);

	if(NULL == parent->avl_node.base.left && NULL == parent->avl_node.base.right)
	{
		/*
		* 在叶节点添加
		*/
		return ttree_add_leaf(ttree, parent, index_info);
	}
	else
	{
		/*
		* 在半叶节点添加
		*/
		return ttree_add_half_leaf(ttree, parent, index_info);
	}
}


/**
 * @brief 在叶节点处删除
 */
static __INLINE__ int ttree_del_leaf(myttree_t * ttree,
									 myttree_node_t * current_node,
									 size_t index)
{
	HMYVECTOR hv_index = NULL;

	assert(ttree && current_node && (current_node->avl_node.base.parent || current_node == ttree->root));
	assert(NULL == current_node->avl_node.base.left && NULL == current_node->avl_node.base.right);

	hv_index = current_node->key.hv_index;

	__vector_inter_del(hv_index, index);

	/*
	* 如果还有节点
	*/
	if(__vector_inter_get_count(hv_index))
		return 0;

	/*
	* 如果没有数组为空了,则需要删除节点,并旋转树balance
	* 注意:如果parent为空,表明当前节点是根节点,不删除根节点
	*/
	if(current_node->avl_node.base.parent)
	{
		/*
		* 删除了节点,旋转树平衡
		* 在旋转之前,需要对当前树的形状进行判断,调整元素数组,防止inter 节点出现underflow的情况
		*
		* 如图 X 表示要删除的节点
		* 情形1                 情形2(与情形1为镜像)
		*        A                    A
		*       / \                  / \
		*      B   X                X   B
		*       \                       /
		*        C                     C
		* 此时需要所B中数组搬给C,防止出现C的节点underflow,因为旋转后,C将成为inter,如下图
		*              C                   C
		*             / \      或者       / \
		*            B   A               A   B
		*/

		if((bstree_node_t *)current_node == current_node->avl_node.base.parent->left)
		{
			myttree_node_t * b_node = (myttree_node_t *)(current_node->avl_node.base.parent->right);
			if(b_node)
			{
				myttree_node_t * c_node = (myttree_node_t *)(current_node->avl_node.base.parent->right->left);
				if(c_node && NULL == b_node->avl_node.base.right && __vector_inter_get_count(c_node->key.hv_index) <= ttree->underflow)
				{
					/*
					* 情形2
					* 把B "最小的那一部分<range>" 借给C
					*/
					size_t range = ttree->underflow + 1 - __vector_inter_get_count(c_node->key.hv_index);

					assert(__vector_inter_get_count(b_node->key.hv_index) > ttree->underflow);

					__vector_move_range_to_end(c_node->key.hv_index, b_node->key.hv_index, 
						0, range);

					ttree_sort_index_array(ttree, c_node->key.hv_index);
				}
			}

			current_node->avl_node.base.parent->left = NULL;
		}
		else
		{
			myttree_node_t * b_node = (myttree_node_t *)(current_node->avl_node.base.parent->left);
			if(b_node)
			{
				myttree_node_t * c_node = (myttree_node_t *)(current_node->avl_node.base.parent->left->right);
				if(c_node && NULL == b_node->avl_node.base.left && __vector_inter_get_count(c_node->key.hv_index) <= ttree->underflow)
				{
					/*
					* 情形1
					* 把B "最大的那一部分<range>" 给C
					*/
					size_t range = ttree->underflow + 1 - __vector_inter_get_count(c_node->key.hv_index);

					assert(__vector_inter_get_count(b_node->key.hv_index) > ttree->underflow);

					__vector_move_range_to_end(c_node->key.hv_index, b_node->key.hv_index, 
						__vector_inter_get_count(b_node->key.hv_index) - range, range);

					ttree_sort_index_array(ttree, c_node->key.hv_index);
				}
			}

			current_node->avl_node.base.parent->right = NULL;
		}

		__avltree_balance((__avltree_node_t **)&ttree->root, (__avltree_node_t *)(current_node->avl_node.base.parent));

		/*
		* 不是根节点,释放
		*/
		ttree_destroy_node(ttree, current_node);
	}

	return 0;
}

/**
 * @brief 在半叶节点处删除
 */
static __INLINE__ int ttree_del_half_leaf(myttree_t * ttree,
										  myttree_node_t * current_node,
										  size_t index)
{
	HMYVECTOR hv_index = NULL;
	myttree_node_t * sub_node = NULL;

	assert(ttree && current_node);
	assert(NULL == current_node->avl_node.base.left || NULL == current_node->avl_node.base.right);

	hv_index = current_node->key.hv_index;

	assert(hv_index && hv_index->el_array && hv_index->el_count && hv_index->el_array_size);
	assert(index <= hv_index->el_count);

	__vector_inter_del(hv_index, index);

	/*
	* 如果没有下溢(所谓的underflow)
	*/
	if(__vector_inter_get_count(hv_index) > ttree->underflow)
		return 0;

	/*
	* if underflow
	* 如果判断是否可以合并相应的子节点,
	* (根据avl树的定义,此时的子节点一定为叶节点)
	*/
	if(current_node->avl_node.base.right)
	{
		sub_node = (myttree_node_t *)(current_node->avl_node.base.right);
	
		assert(sub_node && NULL == sub_node->avl_node.base.left && NULL == sub_node->avl_node.base.right);
		assert(__vector_inter_get_count(sub_node->key.hv_index));

		/*
		* 如果在右子节点,取子节点最小的加入当前节点,根据T树的定义,可知此时,新加入的节点一定是最大的,所以不必排序
		*/
		assert(ttree->compare(__vector_inter_get_index_data(sub_node->key.hv_index, 0), 
			__vector_inter_get_index_data(hv_index, __vector_inter_get_count(hv_index) - 1),
			ttree->context) > 0);
		__vector_inter_add(hv_index, __vector_inter_get_index_data(sub_node->key.hv_index, 0), 0);

		return ttree_del_leaf(ttree, sub_node, 0);
	}
	else
	{
		size_t new_del_index = 0;

		sub_node = (myttree_node_t *)(current_node->avl_node.base.left);

		assert(sub_node && NULL == sub_node->avl_node.base.left && NULL == sub_node->avl_node.base.right);
		assert(__vector_inter_get_count(sub_node->key.hv_index));

		new_del_index = __vector_inter_get_count(sub_node->key.hv_index) - 1;

		/*
		* 如果在右子节点,取子节点最大的加入当前节点,根据T树的定义,可知此时,新加入的节点一定是最小的,所以需要排序
		*/
		assert(ttree->compare(__vector_inter_get_index_data(sub_node->key.hv_index, new_del_index), 
			__vector_inter_get_index_data(hv_index, 0),
			ttree->context) < 0);
		__vector_inter_add(hv_index, __vector_inter_get_index_data(sub_node->key.hv_index, new_del_index), 0);
		ttree_sort_index_array(ttree, hv_index);

		return ttree_del_leaf(ttree, sub_node, new_del_index);
	}
}

/**
 * @brief 在内部节点中删除
 */
static __INLINE__ int ttree_del_inter(myttree_t * ttree,
												   myttree_node_t * current_node,
												   size_t index)
{
	HMYVECTOR hv_index = NULL;
	myttree_node_t * lub_node = NULL;

	assert(current_node && ttree);
	assert(current_node->avl_node.base.left && current_node->avl_node.base.right);

	hv_index = current_node->key.hv_index;

	assert(hv_index && hv_index->el_array && hv_index->el_count && hv_index->el_array_size);
	assert(index <= hv_index->el_count);

	__vector_inter_del(hv_index, index);

	/*
	* 如果没有下溢(所谓的underflow)
	*/
	if(__vector_inter_get_count(hv_index) > ttree->underflow)
		return 0;