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
283