rbtmain.c

p2p类源代码 kadc协议官方源代码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <KadCalloc.h>
#include <rbt.h>

int rbtmain_compLT(void *a, void *b) {
	return (*((int *)(a)) < *((int *)(b)));
}

int rbtmain_compEQ(void *a, void *b) {
	return (*((int *)(a)) == *((int *)(b)));
}

int *newint(int value) {
	int *pint = malloc(sizeof(int));
	if(pint == NULL) {
		printf("no memory\n");
		exit(-1);
	}
	*pint = value;
	return pint;
}

int main(int argc, char *argv[]) {
	int maxnum, ct, duplicatesOK = 0;
	int *prec;
	int *pkey;
	int key_to_find;
	rbt_StatusEnum status;
/* assumed maximum depth of a node even for large tables */
#define RANGE 40
#define VRANGE 16
	int hist[RANGE];
	int maxhist, peakdepth, maxdepth, mindepth;

	/* command-line:
	 *
	 *   rbt maxnum
	 *
	 *   rbt 2000
	 *	   process 2000 records
	 *
	 */

	void *rbt;
	void *iter;

	memset(hist, 0, sizeof(hist));
	maxhist = 0;
	maxdepth = 0;
	mindepth = 1000; /* or MAXINT, or whatever */

	if(argc <= 1) {
		printf("usage: %s maxnum [key_to_find [duplicatesOK]]\n", argv[0]);
		exit(1);
	}

	maxnum = atoi(argv[1]);
	printf("maxnum = %d\n", maxnum);

	if(argc > 2)
		key_to_find = atoi(argv[2]);
	else
		key_to_find = 0;

	if(argc > 3) {
		duplicatesOK = 1;
		printf("duplicate keys are allowed\n");
	}

//	rbt = rbt_new(&rbtmain_compLT, &rbtmain_compEQ, &realloc);
	rbt = rbt_new(&rbtmain_compLT, &rbtmain_compEQ);

	for (ct = maxnum; ct; ct--) {
		/* generate a int key */
		if(duplicatesOK)
			pkey = newint((rand() % 90) + 1); /* force duplications */
		else
			pkey = newint( rand() );

		if (!duplicatesOK && ((status = rbt_find(rbt, pkey, &iter)) == RBT_STATUS_OK)) { /* if already there */
			prec = rbt_value(iter);
			if (!rbtmain_compEQ(prec, pkey)) /*...should have value == key... */
				printf("fail rec: *prec = %d, *pkey = %d\n", *(int *)prec, *(int *)pkey);
//			printf("removing %d\n", *pkey);
			free(rbt_value(iter));
			free(rbt_key(iter));
			free(pkey);
			status = rbt_erase(rbt, iter); /* ...then delete entry */
			if (status) printf("rbt_erase fail: status = %d\n", status);
		} else {
			prec = newint(*(int *)pkey);
//			printf("inserting %d\n", *pkey);
			status = rbt_insert(rbt, pkey, prec, duplicatesOK); /* ...else add entry w/ value == key */
			if (status) printf("rbt_insert fail: status = %d\n", status);
		}
	}

	/* output nodes in order */
	{
		void *iter;

		status = rbt_find(rbt, &key_to_find, &iter);
		if (status) {
			if(iter != NULL)
			printf("key %d not found: next was %d with value %d\n",
					key_to_find, *(int *)rbt_key(iter), *(int *)rbt_value(iter));
			else
				printf("key %d not found: no next\n",
					key_to_find);
		}
		while (iter != NULL) {
			int *prec;
			int depth;
			int curhist;

			// if(rbt_isleaf(rbt, iter)) { /* add this to measure only leaf nodes */
				depth = rbt_depth(rbt, iter);
				if(depth >= RANGE)
					depth = RANGE-1;	/* just in case, to prevent buffer overflows */
				if(depth > maxdepth)
					maxdepth = depth;
				if(depth < mindepth)
					mindepth = depth;
				hist[depth]++;
				curhist = hist[depth];
				if(curhist > maxhist) {
					maxhist = curhist;
					peakdepth = depth;
				}
			//}

			prec = rbt_value(iter);
//			printf("%d had depth %d\n", *(int *)prec, depth);
			iter = rbt_next(rbt, iter);
		}
	}

	{
		void *iter;

	/* list table begin to end */
		printf("list in ascending order:\n");
		for(iter = rbt_begin(rbt); iter != NULL; iter = rbt_next(rbt, iter)) {
				printf("K = %5d V = %5d\n", *(int *)rbt_key(iter), *(int *)rbt_value(iter));
		}

	/* list table end to begin */
		printf("list in descending order:\n");
		for(iter = rbt_end(rbt); iter != NULL; iter = rbt_previous(rbt, iter)) {
				printf("K = %5d V = %5d\n", *(int *)rbt_key(iter), *(int *)rbt_value(iter));
		}

	}
	/* destroy table */

	{
		void *iter;
		void *p;
		rbt_StatusEnum s;

		for(iter = rbt_begin(rbt); iter != NULL; iter = rbt_next(rbt, iter)) {
			if((p = rbt_key(iter)) != NULL) free(p);
			if((p = rbt_value(iter)) != NULL) free(p);
			s = rbt_erase(rbt, iter);
			if(s != RBT_STATUS_OK)
				printf("rbt_erase(rbt, iter) returned %d\n", s);
		}
		free(rbt);


	}
	{
		int i,j;
		printf("Max tree depth: %d min depth: %d most common depth: %d (%2d%% of total)",
				maxdepth, mindepth, peakdepth, maxhist*100/maxnum);
		for(j=VRANGE; j>=0; j--) {
			for(i=0; i<RANGE; i++)  {
				if(hist[i]*VRANGE/maxhist > j) {
					printf("*");
				} else {
					printf(" ");
				}
			}
			printf("\n");
		}
	}

	printf("malloc() called %d times, free() called %d times.\n",
			malloc_cnt, free_cnt);
	return 0;
}