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 "llvm/Support/PointerLikeTypeTraits.h"
  20 #include "llvm/Support/ScalableSize.h"
  21 #include <cassert>
  22 #include <cstddef>
  23 #include <cstdint>
  24 #include <utility>
  25
  26 namespace llvm {
  27
  28 template<typename T>
  29 struct DenseMapInfo {
  30   //static inline T getEmptyKey();
  31   //static inline T getTombstoneKey();
  32   //static unsigned getHashValue(const T &Val);
  33   //static bool isEqual(const T &LHS, const T &RHS);
  34 };
  35
  36 // Provide DenseMapInfo for all pointers.
  37 template<typename T>
  38 struct DenseMapInfo<T*> {
  39   static inline T* getEmptyKey() {
  40     uintptr_t Val = static_cast<uintptr_t>(-1);
  41     Val <<= PointerLikeTypeTraits<T*>::NumLowBitsAvailable;
  42     return reinterpret_cast<T*>(Val);
  43   }
  44
  45   static inline T* getTombstoneKey() {
  46     uintptr_t Val = static_cast<uintptr_t>(-2);
  47     Val <<= PointerLikeTypeTraits<T*>::NumLowBitsAvailable;
  48     return reinterpret_cast<T*>(Val);
  49   }
  50
  51   static unsigned getHashValue(const T *PtrVal) {
  52     return (unsigned((uintptr_t)PtrVal) >> 4) ^
  53            (unsigned((uintptr_t)PtrVal) >> 9);
  54   }
  55
  56   static bool isEqual(const T *LHS, const T *RHS) { return LHS == RHS; }
  57 };
  58
  59 // Provide DenseMapInfo for chars.
  60 template<> struct DenseMapInfo<char> {
  61   static inline char getEmptyKey() { return ~0; }
  62   static inline char getTombstoneKey() { return ~0 - 1; }
  63   static unsigned getHashValue(const char& Val) { return Val * 37U; }
  64
  65   static bool isEqual(const char &LHS, const char &RHS) {
  66     return LHS == RHS;
  67   }
  68 };
  69
  70 // Provide DenseMapInfo for unsigned shorts.
  71 template <> struct DenseMapInfo<unsigned short> {
  72   static inline unsigned short getEmptyKey() { return 0xFFFF; }
  73   static inline unsigned short getTombstoneKey() { return 0xFFFF - 1; }
  74   static unsigned getHashValue(const unsigned short &Val) { return Val * 37U; }
  75
  76   static bool isEqual(const unsigned short &LHS, const unsigned short &RHS) {
  77     return LHS == RHS;
  78   }
  79 };
  80
  81 // Provide DenseMapInfo for unsigned ints.
  82 template<> struct DenseMapInfo<unsigned> {
  83   static inline unsigned getEmptyKey() { return ~0U; }
  84   static inline unsigned getTombstoneKey() { return ~0U - 1; }
  85   static unsigned getHashValue(const unsigned& Val) { return Val * 37U; }
  86
  87   static bool isEqual(const unsigned& LHS, const unsigned& RHS) {
  88     return LHS == RHS;
  89   }
  90 };
  91
  92 // Provide DenseMapInfo for unsigned longs.
  93 template<> struct DenseMapInfo<unsigned long> {
  94   static inline unsigned long getEmptyKey() { return ~0UL; }
  95   static inline unsigned long getTombstoneKey() { return ~0UL - 1L; }
  96
  97   static unsigned getHashValue(const unsigned long& Val) {
  98     return (unsigned)(Val * 37UL);
  99   }
 100
 101   static bool isEqual(const unsigned long& LHS, const unsigned long& RHS) {
 102     return LHS == RHS;
 103   }
 104 };
 105
 106 // Provide DenseMapInfo for unsigned long longs.
 107 template<> struct DenseMapInfo<unsigned long long> {
 108   static inline unsigned long long getEmptyKey() { return ~0ULL; }
 109   static inline unsigned long long getTombstoneKey() { return ~0ULL - 1ULL; }
 110
 111   static unsigned getHashValue(const unsigned long long& Val) {
 112     return (unsigned)(Val * 37ULL);
 113   }
 114
 115   static bool isEqual(const unsigned long long& LHS,
 116                       const unsigned long long& RHS) {
 117     return LHS == RHS;
 118   }
 119 };
 120
 121 // Provide DenseMapInfo for shorts.
 122 template <> struct DenseMapInfo<short> {
 123   static inline short getEmptyKey() { return 0x7FFF; }
 124   static inline short getTombstoneKey() { return -0x7FFF - 1; }
 125   static unsigned getHashValue(const short &Val) { return Val * 37U; }
 126   static bool isEqual(const short &LHS, const short &RHS) { return LHS == RHS; }
 127 };
 128
 129 // Provide DenseMapInfo for ints.
 130 template<> struct DenseMapInfo<int> {
 131   static inline int getEmptyKey() { return 0x7fffffff; }
 132   static inline int getTombstoneKey() { return -0x7fffffff - 1; }
 133   static unsigned getHashValue(const int& Val) { return (unsigned)(Val * 37U); }
 134
 135   static bool isEqual(const int& LHS, const int& RHS) {
 136     return LHS == RHS;
 137   }
 138 };
 139
 140 // Provide DenseMapInfo for longs.
 141 template<> struct DenseMapInfo<long> {
 142   static inline long getEmptyKey() {
 143     return (1UL << (sizeof(long) * 8 - 1)) - 1UL;
 144   }
 145
 146   static inline long getTombstoneKey() { return getEmptyKey() - 1L; }
 147
 148   static unsigned getHashValue(const long& Val) {
 149     return (unsigned)(Val * 37UL);
 150   }
 151
 152   static bool isEqual(const long& LHS, const long& RHS) {
 153     return LHS == RHS;
 154   }
 155 };
 156
 157 // Provide DenseMapInfo for long longs.
 158 template<> struct DenseMapInfo<long long> {
 159   static inline long long getEmptyKey() { return 0x7fffffffffffffffLL; }
 160   static inline long long getTombstoneKey() { return -0x7fffffffffffffffLL-1; }
 161
 162   static unsigned getHashValue(const long long& Val) {
 163     return (unsigned)(Val * 37ULL);
 164   }
 165
 166   static bool isEqual(const long long& LHS,
 167                       const long long& RHS) {
 168     return LHS == RHS;
 169   }
 170 };
 171
 172 // Provide DenseMapInfo for all pairs whose members have info.
 173 template<typename T, typename U>
 174 struct DenseMapInfo<std::pair<T, U>> {
 175   using Pair = std::pair<T, U>;
 176   using FirstInfo = DenseMapInfo<T>;
 177   using SecondInfo = DenseMapInfo<U>;
 178
 179   static inline Pair getEmptyKey() {
 180     return std::make_pair(FirstInfo::getEmptyKey(),
 181                           SecondInfo::getEmptyKey());
 182   }
 183
 184   static inline Pair getTombstoneKey() {
 185     return std::make_pair(FirstInfo::getTombstoneKey(),
 186                           SecondInfo::getTombstoneKey());
 187   }
 188
 189   static unsigned getHashValue(const Pair& PairVal) {
 190     uint64_t key = (uint64_t)FirstInfo::getHashValue(PairVal.first) << 32
 191           | (uint64_t)SecondInfo::getHashValue(PairVal.second);
 192     key += ~(key << 32);
 193     key ^= (key >> 22);
 194     key += ~(key << 13);
 195     key ^= (key >> 8);
 196     key += (key << 3);
 197     key ^= (key >> 15);
 198     key += ~(key << 27);
 199     key ^= (key >> 31);
 200     return (unsigned)key;
 201   }
 202
 203   static bool isEqual(const Pair &LHS, const Pair &RHS) {
 204     return FirstInfo::isEqual(LHS.first, RHS.first) &&
 205            SecondInfo::isEqual(LHS.second, RHS.second);
 206   }
 207 };
 208
 209 // Provide DenseMapInfo for StringRefs.
 210 template <> struct DenseMapInfo<StringRef> {
 211   static inline StringRef getEmptyKey() {
 212     return StringRef(reinterpret_cast<const char *>(~static_cast<uintptr_t>(0)),
 213                      0);
 214   }
 215
 216   static inline StringRef getTombstoneKey() {
 217     return StringRef(reinterpret_cast<const char *>(~static_cast<uintptr_t>(1)),
 218                      0);
 219   }
 220
 221   static unsigned getHashValue(StringRef Val) {
 222     assert(Val.data() != getEmptyKey().data() && "Cannot hash the empty key!");
 223     assert(Val.data() != getTombstoneKey().data() &&
 224            "Cannot hash the tombstone key!");
 225     return (unsigned)(hash_value(Val));
 226   }
 227
 228   static bool isEqual(StringRef LHS, StringRef RHS) {
 229     if (RHS.data() == getEmptyKey().data())
 230       return LHS.data() == getEmptyKey().data();
 231     if (RHS.data() == getTombstoneKey().data())
 232       return LHS.data() == getTombstoneKey().data();
 233     return LHS == RHS;
 234   }
 235 };
 236
 237 // Provide DenseMapInfo for ArrayRefs.
 238 template <typename T> struct DenseMapInfo<ArrayRef<T>> {
 239   static inline ArrayRef<T> getEmptyKey() {
 240     return ArrayRef<T>(reinterpret_cast<const T *>(~static_cast<uintptr_t>(0)),
 241                        size_t(0));
 242   }
 243
 244   static inline ArrayRef<T> getTombstoneKey() {
 245     return ArrayRef<T>(reinterpret_cast<const T *>(~static_cast<uintptr_t>(1)),
 246                        size_t(0));
 247   }
 248
 249   static unsigned getHashValue(ArrayRef<T> Val) {
 250     assert(Val.data() != getEmptyKey().data() && "Cannot hash the empty key!");
 251     assert(Val.data() != getTombstoneKey().data() &&
 252            "Cannot hash the tombstone key!");
 253     return (unsigned)(hash_value(Val));
 254   }
 255
 256   static bool isEqual(ArrayRef<T> LHS, ArrayRef<T> RHS) {
 257     if (RHS.data() == getEmptyKey().data())
 258       return LHS.data() == getEmptyKey().data();
 259     if (RHS.data() == getTombstoneKey().data())
 260       return LHS.data() == getTombstoneKey().data();
 261     return LHS == RHS;
 262   }
 263 };
 264
 265 template <> struct DenseMapInfo<hash_code> {
 266   static inline hash_code getEmptyKey() { return hash_code(-1); }
 267   static inline hash_code getTombstoneKey() { return hash_code(-2); }
 268   static unsigned getHashValue(hash_code val) { return val; }
 269   static bool isEqual(hash_code LHS, hash_code RHS) { return LHS == RHS; }
 270 };
 271
 272 template <> struct DenseMapInfo<ElementCount> {
 273   static inline ElementCount getEmptyKey() { return {~0U, true}; }
 274   static inline ElementCount getTombstoneKey() { return {~0U - 1, false}; }
 275   static unsigned getHashValue(const ElementCount& EltCnt) {
 276     if (EltCnt.Scalable)
 277       return (EltCnt.Min * 37U) - 1U;
 278
 279     return EltCnt.Min * 37U;
 280   }
 281
 282   static bool isEqual(const ElementCount& LHS, const ElementCount& RHS) {
 283     return LHS == RHS;
 284   }
 285 };
 286
 287 } // end namespace llvm
 288
 289 #endif // LLVM_ADT_DENSEMAPINFO_H