| /* A typesafe wrapper around libiberty's splay-tree.h. |
| Copyright (C) 2015-2022 Free Software Foundation, Inc. |
| |
| This file is part of GCC. |
| |
| GCC is free software; you can redistribute it and/or modify it under |
| the terms of the GNU General Public License as published by the Free |
| Software Foundation; either version 3, or (at your option) any later |
| version. |
| |
| GCC is distributed in the hope that it will be useful, but WITHOUT ANY |
| WARRANTY; without even the implied warranty of MERCHANTABILITY or |
| FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
| for more details. |
| |
| You should have received a copy of the GNU General Public License |
| along with GCC; see the file COPYING3. If not see |
| <http://www.gnu.org/licenses/>. */ |
| |
| #ifndef GCC_TYPED_SPLAY_TREE_H |
| #define GCC_TYPED_SPLAY_TREE_H |
| |
| /* Typesafe wrapper around libiberty's splay-tree.h. */ |
| template <typename KEY_TYPE, typename VALUE_TYPE> |
| class typed_splay_tree |
| { |
| public: |
| typedef KEY_TYPE key_type; |
| typedef VALUE_TYPE value_type; |
| |
| typedef int (*compare_fn) (key_type, key_type); |
| typedef void (*delete_key_fn) (key_type); |
| typedef void (*delete_value_fn) (value_type); |
| typedef int (*foreach_fn) (key_type, value_type, void *); |
| |
| typed_splay_tree (compare_fn, |
| delete_key_fn, |
| delete_value_fn); |
| ~typed_splay_tree (); |
| |
| value_type lookup (key_type k); |
| 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: |
| /* 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; |
| |
| /* 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); |
| |
| /* 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>. */ |
| |
| template <typename KEY_TYPE, typename VALUE_TYPE> |
| inline typed_splay_tree<KEY_TYPE, VALUE_TYPE>:: |
| typed_splay_tree (compare_fn compare_fn, |
| delete_key_fn delete_key_fn, |
| delete_value_fn 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>. */ |
| |
| template <typename KEY_TYPE, typename VALUE_TYPE> |
| inline typed_splay_tree<KEY_TYPE, VALUE_TYPE>:: |
| ~typed_splay_tree () |
| { |
| splay_tree_delete_helper (root); |
| } |
| |
| /* Lookup KEY, returning a value if present, and NULL |
| otherwise. */ |
| |
| 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 (key); |
| return node_to_value (node); |
| } |
| |
| /* Return the immediate predecessor of KEY, or NULL if there is no |
| predecessor. KEY need not be present in the tree. */ |
| |
| 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 (key); |
| return node_to_value (node); |
| } |
| |
| /* Return the immediate successor of KEY, or NULL if there is no |
| successor. KEY need not be present in the tree. */ |
| |
| template <typename KEY_TYPE, typename VALUE_TYPE> |
| inline VALUE_TYPE |
| typed_splay_tree<KEY_TYPE, VALUE_TYPE>::successor (key_type key) |
| { |
| splay_tree_node node = splay_tree_successor (key); |
| return node_to_value (node); |
| } |
| |
| /* Insert a new node (associating KEY with VALUE). If a |
| previous node with the indicated KEY exists, its data is replaced |
| with the new value. */ |
| |
| template <typename KEY_TYPE, typename VALUE_TYPE> |
| inline void |
| typed_splay_tree<KEY_TYPE, VALUE_TYPE>::insert (key_type key, |
| value_type 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. */ |
| |
| 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 ()); |
| } |
| |
| /* Get the value with minimal key. */ |
| |
| 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 ()); |
| } |
| |
| /* Call OUTER_CB, passing it the OUTER_USER_DATA, for every node, |
| following an in-order traversal. If OUTER_CB ever 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> |
| inline int |
| typed_splay_tree<KEY_TYPE, VALUE_TYPE>::foreach (foreach_fn foreach_fn, |
| void *user_data) |
| { |
| return splay_tree_foreach_helper (root, foreach_fn, user_data); |
| } |
| |
| /* 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; |
| } |
| |
| 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>::splay_tree_foreach_helper ( |
| splay_tree_node node, |
| foreach_fn fn, void *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; |
| |
| node = node->right; |
| } |
| |
| return val; |
| } |
| |
| /* 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> |
| 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) |
| { |
| 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 */ |