1 /* A type-safe hash map.
2 Copyright (C) 2014-2022 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> */>
class(user)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 = 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
301 private:
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
313 template<typename K, typename V, typename H>
314 static inline void
gt_ggc_mx(hash_map<K,V,H> * h)315 gt_ggc_mx (hash_map<K, V, H> *h)
316 {
317 gt_ggc_mx (&h->m_table);
318 }
319
320 template<typename K, typename V, typename H>
321 static inline void
gt_pch_nx(hash_map<K,V,H> * h)322 gt_pch_nx (hash_map<K, V, H> *h)
323 {
324 gt_pch_nx (&h->m_table);
325 }
326
327 template<typename K, typename V, typename H>
328 static inline void
gt_cleare_cache(hash_map<K,V,H> * h)329 gt_cleare_cache (hash_map<K, V, H> *h)
330 {
331 if (h)
332 gt_cleare_cache (&h->m_table);
333 }
334
335 template<typename K, typename V, typename H>
336 static inline void
gt_pch_nx(hash_map<K,V,H> * h,gt_pointer_operator op,void * cookie)337 gt_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
342 enum hm_alloc { hm_heap = false, hm_ggc = true };
343 template<bool ggc, typename K, typename V, typename H>
344 inline hash_map<K,V,H> *
345 hash_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. */
359 template<typename K, typename V, typename H>
360 inline V*
hash_map_safe_get(hash_map<K,V,H> * h,const K & k)361 hash_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. */
367 template<bool ggc, typename K, typename V, typename H>
368 inline V&
369 hash_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. */
376 template<bool ggc, typename K, typename V, typename H>
377 inline bool
378 hash_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