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