Line data Source code
1 : /* ET-trees data structure implementation.
2 : Contributed by Pavel Nejedly
3 : Copyright (C) 2002-2026 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 7300298816 : set_depth (struct et_occ *occ, int d)
65 : {
66 7300298816 : if (!occ)
67 : return;
68 :
69 7300298816 : occ->min += d - occ->depth;
70 7300298816 : occ->depth = d;
71 : }
72 :
73 : /* Adds D to the depth of OCC. */
74 :
75 : static inline void
76 11360899091 : set_depth_add (struct et_occ *occ, int d)
77 : {
78 11360899091 : if (!occ)
79 : return;
80 :
81 7787361715 : occ->min += d;
82 3235832548 : occ->depth += d;
83 : }
84 :
85 : /* Sets prev field of OCC to P. */
86 :
87 : static inline void
88 11834764385 : set_prev (struct et_occ *occ, struct et_occ *t)
89 : {
90 : #ifdef DEBUG_ET
91 : gcc_assert (occ != t);
92 : #endif
93 :
94 11834764385 : occ->prev = t;
95 11834764385 : if (t)
96 3119072177 : t->parent = occ;
97 : }
98 :
99 : /* Sets next field of OCC to P. */
100 :
101 : static inline void
102 9647520974 : set_next (struct et_occ *occ, struct et_occ *t)
103 : {
104 : #ifdef DEBUG_ET
105 : gcc_assert (occ != t);
106 : #endif
107 :
108 9647520974 : occ->next = t;
109 9647520974 : if (t)
110 2773586145 : t->parent = occ;
111 : }
112 :
113 : /* Recompute minimum for occurrence OCC. */
114 :
115 : static inline void
116 9391018647 : et_recomp_min (struct et_occ *occ)
117 : {
118 9391018647 : struct et_occ *mson = occ->prev;
119 :
120 9391018647 : if (!mson
121 6878683059 : || (occ->next
122 5113653217 : && mson->min > occ->next->min))
123 3847816092 : mson = occ->next;
124 :
125 9391018647 : if (mson && mson->min < 0)
126 : {
127 7578847702 : occ->min = mson->min + occ->depth;
128 7578847702 : occ->min_occ = mson->min_occ;
129 : }
130 : else
131 : {
132 1812170945 : occ->min = occ->depth;
133 1812170945 : occ->min_occ = occ;
134 : }
135 9391018647 : }
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 5898949081 : et_splay (struct et_occ *occ)
303 : {
304 5898949081 : struct et_occ *f, *gf, *ggf;
305 5898949081 : 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 9138647622 : while (occ->parent)
313 : {
314 4060600275 : occ_depth = occ->depth;
315 :
316 4060600275 : f = occ->parent;
317 4060600275 : f_depth = f->depth;
318 :
319 4060600275 : gf = f->parent;
320 :
321 4060600275 : if (!gf)
322 : {
323 820901734 : set_depth_add (occ, f_depth);
324 820901734 : occ->min_occ = f->min_occ;
325 820901734 : occ->min = f->min;
326 :
327 820901734 : if (f->prev == occ)
328 : {
329 : /* zig */
330 344793343 : set_prev (f, occ->next);
331 344793343 : set_next (occ, f);
332 344793343 : set_depth_add (f->prev, occ_depth);
333 : }
334 : else
335 : {
336 : /* zag */
337 476108391 : set_next (f, occ->prev);
338 476108391 : set_prev (occ, f);
339 476108391 : set_depth_add (f->next, occ_depth);
340 : }
341 820901734 : set_depth (f, -occ_depth);
342 820901734 : occ->parent = NULL;
343 :
344 820901734 : et_recomp_min (f);
345 : #ifdef DEBUG_ET
346 : et_check_tree_sanity (occ);
347 : check_path_after (occ);
348 : #endif
349 820901734 : return;
350 : }
351 :
352 3239698541 : gf_depth = gf->depth;
353 :
354 3239698541 : set_depth_add (occ, f_depth + gf_depth);
355 3239698541 : occ->min_occ = gf->min_occ;
356 3239698541 : occ->min = gf->min;
357 :
358 3239698541 : ggf = gf->parent;
359 :
360 3239698541 : if (gf->prev == f)
361 : {
362 2092545412 : if (f->prev == occ)
363 : {
364 : /* zig zig */
365 835864323 : set_prev (gf, f->next);
366 835864323 : set_prev (f, occ->next);
367 835864323 : set_next (occ, f);
368 835864323 : set_next (f, gf);
369 :
370 835864323 : set_depth (f, -occ_depth);
371 835864323 : set_depth_add (f->prev, occ_depth);
372 835864323 : set_depth (gf, -f_depth);
373 835864323 : set_depth_add (gf->prev, f_depth);
374 : }
375 : else
376 : {
377 : /* zag zig */
378 1256681089 : set_prev (gf, occ->next);
379 1256681089 : set_next (f, occ->prev);
380 1256681089 : set_prev (occ, f);
381 1256681089 : set_next (occ, gf);
382 :
383 1256681089 : set_depth (f, -occ_depth);
384 1256681089 : set_depth_add (f->next, occ_depth);
385 1256681089 : set_depth (gf, -occ_depth - f_depth);
386 1256681089 : set_depth_add (gf->prev, occ_depth + f_depth);
387 : }
388 : }
389 : else
390 : {
391 1147153129 : if (f->prev == occ)
392 : {
393 : /* zig zag */
394 346966124 : set_next (gf, occ->prev);
395 346966124 : set_prev (f, occ->next);
396 346966124 : set_prev (occ, gf);
397 346966124 : set_next (occ, f);
398 :
399 346966124 : set_depth (f, -occ_depth);
400 346966124 : set_depth_add (f->prev, occ_depth);
401 346966124 : set_depth (gf, -occ_depth - f_depth);
402 346966124 : set_depth_add (gf->next, occ_depth + f_depth);
403 : }
404 : else
405 : {
406 : /* zag zag */
407 800187005 : set_next (gf, f->prev);
408 800187005 : set_next (f, occ->prev);
409 800187005 : set_prev (occ, f);
410 800187005 : set_prev (f, gf);
411 :
412 800187005 : set_depth (f, -occ_depth);
413 800187005 : set_depth_add (f->next, occ_depth);
414 800187005 : set_depth (gf, -f_depth);
415 800187005 : set_depth_add (gf->next, f_depth);
416 : }
417 : }
418 :
419 3239698541 : occ->parent = ggf;
420 3239698541 : if (ggf)
421 : {
422 1784153324 : if (ggf->prev == gf)
423 968714499 : ggf->prev = occ;
424 : else
425 815438825 : ggf->next = occ;
426 : }
427 :
428 3239698541 : et_recomp_min (gf);
429 3239698541 : et_recomp_min (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 4483735101 : et_new_occ (struct et_node *node)
445 : {
446 4483735101 : et_occ *nw = et_occurrences.allocate ();
447 :
448 4483735101 : nw->of = node;
449 4483735101 : nw->parent = NULL;
450 4483735101 : nw->prev = NULL;
451 4483735101 : nw->next = NULL;
452 :
453 4483735101 : nw->depth = 0;
454 4483735101 : nw->min_occ = nw;
455 4483735101 : nw->min = 0;
456 :
457 4483735101 : return nw;
458 : }
459 :
460 : /* Create a new et tree containing DATA. */
461 :
462 : struct et_node *
463 2473543955 : et_new_tree (void *data)
464 : {
465 2473543955 : et_node *nw = et_nodes.allocate ();
466 :
467 2473543955 : nw->data = data;
468 2473543955 : nw->father = NULL;
469 2473543955 : nw->left = NULL;
470 2473543955 : nw->right = NULL;
471 2473543955 : nw->son = NULL;
472 :
473 2473543955 : nw->rightmost_occ = et_new_occ (nw);
474 2473543955 : nw->parent_occ = NULL;
475 :
476 2473543955 : return nw;
477 : }
478 :
479 : /* Releases et tree T. */
480 :
481 : void
482 48020316 : et_free_tree (struct et_node *t)
483 : {
484 48996519 : while (t->son)
485 976203 : et_split (t->son);
486 :
487 48020316 : if (t->father)
488 47394831 : et_split (t);
489 :
490 48020316 : et_occurrences.remove (t->rightmost_occ);
491 48020316 : et_nodes.remove (t);
492 48020316 : }
493 :
494 : /* Releases et tree T without maintaining other nodes. */
495 :
496 : void
497 2425165098 : et_free_tree_force (struct et_node *t)
498 : {
499 2425165098 : et_occurrences.remove (t->rightmost_occ);
500 2425165098 : if (t->parent_occ)
501 1929414672 : et_occurrences.remove (t->parent_occ);
502 2425165098 : et_nodes.remove (t);
503 2425165098 : }
504 :
505 : /* Release the alloc pools, if they are empty. */
506 :
507 : void
508 246484958 : et_free_pools (void)
509 : {
510 246484958 : et_occurrences.release_if_empty ();
511 246484958 : et_nodes.release_if_empty ();
512 246484958 : }
513 :
514 : /* Sets father of et tree T to FATHER. */
515 :
516 : void
517 2010191146 : et_set_father (struct et_node *t, struct et_node *father)
518 : {
519 2010191146 : struct et_node *left, *right;
520 2010191146 : struct et_occ *rmost, *left_part, *new_f_occ, *p;
521 :
522 : /* Update the path represented in the splay tree. */
523 2010191146 : new_f_occ = et_new_occ (father);
524 :
525 2010191146 : rmost = father->rightmost_occ;
526 2010191146 : et_splay (rmost);
527 :
528 2010191146 : left_part = rmost->prev;
529 :
530 2010191146 : p = t->rightmost_occ;
531 2010191146 : et_splay (p);
532 :
533 2010191146 : set_prev (new_f_occ, left_part);
534 2010191146 : set_next (new_f_occ, p);
535 :
536 2010191146 : p->depth++;
537 2010191146 : p->min++;
538 2010191146 : et_recomp_min (new_f_occ);
539 :
540 2010191146 : set_prev (rmost, new_f_occ);
541 :
542 2010191146 : if (new_f_occ->min + rmost->depth < rmost->min)
543 : {
544 0 : rmost->min = new_f_occ->min + rmost->depth;
545 0 : rmost->min_occ = new_f_occ->min_occ;
546 : }
547 :
548 2010191146 : t->parent_occ = new_f_occ;
549 :
550 : /* Update the tree. */
551 2010191146 : t->father = father;
552 2010191146 : right = father->son;
553 2010191146 : if (right)
554 823017176 : left = right->left;
555 : else
556 : left = right = t;
557 :
558 2010191146 : left->right = t;
559 2010191146 : right->left = t;
560 2010191146 : t->left = left;
561 2010191146 : t->right = right;
562 :
563 2010191146 : father->son = t;
564 :
565 : #ifdef DEBUG_ET
566 : et_check_tree_sanity (rmost);
567 : record_path_before (rmost);
568 : #endif
569 2010191146 : }
570 :
571 : /* Splits the edge from T to its father. */
572 :
573 : void
574 80528685 : et_split (struct et_node *t)
575 : {
576 80528685 : struct et_node *father = t->father;
577 80528685 : struct et_occ *r, *l, *rmost, *p_occ;
578 :
579 : /* Update the path represented by the splay tree. */
580 80528685 : rmost = t->rightmost_occ;
581 80528685 : et_splay (rmost);
582 :
583 165952953 : for (r = rmost->next; r->prev; r = r->prev)
584 85424268 : continue;
585 80528685 : et_splay (r);
586 :
587 80528685 : r->prev->parent = NULL;
588 80528685 : p_occ = t->parent_occ;
589 80528685 : et_splay (p_occ);
590 80528685 : t->parent_occ = NULL;
591 :
592 80528685 : l = p_occ->prev;
593 80528685 : p_occ->next->parent = NULL;
594 :
595 80528685 : set_prev (r, l);
596 :
597 80528685 : et_recomp_min (r);
598 :
599 80528685 : et_splay (rmost);
600 80528685 : rmost->depth = 0;
601 80528685 : rmost->min = 0;
602 :
603 80528685 : et_occurrences.remove (p_occ);
604 :
605 : /* Update the tree. */
606 80528685 : if (father->son == t)
607 46541229 : father->son = t->right;
608 80528685 : if (father->son == t)
609 30741754 : father->son = NULL;
610 : else
611 : {
612 49786931 : t->left->right = t->right;
613 49786931 : t->right->left = t->left;
614 : }
615 80528685 : t->left = t->right = NULL;
616 80528685 : 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 85424268 : }
626 :
627 : /* Finds the nearest common ancestor of the nodes N1 and N2. */
628 :
629 : struct et_node *
630 111618437 : et_nca (struct et_node *n1, struct et_node *n2)
631 : {
632 111618437 : struct et_occ *o1 = n1->rightmost_occ, *o2 = n2->rightmost_occ, *om;
633 111618437 : struct et_occ *l, *r, *ret;
634 111618437 : int mn;
635 :
636 111618437 : if (n1 == n2)
637 : return n1;
638 :
639 93657038 : et_splay (o1);
640 93657038 : l = o1->prev;
641 93657038 : r = o1->next;
642 93657038 : if (l)
643 93657038 : l->parent = NULL;
644 93657038 : if (r)
645 93647445 : r->parent = NULL;
646 93657038 : et_splay (o2);
647 :
648 93657038 : if (l == o2 || (l && l->parent != NULL))
649 : {
650 84690335 : ret = o2->next;
651 :
652 84690335 : set_prev (o1, o2);
653 84690335 : if (r)
654 84680742 : r->parent = o1;
655 : }
656 8966703 : else if (r == o2 || (r && r->parent != NULL))
657 : {
658 8966703 : ret = o2->prev;
659 :
660 8966703 : set_next (o1, o2);
661 8966703 : if (l)
662 8966703 : l->parent = o1;
663 : }
664 : else
665 : {
666 : /* O1 and O2 are in different components of the forest. */
667 0 : if (l)
668 0 : l->parent = o1;
669 0 : if (r)
670 0 : r->parent = o1;
671 0 : return NULL;
672 : }
673 :
674 93657038 : if (o2->depth > 0)
675 : {
676 84095336 : om = o1;
677 84095336 : mn = o1->depth;
678 : }
679 : else
680 : {
681 9561702 : om = o2;
682 9561702 : mn = o2->depth + o1->depth;
683 : }
684 :
685 : #ifdef DEBUG_ET
686 : et_check_tree_sanity (o2);
687 : #endif
688 :
689 93657038 : if (ret && ret->min + o1->depth + o2->depth < mn)
690 7002365 : return ret->min_occ->of;
691 : else
692 86654673 : return om->of;
693 : }
694 :
695 : /* Checks whether the node UP is an ancestor of the node DOWN. */
696 :
697 : bool
698 697122867 : et_below (struct et_node *down, struct et_node *up)
699 : {
700 697122867 : struct et_occ *u = up->rightmost_occ, *d = down->rightmost_occ;
701 697122867 : struct et_occ *l, *r;
702 :
703 697122867 : if (up == down)
704 : return true;
705 :
706 677063457 : et_splay (u);
707 677063457 : l = u->prev;
708 677063457 : r = u->next;
709 :
710 677063457 : if (!l)
711 : return false;
712 :
713 676928566 : l->parent = NULL;
714 :
715 676928566 : if (r)
716 676501685 : r->parent = NULL;
717 :
718 676928566 : et_splay (d);
719 :
720 676928566 : if (l == d || l->parent != NULL)
721 : {
722 348864257 : if (r)
723 348721757 : r->parent = u;
724 348864257 : set_prev (u, d);
725 : #ifdef DEBUG_ET
726 : et_check_tree_sanity (u);
727 : #endif
728 : }
729 : else
730 : {
731 328064309 : l->parent = u;
732 :
733 : /* In case O1 and O2 are in two different trees, we must just restore the
734 : original state. */
735 328064309 : if (r && r->parent != NULL)
736 131637060 : set_next (u, d);
737 : else
738 196427249 : set_next (u, r);
739 :
740 : #ifdef DEBUG_ET
741 : et_check_tree_sanity (u);
742 : #endif
743 328064309 : return false;
744 : }
745 :
746 348864257 : if (d->depth <= 0)
747 : return false;
748 :
749 308275391 : 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 7572975 : et_root (struct et_node *node)
756 : {
757 7572975 : 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 7572975 : et_splay (occ);
762 28598825 : for (r = occ; r->next; r = r->next)
763 13452875 : continue;
764 7572975 : et_splay (r);
765 :
766 7572975 : return r->of;
767 13452875 : }
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 4 : test_single_node ()
779 : {
780 4 : void *test_data = (void *)0xcafebabe;
781 :
782 4 : et_node *n = et_new_tree (test_data);
783 4 : ASSERT_EQ (n->data, test_data);
784 4 : ASSERT_EQ (n, et_root (n));
785 4 : et_free_tree (n);
786 4 : }
787 :
788 : /* Test of this tree:
789 : a
790 : / \
791 : / \
792 : b c
793 : / \ |
794 : d e f. */
795 :
796 : static void
797 4 : test_simple_tree ()
798 : {
799 4 : et_node *a = et_new_tree (NULL);
800 4 : et_node *b = et_new_tree (NULL);
801 4 : et_node *c = et_new_tree (NULL);
802 4 : et_node *d = et_new_tree (NULL);
803 4 : et_node *e = et_new_tree (NULL);
804 4 : et_node *f = et_new_tree (NULL);
805 :
806 4 : et_set_father (b, a);
807 4 : et_set_father (c, a);
808 4 : et_set_father (d, b);
809 4 : et_set_father (e, b);
810 4 : et_set_father (f, c);
811 :
812 4 : ASSERT_TRUE (et_below (a, a));
813 4 : ASSERT_TRUE (et_below (b, a));
814 4 : ASSERT_TRUE (et_below (c, a));
815 4 : ASSERT_TRUE (et_below (d, a));
816 4 : ASSERT_TRUE (et_below (e, a));
817 4 : ASSERT_TRUE (et_below (f, a));
818 :
819 4 : ASSERT_FALSE (et_below (a, b));
820 4 : ASSERT_TRUE (et_below (b, b));
821 4 : ASSERT_FALSE (et_below (c, b));
822 4 : ASSERT_TRUE (et_below (d, b));
823 4 : ASSERT_TRUE (et_below (e, b));
824 4 : ASSERT_FALSE (et_below (f, b));
825 :
826 4 : ASSERT_FALSE (et_below (a, c));
827 4 : ASSERT_FALSE (et_below (b, c));
828 4 : ASSERT_TRUE (et_below (c, c));
829 4 : ASSERT_FALSE (et_below (d, c));
830 4 : ASSERT_FALSE (et_below (e, c));
831 4 : ASSERT_TRUE (et_below (f, c));
832 :
833 4 : ASSERT_FALSE (et_below (a, d));
834 4 : ASSERT_FALSE (et_below (b, d));
835 4 : ASSERT_FALSE (et_below (c, d));
836 4 : ASSERT_TRUE (et_below (d, d));
837 4 : ASSERT_FALSE (et_below (e, d));
838 4 : ASSERT_FALSE (et_below (f, d));
839 :
840 4 : ASSERT_FALSE (et_below (a, e));
841 4 : ASSERT_FALSE (et_below (b, e));
842 4 : ASSERT_FALSE (et_below (c, e));
843 4 : ASSERT_FALSE (et_below (d, e));
844 4 : ASSERT_TRUE (et_below (e, e));
845 4 : ASSERT_FALSE (et_below (f, e));
846 :
847 4 : ASSERT_FALSE (et_below (a, f));
848 4 : ASSERT_FALSE (et_below (b, f));
849 4 : ASSERT_FALSE (et_below (c, f));
850 4 : ASSERT_FALSE (et_below (d, f));
851 4 : ASSERT_FALSE (et_below (e, f));
852 4 : ASSERT_TRUE (et_below (f, f));
853 :
854 4 : et_free_tree_force (a);
855 4 : }
856 :
857 : /* Verify that two disconnected nodes are unrelated. */
858 :
859 : static void
860 4 : test_disconnected_nodes ()
861 : {
862 4 : et_node *a = et_new_tree (NULL);
863 4 : et_node *b = et_new_tree (NULL);
864 :
865 4 : ASSERT_FALSE (et_below (a, b));
866 4 : ASSERT_FALSE (et_below (b, a));
867 :
868 4 : et_free_tree (a);
869 4 : et_free_tree (b);
870 4 : }
871 :
872 : /* Run all of the selftests within this file. */
873 :
874 : void
875 4 : et_forest_cc_tests ()
876 : {
877 4 : test_single_node ();
878 4 : test_simple_tree ();
879 4 : test_disconnected_nodes ();
880 4 : }
881 :
882 : } // namespace selftest
883 :
884 : #endif /* CHECKING_P */
|
