1 /* Traits for hashable types.
2 Copyright (C) 2014-2016 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 inline void mark_empty (Type &);
92 static inline bool is_deleted (Type);
93 static inline bool is_empty (Type);
94 };
95
96 template <typename Type, Type Empty, Type Deleted>
97 inline hashval_t
hash(value_type x)98 int_hash <Type, Empty, Deleted>::hash (value_type x)
99 {
100 return x;
101 }
102
103 template <typename Type, Type Empty, Type Deleted>
104 inline bool
equal(value_type x,value_type y)105 int_hash <Type, Empty, Deleted>::equal (value_type x, value_type y)
106 {
107 return x == y;
108 }
109
110 template <typename Type, Type Empty, Type Deleted>
111 inline void
mark_deleted(Type & x)112 int_hash <Type, Empty, Deleted>::mark_deleted (Type &x)
113 {
114 gcc_assert (Empty != Deleted);
115 x = Deleted;
116 }
117
118 template <typename Type, Type Empty, Type Deleted>
119 inline void
mark_empty(Type & x)120 int_hash <Type, Empty, Deleted>::mark_empty (Type &x)
121 {
122 x = Empty;
123 }
124
125 template <typename Type, Type Empty, Type Deleted>
126 inline bool
is_deleted(Type x)127 int_hash <Type, Empty, Deleted>::is_deleted (Type x)
128 {
129 return Empty != Deleted && x == Deleted;
130 }
131
132 template <typename Type, Type Empty, Type Deleted>
133 inline bool
is_empty(Type x)134 int_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
143 template <typename Type>
144 struct 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
158 template <typename Type>
159 inline hashval_t
hash(const value_type & candidate)160 pointer_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
167 template <typename Type>
168 inline bool
equal(const value_type & existing,const compare_type & candidate)169 pointer_hash <Type>::equal (const value_type &existing,
170 const compare_type &candidate)
171 {
172 return existing == candidate;
173 }
174
175 template <typename Type>
176 inline void
mark_deleted(Type * & e)177 pointer_hash <Type>::mark_deleted (Type *&e)
178 {
179 e = reinterpret_cast<Type *> (1);
180 }
181
182 template <typename Type>
183 inline void
mark_empty(Type * & e)184 pointer_hash <Type>::mark_empty (Type *&e)
185 {
186 e = NULL;
187 }
188
189 template <typename Type>
190 inline bool
is_deleted(Type * e)191 pointer_hash <Type>::is_deleted (Type *e)
192 {
193 return e == reinterpret_cast<Type *> (1);
194 }
195
196 template <typename Type>
197 inline bool
is_empty(Type * e)198 pointer_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
206 struct 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
212 inline hashval_t
hash(const char * id)213 string_hash::hash (const char *id)
214 {
215 return htab_hash_string (id);
216 }
217
218 inline bool
equal(const char * id1,const char * id2)219 string_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
226 template<typename T>
227 struct ggc_remove
228 {
removeggc_remove229 static void remove (T &) {}
230
231 static void
ggc_mxggc_remove232 ggc_mx (T &p)
233 {
234 extern void gt_ggc_mx (T &);
235 gt_ggc_mx (p);
236 }
237
238 static void
pch_nxggc_remove239 pch_nx (T &p)
240 {
241 extern void gt_pch_nx (T &);
242 gt_pch_nx (p);
243 }
244
245 static void
pch_nxggc_remove246 pch_nx (T &p, gt_pointer_operator op, void *cookie)
247 {
248 op (&p, cookie);
249 }
250 };
251
252 /* Remover and marker for "cache" entries in gc memory. These entries can
253 be deleted if there are no non-cache references to the data. */
254
255 template<typename T>
256 struct ggc_cache_remove : ggc_remove<T>
257 {
258 /* Entries are weakly held because this is for caches. */
ggc_mxggc_cache_remove259 static void ggc_mx (T &) {}
260
261 static int
keep_cache_entryggc_cache_remove262 keep_cache_entry (T &e)
263 {
264 return ggc_marked_p (e) ? -1 : 0;
265 }
266 };
267
268 /* Traits for pointer elements that should not be freed when an element
269 is deleted. */
270
271 template <typename T>
272 struct nofree_ptr_hash : pointer_hash <T>, typed_noop_remove <T *> {};
273
274 /* Traits for pointer elements that should be freed via free() when an
275 element is deleted. */
276
277 template <typename T>
278 struct free_ptr_hash : pointer_hash <T>, typed_free_remove <T> {};
279
280 /* Traits for pointer elements that should be freed via delete operand when an
281 element is deleted. */
282
283 template <typename T>
284 struct delete_ptr_hash : pointer_hash <T>, typed_delete_remove <T> {};
285
286 /* Traits for elements that point to gc memory. The pointed-to data
287 must be kept across collections. */
288
289 template <typename T>
290 struct ggc_ptr_hash : pointer_hash <T>, ggc_remove <T *> {};
291
292 /* Traits for elements that point to gc memory. The elements don't
293 in themselves keep the pointed-to data alive and they can be deleted
294 if the pointed-to data is going to be collected. */
295
296 template <typename T>
297 struct ggc_cache_ptr_hash : pointer_hash <T>, ggc_cache_remove <T *> {};
298
299 /* Traits for string elements that should not be freed when an element
300 is deleted. */
301
302 struct nofree_string_hash : string_hash, typed_noop_remove <const char *> {};
303
304 template <typename T> struct default_hash_traits : T {};
305
306 template <typename T>
307 struct default_hash_traits <T *> : ggc_ptr_hash <T> {};
308
309 #endif
310