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