1 /* A type-safe hash map.
2 Copyright (C) 2014-2021 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, 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. */
221
222 template<typename Arg, bool (*f)(const typename Traits::key_type &,
223 const Value &, Arg)>
224 void traverse (Arg a) const
225 {
226 for (typename hash_table<hash_entry>::iterator iter = m_table.begin ();
227 iter != m_table.end (); ++iter)
228 f ((*iter).m_key, (*iter).m_value, a);
229 }
230
231 template<typename Arg, bool (*f)(const typename Traits::key_type &,
232 Value *, Arg)>
233 void traverse (Arg a) const
234 {
235 for (typename hash_table<hash_entry>::iterator iter = m_table.begin ();
236 iter != m_table.end (); ++iter)
237 if (!f ((*iter).m_key, &(*iter).m_value, a))
238 break;
239 }
240
241 size_t elements () const { return m_table.elements (); }
242
243 void empty () { m_table.empty(); }
244
245 /* Return true when there are no elements in this hash map. */
246 bool is_empty () const { return m_table.is_empty (); }
247
248 class iterator
249 {
250 public:
251 explicit iterator (const typename hash_table<hash_entry>::iterator &iter) :
252 m_iter (iter) {}
253
254 iterator &operator++ ()
255 {
256 ++m_iter;
257 return *this;
258 }
259
260 /* Can't use std::pair here, because GCC before 4.3 don't handle
261 std::pair where template parameters are references well.
262 See PR86739. */
263 class reference_pair {
264 public:
265 const Key &first;
266 Value &second;
267
268 reference_pair (const Key &key, Value &value) : first (key), second (value) {}
269
270 template <typename K, typename V>
271 operator std::pair<K, V> () const { return std::pair<K, V> (first, second); }
272 };
273
274 reference_pair operator* ()
275 {
276 hash_entry &e = *m_iter;
277 return reference_pair (e.m_key, e.m_value);
278 }
279
280 bool operator== (const iterator &other) const
281 {
282 return m_iter == other.m_iter;
283 }
284
285 bool operator != (const iterator &other) const
286 {
287 return m_iter != other.m_iter;
288 }
289
290 private:
291 typename hash_table<hash_entry>::iterator m_iter;
292 };
293
294 /* Standard iterator retrieval methods. */
295
296 iterator begin () const { return iterator (m_table.begin ()); }
297 iterator end () const { return iterator (m_table.end ()); }
298
299 private:
300
301 template<typename T, typename U, typename V> friend void gt_ggc_mx (hash_map<T, U, V> *);
302 template<typename T, typename U, typename V> friend void gt_pch_nx (hash_map<T, U, V> *);
303 template<typename T, typename U, typename V> friend void gt_pch_nx (hash_map<T, U, V> *, gt_pointer_operator, void *);
304 template<typename T, typename U, typename V> friend void gt_cleare_cache (hash_map<T, U, V> *);
305
306 hash_table<hash_entry> m_table;
307 };
308
309 /* ggc marking routines. */
310
311 template<typename K, typename V, typename H>
312 static inline void
gt_ggc_mx(hash_map<K,V,H> * h)313 gt_ggc_mx (hash_map<K, V, H> *h)
314 {
315 gt_ggc_mx (&h->m_table);
316 }
317
318 template<typename K, typename V, typename H>
319 static inline void
gt_pch_nx(hash_map<K,V,H> * h)320 gt_pch_nx (hash_map<K, V, H> *h)
321 {
322 gt_pch_nx (&h->m_table);
323 }
324
325 template<typename K, typename V, typename H>
326 static inline void
gt_cleare_cache(hash_map<K,V,H> * h)327 gt_cleare_cache (hash_map<K, V, H> *h)
328 {
329 if (h)
330 gt_cleare_cache (&h->m_table);
331 }
332
333 template<typename K, typename V, typename H>
334 static inline void
gt_pch_nx(hash_map<K,V,H> * h,gt_pointer_operator op,void * cookie)335 gt_pch_nx (hash_map<K, V, H> *h, gt_pointer_operator op, void *cookie)
336 {
337 op (&h->m_table.m_entries, cookie);
338 }
339
340 enum hm_alloc { hm_heap = false, hm_ggc = true };
341 template<bool ggc, typename K, typename V, typename H>
342 inline hash_map<K,V,H> *
343 hash_map_maybe_create (hash_map<K,V,H> *&h,
344 size_t size = default_hash_map_size)
345 {
346 if (!h)
347 {
348 if (ggc)
349 h = hash_map<K,V,H>::create_ggc (size);
350 else
351 h = new hash_map<K,V,H> (size);
352 }
353 return h;
354 }
355
356 /* Like h->get, but handles null h. */
357 template<typename K, typename V, typename H>
358 inline V*
hash_map_safe_get(hash_map<K,V,H> * h,const K & k)359 hash_map_safe_get (hash_map<K,V,H> *h, const K& k)
360 {
361 return h ? h->get (k) : NULL;
362 }
363
364 /* Like h->get, but handles null h. */
365 template<bool ggc, typename K, typename V, typename H>
366 inline V&
367 hash_map_safe_get_or_insert (hash_map<K,V,H> *&h, const K& k, bool *e = NULL,
368 size_t size = default_hash_map_size)
369 {
370 return hash_map_maybe_create<ggc> (h, size)->get_or_insert (k, e);
371 }
372
373 /* Like h->put, but handles null h. */
374 template<bool ggc, typename K, typename V, typename H>
375 inline bool
376 hash_map_safe_put (hash_map<K,V,H> *&h, const K& k, const V& v,
377 size_t size = default_hash_map_size)
378 {
379 return hash_map_maybe_create<ggc> (h, size)->put (k, v);
380 }
381
382 #endif
383