Branch data Line data Source code
1 : : /* A type-safe hash map.
2 : : Copyright (C) 2014-2024 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 : 950851915 : class GTY((user)) hash_map
40 : : {
41 : : typedef typename Traits::key_type Key;
42 : 7193919 : 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 : 82307503778 : static hashval_t hash (const hash_entry &e)
51 : : {
52 : 82455376060 : return Traits::hash (e.m_key);
53 : : }
54 : :
55 : 94638763128 : static bool equal (const hash_entry &a, const Key &b)
56 : : {
57 : 95093605728 : return Traits::equal_keys (a.m_key, b);
58 : : }
59 : :
60 : 850166315 : static void remove (hash_entry &e) { Traits::remove (e); }
61 : :
62 : 16721634 : static void mark_deleted (hash_entry &e) { Traits::mark_deleted (e); }
63 : :
64 : >12642*10^7 : static bool is_deleted (const hash_entry &e)
65 : : {
66 : >12612*10^7 : return Traits::is_deleted (e);
67 : : }
68 : :
69 : : static const bool empty_zero_p = Traits::empty_zero_p;
70 : 1589695516 : static void mark_empty (hash_entry &e) { Traits::mark_empty (e); }
71 : >46606*10^7 : static bool is_empty (const hash_entry &e) { return Traits::is_empty (e); }
72 : :
73 : 721647054 : static void ggc_mx (hash_entry &e)
74 : : {
75 : 45651739 : gt_ggc_mx (e.m_key);
76 : 712991413 : gt_ggc_mx (e.m_value);
77 : 28014436 : }
78 : :
79 : 15061138 : static void ggc_maybe_mx (hash_entry &e)
80 : : {
81 : : if (Traits::maybe_mx)
82 : 695291555 : ggc_mx (e);
83 : 693346992 : }
84 : :
85 : 187227 : static void pch_nx (hash_entry &e)
86 : : {
87 : 1545 : gt_pch_nx (e.m_key);
88 : 187227 : gt_pch_nx (e.m_value);
89 : 187227 : }
90 : :
91 : 187227 : static void pch_nx (hash_entry &e, gt_pointer_operator op, void *c)
92 : : {
93 : 3090 : pch_nx_helper (e.m_key, op, c);
94 : 188772 : pch_nx_helper (e.m_value, op, c);
95 : 187227 : }
96 : :
97 : 28099289 : static int keep_cache_entry (hash_entry &e)
98 : : {
99 : 28099289 : return ggc_marked_p (e.m_key);
100 : : }
101 : :
102 : : private:
103 : : template<typename T>
104 : : static void
105 : 184351 : pch_nx_helper (T &x, gt_pointer_operator op, void *cookie)
106 : : {
107 : 184351 : gt_pch_nx (&x, op, cookie);
108 : : }
109 : :
110 : : template<typename T>
111 : : static void
112 : 4421 : pch_nx_helper (T *&x, gt_pointer_operator op, void *cookie)
113 : : {
114 : 2876 : 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 : 906889958 : 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 : 901185877 : : m_table (n, ggc, sanitize_eq_and_hash, gather_mem_stats,
143 : : HASH_MAP_ORIGIN PASS_MEM_STAT)
144 : : {
145 : 2411904 : }
146 : :
147 : 28940760 : 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 : 28940760 : : 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 : 2277676 : 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 : 2277676 : hash_map *map = ggc_alloc<hash_map> ();
160 : 2277676 : new (map) hash_map (size, true, true, gather_mem_stats PASS_MEM_STAT);
161 : 2277676 : 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 : 4302573583 : bool put (const Key &k, const Value &v)
169 : : {
170 : 4302573583 : hash_entry *e = m_table.find_slot_with_hash (k, Traits::hash (k),
171 : : INSERT);
172 : 4302573583 : bool ins = Traits::is_empty (*e);
173 : 4302573583 : if (ins)
174 : : {
175 : 3965374293 : e->m_key = k;
176 : 3965374293 : new ((void *)&e->m_value) Value (v);
177 : 3965374293 : gcc_checking_assert (!Traits::is_empty (*e)
178 : : && !Traits::is_deleted (*e));
179 : : }
180 : : else
181 : 337199290 : e->m_value = v;
182 : :
183 : 4302573583 : return !ins;
184 : : }
185 : :
186 : : /* If the passed in key is in the map return pointer to its value
187 : : otherwise NULL. */
188 : :
189 : 16736587924 : Value *get (const Key &k)
190 : : {
191 : 16736587924 : hash_entry &e = m_table.find_with_hash (k, Traits::hash (k));
192 : 16698612380 : 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 : 2479585336 : Value &get_or_insert (const Key &k, bool *existed = NULL)
200 : : {
201 : 2479585336 : hash_entry *e = m_table.find_slot_with_hash (k, Traits::hash (k),
202 : : INSERT);
203 : 2479653648 : bool ins = Traits::is_empty (*e);
204 : 2479231953 : if (ins)
205 : : {
206 : 1714978500 : e->m_key = k;
207 : 1714978500 : new ((void *)&e->m_value) Value ();
208 : 1715263571 : gcc_checking_assert (!Traits::is_empty (*e)
209 : : && !Traits::is_deleted (*e));
210 : : }
211 : :
212 : 2479585336 : if (existed != NULL)
213 : 2344122894 : *existed = !ins;
214 : :
215 : 2479585336 : return e->m_value;
216 : : }
217 : :
218 : 161042658 : void remove (const Key &k)
219 : : {
220 : 161042658 : m_table.remove_elt_with_hash (k, Traits::hash (k));
221 : 138457839 : }
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 : 71317126 : void traverse (Arg a) const
230 : : {
231 : 267867354 : for (typename hash_table<hash_entry>::iterator iter = m_table.begin ();
232 : 464417582 : iter != m_table.end (); ++iter)
233 : 196550228 : if (!f ((*iter).m_key, (*iter).m_value, a))
234 : : break;
235 : 71317126 : }
236 : :
237 : : template<typename Arg, bool (*f)(const typename Traits::key_type &,
238 : : Value *, Arg)>
239 : 16559 : void traverse (Arg a) const
240 : : {
241 : 61245 : for (typename hash_table<hash_entry>::iterator iter = m_table.begin ();
242 : 105931 : iter != m_table.end (); ++iter)
243 : 44686 : if (!f ((*iter).m_key, &(*iter).m_value, a))
244 : : break;
245 : 16559 : }
246 : :
247 : 31364151 : size_t elements () const { return m_table.elements (); }
248 : :
249 : 357654093 : void empty () { m_table.empty(); }
250 : :
251 : : /* Return true when there are no elements in this hash map. */
252 : 4541448 : bool is_empty () const { return m_table.is_empty (); }
253 : :
254 : : class iterator
255 : : {
256 : : public:
257 : 484111865 : explicit iterator (const typename hash_table<hash_entry>::iterator &iter) :
258 : 127170909 : m_iter (iter) {}
259 : :
260 : 1230834742 : iterator &operator++ ()
261 : : {
262 : 1230834742 : ++m_iter;
263 : 1173244258 : 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 : 1287912756 : reference_pair (const Key &key, Value &value) : first (key), second (value) {}
275 : :
276 : : template <typename K, typename V>
277 : 238133 : operator std::pair<K, V> () const { return std::pair<K, V> (first, second); }
278 : : };
279 : :
280 : 1287912756 : reference_pair operator* ()
281 : : {
282 : 1287912756 : hash_entry &e = *m_iter;
283 : 497817324 : 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 : 1358005651 : bool operator != (const iterator &other) const
292 : : {
293 : 1484638798 : 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 : 127170909 : iterator begin () const { return iterator (m_table.begin ()); }
303 : 622165998 : 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 : 5875593 : gt_ggc_mx (hash_map<K, V, H> *h)
320 : : {
321 : 5875593 : gt_ggc_mx (&h->m_table);
322 : 5370571 : }
323 : :
324 : : template<typename K, typename V, typename H>
325 : : inline void
326 : 691 : gt_pch_nx (hash_map<K, V, H> *h)
327 : : {
328 : 691 : gt_pch_nx (&h->m_table);
329 : 691 : }
330 : :
331 : : template<typename K, typename V, typename H>
332 : : inline void
333 : 614166 : gt_cleare_cache (hash_map<K, V, H> *h)
334 : : {
335 : 614166 : if (h)
336 : 90456 : gt_cleare_cache (&h->m_table);
337 : : }
338 : :
339 : : template<typename K, typename V, typename H>
340 : : inline void
341 : 691 : gt_pch_nx (hash_map<K, V, H> *h, gt_pointer_operator op, void *cookie)
342 : : {
343 : 691 : op (&h->m_table.m_entries, NULL, cookie);
344 : 691 : }
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 : 124680851 : hash_map_maybe_create (hash_map<K,V,H> *&h,
350 : : size_t size = default_hash_map_size)
351 : : {
352 : 124680851 : if (!h)
353 : : {
354 : : if (ggc)
355 : 251534 : h = hash_map<K,V,H>::create_ggc (size);
356 : : else
357 : : h = new hash_map<K,V,H> (size);
358 : : }
359 : 124680851 : return h;
360 : : }
361 : :
362 : : /* Like h->get, but handles null h. */
363 : : template<typename K, typename V, typename H>
364 : : inline V*
365 : 304869221 : hash_map_safe_get (hash_map<K,V,H> *h, const K& k)
366 : : {
367 : 304869221 : 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 : 37452924 : 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 : 37452924 : 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 : 57338139 : 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 : 57338139 : return hash_map_maybe_create<ggc> (h, size)->put (k, v);
386 : : }
387 : :
388 : : #endif
|
