1 //===- sanitizer_dense_map_info.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 #ifndef SANITIZER_DENSE_MAP_INFO_H
10 #define SANITIZER_DENSE_MAP_INFO_H
11
12 #include "sanitizer_common.h"
13 #include "sanitizer_internal_defs.h"
14 #include "sanitizer_type_traits.h"
15
16 namespace __sanitizer {
17
18 namespace detail {
19
20 /// Simplistic combination of 32-bit hash values into 32-bit hash values.
21 static constexpr unsigned combineHashValue(unsigned a, unsigned b) {
22 u64 key = (u64)a << 32 | (u64)b;
23 key += ~(key << 32);
24 key ^= (key >> 22);
25 key += ~(key << 13);
26 key ^= (key >> 8);
27 key += (key << 3);
28 key ^= (key >> 15);
29 key += ~(key << 27);
30 key ^= (key >> 31);
31 return (unsigned)key;
32 }
33
34 // We extend a pair to allow users to override the bucket type with their own
35 // implementation without requiring two members.
36 template <typename KeyT, typename ValueT>
37 struct DenseMapPair {
38 KeyT first = {};
39 ValueT second = {};
40 constexpr DenseMapPair() = default;
41 constexpr DenseMapPair(const KeyT &f, const ValueT &s)
42 : first(f), second(s) {}
43
44 template <typename KeyT2, typename ValueT2>
45 constexpr DenseMapPair(KeyT2 &&f, ValueT2 &&s)
46 : first(__sanitizer::forward<KeyT2>(f)),
47 second(__sanitizer::forward<ValueT2>(s)) {}
48
49 constexpr DenseMapPair(const DenseMapPair &other) = default;
50 constexpr DenseMapPair &operator=(const DenseMapPair &other) = default;
51 constexpr DenseMapPair(DenseMapPair &&other) = default;
52 constexpr DenseMapPair &operator=(DenseMapPair &&other) = default;
53
54 KeyT &getFirst() { return first; }
55 const KeyT &getFirst() const { return first; }
56 ValueT &getSecond() { return second; }
57 const ValueT &getSecond() const { return second; }
58 };
59
60 } // end namespace detail
61
62 template <typename T>
63 struct DenseMapInfo {
64 // static T getEmptyKey();
65 // static T getTombstoneKey();
66 // static unsigned getHashValue(const T &Val);
67 // static bool isEqual(const T &LHS, const T &RHS);
68 };
69
70 // Provide DenseMapInfo for all pointers. Come up with sentinel pointer values
71 // that are aligned to alignof(T) bytes, but try to avoid requiring T to be
72 // complete. This allows clients to instantiate DenseMap<T*, ...> with forward
73 // declared key types. Assume that no pointer key type requires more than 4096
74 // bytes of alignment.
75 template <typename T>
76 struct DenseMapInfo<T *> {
77 // The following should hold, but it would require T to be complete:
78 // static_assert(alignof(T) <= (1 << Log2MaxAlign),
79 // "DenseMap does not support pointer keys requiring more than "
80 // "Log2MaxAlign bits of alignment");
81 static constexpr uptr Log2MaxAlign = 12;
82
83 static constexpr T *getEmptyKey() {
84 uptr Val = static_cast<uptr>(-1);
85 Val <<= Log2MaxAlign;
86 return reinterpret_cast<T *>(Val);
87 }
88
89 static constexpr T *getTombstoneKey() {
90 uptr Val = static_cast<uptr>(-2);
91 Val <<= Log2MaxAlign;
92 return reinterpret_cast<T *>(Val);
93 }
94
95 static constexpr unsigned getHashValue(const T *PtrVal) {
96 return (unsigned((uptr)PtrVal) >> 4) ^ (unsigned((uptr)PtrVal) >> 9);
97 }
98
99 static constexpr bool isEqual(const T *LHS, const T *RHS) {
100 return LHS == RHS;
101 }
102 };
103
104 // Provide DenseMapInfo for chars.
105 template <>
106 struct DenseMapInfo<char> {
107 static constexpr char getEmptyKey() { return ~0; }
108 static constexpr char getTombstoneKey() { return ~0 - 1; }
109 static constexpr unsigned getHashValue(const char &Val) { return Val * 37U; }
110
111 static constexpr bool isEqual(const char &LHS, const char &RHS) {
112 return LHS == RHS;
113 }
114 };
115
116 // Provide DenseMapInfo for unsigned chars.
117 template <>
118 struct DenseMapInfo<unsigned char> {
119 static constexpr unsigned char getEmptyKey() { return ~0; }
120 static constexpr unsigned char getTombstoneKey() { return ~0 - 1; }
121 static constexpr unsigned getHashValue(const unsigned char &Val) {
122 return Val * 37U;
123 }
124
125 static constexpr bool isEqual(const unsigned char &LHS,
126 const unsigned char &RHS) {
127 return LHS == RHS;
128 }
129 };
130
131 // Provide DenseMapInfo for unsigned shorts.
132 template <>
133 struct DenseMapInfo<unsigned short> {
134 static constexpr unsigned short getEmptyKey() { return 0xFFFF; }
135 static constexpr unsigned short getTombstoneKey() { return 0xFFFF - 1; }
136 static constexpr unsigned getHashValue(const unsigned short &Val) {
137 return Val * 37U;
138 }
139
140 static constexpr bool isEqual(const unsigned short &LHS,
141 const unsigned short &RHS) {
142 return LHS == RHS;
143 }
144 };
145
146 // Provide DenseMapInfo for unsigned ints.
147 template <>
148 struct DenseMapInfo<unsigned> {
149 static constexpr unsigned getEmptyKey() { return ~0U; }
150 static constexpr unsigned getTombstoneKey() { return ~0U - 1; }
151 static constexpr unsigned getHashValue(const unsigned &Val) {
152 return Val * 37U;
153 }
154
155 static constexpr bool isEqual(const unsigned &LHS, const unsigned &RHS) {
156 return LHS == RHS;
157 }
158 };
159
160 // Provide DenseMapInfo for unsigned longs.
161 template <>
162 struct DenseMapInfo<unsigned long> {
163 static constexpr unsigned long getEmptyKey() { return ~0UL; }
164 static constexpr unsigned long getTombstoneKey() { return ~0UL - 1L; }
165
166 static constexpr unsigned getHashValue(const unsigned long &Val) {
167 return (unsigned)(Val * 37UL);
168 }
169
170 static constexpr bool isEqual(const unsigned long &LHS,
171 const unsigned long &RHS) {
172 return LHS == RHS;
173 }
174 };
175
176 // Provide DenseMapInfo for unsigned long longs.
177 template <>
178 struct DenseMapInfo<unsigned long long> {
179 static constexpr unsigned long long getEmptyKey() { return ~0ULL; }
180 static constexpr unsigned long long getTombstoneKey() { return ~0ULL - 1ULL; }
181
182 static constexpr unsigned getHashValue(const unsigned long long &Val) {
183 return (unsigned)(Val * 37ULL);
184 }
185
186 static constexpr bool isEqual(const unsigned long long &LHS,
187 const unsigned long long &RHS) {
188 return LHS == RHS;
189 }
190 };
191
192 // Provide DenseMapInfo for shorts.
193 template <>
194 struct DenseMapInfo<short> {
195 static constexpr short getEmptyKey() { return 0x7FFF; }
196 static constexpr short getTombstoneKey() { return -0x7FFF - 1; }
197 static constexpr unsigned getHashValue(const short &Val) { return Val * 37U; }
198 static constexpr bool isEqual(const short &LHS, const short &RHS) {
199 return LHS == RHS;
200 }
201 };
202
203 // Provide DenseMapInfo for ints.
204 template <>
205 struct DenseMapInfo<int> {
206 static constexpr int getEmptyKey() { return 0x7fffffff; }
207 static constexpr int getTombstoneKey() { return -0x7fffffff - 1; }
208 static constexpr unsigned getHashValue(const int &Val) {
209 return (unsigned)(Val * 37U);
210 }
211
212 static constexpr bool isEqual(const int &LHS, const int &RHS) {
213 return LHS == RHS;
214 }
215 };
216
217 // Provide DenseMapInfo for longs.
218 template <>
219 struct DenseMapInfo<long> {
220 static constexpr long getEmptyKey() {
221 return (1UL << (sizeof(long) * 8 - 1)) - 1UL;
222 }
223
224 static constexpr long getTombstoneKey() { return getEmptyKey() - 1L; }
225
226 static constexpr unsigned getHashValue(const long &Val) {
227 return (unsigned)(Val * 37UL);
228 }
229
230 static constexpr bool isEqual(const long &LHS, const long &RHS) {
231 return LHS == RHS;
232 }
233 };
234
235 // Provide DenseMapInfo for long longs.
236 template <>
237 struct DenseMapInfo<long long> {
238 static constexpr long long getEmptyKey() { return 0x7fffffffffffffffLL; }
239 static constexpr long long getTombstoneKey() {
240 return -0x7fffffffffffffffLL - 1;
241 }
242
243 static constexpr unsigned getHashValue(const long long &Val) {
244 return (unsigned)(Val * 37ULL);
245 }
246
247 static constexpr bool isEqual(const long long &LHS, const long long &RHS) {
248 return LHS == RHS;
249 }
250 };
251
252 // Provide DenseMapInfo for all pairs whose members have info.
253 template <typename T, typename U>
254 struct DenseMapInfo<detail::DenseMapPair<T, U>> {
255 using Pair = detail::DenseMapPair<T, U>;
256 using FirstInfo = DenseMapInfo<T>;
257 using SecondInfo = DenseMapInfo<U>;
258
259 static constexpr Pair getEmptyKey() {
260 return detail::DenseMapPair<T, U>(FirstInfo::getEmptyKey(),
261 SecondInfo::getEmptyKey());
262 }
263
264 static constexpr Pair getTombstoneKey() {
265 return detail::DenseMapPair<T, U>(FirstInfo::getTombstoneKey(),
266 SecondInfo::getTombstoneKey());
267 }
268
269 static constexpr unsigned getHashValue(const Pair &PairVal) {
270 return detail::combineHashValue(FirstInfo::getHashValue(PairVal.first),
271 SecondInfo::getHashValue(PairVal.second));
272 }
273
274 static constexpr bool isEqual(const Pair &LHS, const Pair &RHS) {
275 return FirstInfo::isEqual(LHS.first, RHS.first) &&
276 SecondInfo::isEqual(LHS.second, RHS.second);
277 }
278 };
279
280 } // namespace __sanitizer
281
282 #endif // SANITIZER_DENSE_MAP_INFO_H