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 unsigned getHashValue(const T &Val);
66 // static bool isEqual(const T &LHS, const T &RHS);
67};
68
69// Provide DenseMapInfo for all pointers. Come up with sentinel pointer values
70// that are aligned to alignof(T) bytes, but try to avoid requiring T to be
71// complete. This allows clients to instantiate DenseMap<T*, ...> with forward
72// declared key types. Assume that no pointer key type requires more than 4096
73// bytes of alignment.
74template <typename T>
75struct DenseMapInfo<T *> {
76 // The following should hold, but it would require T to be complete:
77 // static_assert(alignof(T) <= (1 << Log2MaxAlign),
78 // "DenseMap does not support pointer keys requiring more than "
79 // "Log2MaxAlign bits of alignment");
80 static constexpr uptr Log2MaxAlign = 12;
81
82 static constexpr T *getEmptyKey() {
83 uptr Val = static_cast<uptr>(-1);
84 Val <<= Log2MaxAlign;
85 return reinterpret_cast<T *>(Val);
86 }
87
88 static constexpr unsigned getHashValue(const T *PtrVal) {
89 return (unsigned((uptr)PtrVal) >> 4) ^ (unsigned((uptr)PtrVal) >> 9);
90 }
91
92 static constexpr bool isEqual(const T *LHS, const T *RHS) {
93 return LHS == RHS;
94 }
95};
96
97// Provide DenseMapInfo for chars.
98template <>
99struct DenseMapInfo<char> {
100 static constexpr char getEmptyKey() { return ~0; }
101 static constexpr unsigned getHashValue(const char &Val) { return Val * 37U; }
102
103 static constexpr bool isEqual(const char &LHS, const char &RHS) {
104 return LHS == RHS;
105 }
106};
107
108// Provide DenseMapInfo for unsigned chars.
109template <>
110struct DenseMapInfo<unsigned char> {
111 static constexpr unsigned char getEmptyKey() { return ~0; }
112 static constexpr unsigned getHashValue(const unsigned char &Val) {
113 return Val * 37U;
114 }
115
116 static constexpr bool isEqual(const unsigned char &LHS,
117 const unsigned char &RHS) {
118 return LHS == RHS;
119 }
120};
121
122// Provide DenseMapInfo for unsigned shorts.
123template <>
124struct DenseMapInfo<unsigned short> {
125 static constexpr unsigned short getEmptyKey() { return 0xFFFF; }
126 static constexpr unsigned getHashValue(const unsigned short &Val) {
127 return Val * 37U;
128 }
129
130 static constexpr bool isEqual(const unsigned short &LHS,
131 const unsigned short &RHS) {
132 return LHS == RHS;
133 }
134};
135
136// Provide DenseMapInfo for unsigned ints.
137template <>
138struct DenseMapInfo<unsigned> {
139 static constexpr unsigned getEmptyKey() { return ~0U; }
140 static constexpr unsigned getHashValue(const unsigned &Val) {
141 return Val * 37U;
142 }
143
144 static constexpr bool isEqual(const unsigned &LHS, const unsigned &RHS) {
145 return LHS == RHS;
146 }
147};
148
149// Provide DenseMapInfo for unsigned longs.
150template <>
151struct DenseMapInfo<unsigned long> {
152 static constexpr unsigned long getEmptyKey() { return ~0UL; }
153
154 static constexpr unsigned getHashValue(const unsigned long &Val) {
155 return (unsigned)(Val * 37UL);
156 }
157
158 static constexpr bool isEqual(const unsigned long &LHS,
159 const unsigned long &RHS) {
160 return LHS == RHS;
161 }
162};
163
164// Provide DenseMapInfo for unsigned long longs.
165template <>
166struct DenseMapInfo<unsigned long long> {
167 static constexpr unsigned long long getEmptyKey() { return ~0ULL; }
168
169 static constexpr unsigned getHashValue(const unsigned long long &Val) {
170 return (unsigned)(Val * 37ULL);
171 }
172
173 static constexpr bool isEqual(const unsigned long long &LHS,
174 const unsigned long long &RHS) {
175 return LHS == RHS;
176 }
177};
178
179// Provide DenseMapInfo for shorts.
180template <>
181struct DenseMapInfo<short> {
182 static constexpr short getEmptyKey() { return 0x7FFF; }
183 static constexpr unsigned getHashValue(const short &Val) { return Val * 37U; }
184 static constexpr bool isEqual(const short &LHS, const short &RHS) {
185 return LHS == RHS;
186 }
187};
188
189// Provide DenseMapInfo for ints.
190template <>
191struct DenseMapInfo<int> {
192 static constexpr int getEmptyKey() { return 0x7fffffff; }
193 static constexpr unsigned getHashValue(const int &Val) {
194 return (unsigned)(Val * 37U);
195 }
196
197 static constexpr bool isEqual(const int &LHS, const int &RHS) {
198 return LHS == RHS;
199 }
200};
201
202// Provide DenseMapInfo for longs.
203template <>
204struct DenseMapInfo<long> {
205 static constexpr long getEmptyKey() {
206 return (1UL << (sizeof(long) * 8 - 1)) - 1UL;
207 }
208
209 static constexpr unsigned getHashValue(const long &Val) {
210 return (unsigned)(Val * 37UL);
211 }
212
213 static constexpr bool isEqual(const long &LHS, const long &RHS) {
214 return LHS == RHS;
215 }
216};
217
218// Provide DenseMapInfo for long longs.
219template <>
220struct DenseMapInfo<long long> {
221 static constexpr long long getEmptyKey() { return 0x7fffffffffffffffLL; }
222
223 static constexpr unsigned getHashValue(const long long &Val) {
224 return (unsigned)(Val * 37ULL);
225 }
226
227 static constexpr bool isEqual(const long long &LHS, const long long &RHS) {
228 return LHS == RHS;
229 }
230};
231
232// Provide DenseMapInfo for all pairs whose members have info.
233template <typename T, typename U>
234struct DenseMapInfo<detail::DenseMapPair<T, U>> {
235 using Pair = detail::DenseMapPair<T, U>;
236 using FirstInfo = DenseMapInfo<T>;
237 using SecondInfo = DenseMapInfo<U>;
238
239 static constexpr Pair getEmptyKey() {
240 return detail::DenseMapPair<T, U>(FirstInfo::getEmptyKey(),
241 SecondInfo::getEmptyKey());
242 }
243
244 static constexpr unsigned getHashValue(const Pair &PairVal) {
245 return detail::combineHashValue(a: FirstInfo::getHashValue(PairVal.first),
246 b: SecondInfo::getHashValue(PairVal.second));
247 }
248
249 static constexpr bool isEqual(const Pair &LHS, const Pair &RHS) {
250 return FirstInfo::isEqual(LHS.first, RHS.first) &&
251 SecondInfo::isEqual(LHS.second, RHS.second);
252 }
253};
254
255} // namespace __sanitizer
256
257#endif // SANITIZER_DENSE_MAP_INFO_H
258