gcc/typed-splay-tree.h

   1 /* A typesafe wrapper around libiberty's splay-tree.h.
   2    Copyright (C) 2015-2017 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   typedef int (*foreach_fn) (key_type, value_type, void *);
  37
  38   typed_splay_tree (compare_fn,
  39                     delete_key_fn,
  40                     delete_value_fn);
  41   ~typed_splay_tree ();
  42
  43   value_type lookup (key_type k);
  44   value_type predecessor (key_type k);
  45   value_type successor (key_type k);
  46   void insert (key_type k, value_type v);
  47   value_type max ();
  48   value_type min ();
  49   int foreach (foreach_fn, void *);
  50
  51  private:
  52   /* Helper type for typed_splay_tree::foreach.  */
  53   struct closure
  54   {
  55     closure (foreach_fn outer_cb, void *outer_user_data)
  56     : m_outer_cb (outer_cb), m_outer_user_data (outer_user_data) {}
  57
  58     foreach_fn m_outer_cb;
  59     void *m_outer_user_data;
  60   };
  61
  62   static int inner_foreach_fn (splay_tree_node node, void *user_data);
  63
  64   static value_type node_to_value (splay_tree_node node);
  65
  66  private:
  67   ::splay_tree m_inner;
  68 };
  69
  70 /* Constructor for typed_splay_tree <K, V>.  */
  71
  72 template <typename KEY_TYPE, typename VALUE_TYPE>
  73 inline typed_splay_tree<KEY_TYPE, VALUE_TYPE>::
  74   typed_splay_tree (compare_fn compare_fn,
  75                     delete_key_fn delete_key_fn,
  76                     delete_value_fn delete_value_fn)
  77 {
  78   m_inner = splay_tree_new ((splay_tree_compare_fn)compare_fn,
  79                             (splay_tree_delete_key_fn)delete_key_fn,
  80                             (splay_tree_delete_value_fn)delete_value_fn);
  81 }
  82
  83 /* Destructor for typed_splay_tree <K, V>.  */
  84
  85 template <typename KEY_TYPE, typename VALUE_TYPE>
  86 inline typed_splay_tree<KEY_TYPE, VALUE_TYPE>::
  87   ~typed_splay_tree ()
  88 {
  89   splay_tree_delete (m_inner);
  90 }
  91
  92 /* Lookup KEY, returning a value if present, and NULL
  93    otherwise.  */
  94
  95 template <typename KEY_TYPE, typename VALUE_TYPE>
  96 inline VALUE_TYPE
  97 typed_splay_tree<KEY_TYPE, VALUE_TYPE>::lookup (key_type key)
  98 {
  99   splay_tree_node node = splay_tree_lookup (m_inner, (splay_tree_key)key);
 100   return node_to_value (node);
 101 }
 102
 103 /* Return the immediate predecessor of KEY, or NULL if there is no
 104    predecessor.  KEY need not be present in the tree.  */
 105
 106 template <typename KEY_TYPE, typename VALUE_TYPE>
 107 inline VALUE_TYPE
 108 typed_splay_tree<KEY_TYPE, VALUE_TYPE>::predecessor (key_type key)
 109 {
 110   splay_tree_node node = splay_tree_predecessor (m_inner, (splay_tree_key)key);
 111   return node_to_value (node);
 112 }
 113
 114 /* Return the immediate successor of KEY, or NULL if there is no
 115    successor.  KEY need not be present in the tree.  */
 116
 117 template <typename KEY_TYPE, typename VALUE_TYPE>
 118 inline VALUE_TYPE
 119 typed_splay_tree<KEY_TYPE, VALUE_TYPE>::successor (key_type k)
 120 {
 121   splay_tree_node node = splay_tree_successor (m_inner, (splay_tree_key)k);
 122   return node_to_value (node);
 123 }
 124
 125 /* Insert a new node (associating KEY with VALUE).  If a
 126    previous node with the indicated KEY exists, its data is replaced
 127    with the new value.  */
 128
 129 template <typename KEY_TYPE, typename VALUE_TYPE>
 130 inline void
 131 typed_splay_tree<KEY_TYPE, VALUE_TYPE>::insert (key_type key,
 132                                                 value_type value)
 133 {
 134   splay_tree_insert (m_inner,
 135                      (splay_tree_key)key,
 136                      (splay_tree_value)value);
 137 }
 138
 139 /* Get the value with maximal key.  */
 140
 141 template <typename KEY_TYPE, typename VALUE_TYPE>
 142 inline VALUE_TYPE
 143 typed_splay_tree<KEY_TYPE, VALUE_TYPE>::max ()
 144 {
 145   return node_to_value (splay_tree_max (m_inner));
 146 }
 147
 148 /* Get the value with minimal key.  */
 149
 150 template <typename KEY_TYPE, typename VALUE_TYPE>
 151 inline VALUE_TYPE
 152 typed_splay_tree<KEY_TYPE, VALUE_TYPE>::min ()
 153 {
 154   return node_to_value (splay_tree_min (m_inner));
 155 }
 156
 157 /* Call OUTER_CB, passing it the OUTER_USER_DATA, for every node,
 158    following an in-order traversal.  If OUTER_CB ever returns a non-zero
 159    value, the iteration ceases immediately, and the value is returned.
 160    Otherwise, this function returns 0.  */
 161
 162 template <typename KEY_TYPE, typename VALUE_TYPE>
 163 inline int
 164 typed_splay_tree<KEY_TYPE, VALUE_TYPE>::foreach (foreach_fn outer_cb,
 165                                                  void *outer_user_data)
 166 {
 167   closure c (outer_cb, outer_user_data);
 168
 169   return splay_tree_foreach (m_inner, inner_foreach_fn, &c);
 170 }
 171
 172 /* Helper function for typed_splay_tree::foreach.  */
 173
 174 template <typename KEY_TYPE, typename VALUE_TYPE>
 175 int
 176 typed_splay_tree<KEY_TYPE, VALUE_TYPE>::inner_foreach_fn (splay_tree_node node,
 177                                                           void *user_data)
 178 {
 179   closure *c = (closure *)user_data;
 180
 181   return c->m_outer_cb ((KEY_TYPE)node->key, (VALUE_TYPE)node->value,
 182                         c->m_outer_user_data);
 183 }
 184
 185 /* Internal function for converting from splay_tree_node to
 186    VALUE_TYPE.  */
 187 template <typename KEY_TYPE, typename VALUE_TYPE>
 188 inline VALUE_TYPE
 189 typed_splay_tree<KEY_TYPE, VALUE_TYPE>::node_to_value (splay_tree_node node)
 190 {
 191   if (node)
 192     return (value_type)node->value;
 193   else
 194     return 0;
 195 }
 196
 197 #endif  /* GCC_TYPED_SPLAY_TREE_H  */