From dbbe82c6fda43131a101d34e8e20f3b0e00aa883 Mon Sep 17 00:00:00 2001 From: OCHyams Date: Thu, 27 Oct 2022 08:52:47 +0100 Subject: [PATCH] [IntervalMap] Add move and copy ctors and assignment operators And update the unittest. Reviewed By: dblaikie Differential Revision: https://reviews.llvm.org/D136242 --- llvm/include/llvm/ADT/IntervalMap.h | 73 ++++++++++++++++++++------- llvm/unittests/ADT/IntervalMapTest.cpp | 90 ++++++++++++++++++++++++---------- 2 files changed, 120 insertions(+), 43 deletions(-) diff --git a/llvm/include/llvm/ADT/IntervalMap.h b/llvm/include/llvm/ADT/IntervalMap.h index 57f02df2..c68d816 100644 --- a/llvm/include/llvm/ADT/IntervalMap.h +++ b/llvm/include/llvm/ADT/IntervalMap.h @@ -975,13 +975,13 @@ private: // 0: Leaves in root. // 1: Root points to leaf. // 2: root->branch->leaf ... - unsigned height; + unsigned height = 0; // Number of entries in the root node. - unsigned rootSize; + unsigned rootSize = 0; // Allocator used for creating external nodes. - Allocator &allocator; + Allocator *allocator = nullptr; const RootLeaf &rootLeaf() const { assert(!branched() && "Cannot acces leaf data in branched root"); @@ -1007,12 +1007,12 @@ private: KeyT &rootBranchStart() { return rootBranchData().start; } template NodeT *newNode() { - return new(allocator.template Allocate()) NodeT(); + return new (allocator->template Allocate()) NodeT(); } template void deleteNode(NodeT *P) { P->~NodeT(); - allocator.Deallocate(P); + allocator->Deallocate(P); } IdxPair branchRoot(unsigned Position); @@ -1038,20 +1038,59 @@ private: void deleteNode(IntervalMapImpl::NodeRef Node, unsigned Level); public: - explicit IntervalMap(Allocator &a) : height(0), rootSize(0), allocator(a) { - new(&rootLeaf()) RootLeaf(); + explicit IntervalMap(Allocator &a) : allocator(&a) { + new (&rootLeaf()) RootLeaf(); + } + + ///@{ + /// NOTE: The moved-from or copied-from object's allocator needs to have a + /// lifetime equal to or exceeding the moved-to or copied-to object to avoid + /// undefined behaviour. + IntervalMap(IntervalMap const &RHS) : IntervalMap(*RHS.allocator) { + // Future-proofing assertion: this function assumes the IntervalMap + // constructor doesn't add any nodes. + assert(empty() && "Expected emptry tree"); + *this = RHS; + } + IntervalMap &operator=(IntervalMap const &RHS) { + clear(); + allocator = RHS.allocator; + for (auto It = RHS.begin(), End = RHS.end(); It != End; ++It) + insert(It.start(), It.stop(), It.value()); + return *this; + } + + IntervalMap(IntervalMap &&RHS) : IntervalMap(*RHS.allocator) { + // Future-proofing assertion: this function assumes the IntervalMap + // constructor doesn't add any nodes. + assert(empty() && "Expected emptry tree"); + *this = std::move(RHS); } + IntervalMap &operator=(IntervalMap &&RHS) { + // Calling clear deallocates memory and switches to rootLeaf. + clear(); + // Destroy the new rootLeaf. + rootLeaf().~RootLeaf(); - // The default copy/move constructors and assignment operators would perform - // a shallow copy, leading to an incorrect internal state. To prevent - // accidental use, explicitly delete these operators. - // If necessary, implement them to perform a deep copy. - IntervalMap(const IntervalMap &Other) = delete; - IntervalMap(IntervalMap &&Other) = delete; - // Note: these are already implicitly deleted, because RootLeaf (union - // member) has a non-trivial assignment operator (because of std::pair). - IntervalMap &operator=(const IntervalMap &Other) = delete; - IntervalMap &operator=(IntervalMap &&Other) = delete; + height = RHS.height; + rootSize = RHS.rootSize; + allocator = RHS.allocator; + + // rootLeaf and rootBranch are both uninitialized. Move RHS data into + // appropriate field. + if (RHS.branched()) { + rootBranch() = std::move(RHS.rootBranch()); + // Prevent RHS deallocating memory LHS now owns by replacing RHS + // rootBranch with a new rootLeaf. + RHS.rootBranch().~RootBranch(); + RHS.height = 0; + new (&RHS.rootLeaf()) RootLeaf(); + } else { + rootLeaf() = std::move(RHS.rootLeaf()); + } + return *this; + } + ///@} ~IntervalMap() { clear(); diff --git a/llvm/unittests/ADT/IntervalMapTest.cpp b/llvm/unittests/ADT/IntervalMapTest.cpp index 07cda05..99a93ab 100644 --- a/llvm/unittests/ADT/IntervalMapTest.cpp +++ b/llvm/unittests/ADT/IntervalMapTest.cpp @@ -18,15 +18,6 @@ typedef IntervalMap UUMap; typedef IntervalMap> UUHalfOpenMap; -static_assert(!std::is_copy_constructible::value, - "IntervalMap copy constructor should be deleted"); -static_assert(!std::is_move_constructible::value, - "IntervalMap move constructor should be deleted"); -static_assert(!std::is_copy_assignable::value, - "IntervalMap copy assignment should be deleted"); -static_assert(!std::is_move_assignable::value, - "IntervalMap move assignment should be deleted"); - // Empty map tests TEST(IntervalMapTest, EmptyMap) { UUMap::Allocator allocator; @@ -630,26 +621,73 @@ TEST(IntervalMapTest, RandomCoalescing) { } +static void setupOverlaps(UUMap &M) { + M.insert(10, 20, 0); + M.insert(30, 40, 0); + M.insert(50, 60, 0); + // Add extra nodes to force allocations. + for (int i = 70; i < 100; i += 2) + M.insert(i, i + 1, i); +} + +static void checkOverlaps(UUMap &M) { + EXPECT_FALSE(M.overlaps(0, 9)); + EXPECT_TRUE(M.overlaps(0, 10)); + EXPECT_TRUE(M.overlaps(0, 15)); + EXPECT_TRUE(M.overlaps(0, 25)); + EXPECT_TRUE(M.overlaps(0, 45)); + EXPECT_TRUE(M.overlaps(10, 45)); + EXPECT_TRUE(M.overlaps(30, 45)); + EXPECT_TRUE(M.overlaps(35, 36)); + EXPECT_TRUE(M.overlaps(40, 45)); + EXPECT_FALSE(M.overlaps(45, 45)); + EXPECT_TRUE(M.overlaps(60, 60)); + EXPECT_TRUE(M.overlaps(60, 66)); + EXPECT_FALSE(M.overlaps(66, 66)); +} + +TEST(IntervalMapTest, Copy) { + // Test that copy assignment and initialization works. + UUHalfOpenMap::Allocator Allocator; + UUMap Src(Allocator); + setupOverlaps(Src); + + UUMap CopyAssignmentDst(Allocator); + CopyAssignmentDst = Src; + + UUMap CopyInitDst(Src); + + checkOverlaps(Src); + Src.clear(); + + checkOverlaps(CopyAssignmentDst); + checkOverlaps(CopyInitDst); +} + +TEST(IntervalMapTest, Move) { + // Test that move assignment and initialization works. + UUHalfOpenMap::Allocator Allocator; + // Double check that MoveAssignmentDst owns all its data by moving from an + // object that is destroyed before we call checkOverlaps. + UUMap MoveAssignmentDst(Allocator); + { + UUMap Src(Allocator); + setupOverlaps(Src); + MoveAssignmentDst = std::move(Src); + } + checkOverlaps(MoveAssignmentDst); + + UUMap MoveInitSrc(Allocator); + setupOverlaps(MoveInitSrc); + UUMap MoveInitDst(std::move(MoveInitSrc)); + checkOverlaps(MoveInitDst); +} + TEST(IntervalMapTest, Overlaps) { UUMap::Allocator allocator; UUMap map(allocator); - map.insert(10, 20, 0); - map.insert(30, 40, 0); - map.insert(50, 60, 0); - - EXPECT_FALSE(map.overlaps(0, 9)); - EXPECT_TRUE(map.overlaps(0, 10)); - EXPECT_TRUE(map.overlaps(0, 15)); - EXPECT_TRUE(map.overlaps(0, 25)); - EXPECT_TRUE(map.overlaps(0, 45)); - EXPECT_TRUE(map.overlaps(10, 45)); - EXPECT_TRUE(map.overlaps(30, 45)); - EXPECT_TRUE(map.overlaps(35, 36)); - EXPECT_TRUE(map.overlaps(40, 45)); - EXPECT_FALSE(map.overlaps(45, 45)); - EXPECT_TRUE(map.overlaps(60, 60)); - EXPECT_TRUE(map.overlaps(60, 66)); - EXPECT_FALSE(map.overlaps(66, 66)); + setupOverlaps(map); + checkOverlaps(map); } TEST(IntervalMapTest, OverlapsHalfOpen) { -- 2.7.4