aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorDJ Delorie <dj@redhat.com>2010-12-08 16:24:43 +0000
committerDJ Delorie <dj@redhat.com>2010-12-08 16:24:43 +0000
commit98f0b5d4e51f85fd717cda948174ec5c43305e08 (patch)
tree8f295fed2ab8a0b8db18ce3bba1b9a5a104eaf7b
parent017257f8db5c860dd46d7ba45fa867a3a6a7c49e (diff)
downloadgdb-98f0b5d4e51f85fd717cda948174ec5c43305e08.zip
gdb-98f0b5d4e51f85fd717cda948174ec5c43305e08.tar.gz
gdb-98f0b5d4e51f85fd717cda948174ec5c43305e08.tar.bz2
merge from gcc
-rw-r--r--libiberty/ChangeLog5
-rw-r--r--libiberty/splay-tree.c52
2 files changed, 44 insertions, 13 deletions
diff --git a/libiberty/ChangeLog b/libiberty/ChangeLog
index bbd5aaf..bc02da4 100644
--- a/libiberty/ChangeLog
+++ b/libiberty/ChangeLog
@@ -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>.
diff --git a/libiberty/splay-tree.c b/libiberty/splay-tree.c
index bf1a0f3..27ae466 100644
--- a/libiberty/splay-tree.c
+++ b/libiberty/splay-tree.c
@@ -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. */