File:
[ELWIX - Embedded LightWeight unIX -] /
libaitio /
example /
Attic /
rb.c
Revision
1.2:
download - view:
text,
annotated -
select for diffs -
revision graph
Tue Jun 7 11:49:39 2011 UTC (13 years, 1 month ago) by
misho
Branches:
MAIN
CVS tags:
io3_6,
io3_5,
io3_4,
io3_3,
io3_2,
io3_1,
io2_8,
io2_7,
io2_6,
io2_5,
io2_4,
io2_3,
io2_2,
io2_1,
io2_0,
IO3_5,
IO3_4,
IO3_3,
IO3_2,
IO3_1,
IO3_0,
IO2_7,
IO2_6,
IO2_5,
IO2_4,
IO2_3,
IO2_2,
IO2_1,
IO2_0,
IO1_9,
HEAD
ver 1.9
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