From b787d41959163f6104af7b34a5ce719210dfb72f Mon Sep 17 00:00:00 2001 From: Stepan Dyatkovskiy Date: Tue, 26 Jun 2012 11:57:43 +0000 Subject: IntegersSubsetMapping: implemented "diff" operation. Operation allows at the same time perform up to three operations: - LHS exclude RHS - LHS intersect RHS (LHS successors will keeped) - RHS exclude LHS The complexity is N+M, where N is size of LHS M is size of RHS. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@159201 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Support/IntegersSubsetMapping.h | 261 ++++++++++++++++++++++++++- unittests/Support/IntegersSubsetTest.cpp | 143 +++++++++++++++ 2 files changed, 401 insertions(+), 3 deletions(-) diff --git a/include/llvm/Support/IntegersSubsetMapping.h b/include/llvm/Support/IntegersSubsetMapping.h index 4a771331ba..87d0755c51 100644 --- a/include/llvm/Support/IntegersSubsetMapping.h +++ b/include/llvm/Support/IntegersSubsetMapping.h @@ -31,6 +31,10 @@ template class IntegersSubsetMapping { + // FIXME: To much similar iterators typedefs, similar names. + // - Rename RangeIterator to the cluster iterator. + // - Remove unused "add" methods. + // - Class contents needs cleaning. public: typedef IntRange RangeTy; @@ -47,15 +51,17 @@ public: typedef std::pair Cluster; + typedef std::list RangesCollection; + typedef typename RangesCollection::iterator RangesCollectionIt; + typedef typename RangesCollection::const_iterator RangesCollectionConstIt; + typedef IntegersSubsetMapping self; + protected: typedef std::list CaseItems; typedef typename CaseItems::iterator CaseItemIt; typedef typename CaseItems::const_iterator CaseItemConstIt; - typedef std::list RangesCollection; - typedef typename RangesCollection::iterator RangesCollectionIt; - // TODO: Change unclean CRS prefixes to SubsetMap for example. typedef std::map CRSMap; typedef typename CRSMap::iterator CRSMapIt; @@ -96,6 +102,149 @@ protected: Sorted = true; } } + + enum DiffProcessState { + L_OPENED, + INTERSECT_OPENED, + R_OPENED, + ALL_IS_CLOSED + }; + + class DiffStateMachine { + + DiffProcessState State; + IntTy OpenPt; + SuccessorClass *CurrentLSuccessor; + SuccessorClass *CurrentRSuccessor; + + self *LeftMapping; + self *IntersectionMapping; + self *RightMapping; + + public: + + typedef + IntegersSubsetMapping MappingTy; + + DiffStateMachine(MappingTy *L, + MappingTy *Intersection, + MappingTy *R) : + State(ALL_IS_CLOSED), + LeftMapping(L), + IntersectionMapping(Intersection), + RightMapping(R) + {} + + void onLOpen(const IntTy &Pt, SuccessorClass *S) { + switch (State) { + case R_OPENED: + if (Pt > OpenPt/*Don't add empty ranges.*/ && RightMapping) + RightMapping->add(OpenPt, Pt-1, CurrentRSuccessor); + State = INTERSECT_OPENED; + break; + case ALL_IS_CLOSED: + State = L_OPENED; + break; + default: + assert(0 && "Got unexpected point."); + break; + } + CurrentLSuccessor = S; + OpenPt = Pt; + } + + void onLClose(const IntTy &Pt) { + switch (State) { + case L_OPENED: + assert(Pt >= OpenPt && + "Subset is not sorted or contains overlapped ranges"); + if (LeftMapping) + LeftMapping->add(OpenPt, Pt, CurrentLSuccessor); + State = ALL_IS_CLOSED; + break; + case INTERSECT_OPENED: + if (IntersectionMapping) + IntersectionMapping->add(OpenPt, Pt, CurrentLSuccessor); + OpenPt = Pt + 1; + State = R_OPENED; + break; + default: + assert(0 && "Got unexpected point."); + break; + } + } + + void onROpen(const IntTy &Pt, SuccessorClass *S) { + switch (State) { + case L_OPENED: + if (Pt > OpenPt && LeftMapping) + LeftMapping->add(OpenPt, Pt-1, CurrentLSuccessor); + State = INTERSECT_OPENED; + break; + case ALL_IS_CLOSED: + State = R_OPENED; + break; + default: + assert(0 && "Got unexpected point."); + break; + } + CurrentRSuccessor = S; + OpenPt = Pt; + } + + void onRClose(const IntTy &Pt) { + switch (State) { + case R_OPENED: + assert(Pt >= OpenPt && + "Subset is not sorted or contains overlapped ranges"); + if (RightMapping) + RightMapping->add(OpenPt, Pt, CurrentRSuccessor); + State = ALL_IS_CLOSED; + break; + case INTERSECT_OPENED: + if (IntersectionMapping) + IntersectionMapping->add(OpenPt, Pt, CurrentLSuccessor); + OpenPt = Pt + 1; + State = L_OPENED; + break; + default: + assert(0 && "Got unexpected point."); + break; + } + } + + void onRLOpen(const IntTy &Pt, + SuccessorClass *LS, + SuccessorClass *RS) { + switch (State) { + case ALL_IS_CLOSED: + State = INTERSECT_OPENED; + break; + default: + assert(0 && "Got unexpected point."); + break; + } + CurrentLSuccessor = LS; + CurrentRSuccessor = RS; + OpenPt = Pt; + } + + void onRLClose(const IntTy &Pt) { + switch (State) { + case INTERSECT_OPENED: + if (IntersectionMapping) + IntersectionMapping->add(OpenPt, Pt, CurrentLSuccessor); + State = ALL_IS_CLOSED; + break; + default: + assert(0 && "Got unexpected point."); + break; + } + } + + bool isLOpened() { return State == L_OPENED; } + bool isROpened() { return State == R_OPENED; } + }; public: @@ -187,9 +336,110 @@ public: } } + void add(self& RHS) { + Items.insert(Items.end(), RHS.Items.begin(), RHS.Items.end()); + } + + void add(const RangesCollection& RHS, SuccessorClass *S = 0) { + for (RangesCollectionConstIt i = RHS.begin(), e = RHS.end(); i != e; ++i) + add(*i, S); + } + /// Removes items from set. void removeItem(RangeIterator i) { Items.erase(i); } + /// Calculates the difference between this mapping and RHS. + /// THIS without RHS is placed into LExclude, + /// RHS without THIS is placed into RExclude, + /// THIS intersect RHS is placed into Intersection. + void diff(self *LExclude, self *Intersection, self *RExclude, + const self& RHS) { + + DiffStateMachine Machine(LExclude, Intersection, RExclude); + + CaseItemConstIt L = Items.begin(), R = RHS.Items.begin(); + while (L != Items.end() && R != RHS.Items.end()) { + const Cluster &LCluster = *L; + const RangeEx &LRange = LCluster.first; + const Cluster &RCluster = *R; + const RangeEx &RRange = RCluster.first; + + if (LRange.getHigh() < RRange.getLow()) { + Machine.onLOpen(LRange.getLow(), LCluster.second); + Machine.onLClose(LRange.getHigh()); + ++L; + continue; + } + + if (LRange.getLow() > RRange.getHigh()) { + Machine.onROpen(RRange.getLow(), RCluster.second); + Machine.onRClose(RRange.getHigh()); + ++R; + continue; + } + + if (LRange.getLow() < RRange.getLow()) { + // May be opened in previous iteration. + if (!Machine.isLOpened()) + Machine.onLOpen(LRange.getLow(), LCluster.second); + Machine.onROpen(RRange.getLow(), RCluster.second); + } + else if (RRange.getLow() < LRange.getLow()) { + if (!Machine.isROpened()) + Machine.onROpen(RRange.getLow(), RCluster.second); + Machine.onLOpen(LRange.getLow(), LCluster.second); + } + else + Machine.onRLOpen(LRange.getLow(), LCluster.second, RCluster.second); + + if (LRange.getHigh() < RRange.getHigh()) { + Machine.onLClose(LRange.getHigh()); + ++L; + while(L != Items.end() && L->first.getHigh() < RRange.getHigh()) { + Machine.onLOpen(L->first.getLow(), L->second); + Machine.onLClose(L->first.getHigh()); + ++L; + } + } + else if (RRange.getHigh() < LRange.getHigh()) { + Machine.onRClose(RRange.getHigh()); + ++R; + while(R != RHS.Items.end() && R->first.getHigh() < LRange.getHigh()) { + Machine.onROpen(R->first.getLow(), R->second); + Machine.onRClose(R->first.getHigh()); + ++R; + } + } + else { + Machine.onRLClose(LRange.getHigh()); + ++L; + ++R; + } + } + + if (L != Items.end()) { + if (Machine.isLOpened()) { + Machine.onLClose(L->first.getHigh()); + ++L; + } + if (LExclude) + while (L != Items.end()) { + LExclude->add(L->first, L->second); + ++L; + } + } else if (R != RHS.Items.end()) { + if (Machine.isROpened()) { + Machine.onRClose(R->first.getHigh()); + ++R; + } + if (RExclude) + while (R != RHS.Items.end()) { + RExclude->add(R->first, R->second); + ++R; + } + } + } + /// Builds the finalized case objects. void getCases(Cases& TheCases) { CRSMap TheCRSMap; @@ -218,6 +468,11 @@ public: // 2. After first item will added Sorted flag will cleared. } + // Returns number of clusters + unsigned size() const { + return Items.size(); + } + RangeIterator begin() { return Items.begin(); } RangeIterator end() { return Items.end(); } }; diff --git a/unittests/Support/IntegersSubsetTest.cpp b/unittests/Support/IntegersSubsetTest.cpp index 836f29a269..2d0e357894 100644 --- a/unittests/Support/IntegersSubsetTest.cpp +++ b/unittests/Support/IntegersSubsetTest.cpp @@ -21,6 +21,7 @@ namespace { class Int : public APInt { public: + Int() {} Int(uint64_t V) : APInt(64, V) {} Int(const APInt& Src) : APInt(Src) {} bool operator < (const APInt& RHS) const { return ult(RHS); } @@ -178,4 +179,146 @@ namespace { EXPECT_EQ(CaseIt->second.getItem(0), Range(Int(i * 10), Int(i * 10 + 9))); } } + + typedef unsigned unsigned_pair[2]; + typedef unsigned_pair unsigned_ranges[]; + + void TestDiff( + const unsigned_ranges LHS, + unsigned LSize, + const unsigned_ranges RHS, + unsigned RSize, + const unsigned_ranges ExcludeRes, + unsigned ExcludeResSize, + const unsigned_ranges IntersectRes, + unsigned IntersectResSize + ) { + Mapping::RangesCollection Ranges; + + Mapping LHSMapping; + for (unsigned i = 0; i < LSize; ++i) + Ranges.push_back(Range(Int(LHS[i][0]), Int(LHS[i][1]))); + LHSMapping.add(Ranges); + + Ranges.clear(); + + Mapping RHSMapping; + for (unsigned i = 0; i < RSize; ++i) + Ranges.push_back(Range(Int(RHS[i][0]), Int(RHS[i][1]))); + RHSMapping.add(Ranges); + + Mapping LExclude, Intersection; + + LHSMapping.diff(&LExclude, &Intersection, 0, RHSMapping); + + if (ExcludeResSize) { + EXPECT_EQ(LExclude.size(), ExcludeResSize); + + unsigned i = 0; + for (Mapping::RangeIterator rei = LExclude.begin(), + e = LExclude.end(); rei != e; ++rei, ++i) + EXPECT_EQ(rei->first, Range(ExcludeRes[i][0], ExcludeRes[i][1])); + } else + EXPECT_TRUE(LExclude.empty()); + + if (IntersectResSize) { + EXPECT_EQ(Intersection.size(), IntersectResSize); + + unsigned i = 0; + for (Mapping::RangeIterator ii = Intersection.begin(), + e = Intersection.end(); ii != e; ++ii, ++i) + EXPECT_EQ(ii->first, Range(IntersectRes[i][0], IntersectRes[i][1])); + } else + EXPECT_TRUE(Intersection.empty()); + + LExclude.clear(); + Intersection.clear(); + RHSMapping.diff(0, &Intersection, &LExclude, LHSMapping); + + // Check LExclude again. + if (ExcludeResSize) { + EXPECT_EQ(LExclude.size(), ExcludeResSize); + + unsigned i = 0; + for (Mapping::RangeIterator rei = LExclude.begin(), + e = LExclude.end(); rei != e; ++rei, ++i) + EXPECT_EQ(rei->first, Range(ExcludeRes[i][0], ExcludeRes[i][1])); + } else + EXPECT_TRUE(LExclude.empty()); + } + + TEST(IntegersSubsetTest, DiffTest) { + { + unsigned_ranges LHS = { { 0, 4 }, { 7, 10 }, { 13, 17 } }; + unsigned_ranges RHS = { { 3, 14 } }; + unsigned_ranges ExcludeRes = { { 0, 2 }, { 15, 17 } }; + unsigned_ranges IntersectRes = { { 3, 4 }, { 7, 10 }, { 13, 14 } }; + + TestDiff(LHS, 3, RHS, 1, ExcludeRes, 2, IntersectRes, 3); + } + + { + unsigned_ranges LHS = { { 0, 4 }, { 7, 10 }, { 13, 17 } }; + unsigned_ranges RHS = { { 0, 4 }, { 13, 17 } }; + unsigned_ranges ExcludeRes = { { 7, 10 } }; + unsigned_ranges IntersectRes = { { 0, 4 }, { 13, 17 } }; + + TestDiff(LHS, 3, RHS, 2, ExcludeRes, 1, IntersectRes, 2); + } + + { + unsigned_ranges LHS = { { 0, 17 } }; + unsigned_ranges RHS = { { 1, 5 }, { 10, 12 }, { 15, 16 } }; + unsigned_ranges ExcludeRes = + { { 0, 0 }, { 6, 9 }, { 13, 14 }, { 17, 17 } }; + unsigned_ranges IntersectRes = { { 1, 5 }, { 10, 12 }, { 15, 16 } }; + + TestDiff(LHS, 1, RHS, 3, ExcludeRes, 4, IntersectRes, 3); + } + + { + unsigned_ranges LHS = { { 2, 4 } }; + unsigned_ranges RHS = { { 0, 5 } }; + unsigned_ranges ExcludeRes = { {-1UL, -1UL} }; + unsigned_ranges IntersectRes = { { 2, 4 } }; + + TestDiff(LHS, 1, RHS, 1, ExcludeRes, 0, IntersectRes, 1); + } + + { + unsigned_ranges LHS = { { 2, 4 } }; + unsigned_ranges RHS = { { 7, 8 } }; + unsigned_ranges ExcludeRes = { { 2, 4 } }; + unsigned_ranges IntersectRes = { {-1UL, -1UL} }; + + TestDiff(LHS, 1, RHS, 1, ExcludeRes, 1, IntersectRes, 0); + } + + { + unsigned_ranges LHS = { { 3, 7 } }; + unsigned_ranges RHS = { { 1, 4 } }; + unsigned_ranges ExcludeRes = { { 5, 7 } }; + unsigned_ranges IntersectRes = { { 3, 4 } }; + + TestDiff(LHS, 1, RHS, 1, ExcludeRes, 1, IntersectRes, 1); + } + + { + unsigned_ranges LHS = { { 0, 7 } }; + unsigned_ranges RHS = { { 0, 5 }, { 6, 9 } }; + unsigned_ranges ExcludeRes = { {-1UL, -1UL} }; + unsigned_ranges IntersectRes = { { 0, 5 }, {6, 7} }; + + TestDiff(LHS, 1, RHS, 2, ExcludeRes, 0, IntersectRes, 2); + } + + { + unsigned_ranges LHS = { { 17, 17 } }; + unsigned_ranges RHS = { { 4, 4 } }; + unsigned_ranges ExcludeRes = { {17, 17} }; + unsigned_ranges IntersectRes = { { -1UL, -1UL } }; + + TestDiff(LHS, 1, RHS, 1, ExcludeRes, 1, IntersectRes, 0); + } + } } -- cgit v1.2.3