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