From afe77f33b2a361ed0d001596dcdde0e16d57abee Mon Sep 17 00:00:00 2001 From: Michael Ilseman Date: Mon, 21 Jan 2013 18:18:53 +0000 Subject: Introduce a new data structure, the SparseMultiSet, and changes to the MI scheduler to use it. A SparseMultiSet adds multiset behavior to SparseSet, while retaining SparseSet's desirable properties. Essentially, SparseMultiSet provides multiset behavior by storing its dense data in doubly linked lists that are inlined into the dense vector. This allows it to provide good data locality as well as vector-like constant-time clear() and fast constant time find(), insert(), and erase(). It also allows SparseMultiSet to have a builtin recycler rather than keeping SparseSet's behavior of always swapping upon removal, which allows it to preserve more iterators. It's often a better alternative to a SparseSet of a growable container or vector-of-vector. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@173064 91177308-0d34-0410-b5e6-96231b3b80d8 --- unittests/ADT/CMakeLists.txt | 1 + unittests/ADT/SparseMultiSetTest.cpp | 235 +++++++++++++++++++++++++++++++++++ 2 files changed, 236 insertions(+) create mode 100644 unittests/ADT/SparseMultiSetTest.cpp (limited to 'unittests/ADT') diff --git a/unittests/ADT/CMakeLists.txt b/unittests/ADT/CMakeLists.txt index 94f7fda..09ca899 100644 --- a/unittests/ADT/CMakeLists.txt +++ b/unittests/ADT/CMakeLists.txt @@ -24,6 +24,7 @@ set(ADTSources SmallStringTest.cpp SmallVectorTest.cpp SparseBitVectorTest.cpp + SparseMultiSetTest.cpp SparseSetTest.cpp StringMapTest.cpp StringRefTest.cpp diff --git a/unittests/ADT/SparseMultiSetTest.cpp b/unittests/ADT/SparseMultiSetTest.cpp new file mode 100644 index 0000000..4ac0388 --- /dev/null +++ b/unittests/ADT/SparseMultiSetTest.cpp @@ -0,0 +1,235 @@ +//===------ ADT/SparseSetTest.cpp - SparseSet unit tests - -----*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#include "llvm/ADT/SparseMultiSet.h" +#include "gtest/gtest.h" + +using namespace llvm; + +namespace { + +typedef SparseMultiSet USet; + +// Empty set tests. +TEST(SparseMultiSetTest, EmptySet) { + USet Set; + EXPECT_TRUE(Set.empty()); + EXPECT_EQ(0u, Set.size()); + + Set.setUniverse(10); + + // Lookups on empty set. + EXPECT_TRUE(Set.find(0) == Set.end()); + EXPECT_TRUE(Set.find(9) == Set.end()); + + // Same thing on a const reference. + const USet &CSet = Set; + EXPECT_TRUE(CSet.empty()); + EXPECT_EQ(0u, CSet.size()); + EXPECT_TRUE(CSet.find(0) == CSet.end()); + USet::const_iterator I = CSet.find(5); + EXPECT_TRUE(I == CSet.end()); +} + +// Single entry set tests. +TEST(SparseMultiSetTest, SingleEntrySet) { + USet Set; + Set.setUniverse(10); + USet::iterator I = Set.insert(5); + EXPECT_TRUE(I != Set.end()); + EXPECT_TRUE(*I == 5); + + EXPECT_FALSE(Set.empty()); + EXPECT_EQ(1u, Set.size()); + + EXPECT_TRUE(Set.find(0) == Set.end()); + EXPECT_TRUE(Set.find(9) == Set.end()); + + EXPECT_FALSE(Set.contains(0)); + EXPECT_TRUE(Set.contains(5)); + + // Extra insert. + I = Set.insert(5); + EXPECT_TRUE(I != Set.end()); + EXPECT_TRUE(I == ++Set.find(5)); + I--; + EXPECT_TRUE(I == Set.find(5)); + + // Erase non-existent element. + I = Set.find(1); + EXPECT_TRUE(I == Set.end()); + EXPECT_EQ(2u, Set.size()); + EXPECT_EQ(5u, *Set.find(5)); + + // Erase iterator. + I = Set.find(5); + EXPECT_TRUE(I != Set.end()); + I = Set.erase(I); + EXPECT_TRUE(I != Set.end()); + I = Set.erase(I); + EXPECT_TRUE(I == Set.end()); + EXPECT_TRUE(Set.empty()); +} + +// Multiple entry set tests. +TEST(SparseMultiSetTest, MultipleEntrySet) { + USet Set; + Set.setUniverse(10); + + Set.insert(5); + Set.insert(5); + Set.insert(5); + Set.insert(3); + Set.insert(2); + Set.insert(1); + Set.insert(4); + EXPECT_EQ(7u, Set.size()); + + // Erase last element by key. + EXPECT_TRUE(Set.erase(Set.find(4)) == Set.end()); + EXPECT_EQ(6u, Set.size()); + EXPECT_FALSE(Set.contains(4)); + EXPECT_TRUE(Set.find(4) == Set.end()); + + // Erase first element by key. + EXPECT_EQ(3u, Set.count(5)); + EXPECT_TRUE(Set.find(5) != Set.end()); + EXPECT_TRUE(Set.erase(Set.find(5)) != Set.end()); + EXPECT_EQ(5u, Set.size()); + EXPECT_EQ(2u, Set.count(5)); + + Set.insert(6); + Set.insert(7); + EXPECT_EQ(7u, Set.size()); + + // Erase tail by iterator. + EXPECT_TRUE(Set.getTail(6) == Set.getHead(6)); + USet::iterator I = Set.erase(Set.find(6)); + EXPECT_TRUE(I == Set.end()); + EXPECT_EQ(6u, Set.size()); + + // Erase tails by iterator. + EXPECT_EQ(2u, Set.count(5)); + I = Set.getTail(5); + I = Set.erase(I); + EXPECT_TRUE(I == Set.end()); + --I; + EXPECT_EQ(1u, Set.count(5)); + EXPECT_EQ(5u, *I); + I = Set.erase(I); + EXPECT_TRUE(I == Set.end()); + EXPECT_EQ(0u, Set.count(5)); + + Set.insert(8); + Set.insert(8); + Set.insert(8); + Set.insert(8); + Set.insert(8); + + // Erase all the 8s + EXPECT_EQ(5u, std::distance(Set.getHead(8), Set.end())); + Set.eraseAll(8); + EXPECT_EQ(0u, std::distance(Set.getHead(8), Set.end())); + + // Clear and resize the universe. + Set.clear(); + EXPECT_EQ(0u, Set.size()); + EXPECT_FALSE(Set.contains(3)); + Set.setUniverse(1000); + + // Add more than 256 elements. + for (unsigned i = 100; i != 800; ++i) + Set.insert(i); + + for (unsigned i = 0; i != 10; ++i) + Set.eraseAll(i); + + for (unsigned i = 100; i != 800; ++i) + EXPECT_EQ(1u, Set.count(i)); + + EXPECT_FALSE(Set.contains(99)); + EXPECT_FALSE(Set.contains(800)); + EXPECT_EQ(700u, Set.size()); +} + +// Test out iterators +TEST(SparseMultiSetTest, Iterators) { + USet Set; + Set.setUniverse(100); + + Set.insert(0); + Set.insert(1); + Set.insert(2); + Set.insert(0); + Set.insert(1); + Set.insert(0); + + USet::RangePair RangePair = Set.equal_range(0); + USet::iterator B = RangePair.first; + USet::iterator E = RangePair.second; + + // Move the iterators around, going to end and coming back. + EXPECT_EQ(3u, std::distance(B, E)); + EXPECT_EQ(B, --(--(--E))); + EXPECT_EQ(++(++(++E)), Set.end()); + EXPECT_EQ(B, --(--(--E))); + EXPECT_EQ(++(++(++E)), Set.end()); + + // Insert into the tail, and move around again + Set.insert(0); + EXPECT_EQ(B, --(--(--(--E)))); + EXPECT_EQ(++(++(++(++E))), Set.end()); + EXPECT_EQ(B, --(--(--(--E)))); + EXPECT_EQ(++(++(++(++E))), Set.end()); + + // Erase a tail, and move around again + USet::iterator Erased = Set.erase(Set.getTail(0)); + EXPECT_EQ(Erased, E); + EXPECT_EQ(B, --(--(--E))); + + USet Set2; + Set2.setUniverse(11); + Set2.insert(3); + EXPECT_TRUE(!Set2.contains(0)); + EXPECT_TRUE(!Set.contains(3)); + + EXPECT_EQ(Set2.getHead(3), Set2.getTail(3)); + EXPECT_EQ(Set2.getHead(0), Set2.getTail(0)); + B = Set2.find(3); + EXPECT_EQ(Set2.find(3), --(++B)); +} + +struct Alt { + unsigned Value; + explicit Alt(unsigned x) : Value(x) {} + unsigned getSparseSetIndex() const { return Value - 1000; } +}; + +TEST(SparseMultiSetTest, AltStructSet) { + typedef SparseMultiSet ASet; + ASet Set; + Set.setUniverse(10); + Set.insert(Alt(1005)); + + ASet::iterator I = Set.find(5); + ASSERT_TRUE(I != Set.end()); + EXPECT_EQ(1005u, I->Value); + + Set.insert(Alt(1006)); + Set.insert(Alt(1006)); + I = Set.erase(Set.find(6)); + ASSERT_TRUE(I != Set.end()); + EXPECT_EQ(1006u, I->Value); + I = Set.erase(Set.find(6)); + ASSERT_TRUE(I == Set.end()); + + EXPECT_TRUE(Set.contains(5)); + EXPECT_FALSE(Set.contains(6)); +} +} // namespace -- cgit v1.1