CbC/CbC_gcc: gcc/typed-splay-tree.h comparison

comparison gcc/typed-splay-tree.h @ 132:d34655255c78

update gcc-8.2

author	mir3636
date	Thu, 25 Oct 2018 10:21:07 +0900
parents	84e7813d76e9
children	1830386684a0

comparison

equal deleted inserted replaced

-:e108057fa461
+:d34655255c78
 /* A typesafe wrapper around libiberty's splay-tree.h.
-Copyright (C) 2015-2017 Free Software Foundation, Inc.
+Copyright (C) 2015-2018 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
 <http://www.gnu.org/licenses/>.  */
 #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
 {
 public:
 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:
-/* Helper type for typed_splay_tree::foreach.  */
+/* Copy and assignment ops are not supported.  */
-struct closure
+typed_splay_tree (const typed_splay_tree &);
-{
+typed_splay_tree & operator = (const typed_splay_tree &);
-closure (foreach_fn outer_cb, void *outer_user_data)
-: m_outer_cb (outer_cb), m_outer_user_data (outer_user_data) {}
+typedef key_type splay_tree_key;
+typedef value_type splay_tree_value;
-foreach_fn m_outer_cb;
-void *m_outer_user_data;
+/* 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;
-static int inner_foreach_fn (splay_tree_node node, void *user_data);
+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:
+/* The root of the tree.  */
-::splay_tree m_inner;
+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)
 {
-m_inner = splay_tree_new ((splay_tree_compare_fn)compare_fn,
+root = NULL;
-			    (splay_tree_delete_key_fn)delete_key_fn,
+comp = compare_fn;
-			    (splay_tree_delete_value_fn)delete_value_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 (m_inner);
+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 (m_inner, (splay_tree_key)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 (m_inner, (splay_tree_key)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 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);
 }
 /* Insert a new node (associating KEY with VALUE).  If a
 previous node with the indicated KEY exists, its data is replaced
 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 (m_inner,
+splay_tree_insert (key, value);
-		     (splay_tree_key)key,
+}
-		     (splay_tree_value)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 (m_inner));
+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 (m_inner));
+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 outer_cb,
+typed_splay_tree<KEY_TYPE, VALUE_TYPE>::foreach (foreach_fn foreach_fn,
-						 void *outer_user_data)
+						 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);
-}
-/* Helper function for typed_splay_tree::foreach.  */
-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)
-{
-closure *c = (closure *)user_data;
-return c->m_outer_cb ((KEY_TYPE)node->key, (VALUE_TYPE)node->value,
-			c->m_outer_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 (value_type)node->value;
+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  */

Mercurial > hg > CbC > CbC_gcc

comparison gcc/typed-splay-tree.h @ 132:d34655255c78