Return to rb2.c CVS log

Up to [ELWIX - Embedded LightWeight unIX -] / libaitio / example

version 3.6

    1: #include <stdio.h>
    2: #include <stdlib.h>
    3: #include <string.h>
    4: #include <unistd.h>
    5: #include <atree.h>
    6: #include <sys/time.h>
    7: #include <sys/queue.h>
    8: 
    9: struct blah {
   10: 	int n;
   11: 	RB_ENTRY(blah) node;
   12: 	SPLAY_ENTRY(blah) node1;
   13: 	AVL_ENTRY(blah) node2;
   14: 	SLIST_ENTRY(blah) node3;
   15: };
   16: RB_HEAD(rb_head, blah) rbh;
   17: SPLAY_HEAD(sp_head, blah) sph;
   18: AVL_HEAD(avl_head, blah) avlh;
   19: SLIST_HEAD(, blah) slh;
   20: 
   21: static int
   22: rb_cmp(struct blah *a, struct blah *b)
   23: {
   24: 	int n = (a ? a->n : 0) - (b ? b->n : 0);
   25: 
   26: 	if (!n)
   27: 		return 0;
   28: 	else if (n < 0)
   29: 		return -1;
   30: 	else
   31: 		return 1;
   32: }
   33: 
   34: RB_PROTOTYPE(rb_head, blah, node, rb_cmp);
   35: RB_GENERATE(rb_head, blah, node, rb_cmp);
   36: SPLAY_PROTOTYPE(sp_head, blah, node1, rb_cmp);
   37: SPLAY_GENERATE(sp_head, blah, node1, rb_cmp);
   38: AVL_PROTOTYPE(avl_head, blah, node2, rb_cmp)
   39: AVL_GENERATE(avl_head, blah, node2, rb_cmp)
   40: 
   41: 
   42: int
   43: main()
   44: {
   45: 	struct blah *b, *b2;
   46: 	register int i;
   47: 	struct timeval before, after;
   48: 
   49: 	RB_INIT(&rbh);
   50: 	SPLAY_INIT(&sph);
   51: 	AVL_INIT(&avlh);
   52: 	SLIST_INIT(&slh);
   53: 	srandom(getpid());
   54: 
   55: 	for (i = 0; i < 100000; i++) {
   56: 		b = malloc(sizeof(struct blah));
   57: 		memset(b, 0, sizeof(struct blah));
   58: 		b->n = random();
   59: 		SLIST_INSERT_HEAD(&slh, b, node3);
   60: 	}
   61: 
   62: 	gettimeofday(&before, NULL);
   63: 	SLIST_FOREACH(b, &slh, node3)
   64: 		RB_INSERT(rb_head, &rbh, b);
   65: 	gettimeofday(&after, NULL);
   66: 	printf("RB::Time %f\n", (after.tv_sec - before.tv_sec) + (after.tv_usec - before.tv_usec) / 1e6);
   67: 
   68: 	gettimeofday(&before, NULL);
   69: 	SLIST_FOREACH(b, &slh, node3)
   70: 		SPLAY_INSERT(sp_head, &sph, b);
   71: 	gettimeofday(&after, NULL);
   72: 	printf("SP::Time %f\n", (after.tv_sec - before.tv_sec) + (after.tv_usec - before.tv_usec) / 1e6);
   73: 
   74: 	gettimeofday(&before, NULL);
   75: 	SLIST_FOREACH(b, &slh, node3)
   76: 		AVL_INSERT(avl_head, &avlh, b);
   77: 	gettimeofday(&after, NULL);
   78: 	printf("AVL::Time %f\n", (after.tv_sec - before.tv_sec) + (after.tv_usec - before.tv_usec) / 1e6);
   79: 
   80: 	printf("---\n");
   81: 
   82: 	b2 = malloc(sizeof(struct blah));
   83: 
   84: 	gettimeofday(&before, NULL);
   85: 	for (i = 0; i < 20000; i++) {
   86: 		memset(b2, 0, sizeof(struct blah));
   87: 		b2->n = random();
   88: 		b = SPLAY_FIND(sp_head, &sph, b2);
   89: 		if (b)
   90: 			printf("SP::Found key %d -> %d\n", i, b->n);
   91: 	}
   92: 	gettimeofday(&after, NULL);
   93: 	printf("SP::Time %f\n", (after.tv_sec - before.tv_sec) + (after.tv_usec - before.tv_usec) / 1e6);
   94: 
   95: 	printf("---\n");
   96: 
   97: 	gettimeofday(&before, NULL);
   98: 	for (i = 0; i < 20000; i++) {
   99: 		memset(b2, 0, sizeof(struct blah));
  100: 		b2->n = random();
  101: 		b = RB_FIND(rb_head, &rbh, b2);
  102: 		if (b)
  103: 			printf("RB::Found key %d -> %d\n", i, b->n);
  104: 	}
  105: 	gettimeofday(&after, NULL);
  106: 	printf("RB::Time %f\n", (after.tv_sec - before.tv_sec) + (after.tv_usec - before.tv_usec) / 1e6);
  107: 
  108: 	printf("---\n");
  109: 
  110: 	gettimeofday(&before, NULL);
  111: 	for (i = 0; i < 20000; i++) {
  112: 		memset(b2, 0, sizeof(struct blah));
  113: 		b2->n = random();
  114: 		b = AVL_FIND(avl_head, &avlh, b2);
  115: 		if (b)
  116: 			printf("AVL::Found key %d -> %d\n", i, b->n);
  117: 	}
  118: 	gettimeofday(&after, NULL);
  119: 	printf("AVL::Time %f\n", (after.tv_sec - before.tv_sec) + (after.tv_usec - before.tv_usec) / 1e6);
  120: 
  121: 	printf("---\n");
  122: 
  123: 	free(b2);
  124: 
  125: 	gettimeofday(&before, NULL);
  126: 	AVL_FOREACH_SAFE(b, avl_head, &avlh, b2)
  127: 		AVL_REMOVE(avl_head, &avlh, b);
  128: 	gettimeofday(&after, NULL);
  129: 	printf("AVL::Time %f\n", (after.tv_sec - before.tv_sec) + (after.tv_usec - before.tv_usec) / 1e6);
  130: 
  131: 	gettimeofday(&before, NULL);
  132: 	SPLAY_FOREACH_SAFE(b, sp_head, &sph, b2)
  133: 		SPLAY_REMOVE(sp_head, &sph, b);
  134: 	gettimeofday(&after, NULL);
  135: 	printf("SP::Time %f\n", (after.tv_sec - before.tv_sec) + (after.tv_usec - before.tv_usec) / 1e6);
  136: 
  137: 	gettimeofday(&before, NULL);
  138: 	RB_FOREACH_SAFE(b, rb_head, &rbh, b2)
  139: 		RB_REMOVE(rb_head, &rbh, b);
  140: 	gettimeofday(&after, NULL);
  141: 	printf("RB::Time %f\n", (after.tv_sec - before.tv_sec) + (after.tv_usec - before.tv_usec) / 1e6);
  142: 
  143: 	gettimeofday(&before, NULL);
  144: 	while ((b = SLIST_FIRST(&slh))) {
  145: 		SLIST_REMOVE(&slh, b, blah, node3);
  146: 		free(b);
  147: 	}
  148: 	gettimeofday(&after, NULL);
  149: 	printf("SLIST::Time %f\n", (after.tv_sec - before.tv_sec) + (after.tv_usec - before.tv_usec) / 1e6);
  150: 	return !AVL_EMPTY(&avlh);
  151: }