1 /* A type-safe hash map.
2 Copyright (C) 2014-2019 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 template<typename KeyId, typename Value,
25 typename Traits>
class(user)26 class GTY((user)) hash_map
27 {
28 typedef typename Traits::key_type Key;
29 struct hash_entry
30 {
31 Key m_key;
32 Value m_value;
33
34 typedef hash_entry value_type;
35 typedef Key compare_type;
36
37 static hashval_t hash (const hash_entry &e)
38 {
39 return Traits::hash (e.m_key);
40 }
41
42 static bool equal (const hash_entry &a, const Key &b)
43 {
44 return Traits::equal_keys (a.m_key, b);
45 }
46
47 static void remove (hash_entry &e) { Traits::remove (e); }
48
49 static void mark_deleted (hash_entry &e) { Traits::mark_deleted (e); }
50
51 static bool is_deleted (const hash_entry &e)
52 {
53 return Traits::is_deleted (e);
54 }
55
56 static void mark_empty (hash_entry &e) { Traits::mark_empty (e); }
57 static bool is_empty (const hash_entry &e) { return Traits::is_empty (e); }
58
59 static void ggc_mx (hash_entry &e)
60 {
61 gt_ggc_mx (e.m_key);
62 gt_ggc_mx (e.m_value);
63 }
64
65 static void ggc_maybe_mx (hash_entry &e)
66 {
67 if (Traits::maybe_mx)
68 ggc_mx (e);
69 }
70
71 static void pch_nx (hash_entry &e)
72 {
73 gt_pch_nx (e.m_key);
74 gt_pch_nx (e.m_value);
75 }
76
77 static void pch_nx (hash_entry &e, gt_pointer_operator op, void *c)
78 {
79 pch_nx_helper (e.m_key, op, c);
80 pch_nx_helper (e.m_value, op, c);
81 }
82
83 static int keep_cache_entry (hash_entry &e)
84 {
85 return ggc_marked_p (e.m_key);
86 }
87
88 private:
89 template<typename T>
90 static void
91 pch_nx_helper (T &x, gt_pointer_operator op, void *cookie)
92 {
93 gt_pch_nx (&x, op, cookie);
94 }
95
96 static void
97 pch_nx_helper (int, gt_pointer_operator, void *)
98 {
99 }
100
101 static void
102 pch_nx_helper (unsigned int, gt_pointer_operator, void *)
103 {
104 }
105
106 static void
107 pch_nx_helper (bool, gt_pointer_operator, void *)
108 {
109 }
110
111 template<typename T>
112 static void
113 pch_nx_helper (T *&x, gt_pointer_operator op, void *cookie)
114 {
115 op (&x, cookie);
116 }
117 };
118
119 public:
120 explicit hash_map (size_t n = 13, bool ggc = false,
121 bool gather_mem_stats = GATHER_STATISTICS
122 CXX_MEM_STAT_INFO)
123 : m_table (n, ggc, gather_mem_stats, HASH_MAP_ORIGIN PASS_MEM_STAT) {}
124
125 explicit hash_map (const hash_map &h, bool ggc = false,
126 bool gather_mem_stats = GATHER_STATISTICS
127 CXX_MEM_STAT_INFO)
128 : m_table (h.m_table, ggc, gather_mem_stats,
129 HASH_MAP_ORIGIN PASS_MEM_STAT) {}
130
131 /* Create a hash_map in ggc memory. */
132 static hash_map *create_ggc (size_t size,
133 bool gather_mem_stats = GATHER_STATISTICS
134 CXX_MEM_STAT_INFO)
135 {
136 hash_map *map = ggc_alloc<hash_map> ();
137 new (map) hash_map (size, true, gather_mem_stats PASS_MEM_STAT);
138 return map;
139 }
140
141 /* If key k isn't already in the map add key k with value v to the map, and
142 return false. Otherwise set the value of the entry for key k to be v and
143 return true. */
144
145 bool put (const Key &k, const Value &v)
146 {
147 hash_entry *e = m_table.find_slot_with_hash (k, Traits::hash (k),
148 INSERT);
149 bool existed = !hash_entry::is_empty (*e);
150 if (!existed)
151 e->m_key = k;
152
153 e->m_value = v;
154 return existed;
155 }
156
157 /* if the passed in key is in the map return its value otherwise NULL. */
158
159 Value *get (const Key &k)
160 {
161 hash_entry &e = m_table.find_with_hash (k, Traits::hash (k));
162 return Traits::is_empty (e) ? NULL : &e.m_value;
163 }
164
165 /* Return a reference to the value for the passed in key, creating the entry
166 if it doesn't already exist. If existed is not NULL then it is set to false
167 if the key was not previously in the map, and true otherwise. */
168
169 Value &get_or_insert (const Key &k, bool *existed = NULL)
170 {
171 hash_entry *e = m_table.find_slot_with_hash (k, Traits::hash (k),
172 INSERT);
173 bool ins = Traits::is_empty (*e);
174 if (ins)
175 e->m_key = k;
176
177 if (existed != NULL)
178 *existed = !ins;
179
180 return e->m_value;
181 }
182
183 void remove (const Key &k)
184 {
185 m_table.remove_elt_with_hash (k, Traits::hash (k));
186 }
187
188 /* Call the call back on each pair of key and value with the passed in
189 arg. */
190
191 template<typename Arg, bool (*f)(const typename Traits::key_type &,
192 const Value &, Arg)>
193 void traverse (Arg a) const
194 {
195 for (typename hash_table<hash_entry>::iterator iter = m_table.begin ();
196 iter != m_table.end (); ++iter)
197 f ((*iter).m_key, (*iter).m_value, a);
198 }
199
200 template<typename Arg, bool (*f)(const typename Traits::key_type &,
201 Value *, Arg)>
202 void traverse (Arg a) const
203 {
204 for (typename hash_table<hash_entry>::iterator iter = m_table.begin ();
205 iter != m_table.end (); ++iter)
206 if (!f ((*iter).m_key, &(*iter).m_value, a))
207 break;
208 }
209
210 size_t elements () const { return m_table.elements (); }
211
212 void empty () { m_table.empty(); }
213
214 class iterator
215 {
216 public:
217 explicit iterator (const typename hash_table<hash_entry>::iterator &iter) :
218 m_iter (iter) {}
219
220 iterator &operator++ ()
221 {
222 ++m_iter;
223 return *this;
224 }
225
226 /* Can't use std::pair here, because GCC before 4.3 don't handle
227 std::pair where template parameters are references well.
228 See PR86739. */
229 struct reference_pair {
230 const Key &first;
231 Value &second;
232
233 reference_pair (const Key &key, Value &value) : first (key), second (value) {}
234
235 template <typename K, typename V>
236 operator std::pair<K, V> () const { return std::pair<K, V> (first, second); }
237 };
238
239 reference_pair operator* ()
240 {
241 hash_entry &e = *m_iter;
242 return reference_pair (e.m_key, e.m_value);
243 }
244
245 bool
246 operator != (const iterator &other) const
247 {
248 return m_iter != other.m_iter;
249 }
250
251 private:
252 typename hash_table<hash_entry>::iterator m_iter;
253 };
254
255 /* Standard iterator retrieval methods. */
256
257 iterator begin () const { return iterator (m_table.begin ()); }
258 iterator end () const { return iterator (m_table.end ()); }
259
260 private:
261
262 template<typename T, typename U, typename V> friend void gt_ggc_mx (hash_map<T, U, V> *);
263 template<typename T, typename U, typename V> friend void gt_pch_nx (hash_map<T, U, V> *);
264 template<typename T, typename U, typename V> friend void gt_pch_nx (hash_map<T, U, V> *, gt_pointer_operator, void *);
265 template<typename T, typename U, typename V> friend void gt_cleare_cache (hash_map<T, U, V> *);
266
267 hash_table<hash_entry> m_table;
268 };
269
270 /* ggc marking routines. */
271
272 template<typename K, typename V, typename H>
273 static inline void
gt_ggc_mx(hash_map<K,V,H> * h)274 gt_ggc_mx (hash_map<K, V, H> *h)
275 {
276 gt_ggc_mx (&h->m_table);
277 }
278
279 template<typename K, typename V, typename H>
280 static inline void
gt_pch_nx(hash_map<K,V,H> * h)281 gt_pch_nx (hash_map<K, V, H> *h)
282 {
283 gt_pch_nx (&h->m_table);
284 }
285
286 template<typename K, typename V, typename H>
287 static inline void
gt_cleare_cache(hash_map<K,V,H> * h)288 gt_cleare_cache (hash_map<K, V, H> *h)
289 {
290 if (h)
291 gt_cleare_cache (&h->m_table);
292 }
293
294 template<typename K, typename V, typename H>
295 static inline void
gt_pch_nx(hash_map<K,V,H> * h,gt_pointer_operator op,void * cookie)296 gt_pch_nx (hash_map<K, V, H> *h, gt_pointer_operator op, void *cookie)
297 {
298 op (&h->m_table.m_entries, cookie);
299 }
300
301 #endif
302