]>
Commit | Line | Data |
---|---|---|
f11c3779 | 1 | /* Traits for hashable types. |
7adcbafe | 2 | Copyright (C) 2014-2022 Free Software Foundation, Inc. |
f11c3779 RS |
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 | ||
bc84b61b MNW |
31 | template <typename Type> |
32 | struct typed_const_free_remove | |
33 | { | |
34 | static inline void remove (const Type *p); | |
35 | }; | |
f11c3779 RS |
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 | ||
bc84b61b MNW |
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 | ||
74fbae92 ML |
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 | } | |
f11c3779 RS |
70 | |
71 | /* Helpful type for a no-op remove. */ | |
72 | ||
73 | template <typename Type> | |
74 | struct typed_noop_remove | |
75 | { | |
fc17926a | 76 | static inline void remove (Type &); |
f11c3779 RS |
77 | }; |
78 | ||
79 | ||
80 | /* Remove doing nothing. */ | |
81 | ||
82 | template <typename Type> | |
83 | inline void | |
fc17926a | 84 | typed_noop_remove <Type>::remove (Type &) |
f11c3779 RS |
85 | { |
86 | } | |
87 | ||
8c6952ab RS |
88 | /* Base traits for integer type Type, providing just the hash and |
89 | comparison functionality. */ | |
f11c3779 | 90 | |
8c6952ab RS |
91 | template <typename Type> |
92 | struct int_hash_base : typed_noop_remove <Type> | |
e0702244 RS |
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); | |
e0702244 RS |
99 | }; |
100 | ||
8c6952ab | 101 | template <typename Type> |
e0702244 | 102 | inline hashval_t |
8c6952ab | 103 | int_hash_base <Type>::hash (value_type x) |
e0702244 RS |
104 | { |
105 | return x; | |
106 | } | |
107 | ||
8c6952ab | 108 | template <typename Type> |
e0702244 | 109 | inline bool |
8c6952ab | 110 | int_hash_base <Type>::equal (value_type x, value_type y) |
e0702244 RS |
111 | { |
112 | return x == y; | |
113 | } | |
114 | ||
8c6952ab RS |
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 | ||
e0702244 RS |
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 | ||
8d67ee55 RS |
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). */ | |
f11c3779 RS |
165 | |
166 | template <typename Type> | |
8d67ee55 | 167 | struct pointer_hash |
f11c3779 RS |
168 | { |
169 | typedef Type *value_type; | |
170 | typedef Type *compare_type; | |
171 | ||
172 | static inline hashval_t hash (const value_type &); | |
f11c3779 RS |
173 | static inline bool equal (const value_type &existing, |
174 | const compare_type &candidate); | |
843adf88 | 175 | static inline void mark_deleted (Type *&); |
7ca50de0 | 176 | static const bool empty_zero_p = true; |
843adf88 RS |
177 | static inline void mark_empty (Type *&); |
178 | static inline bool is_deleted (Type *); | |
179 | static inline bool is_empty (Type *); | |
f11c3779 RS |
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 | ||
843adf88 RS |
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 | ||
20d2c372 RS |
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 (id1, id2) == 0; | |
246 | } | |
247 | ||
ca752f39 | 248 | /* Remover and marker for entries in gc memory. */ |
f11c3779 RS |
249 | |
250 | template<typename T> | |
ca752f39 | 251 | struct ggc_remove |
f11c3779 | 252 | { |
5ac6389b | 253 | static void remove (T &) {} |
f11c3779 RS |
254 | |
255 | static void | |
5ac6389b | 256 | ggc_mx (T &p) |
f11c3779 RS |
257 | { |
258 | extern void gt_ggc_mx (T &); | |
259 | gt_ggc_mx (p); | |
260 | } | |
261 | ||
21faa101 JM |
262 | /* Overridden in ggc_cache_remove. */ |
263 | static void | |
264 | ggc_maybe_mx (T &p) | |
265 | { | |
266 | ggc_mx (p); | |
267 | } | |
268 | ||
f11c3779 RS |
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 | { | |
747380f4 | 279 | op (&p, NULL, cookie); |
f11c3779 RS |
280 | } |
281 | }; | |
282 | ||
6c907cff RS |
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. */ | |
f11c3779 RS |
285 | |
286 | template<typename T> | |
6c907cff | 287 | struct ggc_cache_remove : ggc_remove<T> |
f11c3779 | 288 | { |
f11c3779 | 289 | /* Entries are weakly held because this is for caches. */ |
21faa101 | 290 | static void ggc_maybe_mx (T &) {} |
f11c3779 | 291 | |
08ec2754 RS |
292 | static int |
293 | keep_cache_entry (T &e) | |
f11c3779 | 294 | { |
08ec2754 | 295 | return ggc_marked_p (e) ? -1 : 0; |
f11c3779 RS |
296 | } |
297 | }; | |
298 | ||
8d67ee55 RS |
299 | /* Traits for pointer elements that should not be freed when an element |
300 | is deleted. */ | |
301 | ||
302 | template <typename T> | |
fc17926a | 303 | struct nofree_ptr_hash : pointer_hash <T>, typed_noop_remove <T *> {}; |
8d67ee55 | 304 | |
95fbe13e RS |
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 | ||
74fbae92 ML |
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 | ||
ca752f39 RS |
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 | ||
6c907cff RS |
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 | ||
bc84b61b MNW |
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 | ||
20d2c372 RS |
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 | ||
9adee305 RS |
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 &); | |
7ca50de0 | 355 | static const bool empty_zero_p = T1::empty_zero_p; |
9adee305 RS |
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 | ||
050309d1 RS |
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 (x.length ()); | |
431 | for (auto &value : x) | |
432 | hstate.merge_hash (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 | ||
fb5c464a | 466 | template <typename T> struct default_hash_traits : T {}; |
b32ca1df RS |
467 | |
468 | template <typename T> | |
469 | struct default_hash_traits <T *> : ggc_ptr_hash <T> {}; | |
470 | ||
f11c3779 | 471 | #endif |