Annotation of libelwix/example/rb2.c, revision 1.1.1.1
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: };
15: RB_HEAD(rb_head, blah) rbh;
16: SPLAY_HEAD(sp_head, blah) sph;
17: AVL_HEAD(avl_head, blah) avlh;
18: SLIST_HEAD(, blah) slh;
19:
20: static int
21: rb_cmp(struct blah *a, struct blah *b)
22: {
23: int n = (a ? a->n : 0) - (b ? b->n : 0);
24:
25: if (!n)
26: return 0;
27: else if (n < 0)
28: return -1;
29: else
30: return 1;
31: }
32:
33: RB_PROTOTYPE(rb_head, blah, node, rb_cmp);
34: RB_GENERATE(rb_head, blah, node, rb_cmp);
35: SPLAY_PROTOTYPE(sp_head, blah, node1, rb_cmp);
36: SPLAY_GENERATE(sp_head, blah, node1, rb_cmp);
37: AVL_PROTOTYPE(avl_head, blah, node2, rb_cmp)
38: AVL_GENERATE(avl_head, blah, node2, rb_cmp)
39:
40:
41: int
42: main()
43: {
44: struct blah *b, *b2;
45: register int i;
46: struct timeval before, after;
47:
48: RB_INIT(&rbh);
49: SPLAY_INIT(&sph);
50: AVL_INIT(&avlh);
51: SLIST_INIT(&slh);
52: srandom(getpid());
53:
54: for (i = 0; i < 100000; i++) {
55: b = malloc(sizeof(struct blah));
56: memset(b, 0, sizeof(struct blah));
57: b->n = random();
58: SLIST_INSERT_HEAD(&slh, b, node3);
59: }
60:
61: gettimeofday(&before, NULL);
62: SLIST_FOREACH(b, &slh, node3)
63: RB_INSERT(rb_head, &rbh, b);
64: gettimeofday(&after, NULL);
65: printf("RB::Time %f\n", (after.tv_sec - before.tv_sec) + (after.tv_usec - before.tv_usec) / 1e6);
66:
67: gettimeofday(&before, NULL);
68: SLIST_FOREACH(b, &slh, node3)
69: SPLAY_INSERT(sp_head, &sph, b);
70: gettimeofday(&after, NULL);
71: printf("SP::Time %f\n", (after.tv_sec - before.tv_sec) + (after.tv_usec - before.tv_usec) / 1e6);
72:
73: gettimeofday(&before, NULL);
74: SLIST_FOREACH(b, &slh, node3)
75: AVL_INSERT(avl_head, &avlh, b);
76: gettimeofday(&after, NULL);
77: printf("AVL::Time %f\n", (after.tv_sec - before.tv_sec) + (after.tv_usec - before.tv_usec) / 1e6);
78:
79: printf("---\n");
80:
81: b2 = malloc(sizeof(struct blah));
82:
83: gettimeofday(&before, NULL);
84: for (i = 0; i < 20000; i++) {
85: memset(b2, 0, sizeof(struct blah));
86: b2->n = random();
87: b = SPLAY_FIND(sp_head, &sph, b2);
88: if (b)
89: printf("SP::Found key %d -> %d\n", i, b->n);
90: }
91: gettimeofday(&after, NULL);
92: printf("SP::Time %f\n", (after.tv_sec - before.tv_sec) + (after.tv_usec - before.tv_usec) / 1e6);
93:
94: printf("---\n");
95:
96: gettimeofday(&before, NULL);
97: for (i = 0; i < 20000; i++) {
98: memset(b2, 0, sizeof(struct blah));
99: b2->n = random();
100: b = RB_FIND(rb_head, &rbh, b2);
101: if (b)
102: printf("RB::Found key %d -> %d\n", i, b->n);
103: }
104: gettimeofday(&after, NULL);
105: printf("RB::Time %f\n", (after.tv_sec - before.tv_sec) + (after.tv_usec - before.tv_usec) / 1e6);
106:
107: printf("---\n");
108:
109: gettimeofday(&before, NULL);
110: for (i = 0; i < 20000; i++) {
111: memset(b2, 0, sizeof(struct blah));
112: b2->n = random();
113: b = AVL_FIND(avl_head, &avlh, b2);
114: if (b)
115: printf("AVL::Found key %d -> %d\n", i, b->n);
116: }
117: gettimeofday(&after, NULL);
118: printf("AVL::Time %f\n", (after.tv_sec - before.tv_sec) + (after.tv_usec - before.tv_usec) / 1e6);
119:
120: printf("---\n");
121:
122: free(b2);
123:
124: gettimeofday(&before, NULL);
125: AVL_FOREACH_SAFE(b, avl_head, &avlh, b2)
126: AVL_REMOVE(avl_head, &avlh, b);
127: gettimeofday(&after, NULL);
128: printf("AVL::Time %f\n", (after.tv_sec - before.tv_sec) + (after.tv_usec - before.tv_usec) / 1e6);
129:
130: gettimeofday(&before, NULL);
131: SPLAY_FOREACH_SAFE(b, sp_head, &sph, b2)
132: SPLAY_REMOVE(sp_head, &sph, b);
133: gettimeofday(&after, NULL);
134: printf("SP::Time %f\n", (after.tv_sec - before.tv_sec) + (after.tv_usec - before.tv_usec) / 1e6);
135:
136: gettimeofday(&before, NULL);
137: RB_FOREACH_SAFE(b, rb_head, &rbh, b2)
138: RB_REMOVE(rb_head, &rbh, b);
139: gettimeofday(&after, NULL);
140: printf("RB::Time %f\n", (after.tv_sec - before.tv_sec) + (after.tv_usec - before.tv_usec) / 1e6);
141:
142: gettimeofday(&before, NULL);
143: while ((b = SLIST_FIRST(&slh))) {
144: SLIST_REMOVE(&slh, b, blah, node3);
145: free(b);
146: }
147: gettimeofday(&after, NULL);
148: printf("SLIST::Time %f\n", (after.tv_sec - before.tv_sec) + (after.tv_usec - before.tv_usec) / 1e6);
149: return !AVL_EMPTY(&avlh);
150: }
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>