1/* Traits for hashable types.
2 Copyright (C) 2014-2026 Free Software Foundation, Inc.
3
4This file is part of GCC.
5
6GCC is free software; you can redistribute it and/or modify it under
7the terms of the GNU General Public License as published by the Free
8Software Foundation; either version 3, or (at your option) any later
9version.
10
11GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12WARRANTY; without even the implied warranty of MERCHANTABILITY or
13FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14for more details.
15
16You should have received a copy of the GNU General Public License
17along 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
25template <typename Type>
26struct typed_free_remove
27{
28 static inline void remove (Type *p);
29};
30
31template <typename Type>
32struct typed_const_free_remove
33{
34 static inline void remove (const Type *p);
35};
36
37/* Remove with free. */
38
39template <typename Type>
40inline void
41typed_free_remove <Type>::remove (Type *p)
42{
43 free (p);
44}
45
46template <typename Type>
47inline void
48typed_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
55template <typename Type>
56struct typed_delete_remove
57{
58 static inline void remove (Type *p);
59};
60
61
62/* Remove with delete. */
63
64template <typename Type>
65inline void
66typed_delete_remove <Type>::remove (Type *p)
67{
68 delete p;
69}
70
71/* Helpful type for a no-op remove. */
72
73template <typename Type>
74struct typed_noop_remove
75{
76 static inline void remove (Type &);
77};
78
79
80/* Remove doing nothing. */
81
82template <typename Type>
83inline void
84typed_noop_remove <Type>::remove (Type &)
85{
86}
87
88/* Base traits for integer type Type, providing just the hash and
89 comparison functionality. */
90
91template <typename Type>
92struct 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
101template <typename Type>
102inline hashval_t
103int_hash_base <Type>::hash (value_type x)
104{
105 return x;
106}
107
108template <typename Type>
109inline bool
110int_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
120template <typename Type, Type Empty, Type Deleted = Empty>
121struct 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
133template <typename Type, Type Empty, Type Deleted>
134inline void
135int_hash <Type, Empty, Deleted>::mark_deleted (Type &x)
136{
137 gcc_assert (Empty != Deleted);
138 x = Deleted;
139}
140
141template <typename Type, Type Empty, Type Deleted>
142inline void
143int_hash <Type, Empty, Deleted>::mark_empty (Type &x)
144{
145 x = Empty;
146}
147
148template <typename Type, Type Empty, Type Deleted>
149inline bool
150int_hash <Type, Empty, Deleted>::is_deleted (Type x)
151{
152 return Empty != Deleted && x == Deleted;
153}
154
155template <typename Type, Type Empty, Type Deleted>
156inline bool
157int_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
166template <typename Type>
167struct 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
182template <typename Type>
183inline hashval_t
184pointer_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
191template <typename Type>
192inline bool
193pointer_hash <Type>::equal (const value_type &existing,
194 const compare_type &candidate)
195{
196 return existing == candidate;
197}
198
199template <typename Type>
200inline void
201pointer_hash <Type>::mark_deleted (Type *&e)
202{
203 e = reinterpret_cast<Type *> (1);
204}
205
206template <typename Type>
207inline void
208pointer_hash <Type>::mark_empty (Type *&e)
209{
210 e = NULL;
211}
212
213template <typename Type>
214inline bool
215pointer_hash <Type>::is_deleted (Type *e)
216{
217 return e == reinterpret_cast<Type *> (1);
218}
219
220template <typename Type>
221inline bool
222pointer_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
230struct 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
236inline hashval_t
237string_hash::hash (const char *id)
238{
239 return htab_hash_string (id);
240}
241
242inline bool
243string_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
250template<typename T>
251struct 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
286template<typename T>
287struct 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
302template <typename T>
303struct 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
308template <typename T>
309struct 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
314template <typename T>
315struct 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
320template <typename T>
321struct 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
327template <typename T>
328struct 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
333struct 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
338struct 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
343template <typename T1, typename T2>
344struct 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
361template <typename T1, typename T2>
362inline hashval_t
363pair_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
368template <typename T1, typename T2>
369inline bool
370pair_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
375template <typename T1, typename T2>
376inline void
377pair_hash <T1, T2>::remove (value_type &x)
378{
379 T1::remove (x.first);
380 T2::remove (x.second);
381}
382
383template <typename T1, typename T2>
384inline void
385pair_hash <T1, T2>::mark_deleted (value_type &x)
386{
387 T1::mark_deleted (x.first);
388}
389
390template <typename T1, typename T2>
391inline void
392pair_hash <T1, T2>::mark_empty (value_type &x)
393{
394 T1::mark_empty (x.first);
395}
396
397template <typename T1, typename T2>
398inline bool
399pair_hash <T1, T2>::is_deleted (const value_type &x)
400{
401 return T1::is_deleted (x.first);
402}
403
404template <typename T1, typename T2>
405inline bool
406pair_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
415template <typename Type>
416struct 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
425template <typename Type>
426inline hashval_t
427vec_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
436template <typename Type>
437inline bool
438vec_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
450template <typename Type>
451struct vec_free_hash_base : vec_hash_base <Type>
452{
453 static void remove (typename vec_hash_base <Type>::value_type &);
454};
455
456template <typename Type>
457void
458vec_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
466template <typename T> struct default_hash_traits : T {};
467
468template <typename T>
469struct default_hash_traits <T *> : ggc_ptr_hash <T> {};
470
471#endif
472

source code of gcc/hash-traits.h