gcc/et-forest.c

   1 /* ET-trees data structure implementation.
   2    Contributed by Pavel Nejedly
   3    Copyright (C) 2002-2019 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, 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 (f, occ->next);
 331               set_next (occ, f);
 332               set_depth_add (f->prev, occ_depth);
 333             }
 334           else
 335             {
 336               /* zag */
 337               set_next (f, occ->prev);
 338               set_prev (occ, f);
 339               set_depth_add (f->next, occ_depth);
 340             }
 341           set_depth (f, -occ_depth);
 342           occ->parent = NULL;
 343
 344           et_recomp_min (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, 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 (gf, f->next);
 366               set_prev (f, occ->next);
 367               set_next (occ, f);
 368               set_next (f, gf);
 369
 370               set_depth (f, -occ_depth);
 371               set_depth_add (f->prev, occ_depth);
 372               set_depth (gf, -f_depth);
 373               set_depth_add (gf->prev, f_depth);
 374             }
 375           else
 376             {
 377               /* zag zig */
 378               set_prev (gf, occ->next);
 379               set_next (f, occ->prev);
 380               set_prev (occ, f);
 381               set_next (occ, gf);
 382
 383               set_depth (f, -occ_depth);
 384               set_depth_add (f->next, occ_depth);
 385               set_depth (gf, -occ_depth - f_depth);
 386               set_depth_add (gf->prev, occ_depth + f_depth);
 387             }
 388         }
 389       else
 390         {
 391           if (f->prev == occ)
 392             {
 393               /* zig zag */
 394               set_next (gf, occ->prev);
 395               set_prev (f, occ->next);
 396               set_prev (occ, gf);
 397               set_next (occ, f);
 398
 399               set_depth (f, -occ_depth);
 400               set_depth_add (f->prev, occ_depth);
 401               set_depth (gf, -occ_depth - f_depth);
 402               set_depth_add (gf->next, occ_depth + f_depth);
 403             }
 404           else
 405             {
 406               /* zag zag */
 407               set_next (gf, f->prev);
 408               set_next (f, occ->prev);
 409               set_prev (occ, f);
 410               set_prev (f, gf);
 411
 412               set_depth (f, -occ_depth);
 413               set_depth_add (f->next, occ_depth);
 414               set_depth (gf, -f_depth);
 415               set_depth_add (gf->next, 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 (gf);
 429       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 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 (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 (t->rightmost_occ);
 491   et_nodes.remove (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 (t->rightmost_occ);
 500   if (t->parent_occ)
 501     et_occurrences.remove (t->parent_occ);
 502   et_nodes.remove (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 (father);
 524
 525   rmost = father->rightmost_occ;
 526   et_splay (rmost);
 527
 528   left_part = rmost->prev;
 529
 530   p = t->rightmost_occ;
 531   et_splay (p);
 532
 533   set_prev (new_f_occ, left_part);
 534   set_next (new_f_occ, p);
 535
 536   p->depth++;
 537   p->min++;
 538   et_recomp_min (new_f_occ);
 539
 540   set_prev (rmost, 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 (rmost);
 582
 583   for (r = rmost->next; r->prev; r = r->prev)
 584     continue;
 585   et_splay (r);
 586
 587   r->prev->parent = NULL;
 588   p_occ = t->parent_occ;
 589   et_splay (p_occ);
 590   t->parent_occ = NULL;
 591
 592   l = p_occ->prev;
 593   p_occ->next->parent = NULL;
 594
 595   set_prev (r, l);
 596
 597   et_recomp_min (r);
 598
 599   et_splay (rmost);
 600   rmost->depth = 0;
 601   rmost->min = 0;
 602
 603   et_occurrences.remove (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 (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 (o2);
 647
 648   if (l == o2 || (l && l->parent != NULL))
 649     {
 650       ret = o2->next;
 651
 652       set_prev (o1, 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 (o1, 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 (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 (d);
 719
 720   if (l == d || l->parent != NULL)
 721     {
 722       if (r)
 723         r->parent = u;
 724       set_prev (u, 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 (u, d);
 737       else
 738         set_next (u, 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 (r);
 765
 766   return r->of;
 767 }
 768
 769 #if CHECKING_P
 770
 771 namespace selftest {
 772
 773 /* Selftests for et-forest.c.  */
 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 (test_data);
 783   ASSERT_EQ (n->data, test_data);
 784   ASSERT_EQ (n, et_root (n));
 785   et_free_tree (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 (b, a);
 807   et_set_father (c, a);
 808   et_set_father (d, b);
 809   et_set_father (e, b);
 810   et_set_father (f, 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 (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 (a);
 869   et_free_tree (b);
 870 }
 871
 872 /* Run all of the selftests within this file.  */
 873
 874 void
 875 et_forest_c_tests ()
 876 {
 877   test_single_node ();
 878   test_simple_tree ();
 879   test_disconnected_nodes ();
 880 }
 881
 882 } // namespace selftest
 883
 884 #endif /* CHECKING_P */