14 #ifndef LLVM_ADT_DENSEMAPINFO_H 15 #define LLVM_ADT_DENSEMAPINFO_H 17 #include "llvm/ArrayRef.h" 18 #include "llvm/Hashing.h" 19 #include "llvm/StringRef.h" 20 #include "llvm/PointerLikeTypeTraits.h" 21 #include "llvm/type_traits.h" 37 CachedHash(T Val,
unsigned Hash) : Val(std::move(Val)), Hash(Hash) {}
53 assert(!isEqual(Val, getEmptyKey()) &&
"Cannot hash the empty key!");
54 assert(!isEqual(Val, getTombstoneKey()) &&
55 "Cannot hash the tombstone key!");
66 static inline T* getEmptyKey() {
67 uintptr_t Val =
static_cast<uintptr_t
>(-1);
68 Val <<= PointerLikeTypeTraits<T*>::NumLowBitsAvailable;
69 return reinterpret_cast<T*
>(Val);
71 static inline T* getTombstoneKey() {
72 uintptr_t Val =
static_cast<uintptr_t
>(-2);
73 Val <<= PointerLikeTypeTraits<T*>::NumLowBitsAvailable;
74 return reinterpret_cast<T*
>(Val);
76 static unsigned getHashValue(
const T *PtrVal) {
77 return (
unsigned((uintptr_t)PtrVal) >> 4) ^
78 (unsigned((uintptr_t)PtrVal) >> 9);
80 static bool isEqual(
const T *LHS,
const T *RHS) {
return LHS == RHS; }
85 static inline char getEmptyKey() {
return ~0; }
86 static inline char getTombstoneKey() {
return ~0 - 1; }
87 static unsigned getHashValue(
const char& Val) {
return Val * 37U; }
88 static bool isEqual(
const char &LHS,
const char &RHS) {
95 static inline unsigned getEmptyKey() {
return ~0U; }
96 static inline unsigned getTombstoneKey() {
return ~0U - 1; }
97 static unsigned getHashValue(
const unsigned& Val) {
return Val * 37U; }
98 static bool isEqual(
const unsigned& LHS,
const unsigned& RHS) {
105 static inline unsigned long getEmptyKey() {
return ~0UL; }
106 static inline unsigned long getTombstoneKey() {
return ~0UL - 1L; }
107 static unsigned getHashValue(
const unsigned long& Val) {
108 return (
unsigned)(Val * 37UL);
110 static bool isEqual(
const unsigned long& LHS,
const unsigned long& RHS) {
117 static inline unsigned long long getEmptyKey() {
return ~0ULL; }
118 static inline unsigned long long getTombstoneKey() {
return ~0ULL - 1ULL; }
119 static unsigned getHashValue(
const unsigned long long& Val) {
120 return (
unsigned)(Val * 37ULL);
122 static bool isEqual(
const unsigned long long& LHS,
123 const unsigned long long& RHS) {
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 static bool isEqual(
const int& LHS,
const int& RHS) {
140 static inline long getEmptyKey() {
141 return (1UL << (
sizeof(
long) * 8 - 1)) - 1UL;
143 static inline long getTombstoneKey() {
return getEmptyKey() - 1L; }
144 static unsigned getHashValue(
const long& Val) {
145 return (
unsigned)(Val * 37UL);
147 static bool isEqual(
const long& LHS,
const long& RHS) {
154 static inline long long getEmptyKey() {
return 0x7fffffffffffffffLL; }
155 static inline long long getTombstoneKey() {
return -0x7fffffffffffffffLL-1; }
156 static unsigned getHashValue(
const long long& Val) {
157 return (
unsigned)(Val * 37ULL);
159 static bool isEqual(
const long long& LHS,
160 const long long& RHS) {
166 template<
typename T,
typename U>
168 typedef std::pair<T, U> Pair;
172 static inline Pair getEmptyKey() {
173 return std::make_pair(FirstInfo::getEmptyKey(),
174 SecondInfo::getEmptyKey());
176 static inline Pair getTombstoneKey() {
177 return std::make_pair(FirstInfo::getTombstoneKey(),
178 SecondInfo::getTombstoneKey());
180 static unsigned getHashValue(
const Pair& PairVal) {
181 uint64_t key = (uint64_t)FirstInfo::getHashValue(PairVal.first) << 32
182 | (uint64_t)SecondInfo::getHashValue(PairVal.second);
191 return (
unsigned)key;
193 static bool isEqual(
const Pair &LHS,
const Pair &RHS) {
194 return FirstInfo::isEqual(LHS.first, RHS.first) &&
195 SecondInfo::isEqual(LHS.second, RHS.second);
202 return StringRef(reinterpret_cast<const char *>(~static_cast<uintptr_t>(0)),
205 static inline StringRef getTombstoneKey() {
206 return StringRef(reinterpret_cast<const char *>(~static_cast<uintptr_t>(1)),
209 static unsigned getHashValue(
StringRef Val) {
210 assert(Val.
data() != getEmptyKey().data() &&
"Cannot hash the empty key!");
211 assert(Val.
data() != getTombstoneKey().data() &&
212 "Cannot hash the tombstone key!");
213 return (
unsigned)(hash_value(Val));
216 if (RHS.
data() == getEmptyKey().data())
217 return LHS.
data() == getEmptyKey().data();
218 if (RHS.
data() == getTombstoneKey().data())
219 return LHS.
data() == getTombstoneKey().data();
227 return ArrayRef<T>(
reinterpret_cast<const T *
>(~static_cast<uintptr_t>(0)),
231 return ArrayRef<T>(
reinterpret_cast<const T *
>(~static_cast<uintptr_t>(1)),
235 assert(Val.data() != getEmptyKey().data() &&
"Cannot hash the empty key!");
236 assert(Val.data() != getTombstoneKey().data() &&
237 "Cannot hash the tombstone key!");
238 return (
unsigned)(hash_value(Val));
241 if (RHS.data() == getEmptyKey().data())
242 return LHS.data() == getEmptyKey().data();
243 if (RHS.data() == getTombstoneKey().data())
244 return LHS.data() == getTombstoneKey().data();
Definition: DenseMapInfo.h:26
Definition: DenseMapInfo.h:33
Definition: json.cpp:1170
const char * data() const
data - Get a pointer to the start of the string (which may not be null terminated).
Definition: StringRef.h:139
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: ArrayRef.h:32
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:42