File:
[ELWIX - Embedded LightWeight unIX -] /
libaitio /
example /
Attic /
rb2.c
Revision
1.2:
download - view:
text,
annotated -
select for diffs -
revision graph
Wed Aug 29 13:51:29 2012 UTC (11 years, 11 months ago) by
misho
Branches:
MAIN
CVS tags:
io5_0,
io4_1,
io4_0,
io3_9,
io3_8,
io3_7,
IO4_1,
IO4_0,
IO3_9,
IO3_8,
IO3_7,
IO3_6,
HEAD
version 3.6
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: #include <sys/queue.h>
8:
9: struct blah {
10: int n;
11: RB_ENTRY(blah) node;
12: SPLAY_ENTRY(blah) node1;
13: AVL_ENTRY(blah) node2;
14: SLIST_ENTRY(blah) node3;
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:
21: static int
22: rb_cmp(struct blah *a, struct blah *b)
23: {
24: int n = (a ? a->n : 0) - (b ? b->n : 0);
25:
26: if (!n)
27: return 0;
28: else if (n < 0)
29: return -1;
30: else
31: return 1;
32: }
33:
34: RB_PROTOTYPE(rb_head, blah, node, rb_cmp);
35: RB_GENERATE(rb_head, blah, node, rb_cmp);
36: SPLAY_PROTOTYPE(sp_head, blah, node1, rb_cmp);
37: SPLAY_GENERATE(sp_head, blah, node1, rb_cmp);
38: AVL_PROTOTYPE(avl_head, blah, node2, rb_cmp)
39: AVL_GENERATE(avl_head, blah, node2, rb_cmp)
40:
41:
42: int
43: main()
44: {
45: struct blah *b, *b2;
46: register int i;
47: struct timeval before, after;
48:
49: RB_INIT(&rbh);
50: SPLAY_INIT(&sph);
51: AVL_INIT(&avlh);
52: SLIST_INIT(&slh);
53: srandom(getpid());
54:
55: for (i = 0; i < 100000; i++) {
56: b = malloc(sizeof(struct blah));
57: memset(b, 0, sizeof(struct blah));
58: b->n = random();
59: SLIST_INSERT_HEAD(&slh, b, node3);
60: }
61:
62: gettimeofday(&before, NULL);
63: SLIST_FOREACH(b, &slh, node3)
64: RB_INSERT(rb_head, &rbh, b);
65: gettimeofday(&after, NULL);
66: printf("RB::Time %f\n", (after.tv_sec - before.tv_sec) + (after.tv_usec - before.tv_usec) / 1e6);
67:
68: gettimeofday(&before, NULL);
69: SLIST_FOREACH(b, &slh, node3)
70: SPLAY_INSERT(sp_head, &sph, b);
71: gettimeofday(&after, NULL);
72: printf("SP::Time %f\n", (after.tv_sec - before.tv_sec) + (after.tv_usec - before.tv_usec) / 1e6);
73:
74: gettimeofday(&before, NULL);
75: SLIST_FOREACH(b, &slh, node3)
76: AVL_INSERT(avl_head, &avlh, b);
77: gettimeofday(&after, NULL);
78: printf("AVL::Time %f\n", (after.tv_sec - before.tv_sec) + (after.tv_usec - before.tv_usec) / 1e6);
79:
80: printf("---\n");
81:
82: b2 = malloc(sizeof(struct blah));
83:
84: gettimeofday(&before, NULL);
85: for (i = 0; i < 20000; i++) {
86: memset(b2, 0, sizeof(struct blah));
87: b2->n = random();
88: b = SPLAY_FIND(sp_head, &sph, b2);
89: if (b)
90: printf("SP::Found key %d -> %d\n", i, b->n);
91: }
92: gettimeofday(&after, NULL);
93: printf("SP::Time %f\n", (after.tv_sec - before.tv_sec) + (after.tv_usec - before.tv_usec) / 1e6);
94:
95: printf("---\n");
96:
97: gettimeofday(&before, NULL);
98: for (i = 0; i < 20000; i++) {
99: memset(b2, 0, sizeof(struct blah));
100: b2->n = random();
101: b = RB_FIND(rb_head, &rbh, b2);
102: if (b)
103: printf("RB::Found key %d -> %d\n", i, b->n);
104: }
105: gettimeofday(&after, NULL);
106: printf("RB::Time %f\n", (after.tv_sec - before.tv_sec) + (after.tv_usec - before.tv_usec) / 1e6);
107:
108: printf("---\n");
109:
110: gettimeofday(&before, NULL);
111: for (i = 0; i < 20000; i++) {
112: memset(b2, 0, sizeof(struct blah));
113: b2->n = random();
114: b = AVL_FIND(avl_head, &avlh, b2);
115: if (b)
116: printf("AVL::Found key %d -> %d\n", i, b->n);
117: }
118: gettimeofday(&after, NULL);
119: printf("AVL::Time %f\n", (after.tv_sec - before.tv_sec) + (after.tv_usec - before.tv_usec) / 1e6);
120:
121: printf("---\n");
122:
123: free(b2);
124:
125: gettimeofday(&before, NULL);
126: AVL_FOREACH_SAFE(b, avl_head, &avlh, b2)
127: AVL_REMOVE(avl_head, &avlh, b);
128: gettimeofday(&after, NULL);
129: printf("AVL::Time %f\n", (after.tv_sec - before.tv_sec) + (after.tv_usec - before.tv_usec) / 1e6);
130:
131: gettimeofday(&before, NULL);
132: SPLAY_FOREACH_SAFE(b, sp_head, &sph, b2)
133: SPLAY_REMOVE(sp_head, &sph, b);
134: gettimeofday(&after, NULL);
135: printf("SP::Time %f\n", (after.tv_sec - before.tv_sec) + (after.tv_usec - before.tv_usec) / 1e6);
136:
137: gettimeofday(&before, NULL);
138: RB_FOREACH_SAFE(b, rb_head, &rbh, b2)
139: RB_REMOVE(rb_head, &rbh, b);
140: gettimeofday(&after, NULL);
141: printf("RB::Time %f\n", (after.tv_sec - before.tv_sec) + (after.tv_usec - before.tv_usec) / 1e6);
142:
143: gettimeofday(&before, NULL);
144: while ((b = SLIST_FIRST(&slh))) {
145: SLIST_REMOVE(&slh, b, blah, node3);
146: free(b);
147: }
148: gettimeofday(&after, NULL);
149: printf("SLIST::Time %f\n", (after.tv_sec - before.tv_sec) + (after.tv_usec - before.tv_usec) / 1e6);
150: return !AVL_EMPTY(&avlh);
151: }
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>