X-Git-Url: http://git.sourceforge.jp/view?a=blobdiff_plain;f=gcc%2Fet-forest.c;h=d1063165c7a3e7232e1c66d16e944f2508dd9770;hb=e21b444cfb76b8d67c9ad45766f55730901b6957;hp=df7c22aff407d31f71e297e4961c2d3b4ecf4eec;hpb=108beec73e6f9087513651b6d42aa253398d7ba0;p=pf3gnuchains%2Fgcc-fork.git

diff --git a/gcc/et-forest.c b/gcc/et-forest.c
index df7c22aff40..d1063165c7a 100644
--- a/gcc/et-forest.c
+++ b/gcc/et-forest.c
@@ -1,12 +1,13 @@
 /* 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, 2010 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
@@ -14,9 +15,8 @@ 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.
+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.
@@ -26,7 +26,6 @@ Boston, MA 02111-1307, USA.
 #include "config.h"
 #include "system.h"
 #include "coretypes.h"
-#include "tm.h"
 #include "et-forest.h"
 #include "alloc-pool.h"
 
@@ -210,7 +209,7 @@ record_path_before_1 (struct et_occ *occ, int depth)
 
   if (occ->prev)
     {
-      m = record_path_before_1 (occ->prev, depth); 
+      m = record_path_before_1 (occ->prev, depth);
       if (m < mn)
 	mn = m;
     }
@@ -261,7 +260,7 @@ check_path_after_1 (struct et_occ *occ, int depth)
 
   if (occ->next)
     {
-      m = check_path_after_1 (occ->next, depth); 
+      m = check_path_after_1 (occ->next, depth);
       if (m < mn)
 	mn =  m;
     }
@@ -308,7 +307,7 @@ et_splay (struct et_occ *occ)
   record_path_before (occ);
   et_check_tree_sanity (occ);
 #endif
- 
+
   while (occ->parent)
     {
       occ_depth = occ->depth;
@@ -444,10 +443,10 @@ static struct et_occ *
 et_new_occ (struct et_node *node)
 {
   struct et_occ *nw;
-  
+
   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;
@@ -467,10 +466,10 @@ struct et_node *
 et_new_tree (void *data)
 {
   struct et_node *nw;
-  
+
   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;
@@ -505,9 +504,20 @@ 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
@@ -579,7 +589,7 @@ et_split (struct et_node *t)
 
   for (r = rmost->next; r->prev; r = r->prev)
     continue;
-  et_splay (r); 
+  et_splay (r);
 
   r->prev->parent = NULL;
   p_occ = t->parent_occ;
@@ -650,7 +660,7 @@ et_nca (struct et_node *n1, struct et_node *n2)
       if (r)
 	r->parent = o1;
     }
-  else
+  else if (r == o2 || (r && r->parent != NULL))
     {
       ret = o2->prev;
 
@@ -658,6 +668,15 @@ et_nca (struct et_node *n1, struct et_node *n2)
       if (l)
 	l->parent = o1;
     }
+  else
+    {
+      /* O1 and O2 are in different components of the forest.  */
+      if (l)
+	l->parent = o1;
+      if (r)
+	r->parent = o1;
+      return NULL;
+    }
 
   if (0 < o2->depth)
     {
@@ -736,3 +755,20 @@ et_below (struct et_node *down, struct et_node *up)
 
   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;
+}