DenseMapInfo.h revision 4bbf4ee1491637c247e195e19e3e4a8ee5ad72fa
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 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. 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 * 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 all pairs whose members have info. 96template<typename T, typename U> 97struct DenseMapInfo<std::pair<T, U> > { 98 typedef std::pair<T, U> Pair; 99 typedef DenseMapInfo<T> FirstInfo; 100 typedef DenseMapInfo<U> SecondInfo; 101 102 static inline Pair getEmptyKey() { 103 return std::make_pair(FirstInfo::getEmptyKey(), 104 SecondInfo::getEmptyKey()); 105 } 106 static inline Pair getTombstoneKey() { 107 return std::make_pair(FirstInfo::getTombstoneKey(), 108 SecondInfo::getEmptyKey()); 109 } 110 static unsigned getHashValue(const Pair& PairVal) { 111 uint64_t key = (uint64_t)FirstInfo::getHashValue(PairVal.first) << 32 112 | (uint64_t)SecondInfo::getHashValue(PairVal.second); 113 key += ~(key << 32); 114 key ^= (key >> 22); 115 key += ~(key << 13); 116 key ^= (key >> 8); 117 key += (key << 3); 118 key ^= (key >> 15); 119 key += ~(key << 27); 120 key ^= (key >> 31); 121 return (unsigned)key; 122 } 123 static bool isEqual(const Pair& LHS, const Pair& RHS) { return LHS == RHS; } 124}; 125 126} // end namespace llvm 127 128#endif 129