1 /* A type-safe hash map.
2 Copyright (C) 2014-2020 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 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
133 public:
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
290 private:
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
302 template<typename K, typename V, typename H>
303 static inline void
gt_ggc_mx(hash_map<K,V,H> * h)304 gt_ggc_mx (hash_map<K, V, H> *h)
305 {
306 gt_ggc_mx (&h->m_table);
307 }
308
309 template<typename K, typename V, typename H>
310 static inline void
gt_pch_nx(hash_map<K,V,H> * h)311 gt_pch_nx (hash_map<K, V, H> *h)
312 {
313 gt_pch_nx (&h->m_table);
314 }
315
316 template<typename K, typename V, typename H>
317 static inline void
gt_cleare_cache(hash_map<K,V,H> * h)318 gt_cleare_cache (hash_map<K, V, H> *h)
319 {
320 if (h)
321 gt_cleare_cache (&h->m_table);
322 }
323
324 template<typename K, typename V, typename H>
325 static inline void
gt_pch_nx(hash_map<K,V,H> * h,gt_pointer_operator op,void * cookie)326 gt_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
331 enum hm_alloc { hm_heap = false, hm_ggc = true };
332 template<bool ggc, typename K, typename V, typename H>
333 inline hash_map<K,V,H> *
334 hash_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. */
348 template<typename K, typename V, typename H>
349 inline V*
hash_map_safe_get(hash_map<K,V,H> * h,const K & k)350 hash_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. */
356 template<bool ggc, typename K, typename V, typename H>
357 inline V&
358 hash_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. */
365 template<bool ggc, typename K, typename V, typename H>
366 inline bool
367 hash_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