i386: Use const reference of struct ix86_frame to avoid copy
[official-gcc.git] / gcc / hash-traits.h
blob6058cfc1d0734319371f3afb4338831a25d8a67a
1 /* Traits for hashable types.
2 Copyright (C) 2014-2018 Free Software Foundation, Inc.
4 This file is part of GCC.
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.
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.
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/>. */
20 #ifndef hash_traits_h
21 #define hash_traits_h
23 /* Helpful type for removing with free. */
25 template <typename Type>
26 struct typed_free_remove
28 static inline void remove (Type *p);
32 /* Remove with free. */
34 template <typename Type>
35 inline void
36 typed_free_remove <Type>::remove (Type *p)
38 free (p);
41 /* Helpful type for removing with delete. */
43 template <typename Type>
44 struct typed_delete_remove
46 static inline void remove (Type *p);
50 /* Remove with delete. */
52 template <typename Type>
53 inline void
54 typed_delete_remove <Type>::remove (Type *p)
56 delete p;
59 /* Helpful type for a no-op remove. */
61 template <typename Type>
62 struct typed_noop_remove
64 static inline void remove (Type &);
68 /* Remove doing nothing. */
70 template <typename Type>
71 inline void
72 typed_noop_remove <Type>::remove (Type &)
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. */
82 template <typename Type, Type Empty, Type Deleted = Empty>
83 struct int_hash : typed_noop_remove <Type>
85 typedef Type value_type;
86 typedef Type compare_type;
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);
96 template <typename Type, Type Empty, Type Deleted>
97 inline hashval_t
98 int_hash <Type, Empty, Deleted>::hash (value_type x)
100 return x;
103 template <typename Type, Type Empty, Type Deleted>
104 inline bool
105 int_hash <Type, Empty, Deleted>::equal (value_type x, value_type y)
107 return x == y;
110 template <typename Type, Type Empty, Type Deleted>
111 inline void
112 int_hash <Type, Empty, Deleted>::mark_deleted (Type &x)
114 gcc_assert (Empty != Deleted);
115 x = Deleted;
118 template <typename Type, Type Empty, Type Deleted>
119 inline void
120 int_hash <Type, Empty, Deleted>::mark_empty (Type &x)
122 x = Empty;
125 template <typename Type, Type Empty, Type Deleted>
126 inline bool
127 int_hash <Type, Empty, Deleted>::is_deleted (Type x)
129 return Empty != Deleted && x == Deleted;
132 template <typename Type, Type Empty, Type Deleted>
133 inline bool
134 int_hash <Type, Empty, Deleted>::is_empty (Type x)
136 return x == Empty;
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). */
143 template <typename Type>
144 struct pointer_hash
146 typedef Type *value_type;
147 typedef Type *compare_type;
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 *);
158 template <typename Type>
159 inline hashval_t
160 pointer_hash <Type>::hash (const value_type &candidate)
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);
167 template <typename Type>
168 inline bool
169 pointer_hash <Type>::equal (const value_type &existing,
170 const compare_type &candidate)
172 return existing == candidate;
175 template <typename Type>
176 inline void
177 pointer_hash <Type>::mark_deleted (Type *&e)
179 e = reinterpret_cast<Type *> (1);
182 template <typename Type>
183 inline void
184 pointer_hash <Type>::mark_empty (Type *&e)
186 e = NULL;
189 template <typename Type>
190 inline bool
191 pointer_hash <Type>::is_deleted (Type *e)
193 return e == reinterpret_cast<Type *> (1);
196 template <typename Type>
197 inline bool
198 pointer_hash <Type>::is_empty (Type *e)
200 return e == NULL;
203 /* Hasher for "const char *" strings, using string rather than pointer
204 equality. */
206 struct string_hash : pointer_hash <const char>
208 static inline hashval_t hash (const char *);
209 static inline bool equal (const char *, const char *);
212 inline hashval_t
213 string_hash::hash (const char *id)
215 return htab_hash_string (id);
218 inline bool
219 string_hash::equal (const char *id1, const char *id2)
221 return strcmp (id1, id2) == 0;
224 /* Remover and marker for entries in gc memory. */
226 template<typename T>
227 struct ggc_remove
229 static void remove (T &) {}
231 static void
232 ggc_mx (T &p)
234 extern void gt_ggc_mx (T &);
235 gt_ggc_mx (p);
238 /* Overridden in ggc_cache_remove. */
239 static void
240 ggc_maybe_mx (T &p)
242 ggc_mx (p);
245 static void
246 pch_nx (T &p)
248 extern void gt_pch_nx (T &);
249 gt_pch_nx (p);
252 static void
253 pch_nx (T &p, gt_pointer_operator op, void *cookie)
255 op (&p, cookie);
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. */
262 template<typename T>
263 struct ggc_cache_remove : ggc_remove<T>
265 /* Entries are weakly held because this is for caches. */
266 static void ggc_maybe_mx (T &) {}
268 static int
269 keep_cache_entry (T &e)
271 return ggc_marked_p (e) ? -1 : 0;
275 /* Traits for pointer elements that should not be freed when an element
276 is deleted. */
278 template <typename T>
279 struct nofree_ptr_hash : pointer_hash <T>, typed_noop_remove <T *> {};
281 /* Traits for pointer elements that should be freed via free() when an
282 element is deleted. */
284 template <typename T>
285 struct free_ptr_hash : pointer_hash <T>, typed_free_remove <T> {};
287 /* Traits for pointer elements that should be freed via delete operand when an
288 element is deleted. */
290 template <typename T>
291 struct delete_ptr_hash : pointer_hash <T>, typed_delete_remove <T> {};
293 /* Traits for elements that point to gc memory. The pointed-to data
294 must be kept across collections. */
296 template <typename T>
297 struct ggc_ptr_hash : pointer_hash <T>, ggc_remove <T *> {};
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. */
303 template <typename T>
304 struct ggc_cache_ptr_hash : pointer_hash <T>, ggc_cache_remove <T *> {};
306 /* Traits for string elements that should not be freed when an element
307 is deleted. */
309 struct nofree_string_hash : string_hash, typed_noop_remove <const char *> {};
311 /* Traits for pairs of values, using the first to record empty and
312 deleted slots. */
314 template <typename T1, typename T2>
315 struct pair_hash
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;
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 &);
331 template <typename T1, typename T2>
332 inline hashval_t
333 pair_hash <T1, T2>::hash (const value_type &x)
335 return iterative_hash_hashval_t (T1::hash (x.first), T2::hash (x.second));
338 template <typename T1, typename T2>
339 inline bool
340 pair_hash <T1, T2>::equal (const value_type &x, const compare_type &y)
342 return T1::equal (x.first, y.first) && T2::equal (x.second, y.second);
345 template <typename T1, typename T2>
346 inline void
347 pair_hash <T1, T2>::remove (value_type &x)
349 T1::remove (x.first);
350 T2::remove (x.second);
353 template <typename T1, typename T2>
354 inline void
355 pair_hash <T1, T2>::mark_deleted (value_type &x)
357 T1::mark_deleted (x.first);
360 template <typename T1, typename T2>
361 inline void
362 pair_hash <T1, T2>::mark_empty (value_type &x)
364 T1::mark_empty (x.first);
367 template <typename T1, typename T2>
368 inline bool
369 pair_hash <T1, T2>::is_deleted (const value_type &x)
371 return T1::is_deleted (x.first);
374 template <typename T1, typename T2>
375 inline bool
376 pair_hash <T1, T2>::is_empty (const value_type &x)
378 return T1::is_empty (x.first);
381 template <typename T> struct default_hash_traits : T {};
383 template <typename T>
384 struct default_hash_traits <T *> : ggc_ptr_hash <T> {};
386 #endif