Annotation of libelwix/example/rb.c, revision 1.1
1.1 ! misho 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: TAILQ_ENTRY(blah) node4;
! 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: TAILQ_HEAD(, blah) tqh;
! 21:
! 22: static int
! 23: rb_cmp(struct blah *a, struct blah *b)
! 24: {
! 25: int n = (a ? a->n : 0) - (b ? b->n : 0);
! 26:
! 27: if (!n)
! 28: return 0;
! 29: else if (n < 0)
! 30: return -1;
! 31: else
! 32: return 1;
! 33: }
! 34:
! 35: RB_PROTOTYPE(rb_head, blah, node, rb_cmp);
! 36: RB_GENERATE(rb_head, blah, node, rb_cmp);
! 37: SPLAY_PROTOTYPE(sp_head, blah, node1, rb_cmp);
! 38: SPLAY_GENERATE(sp_head, blah, node1, rb_cmp);
! 39: AVL_PROTOTYPE(avl_head, blah, node2, rb_cmp)
! 40: AVL_GENERATE(avl_head, blah, node2, rb_cmp)
! 41:
! 42:
! 43: int
! 44: main()
! 45: {
! 46: struct blah *b, *b2;
! 47: register int i;
! 48: struct timeval before, after;
! 49:
! 50: RB_INIT(&rbh);
! 51: SPLAY_INIT(&sph);
! 52: AVL_INIT(&avlh);
! 53: SLIST_INIT(&slh);
! 54: TAILQ_INIT(&tqh);
! 55: srandom(getpid());
! 56:
! 57: gettimeofday(&before, NULL);
! 58: for (i = 0; i < 1000000; i++) {
! 59: b = malloc(sizeof(struct blah));
! 60: memset(b, 0, sizeof(struct blah));
! 61: b->n = random();
! 62: if (RB_INSERT(rb_head, &rbh, b))
! 63: free(b);
! 64: }
! 65: gettimeofday(&after, NULL);
! 66: printf("RB::Time %f\n", (after.tv_sec - before.tv_sec) + (after.tv_usec - before.tv_usec) / 1e6);
! 67: gettimeofday(&before, NULL);
! 68: for (i = 0; i < 1000000; i++) {
! 69: b = malloc(sizeof(struct blah));
! 70: memset(b, 0, sizeof(struct blah));
! 71: b->n = random();
! 72: if (SPLAY_INSERT(sp_head, &sph, b))
! 73: free(b);
! 74: }
! 75: gettimeofday(&after, NULL);
! 76: printf("SP::Time %f\n", (after.tv_sec - before.tv_sec) + (after.tv_usec - before.tv_usec) / 1e6);
! 77:
! 78: gettimeofday(&before, NULL);
! 79: for (i = 0; i < 1000000; i++) {
! 80: b = malloc(sizeof(struct blah));
! 81: memset(b, 0, sizeof(struct blah));
! 82: b->n = random();
! 83: if (AVL_INSERT(avl_head, &avlh, b))
! 84: free(b);
! 85: }
! 86: gettimeofday(&after, NULL);
! 87: printf("AVL::Time %f\n", (after.tv_sec - before.tv_sec) + (after.tv_usec - before.tv_usec) / 1e6);
! 88:
! 89: gettimeofday(&before, NULL);
! 90: for (i = 0; i < 1000000; i++) {
! 91: b = malloc(sizeof(struct blah));
! 92: memset(b, 0, sizeof(struct blah));
! 93: b->n = random();
! 94: SLIST_INSERT_HEAD(&slh, b, node3);
! 95: }
! 96: gettimeofday(&after, NULL);
! 97: printf("SLIST::Time %f\n", (after.tv_sec - before.tv_sec) + (after.tv_usec - before.tv_usec) / 1e6);
! 98: gettimeofday(&before, NULL);
! 99: for (i = 0; i < 1000000; i++) {
! 100: b = malloc(sizeof(struct blah));
! 101: memset(b, 0, sizeof(struct blah));
! 102: b->n = random();
! 103: TAILQ_INSERT_HEAD(&tqh, b, node4);
! 104: }
! 105: gettimeofday(&after, NULL);
! 106: printf("TAILQ::Time %f\n", (after.tv_sec - before.tv_sec) + (after.tv_usec - before.tv_usec) / 1e6);
! 107:
! 108: printf("---\n");
! 109:
! 110: b2 = malloc(sizeof(struct blah));
! 111: gettimeofday(&before, NULL);
! 112: for (i = 0; i < 10000; i++) {
! 113: memset(b2, 0, sizeof(struct blah));
! 114: b2->n = random();
! 115: b = SPLAY_FIND(sp_head, &sph, b2);
! 116: if (b)
! 117: printf("SP::Found key %d(%s) -> %d\n", i, RB_COLOR(b, node) == RB_BLACK ? "black" : "red", b->n);
! 118: }
! 119: gettimeofday(&after, NULL);
! 120: printf("SP::Time %f\n", (after.tv_sec - before.tv_sec) + (after.tv_usec - before.tv_usec) / 1e6);
! 121:
! 122: printf("---\n");
! 123:
! 124: gettimeofday(&before, NULL);
! 125: for (i = 0; i < 10000; i++) {
! 126: memset(b2, 0, sizeof(struct blah));
! 127: b2->n = random();
! 128: b = RB_FIND(rb_head, &rbh, b2);
! 129: if (b)
! 130: printf("RB::Found key %d(%s) -> %d\n", i, RB_COLOR(b, node) == RB_BLACK ? "black" : "red", b->n);
! 131: }
! 132: gettimeofday(&after, NULL);
! 133: printf("RB::Time %f\n", (after.tv_sec - before.tv_sec) + (after.tv_usec - before.tv_usec) / 1e6);
! 134:
! 135: printf("---\n");
! 136:
! 137: gettimeofday(&before, NULL);
! 138: for (i = 0; i < 10000; i++) {
! 139: memset(b2, 0, sizeof(struct blah));
! 140: b2->n = random();
! 141: b = AVL_FIND(avl_head, &avlh, b2);
! 142: if (b)
! 143: printf("AVL::Found key %d %d-> %d next=%d prev=%d\n", i, b2->n, b->n,
! 144: AVL_NEXT(avl_head, &avlh, b) ? AVL_NEXT(avl_head, &avlh, b)->n : 0,
! 145: AVL_PREV(avl_head, &avlh, b) ? AVL_PREV(avl_head, &avlh, b)->n : 0);
! 146: }
! 147: gettimeofday(&after, NULL);
! 148: printf("AVL::Time %f\n", (after.tv_sec - before.tv_sec) + (after.tv_usec - before.tv_usec) / 1e6);
! 149:
! 150: printf("---\n");
! 151:
! 152: free(b2);
! 153:
! 154: gettimeofday(&before, NULL);
! 155: while ((b = TAILQ_FIRST(&tqh))) {
! 156: TAILQ_REMOVE(&tqh, b, node4);
! 157: free(b);
! 158: }
! 159: gettimeofday(&after, NULL);
! 160: printf("TAILQ::Time %f\n", (after.tv_sec - before.tv_sec) + (after.tv_usec - before.tv_usec) / 1e6);
! 161: gettimeofday(&before, NULL);
! 162: while ((b = SLIST_FIRST(&slh))) {
! 163: SLIST_REMOVE(&slh, b, blah, node3);
! 164: free(b);
! 165: }
! 166: gettimeofday(&after, NULL);
! 167: printf("SLIST::Time %f\n", (after.tv_sec - before.tv_sec) + (after.tv_usec - before.tv_usec) / 1e6);
! 168:
! 169: gettimeofday(&before, NULL);
! 170: AVL_FOREACH_SAFE(b, avl_head, &avlh, b2) {
! 171: /*
! 172: printf("aaa %p[%d] %p[%d] --- ", b, b ? b->n : 0, b2, b2 ? b2->n : 0);
! 173: printf("b:%p %p /// ", b ? AVL_LEFT(b, node2) : b, b ? AVL_RIGHT(b, node2) : b);
! 174: printf("b2:%p %p\n", b2 ? AVL_LEFT(b2, node2) : b2, b2 ? AVL_RIGHT(b2, node2) : b2); fflush(stdout);
! 175: */
! 176: AVL_REMOVE(avl_head, &avlh, b);
! 177: free(b);
! 178: }
! 179: gettimeofday(&after, NULL);
! 180: printf("AVL::Time %f\n", (after.tv_sec - before.tv_sec) + (after.tv_usec - before.tv_usec) / 1e6);
! 181:
! 182: gettimeofday(&before, NULL);
! 183: for (b = SPLAY_MIN(sp_head, &sph); b; b = b2) {
! 184: b2 = SPLAY_NEXT(sp_head, &sph, b);
! 185: SPLAY_REMOVE(sp_head, &sph, b);
! 186: }
! 187: gettimeofday(&after, NULL);
! 188: printf("SP::Time %f\n", (after.tv_sec - before.tv_sec) + (after.tv_usec - before.tv_usec) / 1e6);
! 189:
! 190: gettimeofday(&before, NULL);
! 191: RB_FOREACH_SAFE(b, rb_head, &rbh, b2) {
! 192: RB_REMOVE(rb_head, &rbh, b);
! 193: free(b);
! 194: }
! 195: gettimeofday(&after, NULL);
! 196: printf("RB::Time %f\n", (after.tv_sec - before.tv_sec) + (after.tv_usec - before.tv_usec) / 1e6);
! 197: return !AVL_EMPTY(&avlh);
! 198: }
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 -] / libelwix / example