1/* A type-safe hash map. 2 Copyright (C) 2014-2022 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 template<typename T> 111 static void 112 pch_nx_helper (T *&x, gt_pointer_operator op, void *cookie) 113 { 114 op (&x, NULL, cookie); 115 } 116 117 /* The overloads below should match those in ggc.h. */ 118#define DEFINE_PCH_HELPER(T) \ 119 static void pch_nx_helper (T, gt_pointer_operator, void *) { } 120 121 DEFINE_PCH_HELPER (bool); 122 DEFINE_PCH_HELPER (char); 123 DEFINE_PCH_HELPER (signed char); 124 DEFINE_PCH_HELPER (unsigned char); 125 DEFINE_PCH_HELPER (short); 126 DEFINE_PCH_HELPER (unsigned short); 127 DEFINE_PCH_HELPER (int); 128 DEFINE_PCH_HELPER (unsigned int); 129 DEFINE_PCH_HELPER (long); 130 DEFINE_PCH_HELPER (unsigned long); 131 DEFINE_PCH_HELPER (long long); 132 DEFINE_PCH_HELPER (unsigned long long); 133 134#undef DEFINE_PCH_HELPER 135 }; 136 137public: 138 explicit hash_map (size_t n = default_hash_map_size, bool ggc = false, 139 bool sanitize_eq_and_hash = true, 140 bool gather_mem_stats = GATHER_STATISTICS 141 CXX_MEM_STAT_INFO) 142 : m_table (n, ggc, sanitize_eq_and_hash, gather_mem_stats, 143 HASH_MAP_ORIGIN PASS_MEM_STAT) 144 { 145 } 146 147 explicit hash_map (const hash_map &h, bool ggc = false, 148 bool sanitize_eq_and_hash = true, 149 bool gather_mem_stats = GATHER_STATISTICS 150 CXX_MEM_STAT_INFO) 151 : m_table (h.m_table, ggc, sanitize_eq_and_hash, gather_mem_stats, 152 HASH_MAP_ORIGIN PASS_MEM_STAT) {} 153 154 /* Create a hash_map in ggc memory. */ 155 static hash_map *create_ggc (size_t size = default_hash_map_size, 156 bool gather_mem_stats = GATHER_STATISTICS 157 CXX_MEM_STAT_INFO) 158 { 159 hash_map *map = ggc_alloc<hash_map> (); 160 new (map) hash_map (size, true, true, gather_mem_stats PASS_MEM_STAT); 161 return map; 162 } 163 164 /* If key k isn't already in the map add key k with value v to the map, and 165 return false. Otherwise set the value of the entry for key k to be v and 166 return true. */ 167 168 bool put (const Key &k, const Value &v) 169 { 170 hash_entry *e = m_table.find_slot_with_hash (k, Traits::hash (k), 171 INSERT); 172 bool ins = hash_entry::is_empty (*e); 173 if (ins) 174 { 175 e->m_key = k; 176 new ((void *) &e->m_value) Value (v); 177 } 178 else 179 e->m_value = v; 180 181 return !ins; 182 } 183 184 /* If the passed in key is in the map return pointer to its value 185 otherwise NULL. */ 186 187 Value *get (const Key &k) 188 { 189 hash_entry &e = m_table.find_with_hash (k, Traits::hash (k)); 190 return Traits::is_empty (e) ? NULL : &e.m_value; 191 } 192 193 /* Return a reference to the value for the passed in key, creating the entry 194 if it doesn't already exist. If existed is not NULL then it is set to 195 false if the key was not previously in the map, and true otherwise. */ 196 197 Value &get_or_insert (const Key &k, bool *existed = NULL) 198 { 199 hash_entry *e = m_table.find_slot_with_hash (k, Traits::hash (k), 200 INSERT); 201 bool ins = Traits::is_empty (*e); 202 if (ins) 203 { 204 e->m_key = k; 205 new ((void *)&e->m_value) Value (); 206 } 207 208 if (existed != NULL) 209 *existed = !ins; 210 211 return e->m_value; 212 } 213 214 void remove (const Key &k) 215 { 216 m_table.remove_elt_with_hash (k, Traits::hash (k)); 217 } 218 219 /* Call the call back on each pair of key and value with the passed in 220 arg until either the call back returns false or all pairs have been seen. 221 The traversal is unordered. */ 222 223 template<typename Arg, bool (*f)(const typename Traits::key_type &, 224 const Value &, Arg)> 225 void traverse (Arg a) const 226 { 227 for (typename hash_table<hash_entry>::iterator iter = m_table.begin (); 228 iter != m_table.end (); ++iter) 229 if (!f ((*iter).m_key, (*iter).m_value, a)) 230 break; 231 } 232 233 template<typename Arg, bool (*f)(const typename Traits::key_type &, 234 Value *, Arg)> 235 void traverse (Arg a) const 236 { 237 for (typename hash_table<hash_entry>::iterator iter = m_table.begin (); 238 iter != m_table.end (); ++iter) 239 if (!f ((*iter).m_key, &(*iter).m_value, a)) 240 break; 241 } 242 243 size_t elements () const { return m_table.elements (); } 244 245 void empty () { m_table.empty(); } 246 247 /* Return true when there are no elements in this hash map. */ 248 bool is_empty () const { return m_table.is_empty (); } 249 250 class iterator 251 { 252 public: 253 explicit iterator (const typename hash_table<hash_entry>::iterator &iter) : 254 m_iter (iter) {} 255 256 iterator &operator++ () 257 { 258 ++m_iter; 259 return *this; 260 } 261 262 /* Can't use std::pair here, because GCC before 4.3 don't handle 263 std::pair where template parameters are references well. 264 See PR86739. */ 265 class reference_pair { 266 public: 267 const Key &first; 268 Value &second; 269 270 reference_pair (const Key &key, Value &value) : first (key), second (value) {} 271 272 template <typename K, typename V> 273 operator std::pair<K, V> () const { return std::pair<K, V> (first, second); } 274 }; 275 276 reference_pair operator* () 277 { 278 hash_entry &e = *m_iter; 279 return reference_pair (e.m_key, e.m_value); 280 } 281 282 bool operator== (const iterator &other) const 283 { 284 return m_iter == other.m_iter; 285 } 286 287 bool operator != (const iterator &other) const 288 { 289 return m_iter != other.m_iter; 290 } 291 292 private: 293 typename hash_table<hash_entry>::iterator m_iter; 294 }; 295 296 /* Standard iterator retrieval methods. */ 297 298 iterator begin () const { return iterator (m_table.begin ()); } 299 iterator end () const { return iterator (m_table.end ()); } 300 301private: 302 303 template<typename T, typename U, typename V> friend void gt_ggc_mx (hash_map<T, U, V> *); 304 template<typename T, typename U, typename V> friend void gt_pch_nx (hash_map<T, U, V> *); 305 template<typename T, typename U, typename V> friend void gt_pch_nx (hash_map<T, U, V> *, gt_pointer_operator, void *); 306 template<typename T, typename U, typename V> friend void gt_cleare_cache (hash_map<T, U, V> *); 307 308 hash_table<hash_entry> m_table; 309}; 310 311/* ggc marking routines. */ 312 313template<typename K, typename V, typename H> 314static inline void 315gt_ggc_mx (hash_map<K, V, H> *h) 316{ 317 gt_ggc_mx (&h->m_table); 318} 319 320template<typename K, typename V, typename H> 321static inline void 322gt_pch_nx (hash_map<K, V, H> *h) 323{ 324 gt_pch_nx (&h->m_table); 325} 326 327template<typename K, typename V, typename H> 328static inline void 329gt_cleare_cache (hash_map<K, V, H> *h) 330{ 331 if (h) 332 gt_cleare_cache (&h->m_table); 333} 334 335template<typename K, typename V, typename H> 336static inline void 337gt_pch_nx (hash_map<K, V, H> *h, gt_pointer_operator op, void *cookie) 338{ 339 op (&h->m_table.m_entries, NULL, cookie); 340} 341 342enum hm_alloc { hm_heap = false, hm_ggc = true }; 343template<bool ggc, typename K, typename V, typename H> 344inline hash_map<K,V,H> * 345hash_map_maybe_create (hash_map<K,V,H> *&h, 346 size_t size = default_hash_map_size) 347{ 348 if (!h) 349 { 350 if (ggc) 351 h = hash_map<K,V,H>::create_ggc (size); 352 else 353 h = new hash_map<K,V,H> (size); 354 } 355 return h; 356} 357 358/* Like h->get, but handles null h. */ 359template<typename K, typename V, typename H> 360inline V* 361hash_map_safe_get (hash_map<K,V,H> *h, const K& k) 362{ 363 return h ? h->get (k) : NULL; 364} 365 366/* Like h->get, but handles null h. */ 367template<bool ggc, typename K, typename V, typename H> 368inline V& 369hash_map_safe_get_or_insert (hash_map<K,V,H> *&h, const K& k, bool *e = NULL, 370 size_t size = default_hash_map_size) 371{ 372 return hash_map_maybe_create<ggc> (h, size)->get_or_insert (k, e); 373} 374 375/* Like h->put, but handles null h. */ 376template<bool ggc, typename K, typename V, typename H> 377inline bool 378hash_map_safe_put (hash_map<K,V,H> *&h, const K& k, const V& v, 379 size_t size = default_hash_map_size) 380{ 381 return hash_map_maybe_create<ggc> (h, size)->put (k, v); 382} 383 384#endif 385