aboutsummaryrefslogtreecommitdiff
path: root/gcc/et-forest.c
diff options
context:
space:
mode:
authorAndreas Jaeger <aj@suse.de>2003-06-29 18:21:58 +0200
committerAndreas Jaeger <aj@gcc.gnu.org>2003-06-29 18:21:58 +0200
commit502b832280c67d89300d92b91e73a9d3093db4a8 (patch)
treed12a59c660881801d6279dba52e7bd166ec393fb /gcc/et-forest.c
parent7080f7359418d87feb8ec8dfacf327d32b5a070c (diff)
downloadgcc-502b832280c67d89300d92b91e73a9d3093db4a8.zip
gcc-502b832280c67d89300d92b91e73a9d3093db4a8.tar.gz
gcc-502b832280c67d89300d92b91e73a9d3093db4a8.tar.bz2
except.c: Convert prototypes to ISO C90.
* except.c: Convert prototypes to ISO C90. * except.h: Likewise. * emit-rtl.c: Likewise. * et-forest.c: Likewise. * et-forest.h: Likewise. * except.c: Likewise. * explow.c: Likewise. * expmed.c: Likewise. * expr.c: Likewise. * expr.h: Likewise. From-SVN: r68674
Diffstat (limited to 'gcc/et-forest.c')
-rw-r--r--gcc/et-forest.c105
1 files changed, 42 insertions, 63 deletions
diff --git a/gcc/et-forest.c b/gcc/et-forest.c
index 1a9d5a3..1d5cd26 100644
--- a/gcc/et-forest.c
+++ b/gcc/et-forest.c
@@ -1,6 +1,6 @@
/* ET-trees datastructure implementation.
Contributed by Pavel Nejedly
- Copyright (C) 2002 Free Software Foundation, Inc.
+ Copyright (C) 2002, 2003 Free Software Foundation, Inc.
This file is part of the libiberty library.
Libiberty is free software; you can redistribute it and/or
@@ -16,7 +16,7 @@ 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.
+Boston, MA 02111-1307, USA.
The ET-forest structure is described in:
D. D. Sleator and R. E. Tarjan. A data structure for dynamic trees.
@@ -42,7 +42,7 @@ struct et_forest
alloc_pool occur_pool;
};
-/* Single occurrence of node in ET-forest.
+/* Single occurrence of node in ET-forest.
A single node may have multiple occurrences.
*/
struct et_forest_occurrence
@@ -75,18 +75,17 @@ struct et_forest_node
};
-static et_forest_occurrence_t splay PARAMS ((et_forest_occurrence_t));
-static void remove_all_occurrences PARAMS ((et_forest_t, 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));
+static et_forest_occurrence_t splay (et_forest_occurrence_t);
+static void remove_all_occurrences (et_forest_t, et_forest_node_t);
+static inline et_forest_occurrence_t find_leftmost_node
+ (et_forest_occurrence_t);
+static inline et_forest_occurrence_t find_rightmost_node
+ (et_forest_occurrence_t);
+static int calculate_value (et_forest_occurrence_t);
/* 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;
+find_leftmost_node (et_forest_occurrence_t occ)
{
while (occ->left)
occ = occ->left;
@@ -96,8 +95,7 @@ find_leftmost_node (occ)
/* 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;
+find_rightmost_node (et_forest_occurrence_t occ)
{
while (occ->right)
occ = occ->right;
@@ -107,8 +105,7 @@ find_rightmost_node (occ)
/* Operation splay for splay tree structure representing occurrences. */
static et_forest_occurrence_t
-splay (node)
- et_forest_occurrence_t node;
+splay (et_forest_occurrence_t node)
{
et_forest_occurrence_t parent;
et_forest_occurrence_t grandparent;
@@ -276,7 +273,7 @@ splay (node)
}
}
}
-
+
}
/* parent == root. */
@@ -286,7 +283,7 @@ splay (node)
{
et_forest_occurrence_t node1;
int count1;
-
+
node1 = node->right;
count1 = node->count_right;
@@ -306,13 +303,13 @@ splay (node)
else
node->parent->right = node;
}
- }
- else
+ }
+ else
{
/* node == parent->right. */
et_forest_occurrence_t node1;
int count1;
-
+
node1 = node->left;
count1 = node->count_left;
@@ -339,9 +336,7 @@ splay (node)
/* Remove all occurrences of the given node before destroying the node. */
static void
-remove_all_occurrences (forest, forest_node)
- et_forest_t forest;
- et_forest_node_t forest_node;
+remove_all_occurrences (et_forest_t forest, et_forest_node_t forest_node)
{
et_forest_occurrence_t first = forest_node->first;
et_forest_occurrence_t last = forest_node->last;
@@ -352,7 +347,7 @@ remove_all_occurrences (forest, forest_node)
if (first->left)
first->left->parent = 0;
if (first->right)
- first->right->parent = 0;
+ first->right->parent = 0;
if (last != first)
{
@@ -416,8 +411,7 @@ remove_all_occurrences (forest, forest_node)
/* Calculate ET value of the given node. */
static inline int
-calculate_value (node)
- et_forest_occurrence_t node;
+calculate_value (et_forest_occurrence_t node)
{
int value = node->count_left;
@@ -437,7 +431,7 @@ calculate_value (node)
/* Create ET-forest structure. */
et_forest_t
-et_forest_create ()
+et_forest_create (void)
{
et_forest_t forest = xmalloc (sizeof (struct et_forest));
@@ -450,9 +444,8 @@ et_forest_create ()
/* Deallocate the structure. */
-void
-et_forest_delete (forest)
- et_forest_t forest;
+void
+et_forest_delete (et_forest_t forest)
{
if (forest->nnodes)
abort ();
@@ -464,9 +457,7 @@ et_forest_delete (forest)
/* 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;
+et_forest_add_node (et_forest_t forest, void *value)
{
/* Create node with one occurrence. */
et_forest_node_t node;
@@ -489,10 +480,8 @@ et_forest_add_node (forest, value)
/* Add new edge to the tree, return 1 if successful.
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_add_edge (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;
@@ -510,7 +499,7 @@ et_forest_add_edge (forest, parent_node, child_node)
if (child_occ->left)
abort (); /* child must be root of its containing tree. */
-
+
new_occ = pool_alloc (forest->occur_pool);
new_occ->node = parent_node;
@@ -534,9 +523,7 @@ et_forest_add_edge (forest, parent_node, child_node)
/* Remove NODE from the tree and all connected edges. */
void
-et_forest_remove_node (forest, node)
- et_forest_t forest;
- et_forest_node_t node;
+et_forest_remove_node (et_forest_t forest, et_forest_node_t node)
{
remove_all_occurrences (forest, node);
forest->nnodes--;
@@ -547,10 +534,9 @@ et_forest_remove_node (forest, node)
/* Remove edge from the tree, return 1 if successful,
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_remove_edge (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;
@@ -565,7 +551,7 @@ et_forest_remove_edge (forest, parent_node, child_node)
splay (parent_pre_occ);
parent_pre_occ->right->parent = 0;
-
+
parent_post_occ = parent_pre_occ->next;
splay (parent_post_occ);
@@ -587,9 +573,7 @@ et_forest_remove_edge (forest, parent_node, child_node)
/* 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;
+et_forest_parent (et_forest_t forest ATTRIBUTE_UNUSED, et_forest_node_t node)
{
splay (node->first);
@@ -603,17 +587,15 @@ et_forest_parent (forest, node)
/* 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;
+et_forest_common_ancestor (et_forest_t forest ATTRIBUTE_UNUSED,
+ et_forest_node_t node1, et_forest_node_t node2)
{
int value1, value2, max_value;
et_forest_node_t ancestor;
if (node1 == node2)
return node1;
-
+
if (! node1 || ! node2)
abort ();
@@ -636,7 +618,7 @@ et_forest_common_ancestor (forest, node1, node2)
ancestor = node2;
max_value = value1;
}
-
+
while (calculate_value (ancestor->last) < max_value)
{
/* Find parent node. */
@@ -649,9 +631,8 @@ et_forest_common_ancestor (forest, node1, node2)
/* 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;
+et_forest_node_value (et_forest_t forest ATTRIBUTE_UNUSED,
+ et_forest_node_t node)
{
/* Alloc threading NULL as a special node of the forest. */
if (!node)
@@ -662,10 +643,8 @@ et_forest_node_value (forest, node)
/* 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;
+et_forest_enumerate_sons (et_forest_t forest ATTRIBUTE_UNUSED,
+ et_forest_node_t node, et_forest_node_t *array)
{
int n = 0;
et_forest_occurrence_t occ = node->first, stop = node->last, occ1;