diff options
| -rw-r--r-- | gcc/ChangeLog | 26 | ||||
| -rw-r--r-- | gcc/typed-splay-tree.c | 3 | ||||
| -rw-r--r-- | gcc/typed-splay-tree.h | 544 |
3 files changed, 527 insertions, 46 deletions
diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 83e297e..c91c81e 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,29 @@ +2018-06-15 Bernd Edlinger <bernd.edlinger@hotmail.de> + + * typed-splay-tree.h (typed_splay_tree::remove): New function. + (typed_splay_tree::closure, + typed_splay_tree::inner_foreach_fn, typed_splay_tree::m_inner): Deleted. + (typed_splay_tree::typed_splay_tree, + typed_splay_tree::operator =): Declared private. + (typed_splay_tree::splay_tree_key, typed_splay_tree::splay_tree_value, + typed_splay_tree::splay_tree_node_s, typed_splay_tree::KDEL, + typed_splay_tree::VDEL, typed_splay_tree::splay_tree_delete_helper, + typed_splay_tree::rotate_left, typed_splay_tree::rotate_right, + typed_splay_tree::splay_tree_splay, + typed_splay_tree::splay_tree_foreach_helper, + typed_splay_tree::splay_tree_insert, + typed_splay_tree::splay_tree_remove, + typed_splay_tree::splay_tree_lookup, + typed_splay_tree::splay_tree_predecessor, + typed_splay_tree::splay_tree_successor, + typed_splay_tree::splay_tree_min, + typed_splay_tree::splay_tree_max): Took over from splay-tree.c/.h. + (typed_splay_tree::root, typed_splay_tree::comp, + typed_splay_tree::delete_key, + typed_splay_tree::delete_value): New data members. + * typed-splay-tree.c (selftest::test_str_to_int): Add a test for + typed_splay_tree::remove. + 2018-06-15 Matthew Fortune <matthew.fortune@mips.com> * config/mips/mips.h (ASM_SPEC): Pass through -mcrc, -mno-crc, diff --git a/gcc/typed-splay-tree.c b/gcc/typed-splay-tree.c index 5d3ffd7..344920f 100644 --- a/gcc/typed-splay-tree.c +++ b/gcc/typed-splay-tree.c @@ -47,6 +47,9 @@ test_str_to_int () t.insert ("a", 1); t.insert ("b", 2); t.insert ("c", 3); + t.insert ("d", 4); + + t.remove ("d"); ASSERT_EQ (1, t.lookup ("a")); ASSERT_EQ (2, t.lookup ("b")); diff --git a/gcc/typed-splay-tree.h b/gcc/typed-splay-tree.h index 95c2f5f..e8ba219 100644 --- a/gcc/typed-splay-tree.h +++ b/gcc/typed-splay-tree.h @@ -20,8 +20,6 @@ along with GCC; see the file COPYING3. If not see #ifndef GCC_TYPED_SPLAY_TREE_H #define GCC_TYPED_SPLAY_TREE_H -#include "splay-tree.h" - /* Typesafe wrapper around libiberty's splay-tree.h. */ template <typename KEY_TYPE, typename VALUE_TYPE> class typed_splay_tree @@ -44,27 +42,66 @@ class typed_splay_tree value_type predecessor (key_type k); value_type successor (key_type k); void insert (key_type k, value_type v); + void remove (key_type k); value_type max (); value_type min (); int foreach (foreach_fn, void *); private: - /* Helper type for typed_splay_tree::foreach. */ - struct closure - { - closure (foreach_fn outer_cb, void *outer_user_data) - : m_outer_cb (outer_cb), m_outer_user_data (outer_user_data) {} - - foreach_fn m_outer_cb; - void *m_outer_user_data; - }; + /* Copy and assignment ops are not supported. */ + typed_splay_tree (const typed_splay_tree &); + typed_splay_tree & operator = (const typed_splay_tree &); + + typedef key_type splay_tree_key; + typedef value_type splay_tree_value; + + /* The nodes in the splay tree. */ + struct splay_tree_node_s { + /* The key. */ + splay_tree_key key; + + /* The value. */ + splay_tree_value value; - static int inner_foreach_fn (splay_tree_node node, void *user_data); + /* The left and right children, respectively. */ + splay_tree_node_s *left, *right; + + /* Used as temporary value for tree traversals. */ + splay_tree_node_s *back; + }; + typedef splay_tree_node_s *splay_tree_node; + + inline void KDEL (splay_tree_key); + inline void VDEL (splay_tree_value); + void splay_tree_delete_helper (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); + void splay_tree_splay (splay_tree_key); + static int splay_tree_foreach_helper (splay_tree_node, + foreach_fn, void*); + splay_tree_node splay_tree_insert (splay_tree_key, splay_tree_value); + void splay_tree_remove (splay_tree_key key); + splay_tree_node splay_tree_lookup (splay_tree_key key); + splay_tree_node splay_tree_predecessor (splay_tree_key); + splay_tree_node splay_tree_successor (splay_tree_key); + splay_tree_node splay_tree_max (); + splay_tree_node splay_tree_min (); static value_type node_to_value (splay_tree_node node); - private: - ::splay_tree m_inner; + /* The root of the tree. */ + splay_tree_node root; + + /* The comparision function. */ + compare_fn comp; + + /* The deallocate-key function. NULL if no cleanup is necessary. */ + delete_key_fn delete_key; + + /* The deallocate-value function. NULL if no cleanup is necessary. */ + delete_value_fn delete_value; }; /* Constructor for typed_splay_tree <K, V>. */ @@ -75,12 +112,10 @@ inline typed_splay_tree<KEY_TYPE, VALUE_TYPE>:: delete_key_fn delete_key_fn, delete_value_fn delete_value_fn) { - m_inner = splay_tree_new ((splay_tree_compare_fn) - (void (*) (void)) compare_fn, - (splay_tree_delete_key_fn) - (void (*) (void)) delete_key_fn, - (splay_tree_delete_value_fn) - (void (*) (void)) delete_value_fn); + root = NULL; + comp = compare_fn; + delete_key = delete_key_fn; + delete_value = delete_value_fn; } /* Destructor for typed_splay_tree <K, V>. */ @@ -89,7 +124,7 @@ template <typename KEY_TYPE, typename VALUE_TYPE> inline typed_splay_tree<KEY_TYPE, VALUE_TYPE>:: ~typed_splay_tree () { - splay_tree_delete (m_inner); + splay_tree_delete_helper (root); } /* Lookup KEY, returning a value if present, and NULL @@ -99,7 +134,7 @@ template <typename KEY_TYPE, typename VALUE_TYPE> inline VALUE_TYPE typed_splay_tree<KEY_TYPE, VALUE_TYPE>::lookup (key_type key) { - splay_tree_node node = splay_tree_lookup (m_inner, (splay_tree_key)key); + splay_tree_node node = splay_tree_lookup (key); return node_to_value (node); } @@ -110,7 +145,7 @@ template <typename KEY_TYPE, typename VALUE_TYPE> inline VALUE_TYPE typed_splay_tree<KEY_TYPE, VALUE_TYPE>::predecessor (key_type key) { - splay_tree_node node = splay_tree_predecessor (m_inner, (splay_tree_key)key); + splay_tree_node node = splay_tree_predecessor (key); return node_to_value (node); } @@ -119,9 +154,9 @@ typed_splay_tree<KEY_TYPE, VALUE_TYPE>::predecessor (key_type key) template <typename KEY_TYPE, typename VALUE_TYPE> inline VALUE_TYPE -typed_splay_tree<KEY_TYPE, VALUE_TYPE>::successor (key_type k) +typed_splay_tree<KEY_TYPE, VALUE_TYPE>::successor (key_type key) { - splay_tree_node node = splay_tree_successor (m_inner, (splay_tree_key)k); + splay_tree_node node = splay_tree_successor (key); return node_to_value (node); } @@ -134,9 +169,16 @@ inline void typed_splay_tree<KEY_TYPE, VALUE_TYPE>::insert (key_type key, value_type value) { - splay_tree_insert (m_inner, - (splay_tree_key)key, - (splay_tree_value)value); + splay_tree_insert (key, value); +} + +/* Remove a node (associating KEY with VALUE). */ + +template <typename KEY_TYPE, typename VALUE_TYPE> +inline void +typed_splay_tree<KEY_TYPE, VALUE_TYPE>::remove (key_type key) +{ + splay_tree_remove (key); } /* Get the value with maximal key. */ @@ -145,7 +187,7 @@ template <typename KEY_TYPE, typename VALUE_TYPE> inline VALUE_TYPE typed_splay_tree<KEY_TYPE, VALUE_TYPE>::max () { - return node_to_value (splay_tree_max (m_inner)); + return node_to_value (splay_tree_max ()); } /* Get the value with minimal key. */ @@ -154,7 +196,7 @@ template <typename KEY_TYPE, typename VALUE_TYPE> inline VALUE_TYPE typed_splay_tree<KEY_TYPE, VALUE_TYPE>::min () { - return node_to_value (splay_tree_min (m_inner)); + return node_to_value (splay_tree_min ()); } /* Call OUTER_CB, passing it the OUTER_USER_DATA, for every node, @@ -164,37 +206,447 @@ typed_splay_tree<KEY_TYPE, VALUE_TYPE>::min () template <typename KEY_TYPE, typename VALUE_TYPE> inline int -typed_splay_tree<KEY_TYPE, VALUE_TYPE>::foreach (foreach_fn outer_cb, - void *outer_user_data) +typed_splay_tree<KEY_TYPE, VALUE_TYPE>::foreach (foreach_fn foreach_fn, + void *user_data) { - closure c (outer_cb, outer_user_data); + return splay_tree_foreach_helper (root, foreach_fn, user_data); +} - return splay_tree_foreach (m_inner, inner_foreach_fn, &c); +/* Internal function for converting from splay_tree_node to + VALUE_TYPE. */ +template <typename KEY_TYPE, typename VALUE_TYPE> +inline VALUE_TYPE +typed_splay_tree<KEY_TYPE, VALUE_TYPE>::node_to_value (splay_tree_node node) +{ + if (node) + return node->value; + else + return 0; } -/* Helper function for typed_splay_tree::foreach. */ +template <typename KEY_TYPE, typename VALUE_TYPE> +inline void +typed_splay_tree<KEY_TYPE, VALUE_TYPE>::KDEL(splay_tree_key x) +{ + if (delete_key) + (*delete_key)(x); +} + +template <typename KEY_TYPE, typename VALUE_TYPE> +inline void +typed_splay_tree<KEY_TYPE, VALUE_TYPE>::VDEL(splay_tree_value x) +{ + if (delete_value) + (*delete_value)(x); +} + +/* Deallocate NODE (a member of SP), and all its sub-trees. */ + +template <typename KEY_TYPE, typename VALUE_TYPE> +void +typed_splay_tree<KEY_TYPE, + VALUE_TYPE>::splay_tree_delete_helper (splay_tree_node node) +{ + splay_tree_node pending = NULL; + splay_tree_node active = NULL; + + if (!node) + return; + + KDEL (node->key); + VDEL (node->value); + + /* We use the "back" field to hold the "next" pointer. */ + node->back = pending; + pending = 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 = NULL; + 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 (active->left) + { + KDEL (active->left->key); + VDEL (active->left->value); + active->left->back = pending; + pending = active->left; + } + if (active->right) + { + KDEL (active->right->key); + VDEL (active->right->value); + active->right->back = pending; + pending = active->right; + } + + temp = active; + active = temp->back; + delete temp; + } + } +} + +/* Rotate the edge joining the left child N with its parent P. PP is the + grandparents' pointer to P. */ + +template <typename KEY_TYPE, typename VALUE_TYPE> +inline void +typed_splay_tree<KEY_TYPE, VALUE_TYPE>::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; +} + +/* Rotate the edge joining the right child N with its parent P. PP is the + grandparents' pointer to P. */ + +template <typename KEY_TYPE, typename VALUE_TYPE> +inline void +typed_splay_tree<KEY_TYPE, VALUE_TYPE>::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. */ + +template <typename KEY_TYPE, typename VALUE_TYPE> +void +typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_splay (splay_tree_key key) +{ + if (root == NULL) + return; + + do { + int cmp1, cmp2; + splay_tree_node n, c; + + n = root; + cmp1 = (*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 = (*comp) (key, c->key); + if (cmp2 == 0 + || (cmp2 < 0 && !c->left) + || (cmp2 > 0 && !c->right)) + { + if (cmp1 < 0) + rotate_left (&root, n, c); + else + rotate_right (&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 (&root, n, n->left); + } + else if (cmp1 > 0 && cmp2 > 0) + { + rotate_right (&n->right, c, c->right); + rotate_right (&root, n, n->right); + } + else if (cmp1 < 0 && cmp2 > 0) + { + rotate_right (&n->left, c, c->right); + rotate_left (&root, n, n->left); + } + else if (cmp1 > 0 && cmp2 < 0) + { + rotate_left (&n->right, c, c->left); + rotate_right (&root, n, n->right); + } + } while (1); +} + +/* Call FN, passing it the DATA, for every node below NODE, all of + which are from SP, following an in-order traversal. If FN every + returns a non-zero value, the iteration ceases immediately, and the + value is returned. Otherwise, this function returns 0. */ template <typename KEY_TYPE, typename VALUE_TYPE> int -typed_splay_tree<KEY_TYPE, VALUE_TYPE>::inner_foreach_fn (splay_tree_node node, - void *user_data) +typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_foreach_helper ( + splay_tree_node node, + foreach_fn fn, void *data) { - closure *c = (closure *)user_data; + int val; + splay_tree_node stack; + + /* 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. */ + + stack = NULL; + val = 0; + + for (;;) + { + while (node != NULL) + { + node->back = stack; + stack = node; + node = node->left; + } + + if (stack == NULL) + break; + + node = stack; + stack = stack->back; + + val = (*fn) (node->key, node->value, data); + if (val) + break; - return c->m_outer_cb ((KEY_TYPE)node->key, (VALUE_TYPE)node->value, - c->m_outer_user_data); + node = node->right; + } + + return val; } -/* Internal function for converting from splay_tree_node to - VALUE_TYPE. */ +/* Insert a new node (associating KEY with DATA) into SP. If a + previous node with the indicated KEY exists, its data is replaced + with the new value. Returns the new node. */ + template <typename KEY_TYPE, typename VALUE_TYPE> -inline VALUE_TYPE -typed_splay_tree<KEY_TYPE, VALUE_TYPE>::node_to_value (splay_tree_node node) +typename typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_node +typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_insert ( + splay_tree_key key, + splay_tree_value value) { - if (node) - return (value_type)node->value; + int comparison = 0; + + splay_tree_splay (key); + + if (root) + comparison = (*comp)(root->key, key); + + if (root && comparison == 0) + { + /* If the root of the tree already has the indicated KEY, just + replace the value with VALUE. */ + VDEL(root->value); + root->value = value; + } + else + { + /* Create a new node, and insert it at the root. */ + splay_tree_node node; + + node = new splay_tree_node_s; + node->key = key; + node->value = value; + + if (!root) + node->left = node->right = 0; + else if (comparison < 0) + { + node->left = root; + node->right = node->left->right; + node->left->right = 0; + } + else + { + node->right = root; + node->left = node->right->left; + node->right->left = 0; + } + + root = node; + } + + return root; +} + +/* Remove KEY from SP. It is not an error if it did not exist. */ + +template <typename KEY_TYPE, typename VALUE_TYPE> +void +typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_remove (splay_tree_key key) +{ + splay_tree_splay (key); + + if (root && (*comp) (root->key, key) == 0) + { + splay_tree_node left, right; + + left = root->left; + right = root->right; + + /* Delete the root node itself. */ + VDEL (root->value); + delete root; + + /* 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) + { + 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 + root = right; + } +} + +/* Lookup KEY in SP, returning VALUE if present, and NULL + otherwise. */ + +template <typename KEY_TYPE, typename VALUE_TYPE> +typename typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_node +typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_lookup (splay_tree_key key) +{ + splay_tree_splay (key); + + if (root && (*comp)(root->key, key) == 0) + return root; else return 0; } +/* Return the node in SP with the greatest key. */ + +template <typename KEY_TYPE, typename VALUE_TYPE> +typename typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_node +typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_max () +{ + splay_tree_node n = root; + + if (!n) + return NULL; + + while (n->right) + n = n->right; + + return n; +} + +/* Return the node in SP with the smallest key. */ + +template <typename KEY_TYPE, typename VALUE_TYPE> +typename typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_node +typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_min () +{ + splay_tree_node n = 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. */ + +template <typename KEY_TYPE, typename VALUE_TYPE> +typename typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_node +typed_splay_tree<KEY_TYPE, + VALUE_TYPE>::splay_tree_predecessor (splay_tree_key key) +{ + int comparison; + splay_tree_node node; + + /* If the tree is empty, there is certainly no predecessor. */ + if (!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 (key); + comparison = (*comp)(root->key, key); + + /* If the predecessor is at the root, just return it. */ + if (comparison < 0) + return root; + + /* Otherwise, find the rightmost element of the left subtree. */ + node = 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. */ + +template <typename KEY_TYPE, typename VALUE_TYPE> +typename typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_node +typed_splay_tree<KEY_TYPE, + VALUE_TYPE>::splay_tree_successor (splay_tree_key key) +{ + int comparison; + splay_tree_node node; + + /* If the tree is empty, there is certainly no successor. */ + if (!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 (key); + comparison = (*comp)(root->key, key); + + /* If the successor is at the root, just return it. */ + if (comparison > 0) + return root; + + /* Otherwise, find the leftmost element of the right subtree. */ + node = root->right; + if (node) + while (node->left) + node = node->left; + + return node; +} + #endif /* GCC_TYPED_SPLAY_TREE_H */ |