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