runtime/llvm-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 // Taken from llvmCore-3425.0.31.
  15
  16 #ifndef LLVM_ADT_DENSEMAPINFO_H
  17 #define LLVM_ADT_DENSEMAPINFO_H
  18
  19 #include "objc-private.h"
  20 #include "llvm-type_traits.h"
  21
  22 namespace objc {
  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     return reinterpret_cast<T*>(Val);
  38   }
  39   static inline T* getTombstoneKey() {
  40     uintptr_t Val = static_cast<uintptr_t>(-2);
  41     return reinterpret_cast<T*>(Val);
  42   }
  43   static unsigned getHashValue(const T *PtrVal) {
  44       return ptr_hash((uintptr_t)PtrVal);
  45   }
  46   static bool isEqual(const T *LHS, const T *RHS) { return LHS == RHS; }
  47 };
  48
  49 // Provide DenseMapInfo for disguised pointers.
  50 template<typename T>
  51 struct DenseMapInfo<DisguisedPtr<T>> {
  52   static inline DisguisedPtr<T> getEmptyKey() {
  53     return DisguisedPtr<T>((T*)(uintptr_t)-1);
  54   }
  55   static inline DisguisedPtr<T> getTombstoneKey() {
  56     return DisguisedPtr<T>((T*)(uintptr_t)-2);
  57   }
  58   static unsigned getHashValue(const T *PtrVal) {
  59       return ptr_hash((uintptr_t)PtrVal);
  60   }
  61   static bool isEqual(const DisguisedPtr<T> &LHS, const DisguisedPtr<T> &RHS) {
  62       return LHS == RHS;
  63   }
  64 };
  65
  66 // Provide DenseMapInfo for cstrings.
  67 template<> struct DenseMapInfo<const char*> {
  68   static inline const char* getEmptyKey() {
  69     return reinterpret_cast<const char *>((intptr_t)-1);
  70   }
  71   static inline const char* getTombstoneKey() {
  72     return reinterpret_cast<const char *>((intptr_t)-2);
  73   }
  74   static unsigned getHashValue(const char* const &Val) {
  75     return _objc_strhash(Val);
  76   }
  77   static bool isEqual(const char* const &LHS, const char* const &RHS) {
  78     if (LHS == RHS) {
  79       return true;
  80     }
  81     if (LHS == getEmptyKey() || RHS == getEmptyKey()) {
  82       return false;
  83     }
  84     if (LHS == getTombstoneKey() || RHS == getTombstoneKey()) {
  85       return false;
  86     }
  87     return 0 == strcmp(LHS, RHS);
  88   }
  89 };
  90
  91 // Provide DenseMapInfo for chars.
  92 template<> struct DenseMapInfo<char> {
  93   static inline char getEmptyKey() { return ~0; }
  94   static inline char getTombstoneKey() { return ~0 - 1; }
  95   static unsigned getHashValue(const char& Val) { return Val * 37U; }
  96   static bool isEqual(const char &LHS, const char &RHS) {
  97     return LHS == RHS;
  98   }
  99 };
 100
 101 // Provide DenseMapInfo for unsigned ints.
 102 template<> struct DenseMapInfo<unsigned> {
 103   static inline unsigned getEmptyKey() { return ~0U; }
 104   static inline unsigned getTombstoneKey() { return ~0U - 1; }
 105   static unsigned getHashValue(const unsigned& Val) { return Val * 37U; }
 106   static bool isEqual(const unsigned& LHS, const unsigned& RHS) {
 107     return LHS == RHS;
 108   }
 109 };
 110
 111 // Provide DenseMapInfo for unsigned longs.
 112 template<> struct DenseMapInfo<unsigned long> {
 113   static inline unsigned long getEmptyKey() { return ~0UL; }
 114   static inline unsigned long getTombstoneKey() { return ~0UL - 1L; }
 115   static unsigned getHashValue(const unsigned long& Val) {
 116     return (unsigned)(Val * 37UL);
 117   }
 118   static bool isEqual(const unsigned long& LHS, const unsigned long& RHS) {
 119     return LHS == RHS;
 120   }
 121 };
 122
 123 // Provide DenseMapInfo for unsigned long longs.
 124 template<> struct DenseMapInfo<unsigned long long> {
 125   static inline unsigned long long getEmptyKey() { return ~0ULL; }
 126   static inline unsigned long long getTombstoneKey() { return ~0ULL - 1ULL; }
 127   static unsigned getHashValue(const unsigned long long& Val) {
 128     return (unsigned)(Val * 37ULL);
 129   }
 130   static bool isEqual(const unsigned long long& LHS,
 131                       const unsigned long long& RHS) {
 132     return LHS == RHS;
 133   }
 134 };
 135
 136 // Provide DenseMapInfo for ints.
 137 template<> struct DenseMapInfo<int> {
 138   static inline int getEmptyKey() { return 0x7fffffff; }
 139   static inline int getTombstoneKey() { return -0x7fffffff - 1; }
 140   static unsigned getHashValue(const int& Val) { return (unsigned)(Val * 37U); }
 141   static bool isEqual(const int& LHS, const int& RHS) {
 142     return LHS == RHS;
 143   }
 144 };
 145
 146 // Provide DenseMapInfo for longs.
 147 template<> struct DenseMapInfo<long> {
 148   static inline long getEmptyKey() {
 149     return (1UL << (sizeof(long) * 8 - 1)) - 1UL;
 150   }
 151   static inline long getTombstoneKey() { return getEmptyKey() - 1L; }
 152   static unsigned getHashValue(const long& Val) {
 153     return (unsigned)(Val * 37UL);
 154   }
 155   static bool isEqual(const long& LHS, const long& RHS) {
 156     return LHS == RHS;
 157   }
 158 };
 159
 160 // Provide DenseMapInfo for long longs.
 161 template<> struct DenseMapInfo<long long> {
 162   static inline long long getEmptyKey() { return 0x7fffffffffffffffLL; }
 163   static inline long long getTombstoneKey() { return -0x7fffffffffffffffLL-1; }
 164   static unsigned getHashValue(const long long& Val) {
 165     return (unsigned)(Val * 37ULL);
 166   }
 167   static bool isEqual(const long long& LHS,
 168                       const long long& RHS) {
 169     return LHS == RHS;
 170   }
 171 };
 172
 173 // Provide DenseMapInfo for all pairs whose members have info.
 174 template<typename T, typename U>
 175 struct DenseMapInfo<std::pair<T, U> > {
 176   typedef std::pair<T, U> Pair;
 177   typedef DenseMapInfo<T> FirstInfo;
 178   typedef DenseMapInfo<U> SecondInfo;
 179
 180   static inline Pair getEmptyKey() {
 181     return std::make_pair(FirstInfo::getEmptyKey(),
 182                           SecondInfo::getEmptyKey());
 183   }
 184   static inline Pair getTombstoneKey() {
 185     return std::make_pair(FirstInfo::getTombstoneKey(),
 186                           SecondInfo::getTombstoneKey());
 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   static bool isEqual(const Pair &LHS, const Pair &RHS) {
 202     return FirstInfo::isEqual(LHS.first, RHS.first) &&
 203            SecondInfo::isEqual(LHS.second, RHS.second);
 204   }
 205 };
 206
 207 template<typename T>
 208 struct DenseMapValueInfo {
 209     static inline bool isPurgeable(const T &value) {
 210         return false;
 211     }
 212 };
 213
 214 } // end namespace objc
 215
 216 #endif