Add tests for *DenesMap for both key and value types' construction and

destruction and fix a bug in SmallDenseMap they caught.

This is kind of a poor-man's version of the testing that just adds the
addresses to a set on construction and removes them on destruction. We
check that double construction and double destruction don't occur.
Amusingly enough, this is enough to catch a lot of SmallDenseMap issues
because we spend a lot of time with fixed stable addresses in the inline
buffer.

The SmallDenseMap bug fix included makes grow() not double-destroy in
some cases. It also fixes a FIXME there, the code was pretty crappy. We
now don't have any wasted initialization, but we do move the entries in
inline bucket array an extra time. It's probably a better tradeoff, and
is much easier to get correct.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158639 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 28 insertions, 18 deletions

diff --git a/include/llvm/ADT/DenseMap.h b/include/llvm/ADT/DenseMap.h
index 8c57938..dcae0de 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<const DerivedT *>(this)->getNumEntries();
   }
@@ -803,24 +803,34 @@ 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.
+      typename AlignedCharArray<BucketT[InlineBuckets]>::union_type
+        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((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;
     }