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