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