libsanitizer/sanitizer_common/sanitizer_dense_map_info.h

   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