Index: include/llvm/ADT/ImmutableList.h =================================================================== --- include/llvm/ADT/ImmutableList.h +++ include/llvm/ADT/ImmutableList.h @@ -31,8 +31,8 @@ T Head; const ImmutableListImpl* Tail; - ImmutableListImpl(const T& head, const ImmutableListImpl* tail = nullptr) - : Head(head), Tail(tail) {} + ImmutableListImpl(T &&head, const ImmutableListImpl *tail = nullptr) + : Head(std::move(head)), Tail(tail) {} public: ImmutableListImpl(const ImmutableListImpl &) = delete; @@ -66,6 +66,9 @@ using value_type = T; using Factory = ImmutableListFactory; + static_assert(std::is_trivially_destructible::value, + "T must be trivially destructible!"); + private: const ImmutableListImpl* X; @@ -166,7 +169,7 @@ if (ownsAllocator()) delete &getAllocator(); } - LLVM_NODISCARD ImmutableList concat(const T &Head, ImmutableList Tail) { + LLVM_NODISCARD ImmutableList concat(T Head, ImmutableList Tail) { // Profile the new list to see if it already exists in our cache. FoldingSetNodeID ID; void* InsertPos; @@ -179,7 +182,7 @@ // The list does not exist in our cache. Create it. BumpPtrAllocator& A = getAllocator(); L = (ListTy*) A.Allocate(); - new (L) ListTy(Head, TailImpl); + new (L) ListTy(std::move(Head), TailImpl); // Insert the new list into the cache. Cache.InsertNode(L, InsertPos); @@ -188,16 +191,22 @@ return L; } - LLVM_NODISCARD ImmutableList add(const T& D, ImmutableList L) { - return concat(D, L); + LLVM_NODISCARD ImmutableList add(T Data, ImmutableList L) { + return concat(std::move(Data), L); + } + + template + LLVM_NODISCARD ImmutableList emplace(ImmutableList Tail, + CtorArgs &&...Args) { + return concat(T(std::forward(Args)...), Tail); } ImmutableList getEmptyList() const { return ImmutableList(nullptr); } - ImmutableList create(const T& X) { - return concat(X, getEmptyList()); + ImmutableList create(T Data) { + return concat(std::move(Data), getEmptyList()); } }; Index: unittests/ADT/ImmutableListTest.cpp =================================================================== --- unittests/ADT/ImmutableListTest.cpp +++ unittests/ADT/ImmutableListTest.cpp @@ -150,6 +150,49 @@ EXPECT_TRUE(L5.isEqual(L5)); } +template +struct ExplicitCtorWrapper : public Wrapper { + explicit ExplicitCtorWrapper(Fundamental F) : Wrapper(F) {} + ExplicitCtorWrapper(const ExplicitCtorWrapper &) = delete; + ExplicitCtorWrapper(ExplicitCtorWrapper &&) = default; + ExplicitCtorWrapper &operator=(const ExplicitCtorWrapper &) = delete; + ExplicitCtorWrapper &operator=(ExplicitCtorWrapper &&) = default; +}; + +TEST_F(ImmutableListTest, EmplaceIntListTest) { + ImmutableList>::Factory f; + + ImmutableList> L = f.getEmptyList(); + ImmutableList> L2 = f.emplace(L, 3); + + ImmutableList> L3 = + f.add(ExplicitCtorWrapper(2), L2); + + ImmutableList> L4 = + f.emplace(L3, ExplicitCtorWrapper(1)); + + ImmutableList> L5 = + f.add(ExplicitCtorWrapper(1), L3); + + EXPECT_FALSE(L2.isEmpty()); + EXPECT_TRUE(L2.getTail().isEmpty()); + EXPECT_EQ(3, L2.getHead()); + EXPECT_TRUE(L.isEqual(L2.getTail())); + EXPECT_TRUE(L2.getTail().isEqual(L)); + + EXPECT_FALSE(L3.isEmpty()); + EXPECT_FALSE(L2 == L3); + EXPECT_EQ(2, L3.getHead()); + EXPECT_TRUE(L2 == L3.getTail()); + + EXPECT_FALSE(L4.isEmpty()); + EXPECT_EQ(1, L4.getHead()); + EXPECT_TRUE(L3 == L4.getTail()); + + EXPECT_TRUE(L4 == L5); + EXPECT_TRUE(L3 == L5.getTail()); +} + TEST_F(ImmutableListTest, CharListOrderingTest) { ImmutableList>::Factory f; ImmutableList> L = f.getEmptyList();