Annotation of libelwix/example/rb.c, revision 1.2
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++) {
1.2 ! misho 59: b = e_malloc(sizeof(struct blah));
1.1 misho 60: memset(b, 0, sizeof(struct blah));
61: b->n = random();
62: if (RB_INSERT(rb_head, &rbh, b))
1.2 ! misho 63: e_free(b);
1.1 misho 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++) {
1.2 ! misho 69: b = e_malloc(sizeof(struct blah));
1.1 misho 70: memset(b, 0, sizeof(struct blah));
71: b->n = random();
72: if (SPLAY_INSERT(sp_head, &sph, b))
1.2 ! misho 73: e_free(b);
1.1 misho 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++) {
1.2 ! misho 80: b = e_malloc(sizeof(struct blah));
1.1 misho 81: memset(b, 0, sizeof(struct blah));
82: b->n = random();
83: if (AVL_INSERT(avl_head, &avlh, b))
1.2 ! misho 84: e_free(b);
1.1 misho 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++) {
1.2 ! misho 91: b = e_malloc(sizeof(struct blah));
1.1 misho 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++) {
1.2 ! misho 100: b = e_malloc(sizeof(struct blah));
1.1 misho 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:
1.2 ! misho 110: b2 = e_malloc(sizeof(struct blah));
1.1 misho 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:
1.2 ! misho 152: e_free(b2);
1.1 misho 153:
154: gettimeofday(&before, NULL);
155: while ((b = TAILQ_FIRST(&tqh))) {
156: TAILQ_REMOVE(&tqh, b, node4);
1.2 ! misho 157: e_free(b);
1.1 misho 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);
1.2 ! misho 164: e_free(b);
1.1 misho 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: printf("aaa %p[%d] %p[%d] --- ", b, b ? b->n : 0, b2, b2 ? b2->n : 0);
172: printf("b:%p %p /// ", b ? AVL_LEFT(b, node2) : b, b ? AVL_RIGHT(b, node2) : b);
173: printf("b2:%p %p\n", b2 ? AVL_LEFT(b2, node2) : b2, b2 ? AVL_RIGHT(b2, node2) : b2); fflush(stdout);
174: AVL_REMOVE(avl_head, &avlh, b);
1.2 ! misho 175: e_free(b);
1.1 misho 176: }
177: gettimeofday(&after, NULL);
178: printf("AVL::Time %f\n", (after.tv_sec - before.tv_sec) + (after.tv_usec - before.tv_usec) / 1e6);
179:
180: gettimeofday(&before, NULL);
181: for (b = SPLAY_MIN(sp_head, &sph); b; b = b2) {
182: b2 = SPLAY_NEXT(sp_head, &sph, b);
183: SPLAY_REMOVE(sp_head, &sph, b);
184: }
185: gettimeofday(&after, NULL);
186: printf("SP::Time %f\n", (after.tv_sec - before.tv_sec) + (after.tv_usec - before.tv_usec) / 1e6);
187:
188: gettimeofday(&before, NULL);
189: RB_FOREACH_SAFE(b, rb_head, &rbh, b2) {
1.2 ! misho 190: printf("aaa %p[%d] %p[%d] --- ", b, b ? b->n : 0, b2, b2 ? b2->n : 0);
! 191: printf("b:%p %p /// ", b ? RB_LEFT(b, node) : b, b ? RB_RIGHT(b, node) : b);
! 192: printf("b2:%p %p\n", b2 ? RB_LEFT(b2, node) : b2, b2 ? RB_RIGHT(b2, node) : b2); fflush(stdout);
1.1 misho 193: RB_REMOVE(rb_head, &rbh, b);
1.2 ! misho 194: e_free(b);
1.1 misho 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 -] / libelwix / example