contrib/llvm-project/llvm/include/llvm/ADT/DenseMapInfo.h

   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 // This file defines DenseMapInfo traits for DenseMap.
  10 //
  11 //===----------------------------------------------------------------------===//
  12
  13 #ifndef LLVM_ADT_DENSEMAPINFO_H
  14 #define LLVM_ADT_DENSEMAPINFO_H
  15
  16 #include "llvm/ADT/ArrayRef.h"
  17 #include "llvm/ADT/Hashing.h"
  18 #include "llvm/ADT/StringRef.h"
  19 #include <cassert>
  20 #include <cstddef>
  21 #include <cstdint>
  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 template<typename T>
  45 struct DenseMapInfo {
  46   //static inline T getEmptyKey();
  47   //static inline T getTombstoneKey();
  48   //static unsigned getHashValue(const T &Val);
  49   //static bool isEqual(const T &LHS, const T &RHS);
  50 };
  51
  52 // Provide DenseMapInfo for all pointers. Come up with sentinel pointer values
  53 // that are aligned to alignof(T) bytes, but try to avoid requiring T to be
  54 // complete. This allows clients to instantiate DenseMap<T*, ...> with forward
  55 // declared key types. Assume that no pointer key type requires more than 4096
  56 // bytes of alignment.
  57 template<typename T>
  58 struct DenseMapInfo<T*> {
  59   // The following should hold, but it would require T to be complete:
  60   // static_assert(alignof(T) <= (1 << Log2MaxAlign),
  61   //               "DenseMap does not support pointer keys requiring more than "
  62   //               "Log2MaxAlign bits of alignment");
  63   static constexpr uintptr_t Log2MaxAlign = 12;
  64
  65   static inline T* getEmptyKey() {
  66     uintptr_t Val = static_cast<uintptr_t>(-1);
  67     Val <<= Log2MaxAlign;
  68     return reinterpret_cast<T*>(Val);
  69   }
  70
  71   static inline T* getTombstoneKey() {
  72     uintptr_t Val = static_cast<uintptr_t>(-2);
  73     Val <<= Log2MaxAlign;
  74     return reinterpret_cast<T*>(Val);
  75   }
  76
  77   static unsigned getHashValue(const T *PtrVal) {
  78     return (unsigned((uintptr_t)PtrVal) >> 4) ^
  79            (unsigned((uintptr_t)PtrVal) >> 9);
  80   }
  81
  82   static bool isEqual(const T *LHS, const T *RHS) { return LHS == RHS; }
  83 };
  84
  85 // Provide DenseMapInfo for chars.
  86 template<> struct DenseMapInfo<char> {
  87   static inline char getEmptyKey() { return ~0; }
  88   static inline char getTombstoneKey() { return ~0 - 1; }
  89   static unsigned getHashValue(const char& Val) { return Val * 37U; }
  90
  91   static bool isEqual(const char &LHS, const char &RHS) {
  92     return LHS == RHS;
  93   }
  94 };
  95
  96 // Provide DenseMapInfo for unsigned chars.
  97 template <> struct DenseMapInfo<unsigned char> {
  98   static inline unsigned char getEmptyKey() { return ~0; }
  99   static inline unsigned char getTombstoneKey() { return ~0 - 1; }
 100   static unsigned getHashValue(const unsigned char &Val) { return Val * 37U; }
 101
 102   static bool isEqual(const unsigned char &LHS, const unsigned char &RHS) {
 103     return LHS == RHS;
 104   }
 105 };
 106
 107 // Provide DenseMapInfo for unsigned shorts.
 108 template <> struct DenseMapInfo<unsigned short> {
 109   static inline unsigned short getEmptyKey() { return 0xFFFF; }
 110   static inline unsigned short getTombstoneKey() { return 0xFFFF - 1; }
 111   static unsigned getHashValue(const unsigned short &Val) { return Val * 37U; }
 112
 113   static bool isEqual(const unsigned short &LHS, const unsigned short &RHS) {
 114     return LHS == RHS;
 115   }
 116 };
 117
 118 // Provide DenseMapInfo for unsigned ints.
 119 template<> struct DenseMapInfo<unsigned> {
 120   static inline unsigned getEmptyKey() { return ~0U; }
 121   static inline unsigned getTombstoneKey() { return ~0U - 1; }
 122   static unsigned getHashValue(const unsigned& Val) { return Val * 37U; }
 123
 124   static bool isEqual(const unsigned& LHS, const unsigned& RHS) {
 125     return LHS == RHS;
 126   }
 127 };
 128
 129 // Provide DenseMapInfo for unsigned longs.
 130 template<> struct DenseMapInfo<unsigned long> {
 131   static inline unsigned long getEmptyKey() { return ~0UL; }
 132   static inline unsigned long getTombstoneKey() { return ~0UL - 1L; }
 133
 134   static unsigned getHashValue(const unsigned long& Val) {
 135     return (unsigned)(Val * 37UL);
 136   }
 137
 138   static bool isEqual(const unsigned long& LHS, const unsigned long& RHS) {
 139     return LHS == RHS;
 140   }
 141 };
 142
 143 // Provide DenseMapInfo for unsigned long longs.
 144 template<> struct DenseMapInfo<unsigned long long> {
 145   static inline unsigned long long getEmptyKey() { return ~0ULL; }
 146   static inline unsigned long long getTombstoneKey() { return ~0ULL - 1ULL; }
 147
 148   static unsigned getHashValue(const unsigned long long& Val) {
 149     return (unsigned)(Val * 37ULL);
 150   }
 151
 152   static bool isEqual(const unsigned long long& LHS,
 153                       const unsigned long long& RHS) {
 154     return LHS == RHS;
 155   }
 156 };
 157
 158 // Provide DenseMapInfo for shorts.
 159 template <> struct DenseMapInfo<short> {
 160   static inline short getEmptyKey() { return 0x7FFF; }
 161   static inline short getTombstoneKey() { return -0x7FFF - 1; }
 162   static unsigned getHashValue(const short &Val) { return Val * 37U; }
 163   static bool isEqual(const short &LHS, const short &RHS) { return LHS == RHS; }
 164 };
 165
 166 // Provide DenseMapInfo for ints.
 167 template<> struct DenseMapInfo<int> {
 168   static inline int getEmptyKey() { return 0x7fffffff; }
 169   static inline int getTombstoneKey() { return -0x7fffffff - 1; }
 170   static unsigned getHashValue(const int& Val) { return (unsigned)(Val * 37U); }
 171
 172   static bool isEqual(const int& LHS, const int& RHS) {
 173     return LHS == RHS;
 174   }
 175 };
 176
 177 // Provide DenseMapInfo for longs.
 178 template<> struct DenseMapInfo<long> {
 179   static inline long getEmptyKey() {
 180     return (1UL << (sizeof(long) * 8 - 1)) - 1UL;
 181   }
 182
 183   static inline long getTombstoneKey() { return getEmptyKey() - 1L; }
 184
 185   static unsigned getHashValue(const long& Val) {
 186     return (unsigned)(Val * 37UL);
 187   }
 188
 189   static bool isEqual(const long& LHS, const long& RHS) {
 190     return LHS == RHS;
 191   }
 192 };
 193
 194 // Provide DenseMapInfo for long longs.
 195 template<> struct DenseMapInfo<long long> {
 196   static inline long long getEmptyKey() { return 0x7fffffffffffffffLL; }
 197   static inline long long getTombstoneKey() { return -0x7fffffffffffffffLL-1; }
 198
 199   static unsigned getHashValue(const long long& Val) {
 200     return (unsigned)(Val * 37ULL);
 201   }
 202
 203   static bool isEqual(const long long& LHS,
 204                       const long long& RHS) {
 205     return LHS == RHS;
 206   }
 207 };
 208
 209 // Provide DenseMapInfo for all pairs whose members have info.
 210 template<typename T, typename U>
 211 struct DenseMapInfo<std::pair<T, U>> {
 212   using Pair = std::pair<T, U>;
 213   using FirstInfo = DenseMapInfo<T>;
 214   using SecondInfo = DenseMapInfo<U>;
 215
 216   static inline Pair getEmptyKey() {
 217     return std::make_pair(FirstInfo::getEmptyKey(),
 218                           SecondInfo::getEmptyKey());
 219   }
 220
 221   static inline Pair getTombstoneKey() {
 222     return std::make_pair(FirstInfo::getTombstoneKey(),
 223                           SecondInfo::getTombstoneKey());
 224   }
 225
 226   static unsigned getHashValue(const Pair& PairVal) {
 227     return detail::combineHashValue(FirstInfo::getHashValue(PairVal.first),
 228                                     SecondInfo::getHashValue(PairVal.second));
 229   }
 230
 231   static bool isEqual(const Pair &LHS, const Pair &RHS) {
 232     return FirstInfo::isEqual(LHS.first, RHS.first) &&
 233            SecondInfo::isEqual(LHS.second, RHS.second);
 234   }
 235 };
 236
 237 // Provide DenseMapInfo for all tuples whose members have info.
 238 template <typename... Ts> struct DenseMapInfo<std::tuple<Ts...>> {
 239   using Tuple = std::tuple<Ts...>;
 240
 241   static inline Tuple getEmptyKey() {
 242     return Tuple(DenseMapInfo<Ts>::getEmptyKey()...);
 243   }
 244
 245   static inline Tuple getTombstoneKey() {
 246     return Tuple(DenseMapInfo<Ts>::getTombstoneKey()...);
 247   }
 248
 249   template <unsigned I>
 250   static unsigned getHashValueImpl(const Tuple &values, std::false_type) {
 251     using EltType = typename std::tuple_element<I, Tuple>::type;
 252     std::integral_constant<bool, I + 1 == sizeof...(Ts)> atEnd;
 253     return detail::combineHashValue(
 254         DenseMapInfo<EltType>::getHashValue(std::get<I>(values)),
 255         getHashValueImpl<I + 1>(values, atEnd));
 256   }
 257
 258   template <unsigned I>
 259   static unsigned getHashValueImpl(const Tuple &values, std::true_type) {
 260     return 0;
 261   }
 262
 263   static unsigned getHashValue(const std::tuple<Ts...> &values) {
 264     std::integral_constant<bool, 0 == sizeof...(Ts)> atEnd;
 265     return getHashValueImpl<0>(values, atEnd);
 266   }
 267
 268   template <unsigned I>
 269   static bool isEqualImpl(const Tuple &lhs, const Tuple &rhs, std::false_type) {
 270     using EltType = typename std::tuple_element<I, Tuple>::type;
 271     std::integral_constant<bool, I + 1 == sizeof...(Ts)> atEnd;
 272     return DenseMapInfo<EltType>::isEqual(std::get<I>(lhs), std::get<I>(rhs)) &&
 273            isEqualImpl<I + 1>(lhs, rhs, atEnd);
 274   }
 275
 276   template <unsigned I>
 277   static bool isEqualImpl(const Tuple &lhs, const Tuple &rhs, std::true_type) {
 278     return true;
 279   }
 280
 281   static bool isEqual(const Tuple &lhs, const Tuple &rhs) {
 282     std::integral_constant<bool, 0 == sizeof...(Ts)> atEnd;
 283     return isEqualImpl<0>(lhs, rhs, atEnd);
 284   }
 285 };
 286
 287 // Provide DenseMapInfo for StringRefs.
 288 template <> struct DenseMapInfo<StringRef> {
 289   static inline StringRef getEmptyKey() {
 290     return StringRef(reinterpret_cast<const char *>(~static_cast<uintptr_t>(0)),
 291                      0);
 292   }
 293
 294   static inline StringRef getTombstoneKey() {
 295     return StringRef(reinterpret_cast<const char *>(~static_cast<uintptr_t>(1)),
 296                      0);
 297   }
 298
 299   static unsigned getHashValue(StringRef Val) {
 300     assert(Val.data() != getEmptyKey().data() && "Cannot hash the empty key!");
 301     assert(Val.data() != getTombstoneKey().data() &&
 302            "Cannot hash the tombstone key!");
 303     return (unsigned)(hash_value(Val));
 304   }
 305
 306   static bool isEqual(StringRef LHS, StringRef RHS) {
 307     if (RHS.data() == getEmptyKey().data())
 308       return LHS.data() == getEmptyKey().data();
 309     if (RHS.data() == getTombstoneKey().data())
 310       return LHS.data() == getTombstoneKey().data();
 311     return LHS == RHS;
 312   }
 313 };
 314
 315 // Provide DenseMapInfo for ArrayRefs.
 316 template <typename T> struct DenseMapInfo<ArrayRef<T>> {
 317   static inline ArrayRef<T> getEmptyKey() {
 318     return ArrayRef<T>(reinterpret_cast<const T *>(~static_cast<uintptr_t>(0)),
 319                        size_t(0));
 320   }
 321
 322   static inline ArrayRef<T> getTombstoneKey() {
 323     return ArrayRef<T>(reinterpret_cast<const T *>(~static_cast<uintptr_t>(1)),
 324                        size_t(0));
 325   }
 326
 327   static unsigned getHashValue(ArrayRef<T> Val) {
 328     assert(Val.data() != getEmptyKey().data() && "Cannot hash the empty key!");
 329     assert(Val.data() != getTombstoneKey().data() &&
 330            "Cannot hash the tombstone key!");
 331     return (unsigned)(hash_value(Val));
 332   }
 333
 334   static bool isEqual(ArrayRef<T> LHS, ArrayRef<T> RHS) {
 335     if (RHS.data() == getEmptyKey().data())
 336       return LHS.data() == getEmptyKey().data();
 337     if (RHS.data() == getTombstoneKey().data())
 338       return LHS.data() == getTombstoneKey().data();
 339     return LHS == RHS;
 340   }
 341 };
 342
 343 template <> struct DenseMapInfo<hash_code> {
 344   static inline hash_code getEmptyKey() { return hash_code(-1); }
 345   static inline hash_code getTombstoneKey() { return hash_code(-2); }
 346   static unsigned getHashValue(hash_code val) { return val; }
 347   static bool isEqual(hash_code LHS, hash_code RHS) { return LHS == RHS; }
 348 };
 349
 350 } // end namespace llvm
 351
 352 #endif // LLVM_ADT_DENSEMAPINFO_H