DenseMapInfo.h revision e1182b5599f11778286f027eb536d7ddf7657eda
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 <utility> 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 //static bool isPod() 29}; 30 31// Provide DenseMapInfo for all pointers. 32template<typename T> 33struct DenseMapInfo<T*> { 34 static inline T* getEmptyKey() { 35 intptr_t Val = -1; 36 Val <<= PointerLikeTypeTraits<T*>::NumLowBitsAvailable; 37 return reinterpret_cast<T*>(Val); 38 } 39 static inline T* getTombstoneKey() { 40 intptr_t Val = -2; 41 Val <<= PointerLikeTypeTraits<T*>::NumLowBitsAvailable; 42 return reinterpret_cast<T*>(Val); 43 } 44 static unsigned getHashValue(const T *PtrVal) { 45 return (unsigned((uintptr_t)PtrVal) >> 4) ^ 46 (unsigned((uintptr_t)PtrVal) >> 9); 47 } 48 static bool isEqual(const T *LHS, const T *RHS) { return LHS == RHS; } 49 static bool isPod() { return true; } 50}; 51 52// Provide DenseMapInfo for chars. 53template<> struct DenseMapInfo<char> { 54 static inline char getEmptyKey() { return ~0; } 55 static inline char getTombstoneKey() { return ~0 - 1; } 56 static unsigned getHashValue(const char& Val) { return Val * 37; } 57 static bool isPod() { return true; } 58 static bool isEqual(const char &LHS, const char &RHS) { 59 return LHS == RHS; 60 } 61}; 62 63// Provide DenseMapInfo for unsigned ints. 64template<> struct DenseMapInfo<unsigned> { 65 static inline unsigned getEmptyKey() { return ~0; } 66 static inline unsigned getTombstoneKey() { return ~0 - 1; } 67 static unsigned getHashValue(const unsigned& Val) { return Val * 37; } 68 static bool isPod() { return true; } 69 static bool isEqual(const unsigned& LHS, const unsigned& RHS) { 70 return LHS == RHS; 71 } 72}; 73 74// Provide DenseMapInfo for unsigned longs. 75template<> struct DenseMapInfo<unsigned long> { 76 static inline unsigned long getEmptyKey() { return ~0L; } 77 static inline unsigned long getTombstoneKey() { return ~0L - 1L; } 78 static unsigned getHashValue(const unsigned long& Val) { 79 return (unsigned)(Val * 37L); 80 } 81 static bool isPod() { return true; } 82 static bool isEqual(const unsigned long& LHS, const unsigned long& RHS) { 83 return LHS == RHS; 84 } 85}; 86 87// Provide DenseMapInfo for unsigned long longs. 88template<> struct DenseMapInfo<unsigned long long> { 89 static inline unsigned long long getEmptyKey() { return ~0LL; } 90 static inline unsigned long long getTombstoneKey() { return ~0LL - 1LL; } 91 static unsigned getHashValue(const unsigned long long& Val) { 92 return (unsigned)(Val * 37LL); 93 } 94 static bool isPod() { return true; } 95 static bool isEqual(const unsigned long long& LHS, 96 const unsigned long long& RHS) { 97 return LHS == RHS; 98 } 99}; 100 101// Provide DenseMapInfo for all pairs whose members have info. 102template<typename T, typename U> 103struct DenseMapInfo<std::pair<T, U> > { 104 typedef std::pair<T, U> Pair; 105 typedef DenseMapInfo<T> FirstInfo; 106 typedef DenseMapInfo<U> SecondInfo; 107 108 static inline Pair getEmptyKey() { 109 return std::make_pair(FirstInfo::getEmptyKey(), 110 SecondInfo::getEmptyKey()); 111 } 112 static inline Pair getTombstoneKey() { 113 return std::make_pair(FirstInfo::getTombstoneKey(), 114 SecondInfo::getEmptyKey()); 115 } 116 static unsigned getHashValue(const Pair& PairVal) { 117 uint64_t key = (uint64_t)FirstInfo::getHashValue(PairVal.first) << 32 118 | (uint64_t)SecondInfo::getHashValue(PairVal.second); 119 key += ~(key << 32); 120 key ^= (key >> 22); 121 key += ~(key << 13); 122 key ^= (key >> 8); 123 key += (key << 3); 124 key ^= (key >> 15); 125 key += ~(key << 27); 126 key ^= (key >> 31); 127 return (unsigned)key; 128 } 129 static bool isEqual(const Pair& LHS, const Pair& RHS) { return LHS == RHS; } 130 static bool isPod() { return FirstInfo::isPod() && SecondInfo::isPod(); } 131}; 132 133} // end namespace llvm 134 135#endif 136