1 | //===- llvm/ADT/DenseMapInfo.h - Type traits for DenseMap -------*- C++ -*-===// |
2 | // |
3 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
4 | // See https://llvm.org/LICENSE.txt for license information. |
5 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
6 | // |
7 | //===----------------------------------------------------------------------===// |
8 | /// |
9 | /// \file |
10 | /// This file defines DenseMapInfo traits for DenseMap. |
11 | /// |
12 | //===----------------------------------------------------------------------===// |
13 | |
14 | #ifndef LLVM_ADT_DENSEMAPINFO_H |
15 | #define LLVM_ADT_DENSEMAPINFO_H |
16 | |
17 | #include <cassert> |
18 | #include <cstddef> |
19 | #include <cstdint> |
20 | #include <tuple> |
21 | #include <type_traits> |
22 | #include <utility> |
23 | |
24 | namespace llvm { |
25 | |
26 | namespace detail { |
27 | |
28 | /// Simplistic combination of 32-bit hash values into 32-bit hash values. |
29 | static inline unsigned combineHashValue(unsigned a, unsigned b) { |
30 | uint64_t key = (uint64_t)a << 32 | (uint64_t)b; |
31 | key += ~(key << 32); |
32 | key ^= (key >> 22); |
33 | key += ~(key << 13); |
34 | key ^= (key >> 8); |
35 | key += (key << 3); |
36 | key ^= (key >> 15); |
37 | key += ~(key << 27); |
38 | key ^= (key >> 31); |
39 | return (unsigned)key; |
40 | } |
41 | |
42 | } // end namespace detail |
43 | |
44 | /// An information struct used to provide DenseMap with the various necessary |
45 | /// components for a given value type `T`. `Enable` is an optional additional |
46 | /// parameter that is used to support SFINAE (generally using std::enable_if_t) |
47 | /// in derived DenseMapInfo specializations; in non-SFINAE use cases this should |
48 | /// just be `void`. |
49 | template<typename T, typename Enable = void> |
50 | struct DenseMapInfo { |
51 | //static inline T getEmptyKey(); |
52 | //static inline T getTombstoneKey(); |
53 | //static unsigned getHashValue(const T &Val); |
54 | //static bool isEqual(const T &LHS, const T &RHS); |
55 | }; |
56 | |
57 | // Provide DenseMapInfo for all pointers. Come up with sentinel pointer values |
58 | // that are aligned to alignof(T) bytes, but try to avoid requiring T to be |
59 | // complete. This allows clients to instantiate DenseMap<T*, ...> with forward |
60 | // declared key types. Assume that no pointer key type requires more than 4096 |
61 | // bytes of alignment. |
62 | template<typename T> |
63 | struct DenseMapInfo<T*> { |
64 | // The following should hold, but it would require T to be complete: |
65 | // static_assert(alignof(T) <= (1 << Log2MaxAlign), |
66 | // "DenseMap does not support pointer keys requiring more than " |
67 | // "Log2MaxAlign bits of alignment"); |
68 | static constexpr uintptr_t Log2MaxAlign = 12; |
69 | |
70 | static inline T* getEmptyKey() { |
71 | uintptr_t Val = static_cast<uintptr_t>(-1); |
72 | Val <<= Log2MaxAlign; |
73 | return reinterpret_cast<T*>(Val); |
74 | } |
75 | |
76 | static inline T* getTombstoneKey() { |
77 | uintptr_t Val = static_cast<uintptr_t>(-2); |
78 | Val <<= Log2MaxAlign; |
79 | return reinterpret_cast<T*>(Val); |
80 | } |
81 | |
82 | static unsigned getHashValue(const T *PtrVal) { |
83 | return (unsigned((uintptr_t)PtrVal) >> 4) ^ |
84 | (unsigned((uintptr_t)PtrVal) >> 9); |
85 | } |
86 | |
87 | static bool isEqual(const T *LHS, const T *RHS) { return LHS == RHS; } |
88 | }; |
89 | |
90 | // Provide DenseMapInfo for chars. |
91 | template<> struct DenseMapInfo<char> { |
92 | static inline char getEmptyKey() { return ~0; } |
93 | static inline char getTombstoneKey() { return ~0 - 1; } |
94 | static unsigned getHashValue(const char& Val) { return Val * 37U; } |
95 | |
96 | static bool isEqual(const char &LHS, const char &RHS) { |
97 | return LHS == RHS; |
98 | } |
99 | }; |
100 | |
101 | // Provide DenseMapInfo for unsigned chars. |
102 | template <> struct DenseMapInfo<unsigned char> { |
103 | static inline unsigned char getEmptyKey() { return ~0; } |
104 | static inline unsigned char getTombstoneKey() { return ~0 - 1; } |
105 | static unsigned getHashValue(const unsigned char &Val) { return Val * 37U; } |
106 | |
107 | static bool isEqual(const unsigned char &LHS, const unsigned char &RHS) { |
108 | return LHS == RHS; |
109 | } |
110 | }; |
111 | |
112 | // Provide DenseMapInfo for unsigned shorts. |
113 | template <> struct DenseMapInfo<unsigned short> { |
114 | static inline unsigned short getEmptyKey() { return 0xFFFF; } |
115 | static inline unsigned short getTombstoneKey() { return 0xFFFF - 1; } |
116 | static unsigned getHashValue(const unsigned short &Val) { return Val * 37U; } |
117 | |
118 | static bool isEqual(const unsigned short &LHS, const unsigned short &RHS) { |
119 | return LHS == RHS; |
120 | } |
121 | }; |
122 | |
123 | // Provide DenseMapInfo for unsigned ints. |
124 | template<> struct DenseMapInfo<unsigned> { |
125 | static inline unsigned getEmptyKey() { return ~0U; } |
126 | static inline unsigned getTombstoneKey() { return ~0U - 1; } |
127 | static unsigned getHashValue(const unsigned& Val) { return Val * 37U; } |
128 | |
129 | static bool isEqual(const unsigned& LHS, const unsigned& RHS) { |
130 | return LHS == RHS; |
131 | } |
132 | }; |
133 | |
134 | // Provide DenseMapInfo for unsigned longs. |
135 | template<> struct DenseMapInfo<unsigned long> { |
136 | static inline unsigned long getEmptyKey() { return ~0UL; } |
137 | static inline unsigned long getTombstoneKey() { return ~0UL - 1L; } |
138 | |
139 | static unsigned getHashValue(const unsigned long& Val) { |
140 | return (unsigned)(Val * 37UL); |
141 | } |
142 | |
143 | static bool isEqual(const unsigned long& LHS, const unsigned long& RHS) { |
144 | return LHS == RHS; |
145 | } |
146 | }; |
147 | |
148 | // Provide DenseMapInfo for unsigned long longs. |
149 | template<> struct DenseMapInfo<unsigned long long> { |
150 | static inline unsigned long long getEmptyKey() { return ~0ULL; } |
151 | static inline unsigned long long getTombstoneKey() { return ~0ULL - 1ULL; } |
152 | |
153 | static unsigned getHashValue(const unsigned long long& Val) { |
154 | return (unsigned)(Val * 37ULL); |
155 | } |
156 | |
157 | static bool isEqual(const unsigned long long& LHS, |
158 | const unsigned long long& RHS) { |
159 | return LHS == RHS; |
160 | } |
161 | }; |
162 | |
163 | // Provide DenseMapInfo for shorts. |
164 | template <> struct DenseMapInfo<short> { |
165 | static inline short getEmptyKey() { return 0x7FFF; } |
166 | static inline short getTombstoneKey() { return -0x7FFF - 1; } |
167 | static unsigned getHashValue(const short &Val) { return Val * 37U; } |
168 | static bool isEqual(const short &LHS, const short &RHS) { return LHS == RHS; } |
169 | }; |
170 | |
171 | // Provide DenseMapInfo for ints. |
172 | template<> struct DenseMapInfo<int> { |
173 | static inline int getEmptyKey() { return 0x7fffffff; } |
174 | static inline int getTombstoneKey() { return -0x7fffffff - 1; } |
175 | static unsigned getHashValue(const int& Val) { return (unsigned)(Val * 37U); } |
176 | |
177 | static bool isEqual(const int& LHS, const int& RHS) { |
178 | return LHS == RHS; |
179 | } |
180 | }; |
181 | |
182 | // Provide DenseMapInfo for longs. |
183 | template<> struct DenseMapInfo<long> { |
184 | static inline long getEmptyKey() { |
185 | return (1UL << (sizeof(long) * 8 - 1)) - 1UL; |
186 | } |
187 | |
188 | static inline long getTombstoneKey() { return getEmptyKey() - 1L; } |
189 | |
190 | static unsigned getHashValue(const long& Val) { |
191 | return (unsigned)(Val * 37UL); |
192 | } |
193 | |
194 | static bool isEqual(const long& LHS, const long& RHS) { |
195 | return LHS == RHS; |
196 | } |
197 | }; |
198 | |
199 | // Provide DenseMapInfo for long longs. |
200 | template<> struct DenseMapInfo<long long> { |
201 | static inline long long getEmptyKey() { return 0x7fffffffffffffffLL; } |
202 | static inline long long getTombstoneKey() { return -0x7fffffffffffffffLL-1; } |
203 | |
204 | static unsigned getHashValue(const long long& Val) { |
205 | return (unsigned)(Val * 37ULL); |
206 | } |
207 | |
208 | static bool isEqual(const long long& LHS, |
209 | const long long& RHS) { |
210 | return LHS == RHS; |
211 | } |
212 | }; |
213 | |
214 | // Provide DenseMapInfo for all pairs whose members have info. |
215 | template<typename T, typename U> |
216 | struct DenseMapInfo<std::pair<T, U>> { |
217 | using Pair = std::pair<T, U>; |
218 | using FirstInfo = DenseMapInfo<T>; |
219 | using SecondInfo = DenseMapInfo<U>; |
220 | |
221 | static inline Pair getEmptyKey() { |
222 | return std::make_pair(FirstInfo::getEmptyKey(), |
223 | SecondInfo::getEmptyKey()); |
224 | } |
225 | |
226 | static inline Pair getTombstoneKey() { |
227 | return std::make_pair(FirstInfo::getTombstoneKey(), |
228 | SecondInfo::getTombstoneKey()); |
229 | } |
230 | |
231 | static unsigned getHashValue(const Pair& PairVal) { |
232 | return detail::combineHashValue(a: FirstInfo::getHashValue(PairVal.first), |
233 | b: SecondInfo::getHashValue(PairVal.second)); |
234 | } |
235 | |
236 | // Expose an additional function intended to be used by other |
237 | // specializations of DenseMapInfo without needing to know how |
238 | // to combine hash values manually |
239 | static unsigned getHashValuePiecewise(const T &First, const U &Second) { |
240 | return detail::combineHashValue(a: FirstInfo::getHashValue(First), |
241 | b: SecondInfo::getHashValue(Second)); |
242 | } |
243 | |
244 | static bool isEqual(const Pair &LHS, const Pair &RHS) { |
245 | return FirstInfo::isEqual(LHS.first, RHS.first) && |
246 | SecondInfo::isEqual(LHS.second, RHS.second); |
247 | } |
248 | }; |
249 | |
250 | // Provide DenseMapInfo for all tuples whose members have info. |
251 | template <typename... Ts> struct DenseMapInfo<std::tuple<Ts...>> { |
252 | using Tuple = std::tuple<Ts...>; |
253 | |
254 | static inline Tuple getEmptyKey() { |
255 | return Tuple(DenseMapInfo<Ts>::getEmptyKey()...); |
256 | } |
257 | |
258 | static inline Tuple getTombstoneKey() { |
259 | return Tuple(DenseMapInfo<Ts>::getTombstoneKey()...); |
260 | } |
261 | |
262 | template <unsigned I> |
263 | static unsigned getHashValueImpl(const Tuple &values, std::false_type) { |
264 | using EltType = std::tuple_element_t<I, Tuple>; |
265 | std::integral_constant<bool, I + 1 == sizeof...(Ts)> atEnd; |
266 | return detail::combineHashValue( |
267 | a: DenseMapInfo<EltType>::getHashValue(std::get<I>(values)), |
268 | b: getHashValueImpl<I + 1>(values, atEnd)); |
269 | } |
270 | |
271 | template <unsigned I> |
272 | static unsigned getHashValueImpl(const Tuple &, std::true_type) { |
273 | return 0; |
274 | } |
275 | |
276 | static unsigned getHashValue(const std::tuple<Ts...> &values) { |
277 | std::integral_constant<bool, 0 == sizeof...(Ts)> atEnd; |
278 | return getHashValueImpl<0>(values, atEnd); |
279 | } |
280 | |
281 | template <unsigned I> |
282 | static bool isEqualImpl(const Tuple &lhs, const Tuple &rhs, std::false_type) { |
283 | using EltType = std::tuple_element_t<I, Tuple>; |
284 | std::integral_constant<bool, I + 1 == sizeof...(Ts)> atEnd; |
285 | return DenseMapInfo<EltType>::isEqual(std::get<I>(lhs), std::get<I>(rhs)) && |
286 | isEqualImpl<I + 1>(lhs, rhs, atEnd); |
287 | } |
288 | |
289 | template <unsigned I> |
290 | static bool isEqualImpl(const Tuple &, const Tuple &, std::true_type) { |
291 | return true; |
292 | } |
293 | |
294 | static bool isEqual(const Tuple &lhs, const Tuple &rhs) { |
295 | std::integral_constant<bool, 0 == sizeof...(Ts)> atEnd; |
296 | return isEqualImpl<0>(lhs, rhs, atEnd); |
297 | } |
298 | }; |
299 | |
300 | } // end namespace llvm |
301 | |
302 | #endif // LLVM_ADT_DENSEMAPINFO_H |
303 | |