2014-04-04 Richard Biener <rguenther@suse.de>

[pf3gnuchains/gcc-fork.git] / gcc / et-forest.c

diff --git a/gcc/et-forest.c b/gcc/et-forest.c
index b8e5527..d106316 100644 (file)
--- 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, 2005 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., 51 Franklin Street, Fifth Floor,
-Boston, MA 02110-1301, 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 02110-1301, 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;
@@ -590,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;
@@ -661,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;
 
@@ -669,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)
     {
@@ -747,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;
+}