X-Git-Url: http://git.efficios.com/?a=blobdiff_plain;f=libiberty%2Fsplay-tree.c;h=311b49edffbcf011f88993fd7d553fdd80a19e35;hb=f2942ea4dd6da2fb288214764c0be02e859d4177;hp=7999447bc11022037536c056cd96f5661de92992;hpb=3ddbd84c49e7b450704e5d88d96da2ded31a5b01;p=deliverable%2Fbinutils-gdb.git diff --git a/libiberty/splay-tree.c b/libiberty/splay-tree.c index 7999447bc1..311b49edff 100644 --- a/libiberty/splay-tree.c +++ b/libiberty/splay-tree.c @@ -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: @@ -37,52 +37,83 @@ Boston, MA 02111-1307, USA. */ #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, +static void splay_tree_delete_helper (splay_tree, splay_tree_node); +static void splay_tree_splay (splay_tree, splay_tree_key); +static splay_tree_node splay_tree_splay_helper (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*)); + splay_tree_node*); +static int splay_tree_foreach_helper (splay_tree, 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); +#define KDEL(x) if (sp->delete_key) (*sp->delete_key)(x); +#define VDEL(x) if (sp->delete_value) (*sp->delete_value)(x); + + KDEL (node->key); + VDEL (node->value); + + /* We use the "key" field to hold the "next" pointer. */ + node->key = (splay_tree_key)pending; + pending = (splay_tree_node)node; + + /* 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. */ + + while (pending) + { + active = pending; + pending = 0; + while (active) + { + splay_tree_node temp; + + /* active points to a node which has its key and value + deallocated, we just need to process left and right. */ - if (sp->delete_key) - (*sp->delete_key)(node->key); - if (sp->delete_value) - (*sp->delete_value)(node->value); + 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); + } - (*sp->deallocate) ((char*) node, sp->allocate_data); + temp = active; + active = (splay_tree_node)(temp->key); + (*sp->deallocate) ((char*) temp, sp->allocate_data); + } + } +#undef KDEL +#undef VDEL } /* Help splay SP around KEY. PARENT and GRANDPARENT are the parent and grandparent, respectively, of 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_splay_helper (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; @@ -188,9 +219,7 @@ splay_tree_splay_helper (sp, key, node, parent, grandparent) /* Splay SP around 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; @@ -205,11 +234,8 @@ 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 sp, splay_tree_node node, + splay_tree_foreach_fn fn, void *data) { int val; @@ -230,17 +256,13 @@ splay_tree_foreach_helper (sp, node, fn, data) /* An allocator and deallocator based on xmalloc. */ static void * -splay_tree_xmalloc_allocate (size, data) - int size; - void *data ATTRIBUTE_UNUSED; +splay_tree_xmalloc_allocate (int size, void *data ATTRIBUTE_UNUSED) { - return xmalloc (size); + return (void *) xmalloc (size); } static void -splay_tree_xmalloc_deallocate (object, data) - void *object; - void *data ATTRIBUTE_UNUSED; +splay_tree_xmalloc_deallocate (void *object, void *data ATTRIBUTE_UNUSED) { free (object); } @@ -252,10 +274,9 @@ splay_tree_xmalloc_deallocate (object, data) nodes added. */ 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 (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, @@ -268,14 +289,12 @@ splay_tree_new (compare_fn, delete_key_fn, delete_value_fn) values. */ splay_tree -splay_tree_new_with_allocator (compare_fn, delete_key_fn, delete_value_fn, - allocate_fn, deallocate_fn, allocate_data) - 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_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) (*allocate_fn) (sizeof (struct splay_tree_s), allocate_data); @@ -293,8 +312,7 @@ splay_tree_new_with_allocator (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); (*sp->deallocate) ((char*) sp, sp->allocate_data); @@ -305,10 +323,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; @@ -360,9 +375,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); @@ -402,9 +415,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); @@ -417,8 +428,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; @@ -434,8 +444,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; @@ -452,9 +461,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; @@ -472,7 +479,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) @@ -482,17 +489,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; @@ -505,7 +510,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) @@ -520,10 +525,7 @@ 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); } @@ -531,9 +533,7 @@ splay_tree_foreach (sp, 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; @@ -546,9 +546,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;