Line data Source code
1 : /* Traits for hashable types.
2 : Copyright (C) 2014-2026 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 92370944 : typed_free_remove <Type>::remove (Type *p)
42 : {
43 92370944 : free (p);
44 92370944 : }
45 :
46 : template <typename Type>
47 : inline void
48 92896924 : typed_const_free_remove <Type>::remove (const Type *p)
49 : {
50 92896924 : free (const_cast <Type *> (p));
51 67 : }
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 2616964 : typed_delete_remove <Type>::remove (Type *p)
67 : {
68 8130879 : delete p;
69 2616964 : }
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 197760249 : typed_noop_remove <Type>::remove (Type &)
85 : {
86 197760249 : }
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 10664031354 : int_hash_base <Type>::hash (value_type x)
104 : {
105 10664031354 : 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 5219865 : int_hash <Type, Empty, Deleted>::mark_deleted (Type &x)
136 : {
137 : gcc_assert (Empty != Deleted);
138 5219865 : x = Deleted;
139 : }
140 :
141 : template <typename Type, Type Empty, Type Deleted>
142 : inline void
143 1668018852 : int_hash <Type, Empty, Deleted>::mark_empty (Type &x)
144 : {
145 1668018852 : x = Empty;
146 : }
147 :
148 : template <typename Type, Type Empty, Type Deleted>
149 : inline bool
150 12811016322 : int_hash <Type, Empty, Deleted>::is_deleted (Type x)
151 : {
152 12811016322 : 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 >44124*10^7 : 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 >44124*10^7 : return (hashval_t) ((intptr_t)candidate >> 3);
189 : }
190 :
191 : template <typename Type>
192 : inline bool
193 >40277*10^7 : pointer_hash <Type>::equal (const value_type &existing,
194 : const compare_type &candidate)
195 : {
196 >40277*10^7 : return existing == candidate;
197 : }
198 :
199 : template <typename Type>
200 : inline void
201 714195547 : pointer_hash <Type>::mark_deleted (Type *&e)
202 : {
203 571559618 : e = reinterpret_cast<Type *> (1);
204 : }
205 :
206 : template <typename Type>
207 : inline void
208 266819406 : pointer_hash <Type>::mark_empty (Type *&e)
209 : {
210 266819406 : e = NULL;
211 : }
212 :
213 : template <typename Type>
214 : inline bool
215 >67902*10^7 : pointer_hash <Type>::is_deleted (Type *e)
216 : {
217 >67902*10^7 : 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 13386355817 : string_hash::hash (const char *id)
238 : {
239 13386355817 : return htab_hash_string (id);
240 : }
241 :
242 : inline bool
243 10087739199 : string_hash::equal (const char *id1, const char *id2)
244 : {
245 10087739199 : return strcmp (id1, id2) == 0;
246 : }
247 :
248 : /* Remover and marker for entries in gc memory. */
249 :
250 : template<typename T>
251 : struct ggc_remove
252 : {
253 2591 : static void remove (T &) {}
254 :
255 : static void
256 4926605334 : ggc_mx (T &p)
257 : {
258 : extern void gt_ggc_mx (T &);
259 4027752905 : gt_ggc_mx (p);
260 1776029933 : }
261 :
262 : /* Overridden in ggc_cache_remove. */
263 : static void
264 3150575401 : ggc_maybe_mx (T &p)
265 : {
266 3150575401 : ggc_mx (p);
267 3150575401 : }
268 :
269 : static void
270 1825587 : pch_nx (T &p)
271 : {
272 : extern void gt_pch_nx (T &);
273 1825587 : gt_pch_nx (p);
274 1825587 : }
275 :
276 : static void
277 1825587 : pch_nx (T &p, gt_pointer_operator op, void *cookie)
278 : {
279 1825587 : op (&p, NULL, cookie);
280 1825587 : }
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 617264758 : keep_cache_entry (T &e)
294 : {
295 617264758 : 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 295120921 : pair_hash <T1, T2>::hash (const value_type &x)
364 : {
365 295120921 : 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 271918927 : pair_hash <T1, T2>::equal (const value_type &x, const compare_type &y)
371 : {
372 271918927 : 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 0 : pair_hash <T1, T2>::mark_empty (value_type &x)
393 : {
394 0 : T1::mark_empty (x.first);
395 : }
396 :
397 : template <typename T1, typename T2>
398 : inline bool
399 361128741 : pair_hash <T1, T2>::is_deleted (const value_type &x)
400 : {
401 39243323 : return T1::is_deleted (x.first);
402 : }
403 :
404 : template <typename T1, typename T2>
405 : inline bool
406 1196251034 : pair_hash <T1, T2>::is_empty (const value_type &x)
407 : {
408 1157015903 : 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 22195 : vec_hash_base <Type>::hash (value_type x)
428 : {
429 22195 : inchash::hash hstate;
430 22195 : hstate.add_int (x.length ());
431 103501 : for (auto &value : x)
432 59111 : hstate.merge_hash (Type::hash (value));
433 22195 : return hstate.end ();
434 : }
435 :
436 : template <typename Type>
437 : inline bool
438 6219 : vec_hash_base <Type>::equal (value_type x, compare_type y)
439 : {
440 12438 : if (x.length () != y.length ())
441 : return false;
442 17453 : for (unsigned int i = 0; i < x.length (); ++i)
443 11957 : 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
|
