Branch data Line data Source code
1 : : /* Traits for hashable types.
2 : : Copyright (C) 2014-2024 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 : 92656209 : typed_free_remove <Type>::remove (Type *p)
42 : : {
43 : 92656209 : free (p);
44 : 92656209 : }
45 : :
46 : : template <typename Type>
47 : : inline void
48 : 89454787 : typed_const_free_remove <Type>::remove (const Type *p)
49 : : {
50 : 89454787 : free (const_cast <Type *> (p));
51 : 58 : }
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 : 2696889 : typed_delete_remove <Type>::remove (Type *p)
67 : : {
68 : 8165871 : delete p;
69 : 2696889 : }
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 : 160168722 : typed_noop_remove <Type>::remove (Type &)
85 : : {
86 : 160168722 : }
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 : 8798994835 : int_hash_base <Type>::hash (value_type x)
104 : : {
105 : 8798994835 : 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 : 4484317 : int_hash <Type, Empty, Deleted>::mark_deleted (Type &x)
136 : : {
137 : : gcc_assert (Empty != Deleted);
138 : 4484317 : x = Deleted;
139 : : }
140 : :
141 : : template <typename Type, Type Empty, Type Deleted>
142 : : inline void
143 : 1582847084 : int_hash <Type, Empty, Deleted>::mark_empty (Type &x)
144 : : {
145 : 1582847084 : x = Empty;
146 : : }
147 : :
148 : : template <typename Type, Type Empty, Type Deleted>
149 : : inline bool
150 : 10214101072 : int_hash <Type, Empty, Deleted>::is_deleted (Type x)
151 : : {
152 : 10214101072 : 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 : >30493*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 : >30493*10^7 : return (hashval_t) ((intptr_t)candidate >> 3);
189 : : }
190 : :
191 : : template <typename Type>
192 : : inline bool
193 : >27461*10^7 : pointer_hash <Type>::equal (const value_type &existing,
194 : : const compare_type &candidate)
195 : : {
196 : >27461*10^7 : return existing == candidate;
197 : : }
198 : :
199 : : template <typename Type>
200 : : inline void
201 : 638480242 : pointer_hash <Type>::mark_deleted (Type *&e)
202 : : {
203 : 528894221 : e = reinterpret_cast<Type *> (1);
204 : : }
205 : :
206 : : template <typename Type>
207 : : inline void
208 : 250293595 : pointer_hash <Type>::mark_empty (Type *&e)
209 : : {
210 : 250293595 : e = NULL;
211 : : }
212 : :
213 : : template <typename Type>
214 : : inline bool
215 : >47485*10^7 : pointer_hash <Type>::is_deleted (Type *e)
216 : : {
217 : >47485*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 : 10296983203 : string_hash::hash (const char *id)
238 : : {
239 : 10296983203 : return htab_hash_string (id);
240 : : }
241 : :
242 : : inline bool
243 : 7765396069 : string_hash::equal (const char *id1, const char *id2)
244 : : {
245 : 7765396069 : 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 : 4505 : static void remove (T &) {}
254 : :
255 : : static void
256 : 4088756165 : ggc_mx (T &p)
257 : : {
258 : : extern void gt_ggc_mx (T &);
259 : 3400366961 : gt_ggc_mx (p);
260 : 1557899690 : }
261 : :
262 : : /* Overridden in ggc_cache_remove. */
263 : : static void
264 : 2530856475 : ggc_maybe_mx (T &p)
265 : : {
266 : 2530856475 : ggc_mx (p);
267 : 2530856475 : }
268 : :
269 : : static void
270 : 1522202 : pch_nx (T &p)
271 : : {
272 : : extern void gt_pch_nx (T &);
273 : 1522202 : gt_pch_nx (p);
274 : 1522202 : }
275 : :
276 : : static void
277 : 1522202 : pch_nx (T &p, gt_pointer_operator op, void *cookie)
278 : : {
279 : 1522202 : op (&p, NULL, cookie);
280 : 1522202 : }
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 : 243882167 : keep_cache_entry (T &e)
294 : : {
295 : 243882167 : 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 : 281133405 : pair_hash <T1, T2>::hash (const value_type &x)
364 : : {
365 : 281133405 : 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 : 258708849 : pair_hash <T1, T2>::equal (const value_type &x, const compare_type &y)
371 : : {
372 : 258708849 : 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 : 343891643 : pair_hash <T1, T2>::is_deleted (const value_type &x)
400 : : {
401 : 37034081 : return T1::is_deleted (x.first);
402 : : }
403 : :
404 : : template <typename T1, typename T2>
405 : : inline bool
406 : 1130353501 : pair_hash <T1, T2>::is_empty (const value_type &x)
407 : : {
408 : 1093320020 : 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 : 17574 : vec_hash_base <Type>::hash (value_type x)
428 : : {
429 : 17574 : inchash::hash hstate;
430 : 17574 : hstate.add_int (x.length ());
431 : 86081 : for (auto &value : x)
432 : 50933 : hstate.merge_hash (Type::hash (value));
433 : 17574 : return hstate.end ();
434 : : }
435 : :
436 : : template <typename Type>
437 : : inline bool
438 : 4483 : vec_hash_base <Type>::equal (value_type x, compare_type y)
439 : : {
440 : 8966 : if (x.length () != y.length ())
441 : : return false;
442 : 11429 : for (unsigned int i = 0; i < x.length (); ++i)
443 : 7971 : 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
|
