📄 test_myrbtree.c

📁 红黑树生成及应用的算法程序
💻 C
字号:
#include <stdlib.h>
#include <stdio.h>
#include "myrbtree.h"
#include "mylist.h"
#include <time.h>
#include <winsock2.h>
#include <assert.h>

static enum __rbtree_colour
{
	rbtree_colour_black,
	rbtree_colour_red,
};

static 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;
};

static struct __myrbtree_t
{
	struct __myrbtree_node_t * root;

	//内存池
	HMYMEMPOOL hm;

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

int myrbtree_compare1(void * key1, 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 = 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(void * key1, void * key2)
{
	char * actemp = key1;
	char * actemp1 = 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;	}	callid[callid_len - 1] = 0;}
void test_rbtree1()
{
#define CALLID_LEN 32
#define LOOP_COUNT 100000

	HMYRBTREE htree = MyRBTreeConstruct(NULL, myrbtree_compare_string);
	int i = 0;
	int count = 0;
	int temp_test = 0;
	struct __myrbtree_t * temp = htree;

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

	srand(rand_seed);
	for(i = 0; i < LOOP_COUNT; i ++)
	{
		int flag = 0;
		char * actemp =	NULL;
		char * actemp1 = NULL;

		actemp = MyMemPoolMalloc(NULL, CALLID_LEN);
		actemp1 = MyMemPoolMalloc(NULL, CALLID_LEN);
		getcallid(actemp, CALLID_LEN);
		strncpy(actemp1, actemp, CALLID_LEN);

		if(NULL == MyRBTreeSearch(htree, actemp))
		{
			flag = 1;
		}
		else
		{
			flag = 0;
		}

		MyRBTreeInsertUnique(htree, actemp, actemp1);

		if(flag)
		{
			int a = MyRBTreeExamin(htree);
			count ++;
			printf(".");
		}
		else
		{
			printf(" ");
		}
	}

	printf("max path:%d min path:%d black count:%d count:%d-%d\n",
		MyRBTreeLayer(htree, 1), MyRBTreeLayer(htree, 0), MyRBTreeExamin(htree), count, MyRBTreeGetRealCount(htree));

	//{
	//	scanf("\n");
	//}

	printf("开始删除随机记录\n");
	srand(rand_seed);
	count = 0;
	for(i = 0; i < LOOP_COUNT; i ++)
	{
		HMYRBTREE_ITER it = NULL;
		void * data = NULL;
		void * key = NULL;
		int flag = 0;
		char actemp[CALLID_LEN] = {0};
		

		getcallid(actemp, sizeof(actemp));

		it = MyRBTreeSearch(htree, actemp);
		if(NULL == it)
		{
			int aasdfsdf = 0;
		}
		else
		{
			assert(strcmp(actemp, MyRBTreeGetIterData(it)) == 0);
			count ++;
			flag = 1;
		}

		MyRBTreeDelKey(htree, actemp, &key, &data);

		if(flag)
		{
			int a = 0;
			assert(strcmp(actemp, key) == 0);
			a = MyRBTreeExamin(htree);
			printf(".");
		}
		else
		{
			printf(" ");
		}

		if(key)
			MyMemPoolFree(NULL, key);
		if(data)
			MyMemPoolFree(NULL, data);
	}
	printf("black count:%d - %5d - %5d %d\n", MyRBTreeExamin(htree), i, MyRBTreeGetRealCount(htree), count);
	MyMemPoolMemReport();

	MyRBTreeDestruct(htree);
	MyMemPoolMemReport();

	//{
	//	char sdfasdf;
	//	scanf("%c\n", &sdfasdf);
	//}
}

#ifndef MEM_LEAK_CHECK

extern void gettimeofday(struct timeval *ptv, void *tzp);

void test_rbtree()
{
	HMYRBTREE htree = MyRBTreeConstruct(NULL, myrbtree_compare1);
	HMYRBTREE_ITER it = NULL;
	struct timeval tv1;
	struct timeval tv2;
	int i = 0;

	printf("\n开始添加1000k记录\n");
	gettimeofday(&tv1, 0);
	for(i = 0; i < 1000000; i ++)
	{
		MyRBTreeInsertUnique(htree, i, i);
	}
	gettimeofday(&tv2, 0);
	printf("添加用时:%f秒\n", tv2.tv_sec - tv1.tv_sec + (tv2.tv_usec - tv1.tv_usec)/1000000.0);

	printf("添加1000k记录完毕[%d],开始查询\n", MyRBTreeGetRealCount(htree));
	gettimeofday(&tv1, 0);
	for(i = 0; i < 1000000; i ++)
	{
		it = MyRBTreeSearch(htree, i);
	}
	gettimeofday(&tv2, 0);

	printf("查询用时:%f秒\n", tv2.tv_sec - tv1.tv_sec + (tv2.tv_usec - tv1.tv_usec)/1000000.0);

	printf("开始删除1000k记录\n");
	gettimeofday(&tv1, 0);
	for(i = 0; i < 1000000; i ++)
	{
		MyRBTreeDelKey(htree, i, NULL, NULL);
	}
	gettimeofday(&tv2, 0);
	printf("删除1000k记录完毕[%d]\n", MyRBTreeGetRealCount(htree));
	printf("删除用时:%f秒\n", tv2.tv_sec - tv1.tv_sec + (tv2.tv_usec - tv1.tv_usec)/1000000.0);
}

#else

void test_rbtree()
{
	HMYRBTREE htree = MyRBTreeConstruct(NULL, myrbtree_compare1);
	struct __myrbtree_t * temp = htree;
	HMYRBTREE_ITER iter = NULL;
	int i = 0;
	int count = 0;
	int temp_test = 0;

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

	MyRBTreeInsertUnique(htree, (void *)14, (void *)14);
	MyRBTreeInsertUnique(htree, (void *)8, (void *)8);
	MyRBTreeInsertUnique(htree, (void *)3, (void *)3);
	MyRBTreeInsertUnique(htree, (void *)2, (void *)2);
	MyRBTreeInsertUnique(htree, (void *)5, (void *)5);
	MyRBTreeInsertUnique(htree, (void *)10, (void *)10);
	MyRBTreeInsertUnique(htree, (void *)6, (void *)6);
	MyRBTreeInsertUnique(htree, (void *)13, (void *)13);
	MyRBTreeInsertUnique(htree, (void *)4, (void *)4);
	MyRBTreeInsertUnique(htree, (void *)1, (void *)1);
	MyRBTreeInsertUnique(htree, (void *)9, (void *)9);
	MyRBTreeInsertUnique(htree, (void *)7, (void *)7);
	MyRBTreeInsertUnique(htree, (void *)11, (void *)11);
	MyRBTreeInsertUnique(htree, (void *)12, (void *)12);
	MyRBTreeInsertUnique(htree, (void *)15, (void *)15);
	MyRBTreeInsertUnique(htree, (void *)15, (void *)12345);
	printf("black count:%d\n", MyRBTreeExamin(htree));
	printf("max path:%d min path:%d record count:%d\n", MyRBTreeLayer(htree, 1), MyRBTreeLayer(htree, 0), MyRBTreeGetRealCount(htree));
	for(i = 0; i < 16; i ++)
	{
		MyRBTreeDelKey(htree, i, NULL, NULL);
		MyRBTreeExamin(htree);
	}

	printftree(temp->root);

	printf("开始添加随机记录\n");
	srand(rand_seed);
	for(i = 0; i < 400000; i ++)
	{
		unsigned int temp = rand();
		int flag = 0;

		if(NULL == MyRBTreeSearch(htree, (void *)(temp + 16)))
		{
			flag = 1;
		}
		else
		{
			flag = 0;
		}

		MyRBTreeInsertUnique(htree, (void *)(temp + 16), (void *)(temp + 16));

		if(flag)
		{
			MyRBTreeExamin(htree);
			count ++;
			printf(".");
		}
		else
		{
			printf(" ");
		}
	}

	printf("max path:%d min path:%d black count:%d count:%d-%d\n",
		MyRBTreeLayer(htree, 1), MyRBTreeLayer(htree, 0), MyRBTreeExamin(htree), count, MyRBTreeGetRealCount(htree));

#define TEMP_TEST 912	

	iter = MyRBTreeSearch(htree, (void *)TEMP_TEST);
	printf("search TEMP_TEST is %d\n", MyRBTreeGetIterData(iter));

	if(NULL == iter)
	{
		MyRBTreeInsertEqual(htree, (void *)TEMP_TEST, (void *)TEMP_TEST);
		iter = MyRBTreeSearch(htree, (void *)TEMP_TEST);
		printf("search TEMP_TEST is %d\n", MyRBTreeGetIterData(iter));
	}

	printf("black count:%d\n", MyRBTreeExamin(htree));

	{
		void * key;
		void * data;
		MyRBTreeDelKey(htree, TEMP_TEST, &key, &data);
		printf("del %d:%d\n", key, data);
	}

	printf("black count:%d\n", MyRBTreeExamin(htree));

	printf("开始删除随机记录\n");
	srand(rand_seed);
	count = 0;
	for(i = 0; i < 400000; i ++)
	{
		unsigned int temp = rand();
		int flag = 0;

		if(NULL == MyRBTreeSearch(htree, (void *)(temp + 16)))
		{
			int aasdfsdf = 0;
		}
		else
		{
			count ++;
			flag = 1;
		}

		MyRBTreeDelKey(htree, (void *)(temp + 16), NULL, NULL);

		if(flag)
		{
			MyRBTreeExamin(htree);
			printf(".");
		}
		else
		{
			printf(" ");
		}
	}
	printf("black count:%d - %5d - %5d %d\n", MyRBTreeExamin(htree), i, MyRBTreeGetRealCount(htree), count);

#ifdef MEM_LEAK_CHECK
	MyMemPoolMemReport();
#endif

	iter = MyRBTreeSearch(htree, (void *)TEMP_TEST);
	printf("search TEMP_TEST is %d\n", MyRBTreeGetIterData(iter));

	printf("max path:%d min path:%d record count:%d\n", MyRBTreeLayer(htree, 1), MyRBTreeLayer(htree, 0), count);

	temp = htree;

	for(i = 0; i < 16; i ++)
	{
		MyRBTreeDelKey(htree, i, NULL, NULL);
	}

#ifdef MEM_LEAK_CHECK
	MyMemPoolMemReport();
#endif

	MyRBTreeClear(htree);
	MyRBTreeDestruct(htree);

#ifdef MEM_LEAK_CHECK
	MyMemPoolMemReport();
#endif
}

#endif
💿 文件大小 13 K
👤 上传用户 SLing2008
📂 所属分类其他
🏷️ 相关标签

#树 #算法 #程序
⌨️ 快捷键说明

复制代码 Ctrl + C
搜索代码 Ctrl + F
全屏模式 F11
切换主题 Ctrl + Shift + D
显示快捷键 ?
增大字号 Ctrl + =
减小字号 Ctrl + -