Gcc 3.3.1-pre as of 2003-07-11.

1 files changed, 680 insertions, 0 deletions

diff --git a/contrib/gcc/et-forest.c b/contrib/gcc/et-forest.c
new file mode 100644
index 0000000..84594d4
--- /dev/null
+++ b/contrib/gcc/et-forest.c
@@ -0,0 +1,680 @@
+/* ET-trees datastructure implementation.
+   Contributed by Pavel Nejedly
+   Copyright (C) 2002 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.
+
+Libiberty is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+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.  
+
+  The ET-forest structure is described in:
+    D. D. Sleator and R. E. Tarjan. A data structure for dynamic trees.
+    J.  G'omput. System Sci., 26(3):362 381, 1983.
+*/
+
+#include "config.h"
+#include "system.h"
+#include "et-forest.h"
+
+struct et_forest_occurrence;
+typedef struct et_forest_occurrence* et_forest_occurrence_t;
+
+/* The ET-forest type.  */
+struct et_forest
+{
+  /* Linked list of nodes is used to destroy the structure.  */
+  int nnodes;
+};
+
+/* Single occurrence of node in ET-forest.  
+   A single node may have multiple occurrences.
+ */
+struct et_forest_occurrence
+{
+  /* Parent in the splay-tree.  */
+  et_forest_occurrence_t parent;
+
+  /* Children in the splay-tree.  */
+  et_forest_occurrence_t left, right;
+
+  /* Counts of vertices in the two splay-subtrees.  */
+  int count_left, count_right;
+
+  /* Next occurrence of this node in the sequence.  */
+  et_forest_occurrence_t next;
+
+  /* The node, which this occurrence is of.  */
+  et_forest_node_t node;
+};
+
+
+/* ET-forest node.  */
+struct et_forest_node
+{
+  et_forest_t forest;
+  void *value;
+
+  /* First and last occurrence of this node in the sequence.  */
+  et_forest_occurrence_t first, last;
+};
+
+
+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));
+
+/* 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;
+{
+  while (occ->left)
+    occ = occ->left;
+
+  return 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;
+{
+  while (occ->right)
+    occ = occ->right;
+  return occ;
+}
+
+
+/* Operation splay for splay tree structure representing ocuurences.  */
+static et_forest_occurrence_t
+splay (node)
+     et_forest_occurrence_t node;
+{
+  et_forest_occurrence_t parent;
+  et_forest_occurrence_t grandparent;
+
+  while (1)
+    {
+      parent = node->parent;
+
+      if (! parent)
+	return node;  /* node == root.  */
+
+      grandparent = parent->parent;
+
+      if (! grandparent)
+	break;
+
+      /* Now there are four possible combinations:  */
+
+      if (node == parent->left)
+	{
+	  if (parent == grandparent->left)
+	    {
+	      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;
+		}
+	    }
+	  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;
+		}
+	    }
+	}
+      else
+	{
+	  /* node == parent->right.  */
+	  if (parent == grandparent->left)
+	    {
+	      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;
+		}
+	    }
+	  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;
+		}
+	    }
+	}
+	  
+    }
+
+  /* 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)
+	{
+	  if (node->parent->left == parent)
+	    node->parent->left = node;
+	  else
+	    node->parent->right = node;
+	}
+    } 
+  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)
+	{
+	  if (node->parent->left == parent)
+	    node->parent->left = node;
+	  else
+	    node->parent->right = node;
+	}
+    }
+
+  return node;
+}
+
+/* Remove all occurences of the given node before destroying the node.  */
+static void
+remove_all_occurrences (forest_node)
+     et_forest_node_t forest_node;
+{
+  et_forest_occurrence_t first = forest_node->first;
+  et_forest_occurrence_t last = forest_node->last;
+  et_forest_occurrence_t node;
+
+  splay (first);
+
+  if (first->left)
+    first->left->parent = 0;
+  if (first->right)
+    first->right->parent = 0;   
+
+  if (last != first)
+    {
+      splay (last);
+
+      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);
+    }
+
+  if (first != last)
+    {
+      node = first->next;
+
+      while (node != last)
+	{
+	  et_forest_occurrence_t next_node;
+
+	  splay (node);
+
+	  if (node->left)
+	    node->left->parent = 0;
+	  if (node->right)
+	    node->right->parent = 0;
+
+	  next_node = node->next;
+	  free (node);
+	  node = next_node;
+	}
+    }
+
+  free (first);
+  if (first != last)
+    free (last);
+}
+
+/* Calculate ET value of the given node.  */
+static inline int
+calculate_value (node)
+     et_forest_occurrence_t node;
+{
+  int value = node->count_left;
+
+  while (node->parent)
+    {
+      if (node == node->parent->right)
+	value += node->parent->count_left + 1;
+
+      node = node->parent;
+    }
+
+  return value;
+}
+
+
+
+
+/* Create ET-forest structure.  */
+et_forest_t
+et_forest_create ()
+{
+
+  et_forest_t forest = xmalloc (sizeof (struct et_forest));
+
+  forest->nnodes = 0;
+  return forest;
+}
+
+
+
+/* Deallocate the structure.  */
+void 
+et_forest_delete (forest)
+     et_forest_t forest;
+{
+  if (forest->nnodes)
+    abort ();
+
+  free (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;
+{
+  /* 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;
+}
+
+/* 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;
+}
+
+/* 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;
+{
+  remove_all_occurrences (node);
+  forest->nnodes--;
+
+  free (node);
+}
+
+/* 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;
+
+  splay (child_node->first);
+
+  if (! child_node->first->left)
+    return 0;
+
+  parent_pre_occ = find_rightmost_node (child_node->first->left);
+  if (parent_pre_occ->node != parent_node)
+    abort ();
+
+  splay (parent_pre_occ);
+  parent_pre_occ->right->parent = 0;
+  
+  parent_post_occ = parent_pre_occ->next;
+  splay (parent_post_occ);
+
+  parent_post_occ->left->parent = 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;
+
+  parent_pre_occ->next = parent_post_occ->next;
+
+  if (parent_post_occ == parent_node->last)
+    parent_node->last = parent_pre_occ;
+
+  free (parent_post_occ);
+  return 1;
+}
+
+/* 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;
+{
+  splay (node->first);
+
+  if (node->first->left)
+    return find_rightmost_node (node->first->left)->node;
+  else
+    return 0;
+}
+
+
+/* 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;
+{
+  int value1, value2, max_value;
+  et_forest_node_t ancestor;
+
+  if (node1 == node2)
+    return node1;
+  
+  if (! node1 || ! node2)
+    abort ();
+
+  splay (node1->first);
+  splay (node2->first);
+
+  if (! node1->first->parent)  /* The two vertices are in different trees.  */
+    return 0;
+
+  value2 = calculate_value (node2->first);
+  value1 = calculate_value (node1->first);
+
+  if (value1 < value2)
+    {
+      ancestor = node1;
+      max_value = value2;
+    }
+  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;
+    }
+
+  return ancestor;
+}
+
+/* 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;
+}
+
+/* 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;
+{
+  int n = 0;
+  et_forest_occurrence_t occ = node->first, stop = node->last, occ1;
+
+  /* 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;
+}