mybinarysearch.c

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

/**
 *
 * @file MyBinarySearch.c 二分查找
 *
 * @author lin shao chuan (email:[e-mail], msn:[e-mail])
 *
 */
#include "MyAlgorithm.h"

#include <assert.h>

#include "myutility.h"


/**
 * @brief 在一个有序序列里做二分查找
 */
static int __alg_binary_search(const void * buf, size_t len, size_t step_size,
							   const void * key,
							   ALG_COMPARE compare, size_t * pindex,
							   const void * context)
{
	size_t hi = len;
	size_t lo = 0;

	assert(buf && len && step_size && compare);

	while(hi > lo)
	{
		size_t mid = (hi + lo) / 2;
		int ret = compare(key, GET_INDEX_PTR(buf, mid, step_size), context);

		if(ret > 0)
		{
			lo = mid + 1;
			continue;
		}
		else if(ret < 0)
		{
			hi = mid;
			continue;
		}
		else
		{
			if(pindex)
				*pindex = mid;
			return 0;
		}
	}

	assert(hi == lo);

	if(pindex)
		*pindex = lo;

	return -1;
}


/**
 *
 * @brief 在一个有序序列里做二分查找
 *
 * @param buf:有序序列数据缓冲区起始地址
 * @param len:有序序列中的元素个数
 * @param step_size:每个元素的大小
 * @param key:要查找的关键字
 * @param compare:比较回调(不可为空)
 * @param pindex:如果找到,返回元素的位置
 *
 * @retval 0:成功
 * @retval 其它:失败
 *
 */
int MyBinarySearch(const void * buf, size_t len, size_t step_size,
				   const void * key,
				   ALG_COMPARE compare, size_t * pindex,
				   const void * context)
{
	if(NULL == buf || 0 == len || 0 == step_size || NULL == compare)
		return -1;

	return __alg_binary_search(buf, len, step_size, key, compare, pindex, context);
}