LLVM  10.0.0svn
DenseMapInfo.h
Go to the documentation of this file.
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"
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>;
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
static bool isEqual(const char &LHS, const char &RHS)
Definition: DenseMapInfo.h:65
static unsigned char getTombstoneKey()
Definition: DenseMapInfo.h:73
This class represents lattice values for constants.
Definition: AllocatorList.h:23
static unsigned getHashValue(const unsigned long &Val)
Definition: DenseMapInfo.h:108
static unsigned long getEmptyKey()
Definition: DenseMapInfo.h:105
static unsigned getHashValue(const unsigned long long &Val)
Definition: DenseMapInfo.h:122
static bool isEqual(const T *LHS, const T *RHS)
Definition: DenseMapInfo.h:56
static bool isEqual(StringRef LHS, StringRef RHS)
Definition: DenseMapInfo.h:239
static ArrayRef< T > getEmptyKey()
Definition: DenseMapInfo.h:250
static unsigned getHashValue(const long &Val)
Definition: DenseMapInfo.h:159
static unsigned getEmptyKey()
Definition: DenseMapInfo.h:94
unsigned Min
Definition: TypeSize.h:25
static unsigned getHashValue(const unsigned short &Val)
Definition: DenseMapInfo.h:85
static unsigned getHashValue(const long long &Val)
Definition: DenseMapInfo.h:173
static bool isEqual(const unsigned long long &LHS, const unsigned long long &RHS)
Definition: DenseMapInfo.h:126
static bool isEqual(const long long &LHS, const long long &RHS)
Definition: DenseMapInfo.h:177
static bool isEqual(const int &LHS, const int &RHS)
Definition: DenseMapInfo.h:146
static bool isEqual(const Pair &LHS, const Pair &RHS)
Definition: DenseMapInfo.h:214
static ElementCount getTombstoneKey()
Definition: DenseMapInfo.h:285
static unsigned getHashValue(StringRef Val)
Definition: DenseMapInfo.h:232
Definition: BitVector.h:937
static unsigned long long getEmptyKey()
Definition: DenseMapInfo.h:119
static unsigned getHashValue(const short &Val)
Definition: DenseMapInfo.h:136
static bool isEqual(const Function &Caller, const Function &Callee)
static unsigned getHashValue(const ElementCount &EltCnt)
Definition: DenseMapInfo.h:286
static bool isEqual(hash_code LHS, hash_code RHS)
Definition: DenseMapInfo.h:280
static long long getEmptyKey()
Definition: DenseMapInfo.h:170
static bool isEqual(const unsigned &LHS, const unsigned &RHS)
Definition: DenseMapInfo.h:98
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:32
hash_code hash_value(const APFloat &Arg)
See friend declarations above.
Definition: APFloat.cpp:4470
static short getTombstoneKey()
Definition: DenseMapInfo.h:135
static unsigned long getTombstoneKey()
Definition: DenseMapInfo.h:106
static unsigned getHashValue(ArrayRef< T > Val)
Definition: DenseMapInfo.h:260
static bool isEqual(const unsigned short &LHS, const unsigned short &RHS)
Definition: DenseMapInfo.h:87
static char getTombstoneKey()
Definition: DenseMapInfo.h:62
static ElementCount getEmptyKey()
Definition: DenseMapInfo.h:284
static unsigned getHashValue(hash_code val)
Definition: DenseMapInfo.h:279
static unsigned short getEmptyKey()
Definition: DenseMapInfo.h:83
static bool isEqual(const unsigned long &LHS, const unsigned long &RHS)
Definition: DenseMapInfo.h:112
static long getTombstoneKey()
Definition: DenseMapInfo.h:157
static bool isEqual(const long &LHS, const long &RHS)
Definition: DenseMapInfo.h:163
static StringRef getEmptyKey()
Definition: DenseMapInfo.h:222
static unsigned getHashValue(const unsigned &Val)
Definition: DenseMapInfo.h:96
static unsigned getHashValue(const unsigned char &Val)
Definition: DenseMapInfo.h:74
static unsigned getTombstoneKey()
Definition: DenseMapInfo.h:95
const T * data() const
Definition: ArrayRef.h:145
static ArrayRef< T > getTombstoneKey()
Definition: DenseMapInfo.h:255
static int getTombstoneKey()
Definition: DenseMapInfo.h:143
static StringRef getTombstoneKey()
Definition: DenseMapInfo.h:227
An opaque object representing a hash code.
Definition: Hashing.h:70
static long long getTombstoneKey()
Definition: DenseMapInfo.h:171
static bool isEqual(ArrayRef< T > LHS, ArrayRef< T > RHS)
Definition: DenseMapInfo.h:267
static unsigned getHashValue(const int &Val)
Definition: DenseMapInfo.h:144
static unsigned getHashValue(const T *PtrVal)
Definition: DenseMapInfo.h:51
static bool isEqual(const short &LHS, const short &RHS)
Definition: DenseMapInfo.h:137
static unsigned getHashValue(const Pair &PairVal)
Definition: DenseMapInfo.h:200
static unsigned getHashValue(const char &Val)
Definition: DenseMapInfo.h:63
LLVM_NODISCARD const char * data() const
data - Get a pointer to the start of the string (which may not be null terminated).
Definition: StringRef.h:136
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static hash_code getTombstoneKey()
Definition: DenseMapInfo.h:278
static unsigned long long getTombstoneKey()
Definition: DenseMapInfo.h:120
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:48
static unsigned short getTombstoneKey()
Definition: DenseMapInfo.h:84
static bool isEqual(const ElementCount &LHS, const ElementCount &RHS)
Definition: DenseMapInfo.h:293
static unsigned char getEmptyKey()
Definition: DenseMapInfo.h:72
static bool isEqual(const unsigned char &LHS, const unsigned char &RHS)
Definition: DenseMapInfo.h:76
static hash_code getEmptyKey()
Definition: DenseMapInfo.h:277
static T * getTombstoneKey()
Definition: DenseMapInfo.h:45