1 /* $OpenBSD: rb-test.c,v 1.5 2023/12/29 02:37:39 aisha Exp $ */
2 /*
3 * Copyright 2002 Niels Provos <provos@citi.umich.edu>
4 * All rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
8 * are met:
9 * 1. Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 * 2. Redistributions in binary form must reproduce the above copyright
12 * notice, this list of conditions and the following disclaimer in the
13 * documentation and/or other materials provided with the distribution.
14 * 3. The name of the author may not be used to endorse or promote products
15 * derived from this software without specific prior written permission.
16 *
17 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
18 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
19 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
20 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
21 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
22 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 */
28 #include <sys/time.h>
29
30 #include <assert.h>
31 #include <err.h>
32 #include <stddef.h>
33 #include <stdlib.h>
34 #include <stdio.h>
35 #include <string.h>
36 #include <time.h>
37
38 struct timespec start, end, diff, rstart, rend, rdiff, rtot = {0, 0};
39 #ifndef timespecsub
40 #define timespecsub(tsp, usp, vsp) \
41 do { \
42 (vsp)->tv_sec = (tsp)->tv_sec - (usp)->tv_sec; \
43 (vsp)->tv_nsec = (tsp)->tv_nsec - (usp)->tv_nsec; \
44 if ((vsp)->tv_nsec < 0) { \
45 (vsp)->tv_sec--; \
46 (vsp)->tv_nsec += 1000000000L; \
47 } \
48 } while (0)
49 #endif
50 #ifndef timespecadd
51 #define timespecadd(tsp, usp, vsp) \
52 do { \
53 (vsp)->tv_sec = (tsp)->tv_sec + (usp)->tv_sec; \
54 (vsp)->tv_nsec = (tsp)->tv_nsec + (usp)->tv_nsec; \
55 if ((vsp)->tv_nsec >= 1000000000L) { \
56 (vsp)->tv_sec++; \
57 (vsp)->tv_nsec -= 1000000000L; \
58 } \
59 } while (0)
60 #endif
61
62 //#define RB_SMALL
63 //#define RB_TEST_RANK
64 //#define RB_TEST_DIAGNOSTIC
65 //#define _RB_DIAGNOSTIC
66
67 #ifdef DOAUGMENT
68 #define RB_AUGMENT(elm) tree_augment(elm)
69 #endif
70
71 #include <sys/tree.h>
72
73 #define TDEBUGF(fmt, ...) \
74 fprintf(stderr, "%s:%d:%s(): " fmt "\n", \
75 __FILE__, __LINE__, __func__, ##__VA_ARGS__)
76
77
78 #ifdef __OpenBSD__
79 #define SEED_RANDOM srandom_deterministic
80 #else
81 #define SEED_RANDOM srandom
82 #endif
83
84 int ITER=150000;
85 int RANK_TEST_ITERATIONS=10000;
86
87 #define MAX(a, b) ((a) > (b) ? (a) : (b))
88
89 /* declarations */
90 struct node;
91 struct tree;
92 static int compare(const struct node *, const struct node *);
93 static void mix_operations(int *, int, struct node *, int, int, int, int);
94
95 #ifdef DOAUGMENT
96 static int tree_augment(struct node *);
97 #else
98 #define tree_augment(x) (0)
99 #endif
100
101 #ifdef RB_TEST_DIAGNOSTIC
102 static void print_helper(const struct node *, int);
103 static void print_tree(const struct tree *);
104 #else
105 #define print_helper(x, y) do {} while (0)
106 #define print_tree(x) do {} while (0)
107 #endif
108
109 /* definitions */
110 struct node {
111 RB_ENTRY(node) node_link;
112 int key;
113 size_t height;
114 size_t size;
115 };
116
117 RB_HEAD(tree, node);
118 struct tree root = RB_INITIALIZER(&root);
119
RB_PROTOTYPE(tree,node,node_link,compare)120 RB_PROTOTYPE(tree, node, node_link, compare)
121
122 RB_GENERATE(tree, node, node_link, compare)
123
124 #ifndef RB_RANK
125 #define RB_RANK(x, y) 0
126 #endif
127 #ifndef _RB_GET_RDIFF
128 #define _RB_GET_RDIFF(x, y, z) 0
129 #endif
130
131 int
132 main(int argc, char **argv)
133 {
134 char *test_target = NULL;
135 struct node *tmp, *ins, *nodes;
136 int i, r, rank, *perm, *nums;
137
138 if (argc > 1)
139 test_target = argv[1];
140
141 nodes = calloc((ITER + 5), sizeof(struct node));
142 perm = calloc(ITER, sizeof(int));
143 nums = calloc(ITER, sizeof(int));
144
145 // for determinism
146 SEED_RANDOM(4201);
147
148 TDEBUGF("generating a 'random' permutation");
149 clock_gettime(CLOCK_THREAD_CPUTIME_ID, &start);
150 perm[0] = 0;
151 nums[0] = 0;
152 for(i = 1; i < ITER; i++) {
153 r = random() % i; // arc4random_uniform(i);
154 perm[i] = perm[r];
155 perm[r] = i;
156 nums[i] = i;
157 }
158 /*
159 fprintf(stderr, "{");
160 for(int i = 0; i < ITER; i++) {
161 fprintf(stderr, "%d, ", perm[i]);
162 }
163 fprintf(stderr, "}\n");
164 int nperm[10] = {2, 4, 9, 7, 8, 3, 0, 1, 6, 5};
165 int nperm[6] = {2, 6, 1, 4, 5, 3};
166 int nperm[10] = {10, 3, 7, 8, 6, 1, 9, 2, 5, 4};
167 int nperm[2] = {0, 1};
168
169 int nperm[100] = {
170 54, 47, 31, 35, 40, 73, 29, 66, 15, 45, 9, 71, 51, 32, 28, 62,
171 12, 46, 50, 26, 36, 91, 10, 76, 33, 43, 34, 58, 55, 72, 37, 24,
172 75, 4, 90, 88, 30, 25, 82, 18, 67, 81, 80, 65, 23, 41, 61, 86,
173 20, 99, 59, 14, 79, 21, 68, 27, 1, 7, 94, 44, 89, 64, 96, 2, 49,
174 53, 74, 13, 48, 42, 60, 52, 95, 17, 11, 0, 22, 97, 77, 69, 6,
175 16, 84, 78, 8, 83, 98, 93, 39, 38, 85, 70, 3, 19, 57, 5, 87,
176 92, 63, 56
177 };
178 ITER = 100;
179 for(int i = 0; i < ITER; i++){
180 perm[i] = nperm[i];
181 }
182 */
183
184 clock_gettime(CLOCK_THREAD_CPUTIME_ID, &end);
185 timespecsub(&end, &start, &diff);
186 TDEBUGF("done generating a 'random' permutation in: %llu.%09llu s",
187 (unsigned long long)diff.tv_sec, (unsigned long long)diff.tv_nsec);
188
189 RB_INIT(&root);
190
191 // testing random inserts
192 // due to codependency between inserts and removals, this also tests
193 // root removals
194 if (test_target == NULL ||
195 strcmp(test_target, "random-inserts") == 0
196 ) {
197 TDEBUGF("starting random insertions");
198 clock_gettime(CLOCK_THREAD_CPUTIME_ID, &start);
199 mix_operations(perm, ITER, nodes, ITER, ITER, 0, 0);
200 clock_gettime(CLOCK_THREAD_CPUTIME_ID, &end);
201 timespecsub(&end, &start, &diff);
202 TDEBUGF("done random insertions in: %llu.%09llu s",
203 (unsigned long long)diff.tv_sec, (unsigned long long)diff.tv_nsec);
204
205 #ifdef DOAUGMENT
206 ins = RB_ROOT(&root);
207 assert(ITER + 1 == ins->size);
208 #endif
209
210 TDEBUGF("getting min");
211 clock_gettime(CLOCK_THREAD_CPUTIME_ID, &start);
212 ins = RB_MIN(tree, &root);
213 clock_gettime(CLOCK_THREAD_CPUTIME_ID, &end);
214 timespecsub(&end, &start, &diff);
215 TDEBUGF("done getting min in: %lld.%09llu s",
216 (unsigned long long)diff.tv_sec, (unsigned long long)diff.tv_nsec);
217 assert(0 == ins->key);
218
219 TDEBUGF("getting max");
220 clock_gettime(CLOCK_THREAD_CPUTIME_ID, &start);
221 ins = RB_MAX(tree, &root);
222 clock_gettime(CLOCK_THREAD_CPUTIME_ID, &end);
223 timespecsub(&end, &start, &diff);
224 TDEBUGF("done getting max in: %lld.%09llu s",
225 (unsigned long long)diff.tv_sec, (unsigned long long)diff.tv_nsec);
226 assert(ITER + 5 == ins->key);
227
228 ins = RB_ROOT(&root);
229 TDEBUGF("getting root");
230 assert(RB_REMOVE(tree, &root, ins) == ins);
231
232 #ifdef DOAUGMENT
233 assert(ITER == (RB_ROOT(&root))->size);
234 #endif
235
236 TDEBUGF("doing root removals");
237 clock_gettime(CLOCK_THREAD_CPUTIME_ID, &start);
238 for (i = 0; i < ITER; i++) {
239 tmp = RB_ROOT(&root);
240 assert(NULL != tmp);
241 assert(RB_REMOVE(tree, &root, tmp) == tmp);
242 #ifdef RB_TEST_RANK
243 if (i % RANK_TEST_ITERATIONS == 0) {
244 rank = RB_RANK(tree, RB_ROOT(&root));
245 assert(-2 != rank);
246 print_tree(&root);
247 }
248 #endif
249
250 #ifdef DOAUGMENT
251 if (!(RB_EMPTY(&root)) && (RB_ROOT(&root))->size != ITER - 1 - i)
252 errx(1, "RB_REMOVE size error");
253 #endif
254
255 }
256 clock_gettime(CLOCK_THREAD_CPUTIME_ID, &end);
257 timespecsub(&end, &start, &diff);
258 TDEBUGF("done root removals in: %llu.%09llu s",
259 (unsigned long long)diff.tv_sec, (unsigned long long)diff.tv_nsec);
260 }
261
262 // testing insertions in increasing sequential order
263 // removals are done using root removals (separate test)
264 if (test_target == NULL ||
265 strcmp(test_target, "sequential-inserts") == 0
266 ) {
267 TDEBUGF("starting sequential insertions");
268 clock_gettime(CLOCK_THREAD_CPUTIME_ID, &start);
269 mix_operations(nums, ITER, nodes, ITER, ITER, 0, 0);
270 clock_gettime(CLOCK_THREAD_CPUTIME_ID, &end);
271 timespecsub(&end, &start, &diff);
272 TDEBUGF("done sequential insertions in: %lld.%09llu s",
273 (unsigned long long)diff.tv_sec, (unsigned long long)diff.tv_nsec);
274
275 TDEBUGF("doing root removals");
276 clock_gettime(CLOCK_THREAD_CPUTIME_ID, &start);
277 for (i = 0; i < ITER + 1; i++) {
278 tmp = RB_ROOT(&root);
279 assert(NULL != tmp);
280 assert(RB_REMOVE(tree, &root, tmp) == tmp);
281 #ifdef RB_TEST_RANK
282 if (i % RANK_TEST_ITERATIONS == 0) {
283 rank = RB_RANK(tree, RB_ROOT(&root));
284 if (rank == -2)
285 errx(1, "rank error");
286 }
287 #endif
288 }
289 clock_gettime(CLOCK_THREAD_CPUTIME_ID, &end);
290 timespecsub(&end, &start, &diff);
291 TDEBUGF("done root removals in: %llu.%09llu s",
292 (unsigned long long)diff.tv_sec, (unsigned long long)diff.tv_nsec);
293 }
294
295 // testing the RB_FIND function and using it to do removals in
296 // sequential order
297 // insertions are done using sequential insertions (separate test)
298 if (test_target == NULL ||
299 strcmp(test_target, "sequential-removes") == 0
300 ) {
301 TDEBUGF("starting sequential insertions");
302 clock_gettime(CLOCK_THREAD_CPUTIME_ID, &start);
303 mix_operations(nums, ITER, nodes, ITER, ITER, 0, 0);
304 clock_gettime(CLOCK_THREAD_CPUTIME_ID, &end);
305 timespecsub(&end, &start, &diff);
306 TDEBUGF("done sequential insertions in: %lld.%09llu s",
307 (unsigned long long)diff.tv_sec, (unsigned long long)diff.tv_nsec);
308
309 TDEBUGF("doing find and remove in sequential order");
310 clock_gettime(CLOCK_THREAD_CPUTIME_ID, &start);
311 tmp = malloc(sizeof(struct node));
312 for(i = 0; i < ITER; i++) {
313 tmp->key = i;
314 ins = RB_FIND(tree, &root, tmp);
315 assert(NULL != tmp);
316 assert(RB_REMOVE(tree, &root, ins) == ins);
317 #ifdef RB_TEST_RANK
318 if (i % RANK_TEST_ITERATIONS == 0) {
319 rank = RB_RANK(tree, RB_ROOT(&root));
320 if (rank == -2)
321 errx(1, "rank error");
322 }
323 #endif
324 }
325 free(tmp);
326 clock_gettime(CLOCK_THREAD_CPUTIME_ID, &end);
327 timespecsub(&end, &start, &diff);
328 TDEBUGF("done removals in: %lld.%09llu s",
329 (unsigned long long)diff.tv_sec, (unsigned long long)diff.tv_nsec);
330
331 ins = RB_ROOT(&root);
332 if (ins == NULL)
333 errx(1, "RB_ROOT error");
334 if (RB_REMOVE(tree, &root, ins) != ins)
335 errx(1, "RB_REMOVE failed");
336 }
337
338 // testing removals in random order
339 // the elements are found using RB_FIND
340 // insertions are done using sequential insertions (separate test)
341 if (test_target == NULL ||
342 strcmp(test_target, "random-removes") == 0
343 ) {
344 TDEBUGF("starting sequential insertions");
345 clock_gettime(CLOCK_THREAD_CPUTIME_ID, &start);
346 mix_operations(nums, ITER, nodes, ITER, ITER, 0, 0);
347 clock_gettime(CLOCK_THREAD_CPUTIME_ID, &end);
348 timespecsub(&end, &start, &diff);
349 TDEBUGF("done sequential insertions in: %lld.%09llu s",
350 (unsigned long long)diff.tv_sec, (unsigned long long)diff.tv_nsec);
351
352
353 TDEBUGF("doing find and remove in random order");
354 clock_gettime(CLOCK_THREAD_CPUTIME_ID, &start);
355 tmp = malloc(sizeof(struct node));
356 for(i = 0; i < ITER; i++) {
357 tmp->key = perm[i];
358 ins = RB_FIND(tree, &root, tmp);
359 if (ins == NULL) {
360 errx(1, "RB_FIND %d failed: %d", i, perm[i]);
361 }
362 if (RB_REMOVE(tree, &root, ins) == NULL)
363 errx(1, "RB_REMOVE failed: %d", i);
364 #ifdef RB_TEST_RANK
365 if (i % RANK_TEST_ITERATIONS == 0) {
366 rank = RB_RANK(tree, RB_ROOT(&root));
367 if (rank == -2)
368 errx(1, "rank error");
369 }
370 #endif
371 }
372 free(tmp);
373 clock_gettime(CLOCK_THREAD_CPUTIME_ID, &end);
374 timespecsub(&end, &start, &diff);
375 TDEBUGF("done removals in: %lld.%09llu s",
376 (unsigned long long)diff.tv_sec, (unsigned long long)diff.tv_nsec);
377
378 ins = RB_ROOT(&root);
379 if (ins == NULL)
380 errx(1, "RB_ROOT error");
381 if (RB_REMOVE(tree, &root, ins) != ins)
382 errx(1, "RB_REMOVE failed");
383 }
384
385 // testing removals by finding the next largest element
386 // this is testing the RB_NFIND macro
387 // insertions are done using sequential insertions (separate test)
388 if (test_target == NULL ||
389 strcmp(test_target, "remove-nfind") == 0
390 ) {
391 TDEBUGF("starting sequential insertions");
392 clock_gettime(CLOCK_THREAD_CPUTIME_ID, &start);
393 mix_operations(nums, ITER, nodes, ITER, ITER, 0, 0);
394 clock_gettime(CLOCK_THREAD_CPUTIME_ID, &end);
395 timespecsub(&end, &start, &diff);
396 TDEBUGF("done sequential insertions in: %lld.%09llu s",
397 (unsigned long long)diff.tv_sec, (unsigned long long)diff.tv_nsec);
398
399 TDEBUGF("doing nfind and remove");
400 clock_gettime(CLOCK_THREAD_CPUTIME_ID, &start);
401 tmp = malloc(sizeof(struct node));
402 for(i = 0; i < ITER + 1; i++) {
403 tmp->key = i;
404 ins = RB_NFIND(tree, &root, tmp);
405 if (ins == NULL)
406 errx(1, "RB_NFIND failed");
407 if (RB_REMOVE(tree, &root, ins) == NULL)
408 errx(1, "RB_REMOVE failed: %d", i);
409 #ifdef RB_TEST_RANK
410 if (i % RANK_TEST_ITERATIONS == 0) {
411 rank = RB_RANK(tree, RB_ROOT(&root));
412 if (rank == -2)
413 errx(1, "rank error");
414 }
415 #endif
416 }
417 free(tmp);
418 clock_gettime(CLOCK_THREAD_CPUTIME_ID, &end);
419 timespecsub(&end, &start, &diff);
420 TDEBUGF("done removals in: %lld.%09llu s",
421 (unsigned long long)diff.tv_sec, (unsigned long long)diff.tv_nsec);
422 }
423
424 #ifdef RB_PFIND
425 // testing removals by finding the previous element
426 // this is testing the RB_PFIND macro
427 // insertions are done using sequential insertions (separate test)
428 if (test_target == NULL ||
429 strcmp(test_target, "remove-pfind") == 0
430 ) {
431 TDEBUGF("starting sequential insertions");
432 clock_gettime(CLOCK_THREAD_CPUTIME_ID, &start);
433 mix_operations(nums, ITER, nodes, ITER, ITER, 0, 0);
434 clock_gettime(CLOCK_THREAD_CPUTIME_ID, &end);
435 timespecsub(&end, &start, &diff);
436 TDEBUGF("done sequential insertions in: %lld.%09llu s",
437 (unsigned long long)diff.tv_sec, (unsigned long long)diff.tv_nsec);
438
439 TDEBUGF("doing pfind and remove");
440 clock_gettime(CLOCK_THREAD_CPUTIME_ID, &start);
441 tmp = malloc(sizeof(struct node));
442 for(i = 0; i < ITER + 1; i++) {
443 tmp->key = ITER + 6;
444 ins = RB_PFIND(tree, &root, tmp);
445 if (ins == NULL)
446 errx(1, "RB_PFIND failed");
447 if (RB_REMOVE(tree, &root, ins) == NULL)
448 errx(1, "RB_REMOVE failed: %d", i);
449 #ifdef RB_TEST_RANK
450 if (i % RANK_TEST_ITERATIONS == 0) {
451 rank = RB_RANK(tree, RB_ROOT(&root));
452 if (rank == -2)
453 errx(1, "rank error");
454 }
455 #endif
456 }
457 free(tmp);
458 clock_gettime(CLOCK_THREAD_CPUTIME_ID, &end);
459 timespecsub(&end, &start, &diff);
460 TDEBUGF("done removals in: %lld.%09llu s",
461 (unsigned long long)diff.tv_sec, (unsigned long long)diff.tv_nsec);
462 }
463 #endif
464
465 // iterate over the tree using RB_NEXT/RB_PREV
466 // insertions and removals have separate tests
467 if (test_target == NULL ||
468 strcmp(test_target, "node-iterations") == 0
469 ) {
470 TDEBUGF("starting sequential insertions");
471 clock_gettime(CLOCK_THREAD_CPUTIME_ID, &start);
472 mix_operations(nums, ITER, nodes, ITER, ITER, 0, 0);
473 clock_gettime(CLOCK_THREAD_CPUTIME_ID, &end);
474 timespecsub(&end, &start, &diff);
475 TDEBUGF("done sequential insertions in: %lld.%09llu s",
476 (unsigned long long)diff.tv_sec, (unsigned long long)diff.tv_nsec);
477
478 TDEBUGF("iterating over tree with RB_NEXT");
479 clock_gettime(CLOCK_THREAD_CPUTIME_ID, &start);
480 tmp = RB_MIN(tree, &root);
481 assert(tmp != NULL);
482 assert(tmp->key == 0);
483 for(i = 1; i < ITER; i++) {
484 tmp = RB_NEXT(tree, &root, tmp);
485 assert(tmp != NULL);
486 assert(tmp->key == i);
487 }
488 clock_gettime(CLOCK_THREAD_CPUTIME_ID, &end);
489 timespecsub(&end, &start, &diff);
490 TDEBUGF("done iterations in %lld.%09llu s",
491 (unsigned long long)diff.tv_sec, (unsigned long long)diff.tv_nsec);
492
493 TDEBUGF("iterating over tree with RB_PREV");
494 clock_gettime(CLOCK_THREAD_CPUTIME_ID, &start);
495 tmp = RB_MAX(tree, &root);
496 assert(tmp != NULL);
497 assert(tmp->key == ITER + 5);
498 for(i = 0; i < ITER; i++) {
499 tmp = RB_PREV(tree, &root, tmp);
500 assert(tmp != NULL);
501 assert(tmp->key == ITER - 1 - i);
502 }
503 clock_gettime(CLOCK_THREAD_CPUTIME_ID, &end);
504 timespecsub(&end, &start, &diff);
505 TDEBUGF("done iterations in %lld.%09llu s",
506 (unsigned long long)diff.tv_sec, (unsigned long long)diff.tv_nsec);
507
508 TDEBUGF("doing root removals");
509 clock_gettime(CLOCK_THREAD_CPUTIME_ID, &start);
510 for (i = 0; i < ITER + 1; i++) {
511 tmp = RB_ROOT(&root);
512 assert(NULL != tmp);
513 assert(RB_REMOVE(tree, &root, tmp) == tmp);
514 #ifdef RB_TEST_RANK
515 if (i % RANK_TEST_ITERATIONS == 0) {
516 rank = RB_RANK(tree, RB_ROOT(&root));
517 if (rank == -2)
518 errx(1, "rank error");
519 }
520 #endif
521 }
522 clock_gettime(CLOCK_THREAD_CPUTIME_ID, &end);
523 timespecsub(&end, &start, &diff);
524 TDEBUGF("done root removals in: %llu.%09llu s",
525 (unsigned long long)diff.tv_sec, (unsigned long long)diff.tv_nsec);
526 }
527
528 // iterate over the tree using RB_FOREACH* macros
529 // the *_SAFE macros are tested by using them to clear the tree
530 // insertions and removals have separate tests
531 if (test_target == NULL ||
532 strcmp(test_target, "iteration-macros") == 0
533 ) {
534 TDEBUGF("starting sequential insertions");
535 clock_gettime(CLOCK_THREAD_CPUTIME_ID, &start);
536 mix_operations(nums, ITER, nodes, ITER, ITER, 0, 0);
537 clock_gettime(CLOCK_THREAD_CPUTIME_ID, &end);
538 timespecsub(&end, &start, &diff);
539 TDEBUGF("done sequential insertions in: %lld.%09llu s",
540 (unsigned long long)diff.tv_sec, (unsigned long long)diff.tv_nsec);
541
542 #ifdef RB_FOREACH
543 TDEBUGF("iterating over tree with RB_FOREACH");
544 clock_gettime(CLOCK_THREAD_CPUTIME_ID, &start);
545 i = 0;
546 RB_FOREACH(ins, tree, &root) {
547 if (i < ITER)
548 assert(ins->key == i);
549 else
550 assert(ins->key == ITER + 5);
551 i++;
552 }
553 clock_gettime(CLOCK_THREAD_CPUTIME_ID, &end);
554 timespecsub(&end, &start, &diff);
555 TDEBUGF("done iterations in %lld.%09llu s",
556 (unsigned long long)diff.tv_sec, (unsigned long long)diff.tv_nsec);
557 #endif
558
559 #ifdef RB_FOREACH_REVERSE
560 TDEBUGF("iterating over tree with RB_FOREACH_REVERSE");
561 clock_gettime(CLOCK_THREAD_CPUTIME_ID, &start);
562 i = ITER + 5;
563 RB_FOREACH_REVERSE(ins, tree, &root) {
564 assert(ins->key == i);
565 if (i > ITER)
566 i = ITER - 1;
567 else
568 i--;
569 }
570 clock_gettime(CLOCK_THREAD_CPUTIME_ID, &end);
571 timespecsub(&end, &start, &diff);
572 TDEBUGF("done iterations in %lld.%09llu s",
573 (unsigned long long)diff.tv_sec, (unsigned long long)diff.tv_nsec);
574 #endif
575
576 TDEBUGF("doing root removals");
577 clock_gettime(CLOCK_THREAD_CPUTIME_ID, &start);
578 for (i = 0; i < ITER + 1; i++) {
579 tmp = RB_ROOT(&root);
580 assert(NULL != tmp);
581 assert(RB_REMOVE(tree, &root, tmp) == tmp);
582 #ifdef RB_TEST_RANK
583 if (i % RANK_TEST_ITERATIONS == 0) {
584 rank = RB_RANK(tree, RB_ROOT(&root));
585 if (rank == -2)
586 errx(1, "rank error");
587 }
588 #endif
589 }
590 clock_gettime(CLOCK_THREAD_CPUTIME_ID, &end);
591 timespecsub(&end, &start, &diff);
592 TDEBUGF("done root removals in: %llu.%09llu s",
593 (unsigned long long)diff.tv_sec, (unsigned long long)diff.tv_nsec);
594
595 #ifdef RB_FOREACH_SAFE
596 TDEBUGF("starting sequential insertions");
597 clock_gettime(CLOCK_THREAD_CPUTIME_ID, &start);
598 mix_operations(nums, ITER, nodes, ITER, ITER, 0, 0);
599 clock_gettime(CLOCK_THREAD_CPUTIME_ID, &end);
600 timespecsub(&end, &start, &diff);
601 TDEBUGF("done sequential insertions in: %lld.%09llu s",
602 (unsigned long long)diff.tv_sec, (unsigned long long)diff.tv_nsec);
603
604 TDEBUGF("iterating over tree and clearing with RB_FOREACH_SAFE");
605 clock_gettime(CLOCK_THREAD_CPUTIME_ID, &start);
606 i = 0;
607 RB_FOREACH_SAFE(ins, tree, &root, tmp) {
608 if (i < ITER)
609 assert(ins->key == i);
610 else
611 assert(ins->key == ITER + 5);
612 i++;
613 assert(RB_REMOVE(tree, &root, ins) == ins);
614 }
615 clock_gettime(CLOCK_THREAD_CPUTIME_ID, &end);
616 timespecsub(&end, &start, &diff);
617 TDEBUGF("done iterations in %lld.%09llu s",
618 (unsigned long long)diff.tv_sec, (unsigned long long)diff.tv_nsec);
619 #endif
620
621 #ifdef RB_FOREACH_REVERSE_SAFE
622 TDEBUGF("starting sequential insertions");
623 clock_gettime(CLOCK_THREAD_CPUTIME_ID, &start);
624 mix_operations(nums, ITER, nodes, ITER, ITER, 0, 0);
625 clock_gettime(CLOCK_THREAD_CPUTIME_ID, &end);
626 timespecsub(&end, &start, &diff);
627 TDEBUGF("done sequential insertions in: %lld.%09llu s",
628 (unsigned long long)diff.tv_sec, (unsigned long long)diff.tv_nsec);
629
630 TDEBUGF("iterating over tree and clearing with RB_FOREACH_REVERSE_SAFE");
631 clock_gettime(CLOCK_THREAD_CPUTIME_ID, &start);
632 i = ITER + 5;
633 RB_FOREACH_REVERSE_SAFE(ins, tree, &root, tmp) {
634 assert(ins->key == i);
635 if (i > ITER)
636 i = ITER - 1;
637 else
638 i--;
639 assert(RB_REMOVE(tree, &root, ins) == ins);
640 }
641 clock_gettime(CLOCK_THREAD_CPUTIME_ID, &end);
642 timespecsub(&end, &start, &diff);
643 TDEBUGF("done iterations in %lld.%09llu s",
644 (unsigned long long)diff.tv_sec, (unsigned long long)diff.tv_nsec);
645 #endif
646 }
647
648 #ifdef RB_INSERT_NEXT
649 // testing insertions at specific points in the tree
650 // the insertions are done at the next position in the tree at a give node
651 // this assumes that the location is correct for the given ordering
652 if (test_target == NULL ||
653 strcmp(test_target, "insert-next") == 0
654 ) {
655 TDEBUGF("starting sequential insertions using INSERT_NEXT");
656 clock_gettime(CLOCK_THREAD_CPUTIME_ID, &start);
657 tmp = &(nodes[0]);
658 tmp->size = 1;
659 tmp->height = 1;
660 tmp->key = 0;
661 if (RB_INSERT(tree, &root, tmp) != NULL)
662 errx(1, "RB_INSERT failed");
663 ins = tmp;
664 for(i = 1; i < ITER; i++) {
665 tmp = &(nodes[i]);
666 tmp->size = 1;
667 tmp->height = 1;
668 tmp->key = i;
669 if (RB_INSERT_NEXT(tree, &root, ins, tmp) != NULL)
670 errx(1, "RB_INSERT failed");
671 ins = tmp;
672 #ifdef RB_TEST_RANK
673 if (i % RANK_TEST_ITERATIONS == 0) {
674 rank = RB_RANK(tree, RB_ROOT(&root));
675 if (rank == -2)
676 errx(1, "rank error");
677 }
678 #endif
679 }
680 clock_gettime(CLOCK_THREAD_CPUTIME_ID, &end);
681 timespecsub(&end, &start, &diff);
682 TDEBUGF("done insertions in %lld.%09llu s",
683 (unsigned long long)diff.tv_sec, (unsigned long long)diff.tv_nsec);
684
685 TDEBUGF("iterating over tree and clearing with RB_FOREACH_REVERSE_SAFE");
686 clock_gettime(CLOCK_THREAD_CPUTIME_ID, &start);
687 RB_FOREACH_REVERSE_SAFE(ins, tree, &root, tmp) {
688 assert(RB_REMOVE(tree, &root, ins) == ins);
689 }
690 clock_gettime(CLOCK_THREAD_CPUTIME_ID, &end);
691 timespecsub(&end, &start, &diff);
692 TDEBUGF("done iterations in %lld.%09llu s",
693 (unsigned long long)diff.tv_sec, (unsigned long long)diff.tv_nsec);
694 }
695 #endif
696
697 #ifdef RB_INSERT_PREV
698 // testing insertions at specific points in the tree
699 // the insertions are done at the next position in the tree at a give node
700 // this assumes that the location is correct for the given ordering
701 if (test_target == NULL ||
702 strcmp(test_target, "insert-prev") == 0
703 ) {
704 TDEBUGF("starting sequential insertions using INSERT_PREV");
705 clock_gettime(CLOCK_THREAD_CPUTIME_ID, &start);
706 tmp = &(nodes[ITER]);
707 tmp->size = 1;
708 tmp->height = 1;
709 tmp->key = ITER;
710 if (RB_INSERT(tree, &root, tmp) != NULL)
711 errx(1, "RB_INSERT failed");
712 ins = tmp;
713 for(i = ITER - 1; i >= 0; i--) {
714 tmp = &(nodes[i]);
715 tmp->size = 1;
716 tmp->height = 1;
717 tmp->key = i;
718 if (RB_INSERT_PREV(tree, &root, ins, tmp) != NULL)
719 errx(1, "RB_INSERT failed");
720 ins = tmp;
721 #ifdef RB_TEST_RANK
722 if (i % RANK_TEST_ITERATIONS == 0) {
723 rank = RB_RANK(tree, RB_ROOT(&root));
724 if (rank == -2)
725 errx(1, "rank error");
726 }
727 #endif
728 }
729 clock_gettime(CLOCK_THREAD_CPUTIME_ID, &end);
730 timespecsub(&end, &start, &diff);
731 TDEBUGF("done insertions in %lld.%09llu s",
732 (unsigned long long)diff.tv_sec, (unsigned long long)diff.tv_nsec);
733
734 TDEBUGF("iterating over tree and clearing with RB_FOREACH_REVERSE_SAFE");
735 clock_gettime(CLOCK_THREAD_CPUTIME_ID, &start);
736 RB_FOREACH_REVERSE_SAFE(ins, tree, &root, tmp) {
737 assert(RB_REMOVE(tree, &root, ins) == ins);
738 }
739 clock_gettime(CLOCK_THREAD_CPUTIME_ID, &end);
740 timespecsub(&end, &start, &diff);
741 TDEBUGF("done iterations in %lld.%09llu s",
742 (unsigned long long)diff.tv_sec, (unsigned long long)diff.tv_nsec);
743 }
744 #endif
745
746 if (test_target == NULL ||
747 strcmp(test_target, "benchmarks") == 0
748 ) {
749 TDEBUGF("doing 50%% insertions, 50%% lookups");
750 clock_gettime(CLOCK_THREAD_CPUTIME_ID, &start);
751 mix_operations(perm, ITER, nodes, ITER, ITER / 2, ITER / 2, 1);
752 clock_gettime(CLOCK_THREAD_CPUTIME_ID, &end);
753 timespecsub(&end, &start, &diff);
754 TDEBUGF("done operations in: %lld.%09llu s",
755 (unsigned long long)diff.tv_sec, (unsigned long long)diff.tv_nsec);
756
757 TDEBUGF("doing root removals");
758 clock_gettime(CLOCK_THREAD_CPUTIME_ID, &start);
759 for (i = 0; i < ITER / 2 + 1; i++) {
760 tmp = RB_ROOT(&root);
761 if (tmp == NULL)
762 errx(1, "RB_ROOT error");
763 if (RB_REMOVE(tree, &root, tmp) != tmp)
764 errx(1, "RB_REMOVE error");
765 }
766 clock_gettime(CLOCK_THREAD_CPUTIME_ID, &end);
767 timespecsub(&end, &start, &diff);
768 TDEBUGF("done root removals in: %llu.%09llu s",
769 (unsigned long long)diff.tv_sec, (unsigned long long)diff.tv_nsec);
770
771 TDEBUGF("doing 20%% insertions, 80%% lookups");
772 clock_gettime(CLOCK_THREAD_CPUTIME_ID, &start);
773 mix_operations(perm, ITER, nodes, ITER, ITER / 5, 4 * (ITER / 5), 1);
774 clock_gettime(CLOCK_THREAD_CPUTIME_ID, &end);
775 timespecsub(&end, &start, &diff);
776 TDEBUGF("done operations in: %lld.%09llu s",
777 (unsigned long long)diff.tv_sec, (unsigned long long)diff.tv_nsec);
778
779 TDEBUGF("doing root removals");
780 clock_gettime(CLOCK_THREAD_CPUTIME_ID, &start);
781 for (i = 0; i < ITER / 5 + 1; i++) {
782 tmp = RB_ROOT(&root);
783 if (tmp == NULL)
784 errx(1, "RB_ROOT error");
785 if (RB_REMOVE(tree, &root, tmp) != tmp)
786 errx(1, "RB_REMOVE error");
787 }
788 clock_gettime(CLOCK_THREAD_CPUTIME_ID, &end);
789 timespecsub(&end, &start, &diff);
790 TDEBUGF("done root removals in: %llu.%09llu s",
791 (unsigned long long)diff.tv_sec, (unsigned long long)diff.tv_nsec);
792
793 TDEBUGF("doing 10%% insertions, 90%% lookups");
794 clock_gettime(CLOCK_THREAD_CPUTIME_ID, &start);
795 mix_operations(perm, ITER, nodes, ITER, ITER / 10, 9 * (ITER / 10), 1);
796 clock_gettime(CLOCK_THREAD_CPUTIME_ID, &end);
797 timespecsub(&end, &start, &diff);
798 TDEBUGF("done operations in: %lld.%09llu s",
799 (unsigned long long)diff.tv_sec, (unsigned long long)diff.tv_nsec);
800
801 TDEBUGF("doing root removals");
802 clock_gettime(CLOCK_THREAD_CPUTIME_ID, &start);
803 for (i = 0; i < ITER / 10 + 1; i++) {
804 tmp = RB_ROOT(&root);
805 if (tmp == NULL)
806 errx(1, "RB_ROOT error");
807 if (RB_REMOVE(tree, &root, tmp) != tmp)
808 errx(1, "RB_REMOVE error");
809 }
810 clock_gettime(CLOCK_THREAD_CPUTIME_ID, &end);
811 timespecsub(&end, &start, &diff);
812 TDEBUGF("done root removals in: %llu.%09llu s",
813 (unsigned long long)diff.tv_sec, (unsigned long long)diff.tv_nsec);
814
815 TDEBUGF("doing 5%% insertions, 95%% lookups");
816 clock_gettime(CLOCK_THREAD_CPUTIME_ID, &start);
817 mix_operations(perm, ITER, nodes,
818 ITER, 5 * (ITER / 100),
819 95 * (ITER / 100), 1);
820 clock_gettime(CLOCK_THREAD_CPUTIME_ID, &end);
821 timespecsub(&end, &start, &diff);
822 TDEBUGF("done operations in: %lld.%09llu s",
823 (unsigned long long)diff.tv_sec, (unsigned long long)diff.tv_nsec);
824
825 TDEBUGF("doing root removals");
826 clock_gettime(CLOCK_THREAD_CPUTIME_ID, &start);
827 for (i = 0; i < 5 * (ITER / 100) + 1; i++) {
828 tmp = RB_ROOT(&root);
829 if (tmp == NULL)
830 errx(1, "RB_ROOT error");
831 if (RB_REMOVE(tree, &root, tmp) != tmp)
832 errx(1, "RB_REMOVE error");
833 }
834 clock_gettime(CLOCK_THREAD_CPUTIME_ID, &end);
835 timespecsub(&end, &start, &diff);
836 TDEBUGF("done root removals in: %llu.%09llu s",
837 (unsigned long long)diff.tv_sec, (unsigned long long)diff.tv_nsec);
838
839 TDEBUGF("doing 2%% insertions, 98%% lookups");
840 clock_gettime(CLOCK_THREAD_CPUTIME_ID, &start);
841 mix_operations(perm, ITER, nodes, ITER,
842 2 * (ITER / 100),
843 98 * (ITER / 100), 1);
844 clock_gettime(CLOCK_THREAD_CPUTIME_ID, &end);
845 timespecsub(&end, &start, &diff);
846 TDEBUGF("done operations in: %lld.%09llu s",
847 (unsigned long long)diff.tv_sec, (unsigned long long)diff.tv_nsec);
848
849 TDEBUGF("doing root removals");
850 clock_gettime(CLOCK_THREAD_CPUTIME_ID, &start);
851 for (i = 0; i < 2 * (ITER / 100) + 1; i++) {
852 tmp = RB_ROOT(&root);
853 if (tmp == NULL)
854 errx(1, "RB_ROOT error");
855 if (RB_REMOVE(tree, &root, tmp) != tmp)
856 errx(1, "RB_REMOVE error");
857 }
858 clock_gettime(CLOCK_THREAD_CPUTIME_ID, &end);
859 timespecsub(&end, &start, &diff);
860 TDEBUGF("done root removals in: %llu.%09llu s",
861 (unsigned long long)diff.tv_sec, (unsigned long long)diff.tv_nsec);
862 }
863
864 free(nodes);
865 free(perm);
866 free(nums);
867
868 return 0;
869 }
870
871
872 static int
compare(const struct node * a,const struct node * b)873 compare(const struct node *a, const struct node *b)
874 {
875 return a->key - b->key;
876 }
877
878 #ifdef RB_TEST_DIAGNOSTIC
879 static void
print_helper(const struct node * n,int indent)880 print_helper(const struct node *n, int indent)
881 {
882 if (RB_RIGHT(n, node_link))
883 print_helper(RB_RIGHT(n, node_link), indent + 4);
884 TDEBUGF("%*s key=%d :: size=%zu :: rank=%d :: rdiff %lu:%lu",
885 indent, "", n->key, n->size, RB_RANK(tree, n),
886 _RB_GET_RDIFF(n, _RB_LDIR, node_link),
887 _RB_GET_RDIFF(n, _RB_RDIR, node_link));
888 if (RB_LEFT(n, node_link))
889 print_helper(RB_LEFT(n, node_link), indent + 4);
890 }
891
892 static void
print_tree(const struct tree * t)893 print_tree(const struct tree *t)
894 {
895 if (RB_ROOT(t)) print_helper(RB_ROOT(t), 0);
896 }
897 #endif
898
899 #ifdef DOAUGMENT
900 static int
tree_augment(struct node * elm)901 tree_augment(struct node *elm)
902 {
903 size_t newsize = 1, newheight = 0;
904 if ((RB_LEFT(elm, node_link))) {
905 newsize += (RB_LEFT(elm, node_link))->size;
906 newheight = MAX((RB_LEFT(elm, node_link))->height, newheight);
907 }
908 if ((RB_RIGHT(elm, node_link))) {
909 newsize += (RB_RIGHT(elm, node_link))->size;
910 newheight = MAX((RB_RIGHT(elm, node_link))->height, newheight);
911 }
912 newheight += 1;
913 if (elm->size != newsize || elm->height != newheight) {
914 elm->size = newsize;
915 elm->height = newheight;
916 return 1;
917 }
918 return 0;
919 }
920 #endif
921
922
923 void
mix_operations(int * perm,int psize,struct node * nodes,int nsize,int insertions,int reads,int do_reads)924 mix_operations(int *perm, int psize, struct node *nodes, int nsize,
925 int insertions, int reads, int do_reads)
926 {
927 int i, rank;
928 struct node *tmp, *ins;
929 struct node it;
930 assert(psize == nsize);
931 assert(insertions + reads <= psize);
932
933 for(i = 0; i < insertions; i++) {
934 //TDEBUGF("iteration %d", i);
935 tmp = &(nodes[i]);
936 if (tmp == NULL) err(1, "malloc");
937 tmp->size = 1;
938 tmp->height = 1;
939 tmp->key = perm[i];
940 //TDEBUGF("inserting %d", tmp->key);
941 if (RB_INSERT(tree, &root, tmp) != NULL)
942 errx(1, "RB_INSERT failed");
943 print_tree(&root);
944 #ifdef DOAUGMENT
945 //TDEBUGF("size = %zu", RB_ROOT(&root)->size);
946 assert(RB_ROOT(&root)->size == i + 1);
947 #endif
948
949 #ifdef RB_TEST_RANK
950 if (i % RANK_TEST_ITERATIONS == 0) {
951 rank = RB_RANK(tree, RB_ROOT(&root));
952 if (rank == -2)
953 errx(1, "rank error");
954 }
955 #endif
956 }
957 tmp = &(nodes[insertions]);
958 tmp->key = ITER + 5;
959 tmp->size = 1;
960 tmp->height = 1;
961 RB_INSERT(tree, &root, tmp);
962 if (do_reads) {
963 for (i = 0; i < insertions; i++) {
964 it.key = perm[i];
965 ins = RB_FIND(tree, &root, &it);
966 if ((ins == NULL) || ins->key != it.key)
967 errx(1, "RB_FIND failed");
968 }
969 for (i = insertions; i < insertions + reads; i++) {
970 it.key = perm[i];
971 ins = RB_NFIND(tree, &root, &it);
972 if (ins->key < it.key)
973 errx(1, "RB_NFIND failed");
974 }
975 }
976 }
977