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