std::swap(getNumTombstones(), RHS.getNumTombstones());
}
-private:
static unsigned getHashValue(const KeyT &Val) {
return KeyInfoT::getHashValue(Val);
}
return KeyInfoT::getTombstoneKey();
}
+private:
unsigned getNumEntries() const {
return static_cast<const DerivedT *>(this)->getNumEntries();
}
this->grow(NumBuckets);
LookupBucketFor(Key, TheBucket);
}
+ assert(TheBucket);
// Only update the state after we've grown our bucket space appropriately
// so that when growing buckets we have self-consistent entry count.
template<typename LookupKeyT>
bool LookupBucketFor(const LookupKeyT &Val,
const BucketT *&FoundBucket) const {
- unsigned BucketNo = getHashValue(Val);
- unsigned ProbeAmt = 1;
const BucketT *BucketsPtr = getBuckets();
+ const unsigned NumBuckets = getNumBuckets();
- if (getNumBuckets() == 0) {
+ if (NumBuckets == 0) {
FoundBucket = 0;
return false;
}
!KeyInfoT::isEqual(Val, TombstoneKey) &&
"Empty/Tombstone value shouldn't be inserted into map!");
+ unsigned BucketNo = getHashValue(Val) & (NumBuckets-1);
+ unsigned ProbeAmt = 1;
while (1) {
- const BucketT *ThisBucket = BucketsPtr + (BucketNo & (getNumBuckets()-1));
+ const BucketT *ThisBucket = BucketsPtr + BucketNo;
// Found Val's bucket? If so, return it.
if (KeyInfoT::isEqual(Val, ThisBucket->first)) {
FoundBucket = ThisBucket;
// Otherwise, it's a hash collision or a tombstone, continue quadratic
// probing.
BucketNo += ProbeAmt++;
+ BucketNo &= (NumBuckets-1);
}
}
template <typename LookupKeyT>
bool LookupBucketFor(const LookupKeyT &Val, BucketT *&FoundBucket) {
- const BucketT *ConstFoundBucket = FoundBucket;
+ const BucketT *ConstFoundBucket;
bool Result = const_cast<const DenseMapBase *>(this)
->LookupBucketFor(Val, ConstFoundBucket);
FoundBucket = const_cast<BucketT *>(ConstFoundBucket);
this->destroyAll();
// Reduce the number of buckets.
- unsigned NewNumBuckets
- = std::max(64, 1 << (Log2_32_Ceil(OldNumEntries) + 1));
+ unsigned NewNumBuckets = 0;
+ if (OldNumEntries)
+ NewNumBuckets = std::max(64, 1 << (Log2_32_Ceil(OldNumEntries) + 1));
if (NewNumBuckets == NumBuckets) {
this->BaseT::initEmpty();
return;
/// A "union" of an inline bucket array and the struct representing
/// a large bucket. This union will be discriminated by the 'Small' bit.
- typename AlignedCharArray<BucketT[InlineBuckets], LargeRep>::union_type
- storage;
+ AlignedCharArrayUnion<BucketT[InlineBuckets], LargeRep> storage;
public:
explicit SmallDenseMap(unsigned NumInitBuckets = 0) {
}
void swap(SmallDenseMap& RHS) {
- std::swap(NumEntries, RHS.NumEntries);
+ unsigned TmpNumEntries = RHS.NumEntries;
+ RHS.NumEntries = NumEntries;
+ NumEntries = TmpNumEntries;
std::swap(NumTombstones, RHS.NumTombstones);
+
+ const KeyT EmptyKey = this->getEmptyKey();
+ const KeyT TombstoneKey = this->getTombstoneKey();
if (Small && RHS.Small) {
- for (unsigned i = 0, e = InlineBuckets; i != e; ++i)
- std::swap(getInlineBuckets()[i], RHS.getInlineBuckes()[i]);
+ // If we're swapping inline bucket arrays, we have to cope with some of
+ // the tricky bits of DenseMap's storage system: the buckets are not
+ // fully initialized. Thus we swap every key, but we may have
+ // a one-directional move of the value.
+ for (unsigned i = 0, e = InlineBuckets; i != e; ++i) {
+ BucketT *LHSB = &getInlineBuckets()[i],
+ *RHSB = &RHS.getInlineBuckets()[i];
+ bool hasLHSValue = (!KeyInfoT::isEqual(LHSB->first, EmptyKey) &&
+ !KeyInfoT::isEqual(LHSB->first, TombstoneKey));
+ bool hasRHSValue = (!KeyInfoT::isEqual(RHSB->first, EmptyKey) &&
+ !KeyInfoT::isEqual(RHSB->first, TombstoneKey));
+ if (hasLHSValue && hasRHSValue) {
+ // Swap together if we can...
+ std::swap(*LHSB, *RHSB);
+ continue;
+ }
+ // Swap separately and handle any assymetry.
+ std::swap(LHSB->first, RHSB->first);
+ if (hasLHSValue) {
+ new (&RHSB->second) ValueT(llvm_move(LHSB->second));
+ LHSB->second.~ValueT();
+ } else if (hasRHSValue) {
+ new (&LHSB->second) ValueT(llvm_move(RHSB->second));
+ RHSB->second.~ValueT();
+ }
+ }
return;
}
if (!Small && !RHS.Small) {
LargeSide.getLargeRep()->~LargeRep();
LargeSide.Small = true;
// This is similar to the standard move-from-old-buckets, but the bucket
- // count hasn't actually rotate in this case. So we have to carefully
+ // count hasn't actually rotated in this case. So we have to carefully
// move construct the keys and values into their new locations, but there
// is no need to re-hash things.
- const KeyT EmptyKey = this->getEmptyKey();
- const KeyT TombstoneKey = this->getTombstoneKey();
for (unsigned i = 0, e = InlineBuckets; i != e; ++i) {
BucketT *NewB = &LargeSide.getInlineBuckets()[i],
*OldB = &SmallSide.getInlineBuckets()[i];
new (&NewB->first) KeyT(llvm_move(OldB->first));
- NewB->first.~KeyT();
+ OldB->first.~KeyT();
if (!KeyInfoT::isEqual(NewB->first, EmptyKey) &&
!KeyInfoT::isEqual(NewB->first, TombstoneKey)) {
new (&NewB->second) ValueT(llvm_move(OldB->second));
if (AtLeast <= InlineBuckets)
return; // Nothing to do.
- // First grow an allocated bucket array in another map and move our
- // entries into it.
- // FIXME: This is wasteful, we don't need the inline buffer here, and we
- // certainly don't need to initialize it to empty.
- SmallDenseMap TmpMap;
- TmpMap.Small = false;
- new (TmpMap.getLargeRep()) LargeRep(allocateBuckets(AtLeast));
- TmpMap.moveFromOldBuckets(getInlineBuckets(),
- getInlineBuckets()+InlineBuckets);
-
- // Now steal the innards back into this map, and arrange for the
- // temporary map to be cleanly torn down.
- assert(NumEntries == TmpMap.NumEntries);
+ // First move the inline buckets into a temporary storage.
+ AlignedCharArrayUnion<BucketT[InlineBuckets]> TmpStorage;
+ BucketT *TmpBegin = reinterpret_cast<BucketT *>(TmpStorage.buffer);
+ BucketT *TmpEnd = TmpBegin;
+
+ // Loop over the buckets, moving non-empty, non-tombstones into the
+ // temporary storage. Have the loop move the TmpEnd forward as it goes.
+ const KeyT EmptyKey = this->getEmptyKey();
+ const KeyT TombstoneKey = this->getTombstoneKey();
+ for (BucketT *P = getBuckets(), *E = P + InlineBuckets; P != E; ++P) {
+ if (!KeyInfoT::isEqual(P->first, EmptyKey) &&
+ !KeyInfoT::isEqual(P->first, TombstoneKey)) {
+ assert(size_t(TmpEnd - TmpBegin) < InlineBuckets &&
+ "Too many inline buckets!");
+ new (&TmpEnd->first) KeyT(llvm_move(P->first));
+ new (&TmpEnd->second) ValueT(llvm_move(P->second));
+ ++TmpEnd;
+ P->second.~ValueT();
+ }
+ P->first.~KeyT();
+ }
+
+ // Now make this map use the large rep, and move all the entries back
+ // into it.
Small = false;
- NumTombstones = llvm_move(TmpMap.NumTombstones);
- new (getLargeRep()) LargeRep(llvm_move(*TmpMap.getLargeRep()));
- TmpMap.getLargeRep()->~LargeRep();
- TmpMap.Small = true;
+ new (getLargeRep()) LargeRep(allocateBuckets(AtLeast));
+ this->moveFromOldBuckets(TmpBegin, TmpEnd);
return;
}
projects / oota-llvm.git / blobdiff