1fb3af88ba75898896714d49c608b8daa4f106636Dan Gohman//===- llvm/ADT/DenseMapInfo.h - Type traits for DenseMap -------*- C++ -*-===// 2fb3af88ba75898896714d49c608b8daa4f106636Dan Gohman// 3fb3af88ba75898896714d49c608b8daa4f106636Dan Gohman// The LLVM Compiler Infrastructure 4fb3af88ba75898896714d49c608b8daa4f106636Dan Gohman// 5fb3af88ba75898896714d49c608b8daa4f106636Dan Gohman// This file is distributed under the University of Illinois Open Source 6fb3af88ba75898896714d49c608b8daa4f106636Dan Gohman// License. See LICENSE.TXT for details. 7fb3af88ba75898896714d49c608b8daa4f106636Dan Gohman// 8fb3af88ba75898896714d49c608b8daa4f106636Dan Gohman//===----------------------------------------------------------------------===// 9fb3af88ba75898896714d49c608b8daa4f106636Dan Gohman// 10fb3af88ba75898896714d49c608b8daa4f106636Dan Gohman// This file defines DenseMapInfo traits for DenseMap. 11fb3af88ba75898896714d49c608b8daa4f106636Dan Gohman// 12fb3af88ba75898896714d49c608b8daa4f106636Dan Gohman//===----------------------------------------------------------------------===// 13fb3af88ba75898896714d49c608b8daa4f106636Dan Gohman 14fb3af88ba75898896714d49c608b8daa4f106636Dan Gohman#ifndef LLVM_ADT_DENSEMAPINFO_H 15fb3af88ba75898896714d49c608b8daa4f106636Dan Gohman#define LLVM_ADT_DENSEMAPINFO_H 16fb3af88ba75898896714d49c608b8daa4f106636Dan Gohman 17fb3af88ba75898896714d49c608b8daa4f106636Dan Gohman#include "llvm/Support/PointerLikeTypeTraits.h" 184bbf4ee1491637c247e195e19e3e4a8ee5ad72faChris Lattner#include "llvm/Support/type_traits.h" 19fb3af88ba75898896714d49c608b8daa4f106636Dan Gohman 20fb3af88ba75898896714d49c608b8daa4f106636Dan Gohmannamespace llvm { 21fb3af88ba75898896714d49c608b8daa4f106636Dan Gohman 22fb3af88ba75898896714d49c608b8daa4f106636Dan Gohmantemplate<typename T> 23fb3af88ba75898896714d49c608b8daa4f106636Dan Gohmanstruct DenseMapInfo { 24fb3af88ba75898896714d49c608b8daa4f106636Dan Gohman //static inline T getEmptyKey(); 25fb3af88ba75898896714d49c608b8daa4f106636Dan Gohman //static inline T getTombstoneKey(); 26fb3af88ba75898896714d49c608b8daa4f106636Dan Gohman //static unsigned getHashValue(const T &Val); 27fb3af88ba75898896714d49c608b8daa4f106636Dan Gohman //static bool isEqual(const T &LHS, const T &RHS); 28fb3af88ba75898896714d49c608b8daa4f106636Dan Gohman}; 29fb3af88ba75898896714d49c608b8daa4f106636Dan Gohman 30fb3af88ba75898896714d49c608b8daa4f106636Dan Gohman// Provide DenseMapInfo for all pointers. 31fb3af88ba75898896714d49c608b8daa4f106636Dan Gohmantemplate<typename T> 32fb3af88ba75898896714d49c608b8daa4f106636Dan Gohmanstruct DenseMapInfo<T*> { 33fb3af88ba75898896714d49c608b8daa4f106636Dan Gohman static inline T* getEmptyKey() { 341144af3c9b4da48cd581156e05b24261c8de366aRichard Smith uintptr_t Val = static_cast<uintptr_t>(-1); 35fb3af88ba75898896714d49c608b8daa4f106636Dan Gohman Val <<= PointerLikeTypeTraits<T*>::NumLowBitsAvailable; 36fb3af88ba75898896714d49c608b8daa4f106636Dan Gohman return reinterpret_cast<T*>(Val); 37fb3af88ba75898896714d49c608b8daa4f106636Dan Gohman } 38fb3af88ba75898896714d49c608b8daa4f106636Dan Gohman static inline T* getTombstoneKey() { 391144af3c9b4da48cd581156e05b24261c8de366aRichard Smith uintptr_t Val = static_cast<uintptr_t>(-2); 40fb3af88ba75898896714d49c608b8daa4f106636Dan Gohman Val <<= PointerLikeTypeTraits<T*>::NumLowBitsAvailable; 41fb3af88ba75898896714d49c608b8daa4f106636Dan Gohman return reinterpret_cast<T*>(Val); 42fb3af88ba75898896714d49c608b8daa4f106636Dan Gohman } 43fb3af88ba75898896714d49c608b8daa4f106636Dan Gohman static unsigned getHashValue(const T *PtrVal) { 44fb3af88ba75898896714d49c608b8daa4f106636Dan Gohman return (unsigned((uintptr_t)PtrVal) >> 4) ^ 45fb3af88ba75898896714d49c608b8daa4f106636Dan Gohman (unsigned((uintptr_t)PtrVal) >> 9); 46fb3af88ba75898896714d49c608b8daa4f106636Dan Gohman } 47fb3af88ba75898896714d49c608b8daa4f106636Dan Gohman static bool isEqual(const T *LHS, const T *RHS) { return LHS == RHS; } 48fb3af88ba75898896714d49c608b8daa4f106636Dan Gohman}; 49fb3af88ba75898896714d49c608b8daa4f106636Dan Gohman 50fb3af88ba75898896714d49c608b8daa4f106636Dan Gohman// Provide DenseMapInfo for chars. 51fb3af88ba75898896714d49c608b8daa4f106636Dan Gohmantemplate<> struct DenseMapInfo<char> { 52fb3af88ba75898896714d49c608b8daa4f106636Dan Gohman static inline char getEmptyKey() { return ~0; } 53fb3af88ba75898896714d49c608b8daa4f106636Dan Gohman static inline char getTombstoneKey() { return ~0 - 1; } 54a046d2ff9a6ef1a5ecf1068d9fce714db7557c2aEli Friedman static unsigned getHashValue(const char& Val) { return Val * 37U; } 55fb3af88ba75898896714d49c608b8daa4f106636Dan Gohman static bool isEqual(const char &LHS, const char &RHS) { 56fb3af88ba75898896714d49c608b8daa4f106636Dan Gohman return LHS == RHS; 57fb3af88ba75898896714d49c608b8daa4f106636Dan Gohman } 58fb3af88ba75898896714d49c608b8daa4f106636Dan Gohman}; 59fb3af88ba75898896714d49c608b8daa4f106636Dan Gohman 60fb3af88ba75898896714d49c608b8daa4f106636Dan Gohman// Provide DenseMapInfo for unsigned ints. 61fb3af88ba75898896714d49c608b8daa4f106636Dan Gohmantemplate<> struct DenseMapInfo<unsigned> { 62b83a67e1e3fe210bd99a82eccd3dc5b1b44f1503Ahmed Charles static inline unsigned getEmptyKey() { return ~0U; } 638ecbe8d974e1c1f778207b87dcdf887060f5c699Duncan Sands static inline unsigned getTombstoneKey() { return ~0U - 1; } 64a046d2ff9a6ef1a5ecf1068d9fce714db7557c2aEli Friedman static unsigned getHashValue(const unsigned& Val) { return Val * 37U; } 65fb3af88ba75898896714d49c608b8daa4f106636Dan Gohman static bool isEqual(const unsigned& LHS, const unsigned& RHS) { 668ecbe8d974e1c1f778207b87dcdf887060f5c699Duncan Sands return LHS == RHS; 67fb3af88ba75898896714d49c608b8daa4f106636Dan Gohman } 68fb3af88ba75898896714d49c608b8daa4f106636Dan Gohman}; 69fb3af88ba75898896714d49c608b8daa4f106636Dan Gohman 70fb3af88ba75898896714d49c608b8daa4f106636Dan Gohman// Provide DenseMapInfo for unsigned longs. 71fb3af88ba75898896714d49c608b8daa4f106636Dan Gohmantemplate<> struct DenseMapInfo<unsigned long> { 728ecbe8d974e1c1f778207b87dcdf887060f5c699Duncan Sands static inline unsigned long getEmptyKey() { return ~0UL; } 738ecbe8d974e1c1f778207b87dcdf887060f5c699Duncan Sands static inline unsigned long getTombstoneKey() { return ~0UL - 1L; } 74fb3af88ba75898896714d49c608b8daa4f106636Dan Gohman static unsigned getHashValue(const unsigned long& Val) { 753a8ff4c8b67d12689cb5fc9c0e9606f4530e6f41Eric Christopher return (unsigned)(Val * 37UL); 76fb3af88ba75898896714d49c608b8daa4f106636Dan Gohman } 77fb3af88ba75898896714d49c608b8daa4f106636Dan Gohman static bool isEqual(const unsigned long& LHS, const unsigned long& RHS) { 788ecbe8d974e1c1f778207b87dcdf887060f5c699Duncan Sands return LHS == RHS; 79fb3af88ba75898896714d49c608b8daa4f106636Dan Gohman } 80fb3af88ba75898896714d49c608b8daa4f106636Dan Gohman}; 81fb3af88ba75898896714d49c608b8daa4f106636Dan Gohman 82e1182b5599f11778286f027eb536d7ddf7657edaMike Stump// Provide DenseMapInfo for unsigned long longs. 83e1182b5599f11778286f027eb536d7ddf7657edaMike Stumptemplate<> struct DenseMapInfo<unsigned long long> { 848ecbe8d974e1c1f778207b87dcdf887060f5c699Duncan Sands static inline unsigned long long getEmptyKey() { return ~0ULL; } 858ecbe8d974e1c1f778207b87dcdf887060f5c699Duncan Sands static inline unsigned long long getTombstoneKey() { return ~0ULL - 1ULL; } 86e1182b5599f11778286f027eb536d7ddf7657edaMike Stump static unsigned getHashValue(const unsigned long long& Val) { 873a8ff4c8b67d12689cb5fc9c0e9606f4530e6f41Eric Christopher return (unsigned)(Val * 37ULL); 88e1182b5599f11778286f027eb536d7ddf7657edaMike Stump } 89e1182b5599f11778286f027eb536d7ddf7657edaMike Stump static bool isEqual(const unsigned long long& LHS, 90e1182b5599f11778286f027eb536d7ddf7657edaMike Stump const unsigned long long& RHS) { 918ecbe8d974e1c1f778207b87dcdf887060f5c699Duncan Sands return LHS == RHS; 92e1182b5599f11778286f027eb536d7ddf7657edaMike Stump } 93e1182b5599f11778286f027eb536d7ddf7657edaMike Stump}; 94e1182b5599f11778286f027eb536d7ddf7657edaMike Stump 953e6fe5ec17217169cd95ee86515955f7726db008Evan Cheng// Provide DenseMapInfo for ints. 963e6fe5ec17217169cd95ee86515955f7726db008Evan Chengtemplate<> struct DenseMapInfo<int> { 973e6fe5ec17217169cd95ee86515955f7726db008Evan Cheng static inline int getEmptyKey() { return 0x7fffffff; } 983e6fe5ec17217169cd95ee86515955f7726db008Evan Cheng static inline int getTombstoneKey() { return -0x7fffffff - 1; } 99a046d2ff9a6ef1a5ecf1068d9fce714db7557c2aEli Friedman static unsigned getHashValue(const int& Val) { return (unsigned)(Val * 37U); } 1003e6fe5ec17217169cd95ee86515955f7726db008Evan Cheng static bool isEqual(const int& LHS, const int& RHS) { 1013e6fe5ec17217169cd95ee86515955f7726db008Evan Cheng return LHS == RHS; 1023e6fe5ec17217169cd95ee86515955f7726db008Evan Cheng } 1033e6fe5ec17217169cd95ee86515955f7726db008Evan Cheng}; 1043e6fe5ec17217169cd95ee86515955f7726db008Evan Cheng 10525592eb52c39097bc610785f648aca4a09989201Chandler Carruth// Provide DenseMapInfo for longs. 10625592eb52c39097bc610785f648aca4a09989201Chandler Carruthtemplate<> struct DenseMapInfo<long> { 10725592eb52c39097bc610785f648aca4a09989201Chandler Carruth static inline long getEmptyKey() { 1081144af3c9b4da48cd581156e05b24261c8de366aRichard Smith return (1UL << (sizeof(long) * 8 - 1)) - 1UL; 10925592eb52c39097bc610785f648aca4a09989201Chandler Carruth } 11025592eb52c39097bc610785f648aca4a09989201Chandler Carruth static inline long getTombstoneKey() { return getEmptyKey() - 1L; } 11125592eb52c39097bc610785f648aca4a09989201Chandler Carruth static unsigned getHashValue(const long& Val) { 112a046d2ff9a6ef1a5ecf1068d9fce714db7557c2aEli Friedman return (unsigned)(Val * 37UL); 11325592eb52c39097bc610785f648aca4a09989201Chandler Carruth } 11425592eb52c39097bc610785f648aca4a09989201Chandler Carruth static bool isEqual(const long& LHS, const long& RHS) { 11525592eb52c39097bc610785f648aca4a09989201Chandler Carruth return LHS == RHS; 11625592eb52c39097bc610785f648aca4a09989201Chandler Carruth } 11725592eb52c39097bc610785f648aca4a09989201Chandler Carruth}; 11825592eb52c39097bc610785f648aca4a09989201Chandler Carruth 119cf220d5b8955a71d364a0a054e8518197bf6df32Evan Cheng// Provide DenseMapInfo for long longs. 120cf220d5b8955a71d364a0a054e8518197bf6df32Evan Chengtemplate<> struct DenseMapInfo<long long> { 121cf220d5b8955a71d364a0a054e8518197bf6df32Evan Cheng static inline long long getEmptyKey() { return 0x7fffffffffffffffLL; } 122cf220d5b8955a71d364a0a054e8518197bf6df32Evan Cheng static inline long long getTombstoneKey() { return -0x7fffffffffffffffLL-1; } 123cf220d5b8955a71d364a0a054e8518197bf6df32Evan Cheng static unsigned getHashValue(const long long& Val) { 124a046d2ff9a6ef1a5ecf1068d9fce714db7557c2aEli Friedman return (unsigned)(Val * 37ULL); 125cf220d5b8955a71d364a0a054e8518197bf6df32Evan Cheng } 126cf220d5b8955a71d364a0a054e8518197bf6df32Evan Cheng static bool isEqual(const long long& LHS, 127cf220d5b8955a71d364a0a054e8518197bf6df32Evan Cheng const long long& RHS) { 128cf220d5b8955a71d364a0a054e8518197bf6df32Evan Cheng return LHS == RHS; 129cf220d5b8955a71d364a0a054e8518197bf6df32Evan Cheng } 130cf220d5b8955a71d364a0a054e8518197bf6df32Evan Cheng}; 131cf220d5b8955a71d364a0a054e8518197bf6df32Evan Cheng 132fb3af88ba75898896714d49c608b8daa4f106636Dan Gohman// Provide DenseMapInfo for all pairs whose members have info. 133fb3af88ba75898896714d49c608b8daa4f106636Dan Gohmantemplate<typename T, typename U> 134fb3af88ba75898896714d49c608b8daa4f106636Dan Gohmanstruct DenseMapInfo<std::pair<T, U> > { 135fb3af88ba75898896714d49c608b8daa4f106636Dan Gohman typedef std::pair<T, U> Pair; 136fb3af88ba75898896714d49c608b8daa4f106636Dan Gohman typedef DenseMapInfo<T> FirstInfo; 137fb3af88ba75898896714d49c608b8daa4f106636Dan Gohman typedef DenseMapInfo<U> SecondInfo; 138fb3af88ba75898896714d49c608b8daa4f106636Dan Gohman 139fb3af88ba75898896714d49c608b8daa4f106636Dan Gohman static inline Pair getEmptyKey() { 140fb3af88ba75898896714d49c608b8daa4f106636Dan Gohman return std::make_pair(FirstInfo::getEmptyKey(), 141fb3af88ba75898896714d49c608b8daa4f106636Dan Gohman SecondInfo::getEmptyKey()); 142fb3af88ba75898896714d49c608b8daa4f106636Dan Gohman } 143fb3af88ba75898896714d49c608b8daa4f106636Dan Gohman static inline Pair getTombstoneKey() { 144fb3af88ba75898896714d49c608b8daa4f106636Dan Gohman return std::make_pair(FirstInfo::getTombstoneKey(), 145297738fa95d4bb7849c197926f4d4abdcd812e40Nick Lewycky SecondInfo::getTombstoneKey()); 146fb3af88ba75898896714d49c608b8daa4f106636Dan Gohman } 147fb3af88ba75898896714d49c608b8daa4f106636Dan Gohman static unsigned getHashValue(const Pair& PairVal) { 148fb3af88ba75898896714d49c608b8daa4f106636Dan Gohman uint64_t key = (uint64_t)FirstInfo::getHashValue(PairVal.first) << 32 149fb3af88ba75898896714d49c608b8daa4f106636Dan Gohman | (uint64_t)SecondInfo::getHashValue(PairVal.second); 150fb3af88ba75898896714d49c608b8daa4f106636Dan Gohman key += ~(key << 32); 151fb3af88ba75898896714d49c608b8daa4f106636Dan Gohman key ^= (key >> 22); 152fb3af88ba75898896714d49c608b8daa4f106636Dan Gohman key += ~(key << 13); 153fb3af88ba75898896714d49c608b8daa4f106636Dan Gohman key ^= (key >> 8); 154fb3af88ba75898896714d49c608b8daa4f106636Dan Gohman key += (key << 3); 155fb3af88ba75898896714d49c608b8daa4f106636Dan Gohman key ^= (key >> 15); 156fb3af88ba75898896714d49c608b8daa4f106636Dan Gohman key += ~(key << 27); 157fb3af88ba75898896714d49c608b8daa4f106636Dan Gohman key ^= (key >> 31); 158fb3af88ba75898896714d49c608b8daa4f106636Dan Gohman return (unsigned)key; 159fb3af88ba75898896714d49c608b8daa4f106636Dan Gohman } 160b1145c8cee6ab749f00d07d3d7dab0d1d1fd0c06Chris Lattner static bool isEqual(const Pair &LHS, const Pair &RHS) { 161297738fa95d4bb7849c197926f4d4abdcd812e40Nick Lewycky return FirstInfo::isEqual(LHS.first, RHS.first) && 162b1145c8cee6ab749f00d07d3d7dab0d1d1fd0c06Chris Lattner SecondInfo::isEqual(LHS.second, RHS.second); 163b1145c8cee6ab749f00d07d3d7dab0d1d1fd0c06Chris Lattner } 164fb3af88ba75898896714d49c608b8daa4f106636Dan Gohman}; 165fb3af88ba75898896714d49c608b8daa4f106636Dan Gohman 166fb3af88ba75898896714d49c608b8daa4f106636Dan Gohman} // end namespace llvm 167fb3af88ba75898896714d49c608b8daa4f106636Dan Gohman 168fb3af88ba75898896714d49c608b8daa4f106636Dan Gohman#endif 169