X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FADT%2FDenseMap.h;h=cbcf7892c97004c01d0cd6263b1bd3ed9d16682c;hb=75eac5f0ebff4d0ffe10ce6bc8f2867c5f15315b;hp=8c5793853a4353cde5c121d0c3fc09480b52522d;hpb=dd9d38d57bbd2161e04af90a9e03011afb039b16;p=oota-llvm.git diff --git a/include/llvm/ADT/DenseMap.h b/include/llvm/ADT/DenseMap.h index 8c5793853a4..cbcf7892c97 100644 --- a/include/llvm/ADT/DenseMap.h +++ b/include/llvm/ADT/DenseMap.h @@ -310,7 +310,6 @@ protected: std::swap(getNumTombstones(), RHS.getNumTombstones()); } -private: static unsigned getHashValue(const KeyT &Val) { return KeyInfoT::getHashValue(Val); } @@ -325,6 +324,7 @@ private: return KeyInfoT::getTombstoneKey(); } +private: unsigned getNumEntries() const { return static_cast(this)->getNumEntries(); } @@ -423,6 +423,7 @@ private: 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. @@ -442,11 +443,10 @@ private: template 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; } @@ -459,8 +459,10 @@ private: !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; @@ -485,12 +487,13 @@ private: // Otherwise, it's a hash collision or a tombstone, continue quadratic // probing. BucketNo += ProbeAmt++; + BucketNo &= (NumBuckets-1); } } template bool LookupBucketFor(const LookupKeyT &Val, BucketT *&FoundBucket) { - const BucketT *ConstFoundBucket = FoundBucket; + const BucketT *ConstFoundBucket; bool Result = const_cast(this) ->LookupBucketFor(Val, ConstFoundBucket); FoundBucket = const_cast(ConstFoundBucket); @@ -615,8 +618,9 @@ public: 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; @@ -684,8 +688,7 @@ class SmallDenseMap /// 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::union_type - storage; + AlignedCharArrayUnion storage; public: explicit SmallDenseMap(unsigned NumInitBuckets = 0) { @@ -716,11 +719,40 @@ public: } 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) { @@ -737,16 +769,14 @@ public: 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)); @@ -803,24 +833,33 @@ public: 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 TmpStorage; + BucketT *TmpBegin = reinterpret_cast(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; }