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 20namespace llvm { 21 22template<typename T> 23struct 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. 31template<typename T> 32struct DenseMapInfo<T*> { 33 static inline T* getEmptyKey() { 34 uintptr_t Val = static_cast<uintptr_t>(-1); 35 Val <<= PointerLikeTypeTraits<T*>::NumLowBitsAvailable; 36 return reinterpret_cast<T*>(Val); 37 } 38 static inline T* getTombstoneKey() { 39 uintptr_t Val = static_cast<uintptr_t>(-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. 51template<> 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. 61template<> struct DenseMapInfo<unsigned> { 62 static inline unsigned getEmptyKey() { return ~0U; } 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. 71template<> 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. 83template<> 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. 96template<> 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. 106template<> struct DenseMapInfo<long> { 107 static inline long getEmptyKey() { 108 return (1UL << (sizeof(long) * 8 - 1)) - 1UL; 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. 120template<> 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. 133template<typename T, typename U> 134struct 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