1 /* Traits for hashable types.
2 Copyright (C) 2014-2022 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
remove(Type * p)41 typed_free_remove <Type>::remove (Type *p)
42 {
43 free (p);
44 }
45
46 template <typename Type>
47 inline void
remove(const Type * p)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
remove(Type * p)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
remove(Type &)84 typed_noop_remove <Type>::remove (Type &)
85 {
86 }
87
88
89 /* Hasher for integer type Type in which Empty is a spare value that can be
90 used to mark empty slots. If Deleted != Empty then Deleted is another
91 spare value that can be used for deleted slots; if Deleted == Empty then
92 hash table entries cannot be deleted. */
93
94 template <typename Type, Type Empty, Type Deleted = Empty>
95 struct int_hash : typed_noop_remove <Type>
96 {
97 typedef Type value_type;
98 typedef Type compare_type;
99
100 static inline hashval_t hash (value_type);
101 static inline bool equal (value_type existing, value_type candidate);
102 static inline void mark_deleted (Type &);
103 static const bool empty_zero_p = Empty == 0;
104 static inline void mark_empty (Type &);
105 static inline bool is_deleted (Type);
106 static inline bool is_empty (Type);
107 };
108
109 template <typename Type, Type Empty, Type Deleted>
110 inline hashval_t
hash(value_type x)111 int_hash <Type, Empty, Deleted>::hash (value_type x)
112 {
113 return x;
114 }
115
116 template <typename Type, Type Empty, Type Deleted>
117 inline bool
equal(value_type x,value_type y)118 int_hash <Type, Empty, Deleted>::equal (value_type x, value_type y)
119 {
120 return x == y;
121 }
122
123 template <typename Type, Type Empty, Type Deleted>
124 inline void
mark_deleted(Type & x)125 int_hash <Type, Empty, Deleted>::mark_deleted (Type &x)
126 {
127 gcc_assert (Empty != Deleted);
128 x = Deleted;
129 }
130
131 template <typename Type, Type Empty, Type Deleted>
132 inline void
mark_empty(Type & x)133 int_hash <Type, Empty, Deleted>::mark_empty (Type &x)
134 {
135 x = Empty;
136 }
137
138 template <typename Type, Type Empty, Type Deleted>
139 inline bool
is_deleted(Type x)140 int_hash <Type, Empty, Deleted>::is_deleted (Type x)
141 {
142 return Empty != Deleted && x == Deleted;
143 }
144
145 template <typename Type, Type Empty, Type Deleted>
146 inline bool
is_empty(Type x)147 int_hash <Type, Empty, Deleted>::is_empty (Type x)
148 {
149 return x == Empty;
150 }
151
152 /* Pointer hasher based on pointer equality. Other types of pointer hash
153 can inherit this and override the hash and equal functions with some
154 other form of equality (such as string equality). */
155
156 template <typename Type>
157 struct pointer_hash
158 {
159 typedef Type *value_type;
160 typedef Type *compare_type;
161
162 static inline hashval_t hash (const value_type &);
163 static inline bool equal (const value_type &existing,
164 const compare_type &candidate);
165 static inline void mark_deleted (Type *&);
166 static const bool empty_zero_p = true;
167 static inline void mark_empty (Type *&);
168 static inline bool is_deleted (Type *);
169 static inline bool is_empty (Type *);
170 };
171
172 template <typename Type>
173 inline hashval_t
hash(const value_type & candidate)174 pointer_hash <Type>::hash (const value_type &candidate)
175 {
176 /* This is a really poor hash function, but it is what the current code uses,
177 so I am reusing it to avoid an additional axis in testing. */
178 return (hashval_t) ((intptr_t)candidate >> 3);
179 }
180
181 template <typename Type>
182 inline bool
equal(const value_type & existing,const compare_type & candidate)183 pointer_hash <Type>::equal (const value_type &existing,
184 const compare_type &candidate)
185 {
186 return existing == candidate;
187 }
188
189 template <typename Type>
190 inline void
mark_deleted(Type * & e)191 pointer_hash <Type>::mark_deleted (Type *&e)
192 {
193 e = reinterpret_cast<Type *> (1);
194 }
195
196 template <typename Type>
197 inline void
mark_empty(Type * & e)198 pointer_hash <Type>::mark_empty (Type *&e)
199 {
200 e = NULL;
201 }
202
203 template <typename Type>
204 inline bool
is_deleted(Type * e)205 pointer_hash <Type>::is_deleted (Type *e)
206 {
207 return e == reinterpret_cast<Type *> (1);
208 }
209
210 template <typename Type>
211 inline bool
is_empty(Type * e)212 pointer_hash <Type>::is_empty (Type *e)
213 {
214 return e == NULL;
215 }
216
217 /* Hasher for "const char *" strings, using string rather than pointer
218 equality. */
219
220 struct string_hash : pointer_hash <const char>
221 {
222 static inline hashval_t hash (const char *);
223 static inline bool equal (const char *, const char *);
224 };
225
226 inline hashval_t
hash(const char * id)227 string_hash::hash (const char *id)
228 {
229 return htab_hash_string (id);
230 }
231
232 inline bool
equal(const char * id1,const char * id2)233 string_hash::equal (const char *id1, const char *id2)
234 {
235 return strcmp (id1, id2) == 0;
236 }
237
238 /* Remover and marker for entries in gc memory. */
239
240 template<typename T>
241 struct ggc_remove
242 {
removeggc_remove243 static void remove (T &) {}
244
245 static void
ggc_mxggc_remove246 ggc_mx (T &p)
247 {
248 extern void gt_ggc_mx (T &);
249 gt_ggc_mx (p);
250 }
251
252 /* Overridden in ggc_cache_remove. */
253 static void
ggc_maybe_mxggc_remove254 ggc_maybe_mx (T &p)
255 {
256 ggc_mx (p);
257 }
258
259 static void
pch_nxggc_remove260 pch_nx (T &p)
261 {
262 extern void gt_pch_nx (T &);
263 gt_pch_nx (p);
264 }
265
266 static void
pch_nxggc_remove267 pch_nx (T &p, gt_pointer_operator op, void *cookie)
268 {
269 op (&p, NULL, cookie);
270 }
271 };
272
273 /* Remover and marker for "cache" entries in gc memory. These entries can
274 be deleted if there are no non-cache references to the data. */
275
276 template<typename T>
277 struct ggc_cache_remove : ggc_remove<T>
278 {
279 /* Entries are weakly held because this is for caches. */
ggc_maybe_mxggc_cache_remove280 static void ggc_maybe_mx (T &) {}
281
282 static int
keep_cache_entryggc_cache_remove283 keep_cache_entry (T &e)
284 {
285 return ggc_marked_p (e) ? -1 : 0;
286 }
287 };
288
289 /* Traits for pointer elements that should not be freed when an element
290 is deleted. */
291
292 template <typename T>
293 struct nofree_ptr_hash : pointer_hash <T>, typed_noop_remove <T *> {};
294
295 /* Traits for pointer elements that should be freed via free() when an
296 element is deleted. */
297
298 template <typename T>
299 struct free_ptr_hash : pointer_hash <T>, typed_free_remove <T> {};
300
301 /* Traits for pointer elements that should be freed via delete operand when an
302 element is deleted. */
303
304 template <typename T>
305 struct delete_ptr_hash : pointer_hash <T>, typed_delete_remove <T> {};
306
307 /* Traits for elements that point to gc memory. The pointed-to data
308 must be kept across collections. */
309
310 template <typename T>
311 struct ggc_ptr_hash : pointer_hash <T>, ggc_remove <T *> {};
312
313 /* Traits for elements that point to gc memory. The elements don't
314 in themselves keep the pointed-to data alive and they can be deleted
315 if the pointed-to data is going to be collected. */
316
317 template <typename T>
318 struct ggc_cache_ptr_hash : pointer_hash <T>, ggc_cache_remove <T *> {};
319
320 /* Traits for string elements that should be freed when an element is
321 deleted. */
322
323 struct free_string_hash : string_hash, typed_const_free_remove <char> {};
324
325 /* Traits for string elements that should not be freed when an element
326 is deleted. */
327
328 struct nofree_string_hash : string_hash, typed_noop_remove <const char *> {};
329
330 /* Traits for pairs of values, using the first to record empty and
331 deleted slots. */
332
333 template <typename T1, typename T2>
334 struct pair_hash
335 {
336 typedef std::pair <typename T1::value_type,
337 typename T2::value_type> value_type;
338 typedef std::pair <typename T1::compare_type,
339 typename T2::compare_type> compare_type;
340
341 static inline hashval_t hash (const value_type &);
342 static inline bool equal (const value_type &, const compare_type &);
343 static inline void remove (value_type &);
344 static inline void mark_deleted (value_type &);
345 static const bool empty_zero_p = T1::empty_zero_p;
346 static inline void mark_empty (value_type &);
347 static inline bool is_deleted (const value_type &);
348 static inline bool is_empty (const value_type &);
349 };
350
351 template <typename T1, typename T2>
352 inline hashval_t
hash(const value_type & x)353 pair_hash <T1, T2>::hash (const value_type &x)
354 {
355 return iterative_hash_hashval_t (T1::hash (x.first), T2::hash (x.second));
356 }
357
358 template <typename T1, typename T2>
359 inline bool
equal(const value_type & x,const compare_type & y)360 pair_hash <T1, T2>::equal (const value_type &x, const compare_type &y)
361 {
362 return T1::equal (x.first, y.first) && T2::equal (x.second, y.second);
363 }
364
365 template <typename T1, typename T2>
366 inline void
remove(value_type & x)367 pair_hash <T1, T2>::remove (value_type &x)
368 {
369 T1::remove (x.first);
370 T2::remove (x.second);
371 }
372
373 template <typename T1, typename T2>
374 inline void
mark_deleted(value_type & x)375 pair_hash <T1, T2>::mark_deleted (value_type &x)
376 {
377 T1::mark_deleted (x.first);
378 }
379
380 template <typename T1, typename T2>
381 inline void
mark_empty(value_type & x)382 pair_hash <T1, T2>::mark_empty (value_type &x)
383 {
384 T1::mark_empty (x.first);
385 }
386
387 template <typename T1, typename T2>
388 inline bool
is_deleted(const value_type & x)389 pair_hash <T1, T2>::is_deleted (const value_type &x)
390 {
391 return T1::is_deleted (x.first);
392 }
393
394 template <typename T1, typename T2>
395 inline bool
is_empty(const value_type & x)396 pair_hash <T1, T2>::is_empty (const value_type &x)
397 {
398 return T1::is_empty (x.first);
399 }
400
401 template <typename T> struct default_hash_traits : T {};
402
403 template <typename T>
404 struct default_hash_traits <T *> : ggc_ptr_hash <T> {};
405
406 #endif
407