DenseMap.h revision d06c59821a1ca0191ea8a326a18509808a02ed03
16e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner//===- llvm/ADT/DenseMap.h - Dense probed hash table ------------*- C++ -*-===// 26e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner// 36e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner// The LLVM Compiler Infrastructure 46e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner// 57ed47a13356daed2a34cd2209a31f92552e3bdd8Chris Lattner// This file is distributed under the University of Illinois Open Source 67ed47a13356daed2a34cd2209a31f92552e3bdd8Chris Lattner// License. See LICENSE.TXT for details. 76e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner// 86e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner//===----------------------------------------------------------------------===// 96e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner// 106e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner// This file defines the DenseMap class. 116e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner// 126e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner//===----------------------------------------------------------------------===// 136e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 146e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner#ifndef LLVM_ADT_DENSEMAP_H 156e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner#define LLVM_ADT_DENSEMAP_H 166e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 17f341a47d10501bc69b5d4d2217992bb6e08668d8Chris Lattner#include "llvm/Support/PointerLikeTypeTraits.h" 18398b40671b13018f88371b74822fa8ee2638577eOwen Anderson#include "llvm/Support/MathExtras.h" 196e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner#include <cassert> 20d06c59821a1ca0191ea8a326a18509808a02ed03Torok Edwin#include <cstring> 21f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner#include <utility> 2211d8fb960963a1f8a7e2b2972bc560a5b24cf216Chris Lattner#include <new> 236e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 246e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattnernamespace llvm { 253a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 266e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattnertemplate<typename T> 2776c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattnerstruct DenseMapInfo { 286e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner //static inline T getEmptyKey(); 296e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner //static inline T getTombstoneKey(); 306e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner //static unsigned getHashValue(const T &Val); 3176c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattner //static bool isEqual(const T &LHS, const T &RHS); 326e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner //static bool isPod() 336e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner}; 346e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 3576c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattner// Provide DenseMapInfo for all pointers. 366e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattnertemplate<typename T> 3776c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattnerstruct DenseMapInfo<T*> { 38f341a47d10501bc69b5d4d2217992bb6e08668d8Chris Lattner static inline T* getEmptyKey() { 39f341a47d10501bc69b5d4d2217992bb6e08668d8Chris Lattner intptr_t Val = -1; 40f341a47d10501bc69b5d4d2217992bb6e08668d8Chris Lattner Val <<= PointerLikeTypeTraits<T*>::NumLowBitsAvailable; 41f341a47d10501bc69b5d4d2217992bb6e08668d8Chris Lattner return reinterpret_cast<T*>(Val); 42f341a47d10501bc69b5d4d2217992bb6e08668d8Chris Lattner } 43f341a47d10501bc69b5d4d2217992bb6e08668d8Chris Lattner static inline T* getTombstoneKey() { 44f341a47d10501bc69b5d4d2217992bb6e08668d8Chris Lattner intptr_t Val = -2; 45f341a47d10501bc69b5d4d2217992bb6e08668d8Chris Lattner Val <<= PointerLikeTypeTraits<T*>::NumLowBitsAvailable; 46f341a47d10501bc69b5d4d2217992bb6e08668d8Chris Lattner return reinterpret_cast<T*>(Val); 47f341a47d10501bc69b5d4d2217992bb6e08668d8Chris Lattner } 486e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner static unsigned getHashValue(const T *PtrVal) { 493a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman return (unsigned((uintptr_t)PtrVal) >> 4) ^ 50f8a3ee1d637a747c87f72bc880445e6a82280ff0Chris Lattner (unsigned((uintptr_t)PtrVal) >> 9); 516e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 5276c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattner static bool isEqual(const T *LHS, const T *RHS) { return LHS == RHS; } 5329ce95511f905df3a63e3b953a4a0179ead46865Owen Anderson static bool isPod() { return true; } 5429ce95511f905df3a63e3b953a4a0179ead46865Owen Anderson}; 5529ce95511f905df3a63e3b953a4a0179ead46865Owen Anderson 56dd255a62474a2016702e2985710e6e8910b3c974Chris Lattner// Provide DenseMapInfo for chars. 57dd255a62474a2016702e2985710e6e8910b3c974Chris Lattnertemplate<> struct DenseMapInfo<char> { 58dd255a62474a2016702e2985710e6e8910b3c974Chris Lattner static inline char getEmptyKey() { return ~0; } 59dd255a62474a2016702e2985710e6e8910b3c974Chris Lattner static inline char getTombstoneKey() { return ~0 - 1; } 60dd255a62474a2016702e2985710e6e8910b3c974Chris Lattner static unsigned getHashValue(const char& Val) { return Val * 37; } 61dd255a62474a2016702e2985710e6e8910b3c974Chris Lattner static bool isPod() { return true; } 62dd255a62474a2016702e2985710e6e8910b3c974Chris Lattner static bool isEqual(const char &LHS, const char &RHS) { 63dd255a62474a2016702e2985710e6e8910b3c974Chris Lattner return LHS == RHS; 64dd255a62474a2016702e2985710e6e8910b3c974Chris Lattner } 65dd255a62474a2016702e2985710e6e8910b3c974Chris Lattner}; 66dd255a62474a2016702e2985710e6e8910b3c974Chris Lattner 672dba6a1bdb7d78b4d1e5e69b81989816193e6b70Chris Lattner// Provide DenseMapInfo for unsigned ints. 682f39b29170e0f69491fc5b73952725266ac32fb8Chris Lattnertemplate<> struct DenseMapInfo<unsigned> { 692f39b29170e0f69491fc5b73952725266ac32fb8Chris Lattner static inline unsigned getEmptyKey() { return ~0; } 702f39b29170e0f69491fc5b73952725266ac32fb8Chris Lattner static inline unsigned getTombstoneKey() { return ~0 - 1; } 712f39b29170e0f69491fc5b73952725266ac32fb8Chris Lattner static unsigned getHashValue(const unsigned& Val) { return Val * 37; } 722dba6a1bdb7d78b4d1e5e69b81989816193e6b70Chris Lattner static bool isPod() { return true; } 732f39b29170e0f69491fc5b73952725266ac32fb8Chris Lattner static bool isEqual(const unsigned& LHS, const unsigned& RHS) { 742f39b29170e0f69491fc5b73952725266ac32fb8Chris Lattner return LHS == RHS; 752f39b29170e0f69491fc5b73952725266ac32fb8Chris Lattner } 762f39b29170e0f69491fc5b73952725266ac32fb8Chris Lattner}; 772f39b29170e0f69491fc5b73952725266ac32fb8Chris Lattner 782f39b29170e0f69491fc5b73952725266ac32fb8Chris Lattner// Provide DenseMapInfo for unsigned longs. 792f39b29170e0f69491fc5b73952725266ac32fb8Chris Lattnertemplate<> struct DenseMapInfo<unsigned long> { 802f39b29170e0f69491fc5b73952725266ac32fb8Chris Lattner static inline unsigned long getEmptyKey() { return ~0L; } 812f39b29170e0f69491fc5b73952725266ac32fb8Chris Lattner static inline unsigned long getTombstoneKey() { return ~0L - 1L; } 82d10aacea5e2c8ea62e08956aa0a94fa2da60e148Bill Wendling static unsigned getHashValue(const unsigned long& Val) { 83d10aacea5e2c8ea62e08956aa0a94fa2da60e148Bill Wendling return (unsigned)(Val * 37L); 84d10aacea5e2c8ea62e08956aa0a94fa2da60e148Bill Wendling } 852f39b29170e0f69491fc5b73952725266ac32fb8Chris Lattner static bool isPod() { return true; } 862f39b29170e0f69491fc5b73952725266ac32fb8Chris Lattner static bool isEqual(const unsigned long& LHS, const unsigned long& RHS) { 872dba6a1bdb7d78b4d1e5e69b81989816193e6b70Chris Lattner return LHS == RHS; 882dba6a1bdb7d78b4d1e5e69b81989816193e6b70Chris Lattner } 892dba6a1bdb7d78b4d1e5e69b81989816193e6b70Chris Lattner}; 902dba6a1bdb7d78b4d1e5e69b81989816193e6b70Chris Lattner 912dba6a1bdb7d78b4d1e5e69b81989816193e6b70Chris Lattner// Provide DenseMapInfo for all pairs whose members have info. 922dba6a1bdb7d78b4d1e5e69b81989816193e6b70Chris Lattnertemplate<typename T, typename U> 932dba6a1bdb7d78b4d1e5e69b81989816193e6b70Chris Lattnerstruct DenseMapInfo<std::pair<T, U> > { 942dba6a1bdb7d78b4d1e5e69b81989816193e6b70Chris Lattner typedef std::pair<T, U> Pair; 952dba6a1bdb7d78b4d1e5e69b81989816193e6b70Chris Lattner typedef DenseMapInfo<T> FirstInfo; 962dba6a1bdb7d78b4d1e5e69b81989816193e6b70Chris Lattner typedef DenseMapInfo<U> SecondInfo; 972dba6a1bdb7d78b4d1e5e69b81989816193e6b70Chris Lattner 983a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman static inline Pair getEmptyKey() { 993a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman return std::make_pair(FirstInfo::getEmptyKey(), 1003a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman SecondInfo::getEmptyKey()); 1012dba6a1bdb7d78b4d1e5e69b81989816193e6b70Chris Lattner } 1023a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman static inline Pair getTombstoneKey() { 1033a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman return std::make_pair(FirstInfo::getTombstoneKey(), 104b9118246201592e7e6c1353a09f69e8a4d469d9dChris Lattner SecondInfo::getEmptyKey()); 105b9118246201592e7e6c1353a09f69e8a4d469d9dChris Lattner } 106b9118246201592e7e6c1353a09f69e8a4d469d9dChris Lattner static unsigned getHashValue(const Pair& PairVal) { 107b9118246201592e7e6c1353a09f69e8a4d469d9dChris Lattner uint64_t key = (uint64_t)FirstInfo::getHashValue(PairVal.first) << 32 108b9118246201592e7e6c1353a09f69e8a4d469d9dChris Lattner | (uint64_t)SecondInfo::getHashValue(PairVal.second); 109b9118246201592e7e6c1353a09f69e8a4d469d9dChris Lattner key += ~(key << 32); 110b9118246201592e7e6c1353a09f69e8a4d469d9dChris Lattner key ^= (key >> 22); 111b9118246201592e7e6c1353a09f69e8a4d469d9dChris Lattner key += ~(key << 13); 112b9118246201592e7e6c1353a09f69e8a4d469d9dChris Lattner key ^= (key >> 8); 113b9118246201592e7e6c1353a09f69e8a4d469d9dChris Lattner key += (key << 3); 114b9118246201592e7e6c1353a09f69e8a4d469d9dChris Lattner key ^= (key >> 15); 115b9118246201592e7e6c1353a09f69e8a4d469d9dChris Lattner key += ~(key << 27); 116b9118246201592e7e6c1353a09f69e8a4d469d9dChris Lattner key ^= (key >> 31); 117b9118246201592e7e6c1353a09f69e8a4d469d9dChris Lattner return (unsigned)key; 118b9118246201592e7e6c1353a09f69e8a4d469d9dChris Lattner } 119b9118246201592e7e6c1353a09f69e8a4d469d9dChris Lattner static bool isEqual(const Pair& LHS, const Pair& RHS) { return LHS == RHS; } 120b9118246201592e7e6c1353a09f69e8a4d469d9dChris Lattner static bool isPod() { return FirstInfo::isPod() && SecondInfo::isPod(); } 1212dba6a1bdb7d78b4d1e5e69b81989816193e6b70Chris Lattner}; 1222dba6a1bdb7d78b4d1e5e69b81989816193e6b70Chris Lattner 1233a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukmantemplate<typename KeyT, typename ValueT, 12476c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattner typename KeyInfoT = DenseMapInfo<KeyT>, 12576c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattner typename ValueInfoT = DenseMapInfo<ValueT> > 126f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattnerclass DenseMapIterator; 127a76b1febd4fd258e8054395adedcbd477668d956Chris Lattnertemplate<typename KeyT, typename ValueT, 12876c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattner typename KeyInfoT = DenseMapInfo<KeyT>, 12976c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattner typename ValueInfoT = DenseMapInfo<ValueT> > 13070a76a633ed5101dbe472404efd989f4f1b3669cChris Lattnerclass DenseMapConstIterator; 1316e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 132a76b1febd4fd258e8054395adedcbd477668d956Chris Lattnertemplate<typename KeyT, typename ValueT, 13376c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattner typename KeyInfoT = DenseMapInfo<KeyT>, 13476c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattner typename ValueInfoT = DenseMapInfo<ValueT> > 1356e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattnerclass DenseMap { 136f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner typedef std::pair<KeyT, ValueT> BucketT; 1376e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner unsigned NumBuckets; 1386e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner BucketT *Buckets; 1393a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 1406e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner unsigned NumEntries; 14104a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner unsigned NumTombstones; 1426e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattnerpublic: 14313e781ebe7a39e008dd5e5de78983e095e8a1d02David Greene typedef KeyT key_type; 14413e781ebe7a39e008dd5e5de78983e095e8a1d02David Greene typedef ValueT mapped_type; 145aef806e9cb021919be8f3a988af0478f3da75758Ted Kremenek typedef BucketT value_type; 1463a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 14767280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson DenseMap(const DenseMap& other) { 14867280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson NumBuckets = 0; 14967280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson CopyFrom(other); 15067280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson } 1513a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 1525a5f6b6e38b7155200903816f22501cce4ca36a7Chris Lattner explicit DenseMap(unsigned NumInitBuckets = 64) { 1536e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner init(NumInitBuckets); 1546e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 1553a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 1566e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner ~DenseMap() { 1576e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey(); 1586e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner for (BucketT *P = Buckets, *E = Buckets+NumBuckets; P != E; ++P) { 15905831c073abbaacbf2fc21ef5ef160872056e075Chris Lattner if (!KeyInfoT::isEqual(P->first, EmptyKey) && 16005831c073abbaacbf2fc21ef5ef160872056e075Chris Lattner !KeyInfoT::isEqual(P->first, TombstoneKey)) 161f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner P->second.~ValueT(); 162f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner P->first.~KeyT(); 1636e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 164d06c59821a1ca0191ea8a326a18509808a02ed03Torok Edwin#ifndef NDEBUG 165d06c59821a1ca0191ea8a326a18509808a02ed03Torok Edwin memset(Buckets, 0x5a, sizeof(BucketT)*NumBuckets); 166d06c59821a1ca0191ea8a326a18509808a02ed03Torok Edwin#endif 16708c09496c2fa7c1da027a52d8c410c2ae98481e1Dan Gohman operator delete(Buckets); 1686e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 1693a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 170a76b1febd4fd258e8054395adedcbd477668d956Chris Lattner typedef DenseMapIterator<KeyT, ValueT, KeyInfoT> iterator; 171a76b1febd4fd258e8054395adedcbd477668d956Chris Lattner typedef DenseMapConstIterator<KeyT, ValueT, KeyInfoT> const_iterator; 17270a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner inline iterator begin() { 173a76b1febd4fd258e8054395adedcbd477668d956Chris Lattner return iterator(Buckets, Buckets+NumBuckets); 17470a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner } 17570a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner inline iterator end() { 176a76b1febd4fd258e8054395adedcbd477668d956Chris Lattner return iterator(Buckets+NumBuckets, Buckets+NumBuckets); 17770a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner } 17870a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner inline const_iterator begin() const { 179a76b1febd4fd258e8054395adedcbd477668d956Chris Lattner return const_iterator(Buckets, Buckets+NumBuckets); 18070a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner } 18170a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner inline const_iterator end() const { 182a76b1febd4fd258e8054395adedcbd477668d956Chris Lattner return const_iterator(Buckets+NumBuckets, Buckets+NumBuckets); 18370a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner } 1843a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 18570a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner bool empty() const { return NumEntries == 0; } 1866e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner unsigned size() const { return NumEntries; } 187d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin 188d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin /// Grow the densemap so that it has at least Size buckets. Does not shrink 189d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin void resize(size_t Size) { grow(Size); } 1903a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 1916e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner void clear() { 19242e4bdf2577946380ce1529d5716e48b33d4186dChris Lattner // If the capacity of the array is huge, and the # elements used is small, 19342e4bdf2577946380ce1529d5716e48b33d4186dChris Lattner // shrink the array. 1946ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson if (NumEntries * 4 < NumBuckets && NumBuckets > 64) { 1956ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson shrink_and_clear(); 1966ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson return; 1976ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson } 1983a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 1996e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey(); 2006e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner for (BucketT *P = Buckets, *E = Buckets+NumBuckets; P != E; ++P) { 20105831c073abbaacbf2fc21ef5ef160872056e075Chris Lattner if (!KeyInfoT::isEqual(P->first, EmptyKey)) { 20205831c073abbaacbf2fc21ef5ef160872056e075Chris Lattner if (!KeyInfoT::isEqual(P->first, TombstoneKey)) { 2037b54452c84e478ab4d49ac08759ca4ec1badf2b2Chris Lattner P->second.~ValueT(); 2047b54452c84e478ab4d49ac08759ca4ec1badf2b2Chris Lattner --NumEntries; 2057b54452c84e478ab4d49ac08759ca4ec1badf2b2Chris Lattner } 206f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner P->first = EmptyKey; 2076e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 2086e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 2096e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner assert(NumEntries == 0 && "Node count imbalance!"); 21004a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner NumTombstones = 0; 2116e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 2126ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson 2136e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner /// count - Return true if the specified key is in the map. 2146e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner bool count(const KeyT &Val) const { 2156e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner BucketT *TheBucket; 2166e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner return LookupBucketFor(Val, TheBucket); 2176e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 2183a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 219569b935e6b23c4a0e4ebb2c96603974310ef0587Chris Lattner iterator find(const KeyT &Val) { 22070a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner BucketT *TheBucket; 22170a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner if (LookupBucketFor(Val, TheBucket)) 22270a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner return iterator(TheBucket, Buckets+NumBuckets); 22370a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner return end(); 22470a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner } 225569b935e6b23c4a0e4ebb2c96603974310ef0587Chris Lattner const_iterator find(const KeyT &Val) const { 226569b935e6b23c4a0e4ebb2c96603974310ef0587Chris Lattner BucketT *TheBucket; 227569b935e6b23c4a0e4ebb2c96603974310ef0587Chris Lattner if (LookupBucketFor(Val, TheBucket)) 228569b935e6b23c4a0e4ebb2c96603974310ef0587Chris Lattner return const_iterator(TheBucket, Buckets+NumBuckets); 229569b935e6b23c4a0e4ebb2c96603974310ef0587Chris Lattner return end(); 230569b935e6b23c4a0e4ebb2c96603974310ef0587Chris Lattner } 2313a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 2327b75fbf224c0a2d181c35708a27c514ae798c904Daniel Dunbar /// lookup - Return the entry for the specified key, or a default 2337b75fbf224c0a2d181c35708a27c514ae798c904Daniel Dunbar /// constructed value if no such entry exists. 2347b75fbf224c0a2d181c35708a27c514ae798c904Daniel Dunbar ValueT lookup(const KeyT &Val) const { 2357b75fbf224c0a2d181c35708a27c514ae798c904Daniel Dunbar BucketT *TheBucket; 2367b75fbf224c0a2d181c35708a27c514ae798c904Daniel Dunbar if (LookupBucketFor(Val, TheBucket)) 2377b75fbf224c0a2d181c35708a27c514ae798c904Daniel Dunbar return TheBucket->second; 2387b75fbf224c0a2d181c35708a27c514ae798c904Daniel Dunbar return ValueT(); 2397b75fbf224c0a2d181c35708a27c514ae798c904Daniel Dunbar } 2407b75fbf224c0a2d181c35708a27c514ae798c904Daniel Dunbar 2416b345ee9b2833cf1b2f79dc16d06d4060bec36efDan Gohman std::pair<iterator, bool> insert(const std::pair<KeyT, ValueT> &KV) { 24228f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner BucketT *TheBucket; 24328f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner if (LookupBucketFor(KV.first, TheBucket)) 2446b345ee9b2833cf1b2f79dc16d06d4060bec36efDan Gohman return std::make_pair(iterator(TheBucket, Buckets+NumBuckets), 2456b345ee9b2833cf1b2f79dc16d06d4060bec36efDan Gohman false); // Already in map. 2463a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 24728f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner // Otherwise, insert the new element. 2486b345ee9b2833cf1b2f79dc16d06d4060bec36efDan Gohman TheBucket = InsertIntoBucket(KV.first, KV.second, TheBucket); 2496b345ee9b2833cf1b2f79dc16d06d4060bec36efDan Gohman return std::make_pair(iterator(TheBucket, Buckets+NumBuckets), 2506b345ee9b2833cf1b2f79dc16d06d4060bec36efDan Gohman true); 25128f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner } 2523a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 253b6bbe6320b4a60b7399eea08426aec834701d514Chris Lattner /// insert - Range insertion of pairs. 254b6bbe6320b4a60b7399eea08426aec834701d514Chris Lattner template<typename InputIt> 255b6bbe6320b4a60b7399eea08426aec834701d514Chris Lattner void insert(InputIt I, InputIt E) { 256b6bbe6320b4a60b7399eea08426aec834701d514Chris Lattner for (; I != E; ++I) 257b6bbe6320b4a60b7399eea08426aec834701d514Chris Lattner insert(*I); 258b6bbe6320b4a60b7399eea08426aec834701d514Chris Lattner } 259b6bbe6320b4a60b7399eea08426aec834701d514Chris Lattner 2603a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 26170a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner bool erase(const KeyT &Val) { 26270a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner BucketT *TheBucket; 26370a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner if (!LookupBucketFor(Val, TheBucket)) 26470a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner return false; // not in map. 26570a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner 26670a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner TheBucket->second.~ValueT(); 26770a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner TheBucket->first = getTombstoneKey(); 26870a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner --NumEntries; 26904a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner ++NumTombstones; 27070a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner return true; 27170a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner } 27270a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner bool erase(iterator I) { 27370a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner BucketT *TheBucket = &*I; 27470a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner TheBucket->second.~ValueT(); 27570a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner TheBucket->first = getTombstoneKey(); 27670a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner --NumEntries; 27704a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner ++NumTombstones; 27870a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner return true; 27970a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner } 280aef806e9cb021919be8f3a988af0478f3da75758Ted Kremenek 281aef806e9cb021919be8f3a988af0478f3da75758Ted Kremenek value_type& FindAndConstruct(const KeyT &Key) { 2826e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner BucketT *TheBucket; 28328f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner if (LookupBucketFor(Key, TheBucket)) 284aef806e9cb021919be8f3a988af0478f3da75758Ted Kremenek return *TheBucket; 2853a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 286aef806e9cb021919be8f3a988af0478f3da75758Ted Kremenek return *InsertIntoBucket(Key, ValueT(), TheBucket); 287aef806e9cb021919be8f3a988af0478f3da75758Ted Kremenek } 2883a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 289aef806e9cb021919be8f3a988af0478f3da75758Ted Kremenek ValueT &operator[](const KeyT &Key) { 290aef806e9cb021919be8f3a988af0478f3da75758Ted Kremenek return FindAndConstruct(Key).second; 29128f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner } 2923a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 29367280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson DenseMap& operator=(const DenseMap& other) { 29467280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson CopyFrom(other); 2953d345631db71174ffc4997a88c09f21eb9ed052bOwen Anderson return *this; 29667280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson } 2973a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 298bdd376ccb25f251e115fff24b526b4e65e03a1d3Chris Lattner /// isPointerIntoBucketsArray - Return true if the specified pointer points 299bdd376ccb25f251e115fff24b526b4e65e03a1d3Chris Lattner /// somewhere into the DenseMap's array of buckets (i.e. either to a key or 300bdd376ccb25f251e115fff24b526b4e65e03a1d3Chris Lattner /// value in the DenseMap). 301bdd376ccb25f251e115fff24b526b4e65e03a1d3Chris Lattner bool isPointerIntoBucketsArray(const void *Ptr) const { 302bdd376ccb25f251e115fff24b526b4e65e03a1d3Chris Lattner return Ptr >= Buckets && Ptr < Buckets+NumBuckets; 303bdd376ccb25f251e115fff24b526b4e65e03a1d3Chris Lattner } 304bdd376ccb25f251e115fff24b526b4e65e03a1d3Chris Lattner 305bdd376ccb25f251e115fff24b526b4e65e03a1d3Chris Lattner /// getPointerIntoBucketsArray() - Return an opaque pointer into the buckets 306bdd376ccb25f251e115fff24b526b4e65e03a1d3Chris Lattner /// array. In conjunction with the previous method, this can be used to 307bdd376ccb25f251e115fff24b526b4e65e03a1d3Chris Lattner /// determine whether an insertion caused the DenseMap to reallocate. 308bdd376ccb25f251e115fff24b526b4e65e03a1d3Chris Lattner const void *getPointerIntoBucketsArray() const { return Buckets; } 309bdd376ccb25f251e115fff24b526b4e65e03a1d3Chris Lattner 31028f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattnerprivate: 31167280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson void CopyFrom(const DenseMap& other) { 31229ce95511f905df3a63e3b953a4a0179ead46865Owen Anderson if (NumBuckets != 0 && (!KeyInfoT::isPod() || !ValueInfoT::isPod())) { 31367280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey(); 31467280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson for (BucketT *P = Buckets, *E = Buckets+NumBuckets; P != E; ++P) { 31505831c073abbaacbf2fc21ef5ef160872056e075Chris Lattner if (!KeyInfoT::isEqual(P->first, EmptyKey) && 31605831c073abbaacbf2fc21ef5ef160872056e075Chris Lattner !KeyInfoT::isEqual(P->first, TombstoneKey)) 31767280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson P->second.~ValueT(); 31867280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson P->first.~KeyT(); 31967280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson } 32067280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson } 3213a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 32267280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson NumEntries = other.NumEntries; 32367280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson NumTombstones = other.NumTombstones; 3243a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 325d06c59821a1ca0191ea8a326a18509808a02ed03Torok Edwin if (NumBuckets) { 326d06c59821a1ca0191ea8a326a18509808a02ed03Torok Edwin#ifndef NDEBUG 327d06c59821a1ca0191ea8a326a18509808a02ed03Torok Edwin memset(Buckets, 0x5a, sizeof(BucketT)*NumBuckets); 328d06c59821a1ca0191ea8a326a18509808a02ed03Torok Edwin#endif 32908c09496c2fa7c1da027a52d8c410c2ae98481e1Dan Gohman operator delete(Buckets); 330d06c59821a1ca0191ea8a326a18509808a02ed03Torok Edwin } 33108c09496c2fa7c1da027a52d8c410c2ae98481e1Dan Gohman Buckets = static_cast<BucketT*>(operator new(sizeof(BucketT) * 33208c09496c2fa7c1da027a52d8c410c2ae98481e1Dan Gohman other.NumBuckets)); 3333a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 33429ce95511f905df3a63e3b953a4a0179ead46865Owen Anderson if (KeyInfoT::isPod() && ValueInfoT::isPod()) 3359544dc294f63ce116fbab398a8874ebf834cf41eOwen Anderson memcpy(Buckets, other.Buckets, other.NumBuckets * sizeof(BucketT)); 3369544dc294f63ce116fbab398a8874ebf834cf41eOwen Anderson else 3379544dc294f63ce116fbab398a8874ebf834cf41eOwen Anderson for (size_t i = 0; i < other.NumBuckets; ++i) { 3382b7470eb54880ce7f74469d6e09eaf7f0864f8abOwen Anderson new (&Buckets[i].first) KeyT(other.Buckets[i].first); 33905831c073abbaacbf2fc21ef5ef160872056e075Chris Lattner if (!KeyInfoT::isEqual(Buckets[i].first, getEmptyKey()) && 34005831c073abbaacbf2fc21ef5ef160872056e075Chris Lattner !KeyInfoT::isEqual(Buckets[i].first, getTombstoneKey())) 3414938d347723d452786c1a7c1d1b9ec79121b0040Owen Anderson new (&Buckets[i].second) ValueT(other.Buckets[i].second); 3429544dc294f63ce116fbab398a8874ebf834cf41eOwen Anderson } 34367280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson NumBuckets = other.NumBuckets; 34467280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson } 3453a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 34628f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner BucketT *InsertIntoBucket(const KeyT &Key, const ValueT &Value, 34728f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner BucketT *TheBucket) { 34804a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // If the load of the hash table is more than 3/4, or if fewer than 1/8 of 34904a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // the buckets are empty (meaning that many are filled with tombstones), 35004a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // grow the table. 35104a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // 35204a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // The later case is tricky. For example, if we had one empty bucket with 35304a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // tons of tombstones, failing lookups (e.g. for insertion) would have to 35404a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // probe almost the entire table until it found the empty bucket. If the 35504a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // table completely filled with tombstones, no lookup would ever succeed, 35604a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // causing infinite loops in lookup. 357f0e4cac7ebdee07639bd1fc3eadf204f45868556Stuart Hastings ++NumEntries; 35804a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner if (NumEntries*4 >= NumBuckets*3 || 3593a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman NumBuckets-(NumEntries+NumTombstones) < NumBuckets/8) { 360d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin this->grow(NumBuckets * 2); 36128f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner LookupBucketFor(Key, TheBucket); 3626e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 3633a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 36404a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // If we are writing over a tombstone, remember this. 36505831c073abbaacbf2fc21ef5ef160872056e075Chris Lattner if (!KeyInfoT::isEqual(TheBucket->first, getEmptyKey())) 36604a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner --NumTombstones; 3673a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 36828f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner TheBucket->first = Key; 36928f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner new (&TheBucket->second) ValueT(Value); 37028f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner return TheBucket; 3716e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 37228f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner 37370a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner static unsigned getHashValue(const KeyT &Val) { 374a76b1febd4fd258e8054395adedcbd477668d956Chris Lattner return KeyInfoT::getHashValue(Val); 3756e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 37670a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner static const KeyT getEmptyKey() { 377a76b1febd4fd258e8054395adedcbd477668d956Chris Lattner return KeyInfoT::getEmptyKey(); 37870a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner } 37970a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner static const KeyT getTombstoneKey() { 380a76b1febd4fd258e8054395adedcbd477668d956Chris Lattner return KeyInfoT::getTombstoneKey(); 3816e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 3823a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 3836e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner /// LookupBucketFor - Lookup the appropriate bucket for Val, returning it in 3846e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner /// FoundBucket. If the bucket contains the key and a value, this returns 3856e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner /// true, otherwise it returns a bucket with an empty marker or tombstone and 3866e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner /// returns false. 3876e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner bool LookupBucketFor(const KeyT &Val, BucketT *&FoundBucket) const { 3886e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner unsigned BucketNo = getHashValue(Val); 3896e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner unsigned ProbeAmt = 1; 3906e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner BucketT *BucketsPtr = Buckets; 3913a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 3926e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // FoundTombstone - Keep track of whether we find a tombstone while probing. 3936e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner BucketT *FoundTombstone = 0; 3946e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner const KeyT EmptyKey = getEmptyKey(); 3956e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner const KeyT TombstoneKey = getTombstoneKey(); 39605831c073abbaacbf2fc21ef5ef160872056e075Chris Lattner assert(!KeyInfoT::isEqual(Val, EmptyKey) && 39705831c073abbaacbf2fc21ef5ef160872056e075Chris Lattner !KeyInfoT::isEqual(Val, TombstoneKey) && 3986e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner "Empty/Tombstone value shouldn't be inserted into map!"); 3993a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 4006e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner while (1) { 4016e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner BucketT *ThisBucket = BucketsPtr + (BucketNo & (NumBuckets-1)); 4026e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // Found Val's bucket? If so, return it. 40376c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattner if (KeyInfoT::isEqual(ThisBucket->first, Val)) { 4046e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner FoundBucket = ThisBucket; 4056e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner return true; 4066e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 4073a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 4086e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // If we found an empty bucket, the key doesn't exist in the set. 4096e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // Insert it and return the default value. 41076c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattner if (KeyInfoT::isEqual(ThisBucket->first, EmptyKey)) { 4116e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // If we've already seen a tombstone while probing, fill it in instead 4126e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // of the empty bucket we eventually probed to. 4136e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner if (FoundTombstone) ThisBucket = FoundTombstone; 4146e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner FoundBucket = FoundTombstone ? FoundTombstone : ThisBucket; 4156e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner return false; 4166e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 4173a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 4186e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // If this is a tombstone, remember it. If Val ends up not in the map, we 4196e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // prefer to return it than something that would require more probing. 42076c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattner if (KeyInfoT::isEqual(ThisBucket->first, TombstoneKey) && !FoundTombstone) 4216e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner FoundTombstone = ThisBucket; // Remember the first tombstone found. 4223a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 4236e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // Otherwise, it's a hash collision or a tombstone, continue quadratic 4246e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // probing. 4256e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner BucketNo += ProbeAmt++; 4266e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 4276e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 4286e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 4296e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner void init(unsigned InitBuckets) { 4306e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner NumEntries = 0; 43104a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner NumTombstones = 0; 4326e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner NumBuckets = InitBuckets; 433ae9f3a3b7c915f725aef5a7250e88eaeddda03c6Anton Korobeynikov assert(InitBuckets && (InitBuckets & (InitBuckets-1)) == 0 && 4346e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner "# initial buckets must be a power of two!"); 43508c09496c2fa7c1da027a52d8c410c2ae98481e1Dan Gohman Buckets = static_cast<BucketT*>(operator new(sizeof(BucketT)*InitBuckets)); 4366e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // Initialize all the keys to EmptyKey. 4376e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner const KeyT EmptyKey = getEmptyKey(); 4386e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner for (unsigned i = 0; i != InitBuckets; ++i) 439f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner new (&Buckets[i].first) KeyT(EmptyKey); 4406e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 4413a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 442d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin void grow(unsigned AtLeast) { 4436e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner unsigned OldNumBuckets = NumBuckets; 4446e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner BucketT *OldBuckets = Buckets; 4453a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 4466e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // Double the number of buckets. 447d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin while (NumBuckets <= AtLeast) 448d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin NumBuckets <<= 1; 44904a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner NumTombstones = 0; 45008c09496c2fa7c1da027a52d8c410c2ae98481e1Dan Gohman Buckets = static_cast<BucketT*>(operator new(sizeof(BucketT)*NumBuckets)); 4516e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 4526e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // Initialize all the keys to EmptyKey. 4536e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner const KeyT EmptyKey = getEmptyKey(); 4546e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner for (unsigned i = 0, e = NumBuckets; i != e; ++i) 455f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner new (&Buckets[i].first) KeyT(EmptyKey); 4566e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 4576e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // Insert all the old elements. 4586e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner const KeyT TombstoneKey = getTombstoneKey(); 4596e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner for (BucketT *B = OldBuckets, *E = OldBuckets+OldNumBuckets; B != E; ++B) { 46005831c073abbaacbf2fc21ef5ef160872056e075Chris Lattner if (!KeyInfoT::isEqual(B->first, EmptyKey) && 46105831c073abbaacbf2fc21ef5ef160872056e075Chris Lattner !KeyInfoT::isEqual(B->first, TombstoneKey)) { 4626e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // Insert the key/value into the new table. 4636e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner BucketT *DestBucket; 464f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner bool FoundVal = LookupBucketFor(B->first, DestBucket); 465137d4b253384adce88bfa2a1c37695d90f0a9d6cChris Lattner FoundVal = FoundVal; // silence warning. 4666e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner assert(!FoundVal && "Key already in new map?"); 467f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner DestBucket->first = B->first; 468f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner new (&DestBucket->second) ValueT(B->second); 4693a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 4706e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // Free the value. 471f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner B->second.~ValueT(); 4726e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 473f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner B->first.~KeyT(); 4746e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 4753a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 476d06c59821a1ca0191ea8a326a18509808a02ed03Torok Edwin#ifndef NDEBUG 477d06c59821a1ca0191ea8a326a18509808a02ed03Torok Edwin memset(OldBuckets, 0x5a, sizeof(BucketT)*OldNumBuckets); 478d06c59821a1ca0191ea8a326a18509808a02ed03Torok Edwin#endif 4796e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // Free the old table. 48008c09496c2fa7c1da027a52d8c410c2ae98481e1Dan Gohman operator delete(OldBuckets); 4816e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 4823a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 4836ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson void shrink_and_clear() { 4846ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson unsigned OldNumBuckets = NumBuckets; 4856ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson BucketT *OldBuckets = Buckets; 4863a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 487398b40671b13018f88371b74822fa8ee2638577eOwen Anderson // Reduce the number of buckets. 488398b40671b13018f88371b74822fa8ee2638577eOwen Anderson NumBuckets = NumEntries > 32 ? 1 << (Log2_32_Ceil(NumEntries) + 1) 489398b40671b13018f88371b74822fa8ee2638577eOwen Anderson : 64; 4906ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson NumTombstones = 0; 49108c09496c2fa7c1da027a52d8c410c2ae98481e1Dan Gohman Buckets = static_cast<BucketT*>(operator new(sizeof(BucketT)*NumBuckets)); 4926ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson 4936ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson // Initialize all the keys to EmptyKey. 4946ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson const KeyT EmptyKey = getEmptyKey(); 4956ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson for (unsigned i = 0, e = NumBuckets; i != e; ++i) 4966ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson new (&Buckets[i].first) KeyT(EmptyKey); 4976ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson 4986ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson // Free the old buckets. 4996ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson const KeyT TombstoneKey = getTombstoneKey(); 5006ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson for (BucketT *B = OldBuckets, *E = OldBuckets+OldNumBuckets; B != E; ++B) { 50105831c073abbaacbf2fc21ef5ef160872056e075Chris Lattner if (!KeyInfoT::isEqual(B->first, EmptyKey) && 50205831c073abbaacbf2fc21ef5ef160872056e075Chris Lattner !KeyInfoT::isEqual(B->first, TombstoneKey)) { 5036ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson // Free the value. 5046ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson B->second.~ValueT(); 5056ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson } 5066ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson B->first.~KeyT(); 5076ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson } 5083a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 509d06c59821a1ca0191ea8a326a18509808a02ed03Torok Edwin#ifndef NDEBUG 510d06c59821a1ca0191ea8a326a18509808a02ed03Torok Edwin memset(OldBuckets, 0x5a, sizeof(BucketT)*OldNumBuckets); 511d06c59821a1ca0191ea8a326a18509808a02ed03Torok Edwin#endif 5126ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson // Free the old table. 51308c09496c2fa7c1da027a52d8c410c2ae98481e1Dan Gohman operator delete(OldBuckets); 5143a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 5156ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson NumEntries = 0; 5166ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson } 5176e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner}; 5186e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 51929ce95511f905df3a63e3b953a4a0179ead46865Owen Andersontemplate<typename KeyT, typename ValueT, typename KeyInfoT, typename ValueInfoT> 520f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattnerclass DenseMapIterator { 521f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner typedef std::pair<KeyT, ValueT> BucketT; 52270a76a633ed5101dbe472404efd989f4f1b3669cChris Lattnerprotected: 523f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner const BucketT *Ptr, *End; 524f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattnerpublic: 52513e781ebe7a39e008dd5e5de78983e095e8a1d02David Greene DenseMapIterator(void) : Ptr(0), End(0) {} 52613e781ebe7a39e008dd5e5de78983e095e8a1d02David Greene 527f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner DenseMapIterator(const BucketT *Pos, const BucketT *E) : Ptr(Pos), End(E) { 528f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner AdvancePastEmptyBuckets(); 529f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner } 5303a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 53170a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner std::pair<KeyT, ValueT> &operator*() const { 53270a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner return *const_cast<BucketT*>(Ptr); 533f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner } 53470a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner std::pair<KeyT, ValueT> *operator->() const { 53570a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner return const_cast<BucketT*>(Ptr); 536f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner } 5373a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 538f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner bool operator==(const DenseMapIterator &RHS) const { 539f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner return Ptr == RHS.Ptr; 540f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner } 541f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner bool operator!=(const DenseMapIterator &RHS) const { 542f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner return Ptr != RHS.Ptr; 543f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner } 5443a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 545f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner inline DenseMapIterator& operator++() { // Preincrement 546f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner ++Ptr; 547f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner AdvancePastEmptyBuckets(); 548f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner return *this; 549f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner } 550f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner DenseMapIterator operator++(int) { // Postincrement 551f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner DenseMapIterator tmp = *this; ++*this; return tmp; 552f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner } 5533a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 554f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattnerprivate: 555f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner void AdvancePastEmptyBuckets() { 556a76b1febd4fd258e8054395adedcbd477668d956Chris Lattner const KeyT Empty = KeyInfoT::getEmptyKey(); 557a76b1febd4fd258e8054395adedcbd477668d956Chris Lattner const KeyT Tombstone = KeyInfoT::getTombstoneKey(); 558f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner 5593a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman while (Ptr != End && 56076c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattner (KeyInfoT::isEqual(Ptr->first, Empty) || 56176c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattner KeyInfoT::isEqual(Ptr->first, Tombstone))) 562f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner ++Ptr; 563f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner } 564f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner}; 565f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner 56629ce95511f905df3a63e3b953a4a0179ead46865Owen Andersontemplate<typename KeyT, typename ValueT, typename KeyInfoT, typename ValueInfoT> 567a76b1febd4fd258e8054395adedcbd477668d956Chris Lattnerclass DenseMapConstIterator : public DenseMapIterator<KeyT, ValueT, KeyInfoT> { 56870a76a633ed5101dbe472404efd989f4f1b3669cChris Lattnerpublic: 56913e781ebe7a39e008dd5e5de78983e095e8a1d02David Greene DenseMapConstIterator(void) : DenseMapIterator<KeyT, ValueT, KeyInfoT>() {} 57070a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner DenseMapConstIterator(const std::pair<KeyT, ValueT> *Pos, 57170a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner const std::pair<KeyT, ValueT> *E) 572569b935e6b23c4a0e4ebb2c96603974310ef0587Chris Lattner : DenseMapIterator<KeyT, ValueT, KeyInfoT>(Pos, E) { 57370a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner } 57470a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner const std::pair<KeyT, ValueT> &operator*() const { 57570a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner return *this->Ptr; 57670a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner } 57770a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner const std::pair<KeyT, ValueT> *operator->() const { 57870a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner return this->Ptr; 57970a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner } 58070a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner}; 581f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner 5826e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner} // end namespace llvm 5836e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 5846e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner#endif 585