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