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));
return; // Nothing to do.
// First move the inline buckets into a temporary storage.
- typename AlignedCharArray<BucketT[InlineBuckets]>::union_type
- TmpStorage;
+ AlignedCharArrayUnion<BucketT[InlineBuckets]> TmpStorage;
BucketT *TmpBegin = reinterpret_cast<BucketT *>(TmpStorage.buffer);
BucketT *TmpEnd = TmpBegin;
for (BucketT *P = getBuckets(), *E = P + InlineBuckets; P != E; ++P) {
if (!KeyInfoT::isEqual(P->first, EmptyKey) &&
!KeyInfoT::isEqual(P->first, TombstoneKey)) {
- assert((TmpEnd - TmpBegin) < InlineBuckets &&
+ 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));