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