1 /* ET-trees data structure implementation.
2 Contributed by Pavel Nejedly
3 Copyright (C) 2002, 2003, 2004 Free Software Foundation, Inc.
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 2 of the License, or (at your option) any later version.
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.
16 You should have received a copy of the GNU Library General Public
17 License along with libiberty; see the file COPYING.LIB. If
18 not, write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
19 Boston, MA 02111-1307, USA.
21 The ET-forest structure is described in:
22 D. D. Sleator and R. E. Tarjan. A data structure for dynamic trees.
23 J. G'omput. System Sci., 26(3):362 381, 1983.
28 #include "coretypes.h"
30 #include "et-forest.h"
31 #include "alloc-pool.h"
33 /* We do not enable this with ENABLE_CHECKING, since it is awfully slow. */
37 #include "basic-block.h"
40 /* The occurence of a node in the et tree. */
43 struct et_node *of; /* The node. */
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. */
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 occurence in the subtree with the minimal
58 static alloc_pool et_nodes;
59 static alloc_pool et_occurences;
61 /* Changes depth of OCC to D. */
64 set_depth (struct et_occ *occ, int d)
69 occ->min += d - occ->depth;
73 /* Adds D to the depth of OCC. */
76 set_depth_add (struct et_occ *occ, int d)
85 /* Sets prev field of OCC to P. */
88 set_prev (struct et_occ *occ, struct et_occ *t)
100 /* Sets next field of OCC to P. */
103 set_next (struct et_occ *occ, struct et_occ *t)
115 /* Recompute minimum for occurence OCC. */
118 et_recomp_min (struct et_occ *occ)
120 struct et_occ *mson = occ->prev;
124 && mson->min > occ->next->min))
127 if (mson && mson->min < 0)
129 occ->min = mson->min + occ->depth;
130 occ->min_occ = mson->min_occ;
134 occ->min = occ->depth;
140 /* Checks whether neighbourhood of OCC seems sane. */
143 et_check_occ_sanity (struct et_occ *occ)
148 if (occ->parent == occ)
151 if (occ->prev == occ)
154 if (occ->next == occ)
157 if (occ->next && occ->next == occ->prev)
162 if (occ->next == occ->parent)
165 if (occ->next->parent != occ)
171 if (occ->prev == occ->parent)
174 if (occ->prev->parent != occ)
179 && occ->parent->prev != occ
180 && occ->parent->next != occ)
184 /* Checks whether tree rooted at OCC is sane. */
187 et_check_sanity (struct et_occ *occ)
189 et_check_occ_sanity (occ);
191 et_check_sanity (occ->prev);
193 et_check_sanity (occ->next);
196 /* Checks whether tree containing OCC is sane. */
199 et_check_tree_sanity (struct et_occ *occ)
204 et_check_sanity (occ);
207 /* For recording the paths. */
210 static void *datas[100000];
211 static int depths[100000];
213 /* Records the path represented by OCC, with depth incremented by DEPTH. */
216 record_path_before_1 (struct et_occ *occ, int depth)
225 m = record_path_before_1 (occ->prev, depth);
230 fprintf (stderr, "%d (%d); ", ((basic_block) occ->of->data)->index, depth);
232 datas[len] = occ->of;
237 m = record_path_before_1 (occ->next, depth);
242 if (mn != occ->min + depth - occ->depth)
248 /* Records the path represented by a tree containing OCC. */
251 record_path_before (struct et_occ *occ)
257 record_path_before_1 (occ, 0);
258 fprintf (stderr, "\n");
261 /* Checks whether the path represented by OCC, with depth incremented by DEPTH,
262 was not changed since the last recording. */
265 check_path_after_1 (struct et_occ *occ, int depth)
274 m = check_path_after_1 (occ->next, depth);
280 if (depths[len] != depth
281 || datas[len] != occ->of)
286 m = check_path_after_1 (occ->prev, depth);
291 if (mn != occ->min + depth - occ->depth)
297 /* Checks whether the path represented by a tree containing OCC was
298 not changed since the last recording. */
301 check_path_after (struct et_occ *occ)
306 check_path_after_1 (occ, 0);
313 /* Splay the occurence OCC to the root of the tree. */
316 et_splay (struct et_occ *occ)
318 struct et_occ *f, *gf, *ggf;
319 int occ_depth, f_depth, gf_depth;
322 record_path_before (occ);
323 et_check_tree_sanity (occ);
328 occ_depth = occ->depth;
337 set_depth_add (occ, f_depth);
338 occ->min_occ = f->min_occ;
344 set_prev (f, occ->next);
346 set_depth_add (f->prev, occ_depth);
351 set_next (f, occ->prev);
353 set_depth_add (f->next, occ_depth);
355 set_depth (f, -occ_depth);
360 et_check_tree_sanity (occ);
361 check_path_after (occ);
366 gf_depth = gf->depth;
368 set_depth_add (occ, f_depth + gf_depth);
369 occ->min_occ = gf->min_occ;
379 set_prev (gf, f->next);
380 set_prev (f, occ->next);
384 set_depth (f, -occ_depth);
385 set_depth_add (f->prev, occ_depth);
386 set_depth (gf, -f_depth);
387 set_depth_add (gf->prev, f_depth);
392 set_prev (gf, occ->next);
393 set_next (f, occ->prev);
397 set_depth (f, -occ_depth);
398 set_depth_add (f->next, occ_depth);
399 set_depth (gf, -occ_depth - f_depth);
400 set_depth_add (gf->prev, occ_depth + f_depth);
408 set_next (gf, occ->prev);
409 set_prev (f, occ->next);
413 set_depth (f, -occ_depth);
414 set_depth_add (f->prev, occ_depth);
415 set_depth (gf, -occ_depth - f_depth);
416 set_depth_add (gf->next, occ_depth + f_depth);
421 set_next (gf, f->prev);
422 set_next (f, occ->prev);
426 set_depth (f, -occ_depth);
427 set_depth_add (f->next, occ_depth);
428 set_depth (gf, -f_depth);
429 set_depth_add (gf->next, f_depth);
445 et_check_tree_sanity (occ);
450 et_check_sanity (occ);
451 check_path_after (occ);
455 /* Create a new et tree occurence of NODE. */
457 static struct et_occ *
458 et_new_occ (struct et_node *node)
463 et_occurences = create_alloc_pool ("et_occ pool", sizeof (struct et_occ), 300);
464 nw = pool_alloc (et_occurences);
478 /* Create a new et tree containing DATA. */
481 et_new_tree (void *data)
486 et_nodes = create_alloc_pool ("et_node pool", sizeof (struct et_node), 300);
487 nw = pool_alloc (et_nodes);
495 nw->rightmost_occ = et_new_occ (nw);
496 nw->parent_occ = NULL;
501 /* Releases et tree T. */
504 et_free_tree (struct et_node *t)
512 pool_free (et_occurences, t->rightmost_occ);
513 pool_free (et_nodes, t);
516 /* Sets father of et tree T to FATHER. */
519 et_set_father (struct et_node *t, struct et_node *father)
521 struct et_node *left, *right;
522 struct et_occ *rmost, *left_part, *new_f_occ, *p;
524 /* Update the path represented in the splay tree. */
525 new_f_occ = et_new_occ (father);
527 rmost = father->rightmost_occ;
530 left_part = rmost->prev;
532 p = t->rightmost_occ;
535 set_prev (new_f_occ, left_part);
536 set_next (new_f_occ, p);
540 et_recomp_min (new_f_occ);
542 set_prev (rmost, new_f_occ);
544 if (new_f_occ->min + rmost->depth < rmost->min)
546 rmost->min = new_f_occ->min + rmost->depth;
547 rmost->min_occ = new_f_occ->min_occ;
550 t->parent_occ = new_f_occ;
552 /* Update the tree. */
568 et_check_tree_sanity (rmost);
569 record_path_before (rmost);
573 /* Splits the edge from T to its father. */
576 et_split (struct et_node *t)
578 struct et_node *father = t->father;
579 struct et_occ *r, *l, *rmost, *p_occ;
581 /* Update the path represented by the splay tree. */
582 rmost = t->rightmost_occ;
585 for (r = rmost->next; r->prev; r = r->prev)
589 r->prev->parent = NULL;
590 p_occ = t->parent_occ;
592 t->parent_occ = NULL;
595 p_occ->next->parent = NULL;
605 pool_free (et_occurences, p_occ);
607 /* Update the tree. */
608 if (father->son == t)
609 father->son = t->right;
610 if (father->son == t)
614 t->left->right = t->right;
615 t->right->left = t->left;
617 t->left = t->right = NULL;
621 et_check_tree_sanity (rmost);
622 record_path_before (rmost);
624 et_check_tree_sanity (r);
625 record_path_before (r);
629 /* Finds the nearest common ancestor of the nodes N1 and N2. */
632 et_nca (struct et_node *n1, struct et_node *n2)
634 struct et_occ *o1 = n1->rightmost_occ, *o2 = n2->rightmost_occ, *om;
635 struct et_occ *l, *r, *ret;
650 if (l == o2 || (l && l->parent != NULL))
675 mn = o2->depth + o1->depth;
679 et_check_tree_sanity (o2);
682 if (ret && ret->min + o1->depth + o2->depth < mn)
683 return ret->min_occ->of;
688 /* Checks whether the node UP is an ancestor of the node DOWN. */
691 et_below (struct et_node *down, struct et_node *up)
693 struct et_occ *u = up->rightmost_occ, *d = down->rightmost_occ;
694 struct et_occ *l, *r;
713 if (l == d || l->parent != NULL)
719 et_check_tree_sanity (u);
726 /* In case O1 and O2 are in two different trees, we must just restore the
728 if (r && r->parent != NULL)
734 et_check_tree_sanity (u);
742 return !d->next || d->next->min + d->depth >= 0;