DenseMapInfo.h revision 25592eb52c39097bc610785f648aca4a09989201
1ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com//===- llvm/ADT/DenseMapInfo.h - Type traits for DenseMap -------*- C++ -*-===// 2ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com// 3ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com// The LLVM Compiler Infrastructure 4ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com// 5ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com// This file is distributed under the University of Illinois Open Source 6ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com// License. See LICENSE.TXT for details. 7971d0c8049c6bfc7a58f0b41f8f59f9ec9ca077bbsalomon@google.com// 857f7abc8659f17e58fc2d1410117033ad524f9d3epoger@google.com//===----------------------------------------------------------------------===// 957f7abc8659f17e58fc2d1410117033ad524f9d3epoger@google.com// 1057f7abc8659f17e58fc2d1410117033ad524f9d3epoger@google.com// This file defines DenseMapInfo traits for DenseMap. 1157f7abc8659f17e58fc2d1410117033ad524f9d3epoger@google.com// 1257f7abc8659f17e58fc2d1410117033ad524f9d3epoger@google.com//===----------------------------------------------------------------------===// 1357f7abc8659f17e58fc2d1410117033ad524f9d3epoger@google.com 1457f7abc8659f17e58fc2d1410117033ad524f9d3epoger@google.com#ifndef LLVM_ADT_DENSEMAPINFO_H 1557f7abc8659f17e58fc2d1410117033ad524f9d3epoger@google.com#define LLVM_ADT_DENSEMAPINFO_H 16b29c883fb46ac6099440d82ac57b86d25386daedbungeman@google.com 177bc13a62609149f0b535c2f3ff7210eb834d8b36epoger@google.com#include "llvm/Support/PointerLikeTypeTraits.h" 18b9b9a18ab459c2616ac4a52c9f8cc0637d284229reed@android.com#include "llvm/Support/type_traits.h" 198a85d0c4938173476d037d7af0ee3b9436a1234ereed@google.com 204370aedf7f55af74e9ebb4ad1c2e010c08236dfajunov@google.comnamespace llvm { 21971d0c8049c6bfc7a58f0b41f8f59f9ec9ca077bbsalomon@google.com 22de96163a80167636d95837f9ee6a2e98baf9d350epoger@google.comtemplate<typename T> 235af9b2032b552516c9223d9fb22185b022b13c62scroggo@google.comstruct DenseMapInfo { 248015dd83ae37147bb630d4751030868051ad0caereed@android.com //static inline T getEmptyKey(); 258015dd83ae37147bb630d4751030868051ad0caereed@android.com //static inline T getTombstoneKey(); 268015dd83ae37147bb630d4751030868051ad0caereed@android.com //static unsigned getHashValue(const T &Val); 27e8ebeb1f8fde6525bbab988c6090a5d3ab19855bepoger@google.com //static bool isEqual(const T &LHS, const T &RHS); 289875dd14af6d768da8d1a4be58b98fc91ceca0ddtomhudson@google.com}; 29977b9c8af3ef1b9a2fa2a0037cf3734cf2ba13d9robertphillips@google.com 3072c9672ce274a3b6cb40800d66374edf25b157a3scroggo@google.com// Provide DenseMapInfo for all pointers. 312a48c3adb7cf4fc754f99a41352210b4a99edf04bsalomon@google.comtemplate<typename T> 323cb834bd27a16cc60ff30adae96659558c2dc91fjunov@chromium.orgstruct DenseMapInfo<T*> { 3372c9672ce274a3b6cb40800d66374edf25b157a3scroggo@google.com static inline T* getEmptyKey() { 340770044da6d61dcbc8d9673fed8dd92460faa314reed@google.com intptr_t Val = -1; 35cf8fb1f6f03fc77f9927564f9ef9abeeeec508d2bsalomon@google.com Val <<= PointerLikeTypeTraits<T*>::NumLowBitsAvailable; 36cf8fb1f6f03fc77f9927564f9ef9abeeeec508d2bsalomon@google.com return reinterpret_cast<T*>(Val); 37cf8fb1f6f03fc77f9927564f9ef9abeeeec508d2bsalomon@google.com } 38cf8fb1f6f03fc77f9927564f9ef9abeeeec508d2bsalomon@google.com static inline T* getTombstoneKey() { 39cf8fb1f6f03fc77f9927564f9ef9abeeeec508d2bsalomon@google.com intptr_t Val = -2; 40cf8fb1f6f03fc77f9927564f9ef9abeeeec508d2bsalomon@google.com Val <<= PointerLikeTypeTraits<T*>::NumLowBitsAvailable; 41cf8fb1f6f03fc77f9927564f9ef9abeeeec508d2bsalomon@google.com return reinterpret_cast<T*>(Val); 42cf8fb1f6f03fc77f9927564f9ef9abeeeec508d2bsalomon@google.com } 43cf8fb1f6f03fc77f9927564f9ef9abeeeec508d2bsalomon@google.com static unsigned getHashValue(const T *PtrVal) { 44cf8fb1f6f03fc77f9927564f9ef9abeeeec508d2bsalomon@google.com return (unsigned((uintptr_t)PtrVal) >> 4) ^ 45cf8fb1f6f03fc77f9927564f9ef9abeeeec508d2bsalomon@google.com (unsigned((uintptr_t)PtrVal) >> 9); 4610afbefa5b60b0f7e8d2b02f4c996de88aa26830mike@reedtribe.org } 4710afbefa5b60b0f7e8d2b02f4c996de88aa26830mike@reedtribe.org static bool isEqual(const T *LHS, const T *RHS) { return LHS == RHS; } 488923c6cfd580ac9accb11b909fa2a033d69553aareed@google.com}; 498923c6cfd580ac9accb11b909fa2a033d69553aareed@google.com 500770044da6d61dcbc8d9673fed8dd92460faa314reed@google.com// Provide DenseMapInfo for chars. 519875dd14af6d768da8d1a4be58b98fc91ceca0ddtomhudson@google.comtemplate<> struct DenseMapInfo<char> { 529875dd14af6d768da8d1a4be58b98fc91ceca0ddtomhudson@google.com static inline char getEmptyKey() { return ~0; } 530770044da6d61dcbc8d9673fed8dd92460faa314reed@google.com static inline char getTombstoneKey() { return ~0 - 1; } 5400dae86f5872b60927b28a32b375bc01cd7c61c9reed@android.com static unsigned getHashValue(const char& Val) { return Val * 37; } 55e3cc2eb88fef9b2123c6ea2ed813ce53b6385926epoger@google.com static bool isEqual(const char &LHS, const char &RHS) { 56e3cc2eb88fef9b2123c6ea2ed813ce53b6385926epoger@google.com return LHS == RHS; 57e3cc2eb88fef9b2123c6ea2ed813ce53b6385926epoger@google.com } 58b29c883fb46ac6099440d82ac57b86d25386daedbungeman@google.com}; 59b29c883fb46ac6099440d82ac57b86d25386daedbungeman@google.com 60b29c883fb46ac6099440d82ac57b86d25386daedbungeman@google.com// Provide DenseMapInfo for unsigned ints. 61b29c883fb46ac6099440d82ac57b86d25386daedbungeman@google.comtemplate<> struct DenseMapInfo<unsigned> { 6246cce91f4859b9c229938d4d649870c0a43b1806reed@google.com static inline unsigned getEmptyKey() { return ~0; } 6346cce91f4859b9c229938d4d649870c0a43b1806reed@google.com static inline unsigned getTombstoneKey() { return ~0U - 1; } 640a09eef79053f93a9b2311c6a29275abf39f189ebsalomon@google.com static unsigned getHashValue(const unsigned& Val) { return Val * 37; } 6546cce91f4859b9c229938d4d649870c0a43b1806reed@google.com static bool isEqual(const unsigned& LHS, const unsigned& RHS) { 660a09eef79053f93a9b2311c6a29275abf39f189ebsalomon@google.com return LHS == RHS; 6746cce91f4859b9c229938d4d649870c0a43b1806reed@google.com } 6846cce91f4859b9c229938d4d649870c0a43b1806reed@google.com}; 69c7cf2b351f85712a8ed0e1c495d1045dbaa7b785epoger@google.com 70c7cf2b351f85712a8ed0e1c495d1045dbaa7b785epoger@google.com// Provide DenseMapInfo for unsigned longs. 71c7cf2b351f85712a8ed0e1c495d1045dbaa7b785epoger@google.comtemplate<> struct DenseMapInfo<unsigned long> { 72c7cf2b351f85712a8ed0e1c495d1045dbaa7b785epoger@google.com static inline unsigned long getEmptyKey() { return ~0UL; } 73c7cf2b351f85712a8ed0e1c495d1045dbaa7b785epoger@google.com static inline unsigned long getTombstoneKey() { return ~0UL - 1L; } 74c7cf2b351f85712a8ed0e1c495d1045dbaa7b785epoger@google.com static unsigned getHashValue(const unsigned long& Val) { 75c7cf2b351f85712a8ed0e1c495d1045dbaa7b785epoger@google.com return (unsigned)(Val * 37UL); 76c7cf2b351f85712a8ed0e1c495d1045dbaa7b785epoger@google.com } 7700dae86f5872b60927b28a32b375bc01cd7c61c9reed@android.com static bool isEqual(const unsigned long& LHS, const unsigned long& RHS) { 7800dae86f5872b60927b28a32b375bc01cd7c61c9reed@android.com return LHS == RHS; 79ce7ffaccc4a0cd0e0285cdba25bddb627f8e92c4reed@google.com } 80ce7ffaccc4a0cd0e0285cdba25bddb627f8e92c4reed@google.com}; 81ce7ffaccc4a0cd0e0285cdba25bddb627f8e92c4reed@google.com 82ce7ffaccc4a0cd0e0285cdba25bddb627f8e92c4reed@google.com// Provide DenseMapInfo for unsigned long longs. 83ce7ffaccc4a0cd0e0285cdba25bddb627f8e92c4reed@google.comtemplate<> struct DenseMapInfo<unsigned long long> { 84ce7ffaccc4a0cd0e0285cdba25bddb627f8e92c4reed@google.com static inline unsigned long long getEmptyKey() { return ~0ULL; } 85ce7ffaccc4a0cd0e0285cdba25bddb627f8e92c4reed@google.com static inline unsigned long long getTombstoneKey() { return ~0ULL - 1ULL; } 86ce7ffaccc4a0cd0e0285cdba25bddb627f8e92c4reed@google.com static unsigned getHashValue(const unsigned long long& Val) { 87ce7ffaccc4a0cd0e0285cdba25bddb627f8e92c4reed@google.com return (unsigned)(Val * 37ULL); 88ce7ffaccc4a0cd0e0285cdba25bddb627f8e92c4reed@google.com } 89ce7ffaccc4a0cd0e0285cdba25bddb627f8e92c4reed@google.com static bool isEqual(const unsigned long long& LHS, 90ce7ffaccc4a0cd0e0285cdba25bddb627f8e92c4reed@google.com const unsigned long long& RHS) { 9157f7abc8659f17e58fc2d1410117033ad524f9d3epoger@google.com return LHS == RHS; 9257f7abc8659f17e58fc2d1410117033ad524f9d3epoger@google.com } 9357f7abc8659f17e58fc2d1410117033ad524f9d3epoger@google.com}; 9457f7abc8659f17e58fc2d1410117033ad524f9d3epoger@google.com 9557f7abc8659f17e58fc2d1410117033ad524f9d3epoger@google.com// Provide DenseMapInfo for ints. 9657f7abc8659f17e58fc2d1410117033ad524f9d3epoger@google.comtemplate<> struct DenseMapInfo<int> { 9757f7abc8659f17e58fc2d1410117033ad524f9d3epoger@google.com static inline int getEmptyKey() { return 0x7fffffff; } 9857f7abc8659f17e58fc2d1410117033ad524f9d3epoger@google.com static inline int getTombstoneKey() { return -0x7fffffff - 1; } 9900dae86f5872b60927b28a32b375bc01cd7c61c9reed@android.com static unsigned getHashValue(const int& Val) { return (unsigned)(Val * 37); } 10000dae86f5872b60927b28a32b375bc01cd7c61c9reed@android.com static bool isEqual(const int& LHS, const int& RHS) { 10100dae86f5872b60927b28a32b375bc01cd7c61c9reed@android.com return LHS == RHS; 1023914958a49ee089ddeb04acc16373aae8bc2eaf7bsalomon@google.com } 1033914958a49ee089ddeb04acc16373aae8bc2eaf7bsalomon@google.com}; 1043914958a49ee089ddeb04acc16373aae8bc2eaf7bsalomon@google.com 1053914958a49ee089ddeb04acc16373aae8bc2eaf7bsalomon@google.com// Provide DenseMapInfo for longs. 106dd0ac281e920b01a63789893cc3e7422789658ddreed@android.comtemplate<> struct DenseMapInfo<long> { 10700dae86f5872b60927b28a32b375bc01cd7c61c9reed@android.com static inline long getEmptyKey() { 108d4dfd10bb6f9bf3ac6e1ebc9bc3ae22c6d06321freed@google.com return (1UL << (sizeof(long) * 8 - 1)) - 1L; 109dd0ac281e920b01a63789893cc3e7422789658ddreed@android.com } 11000dae86f5872b60927b28a32b375bc01cd7c61c9reed@android.com static inline long getTombstoneKey() { return getEmptyKey() - 1L; } 111dd0ac281e920b01a63789893cc3e7422789658ddreed@android.com static unsigned getHashValue(const long& Val) { 11200dae86f5872b60927b28a32b375bc01cd7c61c9reed@android.com return (unsigned)(Val * 37L); 113dd0ac281e920b01a63789893cc3e7422789658ddreed@android.com } 11400dae86f5872b60927b28a32b375bc01cd7c61c9reed@android.com static bool isEqual(const long& LHS, const long& RHS) { 11500dae86f5872b60927b28a32b375bc01cd7c61c9reed@android.com return LHS == RHS; 11600dae86f5872b60927b28a32b375bc01cd7c61c9reed@android.com } 117d4dfd10bb6f9bf3ac6e1ebc9bc3ae22c6d06321freed@google.com}; 11800dae86f5872b60927b28a32b375bc01cd7c61c9reed@android.com 119dd0ac281e920b01a63789893cc3e7422789658ddreed@android.com// Provide DenseMapInfo for long longs. 12000dae86f5872b60927b28a32b375bc01cd7c61c9reed@android.comtemplate<> struct DenseMapInfo<long long> { 12100dae86f5872b60927b28a32b375bc01cd7c61c9reed@android.com static inline long long getEmptyKey() { return 0x7fffffffffffffffLL; } 12200dae86f5872b60927b28a32b375bc01cd7c61c9reed@android.com static inline long long getTombstoneKey() { return -0x7fffffffffffffffLL-1; } 12300dae86f5872b60927b28a32b375bc01cd7c61c9reed@android.com static unsigned getHashValue(const long long& Val) { 12400dae86f5872b60927b28a32b375bc01cd7c61c9reed@android.com return (unsigned)(Val * 37LL); 12500dae86f5872b60927b28a32b375bc01cd7c61c9reed@android.com } 12600dae86f5872b60927b28a32b375bc01cd7c61c9reed@android.com static bool isEqual(const long long& LHS, 127d4dfd10bb6f9bf3ac6e1ebc9bc3ae22c6d06321freed@google.com const long long& RHS) { 12800dae86f5872b60927b28a32b375bc01cd7c61c9reed@android.com return LHS == RHS; 12900dae86f5872b60927b28a32b375bc01cd7c61c9reed@android.com } 13000dae86f5872b60927b28a32b375bc01cd7c61c9reed@android.com}; 13100dae86f5872b60927b28a32b375bc01cd7c61c9reed@android.com 132686abdfab0e4c45de1fd30774896c46e43a299acvandebo@chromium.org// Provide DenseMapInfo for all pairs whose members have info. 1333cb834bd27a16cc60ff30adae96659558c2dc91fjunov@chromium.orgtemplate<typename T, typename U> 1343cb834bd27a16cc60ff30adae96659558c2dc91fjunov@chromium.orgstruct DenseMapInfo<std::pair<T, U> > { 1353cb834bd27a16cc60ff30adae96659558c2dc91fjunov@chromium.org typedef std::pair<T, U> Pair; 1363cb834bd27a16cc60ff30adae96659558c2dc91fjunov@chromium.org typedef DenseMapInfo<T> FirstInfo; 1373cb834bd27a16cc60ff30adae96659558c2dc91fjunov@chromium.org typedef DenseMapInfo<U> SecondInfo; 1383cb834bd27a16cc60ff30adae96659558c2dc91fjunov@chromium.org 1393cb834bd27a16cc60ff30adae96659558c2dc91fjunov@chromium.org static inline Pair getEmptyKey() { 1403cb834bd27a16cc60ff30adae96659558c2dc91fjunov@chromium.org return std::make_pair(FirstInfo::getEmptyKey(), 1413cb834bd27a16cc60ff30adae96659558c2dc91fjunov@chromium.org SecondInfo::getEmptyKey()); 1423cb834bd27a16cc60ff30adae96659558c2dc91fjunov@chromium.org } 143686abdfab0e4c45de1fd30774896c46e43a299acvandebo@chromium.org static inline Pair getTombstoneKey() { 144686abdfab0e4c45de1fd30774896c46e43a299acvandebo@chromium.org return std::make_pair(FirstInfo::getTombstoneKey(), 1457361f54294d65a5c42ce5cf1cd56d0fd7122e268bsalomon@google.com SecondInfo::getEmptyKey()); 1467361f54294d65a5c42ce5cf1cd56d0fd7122e268bsalomon@google.com } 1477361f54294d65a5c42ce5cf1cd56d0fd7122e268bsalomon@google.com static unsigned getHashValue(const Pair& PairVal) { 1487361f54294d65a5c42ce5cf1cd56d0fd7122e268bsalomon@google.com uint64_t key = (uint64_t)FirstInfo::getHashValue(PairVal.first) << 32 149f28dd8ab109663a6fe67fd4ee3d66248e0dac686epoger@google.com | (uint64_t)SecondInfo::getHashValue(PairVal.second); 1507361f54294d65a5c42ce5cf1cd56d0fd7122e268bsalomon@google.com key += ~(key << 32); 1517361f54294d65a5c42ce5cf1cd56d0fd7122e268bsalomon@google.com key ^= (key >> 22); 1527361f54294d65a5c42ce5cf1cd56d0fd7122e268bsalomon@google.com key += ~(key << 13); 1537361f54294d65a5c42ce5cf1cd56d0fd7122e268bsalomon@google.com key ^= (key >> 8); 1549875dd14af6d768da8d1a4be58b98fc91ceca0ddtomhudson@google.com key += (key << 3); 1557361f54294d65a5c42ce5cf1cd56d0fd7122e268bsalomon@google.com key ^= (key >> 15); 1567361f54294d65a5c42ce5cf1cd56d0fd7122e268bsalomon@google.com key += ~(key << 27); 157cf8fb1f6f03fc77f9927564f9ef9abeeeec508d2bsalomon@google.com key ^= (key >> 31); 1587361f54294d65a5c42ce5cf1cd56d0fd7122e268bsalomon@google.com return (unsigned)key; 1597361f54294d65a5c42ce5cf1cd56d0fd7122e268bsalomon@google.com } 1607361f54294d65a5c42ce5cf1cd56d0fd7122e268bsalomon@google.com static bool isEqual(const Pair& LHS, const Pair& RHS) { return LHS == RHS; } 1619875dd14af6d768da8d1a4be58b98fc91ceca0ddtomhudson@google.com}; 1629875dd14af6d768da8d1a4be58b98fc91ceca0ddtomhudson@google.com 16310afbefa5b60b0f7e8d2b02f4c996de88aa26830mike@reedtribe.org} // end namespace llvm 16410afbefa5b60b0f7e8d2b02f4c996de88aa26830mike@reedtribe.org 165971aca75572ed6e0c5e1cc959173dc58ca7b6b8dreed@google.com#endif 16610afbefa5b60b0f7e8d2b02f4c996de88aa26830mike@reedtribe.org