llvm/ADT/DenseMapInfo.h

0001 //===- llvm/ADT/DenseMapInfo.h - Type traits for DenseMap -------*- C++ -*-===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008 ///
0009 /// \file
0010 /// This file defines DenseMapInfo traits for DenseMap.
0011 ///
0012 //===----------------------------------------------------------------------===//
0013
0014 #ifndef LLVM_ADT_DENSEMAPINFO_H
0015 #define LLVM_ADT_DENSEMAPINFO_H
0016
0017 #include <cassert>
0018 #include <cstddef>
0019 #include <cstdint>
0020 #include <tuple>
0021 #include <type_traits>
0022 #include <utility>
0023
0024 namespace llvm {
0025
0026 namespace densemap::detail {
0027 // A bit mixer with very low latency using one multiplications and one
0028 // xor-shift. The constant is from splitmix64.
0029 inline uint64_t mix(uint64_t x) {
0030   x *= 0xbf58476d1ce4e5b9u;
0031   x ^= x >> 31;
0032   return x;
0033 }
0034 } // namespace densemap::detail
0035
0036 namespace detail {
0037
0038 /// Simplistic combination of 32-bit hash values into 32-bit hash values.
0039 inline unsigned combineHashValue(unsigned a, unsigned b) {
0040   uint64_t x = (uint64_t)a << 32 | (uint64_t)b;
0041   return (unsigned)densemap::detail::mix(x);
0042 }
0043
0044 } // end namespace detail
0045
0046 /// An information struct used to provide DenseMap with the various necessary
0047 /// components for a given value type `T`. `Enable` is an optional additional
0048 /// parameter that is used to support SFINAE (generally using std::enable_if_t)
0049 /// in derived DenseMapInfo specializations; in non-SFINAE use cases this should
0050 /// just be `void`.
0051 template<typename T, typename Enable = void>
0052 struct DenseMapInfo {
0053   //static inline T getEmptyKey();
0054   //static inline T getTombstoneKey();
0055   //static unsigned getHashValue(const T &Val);
0056   //static bool isEqual(const T &LHS, const T &RHS);
0057 };
0058
0059 // Provide DenseMapInfo for all pointers. Come up with sentinel pointer values
0060 // that are aligned to alignof(T) bytes, but try to avoid requiring T to be
0061 // complete. This allows clients to instantiate DenseMap<T*, ...> with forward
0062 // declared key types. Assume that no pointer key type requires more than 4096
0063 // bytes of alignment.
0064 template<typename T>
0065 struct DenseMapInfo<T*> {
0066   // The following should hold, but it would require T to be complete:
0067   // static_assert(alignof(T) <= (1 << Log2MaxAlign),
0068   //               "DenseMap does not support pointer keys requiring more than "
0069   //               "Log2MaxAlign bits of alignment");
0070   static constexpr uintptr_t Log2MaxAlign = 12;
0071
0072   static inline T* getEmptyKey() {
0073     uintptr_t Val = static_cast<uintptr_t>(-1);
0074     Val <<= Log2MaxAlign;
0075     return reinterpret_cast<T*>(Val);
0076   }
0077
0078   static inline T* getTombstoneKey() {
0079     uintptr_t Val = static_cast<uintptr_t>(-2);
0080     Val <<= Log2MaxAlign;
0081     return reinterpret_cast<T*>(Val);
0082   }
0083
0084   static unsigned getHashValue(const T *PtrVal) {
0085     return (unsigned((uintptr_t)PtrVal) >> 4) ^
0086            (unsigned((uintptr_t)PtrVal) >> 9);
0087   }
0088
0089   static bool isEqual(const T *LHS, const T *RHS) { return LHS == RHS; }
0090 };
0091
0092 // Provide DenseMapInfo for chars.
0093 template<> struct DenseMapInfo<char> {
0094   static inline char getEmptyKey() { return ~0; }
0095   static inline char getTombstoneKey() { return ~0 - 1; }
0096   static unsigned getHashValue(const char& Val) { return Val * 37U; }
0097
0098   static bool isEqual(const char &LHS, const char &RHS) {
0099     return LHS == RHS;
0100   }
0101 };
0102
0103 // Provide DenseMapInfo for unsigned chars.
0104 template <> struct DenseMapInfo<unsigned char> {
0105   static inline unsigned char getEmptyKey() { return ~0; }
0106   static inline unsigned char getTombstoneKey() { return ~0 - 1; }
0107   static unsigned getHashValue(const unsigned char &Val) { return Val * 37U; }
0108
0109   static bool isEqual(const unsigned char &LHS, const unsigned char &RHS) {
0110     return LHS == RHS;
0111   }
0112 };
0113
0114 // Provide DenseMapInfo for unsigned shorts.
0115 template <> struct DenseMapInfo<unsigned short> {
0116   static inline unsigned short getEmptyKey() { return 0xFFFF; }
0117   static inline unsigned short getTombstoneKey() { return 0xFFFF - 1; }
0118   static unsigned getHashValue(const unsigned short &Val) { return Val * 37U; }
0119
0120   static bool isEqual(const unsigned short &LHS, const unsigned short &RHS) {
0121     return LHS == RHS;
0122   }
0123 };
0124
0125 // Provide DenseMapInfo for unsigned ints.
0126 template<> struct DenseMapInfo<unsigned> {
0127   static inline unsigned getEmptyKey() { return ~0U; }
0128   static inline unsigned getTombstoneKey() { return ~0U - 1; }
0129   static unsigned getHashValue(const unsigned& Val) { return Val * 37U; }
0130
0131   static bool isEqual(const unsigned& LHS, const unsigned& RHS) {
0132     return LHS == RHS;
0133   }
0134 };
0135
0136 // Provide DenseMapInfo for unsigned longs.
0137 template<> struct DenseMapInfo<unsigned long> {
0138   static inline unsigned long getEmptyKey() { return ~0UL; }
0139   static inline unsigned long getTombstoneKey() { return ~0UL - 1L; }
0140
0141   static unsigned getHashValue(const unsigned long& Val) {
0142     if constexpr (sizeof(Val) == 4)
0143       return DenseMapInfo<unsigned>::getHashValue(Val);
0144     else
0145       return densemap::detail::mix(Val);
0146   }
0147
0148   static bool isEqual(const unsigned long& LHS, const unsigned long& RHS) {
0149     return LHS == RHS;
0150   }
0151 };
0152
0153 // Provide DenseMapInfo for unsigned long longs.
0154 template<> struct DenseMapInfo<unsigned long long> {
0155   static inline unsigned long long getEmptyKey() { return ~0ULL; }
0156   static inline unsigned long long getTombstoneKey() { return ~0ULL - 1ULL; }
0157
0158   static unsigned getHashValue(const unsigned long long& Val) {
0159     return densemap::detail::mix(Val);
0160   }
0161
0162   static bool isEqual(const unsigned long long& LHS,
0163                       const unsigned long long& RHS) {
0164     return LHS == RHS;
0165   }
0166 };
0167
0168 // Provide DenseMapInfo for shorts.
0169 template <> struct DenseMapInfo<short> {
0170   static inline short getEmptyKey() { return 0x7FFF; }
0171   static inline short getTombstoneKey() { return -0x7FFF - 1; }
0172   static unsigned getHashValue(const short &Val) { return Val * 37U; }
0173   static bool isEqual(const short &LHS, const short &RHS) { return LHS == RHS; }
0174 };
0175
0176 // Provide DenseMapInfo for ints.
0177 template<> struct DenseMapInfo<int> {
0178   static inline int getEmptyKey() { return 0x7fffffff; }
0179   static inline int getTombstoneKey() { return -0x7fffffff - 1; }
0180   static unsigned getHashValue(const int& Val) { return (unsigned)(Val * 37U); }
0181
0182   static bool isEqual(const int& LHS, const int& RHS) {
0183     return LHS == RHS;
0184   }
0185 };
0186
0187 // Provide DenseMapInfo for longs.
0188 template<> struct DenseMapInfo<long> {
0189   static inline long getEmptyKey() {
0190     return (1UL << (sizeof(long) * 8 - 1)) - 1UL;
0191   }
0192
0193   static inline long getTombstoneKey() { return getEmptyKey() - 1L; }
0194
0195   static unsigned getHashValue(const long& Val) {
0196     return (unsigned)(Val * 37UL);
0197   }
0198
0199   static bool isEqual(const long& LHS, const long& RHS) {
0200     return LHS == RHS;
0201   }
0202 };
0203
0204 // Provide DenseMapInfo for long longs.
0205 template<> struct DenseMapInfo<long long> {
0206   static inline long long getEmptyKey() { return 0x7fffffffffffffffLL; }
0207   static inline long long getTombstoneKey() { return -0x7fffffffffffffffLL-1; }
0208
0209   static unsigned getHashValue(const long long& Val) {
0210     return (unsigned)(Val * 37ULL);
0211   }
0212
0213   static bool isEqual(const long long& LHS,
0214                       const long long& RHS) {
0215     return LHS == RHS;
0216   }
0217 };
0218
0219 // Provide DenseMapInfo for all pairs whose members have info.
0220 template<typename T, typename U>
0221 struct DenseMapInfo<std::pair<T, U>> {
0222   using Pair = std::pair<T, U>;
0223   using FirstInfo = DenseMapInfo<T>;
0224   using SecondInfo = DenseMapInfo<U>;
0225
0226   static inline Pair getEmptyKey() {
0227     return std::make_pair(FirstInfo::getEmptyKey(),
0228                           SecondInfo::getEmptyKey());
0229   }
0230
0231   static inline Pair getTombstoneKey() {
0232     return std::make_pair(FirstInfo::getTombstoneKey(),
0233                           SecondInfo::getTombstoneKey());
0234   }
0235
0236   static unsigned getHashValue(const Pair& PairVal) {
0237     return detail::combineHashValue(FirstInfo::getHashValue(PairVal.first),
0238                                     SecondInfo::getHashValue(PairVal.second));
0239   }
0240
0241   // Expose an additional function intended to be used by other
0242   // specializations of DenseMapInfo without needing to know how
0243   // to combine hash values manually
0244   static unsigned getHashValuePiecewise(const T &First, const U &Second) {
0245     return detail::combineHashValue(FirstInfo::getHashValue(First),
0246                                     SecondInfo::getHashValue(Second));
0247   }
0248
0249   static bool isEqual(const Pair &LHS, const Pair &RHS) {
0250     return FirstInfo::isEqual(LHS.first, RHS.first) &&
0251            SecondInfo::isEqual(LHS.second, RHS.second);
0252   }
0253 };
0254
0255 // Provide DenseMapInfo for all tuples whose members have info.
0256 template <typename... Ts> struct DenseMapInfo<std::tuple<Ts...>> {
0257   using Tuple = std::tuple<Ts...>;
0258
0259   static inline Tuple getEmptyKey() {
0260     return Tuple(DenseMapInfo<Ts>::getEmptyKey()...);
0261   }
0262
0263   static inline Tuple getTombstoneKey() {
0264     return Tuple(DenseMapInfo<Ts>::getTombstoneKey()...);
0265   }
0266
0267   template <unsigned I>
0268   static unsigned getHashValueImpl(const Tuple &values, std::false_type) {
0269     using EltType = std::tuple_element_t<I, Tuple>;
0270     std::integral_constant<bool, I + 1 == sizeof...(Ts)> atEnd;
0271     return detail::combineHashValue(
0272         DenseMapInfo<EltType>::getHashValue(std::get<I>(values)),
0273         getHashValueImpl<I + 1>(values, atEnd));
0274   }
0275
0276   template <unsigned I>
0277   static unsigned getHashValueImpl(const Tuple &, std::true_type) {
0278     return 0;
0279   }
0280
0281   static unsigned getHashValue(const std::tuple<Ts...> &values) {
0282     std::integral_constant<bool, 0 == sizeof...(Ts)> atEnd;
0283     return getHashValueImpl<0>(values, atEnd);
0284   }
0285
0286   template <unsigned I>
0287   static bool isEqualImpl(const Tuple &lhs, const Tuple &rhs, std::false_type) {
0288     using EltType = std::tuple_element_t<I, Tuple>;
0289     std::integral_constant<bool, I + 1 == sizeof...(Ts)> atEnd;
0290     return DenseMapInfo<EltType>::isEqual(std::get<I>(lhs), std::get<I>(rhs)) &&
0291            isEqualImpl<I + 1>(lhs, rhs, atEnd);
0292   }
0293
0294   template <unsigned I>
0295   static bool isEqualImpl(const Tuple &, const Tuple &, std::true_type) {
0296     return true;
0297   }
0298
0299   static bool isEqual(const Tuple &lhs, const Tuple &rhs) {
0300     std::integral_constant<bool, 0 == sizeof...(Ts)> atEnd;
0301     return isEqualImpl<0>(lhs, rhs, atEnd);
0302   }
0303 };
0304
0305 // Provide DenseMapInfo for enum classes.
0306 template <typename Enum>
0307 struct DenseMapInfo<Enum, std::enable_if_t<std::is_enum_v<Enum>>> {
0308   using UnderlyingType = std::underlying_type_t<Enum>;
0309   using Info = DenseMapInfo<UnderlyingType>;
0310
0311   static Enum getEmptyKey() { return static_cast<Enum>(Info::getEmptyKey()); }
0312
0313   static Enum getTombstoneKey() {
0314     return static_cast<Enum>(Info::getTombstoneKey());
0315   }
0316
0317   static unsigned getHashValue(const Enum &Val) {
0318     return Info::getHashValue(static_cast<UnderlyingType>(Val));
0319   }
0320
0321   static bool isEqual(const Enum &LHS, const Enum &RHS) { return LHS == RHS; }
0322 };
0323 } // end namespace llvm
0324
0325 #endif // LLVM_ADT_DENSEMAPINFO_H