Daily bump.
[official-gcc.git] / gcc / hash-map.h
blobdd039f10343567556d73e5077d97a0e175081c25
1 /* A type-safe hash map.
2 Copyright (C) 2014-2021 Free Software Foundation, Inc.
4 This file is part of GCC.
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.
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.
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/>. */
21 #ifndef hash_map_h
22 #define hash_map_h
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. */
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
41 typedef typename Traits::key_type Key;
42 struct hash_entry
44 Key m_key;
45 Value m_value;
47 typedef hash_entry value_type;
48 typedef Key compare_type;
50 static hashval_t hash (const hash_entry &e)
52 return Traits::hash (e.m_key);
55 static bool equal (const hash_entry &a, const Key &b)
57 return Traits::equal_keys (a.m_key, b);
60 static void remove (hash_entry &e) { Traits::remove (e); }
62 static void mark_deleted (hash_entry &e) { Traits::mark_deleted (e); }
64 static bool is_deleted (const hash_entry &e)
66 return Traits::is_deleted (e);
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); }
73 static void ggc_mx (hash_entry &e)
75 gt_ggc_mx (e.m_key);
76 gt_ggc_mx (e.m_value);
79 static void ggc_maybe_mx (hash_entry &e)
81 if (Traits::maybe_mx)
82 ggc_mx (e);
85 static void pch_nx (hash_entry &e)
87 gt_pch_nx (e.m_key);
88 gt_pch_nx (e.m_value);
91 static void pch_nx (hash_entry &e, gt_pointer_operator op, void *c)
93 pch_nx_helper (e.m_key, op, c);
94 pch_nx_helper (e.m_value, op, c);
97 static int keep_cache_entry (hash_entry &e)
99 return ggc_marked_p (e.m_key);
102 private:
103 template<typename T>
104 static void
105 pch_nx_helper (T &x, gt_pointer_operator op, void *cookie)
107 gt_pch_nx (&x, op, cookie);
110 template<typename T>
111 static void
112 pch_nx_helper (T *&x, gt_pointer_operator op, void *cookie)
114 op (&x, cookie);
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 *) { }
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);
134 #undef DEFINE_PCH_HELPER
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)
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) {}
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)
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;
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. */
168 bool put (const Key &k, const Value &v)
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)
175 e->m_key = k;
176 new ((void *) &e->m_value) Value (v);
178 else
179 e->m_value = v;
181 return !ins;
184 /* If the passed in key is in the map return pointer to its value
185 otherwise NULL. */
187 Value *get (const Key &k)
189 hash_entry &e = m_table.find_with_hash (k, Traits::hash (k));
190 return Traits::is_empty (e) ? NULL : &e.m_value;
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. */
197 Value &get_or_insert (const Key &k, bool *existed = NULL)
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)
204 e->m_key = k;
205 new ((void *)&e->m_value) Value ();
208 if (existed != NULL)
209 *existed = !ins;
211 return e->m_value;
214 void remove (const Key &k)
216 m_table.remove_elt_with_hash (k, Traits::hash (k));
219 /* Call the call back on each pair of key and value with the passed in
220 arg. */
222 template<typename Arg, bool (*f)(const typename Traits::key_type &,
223 const Value &, Arg)>
224 void traverse (Arg a) const
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);
231 template<typename Arg, bool (*f)(const typename Traits::key_type &,
232 Value *, Arg)>
233 void traverse (Arg a) const
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;
241 size_t elements () const { return m_table.elements (); }
243 void empty () { m_table.empty(); }
245 /* Return true when there are no elements in this hash map. */
246 bool is_empty () const { return m_table.is_empty (); }
248 class iterator
250 public:
251 explicit iterator (const typename hash_table<hash_entry>::iterator &iter) :
252 m_iter (iter) {}
254 iterator &operator++ ()
256 ++m_iter;
257 return *this;
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;
268 reference_pair (const Key &key, Value &value) : first (key), second (value) {}
270 template <typename K, typename V>
271 operator std::pair<K, V> () const { return std::pair<K, V> (first, second); }
274 reference_pair operator* ()
276 hash_entry &e = *m_iter;
277 return reference_pair (e.m_key, e.m_value);
280 bool operator== (const iterator &other) const
282 return m_iter == other.m_iter;
285 bool operator != (const iterator &other) const
287 return m_iter != other.m_iter;
290 private:
291 typename hash_table<hash_entry>::iterator m_iter;
294 /* Standard iterator retrieval methods. */
296 iterator begin () const { return iterator (m_table.begin ()); }
297 iterator end () const { return iterator (m_table.end ()); }
299 private:
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> *);
306 hash_table<hash_entry> m_table;
309 /* ggc marking routines. */
311 template<typename K, typename V, typename H>
312 static inline void
313 gt_ggc_mx (hash_map<K, V, H> *h)
315 gt_ggc_mx (&h->m_table);
318 template<typename K, typename V, typename H>
319 static inline void
320 gt_pch_nx (hash_map<K, V, H> *h)
322 gt_pch_nx (&h->m_table);
325 template<typename K, typename V, typename H>
326 static inline void
327 gt_cleare_cache (hash_map<K, V, H> *h)
329 if (h)
330 gt_cleare_cache (&h->m_table);
333 template<typename K, typename V, typename H>
334 static inline void
335 gt_pch_nx (hash_map<K, V, H> *h, gt_pointer_operator op, void *cookie)
337 op (&h->m_table.m_entries, cookie);
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)
346 if (!h)
348 if (ggc)
349 h = hash_map<K,V,H>::create_ggc (size);
350 else
351 h = new hash_map<K,V,H> (size);
353 return h;
356 /* Like h->get, but handles null h. */
357 template<typename K, typename V, typename H>
358 inline V*
359 hash_map_safe_get (hash_map<K,V,H> *h, const K& k)
361 return h ? h->get (k) : NULL;
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)
370 return hash_map_maybe_create<ggc> (h, size)->get_or_insert (k, e);
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)
379 return hash_map_maybe_create<ggc> (h, size)->put (k, v);
382 #endif