i386: Check vector length for EVEX broadcast instructions

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

diff --git a/libiberty/splay-tree.c b/libiberty/splay-tree.c
index bf1a0f3f151f36d641510c86de9c592b9b055686..4bbb39a62ca476de7dd63b5ee592373e7a9a51a2 100644 (file)
--- a/libiberty/splay-tree.c
+++ b/libiberty/splay-tree.c
@@ -1,6 +1,5 @@
 /* A splay-tree datatype.  
-   Copyright (C) 1998, 1999, 2000, 2001, 2009,
-   2010 Free Software Foundation, Inc.
+   Copyright (C) 1998-2019 Free Software Foundation, Inc.
    Contributed by Mark Mitchell (mark@markmitchell.com).
 
 This file is part of GNU CC.
@@ -32,6 +31,9 @@ Boston, MA 02110-1301, USA.  */
 #ifdef HAVE_STDLIB_H
 #include <stdlib.h>
 #endif
+#ifdef HAVE_STRING_H
+#include <string.h>
+#endif
 
 #include <stdio.h>
 
@@ -44,7 +46,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 +206,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.  */
 
-  val = splay_tree_foreach_helper (sp, node->left, fn, data);
-  if (val)
-    return val;
+#define INITIAL_STACK_SIZE 100
+  stack_size = INITIAL_STACK_SIZE;
+  stack_ptr = 0;
+  stack = XNEWVEC (splay_tree_node, stack_size);
+  val = 0;
 
-  val = (*fn)(node, data);
-  if (val)
-    return val;
+  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;
+       }
 
-  return splay_tree_foreach_helper (sp, node->right, fn, data);
-}
+      if (stack_ptr == 0)
+       break;
+
+      node = stack[--stack_ptr];
 
+      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 +302,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
@@ -290,7 +318,11 @@ different types need to be allocated with different allocators.
 
 The splay tree will use @var{compare_fn} to compare nodes,
 @var{delete_key_fn} to deallocate keys, and @var{delete_value_fn} to
-deallocate values.
+deallocate values.  Keys and values will be deallocated when the
+tree is deleted using splay_tree_delete or when a node is removed
+using splay_tree_remove.  splay_tree_insert will release the previously
+inserted key and value using @var{delete_key_fn} and @var{delete_value_fn}
+if the inserted key is already found in the tree.
 
 @end deftypefn
 
@@ -344,10 +376,13 @@ splay_tree_insert (splay_tree sp, splay_tree_key key, splay_tree_value value)
 
   if (sp->root && comparison == 0)
     {
-      /* If the root of the tree already has the indicated KEY, just
-        replace the value with VALUE.  */
+      /* If the root of the tree already has the indicated KEY, delete
+         the old key and old value, and replace them with KEY and  VALUE.  */
+      if (sp->delete_key)
+       (*sp->delete_key) (sp->root->key);
       if (sp->delete_value)
        (*sp->delete_value)(sp->root->value);
+      sp->root->key = key;
       sp->root->value = value;
     } 
   else 
@@ -397,6 +432,8 @@ splay_tree_remove (splay_tree sp, splay_tree_key key)
       right = sp->root->right;
 
       /* Delete the root node itself.  */
+      if (sp->delete_key)
+       (*sp->delete_key) (sp->root->key);
       if (sp->delete_value)
        (*sp->delete_value) (sp->root->value);
       (*sp->deallocate) (sp->root, sp->allocate_data);
@@ -537,7 +574,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.  */
@@ -565,3 +602,19 @@ splay_tree_compare_pointers (splay_tree_key k1, splay_tree_key k2)
   else 
     return 0;
 }
+
+/* Splay-tree comparison function, treating the keys as strings.  */
+
+int
+splay_tree_compare_strings (splay_tree_key k1, splay_tree_key k2)
+{
+  return strcmp ((char *) k1, (char *) k2);
+}
+
+/* Splay-tree delete function, simply using free.  */
+
+void
+splay_tree_delete_pointers (splay_tree_value value)
+{
+  free ((void *) value);
+}