DenseMap.h revision 32859c71d6ba9cd5e38662611a73d82335f4ba41
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" 19fb3af88ba75898896714d49c608b8daa4f106636Dan Gohman#include "llvm/ADT/DenseMapInfo.h" 206e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner#include <cassert> 21d06c59821a1ca0191ea8a326a18509808a02ed03Torok Edwin#include <cstring> 22f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner#include <utility> 2311d8fb960963a1f8a7e2b2972bc560a5b24cf216Chris Lattner#include <new> 246e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 256e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattnernamespace llvm { 263a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 273a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukmantemplate<typename KeyT, typename ValueT, 2876c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattner typename KeyInfoT = DenseMapInfo<KeyT>, 2976c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattner typename ValueInfoT = DenseMapInfo<ValueT> > 30f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattnerclass DenseMapIterator; 31a76b1febd4fd258e8054395adedcbd477668d956Chris Lattnertemplate<typename KeyT, typename ValueT, 3276c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattner typename KeyInfoT = DenseMapInfo<KeyT>, 3376c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattner typename ValueInfoT = DenseMapInfo<ValueT> > 3470a76a633ed5101dbe472404efd989f4f1b3669cChris Lattnerclass DenseMapConstIterator; 356e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 36a76b1febd4fd258e8054395adedcbd477668d956Chris Lattnertemplate<typename KeyT, typename ValueT, 3776c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattner typename KeyInfoT = DenseMapInfo<KeyT>, 3876c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattner typename ValueInfoT = DenseMapInfo<ValueT> > 396e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattnerclass DenseMap { 40f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner typedef std::pair<KeyT, ValueT> BucketT; 416e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner unsigned NumBuckets; 426e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner BucketT *Buckets; 433a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 446e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner unsigned NumEntries; 4504a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner unsigned NumTombstones; 466e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattnerpublic: 4713e781ebe7a39e008dd5e5de78983e095e8a1d02David Greene typedef KeyT key_type; 4813e781ebe7a39e008dd5e5de78983e095e8a1d02David Greene typedef ValueT mapped_type; 49aef806e9cb021919be8f3a988af0478f3da75758Ted Kremenek typedef BucketT value_type; 503a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 5167280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson DenseMap(const DenseMap& other) { 5267280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson NumBuckets = 0; 5367280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson CopyFrom(other); 5467280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson } 553a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 565a5f6b6e38b7155200903816f22501cce4ca36a7Chris Lattner explicit DenseMap(unsigned NumInitBuckets = 64) { 576e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner init(NumInitBuckets); 586e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 593a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 606e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner ~DenseMap() { 616e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey(); 626e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner for (BucketT *P = Buckets, *E = Buckets+NumBuckets; P != E; ++P) { 6305831c073abbaacbf2fc21ef5ef160872056e075Chris Lattner if (!KeyInfoT::isEqual(P->first, EmptyKey) && 6405831c073abbaacbf2fc21ef5ef160872056e075Chris Lattner !KeyInfoT::isEqual(P->first, TombstoneKey)) 65f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner P->second.~ValueT(); 66f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner P->first.~KeyT(); 676e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 68d06c59821a1ca0191ea8a326a18509808a02ed03Torok Edwin#ifndef NDEBUG 69d06c59821a1ca0191ea8a326a18509808a02ed03Torok Edwin memset(Buckets, 0x5a, sizeof(BucketT)*NumBuckets); 70d06c59821a1ca0191ea8a326a18509808a02ed03Torok Edwin#endif 7108c09496c2fa7c1da027a52d8c410c2ae98481e1Dan Gohman operator delete(Buckets); 726e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 733a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 74a76b1febd4fd258e8054395adedcbd477668d956Chris Lattner typedef DenseMapIterator<KeyT, ValueT, KeyInfoT> iterator; 75a76b1febd4fd258e8054395adedcbd477668d956Chris Lattner typedef DenseMapConstIterator<KeyT, ValueT, KeyInfoT> const_iterator; 7670a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner inline iterator begin() { 77a76b1febd4fd258e8054395adedcbd477668d956Chris Lattner return iterator(Buckets, Buckets+NumBuckets); 7870a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner } 7970a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner inline iterator end() { 80a76b1febd4fd258e8054395adedcbd477668d956Chris Lattner return iterator(Buckets+NumBuckets, Buckets+NumBuckets); 8170a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner } 8270a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner inline const_iterator begin() const { 83a76b1febd4fd258e8054395adedcbd477668d956Chris Lattner return const_iterator(Buckets, Buckets+NumBuckets); 8470a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner } 8570a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner inline const_iterator end() const { 86a76b1febd4fd258e8054395adedcbd477668d956Chris Lattner return const_iterator(Buckets+NumBuckets, Buckets+NumBuckets); 8770a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner } 883a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 8970a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner bool empty() const { return NumEntries == 0; } 906e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner unsigned size() const { return NumEntries; } 91d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin 92d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin /// Grow the densemap so that it has at least Size buckets. Does not shrink 93d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin void resize(size_t Size) { grow(Size); } 943a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 956e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner void clear() { 9632859c71d6ba9cd5e38662611a73d82335f4ba41Chris Lattner if (NumEntries == 0 && NumTombstones == 0) return; 9732859c71d6ba9cd5e38662611a73d82335f4ba41Chris Lattner 9842e4bdf2577946380ce1529d5716e48b33d4186dChris Lattner // If the capacity of the array is huge, and the # elements used is small, 9942e4bdf2577946380ce1529d5716e48b33d4186dChris Lattner // shrink the array. 1006ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson if (NumEntries * 4 < NumBuckets && NumBuckets > 64) { 1016ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson shrink_and_clear(); 1026ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson return; 1036ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson } 1043a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 1056e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey(); 1066e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner for (BucketT *P = Buckets, *E = Buckets+NumBuckets; P != E; ++P) { 10705831c073abbaacbf2fc21ef5ef160872056e075Chris Lattner if (!KeyInfoT::isEqual(P->first, EmptyKey)) { 10805831c073abbaacbf2fc21ef5ef160872056e075Chris Lattner if (!KeyInfoT::isEqual(P->first, TombstoneKey)) { 1097b54452c84e478ab4d49ac08759ca4ec1badf2b2Chris Lattner P->second.~ValueT(); 1107b54452c84e478ab4d49ac08759ca4ec1badf2b2Chris Lattner --NumEntries; 1117b54452c84e478ab4d49ac08759ca4ec1badf2b2Chris Lattner } 112f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner P->first = EmptyKey; 1136e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 1146e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 1156e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner assert(NumEntries == 0 && "Node count imbalance!"); 11604a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner NumTombstones = 0; 1176e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 1186ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson 1196e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner /// count - Return true if the specified key is in the map. 1206e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner bool count(const KeyT &Val) const { 1216e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner BucketT *TheBucket; 1226e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner return LookupBucketFor(Val, TheBucket); 1236e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 1243a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 125569b935e6b23c4a0e4ebb2c96603974310ef0587Chris Lattner iterator find(const KeyT &Val) { 12670a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner BucketT *TheBucket; 12770a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner if (LookupBucketFor(Val, TheBucket)) 12870a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner return iterator(TheBucket, Buckets+NumBuckets); 12970a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner return end(); 13070a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner } 131569b935e6b23c4a0e4ebb2c96603974310ef0587Chris Lattner const_iterator find(const KeyT &Val) const { 132569b935e6b23c4a0e4ebb2c96603974310ef0587Chris Lattner BucketT *TheBucket; 133569b935e6b23c4a0e4ebb2c96603974310ef0587Chris Lattner if (LookupBucketFor(Val, TheBucket)) 134569b935e6b23c4a0e4ebb2c96603974310ef0587Chris Lattner return const_iterator(TheBucket, Buckets+NumBuckets); 135569b935e6b23c4a0e4ebb2c96603974310ef0587Chris Lattner return end(); 136569b935e6b23c4a0e4ebb2c96603974310ef0587Chris Lattner } 1373a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 1387b75fbf224c0a2d181c35708a27c514ae798c904Daniel Dunbar /// lookup - Return the entry for the specified key, or a default 1397b75fbf224c0a2d181c35708a27c514ae798c904Daniel Dunbar /// constructed value if no such entry exists. 1407b75fbf224c0a2d181c35708a27c514ae798c904Daniel Dunbar ValueT lookup(const KeyT &Val) const { 1417b75fbf224c0a2d181c35708a27c514ae798c904Daniel Dunbar BucketT *TheBucket; 1427b75fbf224c0a2d181c35708a27c514ae798c904Daniel Dunbar if (LookupBucketFor(Val, TheBucket)) 1437b75fbf224c0a2d181c35708a27c514ae798c904Daniel Dunbar return TheBucket->second; 1447b75fbf224c0a2d181c35708a27c514ae798c904Daniel Dunbar return ValueT(); 1457b75fbf224c0a2d181c35708a27c514ae798c904Daniel Dunbar } 1467b75fbf224c0a2d181c35708a27c514ae798c904Daniel Dunbar 1476b345ee9b2833cf1b2f79dc16d06d4060bec36efDan Gohman std::pair<iterator, bool> insert(const std::pair<KeyT, ValueT> &KV) { 14828f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner BucketT *TheBucket; 14928f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner if (LookupBucketFor(KV.first, TheBucket)) 1506b345ee9b2833cf1b2f79dc16d06d4060bec36efDan Gohman return std::make_pair(iterator(TheBucket, Buckets+NumBuckets), 1516b345ee9b2833cf1b2f79dc16d06d4060bec36efDan Gohman false); // Already in map. 1523a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 15328f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner // Otherwise, insert the new element. 1546b345ee9b2833cf1b2f79dc16d06d4060bec36efDan Gohman TheBucket = InsertIntoBucket(KV.first, KV.second, TheBucket); 1556b345ee9b2833cf1b2f79dc16d06d4060bec36efDan Gohman return std::make_pair(iterator(TheBucket, Buckets+NumBuckets), 1566b345ee9b2833cf1b2f79dc16d06d4060bec36efDan Gohman true); 15728f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner } 1583a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 159b6bbe6320b4a60b7399eea08426aec834701d514Chris Lattner /// insert - Range insertion of pairs. 160b6bbe6320b4a60b7399eea08426aec834701d514Chris Lattner template<typename InputIt> 161b6bbe6320b4a60b7399eea08426aec834701d514Chris Lattner void insert(InputIt I, InputIt E) { 162b6bbe6320b4a60b7399eea08426aec834701d514Chris Lattner for (; I != E; ++I) 163b6bbe6320b4a60b7399eea08426aec834701d514Chris Lattner insert(*I); 164b6bbe6320b4a60b7399eea08426aec834701d514Chris Lattner } 165b6bbe6320b4a60b7399eea08426aec834701d514Chris Lattner 1663a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 16770a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner bool erase(const KeyT &Val) { 16870a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner BucketT *TheBucket; 16970a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner if (!LookupBucketFor(Val, TheBucket)) 17070a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner return false; // not in map. 17170a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner 17270a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner TheBucket->second.~ValueT(); 17370a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner TheBucket->first = getTombstoneKey(); 17470a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner --NumEntries; 17504a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner ++NumTombstones; 17670a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner return true; 17770a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner } 17870a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner bool erase(iterator I) { 17970a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner BucketT *TheBucket = &*I; 18070a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner TheBucket->second.~ValueT(); 18170a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner TheBucket->first = getTombstoneKey(); 18270a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner --NumEntries; 18304a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner ++NumTombstones; 18470a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner return true; 18570a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner } 186aef806e9cb021919be8f3a988af0478f3da75758Ted Kremenek 187aef806e9cb021919be8f3a988af0478f3da75758Ted Kremenek value_type& FindAndConstruct(const KeyT &Key) { 1886e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner BucketT *TheBucket; 18928f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner if (LookupBucketFor(Key, TheBucket)) 190aef806e9cb021919be8f3a988af0478f3da75758Ted Kremenek return *TheBucket; 1913a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 192aef806e9cb021919be8f3a988af0478f3da75758Ted Kremenek return *InsertIntoBucket(Key, ValueT(), TheBucket); 193aef806e9cb021919be8f3a988af0478f3da75758Ted Kremenek } 1943a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 195aef806e9cb021919be8f3a988af0478f3da75758Ted Kremenek ValueT &operator[](const KeyT &Key) { 196aef806e9cb021919be8f3a988af0478f3da75758Ted Kremenek return FindAndConstruct(Key).second; 19728f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner } 1983a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 19967280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson DenseMap& operator=(const DenseMap& other) { 20067280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson CopyFrom(other); 2013d345631db71174ffc4997a88c09f21eb9ed052bOwen Anderson return *this; 20267280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson } 2033a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 204bdd376ccb25f251e115fff24b526b4e65e03a1d3Chris Lattner /// isPointerIntoBucketsArray - Return true if the specified pointer points 205bdd376ccb25f251e115fff24b526b4e65e03a1d3Chris Lattner /// somewhere into the DenseMap's array of buckets (i.e. either to a key or 206bdd376ccb25f251e115fff24b526b4e65e03a1d3Chris Lattner /// value in the DenseMap). 207bdd376ccb25f251e115fff24b526b4e65e03a1d3Chris Lattner bool isPointerIntoBucketsArray(const void *Ptr) const { 208bdd376ccb25f251e115fff24b526b4e65e03a1d3Chris Lattner return Ptr >= Buckets && Ptr < Buckets+NumBuckets; 209bdd376ccb25f251e115fff24b526b4e65e03a1d3Chris Lattner } 210bdd376ccb25f251e115fff24b526b4e65e03a1d3Chris Lattner 211bdd376ccb25f251e115fff24b526b4e65e03a1d3Chris Lattner /// getPointerIntoBucketsArray() - Return an opaque pointer into the buckets 212bdd376ccb25f251e115fff24b526b4e65e03a1d3Chris Lattner /// array. In conjunction with the previous method, this can be used to 213bdd376ccb25f251e115fff24b526b4e65e03a1d3Chris Lattner /// determine whether an insertion caused the DenseMap to reallocate. 214bdd376ccb25f251e115fff24b526b4e65e03a1d3Chris Lattner const void *getPointerIntoBucketsArray() const { return Buckets; } 215bdd376ccb25f251e115fff24b526b4e65e03a1d3Chris Lattner 21628f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattnerprivate: 21767280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson void CopyFrom(const DenseMap& other) { 21829ce95511f905df3a63e3b953a4a0179ead46865Owen Anderson if (NumBuckets != 0 && (!KeyInfoT::isPod() || !ValueInfoT::isPod())) { 21967280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey(); 22067280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson for (BucketT *P = Buckets, *E = Buckets+NumBuckets; P != E; ++P) { 22105831c073abbaacbf2fc21ef5ef160872056e075Chris Lattner if (!KeyInfoT::isEqual(P->first, EmptyKey) && 22205831c073abbaacbf2fc21ef5ef160872056e075Chris Lattner !KeyInfoT::isEqual(P->first, TombstoneKey)) 22367280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson P->second.~ValueT(); 22467280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson P->first.~KeyT(); 22567280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson } 22667280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson } 2273a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 22867280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson NumEntries = other.NumEntries; 22967280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson NumTombstones = other.NumTombstones; 2303a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 231d06c59821a1ca0191ea8a326a18509808a02ed03Torok Edwin if (NumBuckets) { 232d06c59821a1ca0191ea8a326a18509808a02ed03Torok Edwin#ifndef NDEBUG 233d06c59821a1ca0191ea8a326a18509808a02ed03Torok Edwin memset(Buckets, 0x5a, sizeof(BucketT)*NumBuckets); 234d06c59821a1ca0191ea8a326a18509808a02ed03Torok Edwin#endif 23508c09496c2fa7c1da027a52d8c410c2ae98481e1Dan Gohman operator delete(Buckets); 236d06c59821a1ca0191ea8a326a18509808a02ed03Torok Edwin } 23708c09496c2fa7c1da027a52d8c410c2ae98481e1Dan Gohman Buckets = static_cast<BucketT*>(operator new(sizeof(BucketT) * 23808c09496c2fa7c1da027a52d8c410c2ae98481e1Dan Gohman other.NumBuckets)); 2393a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 24029ce95511f905df3a63e3b953a4a0179ead46865Owen Anderson if (KeyInfoT::isPod() && ValueInfoT::isPod()) 2419544dc294f63ce116fbab398a8874ebf834cf41eOwen Anderson memcpy(Buckets, other.Buckets, other.NumBuckets * sizeof(BucketT)); 2429544dc294f63ce116fbab398a8874ebf834cf41eOwen Anderson else 2439544dc294f63ce116fbab398a8874ebf834cf41eOwen Anderson for (size_t i = 0; i < other.NumBuckets; ++i) { 2442b7470eb54880ce7f74469d6e09eaf7f0864f8abOwen Anderson new (&Buckets[i].first) KeyT(other.Buckets[i].first); 24505831c073abbaacbf2fc21ef5ef160872056e075Chris Lattner if (!KeyInfoT::isEqual(Buckets[i].first, getEmptyKey()) && 24605831c073abbaacbf2fc21ef5ef160872056e075Chris Lattner !KeyInfoT::isEqual(Buckets[i].first, getTombstoneKey())) 2474938d347723d452786c1a7c1d1b9ec79121b0040Owen Anderson new (&Buckets[i].second) ValueT(other.Buckets[i].second); 2489544dc294f63ce116fbab398a8874ebf834cf41eOwen Anderson } 24967280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson NumBuckets = other.NumBuckets; 25067280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson } 2513a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 25228f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner BucketT *InsertIntoBucket(const KeyT &Key, const ValueT &Value, 25328f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner BucketT *TheBucket) { 25404a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // If the load of the hash table is more than 3/4, or if fewer than 1/8 of 25504a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // the buckets are empty (meaning that many are filled with tombstones), 25604a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // grow the table. 25704a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // 25804a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // The later case is tricky. For example, if we had one empty bucket with 25904a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // tons of tombstones, failing lookups (e.g. for insertion) would have to 26004a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // probe almost the entire table until it found the empty bucket. If the 26104a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // table completely filled with tombstones, no lookup would ever succeed, 26204a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // causing infinite loops in lookup. 263f0e4cac7ebdee07639bd1fc3eadf204f45868556Stuart Hastings ++NumEntries; 26404a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner if (NumEntries*4 >= NumBuckets*3 || 2653a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman NumBuckets-(NumEntries+NumTombstones) < NumBuckets/8) { 266d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin this->grow(NumBuckets * 2); 26728f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner LookupBucketFor(Key, TheBucket); 2686e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 2693a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 27004a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // If we are writing over a tombstone, remember this. 27105831c073abbaacbf2fc21ef5ef160872056e075Chris Lattner if (!KeyInfoT::isEqual(TheBucket->first, getEmptyKey())) 27204a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner --NumTombstones; 2733a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 27428f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner TheBucket->first = Key; 27528f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner new (&TheBucket->second) ValueT(Value); 27628f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner return TheBucket; 2776e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 27828f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner 27970a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner static unsigned getHashValue(const KeyT &Val) { 280a76b1febd4fd258e8054395adedcbd477668d956Chris Lattner return KeyInfoT::getHashValue(Val); 2816e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 28270a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner static const KeyT getEmptyKey() { 283a76b1febd4fd258e8054395adedcbd477668d956Chris Lattner return KeyInfoT::getEmptyKey(); 28470a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner } 28570a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner static const KeyT getTombstoneKey() { 286a76b1febd4fd258e8054395adedcbd477668d956Chris Lattner return KeyInfoT::getTombstoneKey(); 2876e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 2883a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 2896e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner /// LookupBucketFor - Lookup the appropriate bucket for Val, returning it in 2906e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner /// FoundBucket. If the bucket contains the key and a value, this returns 2916e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner /// true, otherwise it returns a bucket with an empty marker or tombstone and 2926e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner /// returns false. 2936e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner bool LookupBucketFor(const KeyT &Val, BucketT *&FoundBucket) const { 2946e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner unsigned BucketNo = getHashValue(Val); 2956e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner unsigned ProbeAmt = 1; 2966e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner BucketT *BucketsPtr = Buckets; 2973a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 2986e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // FoundTombstone - Keep track of whether we find a tombstone while probing. 2996e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner BucketT *FoundTombstone = 0; 3006e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner const KeyT EmptyKey = getEmptyKey(); 3016e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner const KeyT TombstoneKey = getTombstoneKey(); 30205831c073abbaacbf2fc21ef5ef160872056e075Chris Lattner assert(!KeyInfoT::isEqual(Val, EmptyKey) && 30305831c073abbaacbf2fc21ef5ef160872056e075Chris Lattner !KeyInfoT::isEqual(Val, TombstoneKey) && 3046e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner "Empty/Tombstone value shouldn't be inserted into map!"); 3053a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 3066e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner while (1) { 3076e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner BucketT *ThisBucket = BucketsPtr + (BucketNo & (NumBuckets-1)); 3086e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // Found Val's bucket? If so, return it. 30976c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattner if (KeyInfoT::isEqual(ThisBucket->first, Val)) { 3106e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner FoundBucket = ThisBucket; 3116e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner return true; 3126e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 3133a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 3146e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // If we found an empty bucket, the key doesn't exist in the set. 3156e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // Insert it and return the default value. 31676c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattner if (KeyInfoT::isEqual(ThisBucket->first, EmptyKey)) { 3176e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // If we've already seen a tombstone while probing, fill it in instead 3186e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // of the empty bucket we eventually probed to. 3196e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner if (FoundTombstone) ThisBucket = FoundTombstone; 3206e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner FoundBucket = FoundTombstone ? FoundTombstone : ThisBucket; 3216e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner return false; 3226e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 3233a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 3246e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // If this is a tombstone, remember it. If Val ends up not in the map, we 3256e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // prefer to return it than something that would require more probing. 32676c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattner if (KeyInfoT::isEqual(ThisBucket->first, TombstoneKey) && !FoundTombstone) 3276e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner FoundTombstone = ThisBucket; // Remember the first tombstone found. 3283a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 3296e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // Otherwise, it's a hash collision or a tombstone, continue quadratic 3306e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // probing. 3316e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner BucketNo += ProbeAmt++; 3326e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 3336e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 3346e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 3356e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner void init(unsigned InitBuckets) { 3366e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner NumEntries = 0; 33704a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner NumTombstones = 0; 3386e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner NumBuckets = InitBuckets; 339ae9f3a3b7c915f725aef5a7250e88eaeddda03c6Anton Korobeynikov assert(InitBuckets && (InitBuckets & (InitBuckets-1)) == 0 && 3406e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner "# initial buckets must be a power of two!"); 34108c09496c2fa7c1da027a52d8c410c2ae98481e1Dan Gohman Buckets = static_cast<BucketT*>(operator new(sizeof(BucketT)*InitBuckets)); 3426e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // Initialize all the keys to EmptyKey. 3436e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner const KeyT EmptyKey = getEmptyKey(); 3446e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner for (unsigned i = 0; i != InitBuckets; ++i) 345f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner new (&Buckets[i].first) KeyT(EmptyKey); 3466e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 3473a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 348d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin void grow(unsigned AtLeast) { 3496e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner unsigned OldNumBuckets = NumBuckets; 3506e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner BucketT *OldBuckets = Buckets; 3513a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 3526e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // Double the number of buckets. 353d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin while (NumBuckets <= AtLeast) 354d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin NumBuckets <<= 1; 35504a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner NumTombstones = 0; 35608c09496c2fa7c1da027a52d8c410c2ae98481e1Dan Gohman Buckets = static_cast<BucketT*>(operator new(sizeof(BucketT)*NumBuckets)); 3576e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 3586e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // Initialize all the keys to EmptyKey. 3596e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner const KeyT EmptyKey = getEmptyKey(); 3606e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner for (unsigned i = 0, e = NumBuckets; i != e; ++i) 361f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner new (&Buckets[i].first) KeyT(EmptyKey); 3626e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 3636e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // Insert all the old elements. 3646e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner const KeyT TombstoneKey = getTombstoneKey(); 3656e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner for (BucketT *B = OldBuckets, *E = OldBuckets+OldNumBuckets; B != E; ++B) { 36605831c073abbaacbf2fc21ef5ef160872056e075Chris Lattner if (!KeyInfoT::isEqual(B->first, EmptyKey) && 36705831c073abbaacbf2fc21ef5ef160872056e075Chris Lattner !KeyInfoT::isEqual(B->first, TombstoneKey)) { 3686e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // Insert the key/value into the new table. 3696e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner BucketT *DestBucket; 370f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner bool FoundVal = LookupBucketFor(B->first, DestBucket); 371137d4b253384adce88bfa2a1c37695d90f0a9d6cChris Lattner FoundVal = FoundVal; // silence warning. 3726e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner assert(!FoundVal && "Key already in new map?"); 373f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner DestBucket->first = B->first; 374f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner new (&DestBucket->second) ValueT(B->second); 3753a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 3766e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // Free the value. 377f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner B->second.~ValueT(); 3786e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 379f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner B->first.~KeyT(); 3806e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 3813a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 382d06c59821a1ca0191ea8a326a18509808a02ed03Torok Edwin#ifndef NDEBUG 383d06c59821a1ca0191ea8a326a18509808a02ed03Torok Edwin memset(OldBuckets, 0x5a, sizeof(BucketT)*OldNumBuckets); 384d06c59821a1ca0191ea8a326a18509808a02ed03Torok Edwin#endif 3856e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // Free the old table. 38608c09496c2fa7c1da027a52d8c410c2ae98481e1Dan Gohman operator delete(OldBuckets); 3876e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 3883a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 3896ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson void shrink_and_clear() { 3906ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson unsigned OldNumBuckets = NumBuckets; 3916ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson BucketT *OldBuckets = Buckets; 3923a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 393398b40671b13018f88371b74822fa8ee2638577eOwen Anderson // Reduce the number of buckets. 394398b40671b13018f88371b74822fa8ee2638577eOwen Anderson NumBuckets = NumEntries > 32 ? 1 << (Log2_32_Ceil(NumEntries) + 1) 395398b40671b13018f88371b74822fa8ee2638577eOwen Anderson : 64; 3966ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson NumTombstones = 0; 39708c09496c2fa7c1da027a52d8c410c2ae98481e1Dan Gohman Buckets = static_cast<BucketT*>(operator new(sizeof(BucketT)*NumBuckets)); 3986ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson 3996ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson // Initialize all the keys to EmptyKey. 4006ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson const KeyT EmptyKey = getEmptyKey(); 4016ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson for (unsigned i = 0, e = NumBuckets; i != e; ++i) 4026ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson new (&Buckets[i].first) KeyT(EmptyKey); 4036ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson 4046ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson // Free the old buckets. 4056ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson const KeyT TombstoneKey = getTombstoneKey(); 4066ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson for (BucketT *B = OldBuckets, *E = OldBuckets+OldNumBuckets; B != E; ++B) { 40705831c073abbaacbf2fc21ef5ef160872056e075Chris Lattner if (!KeyInfoT::isEqual(B->first, EmptyKey) && 40805831c073abbaacbf2fc21ef5ef160872056e075Chris Lattner !KeyInfoT::isEqual(B->first, TombstoneKey)) { 4096ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson // Free the value. 4106ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson B->second.~ValueT(); 4116ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson } 4126ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson B->first.~KeyT(); 4136ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson } 4143a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 415d06c59821a1ca0191ea8a326a18509808a02ed03Torok Edwin#ifndef NDEBUG 416d06c59821a1ca0191ea8a326a18509808a02ed03Torok Edwin memset(OldBuckets, 0x5a, sizeof(BucketT)*OldNumBuckets); 417d06c59821a1ca0191ea8a326a18509808a02ed03Torok Edwin#endif 4186ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson // Free the old table. 41908c09496c2fa7c1da027a52d8c410c2ae98481e1Dan Gohman operator delete(OldBuckets); 4203a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 4216ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson NumEntries = 0; 4226ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson } 4236e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner}; 4246e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 42529ce95511f905df3a63e3b953a4a0179ead46865Owen Andersontemplate<typename KeyT, typename ValueT, typename KeyInfoT, typename ValueInfoT> 426f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattnerclass DenseMapIterator { 427f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner typedef std::pair<KeyT, ValueT> BucketT; 42870a76a633ed5101dbe472404efd989f4f1b3669cChris Lattnerprotected: 429f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner const BucketT *Ptr, *End; 430f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattnerpublic: 431a9ad04191cb56c42944b17980b8b2bb2afe11ab2Dan Gohman DenseMapIterator() : Ptr(0), End(0) {} 43213e781ebe7a39e008dd5e5de78983e095e8a1d02David Greene 433f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner DenseMapIterator(const BucketT *Pos, const BucketT *E) : Ptr(Pos), End(E) { 434f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner AdvancePastEmptyBuckets(); 435f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner } 4363a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 43770a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner std::pair<KeyT, ValueT> &operator*() const { 43870a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner return *const_cast<BucketT*>(Ptr); 439f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner } 44070a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner std::pair<KeyT, ValueT> *operator->() const { 44170a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner return const_cast<BucketT*>(Ptr); 442f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner } 4433a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 444f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner bool operator==(const DenseMapIterator &RHS) const { 445f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner return Ptr == RHS.Ptr; 446f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner } 447f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner bool operator!=(const DenseMapIterator &RHS) const { 448f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner return Ptr != RHS.Ptr; 449f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner } 4503a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 451f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner inline DenseMapIterator& operator++() { // Preincrement 452f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner ++Ptr; 453f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner AdvancePastEmptyBuckets(); 454f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner return *this; 455f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner } 456f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner DenseMapIterator operator++(int) { // Postincrement 457f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner DenseMapIterator tmp = *this; ++*this; return tmp; 458f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner } 4593a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 460f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattnerprivate: 461f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner void AdvancePastEmptyBuckets() { 462a76b1febd4fd258e8054395adedcbd477668d956Chris Lattner const KeyT Empty = KeyInfoT::getEmptyKey(); 463a76b1febd4fd258e8054395adedcbd477668d956Chris Lattner const KeyT Tombstone = KeyInfoT::getTombstoneKey(); 464f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner 4653a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman while (Ptr != End && 46676c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattner (KeyInfoT::isEqual(Ptr->first, Empty) || 46776c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattner KeyInfoT::isEqual(Ptr->first, Tombstone))) 468f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner ++Ptr; 469f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner } 470f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner}; 471f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner 47229ce95511f905df3a63e3b953a4a0179ead46865Owen Andersontemplate<typename KeyT, typename ValueT, typename KeyInfoT, typename ValueInfoT> 473a76b1febd4fd258e8054395adedcbd477668d956Chris Lattnerclass DenseMapConstIterator : public DenseMapIterator<KeyT, ValueT, KeyInfoT> { 47470a76a633ed5101dbe472404efd989f4f1b3669cChris Lattnerpublic: 475a9ad04191cb56c42944b17980b8b2bb2afe11ab2Dan Gohman DenseMapConstIterator() : DenseMapIterator<KeyT, ValueT, KeyInfoT>() {} 47670a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner DenseMapConstIterator(const std::pair<KeyT, ValueT> *Pos, 47770a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner const std::pair<KeyT, ValueT> *E) 478569b935e6b23c4a0e4ebb2c96603974310ef0587Chris Lattner : DenseMapIterator<KeyT, ValueT, KeyInfoT>(Pos, E) { 47970a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner } 48070a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner const std::pair<KeyT, ValueT> &operator*() const { 48170a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner return *this->Ptr; 48270a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner } 48370a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner const std::pair<KeyT, ValueT> *operator->() const { 48470a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner return this->Ptr; 48570a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner } 48670a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner}; 487f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner 4886e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner} // end namespace llvm 4896e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 4906e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner#endif 491