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 /// \file 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 <cassert> 18 #include <cstddef> 19 #include <cstdint> 20 #include <tuple> 21 #include <utility> 22 23 namespace llvm { 24 25 namespace detail { 26 27 /// Simplistic combination of 32-bit hash values into 32-bit hash values. 28 static inline unsigned combineHashValue(unsigned a, unsigned b) { 29 uint64_t key = (uint64_t)a << 32 | (uint64_t)b; 30 key += ~(key << 32); 31 key ^= (key >> 22); 32 key += ~(key << 13); 33 key ^= (key >> 8); 34 key += (key << 3); 35 key ^= (key >> 15); 36 key += ~(key << 27); 37 key ^= (key >> 31); 38 return (unsigned)key; 39 } 40 41 } // end namespace detail 42 43 /// An information struct used to provide DenseMap with the various necessary 44 /// components for a given value type `T`. `Enable` is an optional additional 45 /// parameter that is used to support SFINAE (generally using std::enable_if_t) 46 /// in derived DenseMapInfo specializations; in non-SFINAE use cases this should 47 /// just be `void`. 48 template<typename T, typename Enable = void> 49 struct DenseMapInfo { 50 //static inline T getEmptyKey(); 51 //static inline T getTombstoneKey(); 52 //static unsigned getHashValue(const T &Val); 53 //static bool isEqual(const T &LHS, const T &RHS); 54 }; 55 56 // Provide DenseMapInfo for all pointers. Come up with sentinel pointer values 57 // that are aligned to alignof(T) bytes, but try to avoid requiring T to be 58 // complete. This allows clients to instantiate DenseMap<T*, ...> with forward 59 // declared key types. Assume that no pointer key type requires more than 4096 60 // bytes of alignment. 61 template<typename T> 62 struct DenseMapInfo<T*> { 63 // The following should hold, but it would require T to be complete: 64 // static_assert(alignof(T) <= (1 << Log2MaxAlign), 65 // "DenseMap does not support pointer keys requiring more than " 66 // "Log2MaxAlign bits of alignment"); 67 static constexpr uintptr_t Log2MaxAlign = 12; 68 69 static inline T* getEmptyKey() { 70 uintptr_t Val = static_cast<uintptr_t>(-1); 71 Val <<= Log2MaxAlign; 72 return reinterpret_cast<T*>(Val); 73 } 74 75 static inline T* getTombstoneKey() { 76 uintptr_t Val = static_cast<uintptr_t>(-2); 77 Val <<= Log2MaxAlign; 78 return reinterpret_cast<T*>(Val); 79 } 80 81 static unsigned getHashValue(const T *PtrVal) { 82 return (unsigned((uintptr_t)PtrVal) >> 4) ^ 83 (unsigned((uintptr_t)PtrVal) >> 9); 84 } 85 86 static bool isEqual(const T *LHS, const T *RHS) { return LHS == RHS; } 87 }; 88 89 // Provide DenseMapInfo for chars. 90 template<> struct DenseMapInfo<char> { 91 static inline char getEmptyKey() { return ~0; } 92 static inline char getTombstoneKey() { return ~0 - 1; } 93 static unsigned getHashValue(const char& Val) { return Val * 37U; } 94 95 static bool isEqual(const char &LHS, const char &RHS) { 96 return LHS == RHS; 97 } 98 }; 99 100 // Provide DenseMapInfo for unsigned chars. 101 template <> struct DenseMapInfo<unsigned char> { 102 static inline unsigned char getEmptyKey() { return ~0; } 103 static inline unsigned char getTombstoneKey() { return ~0 - 1; } 104 static unsigned getHashValue(const unsigned char &Val) { return Val * 37U; } 105 106 static bool isEqual(const unsigned char &LHS, const unsigned char &RHS) { 107 return LHS == RHS; 108 } 109 }; 110 111 // Provide DenseMapInfo for unsigned shorts. 112 template <> struct DenseMapInfo<unsigned short> { 113 static inline unsigned short getEmptyKey() { return 0xFFFF; } 114 static inline unsigned short getTombstoneKey() { return 0xFFFF - 1; } 115 static unsigned getHashValue(const unsigned short &Val) { return Val * 37U; } 116 117 static bool isEqual(const unsigned short &LHS, const unsigned short &RHS) { 118 return LHS == RHS; 119 } 120 }; 121 122 // Provide DenseMapInfo for unsigned ints. 123 template<> struct DenseMapInfo<unsigned> { 124 static inline unsigned getEmptyKey() { return ~0U; } 125 static inline unsigned getTombstoneKey() { return ~0U - 1; } 126 static unsigned getHashValue(const unsigned& Val) { return Val * 37U; } 127 128 static bool isEqual(const unsigned& LHS, const unsigned& RHS) { 129 return LHS == RHS; 130 } 131 }; 132 133 // Provide DenseMapInfo for unsigned longs. 134 template<> struct DenseMapInfo<unsigned long> { 135 static inline unsigned long getEmptyKey() { return ~0UL; } 136 static inline unsigned long getTombstoneKey() { return ~0UL - 1L; } 137 138 static unsigned getHashValue(const unsigned long& Val) { 139 return (unsigned)(Val * 37UL); 140 } 141 142 static bool isEqual(const unsigned long& LHS, const unsigned long& RHS) { 143 return LHS == RHS; 144 } 145 }; 146 147 // Provide DenseMapInfo for unsigned long longs. 148 template<> struct DenseMapInfo<unsigned long long> { 149 static inline unsigned long long getEmptyKey() { return ~0ULL; } 150 static inline unsigned long long getTombstoneKey() { return ~0ULL - 1ULL; } 151 152 static unsigned getHashValue(const unsigned long long& Val) { 153 return (unsigned)(Val * 37ULL); 154 } 155 156 static bool isEqual(const unsigned long long& LHS, 157 const unsigned long long& RHS) { 158 return LHS == RHS; 159 } 160 }; 161 162 // Provide DenseMapInfo for shorts. 163 template <> struct DenseMapInfo<short> { 164 static inline short getEmptyKey() { return 0x7FFF; } 165 static inline short getTombstoneKey() { return -0x7FFF - 1; } 166 static unsigned getHashValue(const short &Val) { return Val * 37U; } 167 static bool isEqual(const short &LHS, const short &RHS) { return LHS == RHS; } 168 }; 169 170 // Provide DenseMapInfo for ints. 171 template<> struct DenseMapInfo<int> { 172 static inline int getEmptyKey() { return 0x7fffffff; } 173 static inline int getTombstoneKey() { return -0x7fffffff - 1; } 174 static unsigned getHashValue(const int& Val) { return (unsigned)(Val * 37U); } 175 176 static bool isEqual(const int& LHS, const int& RHS) { 177 return LHS == RHS; 178 } 179 }; 180 181 // Provide DenseMapInfo for longs. 182 template<> struct DenseMapInfo<long> { 183 static inline long getEmptyKey() { 184 return (1UL << (sizeof(long) * 8 - 1)) - 1UL; 185 } 186 187 static inline long getTombstoneKey() { return getEmptyKey() - 1L; } 188 189 static unsigned getHashValue(const long& Val) { 190 return (unsigned)(Val * 37UL); 191 } 192 193 static bool isEqual(const long& LHS, const long& RHS) { 194 return LHS == RHS; 195 } 196 }; 197 198 // Provide DenseMapInfo for long longs. 199 template<> struct DenseMapInfo<long long> { 200 static inline long long getEmptyKey() { return 0x7fffffffffffffffLL; } 201 static inline long long getTombstoneKey() { return -0x7fffffffffffffffLL-1; } 202 203 static unsigned getHashValue(const long long& Val) { 204 return (unsigned)(Val * 37ULL); 205 } 206 207 static bool isEqual(const long long& LHS, 208 const long long& RHS) { 209 return LHS == RHS; 210 } 211 }; 212 213 // Provide DenseMapInfo for all pairs whose members have info. 214 template<typename T, typename U> 215 struct DenseMapInfo<std::pair<T, U>> { 216 using Pair = std::pair<T, U>; 217 using FirstInfo = DenseMapInfo<T>; 218 using SecondInfo = DenseMapInfo<U>; 219 220 static inline Pair getEmptyKey() { 221 return std::make_pair(FirstInfo::getEmptyKey(), 222 SecondInfo::getEmptyKey()); 223 } 224 225 static inline Pair getTombstoneKey() { 226 return std::make_pair(FirstInfo::getTombstoneKey(), 227 SecondInfo::getTombstoneKey()); 228 } 229 230 static unsigned getHashValue(const Pair& PairVal) { 231 return detail::combineHashValue(FirstInfo::getHashValue(PairVal.first), 232 SecondInfo::getHashValue(PairVal.second)); 233 } 234 235 static bool isEqual(const Pair &LHS, const Pair &RHS) { 236 return FirstInfo::isEqual(LHS.first, RHS.first) && 237 SecondInfo::isEqual(LHS.second, RHS.second); 238 } 239 }; 240 241 // Provide DenseMapInfo for all tuples whose members have info. 242 template <typename... Ts> struct DenseMapInfo<std::tuple<Ts...>> { 243 using Tuple = std::tuple<Ts...>; 244 245 static inline Tuple getEmptyKey() { 246 return Tuple(DenseMapInfo<Ts>::getEmptyKey()...); 247 } 248 249 static inline Tuple getTombstoneKey() { 250 return Tuple(DenseMapInfo<Ts>::getTombstoneKey()...); 251 } 252 253 template <unsigned I> 254 static unsigned getHashValueImpl(const Tuple &values, std::false_type) { 255 using EltType = typename std::tuple_element<I, Tuple>::type; 256 std::integral_constant<bool, I + 1 == sizeof...(Ts)> atEnd; 257 return detail::combineHashValue( 258 DenseMapInfo<EltType>::getHashValue(std::get<I>(values)), 259 getHashValueImpl<I + 1>(values, atEnd)); 260 } 261 262 template <unsigned I> 263 static unsigned getHashValueImpl(const Tuple &, std::true_type) { 264 return 0; 265 } 266 267 static unsigned getHashValue(const std::tuple<Ts...> &values) { 268 std::integral_constant<bool, 0 == sizeof...(Ts)> atEnd; 269 return getHashValueImpl<0>(values, atEnd); 270 } 271 272 template <unsigned I> 273 static bool isEqualImpl(const Tuple &lhs, const Tuple &rhs, std::false_type) { 274 using EltType = typename std::tuple_element<I, Tuple>::type; 275 std::integral_constant<bool, I + 1 == sizeof...(Ts)> atEnd; 276 return DenseMapInfo<EltType>::isEqual(std::get<I>(lhs), std::get<I>(rhs)) && 277 isEqualImpl<I + 1>(lhs, rhs, atEnd); 278 } 279 280 template <unsigned I> 281 static bool isEqualImpl(const Tuple &, const Tuple &, std::true_type) { 282 return true; 283 } 284 285 static bool isEqual(const Tuple &lhs, const Tuple &rhs) { 286 std::integral_constant<bool, 0 == sizeof...(Ts)> atEnd; 287 return isEqualImpl<0>(lhs, rhs, atEnd); 288 } 289 }; 290 291 } // end namespace llvm 292 293 #endif // LLVM_ADT_DENSEMAPINFO_H 294