162588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen//===------ ADT/SparseSetTest.cpp - SparseSet unit tests - -----*- C++ -*-===// 262588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen// 362588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen// The LLVM Compiler Infrastructure 462588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen// 562588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen// This file is distributed under the University of Illinois Open Source 662588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen// License. See LICENSE.TXT for details. 762588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen// 862588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 962588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen 1062588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen#include "llvm/ADT/SparseSet.h" 1162588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen#include "gtest/gtest.h" 1262588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen 1362588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesenusing namespace llvm; 1462588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen 1562588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesennamespace { 1662588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen 1762588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesentypedef SparseSet<unsigned> USet; 1862588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen 19a3bf915888ba81c4f695ebc38e5d6ce0881ef354Jakob Stoklund Olesen// Empty set tests. 2062588622d40f6c6f5508496db69e06593b615049Jakob Stoklund OlesenTEST(SparseSetTest, EmptySet) { 2162588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen USet Set; 2262588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen EXPECT_TRUE(Set.empty()); 2362588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen EXPECT_TRUE(Set.begin() == Set.end()); 2462588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen EXPECT_EQ(0u, Set.size()); 2562588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen 2662588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen Set.setUniverse(10); 2762588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen 2862588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen // Lookups on empty set. 2962588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen EXPECT_TRUE(Set.find(0) == Set.end()); 3062588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen EXPECT_TRUE(Set.find(9) == Set.end()); 3162588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen 3262588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen // Same thing on a const reference. 3362588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen const USet &CSet = Set; 3462588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen EXPECT_TRUE(CSet.empty()); 3562588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen EXPECT_TRUE(CSet.begin() == CSet.end()); 3662588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen EXPECT_EQ(0u, CSet.size()); 3762588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen EXPECT_TRUE(CSet.find(0) == CSet.end()); 3862588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen USet::const_iterator I = CSet.find(5); 3962588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen EXPECT_TRUE(I == CSet.end()); 4062588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen} 4162588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen 42a3bf915888ba81c4f695ebc38e5d6ce0881ef354Jakob Stoklund Olesen// Single entry set tests. 4362588622d40f6c6f5508496db69e06593b615049Jakob Stoklund OlesenTEST(SparseSetTest, SingleEntrySet) { 4462588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen USet Set; 4562588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen Set.setUniverse(10); 4662588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen std::pair<USet::iterator, bool> IP = Set.insert(5); 4762588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen EXPECT_TRUE(IP.second); 4862588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen EXPECT_TRUE(IP.first == Set.begin()); 4962588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen 5062588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen EXPECT_FALSE(Set.empty()); 5162588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen EXPECT_FALSE(Set.begin() == Set.end()); 5262588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen EXPECT_TRUE(Set.begin() + 1 == Set.end()); 5362588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen EXPECT_EQ(1u, Set.size()); 5462588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen 5562588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen EXPECT_TRUE(Set.find(0) == Set.end()); 5662588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen EXPECT_TRUE(Set.find(9) == Set.end()); 5762588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen 5862588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen EXPECT_FALSE(Set.count(0)); 5962588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen EXPECT_TRUE(Set.count(5)); 6062588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen 6162588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen // Redundant insert. 6262588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen IP = Set.insert(5); 6362588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen EXPECT_FALSE(IP.second); 6462588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen EXPECT_TRUE(IP.first == Set.begin()); 6562588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen 66a3bf915888ba81c4f695ebc38e5d6ce0881ef354Jakob Stoklund Olesen // Erase non-existent element. 6762588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen EXPECT_FALSE(Set.erase(1)); 6862588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen EXPECT_EQ(1u, Set.size()); 6962588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen EXPECT_EQ(5u, *Set.begin()); 7062588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen 7162588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen // Erase iterator. 7262588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen USet::iterator I = Set.find(5); 7362588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen EXPECT_TRUE(I == Set.begin()); 7462588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen I = Set.erase(I); 7562588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen EXPECT_TRUE(I == Set.end()); 7662588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen EXPECT_TRUE(Set.empty()); 7762588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen} 7862588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen 79a3bf915888ba81c4f695ebc38e5d6ce0881ef354Jakob Stoklund Olesen// Multiple entry set tests. 8062588622d40f6c6f5508496db69e06593b615049Jakob Stoklund OlesenTEST(SparseSetTest, MultipleEntrySet) { 8162588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen USet Set; 8262588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen Set.setUniverse(10); 8362588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen 8462588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen Set.insert(5); 8562588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen Set.insert(3); 8662588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen Set.insert(2); 8762588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen Set.insert(1); 8862588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen Set.insert(4); 8962588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen EXPECT_EQ(5u, Set.size()); 9062588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen 9162588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen // Without deletions, iteration order == insertion order. 9262588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen USet::const_iterator I = Set.begin(); 9362588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen EXPECT_EQ(5u, *I); 9462588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen ++I; 9562588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen EXPECT_EQ(3u, *I); 9662588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen ++I; 9762588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen EXPECT_EQ(2u, *I); 9862588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen ++I; 9962588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen EXPECT_EQ(1u, *I); 10062588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen ++I; 10162588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen EXPECT_EQ(4u, *I); 10262588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen ++I; 10362588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen EXPECT_TRUE(I == Set.end()); 10462588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen 10562588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen // Redundant insert. 10662588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen std::pair<USet::iterator, bool> IP = Set.insert(3); 10762588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen EXPECT_FALSE(IP.second); 10862588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen EXPECT_TRUE(IP.first == Set.begin() + 1); 10962588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen 11062588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen // Erase last element by key. 11162588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen EXPECT_TRUE(Set.erase(4)); 11262588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen EXPECT_EQ(4u, Set.size()); 11362588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen EXPECT_FALSE(Set.count(4)); 11462588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen EXPECT_FALSE(Set.erase(4)); 11562588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen EXPECT_EQ(4u, Set.size()); 11662588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen EXPECT_FALSE(Set.count(4)); 11762588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen 11862588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen // Erase first element by key. 11962588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen EXPECT_TRUE(Set.count(5)); 12062588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen EXPECT_TRUE(Set.find(5) == Set.begin()); 12162588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen EXPECT_TRUE(Set.erase(5)); 12262588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen EXPECT_EQ(3u, Set.size()); 12362588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen EXPECT_FALSE(Set.count(5)); 12462588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen EXPECT_FALSE(Set.erase(5)); 12562588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen EXPECT_EQ(3u, Set.size()); 12662588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen EXPECT_FALSE(Set.count(5)); 12762588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen 12862588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen Set.insert(6); 12962588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen Set.insert(7); 13062588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen EXPECT_EQ(5u, Set.size()); 13162588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen 13262588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen // Erase last element by iterator. 13362588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen I = Set.erase(Set.end() - 1); 13462588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen EXPECT_TRUE(I == Set.end()); 13562588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen EXPECT_EQ(4u, Set.size()); 13662588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen 13762588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen // Erase second element by iterator. 13862588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen I = Set.erase(Set.begin() + 1); 13962588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen EXPECT_TRUE(I == Set.begin() + 1); 14062588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen 14162588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen // Clear and resize the universe. 14262588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen Set.clear(); 14362588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen EXPECT_FALSE(Set.count(5)); 14462588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen Set.setUniverse(1000); 14562588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen 14662588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen // Add more than 256 elements. 14762588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen for (unsigned i = 100; i != 800; ++i) 14862588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen Set.insert(i); 14962588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen 15062588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen for (unsigned i = 0; i != 10; ++i) 15162588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen Set.erase(i); 15262588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen 15362588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen for (unsigned i = 100; i != 800; ++i) 15462588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen EXPECT_TRUE(Set.count(i)); 15562588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen 15662588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen EXPECT_FALSE(Set.count(99)); 15762588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen EXPECT_FALSE(Set.count(800)); 15862588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen EXPECT_EQ(700u, Set.size()); 15962588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen} 16062588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen 16162588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesenstruct Alt { 16262588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen unsigned Value; 16362588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen explicit Alt(unsigned x) : Value(x) {} 164c0ccb8bb17028fe0dda139c0972c0125d10e6053Andrew Trick unsigned getSparseSetIndex() const { return Value - 1000; } 16562588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen}; 16662588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen 16762588622d40f6c6f5508496db69e06593b615049Jakob Stoklund OlesenTEST(SparseSetTest, AltStructSet) { 16862588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen typedef SparseSet<Alt> ASet; 16962588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen ASet Set; 17062588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen Set.setUniverse(10); 17162588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen Set.insert(Alt(1005)); 17262588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen 17362588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen ASet::iterator I = Set.find(5); 17462588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen ASSERT_TRUE(I == Set.begin()); 17562588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen EXPECT_EQ(1005u, I->Value); 17662588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen 17762588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen Set.insert(Alt(1006)); 17862588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen Set.insert(Alt(1006)); 17962588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen I = Set.erase(Set.begin()); 18062588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen ASSERT_TRUE(I == Set.begin()); 18162588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen EXPECT_EQ(1006u, I->Value); 18262588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen 18362588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen EXPECT_FALSE(Set.erase(5)); 18462588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen EXPECT_TRUE(Set.erase(6)); 18562588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen} 18662588622d40f6c6f5508496db69e06593b615049Jakob Stoklund Olesen} // namespace 187