DenseMap.h revision 7b54452c84e478ab4d49ac08759ca4ec1badf2b2
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> 256e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattnerstruct DenseMapKeyInfo { 266e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner //static inline T getEmptyKey(); 276e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner //static inline T getTombstoneKey(); 286e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner //static unsigned getHashValue(const T &Val); 296e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner //static bool isPod() 306e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner}; 316e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 3204a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner// Provide DenseMapKeyInfo for all pointers. 336e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattnertemplate<typename T> 346e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattnerstruct DenseMapKeyInfo<T*> { 356e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner static inline T* getEmptyKey() { return (T*)-1; } 366e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner static inline T* getTombstoneKey() { return (T*)-2; } 376e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner static unsigned getHashValue(const T *PtrVal) { 386e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner return (unsigned)((uintptr_t)PtrVal >> 4) ^ 396e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner (unsigned)((uintptr_t)PtrVal >> 9); 406e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 416e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner static bool isPod() { return true; } 426e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner}; 436e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 44a76b1febd4fd258e8054395adedcbd477668d956Chris Lattnertemplate<typename KeyT, typename ValueT, 45a76b1febd4fd258e8054395adedcbd477668d956Chris Lattner typename KeyInfoT = DenseMapKeyInfo<KeyT> > 46f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattnerclass DenseMapIterator; 47a76b1febd4fd258e8054395adedcbd477668d956Chris Lattnertemplate<typename KeyT, typename ValueT, 48a76b1febd4fd258e8054395adedcbd477668d956Chris Lattner typename KeyInfoT = DenseMapKeyInfo<KeyT> > 4970a76a633ed5101dbe472404efd989f4f1b3669cChris Lattnerclass DenseMapConstIterator; 506e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 51a76b1febd4fd258e8054395adedcbd477668d956Chris Lattnertemplate<typename KeyT, typename ValueT, 52a76b1febd4fd258e8054395adedcbd477668d956Chris Lattner typename KeyInfoT = DenseMapKeyInfo<KeyT> > 536e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattnerclass DenseMap { 54f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner typedef std::pair<KeyT, ValueT> BucketT; 556e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner unsigned NumBuckets; 566e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner BucketT *Buckets; 576e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 586e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner unsigned NumEntries; 5904a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner unsigned NumTombstones; 606e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner DenseMap(const DenseMap &); // not implemented. 616e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattnerpublic: 625a5f6b6e38b7155200903816f22501cce4ca36a7Chris Lattner explicit DenseMap(unsigned NumInitBuckets = 64) { 636e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner init(NumInitBuckets); 646e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 656e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner ~DenseMap() { 666e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey(); 676e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner for (BucketT *P = Buckets, *E = Buckets+NumBuckets; P != E; ++P) { 68f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner if (P->first != EmptyKey && P->first != TombstoneKey) 69f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner P->second.~ValueT(); 70f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner P->first.~KeyT(); 716e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 726e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner delete[] (char*)Buckets; 736e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 746e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 75a76b1febd4fd258e8054395adedcbd477668d956Chris Lattner typedef DenseMapIterator<KeyT, ValueT, KeyInfoT> iterator; 76a76b1febd4fd258e8054395adedcbd477668d956Chris Lattner typedef DenseMapConstIterator<KeyT, ValueT, KeyInfoT> const_iterator; 7770a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner inline iterator begin() { 78a76b1febd4fd258e8054395adedcbd477668d956Chris Lattner return iterator(Buckets, Buckets+NumBuckets); 7970a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner } 8070a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner inline iterator end() { 81a76b1febd4fd258e8054395adedcbd477668d956Chris Lattner return iterator(Buckets+NumBuckets, Buckets+NumBuckets); 8270a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner } 8370a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner inline const_iterator begin() const { 84a76b1febd4fd258e8054395adedcbd477668d956Chris Lattner return const_iterator(Buckets, Buckets+NumBuckets); 8570a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner } 8670a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner inline const_iterator end() const { 87a76b1febd4fd258e8054395adedcbd477668d956Chris Lattner return const_iterator(Buckets+NumBuckets, Buckets+NumBuckets); 8870a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner } 89f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner 9070a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner bool empty() const { return NumEntries == 0; } 916e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner unsigned size() const { return NumEntries; } 926e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 936e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner void clear() { 9442e4bdf2577946380ce1529d5716e48b33d4186dChris Lattner // If the capacity of the array is huge, and the # elements used is small, 9542e4bdf2577946380ce1529d5716e48b33d4186dChris Lattner // shrink the array. 966ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson if (NumEntries * 4 < NumBuckets && NumBuckets > 64) { 976ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson shrink_and_clear(); 986ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson return; 996ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson } 1006ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson 1016e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey(); 1026e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner for (BucketT *P = Buckets, *E = Buckets+NumBuckets; P != E; ++P) { 1037b54452c84e478ab4d49ac08759ca4ec1badf2b2Chris Lattner if (P->first != EmptyKey) { 1047b54452c84e478ab4d49ac08759ca4ec1badf2b2Chris Lattner if (P->first != TombstoneKey) { 1057b54452c84e478ab4d49ac08759ca4ec1badf2b2Chris Lattner P->second.~ValueT(); 1067b54452c84e478ab4d49ac08759ca4ec1badf2b2Chris Lattner --NumEntries; 1077b54452c84e478ab4d49ac08759ca4ec1badf2b2Chris Lattner } 108f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner P->first = EmptyKey; 1096e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 1106e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 1116e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner assert(NumEntries == 0 && "Node count imbalance!"); 11204a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner NumTombstones = 0; 1136e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 1146ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson 1156e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner /// count - Return true if the specified key is in the map. 1166e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner bool count(const KeyT &Val) const { 1176e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner BucketT *TheBucket; 1186e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner return LookupBucketFor(Val, TheBucket); 1196e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 1206e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 121569b935e6b23c4a0e4ebb2c96603974310ef0587Chris Lattner iterator find(const KeyT &Val) { 12270a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner BucketT *TheBucket; 12370a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner if (LookupBucketFor(Val, TheBucket)) 12470a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner return iterator(TheBucket, Buckets+NumBuckets); 12570a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner return end(); 12670a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner } 127569b935e6b23c4a0e4ebb2c96603974310ef0587Chris Lattner const_iterator find(const KeyT &Val) const { 128569b935e6b23c4a0e4ebb2c96603974310ef0587Chris Lattner BucketT *TheBucket; 129569b935e6b23c4a0e4ebb2c96603974310ef0587Chris Lattner if (LookupBucketFor(Val, TheBucket)) 130569b935e6b23c4a0e4ebb2c96603974310ef0587Chris Lattner return const_iterator(TheBucket, Buckets+NumBuckets); 131569b935e6b23c4a0e4ebb2c96603974310ef0587Chris Lattner return end(); 132569b935e6b23c4a0e4ebb2c96603974310ef0587Chris Lattner } 13370a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner 13428f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner bool insert(const std::pair<KeyT, ValueT> &KV) { 13528f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner BucketT *TheBucket; 13628f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner if (LookupBucketFor(KV.first, TheBucket)) 13728f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner return false; // Already in map. 13828f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner 13928f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner // Otherwise, insert the new element. 14028f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner InsertIntoBucket(KV.first, KV.second, TheBucket); 14128f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner return true; 14228f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner } 14328f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner 14470a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner bool erase(const KeyT &Val) { 14570a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner BucketT *TheBucket; 14670a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner if (!LookupBucketFor(Val, TheBucket)) 14770a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner return false; // not in map. 14870a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner 14970a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner TheBucket->second.~ValueT(); 15070a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner TheBucket->first = getTombstoneKey(); 15170a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner --NumEntries; 15204a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner ++NumTombstones; 15370a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner return true; 15470a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner } 15570a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner bool erase(iterator I) { 15670a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner BucketT *TheBucket = &*I; 15770a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner TheBucket->second.~ValueT(); 15870a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner TheBucket->first = getTombstoneKey(); 15970a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner --NumEntries; 16004a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner ++NumTombstones; 16170a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner return true; 16270a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner } 16370a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner 16428f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner ValueT &operator[](const KeyT &Key) { 1656e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner BucketT *TheBucket; 16628f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner if (LookupBucketFor(Key, TheBucket)) 167f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner return TheBucket->second; 1686e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 16928f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner return InsertIntoBucket(Key, ValueT(), TheBucket)->second; 17028f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner } 17128f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner 17228f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattnerprivate: 17328f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner BucketT *InsertIntoBucket(const KeyT &Key, const ValueT &Value, 17428f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner BucketT *TheBucket) { 17504a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // If the load of the hash table is more than 3/4, or if fewer than 1/8 of 17604a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // the buckets are empty (meaning that many are filled with tombstones), 17704a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // grow the table. 17804a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // 17904a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // The later case is tricky. For example, if we had one empty bucket with 18004a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // tons of tombstones, failing lookups (e.g. for insertion) would have to 18104a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // probe almost the entire table until it found the empty bucket. If the 18204a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // table completely filled with tombstones, no lookup would ever succeed, 18304a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // causing infinite loops in lookup. 18404a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner if (NumEntries*4 >= NumBuckets*3 || 18504a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner NumBuckets-(NumEntries+NumTombstones) < NumBuckets/8) { 1866e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner this->grow(); 18728f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner LookupBucketFor(Key, TheBucket); 1886e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 1896e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner ++NumEntries; 19004a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner 19104a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // If we are writing over a tombstone, remember this. 19204a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner if (TheBucket->first != getEmptyKey()) 19304a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner --NumTombstones; 19404a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner 19528f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner TheBucket->first = Key; 19628f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner new (&TheBucket->second) ValueT(Value); 19728f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner return TheBucket; 1986e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 19928f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner 20070a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner static unsigned getHashValue(const KeyT &Val) { 201a76b1febd4fd258e8054395adedcbd477668d956Chris Lattner return KeyInfoT::getHashValue(Val); 2026e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 20370a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner static const KeyT getEmptyKey() { 204a76b1febd4fd258e8054395adedcbd477668d956Chris Lattner return KeyInfoT::getEmptyKey(); 20570a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner } 20670a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner static const KeyT getTombstoneKey() { 207a76b1febd4fd258e8054395adedcbd477668d956Chris Lattner return KeyInfoT::getTombstoneKey(); 2086e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 2096e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 2106e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner /// LookupBucketFor - Lookup the appropriate bucket for Val, returning it in 2116e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner /// FoundBucket. If the bucket contains the key and a value, this returns 2126e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner /// true, otherwise it returns a bucket with an empty marker or tombstone and 2136e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner /// returns false. 2146e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner bool LookupBucketFor(const KeyT &Val, BucketT *&FoundBucket) const { 2156e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner unsigned BucketNo = getHashValue(Val); 2166e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner unsigned ProbeAmt = 1; 2176e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner BucketT *BucketsPtr = Buckets; 2186e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 2196e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // FoundTombstone - Keep track of whether we find a tombstone while probing. 2206e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner BucketT *FoundTombstone = 0; 2216e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner const KeyT EmptyKey = getEmptyKey(); 2226e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner const KeyT TombstoneKey = getTombstoneKey(); 2236e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner assert(Val != EmptyKey && Val != TombstoneKey && 2246e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner "Empty/Tombstone value shouldn't be inserted into map!"); 2256e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 2266e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner while (1) { 2276e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner BucketT *ThisBucket = BucketsPtr + (BucketNo & (NumBuckets-1)); 2286e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // Found Val's bucket? If so, return it. 229f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner if (ThisBucket->first == Val) { 2306e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner FoundBucket = ThisBucket; 2316e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner return true; 2326e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 2336e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 2346e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // If we found an empty bucket, the key doesn't exist in the set. 2356e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // Insert it and return the default value. 236f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner if (ThisBucket->first == EmptyKey) { 2376e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // If we've already seen a tombstone while probing, fill it in instead 2386e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // of the empty bucket we eventually probed to. 2396e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner if (FoundTombstone) ThisBucket = FoundTombstone; 2406e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner FoundBucket = FoundTombstone ? FoundTombstone : ThisBucket; 2416e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner return false; 2426e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 2436e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 2446e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // If this is a tombstone, remember it. If Val ends up not in the map, we 2456e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // prefer to return it than something that would require more probing. 246f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner if (ThisBucket->first == TombstoneKey && !FoundTombstone) 2476e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner FoundTombstone = ThisBucket; // Remember the first tombstone found. 2486e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 2496e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // Otherwise, it's a hash collision or a tombstone, continue quadratic 2506e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // probing. 2516e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner BucketNo += ProbeAmt++; 2526e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 2536e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 2546e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 2556e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner void init(unsigned InitBuckets) { 2566e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner NumEntries = 0; 25704a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner NumTombstones = 0; 2586e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner NumBuckets = InitBuckets; 2596e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner assert(InitBuckets && (InitBuckets & InitBuckets-1) == 0 && 2606e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner "# initial buckets must be a power of two!"); 2616e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner Buckets = (BucketT*)new char[sizeof(BucketT)*InitBuckets]; 2626e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // Initialize all the keys to EmptyKey. 2636e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner const KeyT EmptyKey = getEmptyKey(); 2646e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner for (unsigned i = 0; i != InitBuckets; ++i) 265f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner new (&Buckets[i].first) KeyT(EmptyKey); 2666e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 2676e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 2686e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner void grow() { 2696e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner unsigned OldNumBuckets = NumBuckets; 2706e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner BucketT *OldBuckets = Buckets; 2716e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 2726e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // Double the number of buckets. 2736e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner NumBuckets <<= 1; 27404a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner NumTombstones = 0; 2756e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner Buckets = (BucketT*)new char[sizeof(BucketT)*NumBuckets]; 2766e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 2776e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // Initialize all the keys to EmptyKey. 2786e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner const KeyT EmptyKey = getEmptyKey(); 2796e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner for (unsigned i = 0, e = NumBuckets; i != e; ++i) 280f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner new (&Buckets[i].first) KeyT(EmptyKey); 2816e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 2826e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // Insert all the old elements. 2836e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner const KeyT TombstoneKey = getTombstoneKey(); 2846e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner for (BucketT *B = OldBuckets, *E = OldBuckets+OldNumBuckets; B != E; ++B) { 285f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner if (B->first != EmptyKey && B->first != TombstoneKey) { 2866e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // Insert the key/value into the new table. 2876e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner BucketT *DestBucket; 288f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner bool FoundVal = LookupBucketFor(B->first, DestBucket); 289137d4b253384adce88bfa2a1c37695d90f0a9d6cChris Lattner FoundVal = FoundVal; // silence warning. 2906e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner assert(!FoundVal && "Key already in new map?"); 291f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner DestBucket->first = B->first; 292f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner new (&DestBucket->second) ValueT(B->second); 2936e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 2946e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // Free the value. 295f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner B->second.~ValueT(); 2966e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 297f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner B->first.~KeyT(); 2986e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 2996e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 3006e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // Free the old table. 3016e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner delete[] (char*)OldBuckets; 3026e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 3036ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson 3046ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson void shrink_and_clear() { 3056ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson unsigned OldNumBuckets = NumBuckets; 3066ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson BucketT *OldBuckets = Buckets; 3076ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson 308398b40671b13018f88371b74822fa8ee2638577eOwen Anderson // Reduce the number of buckets. 309398b40671b13018f88371b74822fa8ee2638577eOwen Anderson NumBuckets = NumEntries > 32 ? 1 << (Log2_32_Ceil(NumEntries) + 1) 310398b40671b13018f88371b74822fa8ee2638577eOwen Anderson : 64; 3116ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson NumTombstones = 0; 3126ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson Buckets = (BucketT*)new char[sizeof(BucketT)*NumBuckets]; 3136ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson 3146ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson // Initialize all the keys to EmptyKey. 3156ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson const KeyT EmptyKey = getEmptyKey(); 3166ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson for (unsigned i = 0, e = NumBuckets; i != e; ++i) 3176ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson new (&Buckets[i].first) KeyT(EmptyKey); 3186ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson 3196ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson // Free the old buckets. 3206ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson const KeyT TombstoneKey = getTombstoneKey(); 3216ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson for (BucketT *B = OldBuckets, *E = OldBuckets+OldNumBuckets; B != E; ++B) { 3226ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson if (B->first != EmptyKey && B->first != TombstoneKey) { 3236ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson // Free the value. 3246ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson B->second.~ValueT(); 3256ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson } 3266ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson B->first.~KeyT(); 3276ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson } 3286ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson 3296ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson // Free the old table. 3306ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson delete[] (char*)OldBuckets; 3316ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson 3326ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson NumEntries = 0; 3336ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson } 3346e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner}; 3356e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 336a76b1febd4fd258e8054395adedcbd477668d956Chris Lattnertemplate<typename KeyT, typename ValueT, typename KeyInfoT> 337f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattnerclass DenseMapIterator { 338f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner typedef std::pair<KeyT, ValueT> BucketT; 33970a76a633ed5101dbe472404efd989f4f1b3669cChris Lattnerprotected: 340f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner const BucketT *Ptr, *End; 341f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattnerpublic: 342f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner DenseMapIterator(const BucketT *Pos, const BucketT *E) : Ptr(Pos), End(E) { 343f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner AdvancePastEmptyBuckets(); 344f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner } 345f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner 34670a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner std::pair<KeyT, ValueT> &operator*() const { 34770a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner return *const_cast<BucketT*>(Ptr); 348f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner } 34970a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner std::pair<KeyT, ValueT> *operator->() const { 35070a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner return const_cast<BucketT*>(Ptr); 351f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner } 352f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner 353f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner bool operator==(const DenseMapIterator &RHS) const { 354f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner return Ptr == RHS.Ptr; 355f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner } 356f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner bool operator!=(const DenseMapIterator &RHS) const { 357f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner return Ptr != RHS.Ptr; 358f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner } 359f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner 360f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner inline DenseMapIterator& operator++() { // Preincrement 361f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner ++Ptr; 362f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner AdvancePastEmptyBuckets(); 363f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner return *this; 364f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner } 365f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner DenseMapIterator operator++(int) { // Postincrement 366f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner DenseMapIterator tmp = *this; ++*this; return tmp; 367f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner } 368f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner 369f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattnerprivate: 370f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner void AdvancePastEmptyBuckets() { 371a76b1febd4fd258e8054395adedcbd477668d956Chris Lattner const KeyT Empty = KeyInfoT::getEmptyKey(); 372a76b1febd4fd258e8054395adedcbd477668d956Chris Lattner const KeyT Tombstone = KeyInfoT::getTombstoneKey(); 373f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner 37470a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner while (Ptr != End && (Ptr->first == Empty || Ptr->first == Tombstone)) 375f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner ++Ptr; 376f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner } 377f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner}; 378f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner 379a76b1febd4fd258e8054395adedcbd477668d956Chris Lattnertemplate<typename KeyT, typename ValueT, typename KeyInfoT> 380a76b1febd4fd258e8054395adedcbd477668d956Chris Lattnerclass DenseMapConstIterator : public DenseMapIterator<KeyT, ValueT, KeyInfoT> { 38170a76a633ed5101dbe472404efd989f4f1b3669cChris Lattnerpublic: 38270a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner DenseMapConstIterator(const std::pair<KeyT, ValueT> *Pos, 38370a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner const std::pair<KeyT, ValueT> *E) 384569b935e6b23c4a0e4ebb2c96603974310ef0587Chris Lattner : DenseMapIterator<KeyT, ValueT, KeyInfoT>(Pos, E) { 38570a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner } 38670a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner const std::pair<KeyT, ValueT> &operator*() const { 38770a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner return *this->Ptr; 38870a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner } 38970a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner const std::pair<KeyT, ValueT> *operator->() const { 39070a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner return this->Ptr; 39170a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner } 39270a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner}; 393f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner 3946e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner} // end namespace llvm 3956e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 3966e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner#endif 397