File:
[ELWIX - Embedded LightWeight unIX -] /
libelwix /
example /
rb.c
Revision
1.1.1.1 (vendor branch):
download - view:
text,
annotated -
select for diffs -
revision graph
Thu Jan 17 10:05:35 2013 UTC (11 years, 4 months ago) by
misho
Branches:
misho
CVS tags:
elwix5_8,
elwix5_7,
elwix5_6,
elwix5_5,
elwix5_4,
elwix5_3,
elwix5_2,
elwix5_1,
elwix5_0,
elwix4_9,
elwix4_8,
elwix4_7,
elwix4_6,
elwix4_5,
elwix4_4,
elwix4_3,
elwix4_26,
elwix4_25,
elwix4_24,
elwix4_23,
elwix4_22,
elwix4_21,
elwix4_20,
elwix4_2,
elwix4_19,
elwix4_18,
elwix4_17,
elwix4_16,
elwix4_15,
elwix4_14,
elwix4_13,
elwix4_12,
elwix4_11,
elwix4_10,
elwix4_1,
elwix3_9,
elwix3_8,
elwix3_7,
elwix3_6,
elwix3_5,
elwix3_4,
elwix3_3,
elwix3_2,
elwix3_1,
elwix3_0,
elwix2_9,
elwix2_8,
elwix2_7,
elwix2_6,
elwix2_5,
elwix2_4,
elwix2_3,
elwix2_2,
elwix2_1,
elwix2_0,
elwix1_9,
elwix1_8,
elwix1_7,
elwix1_6,
elwix1_5,
elwix1_4,
elwix1_3,
elwix1_2,
elwix1_1,
ELWIX5_7,
ELWIX5_6,
ELWIX5_5,
ELWIX5_4,
ELWIX5_3,
ELWIX5_2,
ELWIX5_1,
ELWIX5_0,
ELWIX4_9,
ELWIX4_8,
ELWIX4_7,
ELWIX4_6,
ELWIX4_5,
ELWIX4_4,
ELWIX4_3,
ELWIX4_26,
ELWIX4_25,
ELWIX4_24,
ELWIX4_23,
ELWIX4_22,
ELWIX4_21,
ELWIX4_20,
ELWIX4_2,
ELWIX4_19,
ELWIX4_18,
ELWIX4_17,
ELWIX4_16,
ELWIX4_15,
ELWIX4_14,
ELWIX4_13,
ELWIX4_12,
ELWIX4_11,
ELWIX4_10,
ELWIX4_1,
ELWIX4_0,
ELWIX3_8,
ELWIX3_7,
ELWIX3_6,
ELWIX3_5,
ELWIX3_4,
ELWIX3_3,
ELWIX3_2,
ELWIX3_1,
ELWIX3_0,
ELWIX2_9,
ELWIX2_8,
ELWIX2_7,
ELWIX2_6,
ELWIX2_5,
ELWIX2_4,
ELWIX2_3,
ELWIX2_2,
ELWIX2_1,
ELWIX2_0,
ELWIX1_9,
ELWIX1_8,
ELWIX1_7,
ELWIX1_6,
ELWIX1_5,
ELWIX1_4,
ELWIX1_3,
ELWIX1_2,
ELWIX1_1,
ELWIX1_0
ELWIX core library
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