1 | /* ET-trees data structure implementation. |
2 | Contributed by Pavel Nejedly |
3 | Copyright (C) 2002-2023 Free Software Foundation, Inc. |
4 | |
5 | This file is part of the libiberty library. |
6 | Libiberty is free software; you can redistribute it and/or |
7 | modify it under the terms of the GNU Library General Public |
8 | License as published by the Free Software Foundation; either |
9 | version 3 of the License, or (at your option) any later version. |
10 | |
11 | Libiberty is distributed in the hope that it will be useful, |
12 | but WITHOUT ANY WARRANTY; without even the implied warranty of |
13 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
14 | Library General Public License for more details. |
15 | |
16 | You should have received a copy of the GNU Library General Public |
17 | License along with libiberty; see the file COPYING3. If not see |
18 | <http://www.gnu.org/licenses/>. |
19 | |
20 | The ET-forest structure is described in: |
21 | D. D. Sleator and R. E. Tarjan. A data structure for dynamic trees. |
22 | J. G'omput. System Sci., 26(3):362 381, 1983. |
23 | */ |
24 | |
25 | #include "config.h" |
26 | #include "system.h" |
27 | #include "coretypes.h" |
28 | #include "alloc-pool.h" |
29 | #include "et-forest.h" |
30 | #include "selftest.h" |
31 | |
32 | /* We do not enable this with CHECKING_P, since it is awfully slow. */ |
33 | #undef DEBUG_ET |
34 | |
35 | #ifdef DEBUG_ET |
36 | #include "backend.h" |
37 | #include "hard-reg-set.h" |
38 | #endif |
39 | |
40 | /* The occurrence of a node in the et tree. */ |
41 | struct et_occ |
42 | { |
43 | struct et_node *of; /* The node. */ |
44 | |
45 | struct et_occ *parent; /* Parent in the splay-tree. */ |
46 | struct et_occ *prev; /* Left son in the splay-tree. */ |
47 | struct et_occ *next; /* Right son in the splay-tree. */ |
48 | |
49 | int depth; /* The depth of the node is the sum of depth |
50 | fields on the path to the root. */ |
51 | int min; /* The minimum value of the depth in the subtree |
52 | is obtained by adding sum of depth fields |
53 | on the path to the root. */ |
54 | struct et_occ *min_occ; /* The occurrence in the subtree with the minimal |
55 | depth. */ |
56 | }; |
57 | |
58 | static object_allocator<et_node> et_nodes ("et_nodes pool" ); |
59 | static object_allocator<et_occ> et_occurrences ("et_occ pool" ); |
60 | |
61 | /* Changes depth of OCC to D. */ |
62 | |
63 | static inline void |
64 | set_depth (struct et_occ *occ, int d) |
65 | { |
66 | if (!occ) |
67 | return; |
68 | |
69 | occ->min += d - occ->depth; |
70 | occ->depth = d; |
71 | } |
72 | |
73 | /* Adds D to the depth of OCC. */ |
74 | |
75 | static inline void |
76 | set_depth_add (struct et_occ *occ, int d) |
77 | { |
78 | if (!occ) |
79 | return; |
80 | |
81 | occ->min += d; |
82 | occ->depth += d; |
83 | } |
84 | |
85 | /* Sets prev field of OCC to P. */ |
86 | |
87 | static inline void |
88 | set_prev (struct et_occ *occ, struct et_occ *t) |
89 | { |
90 | #ifdef DEBUG_ET |
91 | gcc_assert (occ != t); |
92 | #endif |
93 | |
94 | occ->prev = t; |
95 | if (t) |
96 | t->parent = occ; |
97 | } |
98 | |
99 | /* Sets next field of OCC to P. */ |
100 | |
101 | static inline void |
102 | set_next (struct et_occ *occ, struct et_occ *t) |
103 | { |
104 | #ifdef DEBUG_ET |
105 | gcc_assert (occ != t); |
106 | #endif |
107 | |
108 | occ->next = t; |
109 | if (t) |
110 | t->parent = occ; |
111 | } |
112 | |
113 | /* Recompute minimum for occurrence OCC. */ |
114 | |
115 | static inline void |
116 | et_recomp_min (struct et_occ *occ) |
117 | { |
118 | struct et_occ *mson = occ->prev; |
119 | |
120 | if (!mson |
121 | || (occ->next |
122 | && mson->min > occ->next->min)) |
123 | mson = occ->next; |
124 | |
125 | if (mson && mson->min < 0) |
126 | { |
127 | occ->min = mson->min + occ->depth; |
128 | occ->min_occ = mson->min_occ; |
129 | } |
130 | else |
131 | { |
132 | occ->min = occ->depth; |
133 | occ->min_occ = occ; |
134 | } |
135 | } |
136 | |
137 | #ifdef DEBUG_ET |
138 | /* Checks whether neighborhood of OCC seems sane. */ |
139 | |
140 | static void |
141 | et_check_occ_sanity (struct et_occ *occ) |
142 | { |
143 | if (!occ) |
144 | return; |
145 | |
146 | gcc_assert (occ->parent != occ); |
147 | gcc_assert (occ->prev != occ); |
148 | gcc_assert (occ->next != occ); |
149 | gcc_assert (!occ->next || occ->next != occ->prev); |
150 | |
151 | if (occ->next) |
152 | { |
153 | gcc_assert (occ->next != occ->parent); |
154 | gcc_assert (occ->next->parent == occ); |
155 | } |
156 | |
157 | if (occ->prev) |
158 | { |
159 | gcc_assert (occ->prev != occ->parent); |
160 | gcc_assert (occ->prev->parent == occ); |
161 | } |
162 | |
163 | gcc_assert (!occ->parent |
164 | || occ->parent->prev == occ |
165 | || occ->parent->next == occ); |
166 | } |
167 | |
168 | /* Checks whether tree rooted at OCC is sane. */ |
169 | |
170 | static void |
171 | et_check_sanity (struct et_occ *occ) |
172 | { |
173 | et_check_occ_sanity (occ); |
174 | if (occ->prev) |
175 | et_check_sanity (occ->prev); |
176 | if (occ->next) |
177 | et_check_sanity (occ->next); |
178 | } |
179 | |
180 | /* Checks whether tree containing OCC is sane. */ |
181 | |
182 | static void |
183 | et_check_tree_sanity (struct et_occ *occ) |
184 | { |
185 | while (occ->parent) |
186 | occ = occ->parent; |
187 | |
188 | et_check_sanity (occ); |
189 | } |
190 | |
191 | /* For recording the paths. */ |
192 | |
193 | /* An ad-hoc constant; if the function has more blocks, this won't work, |
194 | but since it is used for debugging only, it does not matter. */ |
195 | #define MAX_NODES 100000 |
196 | |
197 | static int len; |
198 | static void *datas[MAX_NODES]; |
199 | static int depths[MAX_NODES]; |
200 | |
201 | /* Records the path represented by OCC, with depth incremented by DEPTH. */ |
202 | |
203 | static int |
204 | record_path_before_1 (struct et_occ *occ, int depth) |
205 | { |
206 | int mn, m; |
207 | |
208 | depth += occ->depth; |
209 | mn = depth; |
210 | |
211 | if (occ->prev) |
212 | { |
213 | m = record_path_before_1 (occ->prev, depth); |
214 | if (m < mn) |
215 | mn = m; |
216 | } |
217 | |
218 | fprintf (stderr, "%d (%d); " , ((basic_block) occ->of->data)->index, depth); |
219 | |
220 | gcc_assert (len < MAX_NODES); |
221 | |
222 | depths[len] = depth; |
223 | datas[len] = occ->of; |
224 | len++; |
225 | |
226 | if (occ->next) |
227 | { |
228 | m = record_path_before_1 (occ->next, depth); |
229 | if (m < mn) |
230 | mn = m; |
231 | } |
232 | |
233 | gcc_assert (mn == occ->min + depth - occ->depth); |
234 | |
235 | return mn; |
236 | } |
237 | |
238 | /* Records the path represented by a tree containing OCC. */ |
239 | |
240 | static void |
241 | record_path_before (struct et_occ *occ) |
242 | { |
243 | while (occ->parent) |
244 | occ = occ->parent; |
245 | |
246 | len = 0; |
247 | record_path_before_1 (occ, 0); |
248 | fprintf (stderr, "\n" ); |
249 | } |
250 | |
251 | /* Checks whether the path represented by OCC, with depth incremented by DEPTH, |
252 | was not changed since the last recording. */ |
253 | |
254 | static int |
255 | check_path_after_1 (struct et_occ *occ, int depth) |
256 | { |
257 | int mn, m; |
258 | |
259 | depth += occ->depth; |
260 | mn = depth; |
261 | |
262 | if (occ->next) |
263 | { |
264 | m = check_path_after_1 (occ->next, depth); |
265 | if (m < mn) |
266 | mn = m; |
267 | } |
268 | |
269 | len--; |
270 | gcc_assert (depths[len] == depth && datas[len] == occ->of); |
271 | |
272 | if (occ->prev) |
273 | { |
274 | m = check_path_after_1 (occ->prev, depth); |
275 | if (m < mn) |
276 | mn = m; |
277 | } |
278 | |
279 | gcc_assert (mn == occ->min + depth - occ->depth); |
280 | |
281 | return mn; |
282 | } |
283 | |
284 | /* Checks whether the path represented by a tree containing OCC was |
285 | not changed since the last recording. */ |
286 | |
287 | static void |
288 | check_path_after (struct et_occ *occ) |
289 | { |
290 | while (occ->parent) |
291 | occ = occ->parent; |
292 | |
293 | check_path_after_1 (occ, 0); |
294 | gcc_assert (!len); |
295 | } |
296 | |
297 | #endif |
298 | |
299 | /* Splay the occurrence OCC to the root of the tree. */ |
300 | |
301 | static void |
302 | et_splay (struct et_occ *occ) |
303 | { |
304 | struct et_occ *f, *gf, *ggf; |
305 | int occ_depth, f_depth, gf_depth; |
306 | |
307 | #ifdef DEBUG_ET |
308 | record_path_before (occ); |
309 | et_check_tree_sanity (occ); |
310 | #endif |
311 | |
312 | while (occ->parent) |
313 | { |
314 | occ_depth = occ->depth; |
315 | |
316 | f = occ->parent; |
317 | f_depth = f->depth; |
318 | |
319 | gf = f->parent; |
320 | |
321 | if (!gf) |
322 | { |
323 | set_depth_add (occ, d: f_depth); |
324 | occ->min_occ = f->min_occ; |
325 | occ->min = f->min; |
326 | |
327 | if (f->prev == occ) |
328 | { |
329 | /* zig */ |
330 | set_prev (occ: f, t: occ->next); |
331 | set_next (occ, t: f); |
332 | set_depth_add (occ: f->prev, d: occ_depth); |
333 | } |
334 | else |
335 | { |
336 | /* zag */ |
337 | set_next (occ: f, t: occ->prev); |
338 | set_prev (occ, t: f); |
339 | set_depth_add (occ: f->next, d: occ_depth); |
340 | } |
341 | set_depth (occ: f, d: -occ_depth); |
342 | occ->parent = NULL; |
343 | |
344 | et_recomp_min (occ: f); |
345 | #ifdef DEBUG_ET |
346 | et_check_tree_sanity (occ); |
347 | check_path_after (occ); |
348 | #endif |
349 | return; |
350 | } |
351 | |
352 | gf_depth = gf->depth; |
353 | |
354 | set_depth_add (occ, d: f_depth + gf_depth); |
355 | occ->min_occ = gf->min_occ; |
356 | occ->min = gf->min; |
357 | |
358 | ggf = gf->parent; |
359 | |
360 | if (gf->prev == f) |
361 | { |
362 | if (f->prev == occ) |
363 | { |
364 | /* zig zig */ |
365 | set_prev (occ: gf, t: f->next); |
366 | set_prev (occ: f, t: occ->next); |
367 | set_next (occ, t: f); |
368 | set_next (occ: f, t: gf); |
369 | |
370 | set_depth (occ: f, d: -occ_depth); |
371 | set_depth_add (occ: f->prev, d: occ_depth); |
372 | set_depth (occ: gf, d: -f_depth); |
373 | set_depth_add (occ: gf->prev, d: f_depth); |
374 | } |
375 | else |
376 | { |
377 | /* zag zig */ |
378 | set_prev (occ: gf, t: occ->next); |
379 | set_next (occ: f, t: occ->prev); |
380 | set_prev (occ, t: f); |
381 | set_next (occ, t: gf); |
382 | |
383 | set_depth (occ: f, d: -occ_depth); |
384 | set_depth_add (occ: f->next, d: occ_depth); |
385 | set_depth (occ: gf, d: -occ_depth - f_depth); |
386 | set_depth_add (occ: gf->prev, d: occ_depth + f_depth); |
387 | } |
388 | } |
389 | else |
390 | { |
391 | if (f->prev == occ) |
392 | { |
393 | /* zig zag */ |
394 | set_next (occ: gf, t: occ->prev); |
395 | set_prev (occ: f, t: occ->next); |
396 | set_prev (occ, t: gf); |
397 | set_next (occ, t: f); |
398 | |
399 | set_depth (occ: f, d: -occ_depth); |
400 | set_depth_add (occ: f->prev, d: occ_depth); |
401 | set_depth (occ: gf, d: -occ_depth - f_depth); |
402 | set_depth_add (occ: gf->next, d: occ_depth + f_depth); |
403 | } |
404 | else |
405 | { |
406 | /* zag zag */ |
407 | set_next (occ: gf, t: f->prev); |
408 | set_next (occ: f, t: occ->prev); |
409 | set_prev (occ, t: f); |
410 | set_prev (occ: f, t: gf); |
411 | |
412 | set_depth (occ: f, d: -occ_depth); |
413 | set_depth_add (occ: f->next, d: occ_depth); |
414 | set_depth (occ: gf, d: -f_depth); |
415 | set_depth_add (occ: gf->next, d: f_depth); |
416 | } |
417 | } |
418 | |
419 | occ->parent = ggf; |
420 | if (ggf) |
421 | { |
422 | if (ggf->prev == gf) |
423 | ggf->prev = occ; |
424 | else |
425 | ggf->next = occ; |
426 | } |
427 | |
428 | et_recomp_min (occ: gf); |
429 | et_recomp_min (occ: f); |
430 | #ifdef DEBUG_ET |
431 | et_check_tree_sanity (occ); |
432 | #endif |
433 | } |
434 | |
435 | #ifdef DEBUG_ET |
436 | et_check_sanity (occ); |
437 | check_path_after (occ); |
438 | #endif |
439 | } |
440 | |
441 | /* Create a new et tree occurrence of NODE. */ |
442 | |
443 | static struct et_occ * |
444 | et_new_occ (struct et_node *node) |
445 | { |
446 | et_occ *nw = et_occurrences.allocate (); |
447 | |
448 | nw->of = node; |
449 | nw->parent = NULL; |
450 | nw->prev = NULL; |
451 | nw->next = NULL; |
452 | |
453 | nw->depth = 0; |
454 | nw->min_occ = nw; |
455 | nw->min = 0; |
456 | |
457 | return nw; |
458 | } |
459 | |
460 | /* Create a new et tree containing DATA. */ |
461 | |
462 | struct et_node * |
463 | et_new_tree (void *data) |
464 | { |
465 | et_node *nw = et_nodes.allocate (); |
466 | |
467 | nw->data = data; |
468 | nw->father = NULL; |
469 | nw->left = NULL; |
470 | nw->right = NULL; |
471 | nw->son = NULL; |
472 | |
473 | nw->rightmost_occ = et_new_occ (node: nw); |
474 | nw->parent_occ = NULL; |
475 | |
476 | return nw; |
477 | } |
478 | |
479 | /* Releases et tree T. */ |
480 | |
481 | void |
482 | et_free_tree (struct et_node *t) |
483 | { |
484 | while (t->son) |
485 | et_split (t->son); |
486 | |
487 | if (t->father) |
488 | et_split (t); |
489 | |
490 | et_occurrences.remove (object: t->rightmost_occ); |
491 | et_nodes.remove (object: t); |
492 | } |
493 | |
494 | /* Releases et tree T without maintaining other nodes. */ |
495 | |
496 | void |
497 | et_free_tree_force (struct et_node *t) |
498 | { |
499 | et_occurrences.remove (object: t->rightmost_occ); |
500 | if (t->parent_occ) |
501 | et_occurrences.remove (object: t->parent_occ); |
502 | et_nodes.remove (object: t); |
503 | } |
504 | |
505 | /* Release the alloc pools, if they are empty. */ |
506 | |
507 | void |
508 | et_free_pools (void) |
509 | { |
510 | et_occurrences.release_if_empty (); |
511 | et_nodes.release_if_empty (); |
512 | } |
513 | |
514 | /* Sets father of et tree T to FATHER. */ |
515 | |
516 | void |
517 | et_set_father (struct et_node *t, struct et_node *father) |
518 | { |
519 | struct et_node *left, *right; |
520 | struct et_occ *rmost, *left_part, *new_f_occ, *p; |
521 | |
522 | /* Update the path represented in the splay tree. */ |
523 | new_f_occ = et_new_occ (node: father); |
524 | |
525 | rmost = father->rightmost_occ; |
526 | et_splay (occ: rmost); |
527 | |
528 | left_part = rmost->prev; |
529 | |
530 | p = t->rightmost_occ; |
531 | et_splay (occ: p); |
532 | |
533 | set_prev (occ: new_f_occ, t: left_part); |
534 | set_next (occ: new_f_occ, t: p); |
535 | |
536 | p->depth++; |
537 | p->min++; |
538 | et_recomp_min (occ: new_f_occ); |
539 | |
540 | set_prev (occ: rmost, t: new_f_occ); |
541 | |
542 | if (new_f_occ->min + rmost->depth < rmost->min) |
543 | { |
544 | rmost->min = new_f_occ->min + rmost->depth; |
545 | rmost->min_occ = new_f_occ->min_occ; |
546 | } |
547 | |
548 | t->parent_occ = new_f_occ; |
549 | |
550 | /* Update the tree. */ |
551 | t->father = father; |
552 | right = father->son; |
553 | if (right) |
554 | left = right->left; |
555 | else |
556 | left = right = t; |
557 | |
558 | left->right = t; |
559 | right->left = t; |
560 | t->left = left; |
561 | t->right = right; |
562 | |
563 | father->son = t; |
564 | |
565 | #ifdef DEBUG_ET |
566 | et_check_tree_sanity (rmost); |
567 | record_path_before (rmost); |
568 | #endif |
569 | } |
570 | |
571 | /* Splits the edge from T to its father. */ |
572 | |
573 | void |
574 | et_split (struct et_node *t) |
575 | { |
576 | struct et_node *father = t->father; |
577 | struct et_occ *r, *l, *rmost, *p_occ; |
578 | |
579 | /* Update the path represented by the splay tree. */ |
580 | rmost = t->rightmost_occ; |
581 | et_splay (occ: rmost); |
582 | |
583 | for (r = rmost->next; r->prev; r = r->prev) |
584 | continue; |
585 | et_splay (occ: r); |
586 | |
587 | r->prev->parent = NULL; |
588 | p_occ = t->parent_occ; |
589 | et_splay (occ: p_occ); |
590 | t->parent_occ = NULL; |
591 | |
592 | l = p_occ->prev; |
593 | p_occ->next->parent = NULL; |
594 | |
595 | set_prev (occ: r, t: l); |
596 | |
597 | et_recomp_min (occ: r); |
598 | |
599 | et_splay (occ: rmost); |
600 | rmost->depth = 0; |
601 | rmost->min = 0; |
602 | |
603 | et_occurrences.remove (object: p_occ); |
604 | |
605 | /* Update the tree. */ |
606 | if (father->son == t) |
607 | father->son = t->right; |
608 | if (father->son == t) |
609 | father->son = NULL; |
610 | else |
611 | { |
612 | t->left->right = t->right; |
613 | t->right->left = t->left; |
614 | } |
615 | t->left = t->right = NULL; |
616 | t->father = NULL; |
617 | |
618 | #ifdef DEBUG_ET |
619 | et_check_tree_sanity (rmost); |
620 | record_path_before (rmost); |
621 | |
622 | et_check_tree_sanity (r); |
623 | record_path_before (r); |
624 | #endif |
625 | } |
626 | |
627 | /* Finds the nearest common ancestor of the nodes N1 and N2. */ |
628 | |
629 | struct et_node * |
630 | et_nca (struct et_node *n1, struct et_node *n2) |
631 | { |
632 | struct et_occ *o1 = n1->rightmost_occ, *o2 = n2->rightmost_occ, *om; |
633 | struct et_occ *l, *r, *ret; |
634 | int mn; |
635 | |
636 | if (n1 == n2) |
637 | return n1; |
638 | |
639 | et_splay (occ: o1); |
640 | l = o1->prev; |
641 | r = o1->next; |
642 | if (l) |
643 | l->parent = NULL; |
644 | if (r) |
645 | r->parent = NULL; |
646 | et_splay (occ: o2); |
647 | |
648 | if (l == o2 || (l && l->parent != NULL)) |
649 | { |
650 | ret = o2->next; |
651 | |
652 | set_prev (occ: o1, t: o2); |
653 | if (r) |
654 | r->parent = o1; |
655 | } |
656 | else if (r == o2 || (r && r->parent != NULL)) |
657 | { |
658 | ret = o2->prev; |
659 | |
660 | set_next (occ: o1, t: o2); |
661 | if (l) |
662 | l->parent = o1; |
663 | } |
664 | else |
665 | { |
666 | /* O1 and O2 are in different components of the forest. */ |
667 | if (l) |
668 | l->parent = o1; |
669 | if (r) |
670 | r->parent = o1; |
671 | return NULL; |
672 | } |
673 | |
674 | if (o2->depth > 0) |
675 | { |
676 | om = o1; |
677 | mn = o1->depth; |
678 | } |
679 | else |
680 | { |
681 | om = o2; |
682 | mn = o2->depth + o1->depth; |
683 | } |
684 | |
685 | #ifdef DEBUG_ET |
686 | et_check_tree_sanity (o2); |
687 | #endif |
688 | |
689 | if (ret && ret->min + o1->depth + o2->depth < mn) |
690 | return ret->min_occ->of; |
691 | else |
692 | return om->of; |
693 | } |
694 | |
695 | /* Checks whether the node UP is an ancestor of the node DOWN. */ |
696 | |
697 | bool |
698 | et_below (struct et_node *down, struct et_node *up) |
699 | { |
700 | struct et_occ *u = up->rightmost_occ, *d = down->rightmost_occ; |
701 | struct et_occ *l, *r; |
702 | |
703 | if (up == down) |
704 | return true; |
705 | |
706 | et_splay (occ: u); |
707 | l = u->prev; |
708 | r = u->next; |
709 | |
710 | if (!l) |
711 | return false; |
712 | |
713 | l->parent = NULL; |
714 | |
715 | if (r) |
716 | r->parent = NULL; |
717 | |
718 | et_splay (occ: d); |
719 | |
720 | if (l == d || l->parent != NULL) |
721 | { |
722 | if (r) |
723 | r->parent = u; |
724 | set_prev (occ: u, t: d); |
725 | #ifdef DEBUG_ET |
726 | et_check_tree_sanity (u); |
727 | #endif |
728 | } |
729 | else |
730 | { |
731 | l->parent = u; |
732 | |
733 | /* In case O1 and O2 are in two different trees, we must just restore the |
734 | original state. */ |
735 | if (r && r->parent != NULL) |
736 | set_next (occ: u, t: d); |
737 | else |
738 | set_next (occ: u, t: r); |
739 | |
740 | #ifdef DEBUG_ET |
741 | et_check_tree_sanity (u); |
742 | #endif |
743 | return false; |
744 | } |
745 | |
746 | if (d->depth <= 0) |
747 | return false; |
748 | |
749 | return !d->next || d->next->min + d->depth >= 0; |
750 | } |
751 | |
752 | /* Returns the root of the tree that contains NODE. */ |
753 | |
754 | struct et_node * |
755 | et_root (struct et_node *node) |
756 | { |
757 | struct et_occ *occ = node->rightmost_occ, *r; |
758 | |
759 | /* The root of the tree corresponds to the rightmost occurrence in the |
760 | represented path. */ |
761 | et_splay (occ); |
762 | for (r = occ; r->next; r = r->next) |
763 | continue; |
764 | et_splay (occ: r); |
765 | |
766 | return r->of; |
767 | } |
768 | |
769 | #if CHECKING_P |
770 | |
771 | namespace selftest { |
772 | |
773 | /* Selftests for et-forest.cc. */ |
774 | |
775 | /* Perform sanity checks for a tree consisting of a single node. */ |
776 | |
777 | static void |
778 | test_single_node () |
779 | { |
780 | void *test_data = (void *)0xcafebabe; |
781 | |
782 | et_node *n = et_new_tree (data: test_data); |
783 | ASSERT_EQ (n->data, test_data); |
784 | ASSERT_EQ (n, et_root (n)); |
785 | et_free_tree (t: n); |
786 | } |
787 | |
788 | /* Test of this tree: |
789 | a |
790 | / \ |
791 | / \ |
792 | b c |
793 | / \ | |
794 | d e f. */ |
795 | |
796 | static void |
797 | test_simple_tree () |
798 | { |
799 | et_node *a = et_new_tree (NULL); |
800 | et_node *b = et_new_tree (NULL); |
801 | et_node *c = et_new_tree (NULL); |
802 | et_node *d = et_new_tree (NULL); |
803 | et_node *e = et_new_tree (NULL); |
804 | et_node *f = et_new_tree (NULL); |
805 | |
806 | et_set_father (t: b, father: a); |
807 | et_set_father (t: c, father: a); |
808 | et_set_father (t: d, father: b); |
809 | et_set_father (t: e, father: b); |
810 | et_set_father (t: f, father: c); |
811 | |
812 | ASSERT_TRUE (et_below (a, a)); |
813 | ASSERT_TRUE (et_below (b, a)); |
814 | ASSERT_TRUE (et_below (c, a)); |
815 | ASSERT_TRUE (et_below (d, a)); |
816 | ASSERT_TRUE (et_below (e, a)); |
817 | ASSERT_TRUE (et_below (f, a)); |
818 | |
819 | ASSERT_FALSE (et_below (a, b)); |
820 | ASSERT_TRUE (et_below (b, b)); |
821 | ASSERT_FALSE (et_below (c, b)); |
822 | ASSERT_TRUE (et_below (d, b)); |
823 | ASSERT_TRUE (et_below (e, b)); |
824 | ASSERT_FALSE (et_below (f, b)); |
825 | |
826 | ASSERT_FALSE (et_below (a, c)); |
827 | ASSERT_FALSE (et_below (b, c)); |
828 | ASSERT_TRUE (et_below (c, c)); |
829 | ASSERT_FALSE (et_below (d, c)); |
830 | ASSERT_FALSE (et_below (e, c)); |
831 | ASSERT_TRUE (et_below (f, c)); |
832 | |
833 | ASSERT_FALSE (et_below (a, d)); |
834 | ASSERT_FALSE (et_below (b, d)); |
835 | ASSERT_FALSE (et_below (c, d)); |
836 | ASSERT_TRUE (et_below (d, d)); |
837 | ASSERT_FALSE (et_below (e, d)); |
838 | ASSERT_FALSE (et_below (f, d)); |
839 | |
840 | ASSERT_FALSE (et_below (a, e)); |
841 | ASSERT_FALSE (et_below (b, e)); |
842 | ASSERT_FALSE (et_below (c, e)); |
843 | ASSERT_FALSE (et_below (d, e)); |
844 | ASSERT_TRUE (et_below (e, e)); |
845 | ASSERT_FALSE (et_below (f, e)); |
846 | |
847 | ASSERT_FALSE (et_below (a, f)); |
848 | ASSERT_FALSE (et_below (b, f)); |
849 | ASSERT_FALSE (et_below (c, f)); |
850 | ASSERT_FALSE (et_below (d, f)); |
851 | ASSERT_FALSE (et_below (e, f)); |
852 | ASSERT_TRUE (et_below (f, f)); |
853 | |
854 | et_free_tree_force (t: a); |
855 | } |
856 | |
857 | /* Verify that two disconnected nodes are unrelated. */ |
858 | |
859 | static void |
860 | test_disconnected_nodes () |
861 | { |
862 | et_node *a = et_new_tree (NULL); |
863 | et_node *b = et_new_tree (NULL); |
864 | |
865 | ASSERT_FALSE (et_below (a, b)); |
866 | ASSERT_FALSE (et_below (b, a)); |
867 | |
868 | et_free_tree (t: a); |
869 | et_free_tree (t: b); |
870 | } |
871 | |
872 | /* Run all of the selftests within this file. */ |
873 | |
874 | void |
875 | et_forest_cc_tests () |
876 | { |
877 | test_single_node (); |
878 | test_simple_tree (); |
879 | test_disconnected_nodes (); |
880 | } |
881 | |
882 | } // namespace selftest |
883 | |
884 | #endif /* CHECKING_P */ |
885 | |