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" 19 #include "llvm/Support/PointerLikeTypeTraits.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>; 187 using FirstInfo = DenseMapInfo<T>; 188 using SecondInfo = DenseMapInfo<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 301