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