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