X-Git-Url: http://git.sourceforge.jp/view?a=blobdiff_plain;f=libiberty%2Fsplay-tree.c;h=fc98db167f329eaf4083b6c5dd480b1fa75b2959;hb=43b3dabf44ee42b616059be92c4bddd136af6701;hp=22ea07d84adb5eada30579685da96e21d99f6841;hpb=b04bbebba35dcf57b50dd6fbb658bf79768f9187;p=pf3gnuchains%2Fgcc-fork.git diff --git a/libiberty/splay-tree.c b/libiberty/splay-tree.c index 22ea07d84ad..fc98db167f3 100644 --- a/libiberty/splay-tree.c +++ b/libiberty/splay-tree.c @@ -1,5 +1,5 @@ /* A splay-tree datatype. - Copyright (C) 1998, 1999 Free Software Foundation, Inc. + Copyright (C) 1998, 1999, 2000, 2001 Free Software Foundation, Inc. Contributed by Mark Mitchell (mark@markmitchell.com). This file is part of GNU CC. @@ -32,6 +32,8 @@ Boston, MA 02111-1307, USA. */ #include #endif +#include + #include "libiberty.h" #include "splay-tree.h" @@ -68,7 +70,7 @@ splay_tree_delete_helper (sp, node) if (sp->delete_value) (*sp->delete_value)(node->value); - free ((char*) node); + (*sp->deallocate) ((char*) node, sp->allocate_data); } /* Help splay SP around KEY. PARENT and GRANDPARENT are the parent @@ -225,9 +227,29 @@ splay_tree_foreach_helper (sp, node, fn, data) return splay_tree_foreach_helper (sp, node->right, fn, data); } + +/* An allocator and deallocator based on xmalloc. */ +static void * +splay_tree_xmalloc_allocate (size, data) + int size; + void *data ATTRIBUTE_UNUSED; +{ + return (void *) xmalloc (size); +} + +static void +splay_tree_xmalloc_deallocate (object, data) + void *object; + void *data ATTRIBUTE_UNUSED; +{ + free (object); +} + + /* Allocate a new splay tree, using COMPARE_FN to compare nodes, DELETE_KEY_FN to deallocate keys, and DELETE_VALUE_FN to deallocate - values. */ + values. Use xmalloc to allocate the splay tree structure, and any + nodes added. */ splay_tree splay_tree_new (compare_fn, delete_key_fn, delete_value_fn) @@ -235,11 +257,35 @@ splay_tree_new (compare_fn, delete_key_fn, delete_value_fn) splay_tree_delete_key_fn delete_key_fn; splay_tree_delete_value_fn delete_value_fn; { - splay_tree sp = (splay_tree) xmalloc (sizeof (struct splay_tree_s)); + 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_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 sp = (splay_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->deallocate = deallocate_fn; + sp->allocate_data = allocate_data; return sp; } @@ -251,7 +297,7 @@ splay_tree_delete (sp) 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 @@ -284,7 +330,9 @@ splay_tree_insert (sp, key, value) /* 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; @@ -303,12 +351,53 @@ splay_tree_insert (sp, key, value) node->right->left = 0; } - sp->root = node; - } + sp->root = node; + } return sp->root; } +/* 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_splay (sp, key); + + if (sp->root && (*sp->comp) (sp->root->key, key) == 0) + { + splay_tree_node left, right; + + left = sp->root->left; + right = sp->root->right; + + /* Delete the root node itself. */ + if (sp->delete_value) + (*sp->delete_value) (sp->root->value); + (*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. */ + if (left) + { + sp->root = left; + + /* If there was a right child as well, hang it off the + right-most leaf of the left child. */ + if (right) + { + while (left->right) + left = left->right; + left->right = right; + } + } + else + sp->root = right; + } +} + /* Lookup KEY in SP, returning VALUE if present, and NULL otherwise. */ @@ -325,6 +414,106 @@ splay_tree_lookup (sp, key) return 0; } +/* Return the node in SP with the greatest key. */ + +splay_tree_node +splay_tree_max (sp) + splay_tree sp; +{ + splay_tree_node n = sp->root; + + if (!n) + return NULL; + + while (n->right) + n = n->right; + + return n; +} + +/* Return the node in SP with the smallest key. */ + +splay_tree_node +splay_tree_min (sp) + splay_tree sp; +{ + splay_tree_node n = sp->root; + + if (!n) + return NULL; + + while (n->left) + n = n->left; + + return n; +} + +/* Return the immediate predecessor KEY, or NULL if there is no + predecessor. KEY need not be present in the tree. */ + +splay_tree_node +splay_tree_predecessor (sp, key) + splay_tree sp; + splay_tree_key key; +{ + int comparison; + splay_tree_node node; + + /* If the tree is empty, there is certainly no predecessor. */ + if (!sp->root) + return NULL; + + /* Splay the tree around KEY. That will leave either the KEY + itself, its predecessor, or its successor at the root. */ + splay_tree_splay (sp, key); + comparison = (*sp->comp)(sp->root->key, key); + + /* If the predecessor is at the root, just return it. */ + if (comparison < 0) + return sp->root; + + /* Otherwise, find the rightmost element of the left subtree. */ + node = sp->root->left; + if (node) + while (node->right) + node = node->right; + + return node; +} + +/* Return the immediate successor KEY, or NULL if there is no + successor. KEY need not be present in the tree. */ + +splay_tree_node +splay_tree_successor (sp, key) + splay_tree sp; + splay_tree_key key; +{ + int comparison; + splay_tree_node node; + + /* If the tree is empty, there is certainly no successor. */ + if (!sp->root) + return NULL; + + /* Splay the tree around KEY. That will leave either the KEY + itself, its predecessor, or its successor at the root. */ + splay_tree_splay (sp, key); + comparison = (*sp->comp)(sp->root->key, key); + + /* If the successor is at the root, just return it. */ + if (comparison > 0) + return sp->root; + + /* Otherwise, find the leftmost element of the right subtree. */ + node = sp->root->right; + if (node) + while (node->left) + node = node->left; + + return node; +} + /* Call FN, passing it the DATA, for every node in SP, following an in-order traversal. If FN every returns a non-zero value, the iteration ceases immediately, and the value is returned.