myttree_备份.c

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

/**
 *
 * @file myTTree.c T树
 *
 * @author lin shao chuan (email:[e-mail], msn:[e-mail])
 *
 * @brief
 * T 树是avl树的扩展(或者说是avl树与b树综合的产物)
 *  即一个node包含一个关键字数组.
 *  数组里的关键字已经被排好序
 *
 * 添加关键字至T树
 * 从根节点开始找寻,如果能找到bound数组,则添加,如果数组已满,抽出最小的那一个元素A.
 * 行进至greate lower bound(左子树最靠右的那个节点),如果可以添加A,则添加
 * 如果不能,则应创建新节点，并且根据实际情况旋转树保证avl树的平衡
 *
 * 如果没有找到合适的节点，则在最右(左)添加，添加不了则创建新节点，并根据实际情况旋转树
 *
 * 删除关键字
 *  从根节点开始找寻,如果找到
 *  a 如果当前节点的个数在删除之后仍然大于下限，操作完成
 *  b 如果当前节点个数小于小限，并且是内部节点，则从greate lower bound节点中借
 *    如果greate lower bound节点是leaf节点 同c
 *    如果greate lower bound节点是half leaf节点 同d
 *
 *  c 如果是half leaf节点，判断是否可以合并，然后根据需要旋转树
 *  d 如果是leaf节点,判断是否要删除，然后根据需要旋转树
 *
 * 关于数组排序:
 *   fastDB与mysql使用的都是二分查找定位排序
 */
#include "myTTree.h"

#include <assert.h>
#include <string.h>
#include <stdio.h>

#include "__avl_tree.h"
#include "myvector.h"
#include "__vector_inter.h"
#include "__bstree.h"


typedef struct __myttree_key_t_
{
	/*
	* 数组,存放索引信息
	*/
	HMYVECTOR hv_index;
}myttree_key_t;

typedef struct __myttree_node_t_
{
	/*
	* avl平衡树节点
	*/
	__avltree_node_t avl_node;

	myttree_key_t key;
}myttree_node_t;

typedef struct __myttree_t_
{
	HMYMEMPOOL hm;

	ALG_COMPARE compare;
	void * context;

	/*
	* T树的根节点
	*/
	myttree_node_t * root;

	/*
	* 一个节点的关键字个数下限
	*/
	size_t underflow;

	/*
	* 一个节点的关键个数上限
	*/
	size_t overflow;
}myttree_t;


/**
 * 索引数组排序
 */
#define ttree_sort_index_array(ttree, hv_index) do{\
		MyAlgQuickSort(__vector_inter_get_array((hv_index)),\
			__vector_inter_get_count((hv_index)), \
			__vector_inter_get_array_step_size((hv_index)),\
			ttree_compare, NULL, NULL, NULL, ttree, NULL, 0);\
	}while(0)


/**
 * T树比较
 */
static __INLINE__ int ttree_compare(const void * data1, const void * data2, const void * context)
{
	HMYVECTOR_ITER it1 = *((HMYVECTOR_ITER *)data1);
	HMYVECTOR_ITER it2 = *((HMYVECTOR_ITER *)data2);
	myttree_t * ttree = (myttree_t *)context;

	assert(ttree && it1 && it2 && ttree->compare);

	return ttree->compare(__vector_inter_get_iter_data(it1), __vector_inter_get_iter_data(it2), ttree->context);
}

/**
 * 索引数组查找
 */
static __INLINE__ int ttree_search(myttree_t * ttree, HMYVECTOR hv_index, const void * index_info, size_t * index)
{
	assert(ttree && hv_index && index_info);

	{
		__vector_inter_get_temp_it(it, 0, (void *)index_info);

		return MyBinarySearch(__vector_inter_get_array(hv_index),
			__vector_inter_get_count(hv_index),
			__vector_inter_get_array_step_size(hv_index),
			&it, ttree_compare, index, ttree);
	}
}

/**
 * 创建一个T树节点
 */
static __INLINE__ myttree_node_t * ttree_create_node(myttree_t * ttree, myttree_node_t * parent)
{
	myttree_node_t * node = MyMemPoolMalloc((assert(ttree), ttree->hm), sizeof(*node));

	if(NULL == node)
		return NULL;

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

	node->key.hv_index = __vector_inter_create(ttree->hm, ttree->overflow + 1, NULL, NULL);
	node->avl_node.height = 1;
	node->avl_node.base.parent = (bstree_node_t *)parent;

	return node;
}


/**
 * 销毁一个T树节点
 */
static __INLINE__ void ttree_destroy_node(myttree_t * ttree, myttree_node_t * node)
{
	assert(ttree && node && node->key.hv_index);

	__vector_inter_destroy(node->key.hv_index);

	MyMemPoolFree(ttree->hm, node);
}

/**
 * @brief 描述在__bstree_erase函数中如何释放每个节点
 * @param context:用户的上下文数据
 * @param root:根节点
 */
static void __ttree_destroy_node_cb(void * context, bstree_node_t * root)
{
	ttree_destroy_node((myttree_t *)context, (myttree_node_t *)root);
}


/**
 * @brief 查找合适的节点位置
 */
static __INLINE__ myttree_node_t * ttree_search_bound(myttree_t * ttree, myttree_node_t * node, const void * key, myttree_node_t ** parent)
{
	HMYVECTOR_ITER it_first = NULL;
	HMYVECTOR_ITER it_last = NULL;

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

	while(node)
	{
		HMYVECTOR hv = node->key.hv_index;

		assert(__vector_inter_get_count(hv));

		*parent = node;
		
		it_first = __vector_get_head(hv);
		it_last = __vector_get_tail(hv);

		if(ttree->compare(key, __vector_inter_get_iter_data(it_first), ttree->context) < 0)
		{
			node = (myttree_node_t *)node->avl_node.base.left;
			continue;
		}

		if(ttree->compare(key, __vector_inter_get_iter_data(it_last), ttree->context) > 0)
		{
			node = (myttree_node_t *)node->avl_node.base.right;
			continue;
		}

		return node;
	}

	return NULL;
}

/**
 * @brief 添加节点
 */
static __INLINE__ int ttree_add(myttree_t * ttree,
								myttree_node_t * current_node,
								const void * index_info)
{
	assert(ttree && current_node && ttree->compare);

	if(NULL == current_node->avl_node.base.left && NULL == current_node->avl_node.base.right)
	{
		/*
		* if is leaf
		* 如果是叶节点
		*/
		HMYVECTOR hv_index = current_node->key.hv_index;

		size_t index = 0;

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

		assert(hv_index && hv_index->el_array && hv_index->el_array_size);

		/*
		* 如果没有上溢
		*/
		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
		{
			myttree_node_t * node = ttree_create_node(ttree, current_node);
			if(NULL == node)
				return -1;

			current_node->avl_node.base.right = (bstree_node_t *)node;

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

			/*
			* 添加了节点,旋转树平衡
			* 在旋转之前,需要对当前树的形状进行判断,调整元素数组,防止inter 节点出现underflow的情况
			*
			* 情形1                 情形2(与情形1为镜像)
			*        A                    A
			*       /                      \
			*      B                        B
			*       \                       /
			*        C                     C
			* 此时需要所B中数组搬给C,防止出现C的节点underflow,因为旋转后,C将成为inter,如下图
			*              C                   C
			*             / \      或者       / \
			*            B   A               A   B
			*
			* 在本例中,由于C必为B右节点,所以只考虑情形1,情形2在本例中是不可能出现的
			*/

			if(current_node->avl_node.base.parent)
			{
				/* 如果树的形状为情形1 */
				if((bstree_node_t *)current_node == current_node->avl_node.base.parent->left && NULL == current_node->avl_node.base.parent->right)
				{
					/*
					* 把B中的元素借为C
					* 将B中的最小元素借给C
					* B C互换元素数组
					*/
					__vector_inter_add(node->key.hv_index, __vector_get_head_data(hv_index), 0);
					__vector_inter_del(hv_index, 0);

					current_node->key.hv_index = node->key.hv_index;
					node->key.hv_index = hv_index;
				}
				else
				{
					/*
					* 节点上溢了
					* 取出最大节点node_max,node_max成为新右分支,并旋转树
					*/
					__vector_inter_add(node->key.hv_index, __vector_get_tail_data(hv_index), 0);
					__vector_inter_del(hv_index, __vector_inter_get_count(hv_index) - 1);
				}
			}
			else
			{
				/*
				* 节点上溢了
				* 取出最大节点node_max,node_max成为新右分支,并旋转树
				*/
				__vector_inter_add(node->key.hv_index, __vector_get_tail_data(hv_index), 0);
				__vector_inter_del(hv_index, __vector_inter_get_count(hv_index) - 1);
			}

			__avltree_balance((__avltree_node_t **)&ttree->root, (__avltree_node_t *)current_node);

			return 0;
		}
	}
	else if(NULL != current_node->avl_node.base.left && NULL != current_node->avl_node.base.right)
	{
		/*
		* if is inter node
		* 如果是内部节点
		*/
		myttree_node_t * parent = NULL;

		/*
		* 寻找bound node
		*/
		myttree_node_t * node = ttree_search_bound(ttree, current_node, index_info, &parent);

		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;

			assert(hv_index && hv_index->el_array && hv_index->el_count && hv_index->el_array_size);

			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
			{
				/*
				* 上溢
				* 在合适的位置添加
				* 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);
				*/
				if(node->avl_node.base.right)
				{
					/*
					* todo:如果ii添加失败,则丢失了用户之前的数据信息
					*/
					int ret = ttree_add(ttree, (myttree_node_t *)(node->avl_node.base.right), ii);
					assert(0 == ret);
				}
				else
				{
					/*
					* todo:如果ii添加失败,则丢失了用户之前的数据信息
					*/
					int ret = ttree_add(ttree, node, ii);
					assert(0 == ret);
				}

				return 0;
			}
		}
		else
		{
			/*
			* 如果找不到 -- 同leaf/half leaf添加
			* ttree_add(parent, node);
			*/
			return ttree_add(ttree, parent, index_info);
		}
	}
	else
	{
		/*
		* 如果是半叶节点
		* 区分左右子树的情况
		* 如果只有左子树,取出最大节点成为新分支
		* 如果只有右子树,取出最大节点成为新分支 ttree_add(left, max_index_info)
		*/
		HMYVECTOR hv_index = current_node->key.hv_index;
		size_t index = 0;

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

		assert(hv_index && hv_index->el_array && hv_index->el_count && hv_index->el_array_size);

		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
		{
			if(current_node->avl_node.base.left)
			{
				myttree_node_t * node = ttree_create_node(ttree, current_node);
				if(NULL == node)
					return -1;

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

				/*
				* 添加了节点,但是根据逻辑得出,此时是不需要旋转树的
				*/
				current_node->avl_node.base.right = (bstree_node_t *)node;

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

				__vector_inter_add(node->key.hv_index, __vector_get_tail_data(hv_index), 0);
				__vector_inter_del(hv_index, __vector_inter_get_count(hv_index) - 1);

				return 0;
			}
			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);
				{
					int ret = ttree_add(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_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