diff options
| -rw-r--r-- | llvm/include/llvm/ADT/SparseSet.h | 5 | ||||
| -rw-r--r-- | llvm/unittests/ADT/SparseSetTest.cpp | 20 |
2 files changed, 25 insertions, 0 deletions
diff --git a/llvm/include/llvm/ADT/SparseSet.h b/llvm/include/llvm/ADT/SparseSet.h index a45d1c8d6b8..5b6494d1712 100644 --- a/llvm/include/llvm/ADT/SparseSet.h +++ b/llvm/include/llvm/ADT/SparseSet.h @@ -263,6 +263,11 @@ public: return *insert(ValueT(Key)).first; } + ValueT pop_back_val() { + // Sparse does not need to be cleared, see find(). + return Dense.pop_back_val(); + } + /// erase - Erases an existing element identified by a valid iterator. /// /// This invalidates all iterators, but erase() returns an iterator pointing diff --git a/llvm/unittests/ADT/SparseSetTest.cpp b/llvm/unittests/ADT/SparseSetTest.cpp index eb0e0db283b..4db7a7d61fb 100644 --- a/llvm/unittests/ADT/SparseSetTest.cpp +++ b/llvm/unittests/ADT/SparseSetTest.cpp @@ -183,4 +183,24 @@ TEST(SparseSetTest, AltStructSet) { EXPECT_FALSE(Set.erase(5)); EXPECT_TRUE(Set.erase(6)); } + +TEST(SparseSetTest, PopBack) { + USet Set; + const unsigned UpperBound = 300; + Set.setUniverse(UpperBound); + for (unsigned i = 0; i < UpperBound; ++i) + Set.insert(i); + + // Make sure pop back returns the values in the reverse order we + // inserted them. + unsigned Expected = UpperBound; + while (!Set.empty()) + ASSERT_TRUE(--Expected == Set.pop_back_val()); + + // Insert again the same elements in the sparse set and make sure + // each insertion actually inserts the elements. I.e., check + // that the underlying data structure are properly cleared. + for (unsigned i = 0; i < UpperBound; ++i) + ASSERT_TRUE(Set.insert(i).second); +} } // namespace |
