diff mbox

[RFA] rewrite splay_tree_foreach_helper to be non-recursive

Message ID 20101205193453.428A72461AB@ruffy.mtv.corp.google.com
State New
Headers show

Commit Message

Doug Evans Dec. 5, 2010, 7:34 p.m. UTC 
Hi.
Splay trees are worst case O(n) in the depth of tree, and I have an
example with ~300000 entries (reading of the address table piece of the
.gdb_index section for a large program).
gdb segfaults because it runs out of stack.
This patch converts splay_tree_foreach_helper to be non-recursive.

One might want to use malloc here and return if it runs out of space
(library utilities should let the caller deal with such things),
but the API doesn't really provide for it, and the new version's behaviour
is no different than the existing behaviour.
It didn't make sense to create another foreach API call just for this,
so I just rewrote the existing one.

One might want gdb/addrmap.c to use something besides splay-trees,
but that's more work, and this patch is generally useful anyways.

Tested by running the gdb testsuite on amd64-linux, no regressions.
Ok to check in?

2010-12-05  Doug Evans  <dje@google.com>

	* splay-tree.c (splay_tree_foreach_helper): Remove arg `sp',
	all callers updated.  Rewrite to be non-recursive.

Comments

Ian Lance Taylor Dec. 7, 2010, 9:17 p.m. UTC | #1 
On Sun, Dec 5, 2010 at 11:34 AM, Doug Evans <dje@google.com> wrote:

> 2010-12-05  Doug Evans  <dje@google.com>
>
>        * splay-tree.c (splay_tree_foreach_helper): Remove arg `sp',
>        all callers updated.  Rewrite to be non-recursive.

This is OK if you rewrite xmalloc to XNEWVEC, xrealloc to XRESIZEVEC,
and free to XDELETEVEC.

Thanks.

Ian
diff mbox

Patch

Index: splay-tree.c
===================================================================
RCS file: /cvs/src/src/libiberty/splay-tree.c,v
retrieving revision 1.18
diff -u -p -r1.18 splay-tree.c
--- splay-tree.c	10 Jun 2010 18:30:24 -0000	1.18
+++ splay-tree.c	5 Dec 2010 09:07:28 -0000
@@ -44,7 +44,7 @@  static inline void rotate_left (splay_tr
 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,48 @@  splay_tree_splay (splay_tree sp, splay_t
    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;
+#define INITIAL_STACK_SIZE 100
+  stack_size = INITIAL_STACK_SIZE;
+  stack_ptr = 0;
+  stack = (splay_tree_node*) xmalloc (stack_size * sizeof (splay_tree_node));
+  val = 0;
+  
+  for (;;)
+    {
+      while (node != NULL)
+	{
+	  if (stack_ptr == stack_size)
+	    {
+	      stack_size *= 2;
+	      stack = (splay_tree_node*)
+		xrealloc (stack, stack_size * sizeof (splay_tree_node));
+	    }
+	  stack[stack_ptr++] = node;
+	  node = node->left;
+	}
 
-  val = splay_tree_foreach_helper (sp, node->left, fn, data);
-  if (val)
-    return val;
-
-  val = (*fn)(node, data);
-  if (val)
-    return val;
+      if (stack_ptr == 0)
+	break;
 
-  return splay_tree_foreach_helper (sp, node->right, fn, data);
-}
+      node = stack[--stack_ptr];
+
+      val = (*fn) (node, data);
+      if (val)
+	break;
+
+      node = node->right;
+    }
 
+  free (stack);
+  return val;
+}
 
 /* An allocator and deallocator based on xmalloc.  */
 static void *
@@ -537,7 +560,7 @@  splay_tree_successor (splay_tree sp, spl
 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.  */