diff options
author | Andreas Jaeger <aj@suse.de> | 2003-06-29 18:21:58 +0200 |
---|---|---|
committer | Andreas Jaeger <aj@gcc.gnu.org> | 2003-06-29 18:21:58 +0200 |
commit | 502b832280c67d89300d92b91e73a9d3093db4a8 (patch) | |
tree | d12a59c660881801d6279dba52e7bd166ec393fb /gcc/et-forest.c | |
parent | 7080f7359418d87feb8ec8dfacf327d32b5a070c (diff) | |
download | gcc-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.c | 105 |
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; |