gcc/typed-splay-tree.h

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