This source file includes following definitions.
- test_insert1_setup
- START_TEST
- START_TEST
- START_TEST
- START_TEST
- START_TEST
- START_TEST
- test_insert2_setup
- START_TEST
- START_TEST
- START_TEST
- START_TEST
- START_TEST
- START_TEST
- START_TEST
- START_TEST
- test_remove1_setup
- START_TEST
- START_TEST
- START_TEST
- START_TEST
- test_remove2_setup
- START_TEST
- START_TEST
- START_TEST
- START_TEST
- START_TEST
- shuffle
- START_TEST
- START_TEST
- test_check_generator
- START_TEST
- test_create_tree
- START_TEST
- START_TEST
- START_TEST
- START_TEST
- START_TEST
- START_TEST
- test_setup_gap_node
- test_setup_gap_node_noadvance
- START_TEST
- START_TEST
- START_TEST
- START_TEST
- START_TEST
- START_TEST
- START_TEST
- START_TEST
- START_TEST
- START_TEST
- START_TEST
- START_TEST
- START_TEST
- START_TEST
- START_TEST
- START_TEST
- START_TEST
- START_TEST
- START_TEST
- basic_suite
- main
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 #include <config.h>
21
22 #include <stdarg.h>
23 #include <stdlib.h>
24
25 #include <check.h>
26 #include "emacs-compat.h"
27
28 #define EMACS_LISP_H
29 #define ITREE_DEBUG 1
30 #define ITREE_TESTING
31 #include "itree.c"
32
33
34
35 static struct itree_tree tree;
36 static struct itree_node A, B, C, D, E;
37 static struct itree_node N_05, N_10, N_15, N_20, N_30, N_40;
38 static struct itree_node N_50, N_70, N_80, N_90, N_85, N_95;
39
40
41
42
43
44
45
46
47
48
49
50 static void
51 test_insert1_setup (void)
52 {
53 enum { N = 6 };
54 const int values[N] = {50, 30, 20, 10, 15, 5};
55 struct itree_node *nodes[N] = {&N_50, &N_30, &N_20, &N_10, &N_15, &N_05};
56 interval_tree_init (&tree);
57 for (int i = 0; i < N; ++i)
58 {
59 nodes[i]->begin = nodes[i]->end = values[i];
60 nodes[i]->otick = tree.otick;
61 }
62 }
63
64 START_TEST (test_insert_1)
65 {
66
67
68
69
70 interval_tree_insert (&tree, &N_50);
71 ck_assert (! N_50.red);
72 ck_assert_ptr_eq (&N_50, tree.root);
73 }
74 END_TEST
75
76 START_TEST (test_insert_2)
77 {
78
79
80
81
82
83
84 interval_tree_insert (&tree, &N_50);
85 interval_tree_insert (&tree, &N_30);
86 ck_assert (! N_50.red);
87 ck_assert (N_30.red);
88 ck_assert_ptr_eq (&N_50, tree.root);
89 ck_assert_ptr_eq (N_30.parent, &N_50);
90 ck_assert_ptr_eq (N_50.left, &N_30);
91 ck_assert_ptr_null (N_50.right);
92 ck_assert_ptr_null (N_30.left);
93 ck_assert_ptr_null (N_30.right);
94 }
95 END_TEST
96
97 START_TEST (test_insert_3)
98 {
99
100
101
102
103
104
105 interval_tree_insert (&tree, &N_50);
106 interval_tree_insert (&tree, &N_30);
107 interval_tree_insert (&tree, &N_20);
108 ck_assert (N_50.red);
109 ck_assert (! N_30.red);
110 ck_assert (N_20.red);
111 ck_assert_ptr_eq (&N_30, tree.root);
112 ck_assert_ptr_eq (N_50.parent, &N_30);
113 ck_assert_ptr_eq (N_30.right, &N_50);
114 ck_assert_ptr_eq (N_30.left, &N_20);
115 ck_assert_ptr_null (N_20.left);
116 ck_assert_ptr_null (N_20.right);
117 ck_assert_ptr_eq (N_20.parent, &N_30);
118 }
119 END_TEST
120
121 START_TEST (test_insert_4)
122 {
123
124
125
126
127
128
129
130
131 interval_tree_insert (&tree, &N_50);
132 interval_tree_insert (&tree, &N_30);
133 interval_tree_insert (&tree, &N_20);
134 interval_tree_insert (&tree, &N_10);
135 ck_assert (! N_50.red);
136 ck_assert (! N_30.red);
137 ck_assert (! N_20.red);
138 ck_assert (N_10.red);
139 ck_assert_ptr_eq (&N_30, tree.root);
140 ck_assert_ptr_eq (N_50.parent, &N_30);
141 ck_assert_ptr_eq (N_30.right, &N_50);
142 ck_assert_ptr_eq (N_30.left, &N_20);
143 ck_assert_ptr_eq (N_20.left, &N_10);
144 ck_assert_ptr_null (N_20.right);
145 ck_assert_ptr_eq (N_20.parent, &N_30);
146 ck_assert_ptr_eq (N_10.parent, &N_20);
147 ck_assert_ptr_eq (N_20.left, &N_10);
148 ck_assert_ptr_null (N_10.right);
149 }
150 END_TEST
151
152 START_TEST (test_insert_5)
153 {
154
155
156
157
158
159
160
161
162 interval_tree_insert (&tree, &N_50);
163 interval_tree_insert (&tree, &N_30);
164 interval_tree_insert (&tree, &N_20);
165 interval_tree_insert (&tree, &N_10);
166 interval_tree_insert (&tree, &N_15);
167 ck_assert (! N_50.red);
168 ck_assert (! N_30.red);
169 ck_assert (N_20.red);
170 ck_assert (N_10.red);
171 ck_assert (! N_15.red);
172 ck_assert_ptr_eq (&N_30, tree.root);
173 ck_assert_ptr_eq (N_50.parent, &N_30);
174 ck_assert_ptr_eq (N_30.right, &N_50);
175 ck_assert_ptr_eq (N_30.left, &N_15);
176 ck_assert_ptr_null (N_20.left);
177 ck_assert_ptr_null (N_20.right);
178 ck_assert_ptr_eq (N_20.parent, &N_15);
179 ck_assert_ptr_eq (N_10.parent, &N_15);
180 ck_assert_ptr_null (N_20.left);
181 ck_assert_ptr_null (N_10.right);
182 ck_assert_ptr_eq (N_15.right, &N_20);
183 ck_assert_ptr_eq (N_15.left, &N_10);
184 ck_assert_ptr_eq (N_15.parent, &N_30);
185 }
186 END_TEST
187
188 START_TEST (test_insert_6)
189 {
190
191
192
193
194
195
196
197
198
199
200 interval_tree_insert (&tree, &N_50);
201 interval_tree_insert (&tree, &N_30);
202 interval_tree_insert (&tree, &N_20);
203 interval_tree_insert (&tree, &N_10);
204 interval_tree_insert (&tree, &N_15);
205 interval_tree_insert (&tree, &N_05);
206 ck_assert (! N_50.red);
207 ck_assert (! N_30.red);
208 ck_assert (! N_20.red);
209 ck_assert (! N_10.red);
210 ck_assert (N_15.red);
211 ck_assert (N_05.red);
212 ck_assert_ptr_eq (&N_30, tree.root);
213 ck_assert_ptr_eq (N_50.parent, &N_30);
214 ck_assert_ptr_eq (N_30.right, &N_50);
215 ck_assert_ptr_eq (N_30.left, &N_15);
216 ck_assert_ptr_null (N_20.left);
217 ck_assert_ptr_null (N_20.right);
218 ck_assert_ptr_eq (N_20.parent, &N_15);
219 ck_assert_ptr_eq (N_10.parent, &N_15);
220 ck_assert_ptr_null (N_20.left);
221 ck_assert_ptr_null (N_10.right);
222 ck_assert_ptr_eq (N_15.right, &N_20);
223 ck_assert_ptr_eq (N_15.left, &N_10);
224 ck_assert_ptr_eq (N_15.parent, &N_30);
225 ck_assert_ptr_eq (N_05.parent, &N_10);
226 ck_assert_ptr_eq (N_10.left, &N_05);
227 ck_assert_ptr_null (N_05.right);
228 }
229 END_TEST
230
231
232
233
234
235 static void
236 test_insert2_setup (void)
237 {
238 enum { N = 6 };
239 const int values[] = {50, 70, 80, 90, 85, 95};
240 struct itree_node *nodes[N] = {&N_50, &N_70, &N_80, &N_90, &N_85, &N_95};
241 interval_tree_init (&tree);
242 for (int i = 0; i < N; ++i)
243 {
244 nodes[i]->begin = nodes[i]->end = values[i];
245 nodes[i]->otick = tree.otick;
246 }
247 }
248
249 START_TEST (test_insert_7)
250 {
251
252
253
254
255 interval_tree_insert (&tree, &N_50);
256 ck_assert (! N_50.red);
257 ck_assert_ptr_eq (&N_50, tree.root);
258 }
259 END_TEST
260
261 START_TEST (test_insert_8)
262 {
263
264
265
266
267
268
269 interval_tree_insert (&tree, &N_50);
270 interval_tree_insert (&tree, &N_70);
271 ck_assert (! N_50.red);
272 ck_assert (N_70.red);
273 ck_assert_ptr_eq (&N_50, tree.root);
274 ck_assert_ptr_eq (N_70.parent, &N_50);
275 ck_assert_ptr_eq (N_50.right, &N_70);
276 ck_assert_ptr_null (N_50.left);
277 ck_assert_ptr_null (N_70.right);
278 ck_assert_ptr_null (N_70.left);
279 }
280 END_TEST
281
282 START_TEST (test_insert_9)
283 {
284
285
286
287
288
289
290 interval_tree_insert (&tree, &N_50);
291 interval_tree_insert (&tree, &N_70);
292 interval_tree_insert (&tree, &N_80);
293 ck_assert (N_50.red);
294 ck_assert (! N_70.red);
295 ck_assert (N_80.red);
296 ck_assert_ptr_eq (&N_70, tree.root);
297 ck_assert_ptr_eq (N_50.parent, &N_70);
298 ck_assert_ptr_eq (N_70.right, &N_80);
299 ck_assert_ptr_eq (N_70.left, &N_50);
300 ck_assert_ptr_null (N_80.right);
301 ck_assert_ptr_null (N_80.left);
302 ck_assert_ptr_eq (N_80.parent, &N_70);
303 }
304 END_TEST
305
306 START_TEST (test_insert_10)
307 {
308
309
310
311
312
313
314
315
316 interval_tree_insert (&tree, &N_50);
317 interval_tree_insert (&tree, &N_70);
318 interval_tree_insert (&tree, &N_80);
319 interval_tree_insert (&tree, &N_90);
320 ck_assert (! N_50.red);
321 ck_assert (! N_70.red);
322 ck_assert (! N_80.red);
323 ck_assert (N_90.red);
324 ck_assert_ptr_eq (&N_70, tree.root);
325 ck_assert_ptr_eq (N_50.parent, &N_70);
326 ck_assert_ptr_eq (N_70.right, &N_80);
327 ck_assert_ptr_eq (N_70.left, &N_50);
328 ck_assert_ptr_eq (N_80.right, &N_90);
329 ck_assert_ptr_null (N_80.left);
330 ck_assert_ptr_eq (N_80.parent, &N_70);
331 ck_assert_ptr_eq (N_90.parent, &N_80);
332 ck_assert_ptr_eq (N_80.right, &N_90);
333 ck_assert_ptr_null (N_90.left);
334 }
335 END_TEST
336
337 START_TEST (test_insert_11)
338 {
339
340
341
342
343
344
345
346
347 interval_tree_insert (&tree, &N_50);
348 interval_tree_insert (&tree, &N_70);
349 interval_tree_insert (&tree, &N_80);
350 interval_tree_insert (&tree, &N_90);
351 interval_tree_insert (&tree, &N_85);
352 ck_assert (! N_50.red);
353 ck_assert (! N_70.red);
354 ck_assert (N_80.red);
355 ck_assert (N_90.red);
356 ck_assert (! N_85.red);
357 ck_assert_ptr_eq (&N_70, tree.root);
358 ck_assert_ptr_eq (N_50.parent, &N_70);
359 ck_assert_ptr_eq (N_70.right, &N_85);
360 ck_assert_ptr_eq (N_70.left, &N_50);
361 ck_assert_ptr_null (N_80.right);
362 ck_assert_ptr_null (N_80.left);
363 ck_assert_ptr_eq (N_80.parent, &N_85);
364 ck_assert_ptr_eq (N_90.parent, &N_85);
365 ck_assert_ptr_null (N_80.right);
366 ck_assert_ptr_null (N_90.left);
367 ck_assert_ptr_eq (N_85.right, &N_90);
368 ck_assert_ptr_eq (N_85.left, &N_80);
369 ck_assert_ptr_eq (N_85.parent, &N_70);
370
371 }
372 END_TEST
373
374 START_TEST (test_insert_12)
375 {
376
377
378
379
380
381
382
383
384
385
386 interval_tree_insert (&tree, &N_50);
387 interval_tree_insert (&tree, &N_70);
388 interval_tree_insert (&tree, &N_80);
389 interval_tree_insert (&tree, &N_90);
390 interval_tree_insert (&tree, &N_85);
391 interval_tree_insert (&tree, &N_95);
392 ck_assert (! N_50.red);
393 ck_assert (! N_70.red);
394 ck_assert (! N_80.red);
395 ck_assert (! N_90.red);
396 ck_assert (N_85.red);
397 ck_assert (N_95.red);
398 ck_assert_ptr_eq (&N_70, tree.root);
399 ck_assert_ptr_eq (N_50.parent, &N_70);
400 ck_assert_ptr_eq (N_70.right, &N_85);
401 ck_assert_ptr_eq (N_70.left, &N_50);
402 ck_assert_ptr_null (N_80.right);
403 ck_assert_ptr_null (N_80.left);
404 ck_assert_ptr_eq (N_80.parent, &N_85);
405 ck_assert_ptr_eq (N_90.parent, &N_85);
406 ck_assert_ptr_null (N_80.right);
407 ck_assert_ptr_null (N_90.left);
408 ck_assert_ptr_eq (N_85.right, &N_90);
409 ck_assert_ptr_eq (N_85.left, &N_80);
410 ck_assert_ptr_eq (N_85.parent, &N_70);
411 ck_assert_ptr_eq (N_95.parent, &N_90);
412 ck_assert_ptr_eq (N_90.right, &N_95);
413 ck_assert_ptr_null (N_95.left);
414 }
415 END_TEST
416
417 START_TEST (test_insert_13)
418 {
419 enum { N = 4 };
420 const int values[N] = {10, 20, 30, 40};
421 struct itree_node *nodes[N] = {&N_10, &N_20, &N_30, &N_40};
422 interval_tree_init (&tree);
423 for (int i = 0; i < N; ++i)
424 itree_insert (&tree, nodes[i], values[i], values[i]);
425
426 ck_assert_ptr_eq (tree.root, &N_20);
427 ck_assert_ptr_eq (N_20.left, &N_10);
428 ck_assert_ptr_eq (N_20.right, &N_30);
429 ck_assert_ptr_eq (N_30.right, &N_40);
430 ck_assert (! N_10.red);
431 ck_assert (! N_20.red);
432 ck_assert (! N_30.red);
433 ck_assert (N_40.red);
434 }
435 END_TEST
436
437 START_TEST (test_insert_14)
438 {
439 enum { N = 3 };
440 struct itree_node nodes[N];
441 interval_tree_init (&tree);
442
443 for (int i = 0; i < N; ++i)
444 itree_insert (&tree, &nodes[i], 10, 10);
445 for (int i = 0; i < N; ++i)
446 ck_assert (interval_tree_contains (&tree, &nodes[i]));
447 }
448 END_TEST
449
450
451
452
453
454
455
456
457
458 static void
459 test_remove1_setup (void)
460 {
461 interval_tree_init (&tree);
462 tree.root = &B;
463 A.parent = &B; B.parent = NULL; C.parent = &D; D.parent = &B; E.parent = &D;
464 A.left = A.right = C.left = C.right = E.left = E.right = NULL;
465 B.left = &A; B.right = &D;
466 D.left = &C; D.right = &E;
467 A.offset = B.offset = C.offset = D.offset = E.offset = 0;
468 A.otick = B.otick = C.otick = D.otick = E.otick = tree.otick;
469 }
470
471
472
473
474
475
476
477
478
479 START_TEST (test_remove_1)
480 {
481 B.red = A.red = C.red = E.red = false;
482 D.red = true;
483 interval_tree_remove_fix (&tree, &A, &B);
484
485 ck_assert (! A.red);
486 ck_assert (! B.red);
487 ck_assert (C.red);
488 ck_assert (! D.red);
489 ck_assert (! E.red);
490 ck_assert_ptr_eq (A.parent, &B);
491 ck_assert_ptr_eq (B.left, &A);
492 ck_assert_ptr_eq (B.right, &C);
493 ck_assert_ptr_eq (C.parent, &B);
494 ck_assert_ptr_eq (E.parent, &D);
495 ck_assert_ptr_eq (D.right, &E);
496 ck_assert_ptr_eq (D.left, &B);
497 ck_assert_ptr_eq (tree.root, &D);
498 }
499 END_TEST
500
501
502 START_TEST (test_remove_2)
503 {
504 B.red = D.red = A.red = C.red = E.red = false;
505 interval_tree_remove_fix (&tree, &A, &B);
506
507 ck_assert (! A.red);
508 ck_assert (! B.red);
509 ck_assert (! C.red);
510 ck_assert (D.red);
511 ck_assert (! E.red);
512 ck_assert_ptr_eq (A.parent, &B);
513 ck_assert_ptr_eq (B.left, &A);
514 ck_assert_ptr_eq (B.right, &D);
515 ck_assert_ptr_eq (C.parent, &D);
516 ck_assert_ptr_eq (E.parent, &D);
517 ck_assert_ptr_eq (tree.root, &B);
518 }
519 END_TEST
520
521
522 START_TEST (test_remove_3)
523 {
524 D.red = A.red = E.red = false;
525 B.red = C.red = true;
526 interval_tree_remove_fix (&tree, &A, &B);
527
528 ck_assert (! A.red);
529 ck_assert (! B.red);
530 ck_assert (! C.red);
531 ck_assert (! D.red);
532 ck_assert (! E.red);
533 ck_assert_ptr_eq (A.parent, &B);
534 ck_assert_ptr_eq (B.left, &A);
535 ck_assert_ptr_null (B.right);
536 ck_assert_ptr_eq (&C, tree.root);
537 ck_assert_ptr_eq (C.left, &B);
538 ck_assert_ptr_eq (C.right, &D);
539 ck_assert_ptr_eq (E.parent, &D);
540 ck_assert_ptr_null (D.left);
541 }
542 END_TEST
543
544
545 START_TEST (test_remove_4)
546 {
547 B.red = C.red = E.red = true;
548 A.red = D.red = false;
549 interval_tree_remove_fix (&tree, &A, &B);
550
551 ck_assert (! A.red);
552 ck_assert (! B.red);
553 ck_assert (C.red);
554 ck_assert (! D.red);
555 ck_assert (! E.red);
556 ck_assert_ptr_eq (A.parent, &B);
557 ck_assert_ptr_eq (B.left, &A);
558 ck_assert_ptr_eq (B.right, &C);
559 ck_assert_ptr_eq (C.parent, &B);
560 ck_assert_ptr_eq (E.parent, &D);
561 ck_assert_ptr_eq (tree.root, &D);
562 }
563 END_TEST
564
565
566
567
568
569 static void
570 test_remove2_setup (void)
571 {
572 interval_tree_init (&tree);
573 tree.root = &B;
574 A.parent = &B; B.parent = NULL; C.parent = &D; D.parent = &B; E.parent = &D;
575 A.right = A.left = C.right = C.left = E.right = E.left = NULL;
576 B.right = &A; B.left = &D;
577 D.right = &C; D.left = &E;
578 }
579
580
581
582
583
584
585
586
587
588 START_TEST (test_remove_5)
589 {
590 B.red = A.red = C.red = E.red = false;
591 D.red = true;
592 interval_tree_remove_fix (&tree, &A, &B);
593
594 ck_assert (! A.red);
595 ck_assert (! B.red);
596 ck_assert (C.red);
597 ck_assert (! D.red);
598 ck_assert (! E.red);
599 ck_assert_ptr_eq (A.parent, &B);
600 ck_assert_ptr_eq (B.right, &A);
601 ck_assert_ptr_eq (B.left, &C);
602 ck_assert_ptr_eq (C.parent, &B);
603 ck_assert_ptr_eq (E.parent, &D);
604 ck_assert_ptr_eq (D.left, &E);
605 ck_assert_ptr_eq (D.right, &B);
606 ck_assert_ptr_eq (tree.root, &D);
607 }
608 END_TEST
609
610
611 START_TEST (test_remove_6)
612 {
613 B.red = D.red = A.red = C.red = E.red = false;
614 interval_tree_remove_fix (&tree, &A, &B);
615
616 ck_assert (! A.red);
617 ck_assert (! B.red);
618 ck_assert (! C.red);
619 ck_assert (D.red);
620 ck_assert (! E.red);
621 ck_assert_ptr_eq (A.parent, &B);
622 ck_assert_ptr_eq (B.right, &A);
623 ck_assert_ptr_eq (B.left, &D);
624 ck_assert_ptr_eq (C.parent, &D);
625 ck_assert_ptr_eq (E.parent, &D);
626 ck_assert_ptr_eq (tree.root, &B);
627 }
628 END_TEST
629
630
631 START_TEST (test_remove_7)
632 {
633 D.red = A.red = E.red = false;
634 B.red = C.red = true;
635 interval_tree_remove_fix (&tree, &A, &B);
636
637 ck_assert (! A.red);
638 ck_assert (! B.red);
639 ck_assert (! C.red);
640 ck_assert (! D.red);
641 ck_assert (! E.red);
642 ck_assert_ptr_eq (A.parent, &B);
643 ck_assert_ptr_eq (B.right, &A);
644 ck_assert_ptr_null (B.left);
645 ck_assert_ptr_eq (&C, tree.root);
646 ck_assert_ptr_eq (C.right, &B);
647 ck_assert_ptr_eq (C.left, &D);
648 ck_assert_ptr_eq (E.parent, &D);
649 ck_assert_ptr_null (D.right);
650 }
651 END_TEST
652
653
654 START_TEST (test_remove_8)
655 {
656 B.red = C.red = E.red = true;
657 A.red = D.red = false;
658 interval_tree_remove_fix (&tree, &A, &B);
659
660 ck_assert (! A.red);
661 ck_assert (! B.red);
662 ck_assert (C.red);
663 ck_assert (! D.red);
664 ck_assert (! E.red);
665 ck_assert_ptr_eq (A.parent, &B);
666 ck_assert_ptr_eq (B.right, &A);
667 ck_assert_ptr_eq (B.left, &C);
668 ck_assert_ptr_eq (C.parent, &B);
669 ck_assert_ptr_eq (E.parent, &D);
670 ck_assert_ptr_eq (tree.root, &D);
671 }
672 END_TEST
673
674 START_TEST (test_remove_9)
675 {
676 enum { N = 4 };
677 const int values[N] = {10, 20, 30, 40};
678 struct itree_node *nodes[N] = {&N_10, &N_20, &N_30, &N_40};
679 interval_tree_init (&tree);
680 for (int i = 0; i < N; ++i)
681 itree_insert (&tree, nodes[i], values[i], values[i]);
682
683 ck_assert (tree.root == &N_20);
684 ck_assert (N_20.left == &N_10);
685 ck_assert (N_20.right == &N_30);
686 ck_assert (N_30.right == &N_40);
687 ck_assert (! N_20.red);
688 ck_assert (! N_10.red);
689 ck_assert (! N_30.red);
690 ck_assert (N_40.red);
691
692 itree_remove (&tree, &N_10);
693
694 ck_assert_ptr_eq (tree.root, &N_30);
695 ck_assert_ptr_null (N_30.parent);
696 ck_assert_ptr_eq (N_30.left, &N_20);
697 ck_assert_ptr_eq (N_30.right, &N_40);
698 ck_assert (! N_20.red);
699 ck_assert (! N_30.red);
700 ck_assert (! N_40.red);
701 }
702 END_TEST
703
704 static void
705 shuffle (int *index, int n)
706 {
707 for (int i = n - 1; i >= 0; --i)
708 {
709 int j = random () % (i + 1);
710 int h = index[j];
711 index[j] = index[i];
712 index[i] = h;
713 }
714 }
715
716 START_TEST (test_remove_10)
717 {
718 enum { N = 3 };
719 int index[N];
720 for (int i = 0; i < N; ++i)
721 index[i] = i;
722 srand (42);
723 shuffle (index, N);
724
725 interval_tree_init (&tree);
726 struct itree_node nodes[N];
727 for (int i = 0; i < N; ++i)
728 {
729 ptrdiff_t pos = (i + 1) * 10;
730 itree_insert (&tree, &nodes[index[i]], pos, pos + 1);
731 }
732
733 shuffle (index, N);
734 for (int i = 0; i < N; ++i)
735 {
736 ck_assert (interval_tree_contains (&tree, &nodes[index[i]]));
737 itree_remove (&tree, &nodes[index[i]]);
738 }
739 ck_assert_ptr_null (tree.root);
740 ck_assert_int_eq (tree.size, 0);
741 }
742 END_TEST
743
744
745
746
747
748
749 START_TEST (test_generator_1)
750 {
751 struct itree_node node, *n;
752 struct itree_iterator *g;
753 interval_tree_init (&tree);
754
755 itree_insert (&tree, &node, 10, 20);
756 g = itree_iterator_start (&tree, 0, 30, ITREE_ASCENDING, NULL, 0);
757 n = itree_iterator_next (g);
758 ck_assert_ptr_eq (n, &node);
759 ck_assert_int_eq (n->begin, 10);
760 ck_assert_int_eq (n->end, 20);
761 ck_assert_ptr_null (itree_iterator_next (g));
762 ck_assert_ptr_null (itree_iterator_next (g));
763 ck_assert_ptr_null (itree_iterator_next (g));
764 itree_iterator_finish (g);
765
766 g = itree_iterator_start (&tree, 30, 50, ITREE_ASCENDING, NULL, 0);
767 ck_assert_ptr_null (itree_iterator_next (g));
768 ck_assert_ptr_null (itree_iterator_next (g));
769 ck_assert_ptr_null (itree_iterator_next (g));
770 itree_iterator_finish (g);
771 }
772 END_TEST
773
774 static void
775 test_check_generator (struct itree_tree *tree,
776 ptrdiff_t begin, ptrdiff_t end,
777 int n, ...)
778 {
779 va_list ap;
780 struct itree_iterator *g =
781 itree_iterator_start (tree, begin, end, ITREE_ASCENDING, NULL, 0);
782
783 va_start (ap, n);
784 for (int i = 0; i < n; ++i)
785 {
786 struct itree_node *node = itree_iterator_next (g);
787 ck_assert_ptr_nonnull (node);
788 ck_assert_int_eq (node->begin, va_arg (ap, ptrdiff_t));
789 }
790 va_end (ap);
791 ck_assert_ptr_null (itree_iterator_next (g));
792 ck_assert_ptr_null (itree_iterator_next (g));
793 itree_iterator_finish (g);
794 }
795
796 START_TEST (test_generator_2)
797 {
798 interval_tree_init (&tree);
799 struct itree_node nodes[3];
800 for (int i = 0; i < 3; ++i)
801 itree_insert (&tree, &nodes[i], 10 * (i + 1), 10 * (i + 2));
802
803 test_check_generator (&tree, 0, 50, 3,
804 10, 20, 30);
805 test_check_generator (&tree, 0, 10, 0);
806 test_check_generator (&tree, 40, 50, 0);
807 test_check_generator (&tree, 15, 35, 3,
808 10, 20, 30);
809 test_check_generator (&tree, -100, -50, 0);
810 test_check_generator (&tree, -100, -50, 0);
811 test_check_generator (&tree, 100, 50, 0);
812 test_check_generator (&tree, 100, 150, 0);
813 test_check_generator (&tree, 0, 0, 0);
814 test_check_generator (&tree, 40, 40, 0);
815 test_check_generator (&tree, 30, 30, 0);
816 test_check_generator (&tree, 35, 35, 1,
817 30);
818 }
819 END_TEST
820
821 static void
822 test_create_tree (struct itree_node *nodes, int n, bool doshuffle)
823 {
824 int *index = calloc (n, sizeof (int));
825 for (int i = 0; i < n; ++i)
826 index[i] = i;
827 if (doshuffle)
828 {
829 srand (42);
830 shuffle (index, n);
831 }
832
833 interval_tree_init (&tree);
834 for (int i = 0; i < n; ++i)
835 {
836 struct itree_node *node = &nodes[index[i]];
837 itree_insert (&tree, node, node->begin, node->end);
838 }
839 free (index);
840 }
841
842 START_TEST (test_generator_3)
843 {
844 enum { N = 3 };
845 struct itree_node nodes[N] = {{.begin = 10, .end = 10},
846 {.begin = 10, .end = 10},
847 {.begin = 10, .end = 10}};
848 test_create_tree (nodes, N, true);
849 test_check_generator (&tree, 0, 10, 0);
850 test_check_generator (&tree, 10, 10, 3,
851 10, 10, 10);
852 test_check_generator (&tree, 10, 20, 3,
853 10, 10, 10);
854 }
855 END_TEST
856
857 START_TEST (test_generator_5)
858 {
859 enum { N = 4 };
860 struct itree_node nodes[N] = {{.begin = 10, .end = 30},
861 {.begin = 20, .end = 40},
862 {.begin = 30, .end = 50},
863 {.begin = 40, .end = 60}};
864 test_create_tree (nodes, N, false);
865 struct itree_iterator *g =
866 itree_iterator_start (&tree, 0, 100, ITREE_PRE_ORDER, NULL, 0);
867 for (int i = 0; i < N; ++i)
868 {
869 struct itree_node *n = itree_iterator_next (g);
870 ck_assert_ptr_nonnull (n);
871 switch (i)
872 {
873 case 0: ck_assert_int_eq (20, n->begin); break;
874 case 1: ck_assert_int_eq (10, n->begin); break;
875 case 2: ck_assert_int_eq (30, n->begin); break;
876 case 3: ck_assert_int_eq (40, n->begin); break;
877 }
878 }
879 itree_iterator_finish (g);
880 }
881 END_TEST
882
883 START_TEST (test_generator_6)
884 {
885 enum { N = 4 };
886 struct itree_node nodes[N] = {{.begin = 10, .end = 30},
887 {.begin = 20, .end = 40},
888 {.begin = 30, .end = 50},
889 {.begin = 40, .end = 60}};
890 test_create_tree (nodes, N, true);
891 struct itree_iterator *g =
892 itree_iterator_start (&tree, 0, 100, ITREE_ASCENDING, NULL, 0);
893 for (int i = 0; i < N; ++i)
894 {
895 struct itree_node *n = itree_iterator_next (g);
896 ck_assert_ptr_nonnull (n);
897 switch (i)
898 {
899 case 0: ck_assert_int_eq (10, n->begin); break;
900 case 1: ck_assert_int_eq (20, n->begin); break;
901 case 2: ck_assert_int_eq (30, n->begin); break;
902 case 3: ck_assert_int_eq (40, n->begin); break;
903 }
904 }
905 itree_iterator_finish (g);
906 }
907 END_TEST
908
909 START_TEST (test_generator_7)
910 {
911 enum { N = 4 };
912 struct itree_node nodes[N] = {{.begin = 10, .end = 30},
913 {.begin = 20, .end = 40},
914 {.begin = 30, .end = 50},
915 {.begin = 40, .end = 60}};
916 test_create_tree (nodes, N, true);
917 struct itree_iterator *g =
918 itree_iterator_start (&tree, 0, 100, ITREE_DESCENDING, NULL, 0);
919 for (int i = 0; i < N; ++i)
920 {
921 struct itree_node *n = itree_iterator_next (g);
922 ck_assert_ptr_nonnull (n);
923 switch (i)
924 {
925 case 0: ck_assert_int_eq (40, n->begin); break;
926 case 1: ck_assert_int_eq (30, n->begin); break;
927 case 2: ck_assert_int_eq (20, n->begin); break;
928 case 3: ck_assert_int_eq (10, n->begin); break;
929 }
930 }
931 itree_iterator_finish (g);
932 }
933 END_TEST
934
935 START_TEST (test_generator_8)
936 {
937 enum { N = 2 };
938 struct itree_node nodes[N] = {{.begin = 20, .end = 30},
939 {.begin = 40, .end = 50}};
940 test_create_tree (nodes, N, false);
941 struct itree_iterator *g =
942 itree_iterator_start (&tree, 1, 60, ITREE_DESCENDING, NULL, 0);
943 struct itree_node *n = itree_iterator_next (g);
944 ck_assert_int_eq (n->begin, 40);
945 itree_iterator_narrow (g, 50, 60);
946 n = itree_iterator_next (g);
947 ck_assert_ptr_null (n);
948 itree_iterator_finish (g);
949 }
950 END_TEST
951
952 START_TEST (test_generator_9)
953 {
954 enum { N = 2 };
955 struct itree_node nodes[N] = {{.begin = 25, .end = 25},
956 {.begin = 20, .end = 30}};
957 test_create_tree (nodes, N, false);
958 struct itree_iterator *g =
959 itree_iterator_start (&tree, 1, 30, ITREE_DESCENDING, NULL, 0);
960 struct itree_node *n = itree_iterator_next (g);
961 ck_assert_int_eq (n->begin, 25);
962 itree_iterator_narrow (g, 25, 30);
963 n = itree_iterator_next (g);
964 ck_assert_int_eq (n->begin, 20);
965 itree_iterator_finish (g);
966 }
967 END_TEST
968
969
970
971
972
973
974 static struct itree_tree gap_tree;
975 static struct itree_node gap_node;
976
977 #define N_BEG (itree_node_begin (&gap_tree, &gap_node))
978 #define N_END (itree_node_end (&gap_tree, &gap_node))
979
980 static void
981 test_setup_gap_node (ptrdiff_t begin, ptrdiff_t end,
982 bool front_advance, bool rear_advance)
983 {
984 interval_tree_init (&gap_tree);
985 gap_node.front_advance = front_advance;
986 gap_node.rear_advance = rear_advance;
987 itree_insert (&gap_tree, &gap_node, begin, end);
988 }
989
990 static void
991 test_setup_gap_node_noadvance (ptrdiff_t begin, ptrdiff_t end)
992 {
993 test_setup_gap_node (begin, end, false, false);
994 }
995
996 START_TEST (test_gap_insert_1)
997 {
998 test_setup_gap_node_noadvance (100, 200);
999 itree_insert_gap (&gap_tree, 100 + 10, 20, false);
1000 ck_assert_int_eq (N_BEG, 100);
1001 ck_assert_int_eq (N_END, 200 + 20);
1002 }
1003 END_TEST
1004
1005 START_TEST (test_gap_insert_2)
1006 {
1007 test_setup_gap_node_noadvance (100, 200);
1008 itree_insert_gap (&gap_tree, 300, 10, false);
1009 ck_assert_int_eq (N_BEG, 100);
1010 ck_assert_int_eq (N_END, 200);
1011 }
1012 END_TEST
1013
1014 START_TEST (test_gap_insert_3)
1015 {
1016 test_setup_gap_node_noadvance (100, 200);
1017 itree_insert_gap (&gap_tree, 0, 15, false);
1018 ck_assert_int_eq (N_BEG, 100 + 15);
1019 ck_assert_int_eq (N_END, 200 + 15);
1020 }
1021 END_TEST
1022
1023 START_TEST (test_gap_insert_4)
1024 {
1025 test_setup_gap_node (100, 200, true, false);
1026 itree_insert_gap (&gap_tree, 100, 20, false);
1027 ck_assert_int_eq (N_BEG, 100 + 20);
1028 ck_assert_int_eq (N_END, 200 + 20);
1029
1030 }
1031 END_TEST
1032
1033 START_TEST (test_gap_insert_5)
1034 {
1035 test_setup_gap_node_noadvance (100, 200);
1036 itree_insert_gap (&gap_tree, 100, 20, false);
1037 ck_assert_int_eq (N_BEG, 100);
1038 ck_assert_int_eq (N_END, 200 + 20);
1039
1040 }
1041 END_TEST
1042
1043 START_TEST (test_gap_insert_6)
1044 {
1045 test_setup_gap_node (100, 200, false, true);
1046 itree_insert_gap (&gap_tree, 200, 20, false);
1047 ck_assert_int_eq (N_BEG, 100);
1048 ck_assert_int_eq (N_END, 200 + 20);
1049
1050 }
1051 END_TEST
1052
1053 START_TEST (test_gap_insert_7)
1054 {
1055 test_setup_gap_node_noadvance (100, 200);
1056 itree_insert_gap (&gap_tree, 200, 20, false);
1057 ck_assert_int_eq (N_BEG, 100);
1058 ck_assert_int_eq (N_END, 200);
1059
1060 }
1061 END_TEST
1062
1063 START_TEST (test_gap_insert_8)
1064 {
1065 test_setup_gap_node (100, 100, true, true);
1066 itree_insert_gap (&gap_tree, 100, 20, false);
1067 ck_assert_int_eq (N_BEG, 100 + 20);
1068 ck_assert_int_eq (N_END, 100 + 20);
1069
1070 }
1071 END_TEST
1072
1073 START_TEST (test_gap_insert_9)
1074 {
1075 test_setup_gap_node (100, 100, false, true);
1076 itree_insert_gap (&gap_tree, 100, 20, false);
1077 ck_assert_int_eq (N_BEG, 100);
1078 ck_assert_int_eq (N_END, 100 + 20);
1079
1080 }
1081 END_TEST
1082
1083 START_TEST (test_gap_insert_10)
1084 {
1085 test_setup_gap_node (100, 100, true, false);
1086 itree_insert_gap (&gap_tree, 100, 20, false);
1087 ck_assert_int_eq (N_BEG, 100);
1088 ck_assert_int_eq (N_END, 100);
1089
1090 }
1091 END_TEST
1092
1093 START_TEST (test_gap_insert_11)
1094 {
1095 test_setup_gap_node_noadvance (100, 100);
1096 itree_insert_gap (&gap_tree, 100, 20, false);
1097 ck_assert_int_eq (N_BEG, 100);
1098 ck_assert_int_eq (N_END, 100);
1099
1100 }
1101 END_TEST
1102
1103
1104
1105
1106
1107
1108 START_TEST (test_gap_delete_1)
1109 {
1110 test_setup_gap_node_noadvance (100, 200);
1111 itree_delete_gap (&gap_tree, 100 + 10, 20);
1112 ck_assert_int_eq (N_BEG, 100);
1113 ck_assert_int_eq (N_END, 200 - 20);
1114
1115 }
1116 END_TEST
1117
1118 START_TEST (test_gap_delete_2)
1119 {
1120 test_setup_gap_node_noadvance (100, 200);
1121 itree_delete_gap (&gap_tree, 200 + 10, 20);
1122 ck_assert_int_eq (N_BEG, 100);
1123 ck_assert_int_eq (N_END, 200);
1124
1125 }
1126 END_TEST
1127
1128 START_TEST (test_gap_delete_3)
1129 {
1130 test_setup_gap_node_noadvance (100, 200);
1131 itree_delete_gap (&gap_tree, 200, 20);
1132 ck_assert_int_eq (N_BEG, 100);
1133 ck_assert_int_eq (N_END, 200);
1134
1135 }
1136 END_TEST
1137
1138 START_TEST (test_gap_delete_4)
1139 {
1140 test_setup_gap_node_noadvance (100, 200);
1141 itree_delete_gap (&gap_tree, 100 - 20, 20);
1142 ck_assert_int_eq (N_BEG, 100 - 20);
1143 ck_assert_int_eq (N_END, 200 - 20);
1144
1145 }
1146 END_TEST
1147
1148 START_TEST (test_gap_delete_5)
1149 {
1150 test_setup_gap_node_noadvance (100, 200);
1151 itree_delete_gap (&gap_tree, 70, 20);
1152 ck_assert_int_eq (N_BEG, 100 - 20);
1153 ck_assert_int_eq (N_END, 200 - 20);
1154
1155 }
1156 END_TEST
1157
1158 START_TEST (test_gap_delete_6)
1159 {
1160 test_setup_gap_node_noadvance (100, 200);
1161 itree_delete_gap (&gap_tree, 80, 100);
1162 ck_assert_int_eq (N_BEG, 80);
1163 ck_assert_int_eq (N_END, 100);
1164 }
1165 END_TEST
1166
1167 START_TEST (test_gap_delete_7)
1168 {
1169 test_setup_gap_node_noadvance (100, 200);
1170 itree_delete_gap (&gap_tree, 120, 100);
1171 ck_assert_int_eq (N_BEG, 100);
1172 ck_assert_int_eq (N_END, 120);
1173 }
1174 END_TEST
1175
1176 START_TEST (test_gap_delete_8)
1177 {
1178 test_setup_gap_node_noadvance (100, 200);
1179 itree_delete_gap (&gap_tree, 100 - 20, 200 + 20);
1180 ck_assert_int_eq (N_BEG, 100 - 20);
1181 ck_assert_int_eq (N_END, 100 - 20);
1182
1183 }
1184 END_TEST
1185
1186
1187
1188 static Suite *
1189 basic_suite ()
1190 {
1191 Suite *s = suite_create ("basic");
1192
1193 TCase *tc = tcase_create ("insert1");
1194 tcase_add_checked_fixture (tc, test_insert1_setup, NULL);
1195 tcase_add_test (tc, test_insert_1);
1196 tcase_add_test (tc, test_insert_2);
1197 tcase_add_test (tc, test_insert_3);
1198 tcase_add_test (tc, test_insert_4);
1199 tcase_add_test (tc, test_insert_5);
1200 tcase_add_test (tc, test_insert_6);
1201 suite_add_tcase (s, tc);
1202
1203 tc = tcase_create ("insert2");
1204 tcase_add_checked_fixture (tc, test_insert2_setup, NULL);
1205 tcase_add_test (tc, test_insert_7);
1206 tcase_add_test (tc, test_insert_8);
1207 tcase_add_test (tc, test_insert_9);
1208 tcase_add_test (tc, test_insert_10);
1209 tcase_add_test (tc, test_insert_11);
1210 tcase_add_test (tc, test_insert_12);
1211 suite_add_tcase (s, tc);
1212
1213 tc = tcase_create ("insert3");
1214 tcase_add_test (tc, test_insert_13);
1215 tcase_add_test (tc, test_insert_14);
1216 suite_add_tcase (s, tc);
1217
1218 tc = tcase_create ("remove1");
1219 tcase_add_checked_fixture (tc, test_remove1_setup, NULL);
1220 tcase_add_test (tc, test_remove_1);
1221 tcase_add_test (tc, test_remove_2);
1222 tcase_add_test (tc, test_remove_3);
1223 tcase_add_test (tc, test_remove_4);
1224 suite_add_tcase (s, tc);
1225
1226 tc = tcase_create ("remove2");
1227 tcase_add_checked_fixture (tc, test_remove2_setup, NULL);
1228 tcase_add_test (tc, test_remove_5);
1229 tcase_add_test (tc, test_remove_6);
1230 tcase_add_test (tc, test_remove_7);
1231 tcase_add_test (tc, test_remove_8);
1232 suite_add_tcase (s, tc);
1233
1234 tc = tcase_create ("remove3");
1235 tcase_add_test (tc, test_remove_9);
1236 tcase_add_test (tc, test_remove_10);
1237 suite_add_tcase (s, tc);
1238
1239 tc = tcase_create ("generator");
1240 tcase_add_test (tc, test_generator_1);
1241 tcase_add_test (tc, test_generator_2);
1242 tcase_add_test (tc, test_generator_3);
1243 tcase_add_test (tc, test_generator_5);
1244 tcase_add_test (tc, test_generator_6);
1245 tcase_add_test (tc, test_generator_7);
1246 tcase_add_test (tc, test_generator_8);
1247 tcase_add_test (tc, test_generator_9);
1248 suite_add_tcase (s, tc);
1249
1250 tc = tcase_create ("insert_gap");
1251 tcase_add_test (tc, test_gap_insert_1);
1252 tcase_add_test (tc, test_gap_insert_2);
1253 tcase_add_test (tc, test_gap_insert_3);
1254 tcase_add_test (tc, test_gap_insert_4);
1255 tcase_add_test (tc, test_gap_insert_5);
1256 tcase_add_test (tc, test_gap_insert_6);
1257 tcase_add_test (tc, test_gap_insert_7);
1258 tcase_add_test (tc, test_gap_insert_8);
1259 tcase_add_test (tc, test_gap_insert_9);
1260 tcase_add_test (tc, test_gap_insert_10);
1261 tcase_add_test (tc, test_gap_insert_11);
1262 suite_add_tcase (s, tc);
1263
1264 tc = tcase_create ("delete_gap");
1265 tcase_add_test (tc, test_gap_delete_1);
1266 tcase_add_test (tc, test_gap_delete_2);
1267 tcase_add_test (tc, test_gap_delete_3);
1268 tcase_add_test (tc, test_gap_delete_4);
1269 tcase_add_test (tc, test_gap_delete_5);
1270 tcase_add_test (tc, test_gap_delete_6);
1271 tcase_add_test (tc, test_gap_delete_7);
1272 tcase_add_test (tc, test_gap_delete_8);
1273 suite_add_tcase (s, tc);
1274
1275 return s;
1276 }
1277
1278 int
1279 main (void)
1280 {
1281 Suite *s = basic_suite ();
1282 SRunner *sr = srunner_create (s);
1283
1284 init_itree ();
1285 srunner_run_all (sr, CK_ENV);
1286 int nfailed = srunner_ntests_failed (sr);
1287 srunner_free (sr);
1288 return (nfailed == 0) ? EXIT_SUCCESS : EXIT_FAILURE;
1289 }