-/* ET-trees datastructure implementation.
+/* ET-trees data structure implementation.
Contributed by Pavel Nejedly
- Copyright (C) 2002 Free Software Foundation, Inc.
+ Copyright (C) 2002, 2003, 2004, 2005, 2007, 2008 Free Software
+ Foundation, Inc.
This file is part of the libiberty library.
Libiberty is free software; you can redistribute it and/or
modify it under the terms of the GNU Library General Public
License as published by the Free Software Foundation; either
-version 2 of the License, or (at your option) any later version.
+version 3 of the License, or (at your option) any later version.
Libiberty is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
Library General Public License for more details.
You should have received a copy of the GNU Library General Public
-License along with libiberty; see the file COPYING.LIB. If
-not, write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
-Boston, MA 02111-1307, USA.
+License along with libiberty; see the file COPYING3. If not see
+<http://www.gnu.org/licenses/>.
The ET-forest structure is described in:
D. D. Sleator and R. E. Tarjan. A data structure for dynamic trees.
#include "config.h"
#include "system.h"
+#include "coretypes.h"
+#include "tm.h"
#include "et-forest.h"
+#include "alloc-pool.h"
-struct et_forest_occurrence;
-typedef struct et_forest_occurrence* et_forest_occurrence_t;
+/* We do not enable this with ENABLE_CHECKING, since it is awfully slow. */
+#undef DEBUG_ET
-/* The ET-forest type. */
-struct et_forest
+#ifdef DEBUG_ET
+#include "basic-block.h"
+#endif
+
+/* The occurrence of a node in the et tree. */
+struct et_occ
{
- /* Linked list of nodes is used to destroy the structure. */
- int nnodes;
+ struct et_node *of; /* The node. */
+
+ struct et_occ *parent; /* Parent in the splay-tree. */
+ struct et_occ *prev; /* Left son in the splay-tree. */
+ struct et_occ *next; /* Right son in the splay-tree. */
+
+ int depth; /* The depth of the node is the sum of depth
+ fields on the path to the root. */
+ int min; /* The minimum value of the depth in the subtree
+ is obtained by adding sum of depth fields
+ on the path to the root. */
+ struct et_occ *min_occ; /* The occurrence in the subtree with the minimal
+ depth. */
};
-/* Single occurrence of node in ET-forest.
- A single node may have multiple occurrences.
- */
-struct et_forest_occurrence
+static alloc_pool et_nodes;
+static alloc_pool et_occurrences;
+
+/* Changes depth of OCC to D. */
+
+static inline void
+set_depth (struct et_occ *occ, int d)
{
- /* Parent in the splay-tree. */
- et_forest_occurrence_t parent;
+ if (!occ)
+ return;
- /* Children in the splay-tree. */
- et_forest_occurrence_t left, right;
+ occ->min += d - occ->depth;
+ occ->depth = d;
+}
- /* Counts of vertices in the two splay-subtrees. */
- int count_left, count_right;
+/* Adds D to the depth of OCC. */
- /* Next occurrence of this node in the sequence. */
- et_forest_occurrence_t next;
+static inline void
+set_depth_add (struct et_occ *occ, int d)
+{
+ if (!occ)
+ return;
- /* The node, which this occurrence is of. */
- et_forest_node_t node;
-};
+ occ->min += d;
+ occ->depth += d;
+}
+/* Sets prev field of OCC to P. */
-/* ET-forest node. */
-struct et_forest_node
+static inline void
+set_prev (struct et_occ *occ, struct et_occ *t)
{
- et_forest_t forest;
- void *value;
+#ifdef DEBUG_ET
+ gcc_assert (occ != t);
+#endif
- /* First and last occurrence of this node in the sequence. */
- et_forest_occurrence_t first, last;
-};
+ occ->prev = t;
+ if (t)
+ t->parent = occ;
+}
+
+/* Sets next field of OCC to P. */
+
+static inline void
+set_next (struct et_occ *occ, struct et_occ *t)
+{
+#ifdef DEBUG_ET
+ gcc_assert (occ != t);
+#endif
+
+ occ->next = t;
+ if (t)
+ t->parent = occ;
+}
+
+/* Recompute minimum for occurrence OCC. */
+
+static inline void
+et_recomp_min (struct et_occ *occ)
+{
+ struct et_occ *mson = occ->prev;
+
+ if (!mson
+ || (occ->next
+ && mson->min > occ->next->min))
+ mson = occ->next;
+
+ if (mson && mson->min < 0)
+ {
+ occ->min = mson->min + occ->depth;
+ occ->min_occ = mson->min_occ;
+ }
+ else
+ {
+ occ->min = occ->depth;
+ occ->min_occ = occ;
+ }
+}
+
+#ifdef DEBUG_ET
+/* Checks whether neighborhood of OCC seems sane. */
+
+static void
+et_check_occ_sanity (struct et_occ *occ)
+{
+ if (!occ)
+ return;
+
+ gcc_assert (occ->parent != occ);
+ gcc_assert (occ->prev != occ);
+ gcc_assert (occ->next != occ);
+ gcc_assert (!occ->next || occ->next != occ->prev);
+
+ if (occ->next)
+ {
+ gcc_assert (occ->next != occ->parent);
+ gcc_assert (occ->next->parent == occ);
+ }
+
+ if (occ->prev)
+ {
+ gcc_assert (occ->prev != occ->parent);
+ gcc_assert (occ->prev->parent == occ);
+ }
+
+ gcc_assert (!occ->parent
+ || occ->parent->prev == occ
+ || occ->parent->next == occ);
+}
+
+/* Checks whether tree rooted at OCC is sane. */
+
+static void
+et_check_sanity (struct et_occ *occ)
+{
+ et_check_occ_sanity (occ);
+ if (occ->prev)
+ et_check_sanity (occ->prev);
+ if (occ->next)
+ et_check_sanity (occ->next);
+}
+
+/* Checks whether tree containing OCC is sane. */
+
+static void
+et_check_tree_sanity (struct et_occ *occ)
+{
+ while (occ->parent)
+ occ = occ->parent;
+
+ et_check_sanity (occ);
+}
+
+/* For recording the paths. */
+
+/* An ad-hoc constant; if the function has more blocks, this won't work,
+ but since it is used for debugging only, it does not matter. */
+#define MAX_NODES 100000
+static int len;
+static void *datas[MAX_NODES];
+static int depths[MAX_NODES];
-static et_forest_occurrence_t splay PARAMS ((et_forest_occurrence_t));
-static void remove_all_occurrences PARAMS ((et_forest_node_t));
-static inline et_forest_occurrence_t find_leftmost_node
- PARAMS ((et_forest_occurrence_t));
-static inline et_forest_occurrence_t find_rightmost_node
- PARAMS ((et_forest_occurrence_t));
-static int calculate_value PARAMS ((et_forest_occurrence_t));
+/* Records the path represented by OCC, with depth incremented by DEPTH. */
-/* Return leftmost node present in the tree roted by OCC. */
-static inline et_forest_occurrence_t
-find_leftmost_node (occ)
- et_forest_occurrence_t occ;
+static int
+record_path_before_1 (struct et_occ *occ, int depth)
{
- while (occ->left)
- occ = occ->left;
+ int mn, m;
+
+ depth += occ->depth;
+ mn = depth;
+
+ if (occ->prev)
+ {
+ m = record_path_before_1 (occ->prev, depth);
+ if (m < mn)
+ mn = m;
+ }
+
+ fprintf (stderr, "%d (%d); ", ((basic_block) occ->of->data)->index, depth);
+
+ gcc_assert (len < MAX_NODES);
- return occ;
+ depths[len] = depth;
+ datas[len] = occ->of;
+ len++;
+
+ if (occ->next)
+ {
+ m = record_path_before_1 (occ->next, depth);
+ if (m < mn)
+ mn = m;
+ }
+
+ gcc_assert (mn == occ->min + depth - occ->depth);
+
+ return mn;
}
-/* Return rightmost node present in the tree roted by OCC. */
-static inline et_forest_occurrence_t
-find_rightmost_node (occ)
- et_forest_occurrence_t occ;
+/* Records the path represented by a tree containing OCC. */
+
+static void
+record_path_before (struct et_occ *occ)
{
- while (occ->right)
- occ = occ->right;
- return occ;
+ while (occ->parent)
+ occ = occ->parent;
+
+ len = 0;
+ record_path_before_1 (occ, 0);
+ fprintf (stderr, "\n");
}
+/* Checks whether the path represented by OCC, with depth incremented by DEPTH,
+ was not changed since the last recording. */
-/* Operation splay for splay tree structure representing ocuurences. */
-static et_forest_occurrence_t
-splay (node)
- et_forest_occurrence_t node;
+static int
+check_path_after_1 (struct et_occ *occ, int depth)
{
- et_forest_occurrence_t parent;
- et_forest_occurrence_t grandparent;
+ int mn, m;
+
+ depth += occ->depth;
+ mn = depth;
- while (1)
+ if (occ->next)
{
- parent = node->parent;
+ m = check_path_after_1 (occ->next, depth);
+ if (m < mn)
+ mn = m;
+ }
- if (! parent)
- return node; /* node == root. */
+ len--;
+ gcc_assert (depths[len] == depth && datas[len] == occ->of);
- grandparent = parent->parent;
+ if (occ->prev)
+ {
+ m = check_path_after_1 (occ->prev, depth);
+ if (m < mn)
+ mn = m;
+ }
+
+ gcc_assert (mn == occ->min + depth - occ->depth);
+
+ return mn;
+}
+
+/* Checks whether the path represented by a tree containing OCC was
+ not changed since the last recording. */
+
+static void
+check_path_after (struct et_occ *occ)
+{
+ while (occ->parent)
+ occ = occ->parent;
+
+ check_path_after_1 (occ, 0);
+ gcc_assert (!len);
+}
+
+#endif
- if (! grandparent)
- break;
+/* Splay the occurrence OCC to the root of the tree. */
- /* Now there are four possible combinations: */
+static void
+et_splay (struct et_occ *occ)
+{
+ struct et_occ *f, *gf, *ggf;
+ int occ_depth, f_depth, gf_depth;
+
+#ifdef DEBUG_ET
+ record_path_before (occ);
+ et_check_tree_sanity (occ);
+#endif
+
+ while (occ->parent)
+ {
+ occ_depth = occ->depth;
+
+ f = occ->parent;
+ f_depth = f->depth;
- if (node == parent->left)
+ gf = f->parent;
+
+ if (!gf)
{
- if (parent == grandparent->left)
+ set_depth_add (occ, f_depth);
+ occ->min_occ = f->min_occ;
+ occ->min = f->min;
+
+ if (f->prev == occ)
{
- et_forest_occurrence_t node1, node2;
- int count1, count2;
-
- node1 = node->right;
- count1 = node->count_right;
- node2 = parent->right;
- count2 = parent->count_right;
-
- grandparent->left = node2;
- grandparent->count_left = count2;
- if (node2)
- node2->parent = grandparent;
- parent->left = node1;
- parent->count_left = count1;
- if (node1)
- node1->parent = parent;
- parent->right = grandparent;
- parent->count_right = count2 + grandparent->count_right + 1;
- node->right = parent;
- node->count_right = count1 + parent->count_right + 1;
-
- node->parent = grandparent->parent;
- parent->parent = node;
- grandparent->parent = parent;
-
- if (node->parent)
- {
- if (node->parent->left == grandparent)
- node->parent->left = node;
- else
- node->parent->right = node;
- }
+ /* zig */
+ set_prev (f, occ->next);
+ set_next (occ, f);
+ set_depth_add (f->prev, occ_depth);
}
else
{
- /* parent == grandparent->right && node == parent->left*/
- et_forest_occurrence_t node1, node2;
- int count1, count2;
-
- node1 = node->left;
- count1 = node->count_left;
- node2 = node->right;
- count2 = node->count_right;
-
- grandparent->right = node1;
- grandparent->count_right = count1;
- if (node1)
- node1->parent = grandparent;
- parent->left = node2;
- parent->count_left = count2;
- if (node2)
- node2->parent = parent;
- node->left = grandparent;
- node->count_left = grandparent->count_left + count1 + 1;
- node->right = parent;
- node->count_right = parent->count_right + count2 + 1;
-
- node->parent = grandparent->parent;
- parent->parent = node;
- grandparent->parent = node;
-
- if (node->parent)
- {
- if (node->parent->left == grandparent)
- node->parent->left = node;
- else
- node->parent->right = node;
- }
+ /* zag */
+ set_next (f, occ->prev);
+ set_prev (occ, f);
+ set_depth_add (f->next, occ_depth);
}
+ set_depth (f, -occ_depth);
+ occ->parent = NULL;
+
+ et_recomp_min (f);
+#ifdef DEBUG_ET
+ et_check_tree_sanity (occ);
+ check_path_after (occ);
+#endif
+ return;
}
- else
+
+ gf_depth = gf->depth;
+
+ set_depth_add (occ, f_depth + gf_depth);
+ occ->min_occ = gf->min_occ;
+ occ->min = gf->min;
+
+ ggf = gf->parent;
+
+ if (gf->prev == f)
{
- /* node == parent->right. */
- if (parent == grandparent->left)
+ if (f->prev == occ)
{
- et_forest_occurrence_t node1, node2;
- int count1, count2;
-
- node1 = node->left;
- count1 = node->count_left;
- node2 = node->right;
- count2 = node->count_right;
-
- parent->right = node1;
- parent->count_right = count1;
- if (node1)
- node1->parent = parent;
- grandparent->left = node2;
- grandparent->count_left = count2;
- if (node2)
- node2->parent = grandparent;
- node->left = parent;
- node->count_left = parent->count_left + count1 + 1;
- node->right = grandparent;
- node->count_right = grandparent->count_right + count2 + 1;
-
- node->parent = grandparent->parent;
- parent->parent = node;
- grandparent->parent = node;
-
- if (node->parent)
- {
- if (node->parent->left == grandparent)
- node->parent->left = node;
- else
- node->parent->right = node;
- }
+ /* zig zig */
+ set_prev (gf, f->next);
+ set_prev (f, occ->next);
+ set_next (occ, f);
+ set_next (f, gf);
+
+ set_depth (f, -occ_depth);
+ set_depth_add (f->prev, occ_depth);
+ set_depth (gf, -f_depth);
+ set_depth_add (gf->prev, f_depth);
}
else
{
- /* parent == grandparent->right && node == parent->right*/
- et_forest_occurrence_t node1, node2;
- int count1, count2;
-
- node1 = node->left;
- count1 = node->count_left;
- node2 = parent->left;
- count2 = parent->count_left;
-
- grandparent->right = node2;
- grandparent->count_right = count2;
- if (node2)
- node2->parent = grandparent;
- parent->right = node1;
- parent->count_right = count1;
- if (node1)
- node1->parent = parent;
- parent->left = grandparent;
- parent->count_left = count2 + grandparent->count_left + 1;
- node->left = parent;
- node->count_left = count1 + parent->count_left + 1;
-
- node->parent = grandparent->parent;
- parent->parent = node;
- grandparent->parent = parent;
-
- if (node->parent)
- {
- if (node->parent->left == grandparent)
- node->parent->left = node;
- else
- node->parent->right = node;
- }
+ /* zag zig */
+ set_prev (gf, occ->next);
+ set_next (f, occ->prev);
+ set_prev (occ, f);
+ set_next (occ, gf);
+
+ set_depth (f, -occ_depth);
+ set_depth_add (f->next, occ_depth);
+ set_depth (gf, -occ_depth - f_depth);
+ set_depth_add (gf->prev, occ_depth + f_depth);
}
}
-
- }
-
- /* parent == root. */
- /* There are two possible combinations: */
-
- if (node == parent->left)
- {
- et_forest_occurrence_t node1;
- int count1;
-
- node1 = node->right;
- count1 = node->count_right;
-
- parent->left = node1;
- parent->count_left = count1;
- if (node1)
- node1->parent = parent;
- node->right = parent;
- node->count_right = parent->count_right + 1 + count1;
- node->parent = parent->parent; /* the same as = 0; */
- parent->parent = node;
-
- if (node->parent)
+ else
{
- if (node->parent->left == parent)
- node->parent->left = node;
+ if (f->prev == occ)
+ {
+ /* zig zag */
+ set_next (gf, occ->prev);
+ set_prev (f, occ->next);
+ set_prev (occ, gf);
+ set_next (occ, f);
+
+ set_depth (f, -occ_depth);
+ set_depth_add (f->prev, occ_depth);
+ set_depth (gf, -occ_depth - f_depth);
+ set_depth_add (gf->next, occ_depth + f_depth);
+ }
else
- node->parent->right = node;
+ {
+ /* zag zag */
+ set_next (gf, f->prev);
+ set_next (f, occ->prev);
+ set_prev (occ, f);
+ set_prev (f, gf);
+
+ set_depth (f, -occ_depth);
+ set_depth_add (f->next, occ_depth);
+ set_depth (gf, -f_depth);
+ set_depth_add (gf->next, f_depth);
+ }
}
- }
- else
- {
- /* node == parent->right. */
- et_forest_occurrence_t node1;
- int count1;
-
- node1 = node->left;
- count1 = node->count_left;
-
- parent->right = node1;
- parent->count_right = count1;
- if (node1)
- node1->parent = parent;
- node->left = parent;
- node->count_left = parent->count_left + 1 + count1;
- node->parent = parent->parent; /* the same as = 0; */
- parent->parent = node;
-
- if (node->parent)
+
+ occ->parent = ggf;
+ if (ggf)
{
- if (node->parent->left == parent)
- node->parent->left = node;
+ if (ggf->prev == gf)
+ ggf->prev = occ;
else
- node->parent->right = node;
+ ggf->next = occ;
}
+
+ et_recomp_min (gf);
+ et_recomp_min (f);
+#ifdef DEBUG_ET
+ et_check_tree_sanity (occ);
+#endif
}
- return node;
+#ifdef DEBUG_ET
+ et_check_sanity (occ);
+ check_path_after (occ);
+#endif
}
-/* Remove all occurences of the given node before destroying the node. */
-static void
-remove_all_occurrences (forest_node)
- et_forest_node_t forest_node;
+/* Create a new et tree occurrence of NODE. */
+
+static struct et_occ *
+et_new_occ (struct et_node *node)
{
- et_forest_occurrence_t first = forest_node->first;
- et_forest_occurrence_t last = forest_node->last;
- et_forest_occurrence_t node;
+ struct et_occ *nw;
- splay (first);
+ if (!et_occurrences)
+ et_occurrences = create_alloc_pool ("et_occ pool", sizeof (struct et_occ), 300);
+ nw = (struct et_occ *) pool_alloc (et_occurrences);
- if (first->left)
- first->left->parent = 0;
- if (first->right)
- first->right->parent = 0;
+ nw->of = node;
+ nw->parent = NULL;
+ nw->prev = NULL;
+ nw->next = NULL;
- if (last != first)
- {
- splay (last);
+ nw->depth = 0;
+ nw->min_occ = nw;
+ nw->min = 0;
- if (last->left)
- last->left->parent = 0;
- if (last->right)
- last->right->parent = 0;
- }
-
- if (last->right && first->left) /* actually, first->left would suffice. */
- {
- /* Need to join them. */
- et_forest_occurrence_t prev_node, next_node;
-
- prev_node = splay (find_rightmost_node (first->left));
- next_node = splay (find_leftmost_node (last->right));
- /* prev_node and next_node are consecutive occurencies
- of the same node. */
- if (prev_node->next != next_node)
- abort ();
-
- prev_node->right = next_node->right;
- prev_node->count_right = next_node->count_right;
- prev_node->next = next_node->next;
- if (prev_node->right)
- prev_node->right->parent = prev_node;
-
- if (prev_node->node->last == next_node)
- prev_node->node->last = prev_node;
-
- free (next_node);
- }
+ return nw;
+}
- if (first != last)
- {
- node = first->next;
+/* Create a new et tree containing DATA. */
- while (node != last)
- {
- et_forest_occurrence_t next_node;
+struct et_node *
+et_new_tree (void *data)
+{
+ struct et_node *nw;
- splay (node);
+ if (!et_nodes)
+ et_nodes = create_alloc_pool ("et_node pool", sizeof (struct et_node), 300);
+ nw = (struct et_node *) pool_alloc (et_nodes);
- if (node->left)
- node->left->parent = 0;
- if (node->right)
- node->right->parent = 0;
+ nw->data = data;
+ nw->father = NULL;
+ nw->left = NULL;
+ nw->right = NULL;
+ nw->son = NULL;
- next_node = node->next;
- free (node);
- node = next_node;
- }
- }
+ nw->rightmost_occ = et_new_occ (nw);
+ nw->parent_occ = NULL;
- free (first);
- if (first != last)
- free (last);
+ return nw;
}
-/* Calculate ET value of the given node. */
-static inline int
-calculate_value (node)
- et_forest_occurrence_t node;
+/* Releases et tree T. */
+
+void
+et_free_tree (struct et_node *t)
{
- int value = node->count_left;
+ while (t->son)
+ et_split (t->son);
- while (node->parent)
- {
- if (node == node->parent->right)
- value += node->parent->count_left + 1;
+ if (t->father)
+ et_split (t);
- node = node->parent;
- }
+ pool_free (et_occurrences, t->rightmost_occ);
+ pool_free (et_nodes, t);
+}
- return value;
+/* Releases et tree T without maintaining other nodes. */
+
+void
+et_free_tree_force (struct et_node *t)
+{
+ pool_free (et_occurrences, t->rightmost_occ);
+ if (t->parent_occ)
+ pool_free (et_occurrences, t->parent_occ);
+ pool_free (et_nodes, t);
}
+/* Release the alloc pools, if they are empty. */
+void
+et_free_pools (void)
+{
+ free_alloc_pool_if_empty (&et_occurrences);
+ free_alloc_pool_if_empty (&et_nodes);
+}
+/* Sets father of et tree T to FATHER. */
-/* Create ET-forest structure. */
-et_forest_t
-et_forest_create ()
+void
+et_set_father (struct et_node *t, struct et_node *father)
{
+ struct et_node *left, *right;
+ struct et_occ *rmost, *left_part, *new_f_occ, *p;
- et_forest_t forest = xmalloc (sizeof (struct et_forest));
+ /* Update the path represented in the splay tree. */
+ new_f_occ = et_new_occ (father);
- forest->nnodes = 0;
- return forest;
-}
+ rmost = father->rightmost_occ;
+ et_splay (rmost);
+ left_part = rmost->prev;
+ p = t->rightmost_occ;
+ et_splay (p);
-/* Deallocate the structure. */
-void
-et_forest_delete (forest)
- et_forest_t forest;
-{
- if (forest->nnodes)
- abort ();
+ set_prev (new_f_occ, left_part);
+ set_next (new_f_occ, p);
- free (forest);
-}
+ p->depth++;
+ p->min++;
+ et_recomp_min (new_f_occ);
-/* Create new node with VALUE and return the edge.
- Return NULL when memory allocation failed. */
-et_forest_node_t
-et_forest_add_node (forest, value)
- et_forest_t forest;
- void *value;
-{
- /* Create node with one occurrence. */
- et_forest_node_t node;
- et_forest_occurrence_t occ;
-
- node = xmalloc (sizeof (struct et_forest_node));
- occ = xmalloc (sizeof (struct et_forest_occurrence));
-
- node->first = node->last = occ;
- node->value = value;
- forest->nnodes++;
-
- occ->node = node;
- occ->left = occ->right = occ->parent = 0;
- occ->next = 0;
- occ->count_left = occ->count_right = 0;
- return node;
-}
+ set_prev (rmost, new_f_occ);
-/* Add new edge to the tree, return 1 if succesfull.
- 0 indicates that creation of the edge will close the cycle in graph. */
-int
-et_forest_add_edge (forest, parent_node, child_node)
- et_forest_t forest ATTRIBUTE_UNUSED;
- et_forest_node_t parent_node;
- et_forest_node_t child_node;
-{
- et_forest_occurrence_t new_occ, parent_occ, child_occ;
-
- if (! parent_node || ! child_node)
- abort ();
-
- parent_occ = parent_node->first;
- child_occ = child_node->first;
-
- splay (parent_occ);
- splay (child_occ);
-
- if (parent_occ->parent)
- return 0; /* Both child and parent are in the same tree. */
-
- if (child_occ->left)
- abort (); /* child must be root of its containing tree. */
-
- new_occ = xmalloc (sizeof (struct et_forest_occurrence));
-
- new_occ->node = parent_node;
- new_occ->left = child_occ;
- new_occ->count_left = child_occ->count_right + 1; /* count_left is 0. */
- new_occ->right = parent_occ->right;
- new_occ->count_right = parent_occ->count_right;
- new_occ->parent = parent_occ;
- new_occ->next = parent_occ->next;
- child_occ->parent = new_occ;
- parent_occ->right = new_occ;
- parent_occ->count_right = new_occ->count_left + new_occ->count_right + 1;
- parent_occ->next = new_occ;
- if (new_occ->right)
- new_occ->right->parent = new_occ;
-
- if (parent_node->last == parent_occ)
- parent_node->last = new_occ;
- return 1;
+ if (new_f_occ->min + rmost->depth < rmost->min)
+ {
+ rmost->min = new_f_occ->min + rmost->depth;
+ rmost->min_occ = new_f_occ->min_occ;
+ }
+
+ t->parent_occ = new_f_occ;
+
+ /* Update the tree. */
+ t->father = father;
+ right = father->son;
+ if (right)
+ left = right->left;
+ else
+ left = right = t;
+
+ left->right = t;
+ right->left = t;
+ t->left = left;
+ t->right = right;
+
+ father->son = t;
+
+#ifdef DEBUG_ET
+ et_check_tree_sanity (rmost);
+ record_path_before (rmost);
+#endif
}
-/* Remove NODE from the tree and all connected edges. */
+/* Splits the edge from T to its father. */
+
void
-et_forest_remove_node (forest, node)
- et_forest_t forest;
- et_forest_node_t node;
+et_split (struct et_node *t)
{
- remove_all_occurrences (node);
- forest->nnodes--;
+ struct et_node *father = t->father;
+ struct et_occ *r, *l, *rmost, *p_occ;
- free (node);
-}
+ /* Update the path represented by the splay tree. */
+ rmost = t->rightmost_occ;
+ et_splay (rmost);
-/* Remove edge from the tree, return 1 if sucesfull,
- 0 indicates nonexisting edge. */
-int
-et_forest_remove_edge (forest, parent_node, child_node)
- et_forest_t forest ATTRIBUTE_UNUSED;
- et_forest_node_t parent_node;
- et_forest_node_t child_node;
-{
- et_forest_occurrence_t parent_pre_occ, parent_post_occ;
+ for (r = rmost->next; r->prev; r = r->prev)
+ continue;
+ et_splay (r);
- splay (child_node->first);
+ r->prev->parent = NULL;
+ p_occ = t->parent_occ;
+ et_splay (p_occ);
+ t->parent_occ = NULL;
- if (! child_node->first->left)
- return 0;
+ l = p_occ->prev;
+ p_occ->next->parent = NULL;
- parent_pre_occ = find_rightmost_node (child_node->first->left);
- if (parent_pre_occ->node != parent_node)
- abort ();
+ set_prev (r, l);
- splay (parent_pre_occ);
- parent_pre_occ->right->parent = 0;
-
- parent_post_occ = parent_pre_occ->next;
- splay (parent_post_occ);
+ et_recomp_min (r);
- parent_post_occ->left->parent = 0;
+ et_splay (rmost);
+ rmost->depth = 0;
+ rmost->min = 0;
- parent_pre_occ->right = parent_post_occ->right;
- parent_pre_occ->count_right = parent_post_occ->count_right;
- if (parent_post_occ->right)
- parent_post_occ->right->parent = parent_pre_occ;
+ pool_free (et_occurrences, p_occ);
- parent_pre_occ->next = parent_post_occ->next;
+ /* Update the tree. */
+ if (father->son == t)
+ father->son = t->right;
+ if (father->son == t)
+ father->son = NULL;
+ else
+ {
+ t->left->right = t->right;
+ t->right->left = t->left;
+ }
+ t->left = t->right = NULL;
+ t->father = NULL;
- if (parent_post_occ == parent_node->last)
- parent_node->last = parent_pre_occ;
+#ifdef DEBUG_ET
+ et_check_tree_sanity (rmost);
+ record_path_before (rmost);
- free (parent_post_occ);
- return 1;
+ et_check_tree_sanity (r);
+ record_path_before (r);
+#endif
}
-/* Return the parent of the NODE if any, NULL otherwise. */
-et_forest_node_t
-et_forest_parent (forest, node)
- et_forest_t forest ATTRIBUTE_UNUSED;
- et_forest_node_t node;
+/* Finds the nearest common ancestor of the nodes N1 and N2. */
+
+struct et_node *
+et_nca (struct et_node *n1, struct et_node *n2)
{
- splay (node->first);
+ struct et_occ *o1 = n1->rightmost_occ, *o2 = n2->rightmost_occ, *om;
+ struct et_occ *l, *r, *ret;
+ int mn;
+
+ if (n1 == n2)
+ return n1;
+
+ et_splay (o1);
+ l = o1->prev;
+ r = o1->next;
+ if (l)
+ l->parent = NULL;
+ if (r)
+ r->parent = NULL;
+ et_splay (o2);
+
+ if (l == o2 || (l && l->parent != NULL))
+ {
+ ret = o2->next;
+
+ set_prev (o1, o2);
+ if (r)
+ r->parent = o1;
+ }
+ else
+ {
+ ret = o2->prev;
+
+ set_next (o1, o2);
+ if (l)
+ l->parent = o1;
+ }
- if (node->first->left)
- return find_rightmost_node (node->first->left)->node;
+ if (0 < o2->depth)
+ {
+ om = o1;
+ mn = o1->depth;
+ }
else
- return 0;
+ {
+ om = o2;
+ mn = o2->depth + o1->depth;
+ }
+
+#ifdef DEBUG_ET
+ et_check_tree_sanity (o2);
+#endif
+
+ if (ret && ret->min + o1->depth + o2->depth < mn)
+ return ret->min_occ->of;
+ else
+ return om->of;
}
+/* Checks whether the node UP is an ancestor of the node DOWN. */
-/* Return nearest common ancestor of NODE1 and NODE2.
- Return NULL of they are in different trees. */
-et_forest_node_t
-et_forest_common_ancestor (forest, node1, node2)
- et_forest_t forest ATTRIBUTE_UNUSED;
- et_forest_node_t node1;
- et_forest_node_t node2;
+bool
+et_below (struct et_node *down, struct et_node *up)
{
- int value1, value2, max_value;
- et_forest_node_t ancestor;
+ struct et_occ *u = up->rightmost_occ, *d = down->rightmost_occ;
+ struct et_occ *l, *r;
+
+ if (up == down)
+ return true;
+
+ et_splay (u);
+ l = u->prev;
+ r = u->next;
- if (node1 == node2)
- return node1;
-
- if (! node1 || ! node2)
- abort ();
+ if (!l)
+ return false;
- splay (node1->first);
- splay (node2->first);
+ l->parent = NULL;
- if (! node1->first->parent) /* The two vertices are in different trees. */
- return 0;
+ if (r)
+ r->parent = NULL;
- value2 = calculate_value (node2->first);
- value1 = calculate_value (node1->first);
+ et_splay (d);
- if (value1 < value2)
+ if (l == d || l->parent != NULL)
{
- ancestor = node1;
- max_value = value2;
+ if (r)
+ r->parent = u;
+ set_prev (u, d);
+#ifdef DEBUG_ET
+ et_check_tree_sanity (u);
+#endif
}
else
{
- ancestor = node2;
- max_value = value1;
- }
-
- while (calculate_value (ancestor->last) < max_value)
- {
- /* Find parent node. */
- splay (ancestor->first);
- ancestor = find_rightmost_node (ancestor->first->left) ->node;
+ l->parent = u;
+
+ /* In case O1 and O2 are in two different trees, we must just restore the
+ original state. */
+ if (r && r->parent != NULL)
+ set_next (u, d);
+ else
+ set_next (u, r);
+
+#ifdef DEBUG_ET
+ et_check_tree_sanity (u);
+#endif
+ return false;
}
- return ancestor;
-}
+ if (0 >= d->depth)
+ return false;
-/* Return the value pointer of node set during it's creation. */
-void *
-et_forest_node_value (forest, node)
- et_forest_t forest ATTRIBUTE_UNUSED;
- et_forest_node_t node;
-{
- /* Alloc threading NULL as a special node of the forest. */
- if (!node)
- return NULL;
- return node->value;
+ return !d->next || d->next->min + d->depth >= 0;
}
-/* Find all sons of NODE and store them into ARRAY allocated by the caller.
- Return number of nodes found. */
-int
-et_forest_enumerate_sons (forest, node, array)
- et_forest_t forest ATTRIBUTE_UNUSED;
- et_forest_node_t node;
- et_forest_node_t *array;
+/* Returns the root of the tree that contains NODE. */
+
+struct et_node *
+et_root (struct et_node *node)
{
- int n = 0;
- et_forest_occurrence_t occ = node->first, stop = node->last, occ1;
+ struct et_occ *occ = node->rightmost_occ, *r;
- /* Parent is the rightmost node of the left successor.
- Look for all occurences having no right succesor
- and lookup the sons. */
- while (occ != stop)
- {
- splay (occ);
- if (occ->right)
- {
- occ1 = find_leftmost_node (occ->right);
- if (occ1->node->first == occ1)
- array[n++] = occ1->node;
- }
- occ = occ->next;
- }
- return n;
+ /* The root of the tree corresponds to the rightmost occurrence in the
+ represented path. */
+ et_splay (occ);
+ for (r = occ; r->next; r = r->next)
+ continue;
+ et_splay (r);
+
+ return r->of;
}
OSDN Git Service
