通用红黑树Tree-Map容器纯C实现

纯C实现的通用红黑树容器不好找，于是自己琢磨着实现了一个。 算法部分直接剪裁自Linux内核中的rbtree 作者主要是在此基础上封装了一个通用的容器 里面含有 test例子 以及 benchmark基准测试 另外这个是Windows和Linux都可以用的 由于Linux内核的rbtree用了很多C99语法，笔者还得写了一些宏改造内核代码 Linux下的make是完整的 Windows下提供了VS08版的sln文件（只有test木有benchmark） 附带了一个C++里面的STL Map的benchmark

#include 
#include 
#include 
#include 

#include 

#include “rbtree_container.h“

#define TEST_SIZE 100000

#define SRAND 0x1234
//#define SRAND （time（NULL））

int compare（void *key1 void *key2）
{
	return *（（int*）key1） - *（（int*）key2）; 
}

int main（void）
{
	rbtree_container tree;
	rbtree_container_node *pc *apc[TEST_SIZE];
	int i ret insert_failed find find_failed tree_size;
	struct timeval begin end;
	
	rbtree_container_init（&tree sizeof（int） compare）;
	
	printf（“rbtree_container benchmark go ... \n\n“）;
	
	srand（SRAND）;
	
	/*
	 * 内存分配
	 */
	
	printf（“malloc %d times...\n“ TEST_SIZE）;
	
	gettimeofday（&begin NULL）;
	
	for（i=0; i	{
		apc[i] = rbtree_container_node_malloc（&tree 4）;
	}
	
	gettimeofday（&end NULL）;

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     目录           0  2012-08-05 14:14  rbtree_container\
     文件        3149  2012-07-29 14:40  rbtree_container\benchmark.c
     文件         859  2012-07-29 14:49  rbtree_container\Makefile
     文件       10283  2012-07-27 18:46  rbtree_container\rbtree.c
     文件        5967  2012-08-05 14:10  rbtree_container\rbtree.h
     文件        3850  2012-08-05 14:05  rbtree_container\rbtree_container.c
     文件        2820  2012-08-05 16:01  rbtree_container\rbtree_container.h
     文件         900  2012-08-05 14:12  rbtree_container\rbtree_container.sln
     文件        2120  2012-07-29 14:39  rbtree_container\STL_map_benchmark.cpp
     文件        5268  2012-07-29 01:45  rbtree_container\test.c
     目录           0  2012-08-05 14:13  rbtree_container\vs\
     文件        3921  2012-08-05 14:06  rbtree_container\vs\rbtree_container.vcproj