2 Copyright (C) 2015 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
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
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_MAP_TRAITS_H
21 #define HASH_MAP_TRAITS_H
23 /* Bacause mem-stats.h uses default hashmap traits, we have to
24 put the class to this separate header file. */
26 #include "hash-traits.h"
28 /* implement default behavior for traits when types allow it. */
30 struct default_hashmap_traits
32 /* Hashes the passed in key. */
38 return uintptr_t (p
) >> 3;
41 /* If the value converts to hashval_t just use it. */
43 template<typename T
> static hashval_t
hash (T v
) { return v
; }
45 /* Return true if the two keys passed as arguments are equal. */
49 equal_keys (const T
&a
, const T
&b
)
54 /* Called to dispose of the key and value before marking the entry as
57 template<typename T
> static void remove (T
&v
) { v
.~T (); }
59 /* Mark the passed in entry as being deleted. */
65 mark_key_deleted (e
.m_key
);
68 /* Mark the passed in entry as being empty. */
74 mark_key_empty (e
.m_key
);
77 /* Return true if the passed in entry is marked as deleted. */
83 return e
.m_key
== (void *)1;
86 /* Return true if the passed in entry is marked as empty. */
88 template<typename T
> static bool is_empty (T
&e
) { return e
.m_key
== NULL
; }
93 mark_key_deleted (T
*&k
)
95 k
= reinterpret_cast<T
*> (1);
100 mark_key_empty (T
*&k
)
102 k
= static_cast<T
*> (0);
106 /* Implement hash_map traits for a key with hash traits H. Empty and
107 deleted map entries are represented as empty and deleted keys. */
109 template <typename H
>
110 struct simple_hashmap_traits
112 static inline hashval_t
hash (const typename
H::value_type
&);
113 static inline bool equal_keys (const typename
H::value_type
&,
114 const typename
H::value_type
&);
115 template <typename T
> static inline void remove (T
&);
116 template <typename T
> static inline bool is_empty (const T
&);
117 template <typename T
> static inline bool is_deleted (const T
&);
118 template <typename T
> static inline void mark_empty (T
&);
119 template <typename T
> static inline void mark_deleted (T
&);
122 template <typename H
>
124 simple_hashmap_traits
<H
>::hash (const typename
H::value_type
&h
)
129 template <typename H
>
131 simple_hashmap_traits
<H
>::equal_keys (const typename
H::value_type
&k1
,
132 const typename
H::value_type
&k2
)
134 return H::equal (k1
, k2
);
137 template <typename H
>
138 template <typename T
>
140 simple_hashmap_traits
<H
>::remove (T
&entry
)
142 H::remove (entry
.m_key
);
145 template <typename H
>
146 template <typename T
>
148 simple_hashmap_traits
<H
>::is_empty (const T
&entry
)
150 return H::is_empty (entry
.m_key
);
153 template <typename H
>
154 template <typename T
>
156 simple_hashmap_traits
<H
>::is_deleted (const T
&entry
)
158 return H::is_deleted (entry
.m_key
);
161 template <typename H
>
162 template <typename T
>
164 simple_hashmap_traits
<H
>::mark_empty (T
&entry
)
166 H::mark_empty (entry
.m_key
);
169 template <typename H
>
170 template <typename T
>
172 simple_hashmap_traits
<H
>::mark_deleted (T
&entry
)
174 H::mark_deleted (entry
.m_key
);
177 /* Implement traits for a hash_map with values of type Value for cases
178 in which the key cannot represent empty and deleted slots. Instead
179 record empty and deleted entries in Value. Derived classes must
180 implement the hash and equal_keys functions. */
182 template <typename Value
>
183 struct unbounded_hashmap_traits
185 template <typename T
> static inline void remove (T
&);
186 template <typename T
> static inline bool is_empty (const T
&);
187 template <typename T
> static inline bool is_deleted (const T
&);
188 template <typename T
> static inline void mark_empty (T
&);
189 template <typename T
> static inline void mark_deleted (T
&);
192 template <typename Value
>
193 template <typename T
>
195 unbounded_hashmap_traits
<Value
>::remove (T
&entry
)
197 default_hash_traits
<Value
>::remove (entry
.m_value
);
200 template <typename Value
>
201 template <typename T
>
203 unbounded_hashmap_traits
<Value
>::is_empty (const T
&entry
)
205 return default_hash_traits
<Value
>::is_empty (entry
.m_value
);
208 template <typename Value
>
209 template <typename T
>
211 unbounded_hashmap_traits
<Value
>::is_deleted (const T
&entry
)
213 return default_hash_traits
<Value
>::is_deleted (entry
.m_value
);
216 template <typename Value
>
217 template <typename T
>
219 unbounded_hashmap_traits
<Value
>::mark_empty (T
&entry
)
221 default_hash_traits
<Value
>::mark_empty (entry
.m_value
);
224 template <typename Value
>
225 template <typename T
>
227 unbounded_hashmap_traits
<Value
>::mark_deleted (T
&entry
)
229 default_hash_traits
<Value
>::mark_deleted (entry
.m_value
);
232 /* Implement traits for a hash_map from integer type Key to Value in
233 cases where Key has no spare values for recording empty and deleted
236 template <typename Key
, typename Value
>
237 struct unbounded_int_hashmap_traits
: unbounded_hashmap_traits
<Value
>
239 static inline hashval_t
hash (Key
);
240 static inline bool equal_keys (Key
, Key
);
243 template <typename Key
, typename Value
>
245 unbounded_int_hashmap_traits
<Key
, Value
>::hash (Key k
)
250 template <typename Key
, typename Value
>
252 unbounded_int_hashmap_traits
<Key
, Value
>::equal_keys (Key k1
, Key k2
)
257 #endif // HASH_MAP_TRAITS_H