]>
Commit | Line | Data |
---|---|---|
1 | /* Traits for hashable types. | |
2 | Copyright (C) 2014-2020 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 | |
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 | |
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 | |
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 | |
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 | |
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 | |
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 | |
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 | |
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 | |
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 | |
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 | |
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 | |
179 | pointer_hash <Type>::mark_deleted (Type *&e) | |
180 | { | |
181 | e = reinterpret_cast<Type *> (1); | |
182 | } | |
183 | ||
184 | template <typename Type> | |
185 | inline void | |
186 | pointer_hash <Type>::mark_empty (Type *&e) | |
187 | { | |
188 | e = NULL; | |
189 | } | |
190 | ||
191 | template <typename Type> | |
192 | inline bool | |
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 | |
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 | |
215 | string_hash::hash (const char *id) | |
216 | { | |
217 | return htab_hash_string (id); | |
218 | } | |
219 | ||
220 | inline bool | |
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 | { | |
231 | static void remove (T &) {} | |
232 | ||
233 | static void | |
234 | 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 | |
242 | ggc_maybe_mx (T &p) | |
243 | { | |
244 | ggc_mx (p); | |
245 | } | |
246 | ||
247 | static void | |
248 | pch_nx (T &p) | |
249 | { | |
250 | extern void gt_pch_nx (T &); | |
251 | gt_pch_nx (p); | |
252 | } | |
253 | ||
254 | static void | |
255 | 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. */ | |
268 | static void ggc_maybe_mx (T &) {} | |
269 | ||
270 | static int | |
271 | 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 | |
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 | |
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 | |
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 | |
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 | |
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 | |
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 | |
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 |