1 /* A type-safe hash map.
2 Copyright (C) 2014-2023 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 /* 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
35 const size_t default_hash_map_size = 13;
36 template<typename KeyId, typename Value,
37 typename Traits /* = simple_hashmap_traits<default_hash_traits<Key>,
38 Value> */>
39 class 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
137 public:
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 = Traits::is_empty (*e);
173 if (ins)
174 {
175 e->m_key = k;
176 new ((void *)&e->m_value) Value (v);
177 gcc_checking_assert (!Traits::is_empty (*e)
178 && !Traits::is_deleted (*e));
179 }
180 else
181 e->m_value = v;
182
183 return !ins;
184 }
185
186 /* If the passed in key is in the map return pointer to its value
187 otherwise NULL. */
188
189 Value *get (const Key &k)
190 {
191 hash_entry &e = m_table.find_with_hash (k, Traits::hash (k));
192 return Traits::is_empty (e) ? NULL : &e.m_value;
193 }
194
195 /* Return a reference to the value for the passed in key, creating the entry
196 if it doesn't already exist. If existed is not NULL then it is set to
197 false if the key was not previously in the map, and true otherwise. */
198
199 Value &get_or_insert (const Key &k, bool *existed = NULL)
200 {
201 hash_entry *e = m_table.find_slot_with_hash (k, Traits::hash (k),
202 INSERT);
203 bool ins = Traits::is_empty (*e);
204 if (ins)
205 {
206 e->m_key = k;
207 new ((void *)&e->m_value) Value ();
208 gcc_checking_assert (!Traits::is_empty (*e)
209 && !Traits::is_deleted (*e));
210 }
211
212 if (existed != NULL)
213 *existed = !ins;
214
215 return e->m_value;
216 }
217
218 void remove (const Key &k)
219 {
220 m_table.remove_elt_with_hash (k, Traits::hash (k));
221 }
222
223 /* Call the call back on each pair of key and value with the passed in
224 arg until either the call back returns false or all pairs have been seen.
225 The traversal is unordered. */
226
227 template<typename Arg, bool (*f)(const typename Traits::key_type &,
228 const Value &, Arg)>
229 void traverse (Arg a) const
230 {
231 for (typename hash_table<hash_entry>::iterator iter = m_table.begin ();
232 iter != m_table.end (); ++iter)
233 if (!f ((*iter).m_key, (*iter).m_value, a))
234 break;
235 }
236
237 template<typename Arg, bool (*f)(const typename Traits::key_type &,
238 Value *, Arg)>
239 void traverse (Arg a) const
240 {
241 for (typename hash_table<hash_entry>::iterator iter = m_table.begin ();
242 iter != m_table.end (); ++iter)
243 if (!f ((*iter).m_key, &(*iter).m_value, a))
244 break;
245 }
246
247 size_t elements () const { return m_table.elements (); }
248
249 void empty () { m_table.empty(); }
250
251 /* Return true when there are no elements in this hash map. */
252 bool is_empty () const { return m_table.is_empty (); }
253
254 class iterator
255 {
256 public:
257 explicit iterator (const typename hash_table<hash_entry>::iterator &iter) :
258 m_iter (iter) {}
259
260 iterator &operator++ ()
261 {
262 ++m_iter;
263 return *this;
264 }
265
266 /* Can't use std::pair here, because GCC before 4.3 don't handle
267 std::pair where template parameters are references well.
268 See PR86739. */
269 class reference_pair {
270 public:
271 const Key &first;
272 Value &second;
273
274 reference_pair (const Key &key, Value &value) : first (key), second (value) {}
275
276 template <typename K, typename V>
277 operator std::pair<K, V> () const { return std::pair<K, V> (first, second); }
278 };
279
280 reference_pair operator* ()
281 {
282 hash_entry &e = *m_iter;
283 return reference_pair (e.m_key, e.m_value);
284 }
285
286 bool operator== (const iterator &other) const
287 {
288 return m_iter == other.m_iter;
289 }
290
291 bool operator != (const iterator &other) const
292 {
293 return m_iter != other.m_iter;
294 }
295
296 private:
297 typename hash_table<hash_entry>::iterator m_iter;
298 };
299
300 /* Standard iterator retrieval methods. */
301
302 iterator begin () const { return iterator (m_table.begin ()); }
303 iterator end () const { return iterator (m_table.end ()); }
304
305 private:
306
307 template<typename T, typename U, typename V> friend void gt_ggc_mx (hash_map<T, U, V> *);
308 template<typename T, typename U, typename V> friend void gt_pch_nx (hash_map<T, U, V> *);
309 template<typename T, typename U, typename V> friend void gt_pch_nx (hash_map<T, U, V> *, gt_pointer_operator, void *);
310 template<typename T, typename U, typename V> friend void gt_cleare_cache (hash_map<T, U, V> *);
311
312 hash_table<hash_entry> m_table;
313 };
314
315 /* ggc marking routines. */
316
317 template<typename K, typename V, typename H>
318 inline void
319 gt_ggc_mx (hash_map<K, V, H> *h)
320 {
321 gt_ggc_mx (&h->m_table);
322 }
323
324 template<typename K, typename V, typename H>
325 inline void
326 gt_pch_nx (hash_map<K, V, H> *h)
327 {
328 gt_pch_nx (&h->m_table);
329 }
330
331 template<typename K, typename V, typename H>
332 inline void
333 gt_cleare_cache (hash_map<K, V, H> *h)
334 {
335 if (h)
336 gt_cleare_cache (&h->m_table);
337 }
338
339 template<typename K, typename V, typename H>
340 inline void
341 gt_pch_nx (hash_map<K, V, H> *h, gt_pointer_operator op, void *cookie)
342 {
343 op (&h->m_table.m_entries, NULL, cookie);
344 }
345
346 enum hm_alloc { hm_heap = false, hm_ggc = true };
347 template<bool ggc, typename K, typename V, typename H>
348 inline hash_map<K,V,H> *
349 hash_map_maybe_create (hash_map<K,V,H> *&h,
350 size_t size = default_hash_map_size)
351 {
352 if (!h)
353 {
354 if (ggc)
355 h = hash_map<K,V,H>::create_ggc (size);
356 else
357 h = new hash_map<K,V,H> (size);
358 }
359 return h;
360 }
361
362 /* Like h->get, but handles null h. */
363 template<typename K, typename V, typename H>
364 inline V*
365 hash_map_safe_get (hash_map<K,V,H> *h, const K& k)
366 {
367 return h ? h->get (k) : NULL;
368 }
369
370 /* Like h->get, but handles null h. */
371 template<bool ggc, typename K, typename V, typename H>
372 inline V&
373 hash_map_safe_get_or_insert (hash_map<K,V,H> *&h, const K& k, bool *e = NULL,
374 size_t size = default_hash_map_size)
375 {
376 return hash_map_maybe_create<ggc> (h, size)->get_or_insert (k, e);
377 }
378
379 /* Like h->put, but handles null h. */
380 template<bool ggc, typename K, typename V, typename H>
381 inline bool
382 hash_map_safe_put (hash_map<K,V,H> *&h, const K& k, const V& v,
383 size_t size = default_hash_map_size)
384 {
385 return hash_map_maybe_create<ggc> (h, size)->put (k, v);
386 }
387
388 #endif