DenseMap.h revision 137d4b253384adce88bfa2a1c37695d90f0a9d6c
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" 186e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner#include <cassert> 19f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner#include <utility> 206e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 216e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattnernamespace llvm { 226e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 236e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattnertemplate<typename T> 246e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattnerstruct DenseMapKeyInfo { 256e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner //static inline T getEmptyKey(); 266e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner //static inline T getTombstoneKey(); 276e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner //static unsigned getHashValue(const T &Val); 286e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner //static bool isPod() 296e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner}; 306e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 316e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattnertemplate<typename T> 326e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattnerstruct DenseMapKeyInfo<T*> { 336e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner static inline T* getEmptyKey() { return (T*)-1; } 346e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner static inline T* getTombstoneKey() { return (T*)-2; } 356e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner static unsigned getHashValue(const T *PtrVal) { 366e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner return (unsigned)((uintptr_t)PtrVal >> 4) ^ 376e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner (unsigned)((uintptr_t)PtrVal >> 9); 386e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 396e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner static bool isPod() { return true; } 406e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner}; 416e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 42f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattnertemplate<typename KeyT, typename ValueT> 43f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattnerclass DenseMapIterator; 4470a76a633ed5101dbe472404efd989f4f1b3669cChris Lattnertemplate<typename KeyT, typename ValueT> 4570a76a633ed5101dbe472404efd989f4f1b3669cChris Lattnerclass DenseMapConstIterator; 466e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 476e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattnertemplate<typename KeyT, typename ValueT> 486e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattnerclass DenseMap { 49f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner typedef std::pair<KeyT, ValueT> BucketT; 506e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner unsigned NumBuckets; 516e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner BucketT *Buckets; 526e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 536e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner unsigned NumEntries; 546e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner DenseMap(const DenseMap &); // not implemented. 556e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattnerpublic: 566e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner explicit DenseMap(unsigned NumInitBuckets = 8) { 576e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner init(NumInitBuckets); 586e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 596e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner ~DenseMap() { 606e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey(); 616e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner for (BucketT *P = Buckets, *E = Buckets+NumBuckets; P != E; ++P) { 62f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner if (P->first != EmptyKey && P->first != TombstoneKey) 63f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner P->second.~ValueT(); 64f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner P->first.~KeyT(); 656e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 666e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner delete[] (char*)Buckets; 676e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 686e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 69f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner typedef DenseMapIterator<KeyT, ValueT> iterator; 7070a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner typedef DenseMapConstIterator<KeyT, ValueT> const_iterator; 7170a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner inline iterator begin() { 7270a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner return DenseMapIterator<KeyT, ValueT>(Buckets, Buckets+NumBuckets); 7370a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner } 7470a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner inline iterator end() { 7570a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner return DenseMapIterator<KeyT, ValueT>(Buckets+NumBuckets, 7670a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner Buckets+NumBuckets); 7770a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner } 7870a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner inline const_iterator begin() const { 7970a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner return DenseMapConstIterator<KeyT, ValueT>(Buckets, Buckets+NumBuckets); 8070a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner } 8170a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner inline const_iterator end() const { 8270a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner return DenseMapConstIterator<KeyT, ValueT>(Buckets+NumBuckets, 8370a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner Buckets+NumBuckets); 8470a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner } 85f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner 8670a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner bool empty() const { return NumEntries == 0; } 876e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner unsigned size() const { return NumEntries; } 886e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 896e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner void clear() { 906e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey(); 916e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner for (BucketT *P = Buckets, *E = Buckets+NumBuckets; P != E; ++P) { 92f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner if (P->first != EmptyKey && P->first != TombstoneKey) { 93f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner P->first = EmptyKey; 94f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner P->second.~ValueT(); 956e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner --NumEntries; 966e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 976e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 986e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner assert(NumEntries == 0 && "Node count imbalance!"); 996e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 1006e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 1016e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner /// count - Return true if the specified key is in the map. 1026e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner bool count(const KeyT &Val) const { 1036e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner BucketT *TheBucket; 1046e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner return LookupBucketFor(Val, TheBucket); 1056e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 1066e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 10770a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner iterator find(const KeyT &Val) const { 10870a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner BucketT *TheBucket; 10970a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner if (LookupBucketFor(Val, TheBucket)) 11070a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner return iterator(TheBucket, Buckets+NumBuckets); 11170a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner return end(); 11270a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner } 11370a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner 11470a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner bool erase(const KeyT &Val) { 11570a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner BucketT *TheBucket; 11670a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner if (!LookupBucketFor(Val, TheBucket)) 11770a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner return false; // not in map. 11870a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner 11970a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner TheBucket->second.~ValueT(); 12070a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner TheBucket->first = getTombstoneKey(); 12170a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner --NumEntries; 12270a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner return true; 12370a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner } 12470a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner bool erase(iterator I) { 12570a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner BucketT *TheBucket = &*I; 12670a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner TheBucket->second.~ValueT(); 12770a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner TheBucket->first = getTombstoneKey(); 12870a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner --NumEntries; 12970a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner return true; 13070a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner } 13170a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner 1326e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner ValueT &operator[](const KeyT &Val) { 1336e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner BucketT *TheBucket; 1346e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner if (LookupBucketFor(Val, TheBucket)) 135f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner return TheBucket->second; 1366e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 1376e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // If the load of the hash table is more than 3/4, grow it. 1386e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner if (NumEntries*4 >= NumBuckets*3) { 1396e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner this->grow(); 1406e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner LookupBucketFor(Val, TheBucket); 1416e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 1426e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner ++NumEntries; 143f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner TheBucket->first = Val; 144f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner new (&TheBucket->second) ValueT(); 145f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner return TheBucket->second; 1466e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 1476e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 1486e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattnerprivate: 14970a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner static unsigned getHashValue(const KeyT &Val) { 1506e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner return DenseMapKeyInfo<KeyT>::getHashValue(Val); 1516e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 15270a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner static const KeyT getEmptyKey() { 15370a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner return DenseMapKeyInfo<KeyT>::getEmptyKey(); 15470a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner } 15570a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner static const KeyT getTombstoneKey() { 1566e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner return DenseMapKeyInfo<KeyT>::getTombstoneKey(); 1576e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 1586e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 1596e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner /// LookupBucketFor - Lookup the appropriate bucket for Val, returning it in 1606e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner /// FoundBucket. If the bucket contains the key and a value, this returns 1616e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner /// true, otherwise it returns a bucket with an empty marker or tombstone and 1626e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner /// returns false. 1636e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner bool LookupBucketFor(const KeyT &Val, BucketT *&FoundBucket) const { 1646e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner unsigned BucketNo = getHashValue(Val); 1656e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner unsigned ProbeAmt = 1; 1666e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner BucketT *BucketsPtr = Buckets; 1676e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 1686e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // FoundTombstone - Keep track of whether we find a tombstone while probing. 1696e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner BucketT *FoundTombstone = 0; 1706e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner const KeyT EmptyKey = getEmptyKey(); 1716e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner const KeyT TombstoneKey = getTombstoneKey(); 1726e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner assert(Val != EmptyKey && Val != TombstoneKey && 1736e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner "Empty/Tombstone value shouldn't be inserted into map!"); 1746e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 1756e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner while (1) { 1766e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner BucketT *ThisBucket = BucketsPtr + (BucketNo & (NumBuckets-1)); 1776e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // Found Val's bucket? If so, return it. 178f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner if (ThisBucket->first == Val) { 1796e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner FoundBucket = ThisBucket; 1806e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner return true; 1816e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 1826e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 1836e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // If we found an empty bucket, the key doesn't exist in the set. 1846e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // Insert it and return the default value. 185f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner if (ThisBucket->first == EmptyKey) { 1866e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // If we've already seen a tombstone while probing, fill it in instead 1876e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // of the empty bucket we eventually probed to. 1886e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner if (FoundTombstone) ThisBucket = FoundTombstone; 1896e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner FoundBucket = FoundTombstone ? FoundTombstone : ThisBucket; 1906e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner return false; 1916e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 1926e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 1936e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // If this is a tombstone, remember it. If Val ends up not in the map, we 1946e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // prefer to return it than something that would require more probing. 195f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner if (ThisBucket->first == TombstoneKey && !FoundTombstone) 1966e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner FoundTombstone = ThisBucket; // Remember the first tombstone found. 1976e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 1986e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // Otherwise, it's a hash collision or a tombstone, continue quadratic 1996e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // probing. 2006e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner BucketNo += ProbeAmt++; 2016e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 2026e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 2036e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 2046e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner void init(unsigned InitBuckets) { 2056e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner NumEntries = 0; 2066e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner NumBuckets = InitBuckets; 2076e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner assert(InitBuckets && (InitBuckets & InitBuckets-1) == 0 && 2086e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner "# initial buckets must be a power of two!"); 2096e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner Buckets = (BucketT*)new char[sizeof(BucketT)*InitBuckets]; 2106e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // Initialize all the keys to EmptyKey. 2116e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner const KeyT EmptyKey = getEmptyKey(); 2126e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner for (unsigned i = 0; i != InitBuckets; ++i) 213f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner new (&Buckets[i].first) KeyT(EmptyKey); 2146e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 2156e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 2166e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner void grow() { 2176e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner unsigned OldNumBuckets = NumBuckets; 2186e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner BucketT *OldBuckets = Buckets; 2196e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 2206e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // Double the number of buckets. 2216e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner NumBuckets <<= 1; 2226e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner Buckets = (BucketT*)new char[sizeof(BucketT)*NumBuckets]; 2236e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 2246e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // Initialize all the keys to EmptyKey. 2256e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner const KeyT EmptyKey = getEmptyKey(); 2266e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner for (unsigned i = 0, e = NumBuckets; i != e; ++i) 227f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner new (&Buckets[i].first) KeyT(EmptyKey); 2286e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 2296e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // Insert all the old elements. 2306e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner const KeyT TombstoneKey = getTombstoneKey(); 2316e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner for (BucketT *B = OldBuckets, *E = OldBuckets+OldNumBuckets; B != E; ++B) { 232f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner if (B->first != EmptyKey && B->first != TombstoneKey) { 2336e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // Insert the key/value into the new table. 2346e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner BucketT *DestBucket; 235f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner bool FoundVal = LookupBucketFor(B->first, DestBucket); 236137d4b253384adce88bfa2a1c37695d90f0a9d6cChris Lattner FoundVal = FoundVal; // silence warning. 2376e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner assert(!FoundVal && "Key already in new map?"); 238f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner DestBucket->first = B->first; 239f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner new (&DestBucket->second) ValueT(B->second); 2406e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 2416e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // Free the value. 242f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner B->second.~ValueT(); 2436e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 244f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner B->first.~KeyT(); 2456e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 2466e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 2476e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // Free the old table. 2486e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner delete[] (char*)OldBuckets; 2496e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 2506e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner}; 2516e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 252f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattnertemplate<typename KeyT, typename ValueT> 253f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattnerclass DenseMapIterator { 254f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner typedef std::pair<KeyT, ValueT> BucketT; 25570a76a633ed5101dbe472404efd989f4f1b3669cChris Lattnerprotected: 256f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner const BucketT *Ptr, *End; 257f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattnerpublic: 258f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner DenseMapIterator(const BucketT *Pos, const BucketT *E) : Ptr(Pos), End(E) { 259f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner AdvancePastEmptyBuckets(); 260f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner } 261f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner 26270a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner std::pair<KeyT, ValueT> &operator*() const { 26370a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner return *const_cast<BucketT*>(Ptr); 264f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner } 26570a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner std::pair<KeyT, ValueT> *operator->() const { 26670a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner return const_cast<BucketT*>(Ptr); 267f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner } 268f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner 269f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner bool operator==(const DenseMapIterator &RHS) const { 270f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner return Ptr == RHS.Ptr; 271f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner } 272f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner bool operator!=(const DenseMapIterator &RHS) const { 273f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner return Ptr != RHS.Ptr; 274f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner } 275f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner 276f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner inline DenseMapIterator& operator++() { // Preincrement 277f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner ++Ptr; 278f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner AdvancePastEmptyBuckets(); 279f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner return *this; 280f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner } 281f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner DenseMapIterator operator++(int) { // Postincrement 282f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner DenseMapIterator tmp = *this; ++*this; return tmp; 283f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner } 284f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner 285f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattnerprivate: 286f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner void AdvancePastEmptyBuckets() { 287f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner const KeyT Empty = DenseMapKeyInfo<KeyT>::getEmptyKey(); 288f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner const KeyT Tombstone = DenseMapKeyInfo<KeyT>::getTombstoneKey(); 289f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner 29070a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner while (Ptr != End && (Ptr->first == Empty || Ptr->first == Tombstone)) 291f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner ++Ptr; 292f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner } 293f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner}; 294f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner 295f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattnertemplate<typename KeyT, typename ValueT> 29670a76a633ed5101dbe472404efd989f4f1b3669cChris Lattnerclass DenseMapConstIterator : public DenseMapIterator<KeyT, ValueT> { 29770a76a633ed5101dbe472404efd989f4f1b3669cChris Lattnerpublic: 29870a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner DenseMapConstIterator(const std::pair<KeyT, ValueT> *Pos, 29970a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner const std::pair<KeyT, ValueT> *E) 30070a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner : DenseMapIterator<KeyT, ValueT>(Pos, E) { 30170a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner } 30270a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner const std::pair<KeyT, ValueT> &operator*() const { 30370a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner return *this->Ptr; 30470a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner } 30570a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner const std::pair<KeyT, ValueT> *operator->() const { 30670a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner return this->Ptr; 30770a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner } 30870a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner}; 309f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner 3106e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner} // end namespace llvm 3116e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 3126e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner#endif 313