OSDN Git Service

* splay-tree.c (splay_tree_foreach_helper): Remove arg `sp',
authordevans <devans@138bc75d-0d04-0410-961f-82ee72b054a4>
Wed, 8 Dec 2010 15:48:50 +0000 (15:48 +0000)
committerdevans <devans@138bc75d-0d04-0410-961f-82ee72b054a4>
Wed, 8 Dec 2010 15:48:50 +0000 (15:48 +0000)
all callers updated.  Rewrite to be non-recursive.

git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@167589 138bc75d-0d04-0410-961f-82ee72b054a4

libiberty/ChangeLog
libiberty/splay-tree.c

index bbd5aaf..bc02da4 100644 (file)
@@ -1,3 +1,8 @@
+2010-12-08  Doug Evans  <dje@google.com>
+
+       * splay-tree.c (splay_tree_foreach_helper): Remove arg `sp',
+       all callers updated.  Rewrite to be non-recursive.
+
 2010-11-29  Rainer Orth  <ro@CeBiTec.Uni-Bielefeld.DE>
 
        * setproctitle.c [HAVE_SYS_PRCTL_H]: Include <sys/types.h>.
index bf1a0f3..27ae466 100644 (file)
@@ -44,7 +44,7 @@ static inline void rotate_left (splay_tree_node *,
 static inline void rotate_right (splay_tree_node *,
                                splay_tree_node, splay_tree_node);
 static void splay_tree_splay (splay_tree, splay_tree_key);
-static int splay_tree_foreach_helper (splay_tree, splay_tree_node,
+static int splay_tree_foreach_helper (splay_tree_node,
                                       splay_tree_foreach_fn, void*);
 
 /* Deallocate NODE (a member of SP), and all its sub-trees.  */
@@ -204,25 +204,51 @@ splay_tree_splay (splay_tree sp, splay_tree_key key)
    value is returned.  Otherwise, this function returns 0.  */
 
 static int
-splay_tree_foreach_helper (splay_tree sp, splay_tree_node node,
+splay_tree_foreach_helper (splay_tree_node node,
                            splay_tree_foreach_fn fn, void *data)
 {
   int val;
+  splay_tree_node *stack;
+  int stack_ptr, stack_size;
 
-  if (!node)
-    return 0;
+  /* A non-recursive implementation is used to avoid filling the stack
+     for large trees.  Splay trees are worst case O(n) in the depth of
+     the tree.  */
+
+#define INITIAL_STACK_SIZE 100
+  stack_size = INITIAL_STACK_SIZE;
+  stack_ptr = 0;
+  stack = XNEWVEC (splay_tree_node, stack_size);
+  val = 0;
+
+  for (;;)
+    {
+      while (node != NULL)
+       {
+         if (stack_ptr == stack_size)
+           {
+             stack_size *= 2;
+             stack = XRESIZEVEC (splay_tree_node, stack, stack_size);
+           }
+         stack[stack_ptr++] = node;
+         node = node->left;
+       }
 
-  val = splay_tree_foreach_helper (sp, node->left, fn, data);
-  if (val)
-    return val;
+      if (stack_ptr == 0)
+       break;
 
-  val = (*fn)(node, data);
-  if (val)
-    return val;
+      node = stack[--stack_ptr];
 
-  return splay_tree_foreach_helper (sp, node->right, fn, data);
-}
+      val = (*fn) (node, data);
+      if (val)
+       break;
 
+      node = node->right;
+    }
+
+  XDELETEVEC (stack);
+  return val;
+}
 
 /* An allocator and deallocator based on xmalloc.  */
 static void *
@@ -537,7 +563,7 @@ splay_tree_successor (splay_tree sp, splay_tree_key key)
 int
 splay_tree_foreach (splay_tree sp, splay_tree_foreach_fn fn, void *data)
 {
-  return splay_tree_foreach_helper (sp, sp->root, fn, data);
+  return splay_tree_foreach_helper (sp->root, fn, data);
 }
 
 /* Splay-tree comparison function, treating the keys as ints.  */