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