libiberty: fix warnings about left shifting a negative value.

[deliverable/binutils-gdb.git] / libiberty / splay-tree.c

diff --git a/libiberty/splay-tree.c b/libiberty/splay-tree.c
index bf1a0f3f151f36d641510c86de9c592b9b055686..12bfa8bbdcc97990d837b6e1280007481ea5c3b5 100644 (file)
--- a/libiberty/splay-tree.c
+++ b/libiberty/splay-tree.c
@@ -1,6 +1,6 @@
 /* A splay-tree datatype.  
    Copyright (C) 1998, 1999, 2000, 2001, 2009,
-   2010 Free Software Foundation, Inc.
+   2010, 2011 Free Software Foundation, Inc.
    Contributed by Mark Mitchell (mark@markmitchell.com).
 
 This file is part of GNU CC.
@@ -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 *
@@ -274,13 +300,13 @@ splay_tree_new_with_allocator (splay_tree_compare_fn compare_fn,
 
 /*
 
-@deftypefn Supplemental splay_tree splay_tree_new_with_typed_alloc
-(splay_tree_compare_fn @var{compare_fn},
-splay_tree_delete_key_fn @var{delete_key_fn},
-splay_tree_delete_value_fn @var{delete_value_fn},
-splay_tree_allocate_fn @var{tree_allocate_fn},
-splay_tree_allocate_fn @var{node_allocate_fn},
-splay_tree_deallocate_fn @var{deallocate_fn},
+@deftypefn Supplemental splay_tree splay_tree_new_with_typed_alloc @
+(splay_tree_compare_fn @var{compare_fn}, @
+splay_tree_delete_key_fn @var{delete_key_fn}, @
+splay_tree_delete_value_fn @var{delete_value_fn}, @
+splay_tree_allocate_fn @var{tree_allocate_fn}, @
+splay_tree_allocate_fn @var{node_allocate_fn}, @
+splay_tree_deallocate_fn @var{deallocate_fn}, @
 void * @var{allocate_data})
 
 This function creates a splay tree that uses two different allocators
@@ -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.  */