From 0f7a7bcd4820eee293f9300769e1ef4c1cbc1c7c Mon Sep 17 00:00:00 2001 From: Stepan Dyatkovskiy Date: Tue, 26 Jun 2012 11:41:47 +0000 Subject: IntegersSubsetMapping: removed exclude operation, it will replaced with more universal "diff" operation in next commit. Changes was separated onto two commits for better readability. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@159200 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Support/IntegersSubsetMapping.h | 52 -------- unittests/Support/IntegersSubsetTest.cpp | 174 --------------------------- 2 files changed, 226 deletions(-) diff --git a/include/llvm/Support/IntegersSubsetMapping.h b/include/llvm/Support/IntegersSubsetMapping.h index c79b3c1684..4a771331ba 100644 --- a/include/llvm/Support/IntegersSubsetMapping.h +++ b/include/llvm/Support/IntegersSubsetMapping.h @@ -66,12 +66,6 @@ protected: } }; - struct ClusterLefterThan { - bool operator()(const Cluster &C, const RangeTy &R) { - return C.first.getHigh() < R.getLow(); - } - }; - CaseItems Items; bool Sorted; @@ -102,40 +96,6 @@ protected: Sorted = true; } } - - void exclude(CaseItemIt &beginIt, RangeTy &R) { - - std::list ToBeErased; - - CaseItemIt endIt = Items.end(); - CaseItemIt It = - std::lower_bound(beginIt, Items.end(), R, ClusterLefterThan()); - - if (It == endIt) - return; - - if (It->first.getLow() < R.getLow()) - Items.insert(It, std::make_pair( - RangeTy(It->first.getLow(), R.getLow()-1), - It->second)); - - do - ToBeErased.push_back(It++); - while (It != endIt && It->first.getLow() <= R.getHigh()); - - beginIt = It; - - CaseItemIt &LastRemoved = *(--ToBeErased.end()); - if (LastRemoved->first.getHigh() > R.getHigh()) - beginIt = Items.insert(LastRemoved, std::make_pair( - RangeTy(R.getHigh() + 1, LastRemoved->first.getHigh()), - LastRemoved->second - )); - - for (typename std::list::iterator i = ToBeErased.begin(), - e = ToBeErased.end(); i != e; ++i) - Items.erase(*i); - } public: @@ -230,18 +190,6 @@ public: /// Removes items from set. void removeItem(RangeIterator i) { Items.erase(i); } - // Excludes RHS subset from current mapping. RHS should consists of non - // overlapped ranges only and sorted from left to the right. - // method will have unpredictional behaviour in another case. - void exclude(IntegersSubsetTy &RHS) { - CaseItemIt startIt = begin(); - for (unsigned i = 0, e = RHS.getNumItems(); - i != e && startIt != end(); ++i) { - RangeTy R = RHS.getItem(i); - exclude(startIt, R); - } - } - /// Builds the finalized case objects. void getCases(Cases& TheCases) { CRSMap TheCRSMap; diff --git a/unittests/Support/IntegersSubsetTest.cpp b/unittests/Support/IntegersSubsetTest.cpp index 471df5d0cb..836f29a269 100644 --- a/unittests/Support/IntegersSubsetTest.cpp +++ b/unittests/Support/IntegersSubsetTest.cpp @@ -178,178 +178,4 @@ namespace { EXPECT_EQ(CaseIt->second.getItem(0), Range(Int(i * 10), Int(i * 10 + 9))); } } - - TEST(IntegersSubsetTest, ExcludeTest) { - std::vector Ranges; - Ranges.reserve(3); - - Mapping TheMapping; - - // Test case - // { {0, 4}, {7, 10} {13, 17} } - // sub - // { {3, 14} } - // = - // { {0, 2}, {15, 17} } - - Ranges.push_back(Range(Int(0), Int(4))); - Ranges.push_back(Range(Int(7), Int(10))); - Ranges.push_back(Range(Int(13), Int(17))); - - Subset TheSubset(Ranges); - - TheMapping.add(TheSubset); - - Ranges.clear(); - Ranges.push_back(Range(Int(3), Int(14))); - TheSubset = Subset(Ranges); - - TheMapping.exclude(TheSubset); - - TheSubset = TheMapping.getCase(); - - EXPECT_EQ(TheSubset.getNumItems(), 2ULL); - EXPECT_EQ(TheSubset.getItem(0), Range(Int(0), Int(2))); - EXPECT_EQ(TheSubset.getItem(1), Range(Int(15), Int(17))); - - // Test case - // { {0, 4}, {7, 10} {13, 17} } - // sub - // { {0, 4}, {13, 17} } - // = - // { {7, 10 } - - Ranges.clear(); - Ranges.push_back(Range(Int(0), Int(4))); - Ranges.push_back(Range(Int(7), Int(10))); - Ranges.push_back(Range(Int(13), Int(17))); - - TheSubset = Subset(Ranges); - - TheMapping.clear(); - TheMapping.add(TheSubset); - - Ranges.clear(); - Ranges.push_back(Range(Int(0), Int(4))); - Ranges.push_back(Range(Int(13), Int(17))); - - TheSubset = Subset(Ranges); - - TheMapping.exclude(TheSubset); - - TheSubset = TheMapping.getCase(); - - EXPECT_EQ(TheSubset.getNumItems(), 1ULL); - EXPECT_EQ(TheSubset.getItem(0), Range(Int(7), Int(10))); - - // Test case - // { {0, 17} } - // sub - // { {1, 5}, {10, 12}, {15, 16} } - // = - // { {0}, {6, 9}, {13, 14}, {17} } - - Ranges.clear(); - Ranges.push_back(Range(Int(0), Int(17))); - - TheSubset = Subset(Ranges); - - TheMapping.clear(); - TheMapping.add(TheSubset); - - Ranges.clear(); - Ranges.push_back(Range(Int(1), Int(5))); - Ranges.push_back(Range(Int(10), Int(12))); - Ranges.push_back(Range(Int(15), Int(16))); - - TheSubset = Subset(Ranges); - - TheMapping.exclude(TheSubset); - - TheSubset = TheMapping.getCase(); - - EXPECT_EQ(TheSubset.getNumItems(), 4ULL); - EXPECT_EQ(TheSubset.getItem(0), Range(Int(0))); - EXPECT_EQ(TheSubset.getItem(1), Range(Int(6), Int(9))); - EXPECT_EQ(TheSubset.getItem(2), Range(Int(13), Int(14))); - EXPECT_EQ(TheSubset.getItem(3), Range(Int(17))); - - // Test case - // { {2, 4} } - // sub - // { {0, 5} } - // = - // { empty } - - Ranges.clear(); - Ranges.push_back(Range(Int(2), Int(4))); - - TheSubset = Subset(Ranges); - - TheMapping.clear(); - TheMapping.add(TheSubset); - - Ranges.clear(); - Ranges.push_back(Range(Int(0), Int(5))); - - TheSubset = Subset(Ranges); - - TheMapping.exclude(TheSubset); - - EXPECT_TRUE(TheMapping.empty()); - - // Test case - // { {2, 4} } - // sub - // { {7, 8} } - // = - // { {2, 4} } - - Ranges.clear(); - Ranges.push_back(Range(Int(2), Int(4))); - - TheSubset = Subset(Ranges); - - TheMapping.clear(); - TheMapping.add(TheSubset); - - Ranges.clear(); - Ranges.push_back(Range(Int(7), Int(8))); - - TheSubset = Subset(Ranges); - - TheMapping.exclude(TheSubset); - - TheSubset = TheMapping.getCase(); - - EXPECT_EQ(TheSubset.getNumItems(), 1ULL); - EXPECT_EQ(TheSubset.getItem(0), Range(Int(2), Int(4))); - - // Test case - // { {3, 7} } - // sub - // { {1, 4} } - // = - // { {5, 7} } - - Ranges.clear(); - Ranges.push_back(Range(Int(3), Int(7))); - - TheSubset = Subset(Ranges); - - TheMapping.clear(); - TheMapping.add(TheSubset); - - Ranges.clear(); - Ranges.push_back(Range(Int(1), Int(4))); - - TheSubset = Subset(Ranges); - - TheMapping.exclude(TheSubset); - - TheSubset = TheMapping.getCase(); - - EXPECT_EQ(TheSubset.getNumItems(), 1ULL); - EXPECT_EQ(TheSubset.getItem(0), Range(Int(5), Int(7))); - } } -- cgit v1.2.3