1132718Skan/* ET-trees data structure implementation. 2117395Skan Contributed by Pavel Nejedly 3169689Skan Copyright (C) 2002, 2003, 2004, 2005 Free Software Foundation, Inc. 4117395Skan 5117395SkanThis file is part of the libiberty library. 6117395SkanLibiberty is free software; you can redistribute it and/or 7117395Skanmodify it under the terms of the GNU Library General Public 8117395SkanLicense as published by the Free Software Foundation; either 9117395Skanversion 2 of the License, or (at your option) any later version. 10117395Skan 11117395SkanLibiberty is distributed in the hope that it will be useful, 12117395Skanbut WITHOUT ANY WARRANTY; without even the implied warranty of 13117395SkanMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 14117395SkanLibrary General Public License for more details. 15117395Skan 16117395SkanYou should have received a copy of the GNU Library General Public 17117395SkanLicense along with libiberty; see the file COPYING.LIB. If 18169689Skannot, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, 19169689SkanBoston, MA 02110-1301, USA. 20117395Skan 21117395Skan The ET-forest structure is described in: 22117395Skan D. D. Sleator and R. E. Tarjan. A data structure for dynamic trees. 23117395Skan J. G'omput. System Sci., 26(3):362 381, 1983. 24117395Skan*/ 25117395Skan 26117395Skan#include "config.h" 27117395Skan#include "system.h" 28132718Skan#include "coretypes.h" 29132718Skan#include "tm.h" 30117395Skan#include "et-forest.h" 31132718Skan#include "alloc-pool.h" 32117395Skan 33132718Skan/* We do not enable this with ENABLE_CHECKING, since it is awfully slow. */ 34132718Skan#undef DEBUG_ET 35117395Skan 36132718Skan#ifdef DEBUG_ET 37132718Skan#include "basic-block.h" 38132718Skan#endif 39132718Skan 40169689Skan/* The occurrence of a node in the et tree. */ 41132718Skanstruct et_occ 42117395Skan{ 43132718Skan struct et_node *of; /* The node. */ 44132718Skan 45132718Skan struct et_occ *parent; /* Parent in the splay-tree. */ 46132718Skan struct et_occ *prev; /* Left son in the splay-tree. */ 47132718Skan struct et_occ *next; /* Right son in the splay-tree. */ 48132718Skan 49132718Skan int depth; /* The depth of the node is the sum of depth 50132718Skan fields on the path to the root. */ 51132718Skan int min; /* The minimum value of the depth in the subtree 52132718Skan is obtained by adding sum of depth fields 53132718Skan on the path to the root. */ 54169689Skan struct et_occ *min_occ; /* The occurrence in the subtree with the minimal 55132718Skan depth. */ 56117395Skan}; 57117395Skan 58132718Skanstatic alloc_pool et_nodes; 59169689Skanstatic alloc_pool et_occurrences; 60117395Skan 61132718Skan/* Changes depth of OCC to D. */ 62117395Skan 63132718Skanstatic inline void 64132718Skanset_depth (struct et_occ *occ, int d) 65132718Skan{ 66132718Skan if (!occ) 67132718Skan return; 68117395Skan 69132718Skan occ->min += d - occ->depth; 70132718Skan occ->depth = d; 71132718Skan} 72117395Skan 73132718Skan/* Adds D to the depth of OCC. */ 74117395Skan 75132718Skanstatic inline void 76132718Skanset_depth_add (struct et_occ *occ, int d) 77117395Skan{ 78132718Skan if (!occ) 79132718Skan return; 80117395Skan 81132718Skan occ->min += d; 82132718Skan occ->depth += d; 83132718Skan} 84117395Skan 85132718Skan/* Sets prev field of OCC to P. */ 86117395Skan 87132718Skanstatic inline void 88132718Skanset_prev (struct et_occ *occ, struct et_occ *t) 89117395Skan{ 90132718Skan#ifdef DEBUG_ET 91169689Skan gcc_assert (occ != t); 92132718Skan#endif 93117395Skan 94132718Skan occ->prev = t; 95132718Skan if (t) 96132718Skan t->parent = occ; 97117395Skan} 98117395Skan 99132718Skan/* Sets next field of OCC to P. */ 100132718Skan 101132718Skanstatic inline void 102132718Skanset_next (struct et_occ *occ, struct et_occ *t) 103117395Skan{ 104132718Skan#ifdef DEBUG_ET 105169689Skan gcc_assert (occ != t); 106132718Skan#endif 107132718Skan 108132718Skan occ->next = t; 109132718Skan if (t) 110132718Skan t->parent = occ; 111117395Skan} 112117395Skan 113169689Skan/* Recompute minimum for occurrence OCC. */ 114117395Skan 115132718Skanstatic inline void 116132718Skanet_recomp_min (struct et_occ *occ) 117117395Skan{ 118132718Skan struct et_occ *mson = occ->prev; 119117395Skan 120132718Skan if (!mson 121132718Skan || (occ->next 122132718Skan && mson->min > occ->next->min)) 123132718Skan mson = occ->next; 124132718Skan 125132718Skan if (mson && mson->min < 0) 126117395Skan { 127132718Skan occ->min = mson->min + occ->depth; 128132718Skan occ->min_occ = mson->min_occ; 129132718Skan } 130132718Skan else 131132718Skan { 132132718Skan occ->min = occ->depth; 133132718Skan occ->min_occ = occ; 134132718Skan } 135132718Skan} 136117395Skan 137132718Skan#ifdef DEBUG_ET 138169689Skan/* Checks whether neighborhood of OCC seems sane. */ 139117395Skan 140132718Skanstatic void 141132718Skanet_check_occ_sanity (struct et_occ *occ) 142132718Skan{ 143132718Skan if (!occ) 144132718Skan return; 145117395Skan 146169689Skan gcc_assert (occ->parent != occ); 147169689Skan gcc_assert (occ->prev != occ); 148169689Skan gcc_assert (occ->next != occ); 149169689Skan gcc_assert (!occ->next || occ->next != occ->prev); 150117395Skan 151132718Skan if (occ->next) 152132718Skan { 153169689Skan gcc_assert (occ->next != occ->parent); 154169689Skan gcc_assert (occ->next->parent == occ); 155132718Skan } 156117395Skan 157132718Skan if (occ->prev) 158132718Skan { 159169689Skan gcc_assert (occ->prev != occ->parent); 160169689Skan gcc_assert (occ->prev->parent == occ); 161132718Skan } 162117395Skan 163169689Skan gcc_assert (!occ->parent 164169689Skan || occ->parent->prev == occ 165169689Skan || occ->parent->next == occ); 166132718Skan} 167117395Skan 168132718Skan/* Checks whether tree rooted at OCC is sane. */ 169117395Skan 170132718Skanstatic void 171132718Skanet_check_sanity (struct et_occ *occ) 172132718Skan{ 173132718Skan et_check_occ_sanity (occ); 174132718Skan if (occ->prev) 175132718Skan et_check_sanity (occ->prev); 176132718Skan if (occ->next) 177132718Skan et_check_sanity (occ->next); 178132718Skan} 179117395Skan 180132718Skan/* Checks whether tree containing OCC is sane. */ 181117395Skan 182132718Skanstatic void 183132718Skanet_check_tree_sanity (struct et_occ *occ) 184132718Skan{ 185132718Skan while (occ->parent) 186132718Skan occ = occ->parent; 187117395Skan 188132718Skan et_check_sanity (occ); 189132718Skan} 190117395Skan 191132718Skan/* For recording the paths. */ 192117395Skan 193169689Skan/* An ad-hoc constant; if the function has more blocks, this won't work, 194169689Skan but since it is used for debugging only, it does not matter. */ 195169689Skan#define MAX_NODES 100000 196169689Skan 197132718Skanstatic int len; 198169689Skanstatic void *datas[MAX_NODES]; 199169689Skanstatic int depths[MAX_NODES]; 200117395Skan 201132718Skan/* Records the path represented by OCC, with depth incremented by DEPTH. */ 202117395Skan 203132718Skanstatic int 204132718Skanrecord_path_before_1 (struct et_occ *occ, int depth) 205132718Skan{ 206132718Skan int mn, m; 207117395Skan 208132718Skan depth += occ->depth; 209132718Skan mn = depth; 210132718Skan 211132718Skan if (occ->prev) 212132718Skan { 213132718Skan m = record_path_before_1 (occ->prev, depth); 214132718Skan if (m < mn) 215132718Skan mn = m; 216117395Skan } 217117395Skan 218132718Skan fprintf (stderr, "%d (%d); ", ((basic_block) occ->of->data)->index, depth); 219169689Skan 220169689Skan gcc_assert (len < MAX_NODES); 221169689Skan 222132718Skan depths[len] = depth; 223132718Skan datas[len] = occ->of; 224132718Skan len++; 225117395Skan 226132718Skan if (occ->next) 227117395Skan { 228132718Skan m = record_path_before_1 (occ->next, depth); 229132718Skan if (m < mn) 230132718Skan mn = m; 231132718Skan } 232117395Skan 233169689Skan gcc_assert (mn == occ->min + depth - occ->depth); 234117395Skan 235132718Skan return mn; 236132718Skan} 237132718Skan 238132718Skan/* Records the path represented by a tree containing OCC. */ 239132718Skan 240132718Skanstatic void 241132718Skanrecord_path_before (struct et_occ *occ) 242132718Skan{ 243132718Skan while (occ->parent) 244132718Skan occ = occ->parent; 245132718Skan 246132718Skan len = 0; 247132718Skan record_path_before_1 (occ, 0); 248132718Skan fprintf (stderr, "\n"); 249132718Skan} 250132718Skan 251132718Skan/* Checks whether the path represented by OCC, with depth incremented by DEPTH, 252132718Skan was not changed since the last recording. */ 253132718Skan 254132718Skanstatic int 255132718Skancheck_path_after_1 (struct et_occ *occ, int depth) 256132718Skan{ 257132718Skan int mn, m; 258132718Skan 259132718Skan depth += occ->depth; 260132718Skan mn = depth; 261132718Skan 262132718Skan if (occ->next) 263117395Skan { 264132718Skan m = check_path_after_1 (occ->next, depth); 265132718Skan if (m < mn) 266132718Skan mn = m; 267132718Skan } 268117395Skan 269132718Skan len--; 270169689Skan gcc_assert (depths[len] == depth && datas[len] == occ->of); 271117395Skan 272132718Skan if (occ->prev) 273132718Skan { 274132718Skan m = check_path_after_1 (occ->prev, depth); 275132718Skan if (m < mn) 276132718Skan mn = m; 277117395Skan } 278117395Skan 279169689Skan gcc_assert (mn == occ->min + depth - occ->depth); 280132718Skan 281132718Skan return mn; 282117395Skan} 283117395Skan 284132718Skan/* Checks whether the path represented by a tree containing OCC was 285132718Skan not changed since the last recording. */ 286132718Skan 287117395Skanstatic void 288132718Skancheck_path_after (struct et_occ *occ) 289117395Skan{ 290132718Skan while (occ->parent) 291132718Skan occ = occ->parent; 292117395Skan 293132718Skan check_path_after_1 (occ, 0); 294169689Skan gcc_assert (!len); 295132718Skan} 296117395Skan 297132718Skan#endif 298117395Skan 299169689Skan/* Splay the occurrence OCC to the root of the tree. */ 300117395Skan 301132718Skanstatic void 302132718Skanet_splay (struct et_occ *occ) 303132718Skan{ 304132718Skan struct et_occ *f, *gf, *ggf; 305132718Skan int occ_depth, f_depth, gf_depth; 306117395Skan 307132718Skan#ifdef DEBUG_ET 308132718Skan record_path_before (occ); 309132718Skan et_check_tree_sanity (occ); 310132718Skan#endif 311132718Skan 312132718Skan while (occ->parent) 313117395Skan { 314132718Skan occ_depth = occ->depth; 315117395Skan 316132718Skan f = occ->parent; 317132718Skan f_depth = f->depth; 318117395Skan 319132718Skan gf = f->parent; 320117395Skan 321132718Skan if (!gf) 322132718Skan { 323132718Skan set_depth_add (occ, f_depth); 324132718Skan occ->min_occ = f->min_occ; 325132718Skan occ->min = f->min; 326117395Skan 327132718Skan if (f->prev == occ) 328132718Skan { 329132718Skan /* zig */ 330132718Skan set_prev (f, occ->next); 331132718Skan set_next (occ, f); 332132718Skan set_depth_add (f->prev, occ_depth); 333132718Skan } 334132718Skan else 335132718Skan { 336132718Skan /* zag */ 337132718Skan set_next (f, occ->prev); 338132718Skan set_prev (occ, f); 339132718Skan set_depth_add (f->next, occ_depth); 340132718Skan } 341132718Skan set_depth (f, -occ_depth); 342132718Skan occ->parent = NULL; 343117395Skan 344132718Skan et_recomp_min (f); 345132718Skan#ifdef DEBUG_ET 346132718Skan et_check_tree_sanity (occ); 347132718Skan check_path_after (occ); 348132718Skan#endif 349132718Skan return; 350132718Skan } 351117395Skan 352132718Skan gf_depth = gf->depth; 353132718Skan 354132718Skan set_depth_add (occ, f_depth + gf_depth); 355132718Skan occ->min_occ = gf->min_occ; 356132718Skan occ->min = gf->min; 357132718Skan 358132718Skan ggf = gf->parent; 359132718Skan 360132718Skan if (gf->prev == f) 361117395Skan { 362132718Skan if (f->prev == occ) 363132718Skan { 364132718Skan /* zig zig */ 365132718Skan set_prev (gf, f->next); 366132718Skan set_prev (f, occ->next); 367132718Skan set_next (occ, f); 368132718Skan set_next (f, gf); 369117395Skan 370132718Skan set_depth (f, -occ_depth); 371132718Skan set_depth_add (f->prev, occ_depth); 372132718Skan set_depth (gf, -f_depth); 373132718Skan set_depth_add (gf->prev, f_depth); 374132718Skan } 375132718Skan else 376132718Skan { 377132718Skan /* zag zig */ 378132718Skan set_prev (gf, occ->next); 379132718Skan set_next (f, occ->prev); 380132718Skan set_prev (occ, f); 381132718Skan set_next (occ, gf); 382117395Skan 383132718Skan set_depth (f, -occ_depth); 384132718Skan set_depth_add (f->next, occ_depth); 385132718Skan set_depth (gf, -occ_depth - f_depth); 386132718Skan set_depth_add (gf->prev, occ_depth + f_depth); 387132718Skan } 388132718Skan } 389132718Skan else 390132718Skan { 391132718Skan if (f->prev == occ) 392132718Skan { 393132718Skan /* zig zag */ 394132718Skan set_next (gf, occ->prev); 395132718Skan set_prev (f, occ->next); 396132718Skan set_prev (occ, gf); 397132718Skan set_next (occ, f); 398117395Skan 399132718Skan set_depth (f, -occ_depth); 400132718Skan set_depth_add (f->prev, occ_depth); 401132718Skan set_depth (gf, -occ_depth - f_depth); 402132718Skan set_depth_add (gf->next, occ_depth + f_depth); 403132718Skan } 404132718Skan else 405132718Skan { 406132718Skan /* zag zag */ 407132718Skan set_next (gf, f->prev); 408132718Skan set_next (f, occ->prev); 409132718Skan set_prev (occ, f); 410132718Skan set_prev (f, gf); 411132718Skan 412132718Skan set_depth (f, -occ_depth); 413132718Skan set_depth_add (f->next, occ_depth); 414132718Skan set_depth (gf, -f_depth); 415132718Skan set_depth_add (gf->next, f_depth); 416132718Skan } 417117395Skan } 418132718Skan 419132718Skan occ->parent = ggf; 420132718Skan if (ggf) 421132718Skan { 422132718Skan if (ggf->prev == gf) 423132718Skan ggf->prev = occ; 424132718Skan else 425132718Skan ggf->next = occ; 426132718Skan } 427132718Skan 428132718Skan et_recomp_min (gf); 429132718Skan et_recomp_min (f); 430132718Skan#ifdef DEBUG_ET 431132718Skan et_check_tree_sanity (occ); 432132718Skan#endif 433117395Skan } 434117395Skan 435132718Skan#ifdef DEBUG_ET 436132718Skan et_check_sanity (occ); 437132718Skan check_path_after (occ); 438132718Skan#endif 439117395Skan} 440117395Skan 441169689Skan/* Create a new et tree occurrence of NODE. */ 442132718Skan 443132718Skanstatic struct et_occ * 444132718Skanet_new_occ (struct et_node *node) 445117395Skan{ 446132718Skan struct et_occ *nw; 447132718Skan 448169689Skan if (!et_occurrences) 449169689Skan et_occurrences = create_alloc_pool ("et_occ pool", sizeof (struct et_occ), 300); 450169689Skan nw = pool_alloc (et_occurrences); 451117395Skan 452132718Skan nw->of = node; 453132718Skan nw->parent = NULL; 454132718Skan nw->prev = NULL; 455132718Skan nw->next = NULL; 456117395Skan 457132718Skan nw->depth = 0; 458132718Skan nw->min_occ = nw; 459132718Skan nw->min = 0; 460117395Skan 461132718Skan return nw; 462117395Skan} 463117395Skan 464132718Skan/* Create a new et tree containing DATA. */ 465117395Skan 466132718Skanstruct et_node * 467132718Skanet_new_tree (void *data) 468132718Skan{ 469132718Skan struct et_node *nw; 470132718Skan 471132718Skan if (!et_nodes) 472132718Skan et_nodes = create_alloc_pool ("et_node pool", sizeof (struct et_node), 300); 473132718Skan nw = pool_alloc (et_nodes); 474117395Skan 475132718Skan nw->data = data; 476132718Skan nw->father = NULL; 477132718Skan nw->left = NULL; 478132718Skan nw->right = NULL; 479132718Skan nw->son = NULL; 480117395Skan 481132718Skan nw->rightmost_occ = et_new_occ (nw); 482132718Skan nw->parent_occ = NULL; 483117395Skan 484132718Skan return nw; 485117395Skan} 486117395Skan 487132718Skan/* Releases et tree T. */ 488117395Skan 489132718Skanvoid 490132718Skanet_free_tree (struct et_node *t) 491117395Skan{ 492132718Skan while (t->son) 493132718Skan et_split (t->son); 494117395Skan 495132718Skan if (t->father) 496132718Skan et_split (t); 497132718Skan 498169689Skan pool_free (et_occurrences, t->rightmost_occ); 499132718Skan pool_free (et_nodes, t); 500117395Skan} 501117395Skan 502169689Skan/* Releases et tree T without maintaining other nodes. */ 503169689Skan 504169689Skanvoid 505169689Skanet_free_tree_force (struct et_node *t) 506169689Skan{ 507169689Skan pool_free (et_occurrences, t->rightmost_occ); 508169689Skan if (t->parent_occ) 509169689Skan pool_free (et_occurrences, t->parent_occ); 510169689Skan pool_free (et_nodes, t); 511169689Skan} 512169689Skan 513169689Skan/* Release the alloc pools, if they are empty. */ 514169689Skan 515169689Skanvoid 516169689Skanet_free_pools (void) 517169689Skan{ 518169689Skan free_alloc_pool_if_empty (&et_occurrences); 519169689Skan free_alloc_pool_if_empty (&et_nodes); 520169689Skan} 521169689Skan 522132718Skan/* Sets father of et tree T to FATHER. */ 523132718Skan 524132718Skanvoid 525132718Skanet_set_father (struct et_node *t, struct et_node *father) 526117395Skan{ 527132718Skan struct et_node *left, *right; 528132718Skan struct et_occ *rmost, *left_part, *new_f_occ, *p; 529117395Skan 530132718Skan /* Update the path represented in the splay tree. */ 531132718Skan new_f_occ = et_new_occ (father); 532117395Skan 533132718Skan rmost = father->rightmost_occ; 534132718Skan et_splay (rmost); 535117395Skan 536132718Skan left_part = rmost->prev; 537117395Skan 538132718Skan p = t->rightmost_occ; 539132718Skan et_splay (p); 540117395Skan 541132718Skan set_prev (new_f_occ, left_part); 542132718Skan set_next (new_f_occ, p); 543117395Skan 544132718Skan p->depth++; 545132718Skan p->min++; 546132718Skan et_recomp_min (new_f_occ); 547117395Skan 548132718Skan set_prev (rmost, new_f_occ); 549117395Skan 550132718Skan if (new_f_occ->min + rmost->depth < rmost->min) 551132718Skan { 552132718Skan rmost->min = new_f_occ->min + rmost->depth; 553132718Skan rmost->min_occ = new_f_occ->min_occ; 554132718Skan } 555117395Skan 556132718Skan t->parent_occ = new_f_occ; 557117395Skan 558132718Skan /* Update the tree. */ 559132718Skan t->father = father; 560132718Skan right = father->son; 561132718Skan if (right) 562132718Skan left = right->left; 563132718Skan else 564132718Skan left = right = t; 565117395Skan 566132718Skan left->right = t; 567132718Skan right->left = t; 568132718Skan t->left = left; 569132718Skan t->right = right; 570117395Skan 571132718Skan father->son = t; 572117395Skan 573132718Skan#ifdef DEBUG_ET 574132718Skan et_check_tree_sanity (rmost); 575132718Skan record_path_before (rmost); 576132718Skan#endif 577117395Skan} 578117395Skan 579132718Skan/* Splits the edge from T to its father. */ 580132718Skan 581132718Skanvoid 582132718Skanet_split (struct et_node *t) 583117395Skan{ 584132718Skan struct et_node *father = t->father; 585132718Skan struct et_occ *r, *l, *rmost, *p_occ; 586117395Skan 587132718Skan /* Update the path represented by the splay tree. */ 588132718Skan rmost = t->rightmost_occ; 589132718Skan et_splay (rmost); 590117395Skan 591132718Skan for (r = rmost->next; r->prev; r = r->prev) 592132718Skan continue; 593132718Skan et_splay (r); 594117395Skan 595132718Skan r->prev->parent = NULL; 596132718Skan p_occ = t->parent_occ; 597132718Skan et_splay (p_occ); 598132718Skan t->parent_occ = NULL; 599117395Skan 600132718Skan l = p_occ->prev; 601132718Skan p_occ->next->parent = NULL; 602117395Skan 603132718Skan set_prev (r, l); 604117395Skan 605132718Skan et_recomp_min (r); 606117395Skan 607132718Skan et_splay (rmost); 608132718Skan rmost->depth = 0; 609132718Skan rmost->min = 0; 610117395Skan 611169689Skan pool_free (et_occurrences, p_occ); 612117395Skan 613132718Skan /* Update the tree. */ 614132718Skan if (father->son == t) 615132718Skan father->son = t->right; 616132718Skan if (father->son == t) 617132718Skan father->son = NULL; 618132718Skan else 619132718Skan { 620132718Skan t->left->right = t->right; 621132718Skan t->right->left = t->left; 622132718Skan } 623132718Skan t->left = t->right = NULL; 624132718Skan t->father = NULL; 625117395Skan 626132718Skan#ifdef DEBUG_ET 627132718Skan et_check_tree_sanity (rmost); 628132718Skan record_path_before (rmost); 629117395Skan 630132718Skan et_check_tree_sanity (r); 631132718Skan record_path_before (r); 632132718Skan#endif 633117395Skan} 634117395Skan 635132718Skan/* Finds the nearest common ancestor of the nodes N1 and N2. */ 636117395Skan 637132718Skanstruct et_node * 638132718Skanet_nca (struct et_node *n1, struct et_node *n2) 639117395Skan{ 640132718Skan struct et_occ *o1 = n1->rightmost_occ, *o2 = n2->rightmost_occ, *om; 641132718Skan struct et_occ *l, *r, *ret; 642132718Skan int mn; 643117395Skan 644132718Skan if (n1 == n2) 645132718Skan return n1; 646117395Skan 647132718Skan et_splay (o1); 648132718Skan l = o1->prev; 649132718Skan r = o1->next; 650132718Skan if (l) 651132718Skan l->parent = NULL; 652132718Skan if (r) 653132718Skan r->parent = NULL; 654132718Skan et_splay (o2); 655117395Skan 656132718Skan if (l == o2 || (l && l->parent != NULL)) 657132718Skan { 658132718Skan ret = o2->next; 659117395Skan 660132718Skan set_prev (o1, o2); 661132718Skan if (r) 662132718Skan r->parent = o1; 663132718Skan } 664132718Skan else 665132718Skan { 666132718Skan ret = o2->prev; 667117395Skan 668132718Skan set_next (o1, o2); 669132718Skan if (l) 670132718Skan l->parent = o1; 671132718Skan } 672132718Skan 673132718Skan if (0 < o2->depth) 674117395Skan { 675132718Skan om = o1; 676132718Skan mn = o1->depth; 677117395Skan } 678117395Skan else 679117395Skan { 680132718Skan om = o2; 681132718Skan mn = o2->depth + o1->depth; 682117395Skan } 683117395Skan 684132718Skan#ifdef DEBUG_ET 685132718Skan et_check_tree_sanity (o2); 686132718Skan#endif 687117395Skan 688132718Skan if (ret && ret->min + o1->depth + o2->depth < mn) 689132718Skan return ret->min_occ->of; 690132718Skan else 691132718Skan return om->of; 692117395Skan} 693117395Skan 694132718Skan/* Checks whether the node UP is an ancestor of the node DOWN. */ 695132718Skan 696132718Skanbool 697132718Skanet_below (struct et_node *down, struct et_node *up) 698117395Skan{ 699132718Skan struct et_occ *u = up->rightmost_occ, *d = down->rightmost_occ; 700132718Skan struct et_occ *l, *r; 701117395Skan 702132718Skan if (up == down) 703132718Skan return true; 704132718Skan 705132718Skan et_splay (u); 706132718Skan l = u->prev; 707132718Skan r = u->next; 708132718Skan 709132718Skan if (!l) 710132718Skan return false; 711132718Skan 712132718Skan l->parent = NULL; 713132718Skan 714132718Skan if (r) 715132718Skan r->parent = NULL; 716132718Skan 717132718Skan et_splay (d); 718132718Skan 719132718Skan if (l == d || l->parent != NULL) 720117395Skan { 721132718Skan if (r) 722132718Skan r->parent = u; 723132718Skan set_prev (u, d); 724132718Skan#ifdef DEBUG_ET 725132718Skan et_check_tree_sanity (u); 726132718Skan#endif 727117395Skan } 728132718Skan else 729132718Skan { 730132718Skan l->parent = u; 731132718Skan 732132718Skan /* In case O1 and O2 are in two different trees, we must just restore the 733132718Skan original state. */ 734132718Skan if (r && r->parent != NULL) 735132718Skan set_next (u, d); 736132718Skan else 737132718Skan set_next (u, r); 738132718Skan 739132718Skan#ifdef DEBUG_ET 740132718Skan et_check_tree_sanity (u); 741132718Skan#endif 742132718Skan return false; 743132718Skan } 744132718Skan 745132718Skan if (0 >= d->depth) 746132718Skan return false; 747132718Skan 748132718Skan return !d->next || d->next->min + d->depth >= 0; 749117395Skan} 750