1 /* A type-safe hash map. 2 Copyright (C) 2014-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 21 #ifndef hash_map_h 22 #define hash_map_h 23 24 #include <new> 25 #include <utility> 26 #include "hash-table.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 template<typename Key, typename Value, 107 typename Traits = default_hashmap_traits> 108 class GTY((user)) hash_map 109 { 110 struct hash_entry 111 { 112 Key m_key; 113 Value m_value; 114 115 typedef hash_entry value_type; 116 typedef Key compare_type; 117 typedef int store_values_directly; 118 119 static hashval_t hash (const hash_entry &e) 120 { 121 return Traits::hash (e.m_key); 122 } 123 124 static bool equal (const hash_entry &a, const Key &b) 125 { 126 return Traits::equal_keys (a.m_key, b); 127 } 128 129 static void remove (hash_entry &e) { Traits::remove (e); } 130 131 static void mark_deleted (hash_entry &e) { Traits::mark_deleted (e); } 132 133 static bool is_deleted (const hash_entry &e) 134 { 135 return Traits::is_deleted (e); 136 } 137 138 static void mark_empty (hash_entry &e) { Traits::mark_empty (e); } 139 static bool is_empty (const hash_entry &e) { return Traits::is_empty (e); } 140 141 static void ggc_mx (hash_entry &e) 142 { 143 gt_ggc_mx (e.m_key); 144 gt_ggc_mx (e.m_value); 145 } 146 147 static void pch_nx (hash_entry &e) 148 { 149 gt_pch_nx (e.m_key); 150 gt_pch_nx (e.m_value); 151 } 152 153 static void pch_nx (hash_entry &e, gt_pointer_operator op, void *c) 154 { 155 pch_nx_helper (e.m_key, op, c); 156 pch_nx_helper (e.m_value, op, c); 157 } 158 159 private: 160 template<typename T> 161 static void 162 pch_nx_helper (T &x, gt_pointer_operator op, void *cookie) 163 { 164 gt_pch_nx (&x, op, cookie); 165 } 166 167 static void 168 pch_nx_helper (int, gt_pointer_operator, void *) 169 { 170 } 171 172 static void 173 pch_nx_helper (unsigned int, gt_pointer_operator, void *) 174 { 175 } 176 177 static void 178 pch_nx_helper (bool, gt_pointer_operator, void *) 179 { 180 } 181 182 template<typename T> 183 static void 184 pch_nx_helper (T *&x, gt_pointer_operator op, void *cookie) 185 { 186 op (&x, cookie); 187 } 188 }; 189 190 public: 191 explicit hash_map (size_t n = 13, bool ggc = false) : m_table (n, ggc) {} 192 193 /* Create a hash_map in ggc memory. */ 194 static hash_map *create_ggc (size_t size) 195 { 196 hash_map *map = ggc_alloc<hash_map> (); 197 new (map) hash_map (size, true); 198 return map; 199 } 200 201 /* If key k isn't already in the map add key k with value v to the map, and 202 return false. Otherwise set the value of the entry for key k to be v and 203 return true. */ 204 205 bool put (const Key &k, const Value &v) 206 { 207 hash_entry *e = m_table.find_slot_with_hash (k, Traits::hash (k), 208 INSERT); 209 bool existed = !hash_entry::is_empty (*e); 210 if (!existed) 211 e->m_key = k; 212 213 e->m_value = v; 214 return existed; 215 } 216 217 /* if the passed in key is in the map return its value otherwise NULL. */ 218 219 Value *get (const Key &k) 220 { 221 hash_entry &e = m_table.find_with_hash (k, Traits::hash (k)); 222 return Traits::is_empty (e) ? NULL : &e.m_value; 223 } 224 225 /* Return a reference to the value for the passed in key, creating the entry 226 if it doesn't already exist. If existed is not NULL then it is set to false 227 if the key was not previously in the map, and true otherwise. */ 228 229 Value &get_or_insert (const Key &k, bool *existed = NULL) 230 { 231 hash_entry *e = m_table.find_slot_with_hash (k, Traits::hash (k), 232 INSERT); 233 bool ins = Traits::is_empty (*e); 234 if (ins) 235 e->m_key = k; 236 237 if (existed != NULL) 238 *existed = !ins; 239 240 return e->m_value; 241 } 242 243 void remove (const Key &k) 244 { 245 m_table.remove_elt_with_hash (k, Traits::hash (k)); 246 } 247 248 /* Call the call back on each pair of key and value with the passed in 249 arg. */ 250 251 template<typename Arg, bool (*f)(const Key &, const Value &, Arg)> 252 void traverse (Arg a) const 253 { 254 for (typename hash_table<hash_entry>::iterator iter = m_table.begin (); 255 iter != m_table.end (); ++iter) 256 f ((*iter).m_key, (*iter).m_value, a); 257 } 258 259 template<typename Arg, bool (*f)(const Key &, Value *, Arg)> 260 void traverse (Arg a) const 261 { 262 for (typename hash_table<hash_entry>::iterator iter = m_table.begin (); 263 iter != m_table.end (); ++iter) 264 if (!f ((*iter).m_key, &(*iter).m_value, a)) 265 break; 266 } 267 268 size_t elements () const { return m_table.elements (); } 269 270 class iterator 271 { 272 public: 273 explicit iterator (const typename hash_table<hash_entry>::iterator &iter) : 274 m_iter (iter) {} 275 276 iterator &operator++ () 277 { 278 ++m_iter; 279 return *this; 280 } 281 282 std::pair<Key, Value> operator* () 283 { 284 hash_entry &e = *m_iter; 285 return std::pair<Key, Value> (e.m_key, e.m_value); 286 } 287 288 bool 289 operator != (const iterator &other) const 290 { 291 return m_iter != other.m_iter; 292 } 293 294 private: 295 typename hash_table<hash_entry>::iterator m_iter; 296 }; 297 298 /* Standard iterator retrieval methods. */ 299 300 iterator begin () const { return iterator (m_table.begin ()); } 301 iterator end () const { return iterator (m_table.end ()); } 302 303 private: 304 305 template<typename T, typename U, typename V> friend void gt_ggc_mx (hash_map<T, U, V> *); 306 template<typename T, typename U, typename V> friend void gt_pch_nx (hash_map<T, U, V> *); 307 template<typename T, typename U, typename V> friend void gt_pch_nx (hash_map<T, U, V> *, gt_pointer_operator, void *); 308 309 hash_table<hash_entry> m_table; 310 }; 311 312 /* ggc marking routines. */ 313 314 template<typename K, typename V, typename H> 315 static inline void 316 gt_ggc_mx (hash_map<K, V, H> *h) 317 { 318 gt_ggc_mx (&h->m_table); 319 } 320 321 template<typename K, typename V, typename H> 322 static inline void 323 gt_pch_nx (hash_map<K, V, H> *h) 324 { 325 gt_pch_nx (&h->m_table); 326 } 327 328 template<typename K, typename V, typename H> 329 static inline void 330 gt_pch_nx (hash_map<K, V, H> *h, gt_pointer_operator op, void *cookie) 331 { 332 op (&h->m_table.m_entries, cookie); 333 } 334 335 #endif 336