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 (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 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 (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
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