include/llvm/ADT/DenseMapInfo.h

   1 //===- llvm/ADT/DenseMapInfo.h - Type traits for DenseMap -------*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file defines DenseMapInfo traits for DenseMap.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #ifndef LLVM_ADT_DENSEMAPINFO_H
  15 #define LLVM_ADT_DENSEMAPINFO_H
  16
  17 #include "llvm/ADT/ArrayRef.h"
  18 #include "llvm/ADT/Hashing.h"
  19 #include "llvm/ADT/StringRef.h"
  20 #include "llvm/Support/PointerLikeTypeTraits.h"
  21 #include "llvm/Support/type_traits.h"
  22
  23 namespace llvm {
  24
  25 template<typename T>
  26 struct DenseMapInfo {
  27   //static inline T getEmptyKey();
  28   //static inline T getTombstoneKey();
  29   //static unsigned getHashValue(const T &Val);
  30   //static bool isEqual(const T &LHS, const T &RHS);
  31 };
  32
  33 // Provide DenseMapInfo for all pointers.
  34 template<typename T>
  35 struct DenseMapInfo<T*> {
  36   static inline T* getEmptyKey() {
  37     uintptr_t Val = static_cast<uintptr_t>(-1);
  38     Val <<= PointerLikeTypeTraits<T*>::NumLowBitsAvailable;
  39     return reinterpret_cast<T*>(Val);
  40   }
  41   static inline T* getTombstoneKey() {
  42     uintptr_t Val = static_cast<uintptr_t>(-2);
  43     Val <<= PointerLikeTypeTraits<T*>::NumLowBitsAvailable;
  44     return reinterpret_cast<T*>(Val);
  45   }
  46   static unsigned getHashValue(const T *PtrVal) {
  47     return (unsigned((uintptr_t)PtrVal) >> 4) ^
  48            (unsigned((uintptr_t)PtrVal) >> 9);
  49   }
  50   static bool isEqual(const T *LHS, const T *RHS) { return LHS == RHS; }
  51 };
  52
  53 // Provide DenseMapInfo for chars.
  54 template<> struct DenseMapInfo<char> {
  55   static inline char getEmptyKey() { return ~0; }
  56   static inline char getTombstoneKey() { return ~0 - 1; }
  57   static unsigned getHashValue(const char& Val) { return Val * 37U; }
  58   static bool isEqual(const char &LHS, const char &RHS) {
  59     return LHS == RHS;
  60   }
  61 };
  62
  63 // Provide DenseMapInfo for unsigned ints.
  64 template<> struct DenseMapInfo<unsigned> {
  65   static inline unsigned getEmptyKey() { return ~0U; }
  66   static inline unsigned getTombstoneKey() { return ~0U - 1; }
  67   static unsigned getHashValue(const unsigned& Val) { return Val * 37U; }
  68   static bool isEqual(const unsigned& LHS, const unsigned& RHS) {
  69     return LHS == RHS;
  70   }
  71 };
  72
  73 // Provide DenseMapInfo for unsigned longs.
  74 template<> struct DenseMapInfo<unsigned long> {
  75   static inline unsigned long getEmptyKey() { return ~0UL; }
  76   static inline unsigned long getTombstoneKey() { return ~0UL - 1L; }
  77   static unsigned getHashValue(const unsigned long& Val) {
  78     return (unsigned)(Val * 37UL);
  79   }
  80   static bool isEqual(const unsigned long& LHS, const unsigned long& RHS) {
  81     return LHS == RHS;
  82   }
  83 };
  84
  85 // Provide DenseMapInfo for unsigned long longs.
  86 template<> struct DenseMapInfo<unsigned long long> {
  87   static inline unsigned long long getEmptyKey() { return ~0ULL; }
  88   static inline unsigned long long getTombstoneKey() { return ~0ULL - 1ULL; }
  89   static unsigned getHashValue(const unsigned long long& Val) {
  90     return (unsigned)(Val * 37ULL);
  91   }
  92   static bool isEqual(const unsigned long long& LHS,
  93                       const unsigned long long& RHS) {
  94     return LHS == RHS;
  95   }
  96 };
  97
  98 // Provide DenseMapInfo for ints.
  99 template<> struct DenseMapInfo<int> {
 100   static inline int getEmptyKey() { return 0x7fffffff; }
 101   static inline int getTombstoneKey() { return -0x7fffffff - 1; }
 102   static unsigned getHashValue(const int& Val) { return (unsigned)(Val * 37U); }
 103   static bool isEqual(const int& LHS, const int& RHS) {
 104     return LHS == RHS;
 105   }
 106 };
 107
 108 // Provide DenseMapInfo for longs.
 109 template<> struct DenseMapInfo<long> {
 110   static inline long getEmptyKey() {
 111     return (1UL << (sizeof(long) * 8 - 1)) - 1UL;
 112   }
 113   static inline long getTombstoneKey() { return getEmptyKey() - 1L; }
 114   static unsigned getHashValue(const long& Val) {
 115     return (unsigned)(Val * 37UL);
 116   }
 117   static bool isEqual(const long& LHS, const long& RHS) {
 118     return LHS == RHS;
 119   }
 120 };
 121
 122 // Provide DenseMapInfo for long longs.
 123 template<> struct DenseMapInfo<long long> {
 124   static inline long long getEmptyKey() { return 0x7fffffffffffffffLL; }
 125   static inline long long getTombstoneKey() { return -0x7fffffffffffffffLL-1; }
 126   static unsigned getHashValue(const long long& Val) {
 127     return (unsigned)(Val * 37ULL);
 128   }
 129   static bool isEqual(const long long& LHS,
 130                       const long long& RHS) {
 131     return LHS == RHS;
 132   }
 133 };
 134
 135 // Provide DenseMapInfo for all pairs whose members have info.
 136 template<typename T, typename U>
 137 struct DenseMapInfo<std::pair<T, U> > {
 138   typedef std::pair<T, U> Pair;
 139   typedef DenseMapInfo<T> FirstInfo;
 140   typedef DenseMapInfo<U> SecondInfo;
 141
 142   static inline Pair getEmptyKey() {
 143     return std::make_pair(FirstInfo::getEmptyKey(),
 144                           SecondInfo::getEmptyKey());
 145   }
 146   static inline Pair getTombstoneKey() {
 147     return std::make_pair(FirstInfo::getTombstoneKey(),
 148                           SecondInfo::getTombstoneKey());
 149   }
 150   static unsigned getHashValue(const Pair& PairVal) {
 151     uint64_t key = (uint64_t)FirstInfo::getHashValue(PairVal.first) << 32
 152           | (uint64_t)SecondInfo::getHashValue(PairVal.second);
 153     key += ~(key << 32);
 154     key ^= (key >> 22);
 155     key += ~(key << 13);
 156     key ^= (key >> 8);
 157     key += (key << 3);
 158     key ^= (key >> 15);
 159     key += ~(key << 27);
 160     key ^= (key >> 31);
 161     return (unsigned)key;
 162   }
 163   static bool isEqual(const Pair &LHS, const Pair &RHS) {
 164     return FirstInfo::isEqual(LHS.first, RHS.first) &&
 165            SecondInfo::isEqual(LHS.second, RHS.second);
 166   }
 167 };
 168
 169 // Provide DenseMapInfo for StringRefs.
 170 template <> struct DenseMapInfo<StringRef> {
 171   static inline StringRef getEmptyKey() {
 172     return StringRef(reinterpret_cast<const char *>(~static_cast<uintptr_t>(0)),
 173                      0);
 174   }
 175   static inline StringRef getTombstoneKey() {
 176     return StringRef(reinterpret_cast<const char *>(~static_cast<uintptr_t>(1)),
 177                      0);
 178   }
 179   static unsigned getHashValue(StringRef Val) {
 180     assert(Val.data() != getEmptyKey().data() && "Cannot hash the empty key!");
 181     assert(Val.data() != getTombstoneKey().data() &&
 182            "Cannot hash the tombstone key!");
 183     return (unsigned)(hash_value(Val));
 184   }
 185   static bool isEqual(StringRef LHS, StringRef RHS) {
 186     if (RHS.data() == getEmptyKey().data())
 187       return LHS.data() == getEmptyKey().data();
 188     if (RHS.data() == getTombstoneKey().data())
 189       return LHS.data() == getTombstoneKey().data();
 190     return LHS == RHS;
 191   }
 192 };
 193
 194 // Provide DenseMapInfo for ArrayRefs.
 195 template <typename T> struct DenseMapInfo<ArrayRef<T>> {
 196   static inline ArrayRef<T> getEmptyKey() {
 197     return ArrayRef<T>(reinterpret_cast<const T *>(~static_cast<uintptr_t>(0)),
 198                        size_t(0));
 199   }
 200   static inline ArrayRef<T> getTombstoneKey() {
 201     return ArrayRef<T>(reinterpret_cast<const T *>(~static_cast<uintptr_t>(1)),
 202                        size_t(0));
 203   }
 204   static unsigned getHashValue(ArrayRef<T> Val) {
 205     assert(Val.data() != getEmptyKey().data() && "Cannot hash the empty key!");
 206     assert(Val.data() != getTombstoneKey().data() &&
 207            "Cannot hash the tombstone key!");
 208     return (unsigned)(hash_value(Val));
 209   }
 210   static bool isEqual(ArrayRef<T> LHS, ArrayRef<T> RHS) {
 211     if (RHS.data() == getEmptyKey().data())
 212       return LHS.data() == getEmptyKey().data();
 213     if (RHS.data() == getTombstoneKey().data())
 214       return LHS.data() == getTombstoneKey().data();
 215     return LHS == RHS;
 216   }
 217 };
 218
 219 } // end namespace llvm
 220
 221 #endif