Return to rb2.c CVS log

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

ELWIX core library

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