X-Git-Url: http://git.efficios.com/?a=blobdiff_plain;f=libiberty%2Fsplay-tree.c;h=3b7b810388ce67b15b419cfb7d165f03b7552890;hb=refs%2Fheads%2Fconcurrent-displaced-stepping-2020-04-01;hp=d7ed86813dc553007827b3208590e8e9ffff9b0a;hpb=145f4ab500b18cd0d31e7bff54983ded2e45b0cf;p=deliverable%2Fbinutils-gdb.git diff --git a/libiberty/splay-tree.c b/libiberty/splay-tree.c index d7ed86813d..3b7b810388 100644 --- a/libiberty/splay-tree.c +++ b/libiberty/splay-tree.c @@ -1,5 +1,5 @@ /* A splay-tree datatype. - Copyright (C) 1998, 1999, 2000, 2001 Free Software Foundation, Inc. + Copyright (C) 1998-2020 Free Software Foundation, Inc. Contributed by Mark Mitchell (mark@markmitchell.com). This file is part of GNU CC. @@ -31,6 +31,9 @@ Boston, MA 02110-1301, USA. */ #ifdef HAVE_STDLIB_H #include #endif +#ifdef HAVE_STRING_H +#include +#endif #include @@ -43,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. */ @@ -203,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. */ + +#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 * @@ -265,13 +294,57 @@ splay_tree_new_with_allocator (splay_tree_compare_fn compare_fn, splay_tree_deallocate_fn deallocate_fn, void *allocate_data) { - splay_tree sp = (splay_tree) (*allocate_fn) (sizeof (struct splay_tree_s), - allocate_data); + return + splay_tree_new_typed_alloc (compare_fn, delete_key_fn, delete_value_fn, + allocate_fn, allocate_fn, deallocate_fn, + allocate_data); +} + +/* + +@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 +@var{tree_allocate_fn} and @var{node_allocate_fn} to use for allocating the +tree itself and its nodes respectively. This is useful when variables of +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. 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 + +*/ + +splay_tree +splay_tree_new_typed_alloc (splay_tree_compare_fn compare_fn, + splay_tree_delete_key_fn delete_key_fn, + splay_tree_delete_value_fn delete_value_fn, + splay_tree_allocate_fn tree_allocate_fn, + splay_tree_allocate_fn node_allocate_fn, + splay_tree_deallocate_fn deallocate_fn, + void * allocate_data) +{ + splay_tree sp = (splay_tree) (*tree_allocate_fn) + (sizeof (struct splay_tree_s), allocate_data); + sp->root = 0; sp->comp = compare_fn; sp->delete_key = delete_key_fn; sp->delete_value = delete_value_fn; - sp->allocate = allocate_fn; + sp->allocate = node_allocate_fn; sp->deallocate = deallocate_fn; sp->allocate_data = allocate_data; @@ -303,20 +376,23 @@ 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 { /* Create a new node, and insert it at the root. */ splay_tree_node node; - + node = ((splay_tree_node) - (*sp->allocate) (sizeof (struct splay_tree_node_s), - sp->allocate_data)); + (*sp->allocate) (sizeof (struct splay_tree_node_s), + sp->allocate_data)); node->key = key; node->value = value; @@ -356,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); @@ -496,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. */ @@ -524,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); +}