DenseMap.h revision 05831c073abbaacbf2fc21ef5ef160872056e075
16e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner//===- llvm/ADT/DenseMap.h - Dense probed hash table ------------*- C++ -*-===// 26e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner// 36e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner// The LLVM Compiler Infrastructure 46e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner// 56e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner// This file was developed by Chris Lattner and is distributed under 66e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner// the University of Illinois Open Source 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 176e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner#include "llvm/Support/DataTypes.h" 18398b40671b13018f88371b74822fa8ee2638577eOwen Anderson#include "llvm/Support/MathExtras.h" 196e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner#include <cassert> 20f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner#include <utility> 216e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 226e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattnernamespace llvm { 236e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 246e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattnertemplate<typename T> 2576c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattnerstruct DenseMapInfo { 266e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner //static inline T getEmptyKey(); 276e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner //static inline T getTombstoneKey(); 286e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner //static unsigned getHashValue(const T &Val); 2976c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattner //static bool isEqual(const T &LHS, const T &RHS); 306e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner //static bool isPod() 316e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner}; 326e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 3376c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattner// Provide DenseMapInfo for all pointers. 346e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattnertemplate<typename T> 3576c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattnerstruct DenseMapInfo<T*> { 36276222a5ae189ed5c6a2afb248d4c8f0335585b4Reid Spencer static inline T* getEmptyKey() { return reinterpret_cast<T*>(-1); } 37276222a5ae189ed5c6a2afb248d4c8f0335585b4Reid Spencer static inline T* getTombstoneKey() { return reinterpret_cast<T*>(-2); } 386e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner static unsigned getHashValue(const T *PtrVal) { 39f8a3ee1d637a747c87f72bc880445e6a82280ff0Chris Lattner return (unsigned((uintptr_t)PtrVal) >> 4) ^ 40f8a3ee1d637a747c87f72bc880445e6a82280ff0Chris Lattner (unsigned((uintptr_t)PtrVal) >> 9); 416e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 4276c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattner static bool isEqual(const T *LHS, const T *RHS) { return LHS == RHS; } 4329ce95511f905df3a63e3b953a4a0179ead46865Owen Anderson static bool isPod() { return true; } 4429ce95511f905df3a63e3b953a4a0179ead46865Owen Anderson}; 4529ce95511f905df3a63e3b953a4a0179ead46865Owen Anderson 46a76b1febd4fd258e8054395adedcbd477668d956Chris Lattnertemplate<typename KeyT, typename ValueT, 4776c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattner typename KeyInfoT = DenseMapInfo<KeyT>, 4876c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattner typename ValueInfoT = DenseMapInfo<ValueT> > 49f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattnerclass DenseMapIterator; 50a76b1febd4fd258e8054395adedcbd477668d956Chris Lattnertemplate<typename KeyT, typename ValueT, 5176c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattner typename KeyInfoT = DenseMapInfo<KeyT>, 5276c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattner typename ValueInfoT = DenseMapInfo<ValueT> > 5370a76a633ed5101dbe472404efd989f4f1b3669cChris Lattnerclass DenseMapConstIterator; 546e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 55a76b1febd4fd258e8054395adedcbd477668d956Chris Lattnertemplate<typename KeyT, typename ValueT, 5676c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattner typename KeyInfoT = DenseMapInfo<KeyT>, 5776c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattner typename ValueInfoT = DenseMapInfo<ValueT> > 586e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattnerclass DenseMap { 59f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner typedef std::pair<KeyT, ValueT> BucketT; 606e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner unsigned NumBuckets; 616e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner BucketT *Buckets; 626e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 636e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner unsigned NumEntries; 6404a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner unsigned NumTombstones; 656e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattnerpublic: 6667280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson DenseMap(const DenseMap& other) { 6767280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson NumBuckets = 0; 6867280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson CopyFrom(other); 6967280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson } 7067280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson 715a5f6b6e38b7155200903816f22501cce4ca36a7Chris Lattner explicit DenseMap(unsigned NumInitBuckets = 64) { 726e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner init(NumInitBuckets); 736e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 7467280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson 756e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner ~DenseMap() { 766e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey(); 776e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner for (BucketT *P = Buckets, *E = Buckets+NumBuckets; P != E; ++P) { 7805831c073abbaacbf2fc21ef5ef160872056e075Chris Lattner if (!KeyInfoT::isEqual(P->first, EmptyKey) && 7905831c073abbaacbf2fc21ef5ef160872056e075Chris Lattner !KeyInfoT::isEqual(P->first, TombstoneKey)) 80f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner P->second.~ValueT(); 81f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner P->first.~KeyT(); 826e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 83276222a5ae189ed5c6a2afb248d4c8f0335585b4Reid Spencer delete[] reinterpret_cast<char*>(Buckets); 846e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 856e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 86a76b1febd4fd258e8054395adedcbd477668d956Chris Lattner typedef DenseMapIterator<KeyT, ValueT, KeyInfoT> iterator; 87a76b1febd4fd258e8054395adedcbd477668d956Chris Lattner typedef DenseMapConstIterator<KeyT, ValueT, KeyInfoT> const_iterator; 8870a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner inline iterator begin() { 89a76b1febd4fd258e8054395adedcbd477668d956Chris Lattner return iterator(Buckets, Buckets+NumBuckets); 9070a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner } 9170a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner inline iterator end() { 92a76b1febd4fd258e8054395adedcbd477668d956Chris Lattner return iterator(Buckets+NumBuckets, Buckets+NumBuckets); 9370a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner } 9470a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner inline const_iterator begin() const { 95a76b1febd4fd258e8054395adedcbd477668d956Chris Lattner return const_iterator(Buckets, Buckets+NumBuckets); 9670a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner } 9770a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner inline const_iterator end() const { 98a76b1febd4fd258e8054395adedcbd477668d956Chris Lattner return const_iterator(Buckets+NumBuckets, Buckets+NumBuckets); 9970a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner } 100f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner 10170a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner bool empty() const { return NumEntries == 0; } 1026e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner unsigned size() const { return NumEntries; } 103d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin 104d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin /// Grow the densemap so that it has at least Size buckets. Does not shrink 105d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin void resize(size_t Size) { grow(Size); } 1066e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 1076e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner void clear() { 10842e4bdf2577946380ce1529d5716e48b33d4186dChris Lattner // If the capacity of the array is huge, and the # elements used is small, 10942e4bdf2577946380ce1529d5716e48b33d4186dChris Lattner // shrink the array. 1106ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson if (NumEntries * 4 < NumBuckets && NumBuckets > 64) { 1116ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson shrink_and_clear(); 1126ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson return; 1136ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson } 1146ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson 1156e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey(); 1166e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner for (BucketT *P = Buckets, *E = Buckets+NumBuckets; P != E; ++P) { 11705831c073abbaacbf2fc21ef5ef160872056e075Chris Lattner if (!KeyInfoT::isEqual(P->first, EmptyKey)) { 11805831c073abbaacbf2fc21ef5ef160872056e075Chris Lattner if (!KeyInfoT::isEqual(P->first, TombstoneKey)) { 1197b54452c84e478ab4d49ac08759ca4ec1badf2b2Chris Lattner P->second.~ValueT(); 1207b54452c84e478ab4d49ac08759ca4ec1badf2b2Chris Lattner --NumEntries; 1217b54452c84e478ab4d49ac08759ca4ec1badf2b2Chris Lattner } 122f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner P->first = EmptyKey; 1236e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 1246e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 1256e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner assert(NumEntries == 0 && "Node count imbalance!"); 12604a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner NumTombstones = 0; 1276e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 1286ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson 1296e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner /// count - Return true if the specified key is in the map. 1306e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner bool count(const KeyT &Val) const { 1316e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner BucketT *TheBucket; 1326e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner return LookupBucketFor(Val, TheBucket); 1336e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 1346e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 135569b935e6b23c4a0e4ebb2c96603974310ef0587Chris Lattner iterator find(const KeyT &Val) { 13670a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner BucketT *TheBucket; 13770a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner if (LookupBucketFor(Val, TheBucket)) 13870a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner return iterator(TheBucket, Buckets+NumBuckets); 13970a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner return end(); 14070a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner } 141569b935e6b23c4a0e4ebb2c96603974310ef0587Chris Lattner const_iterator find(const KeyT &Val) const { 142569b935e6b23c4a0e4ebb2c96603974310ef0587Chris Lattner BucketT *TheBucket; 143569b935e6b23c4a0e4ebb2c96603974310ef0587Chris Lattner if (LookupBucketFor(Val, TheBucket)) 144569b935e6b23c4a0e4ebb2c96603974310ef0587Chris Lattner return const_iterator(TheBucket, Buckets+NumBuckets); 145569b935e6b23c4a0e4ebb2c96603974310ef0587Chris Lattner return end(); 146569b935e6b23c4a0e4ebb2c96603974310ef0587Chris Lattner } 14770a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner 14828f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner bool insert(const std::pair<KeyT, ValueT> &KV) { 14928f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner BucketT *TheBucket; 15028f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner if (LookupBucketFor(KV.first, TheBucket)) 15128f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner return false; // Already in map. 15228f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner 15328f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner // Otherwise, insert the new element. 15428f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner InsertIntoBucket(KV.first, KV.second, TheBucket); 15528f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner return true; 15628f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner } 15728f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner 15870a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner bool erase(const KeyT &Val) { 15970a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner BucketT *TheBucket; 16070a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner if (!LookupBucketFor(Val, TheBucket)) 16170a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner return false; // not in map. 16270a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner 16370a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner TheBucket->second.~ValueT(); 16470a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner TheBucket->first = getTombstoneKey(); 16570a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner --NumEntries; 16604a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner ++NumTombstones; 16770a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner return true; 16870a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner } 16970a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner bool erase(iterator I) { 17070a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner BucketT *TheBucket = &*I; 17170a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner TheBucket->second.~ValueT(); 17270a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner TheBucket->first = getTombstoneKey(); 17370a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner --NumEntries; 17404a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner ++NumTombstones; 17570a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner return true; 17670a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner } 17770a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner 17828f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner ValueT &operator[](const KeyT &Key) { 1796e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner BucketT *TheBucket; 18028f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner if (LookupBucketFor(Key, TheBucket)) 181f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner return TheBucket->second; 1826e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 18328f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner return InsertIntoBucket(Key, ValueT(), TheBucket)->second; 18428f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner } 18528f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner 18667280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson DenseMap& operator=(const DenseMap& other) { 18767280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson CopyFrom(other); 1883d345631db71174ffc4997a88c09f21eb9ed052bOwen Anderson return *this; 18967280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson } 19067280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson 19128f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattnerprivate: 19267280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson void CopyFrom(const DenseMap& other) { 19329ce95511f905df3a63e3b953a4a0179ead46865Owen Anderson if (NumBuckets != 0 && (!KeyInfoT::isPod() || !ValueInfoT::isPod())) { 19467280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey(); 19567280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson for (BucketT *P = Buckets, *E = Buckets+NumBuckets; P != E; ++P) { 19605831c073abbaacbf2fc21ef5ef160872056e075Chris Lattner if (!KeyInfoT::isEqual(P->first, EmptyKey) && 19705831c073abbaacbf2fc21ef5ef160872056e075Chris Lattner !KeyInfoT::isEqual(P->first, TombstoneKey)) 19867280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson P->second.~ValueT(); 19967280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson P->first.~KeyT(); 20067280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson } 20167280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson } 20267280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson 20367280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson NumEntries = other.NumEntries; 20467280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson NumTombstones = other.NumTombstones; 20567280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson 20667280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson if (NumBuckets) 20767280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson delete[] reinterpret_cast<char*>(Buckets); 20867280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson Buckets = reinterpret_cast<BucketT*>(new char[sizeof(BucketT) * 20967280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson other.NumBuckets]); 21067280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson 21129ce95511f905df3a63e3b953a4a0179ead46865Owen Anderson if (KeyInfoT::isPod() && ValueInfoT::isPod()) 2129544dc294f63ce116fbab398a8874ebf834cf41eOwen Anderson memcpy(Buckets, other.Buckets, other.NumBuckets * sizeof(BucketT)); 2139544dc294f63ce116fbab398a8874ebf834cf41eOwen Anderson else 2149544dc294f63ce116fbab398a8874ebf834cf41eOwen Anderson for (size_t i = 0; i < other.NumBuckets; ++i) { 2159544dc294f63ce116fbab398a8874ebf834cf41eOwen Anderson new (Buckets[i].first) KeyT(other.Buckets[i].first); 21605831c073abbaacbf2fc21ef5ef160872056e075Chris Lattner if (!KeyInfoT::isEqual(Buckets[i].first, getEmptyKey()) && 21705831c073abbaacbf2fc21ef5ef160872056e075Chris Lattner !KeyInfoT::isEqual(Buckets[i].first, getTombstoneKey())) 2184938d347723d452786c1a7c1d1b9ec79121b0040Owen Anderson new (&Buckets[i].second) ValueT(other.Buckets[i].second); 2199544dc294f63ce116fbab398a8874ebf834cf41eOwen Anderson } 22067280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson NumBuckets = other.NumBuckets; 22167280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson } 22267280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson 22328f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner BucketT *InsertIntoBucket(const KeyT &Key, const ValueT &Value, 22428f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner BucketT *TheBucket) { 22504a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // If the load of the hash table is more than 3/4, or if fewer than 1/8 of 22604a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // the buckets are empty (meaning that many are filled with tombstones), 22704a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // grow the table. 22804a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // 22904a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // The later case is tricky. For example, if we had one empty bucket with 23004a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // tons of tombstones, failing lookups (e.g. for insertion) would have to 23104a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // probe almost the entire table until it found the empty bucket. If the 23204a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // table completely filled with tombstones, no lookup would ever succeed, 23304a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // causing infinite loops in lookup. 23404a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner if (NumEntries*4 >= NumBuckets*3 || 23504a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner NumBuckets-(NumEntries+NumTombstones) < NumBuckets/8) { 236d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin this->grow(NumBuckets * 2); 23728f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner LookupBucketFor(Key, TheBucket); 2386e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 2396e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner ++NumEntries; 24004a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner 24104a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // If we are writing over a tombstone, remember this. 24205831c073abbaacbf2fc21ef5ef160872056e075Chris Lattner if (!KeyInfoT::isEqual(TheBucket->first, getEmptyKey())) 24304a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner --NumTombstones; 24404a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner 24528f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner TheBucket->first = Key; 24628f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner new (&TheBucket->second) ValueT(Value); 24728f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner return TheBucket; 2486e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 24928f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner 25070a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner static unsigned getHashValue(const KeyT &Val) { 251a76b1febd4fd258e8054395adedcbd477668d956Chris Lattner return KeyInfoT::getHashValue(Val); 2526e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 25370a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner static const KeyT getEmptyKey() { 254a76b1febd4fd258e8054395adedcbd477668d956Chris Lattner return KeyInfoT::getEmptyKey(); 25570a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner } 25670a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner static const KeyT getTombstoneKey() { 257a76b1febd4fd258e8054395adedcbd477668d956Chris Lattner return KeyInfoT::getTombstoneKey(); 2586e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 2596e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 2606e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner /// LookupBucketFor - Lookup the appropriate bucket for Val, returning it in 2616e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner /// FoundBucket. If the bucket contains the key and a value, this returns 2626e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner /// true, otherwise it returns a bucket with an empty marker or tombstone and 2636e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner /// returns false. 2646e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner bool LookupBucketFor(const KeyT &Val, BucketT *&FoundBucket) const { 2656e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner unsigned BucketNo = getHashValue(Val); 2666e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner unsigned ProbeAmt = 1; 2676e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner BucketT *BucketsPtr = Buckets; 2686e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 2696e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // FoundTombstone - Keep track of whether we find a tombstone while probing. 2706e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner BucketT *FoundTombstone = 0; 2716e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner const KeyT EmptyKey = getEmptyKey(); 2726e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner const KeyT TombstoneKey = getTombstoneKey(); 27305831c073abbaacbf2fc21ef5ef160872056e075Chris Lattner assert(!KeyInfoT::isEqual(Val, EmptyKey) && 27405831c073abbaacbf2fc21ef5ef160872056e075Chris Lattner !KeyInfoT::isEqual(Val, TombstoneKey) && 2756e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner "Empty/Tombstone value shouldn't be inserted into map!"); 2766e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 2776e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner while (1) { 2786e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner BucketT *ThisBucket = BucketsPtr + (BucketNo & (NumBuckets-1)); 2796e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // Found Val's bucket? If so, return it. 28076c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattner if (KeyInfoT::isEqual(ThisBucket->first, Val)) { 2816e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner FoundBucket = ThisBucket; 2826e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner return true; 2836e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 2846e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 2856e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // If we found an empty bucket, the key doesn't exist in the set. 2866e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // Insert it and return the default value. 28776c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattner if (KeyInfoT::isEqual(ThisBucket->first, EmptyKey)) { 2886e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // If we've already seen a tombstone while probing, fill it in instead 2896e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // of the empty bucket we eventually probed to. 2906e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner if (FoundTombstone) ThisBucket = FoundTombstone; 2916e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner FoundBucket = FoundTombstone ? FoundTombstone : ThisBucket; 2926e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner return false; 2936e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 2946e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 2956e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // If this is a tombstone, remember it. If Val ends up not in the map, we 2966e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // prefer to return it than something that would require more probing. 29776c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattner if (KeyInfoT::isEqual(ThisBucket->first, TombstoneKey) && !FoundTombstone) 2986e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner FoundTombstone = ThisBucket; // Remember the first tombstone found. 2996e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 3006e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // Otherwise, it's a hash collision or a tombstone, continue quadratic 3016e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // probing. 3026e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner BucketNo += ProbeAmt++; 3036e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 3046e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 3056e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 3066e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner void init(unsigned InitBuckets) { 3076e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner NumEntries = 0; 30804a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner NumTombstones = 0; 3096e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner NumBuckets = InitBuckets; 3106e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner assert(InitBuckets && (InitBuckets & InitBuckets-1) == 0 && 3116e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner "# initial buckets must be a power of two!"); 312276222a5ae189ed5c6a2afb248d4c8f0335585b4Reid Spencer Buckets = reinterpret_cast<BucketT*>(new char[sizeof(BucketT)*InitBuckets]); 3136e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // Initialize all the keys to EmptyKey. 3146e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner const KeyT EmptyKey = getEmptyKey(); 3156e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner for (unsigned i = 0; i != InitBuckets; ++i) 316f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner new (&Buckets[i].first) KeyT(EmptyKey); 3176e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 3186e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 319d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin void grow(unsigned AtLeast) { 3206e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner unsigned OldNumBuckets = NumBuckets; 3216e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner BucketT *OldBuckets = Buckets; 3226e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 3236e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // Double the number of buckets. 324d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin while (NumBuckets <= AtLeast) 325d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin NumBuckets <<= 1; 32604a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner NumTombstones = 0; 327276222a5ae189ed5c6a2afb248d4c8f0335585b4Reid Spencer Buckets = reinterpret_cast<BucketT*>(new char[sizeof(BucketT)*NumBuckets]); 3286e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 3296e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // Initialize all the keys to EmptyKey. 3306e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner const KeyT EmptyKey = getEmptyKey(); 3316e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner for (unsigned i = 0, e = NumBuckets; i != e; ++i) 332f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner new (&Buckets[i].first) KeyT(EmptyKey); 3336e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 3346e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // Insert all the old elements. 3356e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner const KeyT TombstoneKey = getTombstoneKey(); 3366e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner for (BucketT *B = OldBuckets, *E = OldBuckets+OldNumBuckets; B != E; ++B) { 33705831c073abbaacbf2fc21ef5ef160872056e075Chris Lattner if (!KeyInfoT::isEqual(B->first, EmptyKey) && 33805831c073abbaacbf2fc21ef5ef160872056e075Chris Lattner !KeyInfoT::isEqual(B->first, TombstoneKey)) { 3396e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // Insert the key/value into the new table. 3406e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner BucketT *DestBucket; 341f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner bool FoundVal = LookupBucketFor(B->first, DestBucket); 342137d4b253384adce88bfa2a1c37695d90f0a9d6cChris Lattner FoundVal = FoundVal; // silence warning. 3436e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner assert(!FoundVal && "Key already in new map?"); 344f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner DestBucket->first = B->first; 345f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner new (&DestBucket->second) ValueT(B->second); 3466e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 3476e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // Free the value. 348f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner B->second.~ValueT(); 3496e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 350f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner B->first.~KeyT(); 3516e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 3526e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 3536e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // Free the old table. 354276222a5ae189ed5c6a2afb248d4c8f0335585b4Reid Spencer delete[] reinterpret_cast<char*>(OldBuckets); 3556e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 3566ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson 3576ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson void shrink_and_clear() { 3586ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson unsigned OldNumBuckets = NumBuckets; 3596ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson BucketT *OldBuckets = Buckets; 3606ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson 361398b40671b13018f88371b74822fa8ee2638577eOwen Anderson // Reduce the number of buckets. 362398b40671b13018f88371b74822fa8ee2638577eOwen Anderson NumBuckets = NumEntries > 32 ? 1 << (Log2_32_Ceil(NumEntries) + 1) 363398b40671b13018f88371b74822fa8ee2638577eOwen Anderson : 64; 3646ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson NumTombstones = 0; 365276222a5ae189ed5c6a2afb248d4c8f0335585b4Reid Spencer Buckets = reinterpret_cast<BucketT*>(new char[sizeof(BucketT)*NumBuckets]); 3666ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson 3676ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson // Initialize all the keys to EmptyKey. 3686ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson const KeyT EmptyKey = getEmptyKey(); 3696ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson for (unsigned i = 0, e = NumBuckets; i != e; ++i) 3706ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson new (&Buckets[i].first) KeyT(EmptyKey); 3716ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson 3726ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson // Free the old buckets. 3736ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson const KeyT TombstoneKey = getTombstoneKey(); 3746ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson for (BucketT *B = OldBuckets, *E = OldBuckets+OldNumBuckets; B != E; ++B) { 37505831c073abbaacbf2fc21ef5ef160872056e075Chris Lattner if (!KeyInfoT::isEqual(B->first, EmptyKey) && 37605831c073abbaacbf2fc21ef5ef160872056e075Chris Lattner !KeyInfoT::isEqual(B->first, TombstoneKey)) { 3776ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson // Free the value. 3786ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson B->second.~ValueT(); 3796ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson } 3806ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson B->first.~KeyT(); 3816ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson } 3826ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson 3836ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson // Free the old table. 384276222a5ae189ed5c6a2afb248d4c8f0335585b4Reid Spencer delete[] reinterpret_cast<char*>(OldBuckets); 3856ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson 3866ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson NumEntries = 0; 3876ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson } 3886e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner}; 3896e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 39029ce95511f905df3a63e3b953a4a0179ead46865Owen Andersontemplate<typename KeyT, typename ValueT, typename KeyInfoT, typename ValueInfoT> 391f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattnerclass DenseMapIterator { 392f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner typedef std::pair<KeyT, ValueT> BucketT; 39370a76a633ed5101dbe472404efd989f4f1b3669cChris Lattnerprotected: 394f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner const BucketT *Ptr, *End; 395f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattnerpublic: 396f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner DenseMapIterator(const BucketT *Pos, const BucketT *E) : Ptr(Pos), End(E) { 397f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner AdvancePastEmptyBuckets(); 398f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner } 399f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner 40070a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner std::pair<KeyT, ValueT> &operator*() const { 40170a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner return *const_cast<BucketT*>(Ptr); 402f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner } 40370a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner std::pair<KeyT, ValueT> *operator->() const { 40470a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner return const_cast<BucketT*>(Ptr); 405f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner } 406f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner 407f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner bool operator==(const DenseMapIterator &RHS) const { 408f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner return Ptr == RHS.Ptr; 409f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner } 410f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner bool operator!=(const DenseMapIterator &RHS) const { 411f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner return Ptr != RHS.Ptr; 412f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner } 413f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner 414f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner inline DenseMapIterator& operator++() { // Preincrement 415f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner ++Ptr; 416f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner AdvancePastEmptyBuckets(); 417f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner return *this; 418f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner } 419f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner DenseMapIterator operator++(int) { // Postincrement 420f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner DenseMapIterator tmp = *this; ++*this; return tmp; 421f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner } 422f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner 423f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattnerprivate: 424f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner void AdvancePastEmptyBuckets() { 425a76b1febd4fd258e8054395adedcbd477668d956Chris Lattner const KeyT Empty = KeyInfoT::getEmptyKey(); 426a76b1febd4fd258e8054395adedcbd477668d956Chris Lattner const KeyT Tombstone = KeyInfoT::getTombstoneKey(); 427f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner 42876c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattner while (Ptr != End && 42976c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattner (KeyInfoT::isEqual(Ptr->first, Empty) || 43076c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattner KeyInfoT::isEqual(Ptr->first, Tombstone))) 431f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner ++Ptr; 432f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner } 433f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner}; 434f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner 43529ce95511f905df3a63e3b953a4a0179ead46865Owen Andersontemplate<typename KeyT, typename ValueT, typename KeyInfoT, typename ValueInfoT> 436a76b1febd4fd258e8054395adedcbd477668d956Chris Lattnerclass DenseMapConstIterator : public DenseMapIterator<KeyT, ValueT, KeyInfoT> { 43770a76a633ed5101dbe472404efd989f4f1b3669cChris Lattnerpublic: 43870a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner DenseMapConstIterator(const std::pair<KeyT, ValueT> *Pos, 43970a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner const std::pair<KeyT, ValueT> *E) 440569b935e6b23c4a0e4ebb2c96603974310ef0587Chris Lattner : DenseMapIterator<KeyT, ValueT, KeyInfoT>(Pos, E) { 44170a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner } 44270a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner const std::pair<KeyT, ValueT> &operator*() const { 44370a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner return *this->Ptr; 44470a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner } 44570a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner const std::pair<KeyT, ValueT> *operator->() const { 44670a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner return this->Ptr; 44770a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner } 44870a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner}; 449f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner 4506e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner} // end namespace llvm 4516e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 4526e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner#endif 453