gcc/hash-map-traits.h

   1 /* A hash map traits.
   2    Copyright (C) 2015 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 HASH_MAP_TRAITS_H
  21 #define HASH_MAP_TRAITS_H
  22
  23 /* Bacause mem-stats.h uses default hashmap traits, we have to
  24    put the class to this separate header file.  */
  25
  26 #include "hash-traits.h"
  27
  28 /* implement default behavior for traits when types allow it.  */
  29
  30 struct default_hashmap_traits
  31 {
  32   /* Hashes the passed in key.  */
  33
  34   template<typename T>
  35   static hashval_t
  36   hash (T *p)
  37     {
  38       return uintptr_t (p) >> 3;
  39     }
  40
  41   /* If the value converts to hashval_t just use it.  */
  42
  43   template<typename T> static hashval_t hash (T v) { return v; }
  44
  45   /* Return true if the two keys passed as arguments are equal.  */
  46
  47   template<typename T>
  48   static bool
  49   equal_keys (const T &a, const T &b)
  50     {
  51       return a == b;
  52     }
  53
  54   /* Called to dispose of the key and value before marking the entry as
  55      deleted.  */
  56
  57   template<typename T> static void remove (T &v) { v.~T (); }
  58
  59   /* Mark the passed in entry as being deleted.  */
  60
  61   template<typename T>
  62   static void
  63   mark_deleted (T &e)
  64     {
  65       mark_key_deleted (e.m_key);
  66     }
  67
  68   /* Mark the passed in entry as being empty.  */
  69
  70   template<typename T>
  71   static void
  72   mark_empty (T &e)
  73     {
  74       mark_key_empty (e.m_key);
  75     }
  76
  77   /* Return true if the passed in entry is marked as deleted.  */
  78
  79   template<typename T>
  80   static bool
  81   is_deleted (T &e)
  82     {
  83       return e.m_key == (void *)1;
  84     }
  85
  86   /* Return true if the passed in entry is marked as empty.  */
  87
  88   template<typename T> static bool is_empty (T &e) { return e.m_key == NULL; }
  89
  90 private:
  91   template<typename T>
  92   static void
  93   mark_key_deleted (T *&k)
  94     {
  95       k = reinterpret_cast<T *> (1);
  96     }
  97
  98   template<typename T>
  99   static void
 100   mark_key_empty (T *&k)
 101     {
 102       k = static_cast<T *> (0);
 103     }
 104 };
 105
 106 /* Implement hash_map traits for a key with hash traits H.  Empty and
 107    deleted map entries are represented as empty and deleted keys.  */
 108
 109 template <typename H>
 110 struct simple_hashmap_traits
 111 {
 112   static inline hashval_t hash (const typename H::value_type &);
 113   static inline bool equal_keys (const typename H::value_type &,
 114                                  const typename H::value_type &);
 115   template <typename T> static inline void remove (T &);
 116   template <typename T> static inline bool is_empty (const T &);
 117   template <typename T> static inline bool is_deleted (const T &);
 118   template <typename T> static inline void mark_empty (T &);
 119   template <typename T> static inline void mark_deleted (T &);
 120 };
 121
 122 template <typename H>
 123 inline hashval_t
 124 simple_hashmap_traits <H>::hash (const typename H::value_type &h)
 125 {
 126   return H::hash (h);
 127 }
 128
 129 template <typename H>
 130 inline bool
 131 simple_hashmap_traits <H>::equal_keys (const typename H::value_type &k1,
 132                                        const typename H::value_type &k2)
 133 {
 134   return H::equal (k1, k2);
 135 }
 136
 137 template <typename H>
 138 template <typename T>
 139 inline void
 140 simple_hashmap_traits <H>::remove (T &entry)
 141 {
 142   H::remove (entry.m_key);
 143 }
 144
 145 template <typename H>
 146 template <typename T>
 147 inline bool
 148 simple_hashmap_traits <H>::is_empty (const T &entry)
 149 {
 150   return H::is_empty (entry.m_key);
 151 }
 152
 153 template <typename H>
 154 template <typename T>
 155 inline bool
 156 simple_hashmap_traits <H>::is_deleted (const T &entry)
 157 {
 158   return H::is_deleted (entry.m_key);
 159 }
 160
 161 template <typename H>
 162 template <typename T>
 163 inline void
 164 simple_hashmap_traits <H>::mark_empty (T &entry)
 165 {
 166   H::mark_empty (entry.m_key);
 167 }
 168
 169 template <typename H>
 170 template <typename T>
 171 inline void
 172 simple_hashmap_traits <H>::mark_deleted (T &entry)
 173 {
 174   H::mark_deleted (entry.m_key);
 175 }
 176
 177 /* Implement traits for a hash_map with values of type Value for cases
 178    in which the key cannot represent empty and deleted slots.  Instead
 179    record empty and deleted entries in Value.  Derived classes must
 180    implement the hash and equal_keys functions.  */
 181
 182 template <typename Value>
 183 struct unbounded_hashmap_traits
 184 {
 185   template <typename T> static inline void remove (T &);
 186   template <typename T> static inline bool is_empty (const T &);
 187   template <typename T> static inline bool is_deleted (const T &);
 188   template <typename T> static inline void mark_empty (T &);
 189   template <typename T> static inline void mark_deleted (T &);
 190 };
 191
 192 template <typename Value>
 193 template <typename T>
 194 inline void
 195 unbounded_hashmap_traits <Value>::remove (T &entry)
 196 {
 197   default_hash_traits <Value>::remove (entry.m_value);
 198 }
 199
 200 template <typename Value>
 201 template <typename T>
 202 inline bool
 203 unbounded_hashmap_traits <Value>::is_empty (const T &entry)
 204 {
 205   return default_hash_traits <Value>::is_empty (entry.m_value);
 206 }
 207
 208 template <typename Value>
 209 template <typename T>
 210 inline bool
 211 unbounded_hashmap_traits <Value>::is_deleted (const T &entry)
 212 {
 213   return default_hash_traits <Value>::is_deleted (entry.m_value);
 214 }
 215
 216 template <typename Value>
 217 template <typename T>
 218 inline void
 219 unbounded_hashmap_traits <Value>::mark_empty (T &entry)
 220 {
 221   default_hash_traits <Value>::mark_empty (entry.m_value);
 222 }
 223
 224 template <typename Value>
 225 template <typename T>
 226 inline void
 227 unbounded_hashmap_traits <Value>::mark_deleted (T &entry)
 228 {
 229   default_hash_traits <Value>::mark_deleted (entry.m_value);
 230 }
 231
 232 /* Implement traits for a hash_map from integer type Key to Value in
 233    cases where Key has no spare values for recording empty and deleted
 234    slots.  */
 235
 236 template <typename Key, typename Value>
 237 struct unbounded_int_hashmap_traits : unbounded_hashmap_traits <Value>
 238 {
 239   static inline hashval_t hash (Key);
 240   static inline bool equal_keys (Key, Key);
 241 };
 242
 243 template <typename Key, typename Value>
 244 inline hashval_t
 245 unbounded_int_hashmap_traits <Key, Value>::hash (Key k)
 246 {
 247   return k;
 248 }
 249
 250 template <typename Key, typename Value>
 251 inline bool
 252 unbounded_int_hashmap_traits <Key, Value>::equal_keys (Key k1, Key k2)
 253 {
 254   return k1 == k2;
 255 }
 256
 257 #endif // HASH_MAP_TRAITS_H