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