test_myrbtree.c

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

#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <string.h>
#ifdef WIN32
#include <winsock2.h>
extern void gettimeofday(struct timeval *ptv, void *tzp);
#else
#include <sys/time.h>
#endif
#include <assert.h>

#ifdef __cplusplus
extern "C"
{
#endif
#include "mymap.h"
#include "myrbtree.h"
#include "mylist.h"
#ifdef __cplusplus
}
#endif

extern void getcallid(char * callid, size_t callid_len);

#define LOOP_COUNT 10000
#define CALLID_LEN 32

enum __rbtree_colour_
{
	rbtree_colour_black,
	rbtree_colour_red,
};

struct __myrbtree_node_t_
{
	struct __myrbtree_node_t_ * left;
	struct __myrbtree_node_t_ * right;
	struct __myrbtree_node_t_ * parent;

	enum __rbtree_colour_ colour;

	char * key;
	char * data;
};

struct __myrbtree_t_
{
	struct __myrbtree_node_t_ * root;

	//内存池
	HMYMEMPOOL hm;

	//比较运算符
	myrbtree_compare compare;
};

int myrbtree_compare1(const void * key1, const void * key2)
{
	return (int)key1 > (int)key2;
}

static void printftree(struct __myrbtree_node_t_ * node)
{
	HMYLIST hlist = MyListConstruct(NULL);
	int son = 0;

	MyListAddTail(hlist, node);

	while(!MyListIsEmpty(hlist))
	{
		node = (struct __myrbtree_node_t_ *)MyListPopHead(hlist);

		if(NULL == node)
			continue;

		printf("%d-%d-%x-%x  ", node->data, node->colour, node, node->parent);

		son --;
		if(son <= 0)
			printf("\n\n\n");

		if(node->left)
		{
			MyListAddTail(hlist, node->left);
			//son ++;
		}

		if(node->right)
		{
			MyListAddTail(hlist, node->right);
			//son ++;
		}
		if(son <= 0)
			son = MyListGetCount(hlist);
	}

	MyListDestruct(hlist);
}

int myrbtree_compare_string(const void * key1, const void * key2)
{
	const char * actemp = (const char * )key1;
	const char * actemp1 = (const char * )key2;

	if(strcmp(actemp, actemp1) > 0)
		return 1;

	return 0;
}

//void getcallid(char * callid, size_t callid_len)
//{
//	int i = 0;
//	for(i=0; i<callid_len - 1; i++)
//	{		
//		char ucRandomNum = (char)(rand()%36);
//		if(ucRandomNum<=9)
//			callid[i] = '0'+ucRandomNum;
//		else
//			callid[i] = 'a'+ucRandomNum-10;
//	}
//
//	//strncpy(callid, "aaaaaaaaaaaaaaa", callid_len/2);
//
//	callid[callid_len - 1] = 0;
//}


typedef struct __test_map_tag_
{
	char rand_string[CALLID_LEN];

#ifdef _DEBUG
	char * data;
#endif
}test_map_tag;

static int map_compare_string(const void * key1, const void * key2)
{
	//const test_map_tag * actemp = key1;
	//const test_map_tag * actemp1 = key2;

	if(strcmp(((test_map_tag*)key1)->rand_string, ((test_map_tag*)key2)->rand_string) > 0)
		return 1;

	return 0;
}

#ifdef _DEBUG

/*
*
*描述如何构造key
*
*/
static void test_key_construct(void * key, size_t key_size, void * param, size_t param_size)
{
	test_map_tag * tag = (test_map_tag *)key;

	tag->data = (char *)MyMemPoolMalloc(NULL, sizeof(tag->rand_string));
}

/*
*
*描述如何析构key
*
*/
static void test_key_destruct(void * key, size_t key_size)
{
	test_map_tag * tag = (test_map_tag *)key;

	MyMemPoolFree(NULL, tag->data);
}

/*
*
*描述如何构造data
*
*/
static void test_data_construct(void * data, size_t data_size, void * param, size_t param_size)
{
	test_map_tag * tag = (test_map_tag *)data;

	tag->data = (char *)MyMemPoolMalloc(NULL, sizeof(tag->rand_string));
}

/*
*
*描述如何析构data
*
*/
static void test_data_destruct(void * data, size_t data_size)
{
	test_map_tag * tag = (test_map_tag *)data;

	MyMemPoolFree(NULL, tag->data);
}

/*
*
*描述如何拷贝key
*
*/
static void test_key_copy(void * dst, size_t dst_len, const void * src, size_t src_len)
{
	test_map_tag * tag_src = (test_map_tag *)src;
	test_map_tag * tag_dst = (test_map_tag *)dst;

	strncpy(tag_dst->rand_string, tag_src->rand_string, sizeof(tag_dst->rand_string));
	strncpy(tag_dst->data, tag_dst->rand_string, sizeof(tag_dst->rand_string));
}

/*
*
*描述如何拷贝data
*
*/
static void test_data_copy(void * dst, size_t dst_len, const void * src, size_t src_len)
{
	test_map_tag * tag_src = (test_map_tag *)src;
	test_map_tag * tag_dst = (test_map_tag *)dst;

	strncpy(tag_dst->rand_string, tag_src->rand_string, sizeof(tag_dst->rand_string));
	strncpy(tag_dst->data, tag_dst->rand_string, sizeof(tag_dst->rand_string));
}
#endif
static myobj_ops key_ops = {
#ifndef _DEBUG
	0
#else
	test_key_construct,
	test_key_destruct,
	test_key_copy,
#endif
};

static myobj_ops data_ops = {
#ifndef _DEBUG
	0
#else
	test_data_construct,
	test_data_destruct,
	test_data_copy,
#endif
};

void test_map()
{

	struct timeval tv1;
	struct timeval tv2;
	HMYMAP hmap = MyMapRealConstruct(NULL, map_compare_string, 
		&key_ops,
		&data_ops
		/*test_key_construct, test_key_destruct,
		test_data_construct, test_data_destruct,
		test_key_copy, test_data_copy*/);

	int i = 0;
	int count = 0;
	int temp_test = 0;
	struct __myrbtree_t * temp = (struct __myrbtree_t * )hmap;

	unsigned long rand_seed = time(0);
	{
		FILE * pfile = fopen("rand_seed.txt", "aw");
		if(pfile)
		{
			fprintf(pfile, "rand seed:%d\n", rand_seed);
			fclose(pfile);
		}
	}
	srand(rand_seed);
	temp_test = rand();
	srand(rand_seed);
	temp_test = rand();

	srand(0/*rand_seed*/);
	gettimeofday(&tv1, 0);
	for(i = 0; i < LOOP_COUNT; i ++)
	{
#ifndef _DEBUG
		test_map_tag temp_tag = {0};

		getcallid(temp_tag.rand_string, sizeof(temp_tag.rand_string) - 1);

		MyMapInsertUnique(hmap, &temp_tag, sizeof(temp_tag), &temp_tag, 20);
#else
		int flag = 0;
		test_map_tag temp_tag = {0};

		getcallid(temp_tag.rand_string, sizeof(temp_tag.rand_string)-1);

		if(NULL == MyMapSearch(hmap, &temp_tag))
		{
			flag = 1;
		}
		else
		{
			assert(0);
			flag = 0;
		}

		MyMapInsertUnique(hmap, &temp_tag, sizeof(temp_tag), &temp_tag, sizeof(temp_tag));

		if(flag)
		{
			int a = MyMapExamin(hmap);
			count ++;
			printf(".");
		}
		else
		{
			printf(" ");
		}
#endif
	}
	gettimeofday(&tv2, 0);
	printf("mymap添加用时:%f秒\n", tv2.tv_sec - tv1.tv_sec + (tv2.tv_usec - tv1.tv_usec)/1000000.0);

	printf("开始搜索随机记录\n");
	printf("\n开始mymap开始查找1000k记录\n");
	srand(0/*rand_seed*/);
	gettimeofday(&tv1, 0);
	for(i = 0; i < LOOP_COUNT; i ++)
	{
#ifndef _DEBUG
		test_map_tag temp_tag = {0};

		getcallid(temp_tag.rand_string, sizeof(temp_tag.rand_string)-1);

		MyMapSearch(hmap, &temp_tag);
#else
		HMYMAP_ITER it = NULL;
		test_map_tag temp_tag = {0};

		getcallid(temp_tag.rand_string, sizeof(temp_tag.rand_string)-1);

		it = MyMapSearch(hmap, &temp_tag);
		assert(it);
#endif
	}
	gettimeofday(&tv2, 0);
	printf("mymap查找用时:%f秒\n", tv2.tv_sec - tv1.tv_sec + (tv2.tv_usec - tv1.tv_usec)/1000000.0);

	printf("max path:%d min path:%d black count:%d count:%d-%d\n",
		MyMapLayer(hmap, 1), MyMapLayer(hmap, 0), MyMapExamin(hmap), count, MyMapGetRealCount(hmap));

	printf("开始删除随机记录\n");
	srand(0/*rand_seed*/);
	count = 0;
	gettimeofday(&tv1, 0);
	for(i = 0; i < LOOP_COUNT; i ++)
	{
#ifndef _DEBUG
		test_map_tag temp_tag = {0};

		getcallid(temp_tag.rand_string, sizeof(temp_tag.rand_string)-1);

		MyMapDelKey(hmap, &temp_tag);
#else
		HMYMAP_ITER it = NULL;
		int flag = 0;
		test_map_tag temp_tag = {0};

		getcallid(temp_tag.rand_string, sizeof(temp_tag.rand_string)-1);

		it = MyMapSearch(hmap, &temp_tag);
		assert(it);
		if(NULL == it)
		{
			int aasdfsdf = 0;
		}
		else
		{
			assert(strcmp(temp_tag.rand_string, ((test_map_tag*)MyMapGetIterData(it, NULL))->rand_string) == 0);
			count ++;
			flag = 1;
		}

		MyMapDelKey(hmap, &temp_tag);

		if(flag)
		{
			int a = 0;
			a = MyMapExamin(hmap);
			printf(".");
		}