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=a71239526717aee4feadbf6432ac15aa8ec58918;hpb=e00bc6a7ba6342b27c657c0f59b27e06bd870346;p=deliverable%2Fbinutils-gdb.git diff --git a/libiberty/splay-tree.c b/libiberty/splay-tree.c index a712395267..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. @@ -16,8 +16,8 @@ General Public License for more details. You should have received a copy of the GNU General Public License along with GNU CC; see the file COPYING. If not, write to -the Free Software Foundation, 59 Temple Place - Suite 330, -Boston, MA 02111-1307, USA. */ +the Free Software Foundation, 51 Franklin Street - Fifth Floor, +Boston, MA 02110-1301, USA. */ /* For an easily readable description of splay-trees, see: @@ -31,172 +31,173 @@ Boston, MA 02111-1307, USA. */ #ifdef HAVE_STDLIB_H #include #endif +#ifdef HAVE_STRING_H +#include +#endif #include #include "libiberty.h" #include "splay-tree.h" -static void splay_tree_delete_helper PARAMS((splay_tree, - splay_tree_node)); -static void splay_tree_splay PARAMS((splay_tree, - splay_tree_key)); -static splay_tree_node splay_tree_splay_helper - PARAMS((splay_tree, - splay_tree_key, - splay_tree_node*, - splay_tree_node*, - splay_tree_node*)); -static int splay_tree_foreach_helper PARAMS((splay_tree, - splay_tree_node, - splay_tree_foreach_fn, - void*)); +static void splay_tree_delete_helper (splay_tree, splay_tree_node); +static inline void rotate_left (splay_tree_node *, + splay_tree_node, 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_node, + splay_tree_foreach_fn, void*); /* Deallocate NODE (a member of SP), and all its sub-trees. */ static void -splay_tree_delete_helper (sp, node) - splay_tree sp; - splay_tree_node node; +splay_tree_delete_helper (splay_tree sp, splay_tree_node node) { + splay_tree_node pending = 0; + splay_tree_node active = 0; + if (!node) return; - splay_tree_delete_helper (sp, node->left); - splay_tree_delete_helper (sp, node->right); - - if (sp->delete_key) - (*sp->delete_key)(node->key); - if (sp->delete_value) - (*sp->delete_value)(node->value); +#define KDEL(x) if (sp->delete_key) (*sp->delete_key)(x); +#define VDEL(x) if (sp->delete_value) (*sp->delete_value)(x); - free ((char*) node); -} + KDEL (node->key); + VDEL (node->value); -/* Help splay SP around KEY. PARENT and GRANDPARENT are the parent - and grandparent, respectively, of NODE. */ + /* We use the "key" field to hold the "next" pointer. */ + node->key = (splay_tree_key)pending; + pending = (splay_tree_node)node; -static splay_tree_node -splay_tree_splay_helper (sp, key, node, parent, grandparent) - splay_tree sp; - splay_tree_key key; - splay_tree_node *node; - splay_tree_node *parent; - splay_tree_node *grandparent; -{ - splay_tree_node *next; - splay_tree_node n; - int comparison; - - n = *node; - - if (!n) - return *parent; - - comparison = (*sp->comp) (key, n->key); - - if (comparison == 0) - /* We've found the target. */ - next = 0; - else if (comparison < 0) - /* The target is to the left. */ - next = &n->left; - else - /* The target is to the right. */ - next = &n->right; + /* Now, keep processing the pending list until there aren't any + more. This is a little more complicated than just recursing, but + it doesn't toast the stack for large trees. */ - if (next) + while (pending) { - /* Continue down the tree. */ - n = splay_tree_splay_helper (sp, key, next, node, parent); + active = pending; + pending = 0; + while (active) + { + splay_tree_node temp; - /* The recursive call will change the place to which NODE - points. */ - if (*node != n) - return n; - } + /* active points to a node which has its key and value + deallocated, we just need to process left and right. */ - if (!parent) - /* NODE is the root. We are done. */ - return n; + if (active->left) + { + KDEL (active->left->key); + VDEL (active->left->value); + active->left->key = (splay_tree_key)pending; + pending = (splay_tree_node)(active->left); + } + if (active->right) + { + KDEL (active->right->key); + VDEL (active->right->value); + active->right->key = (splay_tree_key)pending; + pending = (splay_tree_node)(active->right); + } - /* First, handle the case where there is no grandparent (i.e., - *PARENT is the root of the tree.) */ - if (!grandparent) - { - if (n == (*parent)->left) - { - *node = n->right; - n->right = *parent; - } - else - { - *node = n->left; - n->left = *parent; + temp = active; + active = (splay_tree_node)(temp->key); + (*sp->deallocate) ((char*) temp, sp->allocate_data); } - *parent = n; - return n; } +#undef KDEL +#undef VDEL +} - /* Next handle the cases where both N and *PARENT are left children, - or where both are right children. */ - if (n == (*parent)->left && *parent == (*grandparent)->left) - { - splay_tree_node p = *parent; - - (*grandparent)->left = p->right; - p->right = *grandparent; - p->left = n->right; - n->right = p; - *grandparent = n; - return n; - } - else if (n == (*parent)->right && *parent == (*grandparent)->right) - { - splay_tree_node p = *parent; - - (*grandparent)->right = p->left; - p->left = *grandparent; - p->right = n->left; - n->left = p; - *grandparent = n; - return n; - } +/* Rotate the edge joining the left child N with its parent P. PP is the + grandparents' pointer to P. */ - /* Finally, deal with the case where N is a left child, but *PARENT - is a right child, or vice versa. */ - if (n == (*parent)->left) - { - (*parent)->left = n->right; - n->right = *parent; - (*grandparent)->right = n->left; - n->left = *grandparent; - *grandparent = n; - return n; - } - else - { - (*parent)->right = n->left; - n->left = *parent; - (*grandparent)->left = n->right; - n->right = *grandparent; - *grandparent = n; - return n; - } +static inline void +rotate_left (splay_tree_node *pp, splay_tree_node p, splay_tree_node n) +{ + splay_tree_node tmp; + tmp = n->right; + n->right = p; + p->left = tmp; + *pp = n; } -/* Splay SP around KEY. */ +/* Rotate the edge joining the right child N with its parent P. PP is the + grandparents' pointer to P. */ + +static inline void +rotate_right (splay_tree_node *pp, splay_tree_node p, splay_tree_node n) +{ + splay_tree_node tmp; + tmp = n->left; + n->left = p; + p->right = tmp; + *pp = n; +} + +/* Bottom up splay of key. */ static void -splay_tree_splay (sp, key) - splay_tree sp; - splay_tree_key key; +splay_tree_splay (splay_tree sp, splay_tree_key key) { if (sp->root == 0) return; - splay_tree_splay_helper (sp, key, &sp->root, - /*grandparent=*/0, /*parent=*/0); + do { + int cmp1, cmp2; + splay_tree_node n, c; + + n = sp->root; + cmp1 = (*sp->comp) (key, n->key); + + /* Found. */ + if (cmp1 == 0) + return; + + /* Left or right? If no child, then we're done. */ + if (cmp1 < 0) + c = n->left; + else + c = n->right; + if (!c) + return; + + /* Next one left or right? If found or no child, we're done + after one rotation. */ + cmp2 = (*sp->comp) (key, c->key); + if (cmp2 == 0 + || (cmp2 < 0 && !c->left) + || (cmp2 > 0 && !c->right)) + { + if (cmp1 < 0) + rotate_left (&sp->root, n, c); + else + rotate_right (&sp->root, n, c); + return; + } + + /* Now we have the four cases of double-rotation. */ + if (cmp1 < 0 && cmp2 < 0) + { + rotate_left (&n->left, c, c->left); + rotate_left (&sp->root, n, n->left); + } + else if (cmp1 > 0 && cmp2 > 0) + { + rotate_right (&n->right, c, c->right); + rotate_right (&sp->root, n, n->right); + } + else if (cmp1 < 0 && cmp2 > 0) + { + rotate_right (&n->left, c, c->right); + rotate_left (&sp->root, n, n->left); + } + else if (cmp1 > 0 && cmp2 < 0) + { + rotate_left (&n->right, c, c->left); + rotate_right (&sp->root, n, n->right); + } + } while (1); } /* Call FN, passing it the DATA, for every node below NODE, all of @@ -205,43 +206,147 @@ splay_tree_splay (sp, key) value is returned. Otherwise, this function returns 0. */ static int -splay_tree_foreach_helper (sp, node, fn, data) - splay_tree sp; - splay_tree_node node; - splay_tree_foreach_fn fn; - void* data; +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; + } + + 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 * +splay_tree_xmalloc_allocate (int size, void *data ATTRIBUTE_UNUSED) +{ + return (void *) xmalloc (size); +} - val = splay_tree_foreach_helper (sp, node->left, fn, data); - if (val) - return val; +static void +splay_tree_xmalloc_deallocate (void *object, void *data ATTRIBUTE_UNUSED) +{ + free (object); +} - val = (*fn)(node, data); - if (val) - return val; - return splay_tree_foreach_helper (sp, node->right, fn, data); +/* Allocate a new splay tree, using COMPARE_FN to compare nodes, + DELETE_KEY_FN to deallocate keys, and DELETE_VALUE_FN to deallocate + values. Use xmalloc to allocate the splay tree structure, and any + nodes added. */ + +splay_tree +splay_tree_new (splay_tree_compare_fn compare_fn, + splay_tree_delete_key_fn delete_key_fn, + splay_tree_delete_value_fn delete_value_fn) +{ + return (splay_tree_new_with_allocator + (compare_fn, delete_key_fn, delete_value_fn, + splay_tree_xmalloc_allocate, splay_tree_xmalloc_deallocate, 0)); } + /* Allocate a new splay tree, using COMPARE_FN to compare nodes, DELETE_KEY_FN to deallocate keys, and DELETE_VALUE_FN to deallocate values. */ splay_tree -splay_tree_new (compare_fn, delete_key_fn, delete_value_fn) - splay_tree_compare_fn compare_fn; - splay_tree_delete_key_fn delete_key_fn; - splay_tree_delete_value_fn delete_value_fn; +splay_tree_new_with_allocator (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 allocate_fn, + splay_tree_deallocate_fn deallocate_fn, + void *allocate_data) { - splay_tree sp = (splay_tree) xmalloc (sizeof (struct splay_tree_s)); + 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 = node_allocate_fn; + sp->deallocate = deallocate_fn; + sp->allocate_data = allocate_data; return sp; } @@ -249,11 +354,10 @@ splay_tree_new (compare_fn, delete_key_fn, delete_value_fn) /* Deallocate SP. */ void -splay_tree_delete (sp) - splay_tree sp; +splay_tree_delete (splay_tree sp) { splay_tree_delete_helper (sp, sp->root); - free ((char*) sp); + (*sp->deallocate) ((char*) sp, sp->allocate_data); } /* Insert a new node (associating KEY with DATA) into SP. If a @@ -261,10 +365,7 @@ splay_tree_delete (sp) with the new value. Returns the new node. */ splay_tree_node -splay_tree_insert (sp, key, value) - splay_tree sp; - splay_tree_key key; - splay_tree_value value; +splay_tree_insert (splay_tree sp, splay_tree_key key, splay_tree_value value) { int comparison = 0; @@ -275,18 +376,23 @@ splay_tree_insert (sp, key, 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) xmalloc (sizeof (struct splay_tree_node_s)); + + node = ((splay_tree_node) + (*sp->allocate) (sizeof (struct splay_tree_node_s), + sp->allocate_data)); node->key = key; node->value = value; @@ -314,9 +420,7 @@ splay_tree_insert (sp, key, value) /* Remove KEY from SP. It is not an error if it did not exist. */ void -splay_tree_remove (sp, key) - splay_tree sp; - splay_tree_key key; +splay_tree_remove (splay_tree sp, splay_tree_key key) { splay_tree_splay (sp, key); @@ -328,9 +432,11 @@ splay_tree_remove (sp, 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); - free (sp->root); + (*sp->deallocate) (sp->root, sp->allocate_data); /* One of the children is now the root. Doesn't matter much which, so long as we preserve the properties of the tree. */ @@ -356,9 +462,7 @@ splay_tree_remove (sp, key) otherwise. */ splay_tree_node -splay_tree_lookup (sp, key) - splay_tree sp; - splay_tree_key key; +splay_tree_lookup (splay_tree sp, splay_tree_key key) { splay_tree_splay (sp, key); @@ -371,8 +475,7 @@ splay_tree_lookup (sp, key) /* Return the node in SP with the greatest key. */ splay_tree_node -splay_tree_max (sp) - splay_tree sp; +splay_tree_max (splay_tree sp) { splay_tree_node n = sp->root; @@ -388,8 +491,7 @@ splay_tree_max (sp) /* Return the node in SP with the smallest key. */ splay_tree_node -splay_tree_min (sp) - splay_tree sp; +splay_tree_min (splay_tree sp) { splay_tree_node n = sp->root; @@ -406,9 +508,7 @@ splay_tree_min (sp) predecessor. KEY need not be present in the tree. */ splay_tree_node -splay_tree_predecessor (sp, key) - splay_tree sp; - splay_tree_key key; +splay_tree_predecessor (splay_tree sp, splay_tree_key key) { int comparison; splay_tree_node node; @@ -426,7 +526,7 @@ splay_tree_predecessor (sp, key) if (comparison < 0) return sp->root; - /* Otherwise, find the leftmost element of the right subtree. */ + /* Otherwise, find the rightmost element of the left subtree. */ node = sp->root->left; if (node) while (node->right) @@ -436,17 +536,15 @@ splay_tree_predecessor (sp, key) } /* Return the immediate successor KEY, or NULL if there is no - predecessor. KEY need not be present in the tree. */ + successor. KEY need not be present in the tree. */ splay_tree_node -splay_tree_successor (sp, key) - splay_tree sp; - splay_tree_key key; +splay_tree_successor (splay_tree sp, splay_tree_key key) { int comparison; splay_tree_node node; - /* If the tree is empty, there is certainly no predecessor. */ + /* If the tree is empty, there is certainly no successor. */ if (!sp->root) return NULL; @@ -459,7 +557,7 @@ splay_tree_successor (sp, key) if (comparison > 0) return sp->root; - /* Otherwise, find the rightmost element of the left subtree. */ + /* Otherwise, find the leftmost element of the right subtree. */ node = sp->root->right; if (node) while (node->left) @@ -474,20 +572,15 @@ splay_tree_successor (sp, key) Otherwise, this function returns 0. */ int -splay_tree_foreach (sp, fn, data) - splay_tree sp; - splay_tree_foreach_fn fn; - void *data; +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. */ int -splay_tree_compare_ints (k1, k2) - splay_tree_key k1; - splay_tree_key k2; +splay_tree_compare_ints (splay_tree_key k1, splay_tree_key k2) { if ((int) k1 < (int) k2) return -1; @@ -500,9 +593,7 @@ splay_tree_compare_ints (k1, k2) /* Splay-tree comparison function, treating the keys as pointers. */ int -splay_tree_compare_pointers (k1, k2) - splay_tree_key k1; - splay_tree_key k2; +splay_tree_compare_pointers (splay_tree_key k1, splay_tree_key k2) { if ((char*) k1 < (char*) k2) return -1; @@ -511,3 +602,19 @@ splay_tree_compare_pointers (k1, 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); +}