myskiplist.c

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

//	//	else
//	//	{
//	//		/*
//	//		* 如果大于等于4,选出新的分割点
//	//		*/
//
//	//		myskl_node_t * right_down_prev = right->down->prev;
//
//	//		assert(right_down_prev);
//	//		assert(skl->compare(key, right->down->key, NULL) == 0);
//
//	//		/*
//	//		* 选取合适的分割点,这里注意别把下层要删除的节点选为分割点
//	//		*/
//	//		if(right_down_prev->prev)
//	//		{
//	//			/*
//	//			* 说明原间隙容量为 左>= 2 右>=1
//	//			* [? a b] [del c ?]
//	//			* 分法: 左1 中3 右?
//	//			* [!] [! ! !] [?]     !:表示一定有, ?:表示有可能不存在
//	//			* 此时要删除的节点在中间那个间隙
//	//			*/
//	//			myskl_node_t * node_new1 = skl_create_node(skl);
//	//			myskl_node_t * node_partion = second_layer_head->right->right->right;
//	//			assert(node_new1);//bug here;
//
//	//			node_new1->key = second_layer_head->right->key;
//	//			node_new1->data = second_layer_head->right->data;
//
//	//			node_new1->prev = NULL;
//	//			node_new1->right = first_tail_down;
//	//			node_new1->down = second_layer_head;
//
//	//			first_tail->down = first_tail_down = node_new1;
//
//	//			/* 根据需要创建第二个分割点 */
//	//			if(!node_partion->btail)
//	//			{
//	//				myskl_node_t * node_new2 = skl_create_node(skl);
//	//				assert(node_new2);//bug here;
//
//	//				node_new2->key = node_partion->key;
//	//				node_new2->data = node_partion->data;
//
//	//				node_new2->prev = node_new1;
//	//				node_new2->right = first_tail_down;
//	//				node_new2->down = second_layer_head->right;
//
//	//				node_new1->right = node_new2;
//
//	//				first_tail_down->down = node_partion;
//	//			}
//	//			else
//	//			{
//	//				first_tail_down->down = second_layer_head->right;
//	//			}
//	//		}
//	//		else 
//	//		{
//	//			/* 
//	//			* 说明原间隙容量为 左1 右3
//	//			* [ a ] [del b c]
//	//			* 分法: 左2 右2
//	//			* [a del] [b c] 
//	//			* 此时要删除的节点在第一个间隙的第二个节点
//	//			*/
//
//	//			myskl_node_t * node_new = skl_create_node(skl);
//	//			myskl_node_t * node_partion = right->down->right;
//	//			assert(node_new);//bug here
//
//	//			node_new->key = node_partion->key;
//	//			node_new->data = node_partion->data;
//
//	//			node_new->prev = NULL;
//	//			node_new->right = first_tail_down;
//	//			node_new->down = second_layer_head;
//
//	//			first_tail_down->down = node_partion;
//	//		}
//	//	}
//	//}
//	//else
//	//{
//	//}
//
//	///* 如果总和大于等于4,重新分割,保证即将递归的子间隙容量为2 */
//}
//
///**
// * @brief 创建一个节点
// */
//static void skl_destroy_node(myskl_t * skl, myskl_node_t * node)
//{
//	assert(skl && node);
//
//	MyMemPoolFree(skl->hm, node);
//}
//
///**
// * @brief 销毁skl
// */
//static __INLINE__ void skl_destroy(myskl_t * skl)
//{
//	assert(0);
//}
//
//
///**
// * @brief 创建跳跃表
// * @param max_level:跳表的层数
// */
//HMYSKL mySkipListConstruct(HMYMEMPOOL hm, ALG_COMPARE compare)
//{
//	myskl_t * skl = MyMemPoolMalloc(hm, sizeof(*skl));
//	if(NULL == skl)
//		return NULL;
//
//	skl->hm = hm;
//	skl->compare = compare;
//	skl->current_level = 0;
//
//	skl->first_tail = skl_create_node(skl);
//
//	skl->first_tail->right = skl->first_tail;
//	skl->first_tail->prev = NULL;
//	skl->first_tail->btail = 1;
//
//	return skl;
//
//mySkipListConstruct_end_:
//
//	skl_destroy(skl);
//
//	return NULL;
//}
//
///**
// * @brief 销毁跳跃表
// */
//HMYSKL mySkipListDestruct(HMYSKL hskl);
//
///**
// * @brief 往跳表里添加一条记录
// */
//int mySkipListAdd(HMYSKL hskl, const void * key, const void * data)
//{
//	myskl_node_t * new_node = NULL;
//	myskl_node_t * current = NULL;
//
//	if(NULL == hskl)
//		return -1;
//
//	current = hskl->first_tail;
//
//	while(1)
//	{
//		/*
//		* 比较大小,如果key大,往后跳,key小停止,如果到了该层链表的结尾,也停止
//		*/
//		while(hskl->compare(key, current->key, NULL) > 0 && !(current->btail))
//			current = current->right;
//
//		if(NULL == current->down)
//			break;
//
//		/*
//		* 看看当前的间隙容量是否等于3,如果为3,则需要分裂间隙 
//		*/
//		if(skl_compare(hskl, current, current->down->right->right) <= 0)
//		{
//			current = current->down;
//			continue;
//		}
//
//		new_node = skl_create_node(hskl);
//		if(NULL == new_node)
//			return -1;
//
//		/* 长高一层 */
//		if(current == hskl->first_tail)
//		{	
//			myskl_node_t * new_list_tail = skl_create_node(hskl);
//			new_list_tail = 1;
//			if(NULL == new_list_tail)
//			{
//				skl_destroy_node(new_node);
//				return -1;
//			}
//
//			new_list_tail->down = current->down;
//			current->down = new_list_tail;
//			new_list_tail->right = new_list_tail;
//			new_list_tail->prev = NULL;
//
//			current = new_list_tail;
//		}
//
//		/*
//		* 新节点关键字赋值
//		*/
//		new_node->key = current->key;
//		new_node->data = current->data;
//		new_node->btail = current->btail;
//
//		/*
//		* 新节点链接关系
//		*/
//		new_node->right = current->right;
//		new_node->down = current->down->right;
//		new_node->prev = current;
//
//		/*
//		* 更新当前节点
//		*/
//		current->key = current->down->right->key;
//		current->data = current->down->right->data;
//
//		/*
//		* 当前节点链接关系更新
//		*/
//		current->right = new_node;
//		current->btail = 0;
//
//		/* 指针不必下走 */
//	}
//
//	/* 直接链入即可 */
//	new_node = skl_create_node(hskl);
//	if(NULL == new_node)
//		return -1;
//
//	/*
//	* 新节点取代current
//	*/
//	new_node->key = current->key;
//	new_node->data = current->data;
//	new_node->btail = current->btail;
//
//	new_node->right = current->right;
//
//	/*
//	* current赋为添加的键与值,更改right链接
//	*/
//	current->key = key;
//	current->data = data;
//	current->btail = 0;
//
//	current->right = new_node;
//}
//
///**
// * @brief 从跳表里删除一条记录
// */
//int mySkipListDel(HMYSKL hskl, const void * key, void ** key_ount, void ** data_out)
//{
//	/*
//	* 在每一层链表里查找,依次删除
//	*
//	* 如果要删除的节点在第一层出现,直接删除了它,如果第一层为空,寻找新的分割节点,或者整个跳表下降一层(次层节点不足4的情况下)
//	* 如果要删除的节点不在第一层,并出现了"总和为4"的问题,则应考虑切换分割节点,即让要删除的区间间隙变成2
//	* 
//	* 非顶层节点处理情况,如果要删除的节点在当前间隙
//	*  如果检查删除后合并下一层的新间隙容量会达到 4~6 选出新的节点分割间隙
//	*  如果删除后当前间隙只剩下一个节点,应选出新的分割点,将当前间隙容量补到2
//	*  检查将要递归到下一层的子间隙,如果它的容量为1,则考虑借,或合并,保证将要递归的新间隙的容量大于等于2
//	*/
//
//	//if(NULL == hskl)
//	//	return -1;
//
//	//while(1)
//	//{
//	//	/*
//	//	* 比较大小,如果key大,往后跳,key小停止,如果到了该层链表的结尾,也停止
//	//	*/
//	//	int ret = hskl->compare(key, current->key, NULL);
//	//	while(ret > 0 && !(current->btail))
//	//	{
//	//		current = current->right;
//	//		prev = current;
//	//		ret = hskl->compare(key, current->key, NULL);
//	//	}
//
//	//	if(0 == ret)
//	//	{
//	//		/*
//	//		* 在递归向下的过程中已确保,当前间隙容量大于等于2
//	//		*/
//	//		if(prev)
//	//			prev->right;
//	//	}
//
//	//	if(NULL == current->down)
//	//		break;
//	//}
//
//	//return 0;
//}
//
///**
// * @brief 查询一条记录
// */
//int mySkipListSearch(HMYSKL hskl, const void * key, void ** data_out)
//{}
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//