DenseMapInfo.h revision 3e6fe5ec17217169cd95ee86515955f7726db008
1197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch//===- llvm/ADT/DenseMapInfo.h - Type traits for DenseMap -------*- C++ -*-===// 2197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch// 3197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch// The LLVM Compiler Infrastructure 4197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch// 5197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch// This file is distributed under the University of Illinois Open Source 6197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch// License. See LICENSE.TXT for details. 7197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch// 8197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch//===----------------------------------------------------------------------===// 9197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch// 10197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch// This file defines DenseMapInfo traits for DenseMap. 11197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch// 127242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci//===----------------------------------------------------------------------===// 13197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch 14197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch#ifndef LLVM_ADT_DENSEMAPINFO_H 15197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch#define LLVM_ADT_DENSEMAPINFO_H 16197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch 17197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch#include "llvm/Support/PointerLikeTypeTraits.h" 18197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch#include "llvm/Support/type_traits.h" 19197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch 20197021e6b966cfb06891637935ef33fff06433d1Ben Murdochnamespace llvm { 21197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch 22197021e6b966cfb06891637935ef33fff06433d1Ben Murdochtemplate<typename T> 23197021e6b966cfb06891637935ef33fff06433d1Ben Murdochstruct DenseMapInfo { 24197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch //static inline T getEmptyKey(); 25197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch //static inline T getTombstoneKey(); 26197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch //static unsigned getHashValue(const T &Val); 27197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch //static bool isEqual(const T &LHS, const T &RHS); 28197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch}; 29197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch 30197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch// Provide DenseMapInfo for all pointers. 31197021e6b966cfb06891637935ef33fff06433d1Ben Murdochtemplate<typename T> 32197021e6b966cfb06891637935ef33fff06433d1Ben Murdochstruct DenseMapInfo<T*> { 33197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch static inline T* getEmptyKey() { 34197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch intptr_t Val = -1; 35197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch Val <<= PointerLikeTypeTraits<T*>::NumLowBitsAvailable; 36197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch return reinterpret_cast<T*>(Val); 37197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch } 38197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch static inline T* getTombstoneKey() { 39197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch intptr_t Val = -2; 40197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch Val <<= PointerLikeTypeTraits<T*>::NumLowBitsAvailable; 41197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch return reinterpret_cast<T*>(Val); 42197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch } 43197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch static unsigned getHashValue(const T *PtrVal) { 44197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch return (unsigned((uintptr_t)PtrVal) >> 4) ^ 45197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch (unsigned((uintptr_t)PtrVal) >> 9); 46197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch } 47197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch static bool isEqual(const T *LHS, const T *RHS) { return LHS == RHS; } 48197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch}; 49197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch 50197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch// Provide DenseMapInfo for chars. 51197021e6b966cfb06891637935ef33fff06433d1Ben Murdochtemplate<> 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 * 37; } 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 ~0; } 63 static inline unsigned getTombstoneKey() { return ~0U - 1; } 64 static unsigned getHashValue(const unsigned& Val) { return Val * 37; } 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 * 37); } 100 static bool isEqual(const int& LHS, const int& RHS) { 101 return LHS == RHS; 102 } 103}; 104 105// Provide DenseMapInfo for long longs. 106template<> struct DenseMapInfo<long long> { 107 static inline long long getEmptyKey() { return 0x7fffffffffffffffLL; } 108 static inline long long getTombstoneKey() { return -0x7fffffffffffffffLL-1; } 109 static unsigned getHashValue(const long long& Val) { 110 return (unsigned)(Val * 37LL); 111 } 112 static bool isEqual(const long long& LHS, 113 const long long& RHS) { 114 return LHS == RHS; 115 } 116}; 117 118// Provide DenseMapInfo for all pairs whose members have info. 119template<typename T, typename U> 120struct DenseMapInfo<std::pair<T, U> > { 121 typedef std::pair<T, U> Pair; 122 typedef DenseMapInfo<T> FirstInfo; 123 typedef DenseMapInfo<U> SecondInfo; 124 125 static inline Pair getEmptyKey() { 126 return std::make_pair(FirstInfo::getEmptyKey(), 127 SecondInfo::getEmptyKey()); 128 } 129 static inline Pair getTombstoneKey() { 130 return std::make_pair(FirstInfo::getTombstoneKey(), 131 SecondInfo::getEmptyKey()); 132 } 133 static unsigned getHashValue(const Pair& PairVal) { 134 uint64_t key = (uint64_t)FirstInfo::getHashValue(PairVal.first) << 32 135 | (uint64_t)SecondInfo::getHashValue(PairVal.second); 136 key += ~(key << 32); 137 key ^= (key >> 22); 138 key += ~(key << 13); 139 key ^= (key >> 8); 140 key += (key << 3); 141 key ^= (key >> 15); 142 key += ~(key << 27); 143 key ^= (key >> 31); 144 return (unsigned)key; 145 } 146 static bool isEqual(const Pair& LHS, const Pair& RHS) { return LHS == RHS; } 147}; 148 149} // end namespace llvm 150 151#endif 152