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" 20 #include "llvm/Support/PointerLikeTypeTraits.h" 21 #include "llvm/Support/type_traits.h" 22 23 namespace llvm { 24 25 template<typename T> 26 struct DenseMapInfo { 27 //static inline T getEmptyKey(); 28 //static inline T getTombstoneKey(); 29 //static unsigned getHashValue(const T &Val); 30 //static bool isEqual(const T &LHS, const T &RHS); 31 }; 32 33 // Provide DenseMapInfo for all pointers. 34 template<typename T> 35 struct DenseMapInfo<T*> { 36 static inline T* getEmptyKey() { 37 uintptr_t Val = static_cast<uintptr_t>(-1); 38 Val <<= PointerLikeTypeTraits<T*>::NumLowBitsAvailable; 39 return reinterpret_cast<T*>(Val); 40 } 41 static inline T* getTombstoneKey() { 42 uintptr_t Val = static_cast<uintptr_t>(-2); 43 Val <<= PointerLikeTypeTraits<T*>::NumLowBitsAvailable; 44 return reinterpret_cast<T*>(Val); 45 } 46 static unsigned getHashValue(const T *PtrVal) { 47 return (unsigned((uintptr_t)PtrVal) >> 4) ^ 48 (unsigned((uintptr_t)PtrVal) >> 9); 49 } 50 static bool isEqual(const T *LHS, const T *RHS) { return LHS == RHS; } 51 }; 52 53 // Provide DenseMapInfo for chars. 54 template<> struct DenseMapInfo<char> { 55 static inline char getEmptyKey() { return ~0; } 56 static inline char getTombstoneKey() { return ~0 - 1; } 57 static unsigned getHashValue(const char& Val) { return Val * 37U; } 58 static bool isEqual(const char &LHS, const char &RHS) { 59 return LHS == RHS; 60 } 61 }; 62 63 // Provide DenseMapInfo for unsigned ints. 64 template<> struct DenseMapInfo<unsigned> { 65 static inline unsigned getEmptyKey() { return ~0U; } 66 static inline unsigned getTombstoneKey() { return ~0U - 1; } 67 static unsigned getHashValue(const unsigned& Val) { return Val * 37U; } 68 static bool isEqual(const unsigned& LHS, const unsigned& RHS) { 69 return LHS == RHS; 70 } 71 }; 72 73 // Provide DenseMapInfo for unsigned longs. 74 template<> struct DenseMapInfo<unsigned long> { 75 static inline unsigned long getEmptyKey() { return ~0UL; } 76 static inline unsigned long getTombstoneKey() { return ~0UL - 1L; } 77 static unsigned getHashValue(const unsigned long& Val) { 78 return (unsigned)(Val * 37UL); 79 } 80 static bool isEqual(const unsigned long& LHS, const unsigned long& RHS) { 81 return LHS == RHS; 82 } 83 }; 84 85 // Provide DenseMapInfo for unsigned long longs. 86 template<> struct DenseMapInfo<unsigned long long> { 87 static inline unsigned long long getEmptyKey() { return ~0ULL; } 88 static inline unsigned long long getTombstoneKey() { return ~0ULL - 1ULL; } 89 static unsigned getHashValue(const unsigned long long& Val) { 90 return (unsigned)(Val * 37ULL); 91 } 92 static bool isEqual(const unsigned long long& LHS, 93 const unsigned long long& RHS) { 94 return LHS == RHS; 95 } 96 }; 97 98 // Provide DenseMapInfo for ints. 99 template<> struct DenseMapInfo<int> { 100 static inline int getEmptyKey() { return 0x7fffffff; } 101 static inline int getTombstoneKey() { return -0x7fffffff - 1; } 102 static unsigned getHashValue(const int& Val) { return (unsigned)(Val * 37U); } 103 static bool isEqual(const int& LHS, const int& RHS) { 104 return LHS == RHS; 105 } 106 }; 107 108 // Provide DenseMapInfo for longs. 109 template<> struct DenseMapInfo<long> { 110 static inline long getEmptyKey() { 111 return (1UL << (sizeof(long) * 8 - 1)) - 1UL; 112 } 113 static inline long getTombstoneKey() { return getEmptyKey() - 1L; } 114 static unsigned getHashValue(const long& Val) { 115 return (unsigned)(Val * 37UL); 116 } 117 static bool isEqual(const long& LHS, const long& RHS) { 118 return LHS == RHS; 119 } 120 }; 121 122 // Provide DenseMapInfo for long longs. 123 template<> struct DenseMapInfo<long long> { 124 static inline long long getEmptyKey() { return 0x7fffffffffffffffLL; } 125 static inline long long getTombstoneKey() { return -0x7fffffffffffffffLL-1; } 126 static unsigned getHashValue(const long long& Val) { 127 return (unsigned)(Val * 37ULL); 128 } 129 static bool isEqual(const long long& LHS, 130 const long long& RHS) { 131 return LHS == RHS; 132 } 133 }; 134 135 // Provide DenseMapInfo for all pairs whose members have info. 136 template<typename T, typename U> 137 struct DenseMapInfo<std::pair<T, U> > { 138 typedef std::pair<T, U> Pair; 139 typedef DenseMapInfo<T> FirstInfo; 140 typedef DenseMapInfo<U> SecondInfo; 141 142 static inline Pair getEmptyKey() { 143 return std::make_pair(FirstInfo::getEmptyKey(), 144 SecondInfo::getEmptyKey()); 145 } 146 static inline Pair getTombstoneKey() { 147 return std::make_pair(FirstInfo::getTombstoneKey(), 148 SecondInfo::getTombstoneKey()); 149 } 150 static unsigned getHashValue(const Pair& PairVal) { 151 uint64_t key = (uint64_t)FirstInfo::getHashValue(PairVal.first) << 32 152 | (uint64_t)SecondInfo::getHashValue(PairVal.second); 153 key += ~(key << 32); 154 key ^= (key >> 22); 155 key += ~(key << 13); 156 key ^= (key >> 8); 157 key += (key << 3); 158 key ^= (key >> 15); 159 key += ~(key << 27); 160 key ^= (key >> 31); 161 return (unsigned)key; 162 } 163 static bool isEqual(const Pair &LHS, const Pair &RHS) { 164 return FirstInfo::isEqual(LHS.first, RHS.first) && 165 SecondInfo::isEqual(LHS.second, RHS.second); 166 } 167 }; 168 169 // Provide DenseMapInfo for StringRefs. 170 template <> struct DenseMapInfo<StringRef> { 171 static inline StringRef getEmptyKey() { 172 return StringRef(reinterpret_cast<const char *>(~static_cast<uintptr_t>(0)), 173 0); 174 } 175 static inline StringRef getTombstoneKey() { 176 return StringRef(reinterpret_cast<const char *>(~static_cast<uintptr_t>(1)), 177 0); 178 } 179 static unsigned getHashValue(StringRef Val) { 180 assert(Val.data() != getEmptyKey().data() && "Cannot hash the empty key!"); 181 assert(Val.data() != getTombstoneKey().data() && 182 "Cannot hash the tombstone key!"); 183 return (unsigned)(hash_value(Val)); 184 } 185 static bool isEqual(StringRef LHS, StringRef RHS) { 186 if (RHS.data() == getEmptyKey().data()) 187 return LHS.data() == getEmptyKey().data(); 188 if (RHS.data() == getTombstoneKey().data()) 189 return LHS.data() == getTombstoneKey().data(); 190 return LHS == RHS; 191 } 192 }; 193 194 // Provide DenseMapInfo for ArrayRefs. 195 template <typename T> struct DenseMapInfo<ArrayRef<T>> { 196 static inline ArrayRef<T> getEmptyKey() { 197 return ArrayRef<T>(reinterpret_cast<const T *>(~static_cast<uintptr_t>(0)), 198 size_t(0)); 199 } 200 static inline ArrayRef<T> getTombstoneKey() { 201 return ArrayRef<T>(reinterpret_cast<const T *>(~static_cast<uintptr_t>(1)), 202 size_t(0)); 203 } 204 static unsigned getHashValue(ArrayRef<T> Val) { 205 assert(Val.data() != getEmptyKey().data() && "Cannot hash the empty key!"); 206 assert(Val.data() != getTombstoneKey().data() && 207 "Cannot hash the tombstone key!"); 208 return (unsigned)(hash_value(Val)); 209 } 210 static bool isEqual(ArrayRef<T> LHS, ArrayRef<T> RHS) { 211 if (RHS.data() == getEmptyKey().data()) 212 return LHS.data() == getEmptyKey().data(); 213 if (RHS.data() == getTombstoneKey().data()) 214 return LHS.data() == getTombstoneKey().data(); 215 return LHS == RHS; 216 } 217 }; 218 219 } // end namespace llvm 220 221 #endif 222
