1/* A type-safe hash map. 2 Copyright (C) 2014-2020 Free Software Foundation, Inc. 3 4This file is part of GCC. 5 6GCC is free software; you can redistribute it and/or modify it under 7the terms of the GNU General Public License as published by the Free 8Software Foundation; either version 3, or (at your option) any later 9version. 10 11GCC is distributed in the hope that it will be useful, but WITHOUT ANY 12WARRANTY; without even the implied warranty of MERCHANTABILITY or 13FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14for more details. 15 16You should have received a copy of the GNU General Public License 17along 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/* Class hash_map is a hash-value based container mapping objects of 25 KeyId type to those of the Value type. 26 Both KeyId and Value may be non-trivial (non-POD) types provided 27 a suitabe Traits class. A few default Traits specializations are 28 provided for basic types such as integers, pointers, and std::pair. 29 Inserted elements are value-initialized either to zero for POD types 30 or by invoking their default ctor. Removed elements are destroyed 31 by invoking their dtor. On hash_map destruction all elements are 32 removed. Objects of hash_map type are copy-constructible but not 33 assignable. */ 34 35const size_t default_hash_map_size = 13; 36template<typename KeyId, typename Value, 37 typename Traits /* = simple_hashmap_traits<default_hash_traits<Key>, 38 Value> */> 39class GTY((user)) hash_map 40{ 41 typedef typename Traits::key_type Key; 42 struct hash_entry 43 { 44 Key m_key; 45 Value m_value; 46 47 typedef hash_entry value_type; 48 typedef Key compare_type; 49 50 static hashval_t hash (const hash_entry &e) 51 { 52 return Traits::hash (e.m_key); 53 } 54 55 static bool equal (const hash_entry &a, const Key &b) 56 { 57 return Traits::equal_keys (a.m_key, b); 58 } 59 60 static void remove (hash_entry &e) { Traits::remove (e); } 61 62 static void mark_deleted (hash_entry &e) { Traits::mark_deleted (e); } 63 64 static bool is_deleted (const hash_entry &e) 65 { 66 return Traits::is_deleted (e); 67 } 68 69 static const bool empty_zero_p = Traits::empty_zero_p; 70 static void mark_empty (hash_entry &e) { Traits::mark_empty (e); } 71 static bool is_empty (const hash_entry &e) { return Traits::is_empty (e); } 72 73 static void ggc_mx (hash_entry &e) 74 { 75 gt_ggc_mx (e.m_key); 76 gt_ggc_mx (e.m_value); 77 } 78 79 static void ggc_maybe_mx (hash_entry &e) 80 { 81 if (Traits::maybe_mx) 82 ggc_mx (e); 83 } 84 85 static void pch_nx (hash_entry &e) 86 { 87 gt_pch_nx (e.m_key); 88 gt_pch_nx (e.m_value); 89 } 90 91 static void pch_nx (hash_entry &e, gt_pointer_operator op, void *c) 92 { 93 pch_nx_helper (e.m_key, op, c); 94 pch_nx_helper (e.m_value, op, c); 95 } 96 97 static int keep_cache_entry (hash_entry &e) 98 { 99 return ggc_marked_p (e.m_key); 100 } 101 102 private: 103 template<typename T> 104 static void 105 pch_nx_helper (T &x, gt_pointer_operator op, void *cookie) 106 { 107 gt_pch_nx (&x, op, cookie); 108 } 109 110 static void 111 pch_nx_helper (int, gt_pointer_operator, void *) 112 { 113 } 114 115 static void 116 pch_nx_helper (unsigned int, gt_pointer_operator, void *) 117 { 118 } 119 120 static void 121 pch_nx_helper (bool, gt_pointer_operator, void *) 122 { 123 } 124 125 template<typename T> 126 static void 127 pch_nx_helper (T *&x, gt_pointer_operator op, void *cookie) 128 { 129 op (&x, cookie); 130 } 131 }; 132 133public: 134 explicit hash_map (size_t n = default_hash_map_size, bool ggc = false, 135 bool sanitize_eq_and_hash = true, 136 bool gather_mem_stats = GATHER_STATISTICS 137 CXX_MEM_STAT_INFO) 138 : m_table (n, ggc, sanitize_eq_and_hash, gather_mem_stats, 139 HASH_MAP_ORIGIN PASS_MEM_STAT) 140 { 141 } 142 143 explicit hash_map (const hash_map &h, bool ggc = false, 144 bool sanitize_eq_and_hash = true, 145 bool gather_mem_stats = GATHER_STATISTICS 146 CXX_MEM_STAT_INFO) 147 : m_table (h.m_table, ggc, sanitize_eq_and_hash, gather_mem_stats, 148 HASH_MAP_ORIGIN PASS_MEM_STAT) {} 149 150 /* Create a hash_map in ggc memory. */ 151 static hash_map *create_ggc (size_t size = default_hash_map_size, 152 bool gather_mem_stats = GATHER_STATISTICS 153 CXX_MEM_STAT_INFO) 154 { 155 hash_map *map = ggc_alloc<hash_map> (); 156 new (map) hash_map (size, true, true, gather_mem_stats PASS_MEM_STAT); 157 return map; 158 } 159 160 /* If key k isn't already in the map add key k with value v to the map, and 161 return false. Otherwise set the value of the entry for key k to be v and 162 return true. */ 163 164 bool put (const Key &k, const Value &v) 165 { 166 hash_entry *e = m_table.find_slot_with_hash (k, Traits::hash (k), 167 INSERT); 168 bool ins = hash_entry::is_empty (*e); 169 if (ins) 170 { 171 e->m_key = k; 172 new ((void *) &e->m_value) Value (v); 173 } 174 else 175 e->m_value = v; 176 177 return !ins; 178 } 179 180 /* if the passed in key is in the map return its value otherwise NULL. */ 181 182 Value *get (const Key &k) 183 { 184 hash_entry &e = m_table.find_with_hash (k, Traits::hash (k)); 185 return Traits::is_empty (e) ? NULL : &e.m_value; 186 } 187 188 /* Return a reference to the value for the passed in key, creating the entry 189 if it doesn't already exist. If existed is not NULL then it is set to 190 false if the key was not previously in the map, and true otherwise. */ 191 192 Value &get_or_insert (const Key &k, bool *existed = NULL) 193 { 194 hash_entry *e = m_table.find_slot_with_hash (k, Traits::hash (k), 195 INSERT); 196 bool ins = Traits::is_empty (*e); 197 if (ins) 198 { 199 e->m_key = k; 200 new ((void *)&e->m_value) Value (); 201 } 202 203 if (existed != NULL) 204 *existed = !ins; 205 206 return e->m_value; 207 } 208 209 void remove (const Key &k) 210 { 211 m_table.remove_elt_with_hash (k, Traits::hash (k)); 212 } 213 214 /* Call the call back on each pair of key and value with the passed in 215 arg. */ 216 217 template<typename Arg, bool (*f)(const typename Traits::key_type &, 218 const Value &, Arg)> 219 void traverse (Arg a) const 220 { 221 for (typename hash_table<hash_entry>::iterator iter = m_table.begin (); 222 iter != m_table.end (); ++iter) 223 f ((*iter).m_key, (*iter).m_value, a); 224 } 225 226 template<typename Arg, bool (*f)(const typename Traits::key_type &, 227 Value *, Arg)> 228 void traverse (Arg a) const 229 { 230 for (typename hash_table<hash_entry>::iterator iter = m_table.begin (); 231 iter != m_table.end (); ++iter) 232 if (!f ((*iter).m_key, &(*iter).m_value, a)) 233 break; 234 } 235 236 size_t elements () const { return m_table.elements (); } 237 238 void empty () { m_table.empty(); } 239 240 /* Return true when there are no elements in this hash map. */ 241 bool is_empty () const { return m_table.is_empty (); } 242 243 class iterator 244 { 245 public: 246 explicit iterator (const typename hash_table<hash_entry>::iterator &iter) : 247 m_iter (iter) {} 248 249 iterator &operator++ () 250 { 251 ++m_iter; 252 return *this; 253 } 254 255 /* Can't use std::pair here, because GCC before 4.3 don't handle 256 std::pair where template parameters are references well. 257 See PR86739. */ 258 class reference_pair { 259 public: 260 const Key &first; 261 Value &second; 262 263 reference_pair (const Key &key, Value &value) : first (key), second (value) {} 264 265 template <typename K, typename V> 266 operator std::pair<K, V> () const { return std::pair<K, V> (first, second); } 267 }; 268 269 reference_pair operator* () 270 { 271 hash_entry &e = *m_iter; 272 return reference_pair (e.m_key, e.m_value); 273 } 274 275 bool 276 operator != (const iterator &other) const 277 { 278 return m_iter != other.m_iter; 279 } 280 281 private: 282 typename hash_table<hash_entry>::iterator m_iter; 283 }; 284 285 /* Standard iterator retrieval methods. */ 286 287 iterator begin () const { return iterator (m_table.begin ()); } 288 iterator end () const { return iterator (m_table.end ()); } 289 290private: 291 292 template<typename T, typename U, typename V> friend void gt_ggc_mx (hash_map<T, U, V> *); 293 template<typename T, typename U, typename V> friend void gt_pch_nx (hash_map<T, U, V> *); 294 template<typename T, typename U, typename V> friend void gt_pch_nx (hash_map<T, U, V> *, gt_pointer_operator, void *); 295 template<typename T, typename U, typename V> friend void gt_cleare_cache (hash_map<T, U, V> *); 296 297 hash_table<hash_entry> m_table; 298}; 299 300/* ggc marking routines. */ 301 302template<typename K, typename V, typename H> 303static inline void 304gt_ggc_mx (hash_map<K, V, H> *h) 305{ 306 gt_ggc_mx (&h->m_table); 307} 308 309template<typename K, typename V, typename H> 310static inline void 311gt_pch_nx (hash_map<K, V, H> *h) 312{ 313 gt_pch_nx (&h->m_table); 314} 315 316template<typename K, typename V, typename H> 317static inline void 318gt_cleare_cache (hash_map<K, V, H> *h) 319{ 320 if (h) 321 gt_cleare_cache (&h->m_table); 322} 323 324template<typename K, typename V, typename H> 325static inline void 326gt_pch_nx (hash_map<K, V, H> *h, gt_pointer_operator op, void *cookie) 327{ 328 op (&h->m_table.m_entries, cookie); 329} 330 331enum hm_alloc { hm_heap = false, hm_ggc = true }; 332template<bool ggc, typename K, typename V, typename H> 333inline hash_map<K,V,H> * 334hash_map_maybe_create (hash_map<K,V,H> *&h, 335 size_t size = default_hash_map_size) 336{ 337 if (!h) 338 { 339 if (ggc) 340 h = hash_map<K,V,H>::create_ggc (size); 341 else 342 h = new hash_map<K,V,H> (size); 343 } 344 return h; 345} 346 347/* Like h->get, but handles null h. */ 348template<typename K, typename V, typename H> 349inline V* 350hash_map_safe_get (hash_map<K,V,H> *h, const K& k) 351{ 352 return h ? h->get (k) : NULL; 353} 354 355/* Like h->get, but handles null h. */ 356template<bool ggc, typename K, typename V, typename H> 357inline V& 358hash_map_safe_get_or_insert (hash_map<K,V,H> *&h, const K& k, bool *e = NULL, 359 size_t size = default_hash_map_size) 360{ 361 return hash_map_maybe_create<ggc> (h, size)->get_or_insert (k, e); 362} 363 364/* Like h->put, but handles null h. */ 365template<bool ggc, typename K, typename V, typename H> 366inline bool 367hash_map_safe_put (hash_map<K,V,H> *&h, const K& k, const V& v, 368 size_t size = default_hash_map_size) 369{ 370 return hash_map_maybe_create<ggc> (h, size)->put (k, v); 371} 372 373#endif 374