Annotation of libaitio/example/rb.c, revision 1.2
1.2 ! misho 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:
! 8: struct blah {
! 9: int n;
! 10: RB_ENTRY(blah) node;
! 11: SPLAY_ENTRY(blah) node1;
! 12: AVL_ENTRY(blah) node2;
! 13: };
! 14: RB_HEAD(rb_head, blah) rbh;
! 15: SPLAY_HEAD(sp_head, blah) sph;
! 16: AVL_HEAD(avl_head, blah) avlh;
! 17:
! 18: static int
! 19: rb_cmp(struct blah *a, struct blah *b)
! 20: {
! 21: int n = (a ? a->n : 0) - (b ? b->n : 0);
! 22:
! 23: if (!n)
! 24: return 0;
! 25: else if (n < 0)
! 26: return -1;
! 27: else
! 28: return 1;
! 29: }
! 30:
! 31: RB_PROTOTYPE(rb_head, blah, node, rb_cmp);
! 32: RB_GENERATE(rb_head, blah, node, rb_cmp);
! 33: SPLAY_PROTOTYPE(sp_head, blah, node1, rb_cmp);
! 34: SPLAY_GENERATE(sp_head, blah, node1, rb_cmp);
! 35: AVL_PROTOTYPE(avl_head, blah, node2, rb_cmp)
! 36: AVL_GENERATE(avl_head, blah, node2, rb_cmp)
! 37:
! 38:
! 39: int
! 40: main()
! 41: {
! 42: struct blah *b, *b2;
! 43: register int i;
! 44: struct timeval before, after;
! 45:
! 46: RB_INIT(&rbh);
! 47: SPLAY_INIT(&sph);
! 48: AVL_INIT(&avlh, 0);
! 49: srandom(getpid());
! 50:
! 51: gettimeofday(&before, NULL);
! 52: for (i = 0; i < 1000000; i++) {
! 53: b = malloc(sizeof(struct blah));
! 54: memset(b, 0, sizeof(struct blah));
! 55: b->n = random();
! 56: if (RB_INSERT(rb_head, &rbh, b))
! 57: free(b);
! 58: }
! 59: gettimeofday(&after, NULL);
! 60: printf("RB::Time %f\n", (after.tv_sec - before.tv_sec) + (after.tv_usec - before.tv_usec) / 1e6);
! 61: gettimeofday(&before, NULL);
! 62: for (i = 0; i < 1000000; i++) {
! 63: b = malloc(sizeof(struct blah));
! 64: memset(b, 0, sizeof(struct blah));
! 65: b->n = random();
! 66: if (SPLAY_INSERT(sp_head, &sph, b))
! 67: free(b);
! 68: }
! 69: gettimeofday(&after, NULL);
! 70: printf("SP::Time %f\n", (after.tv_sec - before.tv_sec) + (after.tv_usec - before.tv_usec) / 1e6);
! 71:
! 72: gettimeofday(&before, NULL);
! 73: for (i = 0; i < 1000000; i++) {
! 74: b = malloc(sizeof(struct blah));
! 75: memset(b, 0, sizeof(struct blah));
! 76: b->n = random();
! 77: if (AVL_INSERT(avl_head, &avlh, b))
! 78: free(b);
! 79: }
! 80: gettimeofday(&after, NULL);
! 81: printf("AVL::Time %f\n", (after.tv_sec - before.tv_sec) + (after.tv_usec - before.tv_usec) / 1e6);
! 82:
! 83: printf("---\n");
! 84:
! 85: b2 = malloc(sizeof(struct blah));
! 86: gettimeofday(&before, NULL);
! 87: for (i = 0; i < 10000; i++) {
! 88: memset(b2, 0, sizeof(struct blah));
! 89: b2->n = random();
! 90: b = SPLAY_FIND(sp_head, &sph, b2);
! 91: if (b)
! 92: printf("SP::Found key %d(%s) -> %d\n", i, RB_COLOR(b, node) == RB_BLACK ? "black" : "red", b->n);
! 93: }
! 94: gettimeofday(&after, NULL);
! 95: printf("SP::Time %f\n", (after.tv_sec - before.tv_sec) + (after.tv_usec - before.tv_usec) / 1e6);
! 96:
! 97: printf("---\n");
! 98:
! 99: gettimeofday(&before, NULL);
! 100: for (i = 0; i < 10000; i++) {
! 101: memset(b2, 0, sizeof(struct blah));
! 102: b2->n = random();
! 103: b = RB_FIND(rb_head, &rbh, b2);
! 104: if (b)
! 105: printf("RB::Found key %d(%s) -> %d\n", i, RB_COLOR(b, node) == RB_BLACK ? "black" : "red", b->n);
! 106: }
! 107: gettimeofday(&after, NULL);
! 108: printf("RB::Time %f\n", (after.tv_sec - before.tv_sec) + (after.tv_usec - before.tv_usec) / 1e6);
! 109: free(b2);
! 110:
! 111: printf("---\n");
! 112:
! 113: b2 = malloc(sizeof(struct blah));
! 114: gettimeofday(&before, NULL);
! 115: for (i = 0; i < 10000; i++) {
! 116: memset(b2, 0, sizeof(struct blah));
! 117: b2->n = random();
! 118: b = AVL_FIND(avl_head, &avlh, b2);
! 119: if (b)
! 120: printf("AVL::Found key %d %d-> %d next=%d prev=%d\n", i, b2->n, b->n,
! 121: AVL_NEXT(avl_head, &avlh, b) ? AVL_NEXT(avl_head, &avlh, b)->n : 0,
! 122: AVL_PREV(avl_head, &avlh, b) ? AVL_PREV(avl_head, &avlh, b)->n : 0);
! 123: }
! 124: gettimeofday(&after, NULL);
! 125: printf("AVL::Time %f\n", (after.tv_sec - before.tv_sec) + (after.tv_usec - before.tv_usec) / 1e6);
! 126:
! 127: printf("---\n");
! 128:
! 129: gettimeofday(&before, NULL);
! 130: AVL_FOREACH_SAFE(b, avl_head, &avlh, b2) {
! 131: /*
! 132: printf("aaa %p[%d] %p[%d] --- ", b, b ? b->n : 0, b2, b2 ? b2->n : 0);
! 133: printf("b:%p %p /// ", b ? AVL_LEFT(b, node2) : b, b ? AVL_RIGHT(b, node2) : b);
! 134: printf("b2:%p %p\n", b2 ? AVL_LEFT(b2, node2) : b2, b2 ? AVL_RIGHT(b2, node2) : b2); fflush(stdout);
! 135: */
! 136: AVL_REMOVE(avl_head, &avlh, b);
! 137: free(b);
! 138: }
! 139: gettimeofday(&after, NULL);
! 140: printf("AVL::Time %f\n", (after.tv_sec - before.tv_sec) + (after.tv_usec - before.tv_usec) / 1e6);
! 141: gettimeofday(&before, NULL);
! 142: for (b = SPLAY_MIN(sp_head, &sph); b; b = b2) {
! 143: b2 = SPLAY_NEXT(sp_head, &sph, b);
! 144: SPLAY_REMOVE(sp_head, &sph, b);
! 145: }
! 146: gettimeofday(&after, NULL);
! 147: printf("SP::Time %f\n", (after.tv_sec - before.tv_sec) + (after.tv_usec - before.tv_usec) / 1e6);
! 148:
! 149: gettimeofday(&before, NULL);
! 150: RB_FOREACH_SAFE(b, rb_head, &rbh, b2) {
! 151: RB_REMOVE(rb_head, &rbh, b);
! 152: free(b);
! 153: }
! 154: gettimeofday(&after, NULL);
! 155: printf("RB::Time %f\n", (after.tv_sec - before.tv_sec) + (after.tv_usec - before.tv_usec) / 1e6);
! 156: return !AVL_EMPTY(&avlh);
! 157: }
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to rb.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / libaitio / example