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