1 | /* Traits for hashable types. |
2 | Copyright (C) 2014-2023 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 | #ifndef hash_traits_h |
21 | #define hash_traits_h |
22 | |
23 | /* Helpful type for removing with free. */ |
24 | |
25 | template <typename Type> |
26 | struct typed_free_remove |
27 | { |
28 | static inline void remove (Type *p); |
29 | }; |
30 | |
31 | template <typename Type> |
32 | struct typed_const_free_remove |
33 | { |
34 | static inline void remove (const Type *p); |
35 | }; |
36 | |
37 | /* Remove with free. */ |
38 | |
39 | template <typename Type> |
40 | inline void |
41 | typed_free_remove <Type>::remove (Type *p) |
42 | { |
43 | free (p); |
44 | } |
45 | |
46 | template <typename Type> |
47 | inline void |
48 | typed_const_free_remove <Type>::remove (const Type *p) |
49 | { |
50 | free (const_cast <Type *> (p)); |
51 | } |
52 | |
53 | /* Helpful type for removing with delete. */ |
54 | |
55 | template <typename Type> |
56 | struct typed_delete_remove |
57 | { |
58 | static inline void remove (Type *p); |
59 | }; |
60 | |
61 | |
62 | /* Remove with delete. */ |
63 | |
64 | template <typename Type> |
65 | inline void |
66 | typed_delete_remove <Type>::remove (Type *p) |
67 | { |
68 | delete p; |
69 | } |
70 | |
71 | /* Helpful type for a no-op remove. */ |
72 | |
73 | template <typename Type> |
74 | struct typed_noop_remove |
75 | { |
76 | static inline void remove (Type &); |
77 | }; |
78 | |
79 | |
80 | /* Remove doing nothing. */ |
81 | |
82 | template <typename Type> |
83 | inline void |
84 | typed_noop_remove <Type>::remove (Type &) |
85 | { |
86 | } |
87 | |
88 | /* Base traits for integer type Type, providing just the hash and |
89 | comparison functionality. */ |
90 | |
91 | template <typename Type> |
92 | struct int_hash_base : typed_noop_remove <Type> |
93 | { |
94 | typedef Type value_type; |
95 | typedef Type compare_type; |
96 | |
97 | static inline hashval_t hash (value_type); |
98 | static inline bool equal (value_type existing, value_type candidate); |
99 | }; |
100 | |
101 | template <typename Type> |
102 | inline hashval_t |
103 | int_hash_base <Type>::hash (value_type x) |
104 | { |
105 | return x; |
106 | } |
107 | |
108 | template <typename Type> |
109 | inline bool |
110 | int_hash_base <Type>::equal (value_type x, value_type y) |
111 | { |
112 | return x == y; |
113 | } |
114 | |
115 | /* Hasher for integer type Type in which Empty is a spare value that can be |
116 | used to mark empty slots. If Deleted != Empty then Deleted is another |
117 | spare value that can be used for deleted slots; if Deleted == Empty then |
118 | hash table entries cannot be deleted. */ |
119 | |
120 | template <typename Type, Type Empty, Type Deleted = Empty> |
121 | struct int_hash : int_hash_base <Type> |
122 | { |
123 | typedef Type value_type; |
124 | typedef Type compare_type; |
125 | |
126 | static inline void mark_deleted (Type &); |
127 | static const bool empty_zero_p = Empty == 0; |
128 | static inline void mark_empty (Type &); |
129 | static inline bool is_deleted (Type); |
130 | static inline bool is_empty (Type); |
131 | }; |
132 | |
133 | template <typename Type, Type Empty, Type Deleted> |
134 | inline void |
135 | int_hash <Type, Empty, Deleted>::mark_deleted (Type &x) |
136 | { |
137 | gcc_assert (Empty != Deleted); |
138 | x = Deleted; |
139 | } |
140 | |
141 | template <typename Type, Type Empty, Type Deleted> |
142 | inline void |
143 | int_hash <Type, Empty, Deleted>::mark_empty (Type &x) |
144 | { |
145 | x = Empty; |
146 | } |
147 | |
148 | template <typename Type, Type Empty, Type Deleted> |
149 | inline bool |
150 | int_hash <Type, Empty, Deleted>::is_deleted (Type x) |
151 | { |
152 | return Empty != Deleted && x == Deleted; |
153 | } |
154 | |
155 | template <typename Type, Type Empty, Type Deleted> |
156 | inline bool |
157 | int_hash <Type, Empty, Deleted>::is_empty (Type x) |
158 | { |
159 | return x == Empty; |
160 | } |
161 | |
162 | /* Pointer hasher based on pointer equality. Other types of pointer hash |
163 | can inherit this and override the hash and equal functions with some |
164 | other form of equality (such as string equality). */ |
165 | |
166 | template <typename Type> |
167 | struct pointer_hash |
168 | { |
169 | typedef Type *value_type; |
170 | typedef Type *compare_type; |
171 | |
172 | static inline hashval_t hash (const value_type &); |
173 | static inline bool equal (const value_type &existing, |
174 | const compare_type &candidate); |
175 | static inline void mark_deleted (Type *&); |
176 | static const bool empty_zero_p = true; |
177 | static inline void mark_empty (Type *&); |
178 | static inline bool is_deleted (Type *); |
179 | static inline bool is_empty (Type *); |
180 | }; |
181 | |
182 | template <typename Type> |
183 | inline hashval_t |
184 | pointer_hash <Type>::hash (const value_type &candidate) |
185 | { |
186 | /* This is a really poor hash function, but it is what the current code uses, |
187 | so I am reusing it to avoid an additional axis in testing. */ |
188 | return (hashval_t) ((intptr_t)candidate >> 3); |
189 | } |
190 | |
191 | template <typename Type> |
192 | inline bool |
193 | pointer_hash <Type>::equal (const value_type &existing, |
194 | const compare_type &candidate) |
195 | { |
196 | return existing == candidate; |
197 | } |
198 | |
199 | template <typename Type> |
200 | inline void |
201 | pointer_hash <Type>::mark_deleted (Type *&e) |
202 | { |
203 | e = reinterpret_cast<Type *> (1); |
204 | } |
205 | |
206 | template <typename Type> |
207 | inline void |
208 | pointer_hash <Type>::mark_empty (Type *&e) |
209 | { |
210 | e = NULL; |
211 | } |
212 | |
213 | template <typename Type> |
214 | inline bool |
215 | pointer_hash <Type>::is_deleted (Type *e) |
216 | { |
217 | return e == reinterpret_cast<Type *> (1); |
218 | } |
219 | |
220 | template <typename Type> |
221 | inline bool |
222 | pointer_hash <Type>::is_empty (Type *e) |
223 | { |
224 | return e == NULL; |
225 | } |
226 | |
227 | /* Hasher for "const char *" strings, using string rather than pointer |
228 | equality. */ |
229 | |
230 | struct string_hash : pointer_hash <const char> |
231 | { |
232 | static inline hashval_t hash (const char *); |
233 | static inline bool equal (const char *, const char *); |
234 | }; |
235 | |
236 | inline hashval_t |
237 | string_hash::hash (const char *id) |
238 | { |
239 | return htab_hash_string (id); |
240 | } |
241 | |
242 | inline bool |
243 | string_hash::equal (const char *id1, const char *id2) |
244 | { |
245 | return strcmp (s1: id1, s2: id2) == 0; |
246 | } |
247 | |
248 | /* Remover and marker for entries in gc memory. */ |
249 | |
250 | template<typename T> |
251 | struct ggc_remove |
252 | { |
253 | static void remove (T &) {} |
254 | |
255 | static void |
256 | ggc_mx (T &p) |
257 | { |
258 | extern void gt_ggc_mx (T &); |
259 | gt_ggc_mx (p); |
260 | } |
261 | |
262 | /* Overridden in ggc_cache_remove. */ |
263 | static void |
264 | ggc_maybe_mx (T &p) |
265 | { |
266 | ggc_mx (p); |
267 | } |
268 | |
269 | static void |
270 | pch_nx (T &p) |
271 | { |
272 | extern void gt_pch_nx (T &); |
273 | gt_pch_nx (p); |
274 | } |
275 | |
276 | static void |
277 | pch_nx (T &p, gt_pointer_operator op, void *cookie) |
278 | { |
279 | op (&p, NULL, cookie); |
280 | } |
281 | }; |
282 | |
283 | /* Remover and marker for "cache" entries in gc memory. These entries can |
284 | be deleted if there are no non-cache references to the data. */ |
285 | |
286 | template<typename T> |
287 | struct ggc_cache_remove : ggc_remove<T> |
288 | { |
289 | /* Entries are weakly held because this is for caches. */ |
290 | static void ggc_maybe_mx (T &) {} |
291 | |
292 | static int |
293 | keep_cache_entry (T &e) |
294 | { |
295 | return ggc_marked_p (e) ? -1 : 0; |
296 | } |
297 | }; |
298 | |
299 | /* Traits for pointer elements that should not be freed when an element |
300 | is deleted. */ |
301 | |
302 | template <typename T> |
303 | struct nofree_ptr_hash : pointer_hash <T>, typed_noop_remove <T *> {}; |
304 | |
305 | /* Traits for pointer elements that should be freed via free() when an |
306 | element is deleted. */ |
307 | |
308 | template <typename T> |
309 | struct free_ptr_hash : pointer_hash <T>, typed_free_remove <T> {}; |
310 | |
311 | /* Traits for pointer elements that should be freed via delete operand when an |
312 | element is deleted. */ |
313 | |
314 | template <typename T> |
315 | struct delete_ptr_hash : pointer_hash <T>, typed_delete_remove <T> {}; |
316 | |
317 | /* Traits for elements that point to gc memory. The pointed-to data |
318 | must be kept across collections. */ |
319 | |
320 | template <typename T> |
321 | struct ggc_ptr_hash : pointer_hash <T>, ggc_remove <T *> {}; |
322 | |
323 | /* Traits for elements that point to gc memory. The elements don't |
324 | in themselves keep the pointed-to data alive and they can be deleted |
325 | if the pointed-to data is going to be collected. */ |
326 | |
327 | template <typename T> |
328 | struct ggc_cache_ptr_hash : pointer_hash <T>, ggc_cache_remove <T *> {}; |
329 | |
330 | /* Traits for string elements that should be freed when an element is |
331 | deleted. */ |
332 | |
333 | struct free_string_hash : string_hash, typed_const_free_remove <char> {}; |
334 | |
335 | /* Traits for string elements that should not be freed when an element |
336 | is deleted. */ |
337 | |
338 | struct nofree_string_hash : string_hash, typed_noop_remove <const char *> {}; |
339 | |
340 | /* Traits for pairs of values, using the first to record empty and |
341 | deleted slots. */ |
342 | |
343 | template <typename T1, typename T2> |
344 | struct pair_hash |
345 | { |
346 | typedef std::pair <typename T1::value_type, |
347 | typename T2::value_type> value_type; |
348 | typedef std::pair <typename T1::compare_type, |
349 | typename T2::compare_type> compare_type; |
350 | |
351 | static inline hashval_t hash (const value_type &); |
352 | static inline bool equal (const value_type &, const compare_type &); |
353 | static inline void remove (value_type &); |
354 | static inline void mark_deleted (value_type &); |
355 | static const bool empty_zero_p = T1::empty_zero_p; |
356 | static inline void mark_empty (value_type &); |
357 | static inline bool is_deleted (const value_type &); |
358 | static inline bool is_empty (const value_type &); |
359 | }; |
360 | |
361 | template <typename T1, typename T2> |
362 | inline hashval_t |
363 | pair_hash <T1, T2>::hash (const value_type &x) |
364 | { |
365 | return iterative_hash_hashval_t (T1::hash (x.first), T2::hash (x.second)); |
366 | } |
367 | |
368 | template <typename T1, typename T2> |
369 | inline bool |
370 | pair_hash <T1, T2>::equal (const value_type &x, const compare_type &y) |
371 | { |
372 | return T1::equal (x.first, y.first) && T2::equal (x.second, y.second); |
373 | } |
374 | |
375 | template <typename T1, typename T2> |
376 | inline void |
377 | pair_hash <T1, T2>::remove (value_type &x) |
378 | { |
379 | T1::remove (x.first); |
380 | T2::remove (x.second); |
381 | } |
382 | |
383 | template <typename T1, typename T2> |
384 | inline void |
385 | pair_hash <T1, T2>::mark_deleted (value_type &x) |
386 | { |
387 | T1::mark_deleted (x.first); |
388 | } |
389 | |
390 | template <typename T1, typename T2> |
391 | inline void |
392 | pair_hash <T1, T2>::mark_empty (value_type &x) |
393 | { |
394 | T1::mark_empty (x.first); |
395 | } |
396 | |
397 | template <typename T1, typename T2> |
398 | inline bool |
399 | pair_hash <T1, T2>::is_deleted (const value_type &x) |
400 | { |
401 | return T1::is_deleted (x.first); |
402 | } |
403 | |
404 | template <typename T1, typename T2> |
405 | inline bool |
406 | pair_hash <T1, T2>::is_empty (const value_type &x) |
407 | { |
408 | return T1::is_empty (x.first); |
409 | } |
410 | |
411 | /* Base traits for vectors, providing just the hash and comparison |
412 | functionality. Type gives the corresponding traits for the element |
413 | type. */ |
414 | |
415 | template <typename Type> |
416 | struct vec_hash_base |
417 | { |
418 | typedef vec<typename Type::value_type> value_type; |
419 | typedef vec<typename Type::compare_type> compare_type; |
420 | |
421 | static inline hashval_t hash (value_type); |
422 | static inline bool equal (value_type, compare_type); |
423 | }; |
424 | |
425 | template <typename Type> |
426 | inline hashval_t |
427 | vec_hash_base <Type>::hash (value_type x) |
428 | { |
429 | inchash::hash hstate; |
430 | hstate.add_int (v: x.length ()); |
431 | for (auto &value : x) |
432 | hstate.merge_hash (other: Type::hash (value)); |
433 | return hstate.end (); |
434 | } |
435 | |
436 | template <typename Type> |
437 | inline bool |
438 | vec_hash_base <Type>::equal (value_type x, compare_type y) |
439 | { |
440 | if (x.length () != y.length ()) |
441 | return false; |
442 | for (unsigned int i = 0; i < x.length (); ++i) |
443 | if (!Type::equal (x[i], y[i])) |
444 | return false; |
445 | return true; |
446 | } |
447 | |
448 | /* Traits for vectors whose contents should be freed normally. */ |
449 | |
450 | template <typename Type> |
451 | struct vec_free_hash_base : vec_hash_base <Type> |
452 | { |
453 | static void remove (typename vec_hash_base <Type>::value_type &); |
454 | }; |
455 | |
456 | template <typename Type> |
457 | void |
458 | vec_free_hash_base <Type> |
459 | ::remove (typename vec_hash_base <Type>::value_type &x) |
460 | { |
461 | for (auto &value : x) |
462 | Type::remove (x); |
463 | x.release (); |
464 | } |
465 | |
466 | template <typename T> struct default_hash_traits : T {}; |
467 | |
468 | template <typename T> |
469 | struct default_hash_traits <T *> : ggc_ptr_hash <T> {}; |
470 | |
471 | #endif |
472 | |