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 (unsigned((uintptr_t)PtrVal) >> 4) ^
  45            (unsigned((uintptr_t)PtrVal) >> 9);
  46   }
  47   static bool isEqual(const T *LHS, const T *RHS) { return LHS == RHS; }
  48 };
  49
  50 // Provide DenseMapInfo for cstrings.
  51 template<> struct DenseMapInfo<const char*> {
  52   static inline const char* getEmptyKey() {
  53     return reinterpret_cast<const char *>((intptr_t)-1);
  54   }
  55   static inline const char* getTombstoneKey() {
  56     return reinterpret_cast<const char *>((intptr_t)-2);
  57   }
  58   static unsigned getHashValue(const char* const &Val) {
  59     return _objc_strhash(Val);
  60   }
  61   static bool isEqual(const char* const &LHS, const char* const &RHS) {
  62     return 0 == strcmp(LHS, RHS);
  63   }
  64 };
  65
  66 // Provide DenseMapInfo for chars.
  67 template<> struct DenseMapInfo<char> {
  68   static inline char getEmptyKey() { return ~0; }
  69   static inline char getTombstoneKey() { return ~0 - 1; }
  70   static unsigned getHashValue(const char& Val) { return Val * 37U; }
  71   static bool isEqual(const char &LHS, const char &RHS) {
  72     return LHS == RHS;
  73   }
  74 };
  75
  76 // Provide DenseMapInfo for unsigned ints.
  77 template<> struct DenseMapInfo<unsigned> {
  78   static inline unsigned getEmptyKey() { return ~0U; }
  79   static inline unsigned getTombstoneKey() { return ~0U - 1; }
  80   static unsigned getHashValue(const unsigned& Val) { return Val * 37U; }
  81   static bool isEqual(const unsigned& LHS, const unsigned& RHS) {
  82     return LHS == RHS;
  83   }
  84 };
  85
  86 // Provide DenseMapInfo for unsigned longs.
  87 template<> struct DenseMapInfo<unsigned long> {
  88   static inline unsigned long getEmptyKey() { return ~0UL; }
  89   static inline unsigned long getTombstoneKey() { return ~0UL - 1L; }
  90   static unsigned getHashValue(const unsigned long& Val) {
  91     return (unsigned)(Val * 37UL);
  92   }
  93   static bool isEqual(const unsigned long& LHS, const unsigned long& RHS) {
  94     return LHS == RHS;
  95   }
  96 };
  97
  98 // Provide DenseMapInfo for unsigned long longs.
  99 template<> struct DenseMapInfo<unsigned long long> {
 100   static inline unsigned long long getEmptyKey() { return ~0ULL; }
 101   static inline unsigned long long getTombstoneKey() { return ~0ULL - 1ULL; }
 102   static unsigned getHashValue(const unsigned long long& Val) {
 103     return (unsigned)(Val * 37ULL);
 104   }
 105   static bool isEqual(const unsigned long long& LHS,
 106                       const unsigned long long& RHS) {
 107     return LHS == RHS;
 108   }
 109 };
 110
 111 // Provide DenseMapInfo for ints.
 112 template<> struct DenseMapInfo<int> {
 113   static inline int getEmptyKey() { return 0x7fffffff; }
 114   static inline int getTombstoneKey() { return -0x7fffffff - 1; }
 115   static unsigned getHashValue(const int& Val) { return (unsigned)(Val * 37U); }
 116   static bool isEqual(const int& LHS, const int& RHS) {
 117     return LHS == RHS;
 118   }
 119 };
 120
 121 // Provide DenseMapInfo for longs.
 122 template<> struct DenseMapInfo<long> {
 123   static inline long getEmptyKey() {
 124     return (1UL << (sizeof(long) * 8 - 1)) - 1UL;
 125   }
 126   static inline long getTombstoneKey() { return getEmptyKey() - 1L; }
 127   static unsigned getHashValue(const long& Val) {
 128     return (unsigned)(Val * 37UL);
 129   }
 130   static bool isEqual(const long& LHS, const long& RHS) {
 131     return LHS == RHS;
 132   }
 133 };
 134
 135 // Provide DenseMapInfo for long longs.
 136 template<> struct DenseMapInfo<long long> {
 137   static inline long long getEmptyKey() { return 0x7fffffffffffffffLL; }
 138   static inline long long getTombstoneKey() { return -0x7fffffffffffffffLL-1; }
 139   static unsigned getHashValue(const long long& Val) {
 140     return (unsigned)(Val * 37ULL);
 141   }
 142   static bool isEqual(const long long& LHS,
 143                       const long long& RHS) {
 144     return LHS == RHS;
 145   }
 146 };
 147
 148 // Provide DenseMapInfo for all pairs whose members have info.
 149 template<typename T, typename U>
 150 struct DenseMapInfo<std::pair<T, U> > {
 151   typedef std::pair<T, U> Pair;
 152   typedef DenseMapInfo<T> FirstInfo;
 153   typedef DenseMapInfo<U> SecondInfo;
 154
 155   static inline Pair getEmptyKey() {
 156     return std::make_pair(FirstInfo::getEmptyKey(),
 157                           SecondInfo::getEmptyKey());
 158   }
 159   static inline Pair getTombstoneKey() {
 160     return std::make_pair(FirstInfo::getTombstoneKey(),
 161                           SecondInfo::getTombstoneKey());
 162   }
 163   static unsigned getHashValue(const Pair& PairVal) {
 164     uint64_t key = (uint64_t)FirstInfo::getHashValue(PairVal.first) << 32
 165           | (uint64_t)SecondInfo::getHashValue(PairVal.second);
 166     key += ~(key << 32);
 167     key ^= (key >> 22);
 168     key += ~(key << 13);
 169     key ^= (key >> 8);
 170     key += (key << 3);
 171     key ^= (key >> 15);
 172     key += ~(key << 27);
 173     key ^= (key >> 31);
 174     return (unsigned)key;
 175   }
 176   static bool isEqual(const Pair &LHS, const Pair &RHS) {
 177     return FirstInfo::isEqual(LHS.first, RHS.first) &&
 178            SecondInfo::isEqual(LHS.second, RHS.second);
 179   }
 180 };
 181
 182 } // end namespace objc
 183
 184 #endif