typed-splay-tree.h

Go to the documentation of this file.

/* A typesafe wrapper around libiberty's splay-tree.h.
   Copyright (C) 2015-2024 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  */