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
16namespace __sanitizer {
17
18namespace detail {
19
20/// Simplistic combination of 32-bit hash values into 32-bit hash values.
21static 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.
36template <typename KeyT, typename ValueT>
37struct 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
62template <typename T>
63struct 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.
75template <typename T>
76struct 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.
105template <>
106struct 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.
117template <>
118struct 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.
132template <>
133struct 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.
147template <>
148struct 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.
161template <>
162struct 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.
177template <>
178struct 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.
193template <>
194struct 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.
204template <>
205struct 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.
218template <>
219struct 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.
236template <>
237struct 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.
253template <typename T, typename U>
254struct 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(a: FirstInfo::getHashValue(PairVal.first),
271 b: 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
283