/* ET-trees data structure implementation.
Contributed by Pavel Nejedly
- Copyright (C) 2002, 2003, 2004 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.
set_prev (struct et_occ *occ, struct et_occ *t)
{
#ifdef DEBUG_ET
- if (occ == t)
- abort ();
+ gcc_assert (occ != t);
#endif
occ->prev = t;
set_next (struct et_occ *occ, struct et_occ *t)
{
#ifdef DEBUG_ET
- if (occ == t)
- abort ();
+ gcc_assert (occ != t);
#endif
occ->next = t;
}
#ifdef DEBUG_ET
-/* Checks whether neighbourhood of OCC seems sane. */
+/* Checks whether neighborhood of OCC seems sane. */
static void
et_check_occ_sanity (struct et_occ *occ)
if (!occ)
return;
- if (occ->parent == occ)
- abort ();
-
- if (occ->prev == occ)
- abort ();
-
- if (occ->next == occ)
- abort ();
-
- if (occ->next && occ->next == occ->prev)
- abort ();
+ 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)
{
- if (occ->next == occ->parent)
- abort ();
-
- if (occ->next->parent != occ)
- abort ();
+ gcc_assert (occ->next != occ->parent);
+ gcc_assert (occ->next->parent == occ);
}
if (occ->prev)
{
- if (occ->prev == occ->parent)
- abort ();
-
- if (occ->prev->parent != occ)
- abort ();
+ gcc_assert (occ->prev != occ->parent);
+ gcc_assert (occ->prev->parent == occ);
}
- if (occ->parent
- && occ->parent->prev != occ
- && occ->parent->next != occ)
- abort ();
+ gcc_assert (!occ->parent
+ || occ->parent->prev == occ
+ || occ->parent->next == occ);
}
/* Checks whether tree rooted at OCC is sane. */
fprintf (stderr, "%d (%d); ", ((basic_block) occ->of->data)->index, depth);
- if (len >= MAX_NODES)
- abort ();
+ gcc_assert (len < MAX_NODES);
depths[len] = depth;
datas[len] = occ->of;
mn = m;
}
- if (mn != occ->min + depth - occ->depth)
- abort ();
+ gcc_assert (mn == occ->min + depth - occ->depth);
return mn;
}
}
len--;
- if (depths[len] != depth
- || datas[len] != occ->of)
- abort ();
+ gcc_assert (depths[len] == depth && datas[len] == occ->of);
if (occ->prev)
{
mn = m;
}
- if (mn != occ->min + depth - occ->depth)
- abort ();
+ gcc_assert (mn == occ->min + depth - occ->depth);
return mn;
}
occ = occ->parent;
check_path_after_1 (occ, 0);
- if (len != 0)
- abort ();
+ gcc_assert (!len);
}
#endif
if (!et_occurrences)
et_occurrences = create_alloc_pool ("et_occ pool", sizeof (struct et_occ), 300);
- nw = pool_alloc (et_occurrences);
+ nw = (struct et_occ *) pool_alloc (et_occurrences);
nw->of = node;
nw->parent = NULL;
if (!et_nodes)
et_nodes = create_alloc_pool ("et_node pool", sizeof (struct et_node), 300);
- nw = pool_alloc (et_nodes);
+ nw = (struct et_node *) pool_alloc (et_nodes);
nw->data = data;
nw->father = NULL;
pool_free (et_nodes, t);
}
+/* 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. */
void
return !d->next || d->next->min + d->depth >= 0;
}
+
+/* Returns the root of the tree that contains NODE. */
+
+struct et_node *
+et_root (struct et_node *node)
+{
+ struct et_occ *occ = node->rightmost_occ, *r;
+
+ /* 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;
+}