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包含一个关键字数组.
 *  数组里的关键字已经被排好序
 *  oracle ten times, fastdb, mysql cluster等,使用了T树做为索引.
 *
 * 添加关键字至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 = (myttree_node_t *)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_leaf(myttree_t * ttree,
									 myttree_node_t * current_node,
									 const void * index_info)
{
	HMYVECTOR hv_index = NULL;

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

	hv_index = current_node->key.hv_index;
	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;
	}
}

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

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

	/*
	* 如果是半叶节点
	* 区分左右子树的情况
	* 如果只有左子树,取出最大节点成为新分支
	* 如果只有右子树,取出最大节点成为新分支 ttree_add(left, max_index_info)
	*/
	hv_index = current_node->key.hv_index;
	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;
		}