LLVM  6.0.0svn
DenseMapInfo.h
Go to the documentation of this file.
1 //===- llvm/ADT/DenseMapInfo.h - Type traits for DenseMap -------*- C++ -*-===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file defines DenseMapInfo traits for DenseMap.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #ifndef LLVM_ADT_DENSEMAPINFO_H
15 #define LLVM_ADT_DENSEMAPINFO_H
16 
17 #include "llvm/ADT/ArrayRef.h"
18 #include "llvm/ADT/Hashing.h"
19 #include "llvm/ADT/StringRef.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>;
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 } // end namespace llvm
266 
267 #endif // LLVM_ADT_DENSEMAPINFO_H
static bool isEqual(const char &LHS, const char &RHS)
Definition: DenseMapInfo.h:65
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
static unsigned getHashValue(const unsigned long &Val)
Definition: DenseMapInfo.h:97
static unsigned long getEmptyKey()
Definition: DenseMapInfo.h:94
static unsigned getHashValue(const unsigned long long &Val)
Definition: DenseMapInfo.h:111
static bool isEqual(const T *LHS, const T *RHS)
Definition: DenseMapInfo.h:56
static bool isEqual(StringRef LHS, StringRef RHS)
Definition: DenseMapInfo.h:228
static ArrayRef< T > getEmptyKey()
Definition: DenseMapInfo.h:239
static unsigned getHashValue(const long &Val)
Definition: DenseMapInfo.h:148
static unsigned getEmptyKey()
Definition: DenseMapInfo.h:83
static unsigned getHashValue(const unsigned short &Val)
Definition: DenseMapInfo.h:74
LLVM_NODISCARD LLVM_ATTRIBUTE_ALWAYS_INLINE const char * data() const
data - Get a pointer to the start of the string (which may not be null terminated).
Definition: StringRef.h:128
static unsigned getHashValue(const long long &Val)
Definition: DenseMapInfo.h:162
static bool isEqual(const unsigned long long &LHS, const unsigned long long &RHS)
Definition: DenseMapInfo.h:115
static bool isEqual(const long long &LHS, const long long &RHS)
Definition: DenseMapInfo.h:166
static bool isEqual(const int &LHS, const int &RHS)
Definition: DenseMapInfo.h:135
static bool isEqual(const Pair &LHS, const Pair &RHS)
Definition: DenseMapInfo.h:203
static unsigned getHashValue(StringRef Val)
Definition: DenseMapInfo.h:221
Definition: BitVector.h:920
static unsigned long long getEmptyKey()
Definition: DenseMapInfo.h:108
static unsigned getHashValue(const short &Val)
Definition: DenseMapInfo.h:125
static bool isEqual(const Function &Caller, const Function &Callee)
static long long getEmptyKey()
Definition: DenseMapInfo.h:159
static bool isEqual(const unsigned &LHS, const unsigned &RHS)
Definition: DenseMapInfo.h:87
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:33
hash_code hash_value(const APFloat &Arg)
See friend declarations above.
Definition: APFloat.cpp:4428
static short getTombstoneKey()
Definition: DenseMapInfo.h:124
static unsigned long getTombstoneKey()
Definition: DenseMapInfo.h:95
static unsigned getHashValue(ArrayRef< T > Val)
Definition: DenseMapInfo.h:249
static bool isEqual(const unsigned short &LHS, const unsigned short &RHS)
Definition: DenseMapInfo.h:76
static char getTombstoneKey()
Definition: DenseMapInfo.h:62
static unsigned short getEmptyKey()
Definition: DenseMapInfo.h:72
static bool isEqual(const unsigned long &LHS, const unsigned long &RHS)
Definition: DenseMapInfo.h:101
static long getTombstoneKey()
Definition: DenseMapInfo.h:146
static bool isEqual(const long &LHS, const long &RHS)
Definition: DenseMapInfo.h:152
static StringRef getEmptyKey()
Definition: DenseMapInfo.h:211
static unsigned getHashValue(const unsigned &Val)
Definition: DenseMapInfo.h:85
static unsigned getTombstoneKey()
Definition: DenseMapInfo.h:84
const T * data() const
Definition: ArrayRef.h:146
static ArrayRef< T > getTombstoneKey()
Definition: DenseMapInfo.h:244
static int getTombstoneKey()
Definition: DenseMapInfo.h:132
static StringRef getTombstoneKey()
Definition: DenseMapInfo.h:216
static long long getTombstoneKey()
Definition: DenseMapInfo.h:160
static bool isEqual(ArrayRef< T > LHS, ArrayRef< T > RHS)
Definition: DenseMapInfo.h:256
static unsigned getHashValue(const int &Val)
Definition: DenseMapInfo.h:133
static unsigned getHashValue(const T *PtrVal)
Definition: DenseMapInfo.h:51
static bool isEqual(const short &LHS, const short &RHS)
Definition: DenseMapInfo.h:126
static unsigned getHashValue(const Pair &PairVal)
Definition: DenseMapInfo.h:189
static unsigned getHashValue(const char &Val)
Definition: DenseMapInfo.h:63
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static unsigned long long getTombstoneKey()
Definition: DenseMapInfo.h:109
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:49
static unsigned short getTombstoneKey()
Definition: DenseMapInfo.h:73
static T * getTombstoneKey()
Definition: DenseMapInfo.h:45