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