LLVM API Documentation
00001 //===- llvm/ADT/DenseMapInfo.h - Type traits for DenseMap -------*- C++ -*-===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file is distributed under the University of Illinois Open Source 00006 // License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This file defines DenseMapInfo traits for DenseMap. 00011 // 00012 //===----------------------------------------------------------------------===// 00013 00014 #ifndef LLVM_ADT_DENSEMAPINFO_H 00015 #define LLVM_ADT_DENSEMAPINFO_H 00016 00017 #include "llvm/Support/PointerLikeTypeTraits.h" 00018 #include <utility> 00019 00020 namespace llvm { 00021 00022 template<typename T> 00023 struct DenseMapInfo { 00024 //static inline T getEmptyKey(); 00025 //static inline T getTombstoneKey(); 00026 //static unsigned getHashValue(const T &Val); 00027 //static bool isEqual(const T &LHS, const T &RHS); 00028 //static bool isPod() 00029 }; 00030 00031 // Provide DenseMapInfo for all pointers. 00032 template<typename T> 00033 struct DenseMapInfo<T*> { 00034 static inline T* getEmptyKey() { 00035 intptr_t Val = -1; 00036 Val <<= PointerLikeTypeTraits<T*>::NumLowBitsAvailable; 00037 return reinterpret_cast<T*>(Val); 00038 } 00039 static inline T* getTombstoneKey() { 00040 intptr_t Val = -2; 00041 Val <<= PointerLikeTypeTraits<T*>::NumLowBitsAvailable; 00042 return reinterpret_cast<T*>(Val); 00043 } 00044 static unsigned getHashValue(const T *PtrVal) { 00045 return (unsigned((uintptr_t)PtrVal) >> 4) ^ 00046 (unsigned((uintptr_t)PtrVal) >> 9); 00047 } 00048 static bool isEqual(const T *LHS, const T *RHS) { return LHS == RHS; } 00049 static bool isPod() { return true; } 00050 }; 00051 00052 // Provide DenseMapInfo for chars. 00053 template<> struct DenseMapInfo<char> { 00054 static inline char getEmptyKey() { return ~0; } 00055 static inline char getTombstoneKey() { return ~0 - 1; } 00056 static unsigned getHashValue(const char& Val) { return Val * 37; } 00057 static bool isPod() { return true; } 00058 static bool isEqual(const char &LHS, const char &RHS) { 00059 return LHS == RHS; 00060 } 00061 }; 00062 00063 // Provide DenseMapInfo for unsigned ints. 00064 template<> struct DenseMapInfo<unsigned> { 00065 static inline unsigned getEmptyKey() { return ~0; } 00066 static inline unsigned getTombstoneKey() { return ~0 - 1; } 00067 static unsigned getHashValue(const unsigned& Val) { return Val * 37; } 00068 static bool isPod() { return true; } 00069 static bool isEqual(const unsigned& LHS, const unsigned& RHS) { 00070 return LHS == RHS; 00071 } 00072 }; 00073 00074 // Provide DenseMapInfo for unsigned longs. 00075 template<> struct DenseMapInfo<unsigned long> { 00076 static inline unsigned long getEmptyKey() { return ~0L; } 00077 static inline unsigned long getTombstoneKey() { return ~0L - 1L; } 00078 static unsigned getHashValue(const unsigned long& Val) { 00079 return (unsigned)(Val * 37L); 00080 } 00081 static bool isPod() { return true; } 00082 static bool isEqual(const unsigned long& LHS, const unsigned long& RHS) { 00083 return LHS == RHS; 00084 } 00085 }; 00086 00087 // Provide DenseMapInfo for all pairs whose members have info. 00088 template<typename T, typename U> 00089 struct DenseMapInfo<std::pair<T, U> > { 00090 typedef std::pair<T, U> Pair; 00091 typedef DenseMapInfo<T> FirstInfo; 00092 typedef DenseMapInfo<U> SecondInfo; 00093 00094 static inline Pair getEmptyKey() { 00095 return std::make_pair(FirstInfo::getEmptyKey(), 00096 SecondInfo::getEmptyKey()); 00097 } 00098 static inline Pair getTombstoneKey() { 00099 return std::make_pair(FirstInfo::getTombstoneKey(), 00100 SecondInfo::getEmptyKey()); 00101 } 00102 static unsigned getHashValue(const Pair& PairVal) { 00103 uint64_t key = (uint64_t)FirstInfo::getHashValue(PairVal.first) << 32 00104 | (uint64_t)SecondInfo::getHashValue(PairVal.second); 00105 key += ~(key << 32); 00106 key ^= (key >> 22); 00107 key += ~(key << 13); 00108 key ^= (key >> 8); 00109 key += (key << 3); 00110 key ^= (key >> 15); 00111 key += ~(key << 27); 00112 key ^= (key >> 31); 00113 return (unsigned)key; 00114 } 00115 static bool isEqual(const Pair& LHS, const Pair& RHS) { return LHS == RHS; } 00116 static bool isPod() { return FirstInfo::isPod() && SecondInfo::isPod(); } 00117 }; 00118 00119 } // end namespace llvm 00120 00121 #endif