1 //===- sanitizer_dense_map_info.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 #ifndef SANITIZER_DENSE_MAP_INFO_H 10 #define SANITIZER_DENSE_MAP_INFO_H 11 12 #include "sanitizer_common.h" 13 #include "sanitizer_internal_defs.h" 14 #include "sanitizer_type_traits.h" 15 16 namespace __sanitizer { 17 18 namespace detail { 19 20 /// Simplistic combination of 32-bit hash values into 32-bit hash values. 21 static constexpr unsigned combineHashValue(unsigned a, unsigned b) { 22 u64 key = (u64)a << 32 | (u64)b; 23 key += ~(key << 32); 24 key ^= (key >> 22); 25 key += ~(key << 13); 26 key ^= (key >> 8); 27 key += (key << 3); 28 key ^= (key >> 15); 29 key += ~(key << 27); 30 key ^= (key >> 31); 31 return (unsigned)key; 32 } 33 34 // We extend a pair to allow users to override the bucket type with their own 35 // implementation without requiring two members. 36 template <typename KeyT, typename ValueT> 37 struct DenseMapPair { 38 KeyT first = {}; 39 ValueT second = {}; 40 constexpr DenseMapPair() = default; 41 constexpr DenseMapPair(const KeyT &f, const ValueT &s) 42 : first(f), second(s) {} 43 44 template <typename KeyT2, typename ValueT2> 45 constexpr DenseMapPair(KeyT2 &&f, ValueT2 &&s) 46 : first(__sanitizer::forward<KeyT2>(f)), 47 second(__sanitizer::forward<ValueT2>(s)) {} 48 49 constexpr DenseMapPair(const DenseMapPair &other) = default; 50 constexpr DenseMapPair &operator=(const DenseMapPair &other) = default; 51 constexpr DenseMapPair(DenseMapPair &&other) = default; 52 constexpr DenseMapPair &operator=(DenseMapPair &&other) = default; 53 54 KeyT &getFirst() { return first; } 55 const KeyT &getFirst() const { return first; } 56 ValueT &getSecond() { return second; } 57 const ValueT &getSecond() const { return second; } 58 }; 59 60 } // end namespace detail 61 62 template <typename T> 63 struct DenseMapInfo { 64 // static T getEmptyKey(); 65 // static T getTombstoneKey(); 66 // static unsigned getHashValue(const T &Val); 67 // static bool isEqual(const T &LHS, const T &RHS); 68 }; 69 70 // Provide DenseMapInfo for all pointers. Come up with sentinel pointer values 71 // that are aligned to alignof(T) bytes, but try to avoid requiring T to be 72 // complete. This allows clients to instantiate DenseMap<T*, ...> with forward 73 // declared key types. Assume that no pointer key type requires more than 4096 74 // bytes of alignment. 75 template <typename T> 76 struct DenseMapInfo<T *> { 77 // The following should hold, but it would require T to be complete: 78 // static_assert(alignof(T) <= (1 << Log2MaxAlign), 79 // "DenseMap does not support pointer keys requiring more than " 80 // "Log2MaxAlign bits of alignment"); 81 static constexpr uptr Log2MaxAlign = 12; 82 83 static constexpr T *getEmptyKey() { 84 uptr Val = static_cast<uptr>(-1); 85 Val <<= Log2MaxAlign; 86 return reinterpret_cast<T *>(Val); 87 } 88 89 static constexpr T *getTombstoneKey() { 90 uptr Val = static_cast<uptr>(-2); 91 Val <<= Log2MaxAlign; 92 return reinterpret_cast<T *>(Val); 93 } 94 95 static constexpr unsigned getHashValue(const T *PtrVal) { 96 return (unsigned((uptr)PtrVal) >> 4) ^ (unsigned((uptr)PtrVal) >> 9); 97 } 98 99 static constexpr bool isEqual(const T *LHS, const T *RHS) { 100 return LHS == RHS; 101 } 102 }; 103 104 // Provide DenseMapInfo for chars. 105 template <> 106 struct DenseMapInfo<char> { 107 static constexpr char getEmptyKey() { return ~0; } 108 static constexpr char getTombstoneKey() { return ~0 - 1; } 109 static constexpr unsigned getHashValue(const char &Val) { return Val * 37U; } 110 111 static constexpr bool isEqual(const char &LHS, const char &RHS) { 112 return LHS == RHS; 113 } 114 }; 115 116 // Provide DenseMapInfo for unsigned chars. 117 template <> 118 struct DenseMapInfo<unsigned char> { 119 static constexpr unsigned char getEmptyKey() { return ~0; } 120 static constexpr unsigned char getTombstoneKey() { return ~0 - 1; } 121 static constexpr unsigned getHashValue(const unsigned char &Val) { 122 return Val * 37U; 123 } 124 125 static constexpr bool isEqual(const unsigned char &LHS, 126 const unsigned char &RHS) { 127 return LHS == RHS; 128 } 129 }; 130 131 // Provide DenseMapInfo for unsigned shorts. 132 template <> 133 struct DenseMapInfo<unsigned short> { 134 static constexpr unsigned short getEmptyKey() { return 0xFFFF; } 135 static constexpr unsigned short getTombstoneKey() { return 0xFFFF - 1; } 136 static constexpr unsigned getHashValue(const unsigned short &Val) { 137 return Val * 37U; 138 } 139 140 static constexpr bool isEqual(const unsigned short &LHS, 141 const unsigned short &RHS) { 142 return LHS == RHS; 143 } 144 }; 145 146 // Provide DenseMapInfo for unsigned ints. 147 template <> 148 struct DenseMapInfo<unsigned> { 149 static constexpr unsigned getEmptyKey() { return ~0U; } 150 static constexpr unsigned getTombstoneKey() { return ~0U - 1; } 151 static constexpr unsigned getHashValue(const unsigned &Val) { 152 return Val * 37U; 153 } 154 155 static constexpr bool isEqual(const unsigned &LHS, const unsigned &RHS) { 156 return LHS == RHS; 157 } 158 }; 159 160 // Provide DenseMapInfo for unsigned longs. 161 template <> 162 struct DenseMapInfo<unsigned long> { 163 static constexpr unsigned long getEmptyKey() { return ~0UL; } 164 static constexpr unsigned long getTombstoneKey() { return ~0UL - 1L; } 165 166 static constexpr unsigned getHashValue(const unsigned long &Val) { 167 return (unsigned)(Val * 37UL); 168 } 169 170 static constexpr bool isEqual(const unsigned long &LHS, 171 const unsigned long &RHS) { 172 return LHS == RHS; 173 } 174 }; 175 176 // Provide DenseMapInfo for unsigned long longs. 177 template <> 178 struct DenseMapInfo<unsigned long long> { 179 static constexpr unsigned long long getEmptyKey() { return ~0ULL; } 180 static constexpr unsigned long long getTombstoneKey() { return ~0ULL - 1ULL; } 181 182 static constexpr unsigned getHashValue(const unsigned long long &Val) { 183 return (unsigned)(Val * 37ULL); 184 } 185 186 static constexpr bool isEqual(const unsigned long long &LHS, 187 const unsigned long long &RHS) { 188 return LHS == RHS; 189 } 190 }; 191 192 // Provide DenseMapInfo for shorts. 193 template <> 194 struct DenseMapInfo<short> { 195 static constexpr short getEmptyKey() { return 0x7FFF; } 196 static constexpr short getTombstoneKey() { return -0x7FFF - 1; } 197 static constexpr unsigned getHashValue(const short &Val) { return Val * 37U; } 198 static constexpr bool isEqual(const short &LHS, const short &RHS) { 199 return LHS == RHS; 200 } 201 }; 202 203 // Provide DenseMapInfo for ints. 204 template <> 205 struct DenseMapInfo<int> { 206 static constexpr int getEmptyKey() { return 0x7fffffff; } 207 static constexpr int getTombstoneKey() { return -0x7fffffff - 1; } 208 static constexpr unsigned getHashValue(const int &Val) { 209 return (unsigned)(Val * 37U); 210 } 211 212 static constexpr bool isEqual(const int &LHS, const int &RHS) { 213 return LHS == RHS; 214 } 215 }; 216 217 // Provide DenseMapInfo for longs. 218 template <> 219 struct DenseMapInfo<long> { 220 static constexpr long getEmptyKey() { 221 return (1UL << (sizeof(long) * 8 - 1)) - 1UL; 222 } 223 224 static constexpr long getTombstoneKey() { return getEmptyKey() - 1L; } 225 226 static constexpr unsigned getHashValue(const long &Val) { 227 return (unsigned)(Val * 37UL); 228 } 229 230 static constexpr bool isEqual(const long &LHS, const long &RHS) { 231 return LHS == RHS; 232 } 233 }; 234 235 // Provide DenseMapInfo for long longs. 236 template <> 237 struct DenseMapInfo<long long> { 238 static constexpr long long getEmptyKey() { return 0x7fffffffffffffffLL; } 239 static constexpr long long getTombstoneKey() { 240 return -0x7fffffffffffffffLL - 1; 241 } 242 243 static constexpr unsigned getHashValue(const long long &Val) { 244 return (unsigned)(Val * 37ULL); 245 } 246 247 static constexpr bool isEqual(const long long &LHS, const long long &RHS) { 248 return LHS == RHS; 249 } 250 }; 251 252 // Provide DenseMapInfo for all pairs whose members have info. 253 template <typename T, typename U> 254 struct DenseMapInfo<detail::DenseMapPair<T, U>> { 255 using Pair = detail::DenseMapPair<T, U>; 256 using FirstInfo = DenseMapInfo<T>; 257 using SecondInfo = DenseMapInfo<U>; 258 259 static constexpr Pair getEmptyKey() { 260 return detail::DenseMapPair<T, U>(FirstInfo::getEmptyKey(), 261 SecondInfo::getEmptyKey()); 262 } 263 264 static constexpr Pair getTombstoneKey() { 265 return detail::DenseMapPair<T, U>(FirstInfo::getTombstoneKey(), 266 SecondInfo::getTombstoneKey()); 267 } 268 269 static constexpr unsigned getHashValue(const Pair &PairVal) { 270 return detail::combineHashValue(FirstInfo::getHashValue(PairVal.first), 271 SecondInfo::getHashValue(PairVal.second)); 272 } 273 274 static constexpr bool isEqual(const Pair &LHS, const Pair &RHS) { 275 return FirstInfo::isEqual(LHS.first, RHS.first) && 276 SecondInfo::isEqual(LHS.second, RHS.second); 277 } 278 }; 279 280 } // namespace __sanitizer 281 282 #endif // SANITIZER_DENSE_MAP_INFO_H 283