gcc/typed-splay-tree.h

   1 /* A typesafe wrapper around libiberty's splay-tree.h.
   2    Copyright (C) 2015-2016 Free Software Foundation, Inc.
   3
   4 This file is part of GCC.
   5
   6 GCC is free software; you can redistribute it and/or modify it under
   7 the terms of the GNU General Public License as published by the Free
   8 Software Foundation; either version 3, or (at your option) any later
   9 version.
  10
  11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14 for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GCC; see the file COPYING3.  If not see
  18 <http://www.gnu.org/licenses/>.  */
  19
  20 #ifndef GCC_TYPED_SPLAY_TREE_H
  21 #define GCC_TYPED_SPLAY_TREE_H
  22
  23 #include "splay-tree.h"
  24
  25 /* Typesafe wrapper around libiberty's splay-tree.h.  */
  26 template <typename KEY_TYPE, typename VALUE_TYPE>
  27 class typed_splay_tree
  28 {
  29  public:
  30   typedef KEY_TYPE key_type;
  31   typedef VALUE_TYPE value_type;
  32
  33   typedef int (*compare_fn) (key_type, key_type);
  34   typedef void (*delete_key_fn) (key_type);
  35   typedef void (*delete_value_fn) (value_type);
  36
  37   typed_splay_tree (compare_fn,
  38                     delete_key_fn,
  39                     delete_value_fn);
  40   ~typed_splay_tree ();
  41
  42   value_type lookup (key_type k);
  43   value_type predecessor (key_type k);
  44   value_type successor (key_type k);
  45   void insert (key_type k, value_type v);
  46
  47  private:
  48   static value_type node_to_value (splay_tree_node node);
  49
  50  private:
  51   ::splay_tree m_inner;
  52 };
  53
  54 /* Constructor for typed_splay_tree <K, V>.  */
  55
  56 template <typename KEY_TYPE, typename VALUE_TYPE>
  57 inline typed_splay_tree<KEY_TYPE, VALUE_TYPE>::
  58   typed_splay_tree (compare_fn compare_fn,
  59                     delete_key_fn delete_key_fn,
  60                     delete_value_fn delete_value_fn)
  61 {
  62   m_inner = splay_tree_new ((splay_tree_compare_fn)compare_fn,
  63                             (splay_tree_delete_key_fn)delete_key_fn,
  64                             (splay_tree_delete_value_fn)delete_value_fn);
  65 }
  66
  67 /* Destructor for typed_splay_tree <K, V>.  */
  68
  69 template <typename KEY_TYPE, typename VALUE_TYPE>
  70 inline typed_splay_tree<KEY_TYPE, VALUE_TYPE>::
  71   ~typed_splay_tree ()
  72 {
  73   splay_tree_delete (m_inner);
  74 }
  75
  76 /* Lookup KEY, returning a value if present, and NULL
  77    otherwise.  */
  78
  79 template <typename KEY_TYPE, typename VALUE_TYPE>
  80 inline VALUE_TYPE
  81 typed_splay_tree<KEY_TYPE, VALUE_TYPE>::lookup (key_type key)
  82 {
  83   splay_tree_node node = splay_tree_lookup (m_inner, (splay_tree_key)key);
  84   return node_to_value (node);
  85 }
  86
  87 /* Return the immediate predecessor of KEY, or NULL if there is no
  88    predecessor.  KEY need not be present in the tree.  */
  89
  90 template <typename KEY_TYPE, typename VALUE_TYPE>
  91 inline VALUE_TYPE
  92 typed_splay_tree<KEY_TYPE, VALUE_TYPE>::predecessor (key_type key)
  93 {
  94   splay_tree_node node = splay_tree_predecessor (m_inner, (splay_tree_key)key);
  95   return node_to_value (node);
  96 }
  97
  98 /* Return the immediate successor of KEY, or NULL if there is no
  99    successor.  KEY need not be present in the tree.  */
 100
 101 template <typename KEY_TYPE, typename VALUE_TYPE>
 102 inline VALUE_TYPE
 103 typed_splay_tree<KEY_TYPE, VALUE_TYPE>::successor (key_type k)
 104 {
 105   splay_tree_node node = splay_tree_successor (m_inner, (splay_tree_key)k);
 106   return node_to_value (node);
 107 }
 108
 109 /* Insert a new node (associating KEY with VALUE).  If a
 110    previous node with the indicated KEY exists, its data is replaced
 111    with the new value.  */
 112
 113 template <typename KEY_TYPE, typename VALUE_TYPE>
 114 inline void
 115 typed_splay_tree<KEY_TYPE, VALUE_TYPE>::insert (key_type key,
 116                                                 value_type value)
 117 {
 118   splay_tree_insert (m_inner,
 119                      (splay_tree_key)key,
 120                      (splay_tree_value)value);
 121 }
 122
 123 /* Internal function for converting from splay_tree_node to
 124    VALUE_TYPE.  */
 125 template <typename KEY_TYPE, typename VALUE_TYPE>
 126 inline VALUE_TYPE
 127 typed_splay_tree<KEY_TYPE, VALUE_TYPE>::node_to_value (splay_tree_node node)
 128 {
 129   if (node)
 130     return (value_type)node->value;
 131   else
 132     return 0;
 133 }
 134
 135 #endif  /* GCC_TYPED_SPLAY_TREE_H  */