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 22namespace objc { 23 24template<typename T> 25struct 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. 33template<typename T> 34struct 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. 51template<> 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. 67template<> 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. 77template<> 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. 87template<> 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. 99template<> 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. 112template<> 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. 122template<> 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. 136template<> 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. 149template<typename T, typename U> 150struct 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 185