X-Git-Url: http://drtracing.org/?a=blobdiff_plain;f=libiberty%2Fsplay-tree.c;h=12bfa8bbdcc97990d837b6e1280007481ea5c3b5;hb=693dca065a58bf2dd39df9cff019b0c65e15e132;hp=060f900ae0a08792a75fe2ece703d6c837a525d9;hpb=718c0ded1f2626b3e7e8e210cb93e2714a91b548;p=deliverable%2Fbinutils-gdb.git diff --git a/libiberty/splay-tree.c b/libiberty/splay-tree.c index 060f900ae0..12bfa8bbdc 100644 --- a/libiberty/splay-tree.c +++ b/libiberty/splay-tree.c @@ -1,5 +1,6 @@ /* A splay-tree datatype. - Copyright (C) 1998, 1999, 2000, 2001 Free Software Foundation, Inc. + Copyright (C) 1998, 1999, 2000, 2001, 2009, + 2010, 2011 Free Software Foundation, Inc. Contributed by Mark Mitchell (mark@markmitchell.com). This file is part of GNU CC. @@ -43,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. */ @@ -107,7 +108,7 @@ splay_tree_delete_helper (splay_tree sp, splay_tree_node node) } /* Rotate the edge joining the left child N with its parent P. PP is the - grandparents pointer to P. */ + grandparents' pointer to P. */ static inline void rotate_left (splay_tree_node *pp, splay_tree_node p, splay_tree_node n) @@ -120,7 +121,7 @@ rotate_left (splay_tree_node *pp, splay_tree_node p, splay_tree_node n) } /* Rotate the edge joining the right child N with its parent P. PP is the - grandparents pointer to P. */ + grandparents' pointer to P. */ static inline void rotate_right (splay_tree_node *pp, splay_tree_node p, splay_tree_node n) @@ -203,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 * @@ -265,13 +292,53 @@ 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. + +@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; @@ -313,10 +380,10 @@ splay_tree_insert (splay_tree sp, splay_tree_key key, splay_tree_value value) { /* 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; @@ -496,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. */