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     return 0 == strcmp(LHS, RHS);
  79   }
  80 };
  81
  82 // Provide DenseMapInfo for chars.
  83 template<> struct DenseMapInfo<char> {
  84   static inline char getEmptyKey() { return ~0; }
  85   static inline char getTombstoneKey() { return ~0 - 1; }
  86   static unsigned getHashValue(const char& Val) { return Val * 37U; }
  87   static bool isEqual(const char &LHS, const char &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   static bool isEqual(const unsigned& LHS, const unsigned& RHS) {
  98     return LHS == RHS;
  99   }
 100 };
 101
 102 // Provide DenseMapInfo for unsigned longs.
 103 template<> struct DenseMapInfo<unsigned long> {
 104   static inline unsigned long getEmptyKey() { return ~0UL; }
 105   static inline unsigned long getTombstoneKey() { return ~0UL - 1L; }
 106   static unsigned getHashValue(const unsigned long& Val) {
 107     return (unsigned)(Val * 37UL);
 108   }
 109   static bool isEqual(const unsigned long& LHS, const unsigned long& RHS) {
 110     return LHS == RHS;
 111   }
 112 };
 113
 114 // Provide DenseMapInfo for unsigned long longs.
 115 template<> struct DenseMapInfo<unsigned long long> {
 116   static inline unsigned long long getEmptyKey() { return ~0ULL; }
 117   static inline unsigned long long getTombstoneKey() { return ~0ULL - 1ULL; }
 118   static unsigned getHashValue(const unsigned long long& Val) {
 119     return (unsigned)(Val * 37ULL);
 120   }
 121   static bool isEqual(const unsigned long long& LHS,
 122                       const unsigned long long& RHS) {
 123     return LHS == RHS;
 124   }
 125 };
 126
 127 // Provide DenseMapInfo for ints.
 128 template<> struct DenseMapInfo<int> {
 129   static inline int getEmptyKey() { return 0x7fffffff; }
 130   static inline int getTombstoneKey() { return -0x7fffffff - 1; }
 131   static unsigned getHashValue(const int& Val) { return (unsigned)(Val * 37U); }
 132   static bool isEqual(const int& LHS, const int& RHS) {
 133     return LHS == RHS;
 134   }
 135 };
 136
 137 // Provide DenseMapInfo for longs.
 138 template<> struct DenseMapInfo<long> {
 139   static inline long getEmptyKey() {
 140     return (1UL << (sizeof(long) * 8 - 1)) - 1UL;
 141   }
 142   static inline long getTombstoneKey() { return getEmptyKey() - 1L; }
 143   static unsigned getHashValue(const long& Val) {
 144     return (unsigned)(Val * 37UL);
 145   }
 146   static bool isEqual(const long& LHS, const long& RHS) {
 147     return LHS == RHS;
 148   }
 149 };
 150
 151 // Provide DenseMapInfo for long longs.
 152 template<> struct DenseMapInfo<long long> {
 153   static inline long long getEmptyKey() { return 0x7fffffffffffffffLL; }
 154   static inline long long getTombstoneKey() { return -0x7fffffffffffffffLL-1; }
 155   static unsigned getHashValue(const long long& Val) {
 156     return (unsigned)(Val * 37ULL);
 157   }
 158   static bool isEqual(const long long& LHS,
 159                       const long long& RHS) {
 160     return LHS == RHS;
 161   }
 162 };
 163
 164 // Provide DenseMapInfo for all pairs whose members have info.
 165 template<typename T, typename U>
 166 struct DenseMapInfo<std::pair<T, U> > {
 167   typedef std::pair<T, U> Pair;
 168   typedef DenseMapInfo<T> FirstInfo;
 169   typedef DenseMapInfo<U> SecondInfo;
 170
 171   static inline Pair getEmptyKey() {
 172     return std::make_pair(FirstInfo::getEmptyKey(),
 173                           SecondInfo::getEmptyKey());
 174   }
 175   static inline Pair getTombstoneKey() {
 176     return std::make_pair(FirstInfo::getTombstoneKey(),
 177                           SecondInfo::getTombstoneKey());
 178   }
 179   static unsigned getHashValue(const Pair& PairVal) {
 180     uint64_t key = (uint64_t)FirstInfo::getHashValue(PairVal.first) << 32
 181           | (uint64_t)SecondInfo::getHashValue(PairVal.second);
 182     key += ~(key << 32);
 183     key ^= (key >> 22);
 184     key += ~(key << 13);
 185     key ^= (key >> 8);
 186     key += (key << 3);
 187     key ^= (key >> 15);
 188     key += ~(key << 27);
 189     key ^= (key >> 31);
 190     return (unsigned)key;
 191   }
 192   static bool isEqual(const Pair &LHS, const Pair &RHS) {
 193     return FirstInfo::isEqual(LHS.first, RHS.first) &&
 194            SecondInfo::isEqual(LHS.second, RHS.second);
 195   }
 196 };
 197
 198 } // end namespace objc
 199
 200 #endif