Add a unit test for 'swap', and fix a pile of bugs in
SmallDenseMap::swap.
First, make it parse cleanly. Yay for uninstantiated methods.
Second, make the inline-buckets case work correctly. This is way
trickier than it should be due to the uninitialized values in empty and
tombstone buckets.
Finally fix a few typos that caused construction/destruction mismatches
in the counting unittest.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158641 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/include/llvm/ADT/DenseMap.h b/include/llvm/ADT/DenseMap.h
index dcae0de..045b5c6 100644
--- a/include/llvm/ADT/DenseMap.h
+++ b/include/llvm/ADT/DenseMap.h
@@ -716,11 +716,40 @@
}
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 +766,14 @@
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));
diff --git a/unittests/ADT/DenseMapTest.cpp b/unittests/ADT/DenseMapTest.cpp
index bd9a3f2..75e7006 100644
--- a/unittests/ADT/DenseMapTest.cpp
+++ b/unittests/ADT/DenseMapTest.cpp
@@ -218,6 +218,42 @@
EXPECT_EQ(this->getValue(), copyMap[this->getKey()]);
}
+// Test swap method
+TYPED_TEST(DenseMapTest, SwapTest) {
+ this->Map[this->getKey()] = this->getValue();
+ TypeParam otherMap;
+
+ this->Map.swap(otherMap);
+ EXPECT_EQ(0u, this->Map.size());
+ EXPECT_TRUE(this->Map.empty());
+ EXPECT_EQ(1u, otherMap.size());
+ EXPECT_EQ(this->getValue(), otherMap[this->getKey()]);
+
+ this->Map.swap(otherMap);
+ EXPECT_EQ(0u, otherMap.size());
+ EXPECT_TRUE(otherMap.empty());
+ EXPECT_EQ(1u, this->Map.size());
+ EXPECT_EQ(this->getValue(), this->Map[this->getKey()]);
+
+ // Make this more interesting by inserting 100 numbers into the map.
+ for (int i = 0; i < 100; ++i)
+ this->Map[this->getKey(i)] = this->getValue(i);
+
+ this->Map.swap(otherMap);
+ EXPECT_EQ(0u, this->Map.size());
+ EXPECT_TRUE(this->Map.empty());
+ EXPECT_EQ(100u, otherMap.size());
+ for (int i = 0; i < 100; ++i)
+ EXPECT_EQ(this->getValue(i), otherMap[this->getKey(i)]);
+
+ this->Map.swap(otherMap);
+ EXPECT_EQ(0u, otherMap.size());
+ EXPECT_TRUE(otherMap.empty());
+ EXPECT_EQ(100u, this->Map.size());
+ for (int i = 0; i < 100; ++i)
+ EXPECT_EQ(this->getValue(i), this->Map[this->getKey(i)]);
+}
+
// A more complex iteration test
TYPED_TEST(DenseMapTest, IterationTest) {
bool visited[100];