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