bool IsConst = false>
class DenseMapIterator;
-template<typename KeyT, typename ValueT,
- typename KeyInfoT = DenseMapInfo<KeyT> >
-class DenseMap {
+template<typename DerivedT,
+ typename KeyT, typename ValueT, typename KeyInfoT>
+class DenseMapBase {
+protected:
typedef std::pair<KeyT, ValueT> BucketT;
- BucketT *Buckets;
-
- unsigned NumBuckets;
unsigned NumEntries;
unsigned NumTombstones;
+
public:
typedef KeyT key_type;
typedef ValueT mapped_type;
typedef BucketT value_type;
- DenseMap(const DenseMap &other) {
- NumBuckets = 0;
- CopyFrom(other);
- }
-
-#if LLVM_USE_RVALUE_REFERENCES
- DenseMap(DenseMap &&other) {
- init(0);
- swap(other);
- }
-#endif
-
- explicit DenseMap(unsigned NumInitBuckets = 0) {
- init(NumInitBuckets);
- }
-
- template<typename InputIt>
- DenseMap(const InputIt &I, const InputIt &E) {
- init(NextPowerOf2(std::distance(I, E)));
- insert(I, E);
- }
-
- ~DenseMap() {
- DestroyAll();
- }
-
typedef DenseMapIterator<KeyT, ValueT, KeyInfoT> iterator;
typedef DenseMapIterator<KeyT, ValueT,
KeyInfoT, true> const_iterator;
inline iterator begin() {
// When the map is empty, avoid the overhead of AdvancePastEmptyBuckets().
- return empty() ? end() : iterator(Buckets, Buckets+NumBuckets);
+ return empty() ? end() : iterator(getBuckets(), getBucketsEnd());
}
inline iterator end() {
- return iterator(Buckets+NumBuckets, Buckets+NumBuckets, true);
+ return iterator(getBucketsEnd(), getBucketsEnd(), true);
}
inline const_iterator begin() const {
- return empty() ? end() : const_iterator(Buckets, Buckets+NumBuckets);
+ return empty() ? end() : const_iterator(getBuckets(), getBucketsEnd());
}
inline const_iterator end() const {
- return const_iterator(Buckets+NumBuckets, Buckets+NumBuckets, true);
+ return const_iterator(getBucketsEnd(), getBucketsEnd(), true);
}
bool empty() const { return NumEntries == 0; }
/// Grow the densemap so that it has at least Size buckets. Does not shrink
void resize(size_t Size) {
- if (Size > NumBuckets)
+ if (Size > getNumBuckets())
grow(Size);
}
// If the capacity of the array is huge, and the # elements used is small,
// shrink the array.
- if (NumEntries * 4 < NumBuckets && NumBuckets > 64) {
+ if (NumEntries * 4 < getNumBuckets() && getNumBuckets() > 64) {
shrink_and_clear();
return;
}
const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey();
- for (BucketT *P = Buckets, *E = Buckets+NumBuckets; P != E; ++P) {
+ for (BucketT *P = getBuckets(), *E = getBucketsEnd(); P != E; ++P) {
if (!KeyInfoT::isEqual(P->first, EmptyKey)) {
if (!KeyInfoT::isEqual(P->first, TombstoneKey)) {
P->second.~ValueT();
iterator find(const KeyT &Val) {
BucketT *TheBucket;
if (LookupBucketFor(Val, TheBucket))
- return iterator(TheBucket, Buckets+NumBuckets, true);
+ return iterator(TheBucket, getBucketsEnd(), true);
return end();
}
const_iterator find(const KeyT &Val) const {
BucketT *TheBucket;
if (LookupBucketFor(Val, TheBucket))
- return const_iterator(TheBucket, Buckets+NumBuckets, true);
+ return const_iterator(TheBucket, getBucketsEnd(), true);
return end();
}
iterator find_as(const LookupKeyT &Val) {
BucketT *TheBucket;
if (LookupBucketFor(Val, TheBucket))
- return iterator(TheBucket, Buckets+NumBuckets, true);
+ return iterator(TheBucket, getBucketsEnd(), true);
return end();
}
template<class LookupKeyT>
const_iterator find_as(const LookupKeyT &Val) const {
BucketT *TheBucket;
if (LookupBucketFor(Val, TheBucket))
- return const_iterator(TheBucket, Buckets+NumBuckets, true);
+ return const_iterator(TheBucket, getBucketsEnd(), true);
return end();
}
std::pair<iterator, bool> insert(const std::pair<KeyT, ValueT> &KV) {
BucketT *TheBucket;
if (LookupBucketFor(KV.first, TheBucket))
- return std::make_pair(iterator(TheBucket, Buckets+NumBuckets, true),
+ return std::make_pair(iterator(TheBucket, getBucketsEnd(), true),
false); // Already in map.
// Otherwise, insert the new element.
TheBucket = InsertIntoBucket(KV.first, KV.second, TheBucket);
- return std::make_pair(iterator(TheBucket, Buckets+NumBuckets, true), true);
+ return std::make_pair(iterator(TheBucket, getBucketsEnd(), true), true);
}
/// insert - Range insertion of pairs.
++NumTombstones;
}
- void swap(DenseMap& RHS) {
- std::swap(NumBuckets, RHS.NumBuckets);
- std::swap(Buckets, RHS.Buckets);
- std::swap(NumEntries, RHS.NumEntries);
- std::swap(NumTombstones, RHS.NumTombstones);
- }
-
value_type& FindAndConstruct(const KeyT &Key) {
BucketT *TheBucket;
if (LookupBucketFor(Key, TheBucket))
}
#endif
- DenseMap& operator=(const DenseMap& other) {
- CopyFrom(other);
- return *this;
- }
-
-#if LLVM_USE_RVALUE_REFERENCES
- DenseMap& operator=(DenseMap &&other) {
- DestroyAll();
- init(0);
- swap(other);
- return *this;
- }
-#endif
-
/// isPointerIntoBucketsArray - Return true if the specified pointer points
/// somewhere into the DenseMap's array of buckets (i.e. either to a key or
/// value in the DenseMap).
bool isPointerIntoBucketsArray(const void *Ptr) const {
- return Ptr >= Buckets && Ptr < Buckets+NumBuckets;
+ return Ptr >= getBuckets() && Ptr < getBucketsEnd();
}
/// getPointerIntoBucketsArray() - Return an opaque pointer into the buckets
/// array. In conjunction with the previous method, this can be used to
/// determine whether an insertion caused the DenseMap to reallocate.
- const void *getPointerIntoBucketsArray() const { return Buckets; }
+ const void *getPointerIntoBucketsArray() const { return getBuckets(); }
-private:
- void DestroyAll() {
- if (NumBuckets == 0) // Nothing to do.
+protected:
+ DenseMapBase() : NumEntries(), NumTombstones() {}
+
+ void destroyAll() {
+ if (getNumBuckets() == 0) // Nothing to do.
return;
const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey();
- for (BucketT *P = Buckets, *E = Buckets+NumBuckets; P != E; ++P) {
+ for (BucketT *P = getBuckets(), *E = getBucketsEnd(); P != E; ++P) {
if (!KeyInfoT::isEqual(P->first, EmptyKey) &&
!KeyInfoT::isEqual(P->first, TombstoneKey))
P->second.~ValueT();
}
#ifndef NDEBUG
- memset((void*)Buckets, 0x5a, sizeof(BucketT)*NumBuckets);
+ memset((void*)getBuckets(), 0x5a, sizeof(BucketT)*getNumBuckets());
#endif
- operator delete(Buckets);
}
- void CopyFrom(const DenseMap& other) {
- DestroyAll();
+ void initEmpty() {
+ NumEntries = 0;
+ NumTombstones = 0;
+
+ assert((getNumBuckets() & (getNumBuckets()-1)) == 0 &&
+ "# initial buckets must be a power of two!");
+ const KeyT EmptyKey = getEmptyKey();
+ for (BucketT *B = getBuckets(), *E = getBucketsEnd(); B != E; ++B)
+ new (&B->first) KeyT(EmptyKey);
+ }
- NumEntries = other.NumEntries;
- NumTombstones = other.NumTombstones;
- NumBuckets = other.NumBuckets;
+ void moveFromOldBuckets(BucketT *OldBucketsBegin, BucketT *OldBucketsEnd) {
+ initEmpty();
- if (NumBuckets == 0) {
- Buckets = 0;
- return;
+ // Insert all the old elements.
+ const KeyT EmptyKey = getEmptyKey();
+ const KeyT TombstoneKey = getTombstoneKey();
+ for (BucketT *B = OldBucketsBegin, *E = OldBucketsEnd; B != E; ++B) {
+ if (!KeyInfoT::isEqual(B->first, EmptyKey) &&
+ !KeyInfoT::isEqual(B->first, TombstoneKey)) {
+ // Insert the key/value into the new table.
+ BucketT *DestBucket;
+ bool FoundVal = LookupBucketFor(B->first, DestBucket);
+ (void)FoundVal; // silence warning.
+ assert(!FoundVal && "Key already in new map?");
+ DestBucket->first = llvm_move(B->first);
+ new (&DestBucket->second) ValueT(llvm_move(B->second));
+ ++NumEntries;
+
+ // Free the value.
+ B->second.~ValueT();
+ }
+ B->first.~KeyT();
}
- Buckets = static_cast<BucketT*>(operator new(sizeof(BucketT) * NumBuckets));
+#ifndef NDEBUG
+ if (OldBucketsBegin != OldBucketsEnd)
+ memset((void*)OldBucketsBegin, 0x5a,
+ sizeof(BucketT) * (OldBucketsEnd - OldBucketsBegin));
+#endif
+ }
+
+ template <typename OtherBaseT>
+ void copyFrom(const DenseMapBase<OtherBaseT, KeyT, ValueT, KeyInfoT>& other) {
+ assert(getNumBuckets() == other.getNumBuckets());
+
+ NumEntries = other.NumEntries;
+ NumTombstones = other.NumTombstones;
if (isPodLike<KeyT>::value && isPodLike<ValueT>::value)
- memcpy(Buckets, other.Buckets, NumBuckets * sizeof(BucketT));
+ memcpy(getBuckets(), other.getBuckets(),
+ getNumBuckets() * sizeof(BucketT));
else
- for (size_t i = 0; i < NumBuckets; ++i) {
- new (&Buckets[i].first) KeyT(other.Buckets[i].first);
- if (!KeyInfoT::isEqual(Buckets[i].first, getEmptyKey()) &&
- !KeyInfoT::isEqual(Buckets[i].first, getTombstoneKey()))
- new (&Buckets[i].second) ValueT(other.Buckets[i].second);
+ for (size_t i = 0; i < getNumBuckets(); ++i) {
+ new (&getBuckets()[i].first) KeyT(other.getBuckets()[i].first);
+ if (!KeyInfoT::isEqual(getBuckets()[i].first, getEmptyKey()) &&
+ !KeyInfoT::isEqual(getBuckets()[i].first, getTombstoneKey()))
+ new (&getBuckets()[i].second) ValueT(other.getBuckets()[i].second);
}
}
+ void swap(DenseMapBase& RHS) {
+ std::swap(NumEntries, RHS.NumEntries);
+ std::swap(NumTombstones, RHS.NumTombstones);
+ }
+
+private:
+ static unsigned getHashValue(const KeyT &Val) {
+ return KeyInfoT::getHashValue(Val);
+ }
+ template<typename LookupKeyT>
+ static unsigned getHashValue(const LookupKeyT &Val) {
+ return KeyInfoT::getHashValue(Val);
+ }
+ static const KeyT getEmptyKey() {
+ return KeyInfoT::getEmptyKey();
+ }
+ static const KeyT getTombstoneKey() {
+ return KeyInfoT::getTombstoneKey();
+ }
+
+ BucketT *getBuckets() const {
+ return static_cast<const DerivedT *>(this)->getBuckets();
+ }
+
+ unsigned getNumBuckets() const {
+ return static_cast<const DerivedT *>(this)->getNumBuckets();
+ }
+
+ BucketT *getBucketsEnd() const {
+ return getBuckets() + getNumBuckets();
+ }
+
+ void grow(unsigned AtLeast) {
+ static_cast<DerivedT *>(this)->grow(AtLeast);
+ }
+
+ void shrink_and_clear() {
+ static_cast<DerivedT *>(this)->shrink_and_clear();
+ NumTombstones = 0;
+ NumEntries = 0;
+ }
+
+
BucketT *InsertIntoBucket(const KeyT &Key, const ValueT &Value,
BucketT *TheBucket) {
TheBucket = InsertIntoBucketImpl(Key, TheBucket);
// probe almost the entire table until it found the empty bucket. If the
// table completely filled with tombstones, no lookup would ever succeed,
// causing infinite loops in lookup.
- ++NumEntries;
- if (NumEntries*4 >= NumBuckets*3) {
- this->grow(NumBuckets * 2);
+ unsigned NewNumEntries = NumEntries + 1;
+ if (NewNumEntries*4 >= getNumBuckets()*3) {
+ this->grow(getNumBuckets() * 2);
LookupBucketFor(Key, TheBucket);
}
- if (NumBuckets-(NumEntries+NumTombstones) < NumBuckets/8) {
- this->grow(NumBuckets);
+ if (getNumBuckets()-(NewNumEntries+NumTombstones) < getNumBuckets()/8) {
+ this->grow(getNumBuckets());
LookupBucketFor(Key, TheBucket);
}
+ // Only update the state after we've grown our bucket space appropriately
+ // so that when growing buckets we have self-consistent entry count.
+ ++NumEntries;
+
// If we are writing over a tombstone, remember this.
if (!KeyInfoT::isEqual(TheBucket->first, getEmptyKey()))
--NumTombstones;
return TheBucket;
}
- static unsigned getHashValue(const KeyT &Val) {
- return KeyInfoT::getHashValue(Val);
- }
- template<typename LookupKeyT>
- static unsigned getHashValue(const LookupKeyT &Val) {
- return KeyInfoT::getHashValue(Val);
- }
- static const KeyT getEmptyKey() {
- return KeyInfoT::getEmptyKey();
- }
- static const KeyT getTombstoneKey() {
- return KeyInfoT::getTombstoneKey();
- }
-
/// LookupBucketFor - Lookup the appropriate bucket for Val, returning it in
/// FoundBucket. If the bucket contains the key and a value, this returns
/// true, otherwise it returns a bucket with an empty marker or tombstone and
bool LookupBucketFor(const LookupKeyT &Val, BucketT *&FoundBucket) const {
unsigned BucketNo = getHashValue(Val);
unsigned ProbeAmt = 1;
- BucketT *BucketsPtr = Buckets;
+ BucketT *BucketsPtr = getBuckets();
- if (NumBuckets == 0) {
+ if (getNumBuckets() == 0) {
FoundBucket = 0;
return false;
}
"Empty/Tombstone value shouldn't be inserted into map!");
while (1) {
- BucketT *ThisBucket = BucketsPtr + (BucketNo & (NumBuckets-1));
+ BucketT *ThisBucket = BucketsPtr + (BucketNo & (getNumBuckets()-1));
// Found Val's bucket? If so, return it.
if (KeyInfoT::isEqual(Val, ThisBucket->first)) {
FoundBucket = ThisBucket;
}
}
- void init(unsigned InitBuckets) {
- NumEntries = 0;
- NumTombstones = 0;
- NumBuckets = InitBuckets;
+public:
+ /// Return the approximate size (in bytes) of the actual map.
+ /// This is just the raw memory used by DenseMap.
+ /// If entries are pointers to objects, the size of the referenced objects
+ /// are not included.
+ size_t getMemorySize() const {
+ return getNumBuckets() * sizeof(BucketT);
+ }
+};
- if (InitBuckets == 0) {
- Buckets = 0;
- return;
- }
+template<typename KeyT, typename ValueT,
+ typename KeyInfoT = DenseMapInfo<KeyT> >
+class DenseMap
+ : public DenseMapBase<DenseMap<KeyT, ValueT, KeyInfoT>,
+ KeyT, ValueT, KeyInfoT> {
+ // Lift some types from the dependent base class into this class for
+ // simplicity of referring to them.
+ typedef DenseMapBase<DenseMap, KeyT, ValueT, KeyInfoT> BaseT;
+ typedef typename BaseT::BucketT BucketT;
+ friend class DenseMapBase<DenseMap, KeyT, ValueT, KeyInfoT>;
- assert(InitBuckets && (InitBuckets & (InitBuckets-1)) == 0 &&
- "# initial buckets must be a power of two!");
- Buckets = static_cast<BucketT*>(operator new(sizeof(BucketT)*InitBuckets));
- // Initialize all the keys to EmptyKey.
- const KeyT EmptyKey = getEmptyKey();
- for (unsigned i = 0; i != InitBuckets; ++i)
- new (&Buckets[i].first) KeyT(EmptyKey);
+ BucketT *Buckets;
+ unsigned NumBuckets;
+
+public:
+ explicit DenseMap(unsigned NumInitBuckets = 0) {
+ init(NumInitBuckets);
}
- void grow(unsigned AtLeast) {
- unsigned OldNumBuckets = NumBuckets;
- BucketT *OldBuckets = Buckets;
+ DenseMap(const DenseMap &other) {
+ init(0);
+ copyFrom(other);
+ }
- if (NumBuckets < 64)
- NumBuckets = 64;
+#if LLVM_USE_RVALUE_REFERENCES
+ DenseMap(DenseMap &&other) {
+ init(0);
+ swap(other);
+ }
+#endif
- // Double the number of buckets.
- while (NumBuckets < AtLeast)
- NumBuckets <<= 1;
- NumTombstones = 0;
- Buckets = static_cast<BucketT*>(operator new(sizeof(BucketT)*NumBuckets));
+ template<typename InputIt>
+ DenseMap(const InputIt &I, const InputIt &E) {
+ init(NextPowerOf2(std::distance(I, E)));
+ this->insert(I, E);
+ }
- // Initialize all the keys to EmptyKey.
- const KeyT EmptyKey = getEmptyKey();
- for (unsigned i = 0, e = NumBuckets; i != e; ++i)
- new (&Buckets[i].first) KeyT(EmptyKey);
+ ~DenseMap() {
+ this->destroyAll();
+ operator delete(Buckets);
+ }
- // Insert all the old elements.
- const KeyT TombstoneKey = getTombstoneKey();
- for (BucketT *B = OldBuckets, *E = OldBuckets+OldNumBuckets; B != E; ++B) {
- if (!KeyInfoT::isEqual(B->first, EmptyKey) &&
- !KeyInfoT::isEqual(B->first, TombstoneKey)) {
- // Insert the key/value into the new table.
- BucketT *DestBucket;
- bool FoundVal = LookupBucketFor(B->first, DestBucket);
- (void)FoundVal; // silence warning.
- assert(!FoundVal && "Key already in new map?");
- DestBucket->first = llvm_move(B->first);
- new (&DestBucket->second) ValueT(llvm_move(B->second));
+ void swap(DenseMap& RHS) {
+ std::swap(NumBuckets, RHS.NumBuckets);
+ std::swap(Buckets, RHS.Buckets);
- // Free the value.
- B->second.~ValueT();
- }
- B->first.~KeyT();
- }
+ this->BaseT::swap(RHS);
+ }
-#ifndef NDEBUG
- if (OldNumBuckets)
- memset((void*)OldBuckets, 0x5a, sizeof(BucketT)*OldNumBuckets);
+ DenseMap& operator=(const DenseMap& other) {
+ copyFrom(other);
+ return *this;
+ }
+
+#if LLVM_USE_RVALUE_REFERENCES
+ DenseMap& operator=(DenseMap &&other) {
+ this->destroyAll();
+ operator delete(Buckets);
+ init(0);
+ swap(other);
+ return *this;
+ }
#endif
- // Free the old table.
- operator delete(OldBuckets);
+
+ void copyFrom(const DenseMap& other) {
+ this->destroyAll();
+ operator delete(Buckets);
+
+ if (allocateBuckets(other.NumBuckets))
+ this->BaseT::copyFrom(other);
}
- void shrink_and_clear() {
+ void init(unsigned InitBuckets) {
+ if (allocateBuckets(InitBuckets))
+ this->BaseT::initEmpty();
+ }
+
+ void grow(unsigned AtLeast) {
unsigned OldNumBuckets = NumBuckets;
BucketT *OldBuckets = Buckets;
- // Reduce the number of buckets.
- NumBuckets = NumEntries > 32 ? 1 << (Log2_32_Ceil(NumEntries) + 1)
- : 64;
- NumTombstones = 0;
- Buckets = static_cast<BucketT*>(operator new(sizeof(BucketT)*NumBuckets));
-
- // Initialize all the keys to EmptyKey.
- const KeyT EmptyKey = getEmptyKey();
- for (unsigned i = 0, e = NumBuckets; i != e; ++i)
- new (&Buckets[i].first) KeyT(EmptyKey);
-
- // Free the old buckets.
- const KeyT TombstoneKey = getTombstoneKey();
- for (BucketT *B = OldBuckets, *E = OldBuckets+OldNumBuckets; B != E; ++B) {
- if (!KeyInfoT::isEqual(B->first, EmptyKey) &&
- !KeyInfoT::isEqual(B->first, TombstoneKey)) {
- // Free the value.
- B->second.~ValueT();
- }
- B->first.~KeyT();
+ allocateBuckets(std::max<unsigned>(64, NextPowerOf2(AtLeast)));
+ assert(Buckets);
+ if (!OldBuckets) {
+ this->BaseT::initEmpty();
+ return;
}
-#ifndef NDEBUG
- memset((void*)OldBuckets, 0x5a, sizeof(BucketT)*OldNumBuckets);
-#endif
+ this->moveFromOldBuckets(OldBuckets, OldBuckets+OldNumBuckets);
+
// Free the old table.
operator delete(OldBuckets);
+ }
- NumEntries = 0;
+ void shrink_and_clear() {
+ unsigned OldSize = this->size();
+ this->destroyAll();
+
+ // Reduce the number of buckets.
+ unsigned NewNumBuckets
+ = std::max(64, 1 << (Log2_32_Ceil(OldSize) + 1));
+ if (NewNumBuckets == NumBuckets) {
+ this->BaseT::initEmpty();
+ return;
+ }
+
+ operator delete(Buckets);
+ init(NewNumBuckets);
}
-
-public:
- /// Return the approximate size (in bytes) of the actual map.
- /// This is just the raw memory used by DenseMap.
- /// If entries are pointers to objects, the size of the referenced objects
- /// are not included.
- size_t getMemorySize() const {
- return NumBuckets * sizeof(BucketT);
+
+private:
+ BucketT *getBuckets() const {
+ return Buckets;
+ }
+
+ unsigned getNumBuckets() const {
+ return NumBuckets;
+ }
+
+ bool allocateBuckets(unsigned Num) {
+ NumBuckets = Num;
+ if (NumBuckets == 0) {
+ Buckets = 0;
+ return false;
+ }
+
+ Buckets = static_cast<BucketT*>(operator new(sizeof(BucketT) * NumBuckets));
+ return true;
}
};
projects / oota-llvm.git / commitdiff