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