summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--absl/container/inlined_vector.h13
-rw-r--r--absl/container/inlined_vector_test.cc239
-rw-r--r--absl/container/internal/inlined_vector.h106
3 files changed, 254 insertions, 104 deletions
diff --git a/absl/container/inlined_vector.h b/absl/container/inlined_vector.h
index 10b1896b..15616001 100644
--- a/absl/container/inlined_vector.h
+++ b/absl/container/inlined_vector.h
@@ -97,14 +97,11 @@ class InlinedVector {
using DisableIfAtLeastForwardIterator = absl::enable_if_t<
!inlined_vector_internal::IsAtLeastForwardIterator<Iterator>::value, int>;
- struct MemcpyPolicy {};
- struct ElementwiseAssignPolicy {};
- struct ElementwiseConstructPolicy {};
-
- using MoveAssignmentPolicy = absl::conditional_t<
- IsMemcpyOk<A>::value, MemcpyPolicy,
- absl::conditional_t<IsMoveAssignOk<A>::value, ElementwiseAssignPolicy,
- ElementwiseConstructPolicy>>;
+ using MemcpyPolicy = typename Storage::MemcpyPolicy;
+ using ElementwiseAssignPolicy = typename Storage::ElementwiseAssignPolicy;
+ using ElementwiseConstructPolicy =
+ typename Storage::ElementwiseConstructPolicy;
+ using MoveAssignmentPolicy = typename Storage::MoveAssignmentPolicy;
public:
using allocator_type = A;
diff --git a/absl/container/inlined_vector_test.cc b/absl/container/inlined_vector_test.cc
index 65ddbab6..1dc6c81b 100644
--- a/absl/container/inlined_vector_test.cc
+++ b/absl/container/inlined_vector_test.cc
@@ -1841,98 +1841,185 @@ MATCHER(HasValue, "") {
return ::testing::get<0>(arg).value() == ::testing::get<1>(arg);
}
-TEST(MoveAssignment, NonAssignable) {
+TEST(NonAssignableMoveAssignmentTest, AllocatedToInline) {
using X = MoveConstructibleOnlyInstance;
- {
- InstanceTracker tracker;
- absl::InlinedVector<X, 2> inlined;
- inlined.emplace_back(1);
- absl::InlinedVector<X, 2> allocated;
- allocated.emplace_back(1);
- allocated.emplace_back(2);
- allocated.emplace_back(3);
- tracker.ResetCopiesMovesSwaps();
+ InstanceTracker tracker;
+ absl::InlinedVector<X, 2> inlined;
+ inlined.emplace_back(1);
+ absl::InlinedVector<X, 2> allocated;
+ allocated.emplace_back(1);
+ allocated.emplace_back(2);
+ allocated.emplace_back(3);
+ tracker.ResetCopiesMovesSwaps();
- inlined = std::move(allocated);
- // passed ownership of the allocated storage
- EXPECT_EQ(tracker.moves(), 0);
- EXPECT_EQ(tracker.live_instances(), 3);
+ inlined = std::move(allocated);
+ // passed ownership of the allocated storage
+ EXPECT_EQ(tracker.moves(), 0);
+ EXPECT_EQ(tracker.live_instances(), 3);
- EXPECT_THAT(inlined, Pointwise(HasValue(), {1, 2, 3}));
- }
+ EXPECT_THAT(inlined, Pointwise(HasValue(), {1, 2, 3}));
+}
- {
- InstanceTracker tracker;
- absl::InlinedVector<X, 2> inlined;
- inlined.emplace_back(1);
- absl::InlinedVector<X, 2> allocated;
- allocated.emplace_back(1);
- allocated.emplace_back(2);
- allocated.emplace_back(3);
- tracker.ResetCopiesMovesSwaps();
+TEST(NonAssignableMoveAssignmentTest, InlineToAllocated) {
+ using X = MoveConstructibleOnlyInstance;
+ InstanceTracker tracker;
+ absl::InlinedVector<X, 2> inlined;
+ inlined.emplace_back(1);
+ absl::InlinedVector<X, 2> allocated;
+ allocated.emplace_back(1);
+ allocated.emplace_back(2);
+ allocated.emplace_back(3);
+ tracker.ResetCopiesMovesSwaps();
- allocated = std::move(inlined);
- // Moved elements
- EXPECT_EQ(tracker.moves(), 1);
- EXPECT_EQ(tracker.live_instances(), 1);
+ allocated = std::move(inlined);
+ // Moved elements
+ EXPECT_EQ(tracker.moves(), 1);
+ EXPECT_EQ(tracker.live_instances(), 1);
- EXPECT_THAT(allocated, Pointwise(HasValue(), {1}));
- }
+ EXPECT_THAT(allocated, Pointwise(HasValue(), {1}));
+}
- {
- InstanceTracker tracker;
- absl::InlinedVector<X, 2> inlined_a;
- inlined_a.emplace_back(1);
- absl::InlinedVector<X, 2> inlined_b;
- inlined_b.emplace_back(1);
- tracker.ResetCopiesMovesSwaps();
+TEST(NonAssignableMoveAssignmentTest, InlineToInline) {
+ using X = MoveConstructibleOnlyInstance;
+ InstanceTracker tracker;
+ absl::InlinedVector<X, 2> inlined_a;
+ inlined_a.emplace_back(1);
+ absl::InlinedVector<X, 2> inlined_b;
+ inlined_b.emplace_back(1);
+ tracker.ResetCopiesMovesSwaps();
- inlined_a = std::move(inlined_b);
- // Moved elements
- EXPECT_EQ(tracker.moves(), 1);
- EXPECT_EQ(tracker.live_instances(), 1);
+ inlined_a = std::move(inlined_b);
+ // Moved elements
+ EXPECT_EQ(tracker.moves(), 1);
+ EXPECT_EQ(tracker.live_instances(), 1);
- EXPECT_THAT(inlined_a, Pointwise(HasValue(), {1}));
- }
+ EXPECT_THAT(inlined_a, Pointwise(HasValue(), {1}));
+}
- {
- InstanceTracker tracker;
- absl::InlinedVector<X, 2> allocated_a;
- allocated_a.emplace_back(1);
- allocated_a.emplace_back(2);
- allocated_a.emplace_back(3);
- absl::InlinedVector<X, 2> allocated_b;
- allocated_b.emplace_back(4);
- allocated_b.emplace_back(5);
- allocated_b.emplace_back(6);
- allocated_b.emplace_back(7);
- tracker.ResetCopiesMovesSwaps();
+TEST(NonAssignableMoveAssignmentTest, AllocatedToAllocated) {
+ using X = MoveConstructibleOnlyInstance;
+ InstanceTracker tracker;
+ absl::InlinedVector<X, 2> allocated_a;
+ allocated_a.emplace_back(1);
+ allocated_a.emplace_back(2);
+ allocated_a.emplace_back(3);
+ absl::InlinedVector<X, 2> allocated_b;
+ allocated_b.emplace_back(4);
+ allocated_b.emplace_back(5);
+ allocated_b.emplace_back(6);
+ allocated_b.emplace_back(7);
+ tracker.ResetCopiesMovesSwaps();
- allocated_a = std::move(allocated_b);
- // passed ownership of the allocated storage
- EXPECT_EQ(tracker.moves(), 0);
- EXPECT_EQ(tracker.live_instances(), 4);
+ allocated_a = std::move(allocated_b);
+ // passed ownership of the allocated storage
+ EXPECT_EQ(tracker.moves(), 0);
+ EXPECT_EQ(tracker.live_instances(), 4);
- EXPECT_THAT(allocated_a, Pointwise(HasValue(), {4, 5, 6, 7}));
- }
+ EXPECT_THAT(allocated_a, Pointwise(HasValue(), {4, 5, 6, 7}));
+}
- {
- InstanceTracker tracker;
- absl::InlinedVector<X, 2> v;
- v.emplace_back(1);
- v.emplace_back(2);
- v.emplace_back(3);
+TEST(NonAssignableMoveAssignmentTest, AssignThis) {
+ using X = MoveConstructibleOnlyInstance;
+ InstanceTracker tracker;
+ absl::InlinedVector<X, 2> v;
+ v.emplace_back(1);
+ v.emplace_back(2);
+ v.emplace_back(3);
- tracker.ResetCopiesMovesSwaps();
+ tracker.ResetCopiesMovesSwaps();
- // Obfuscated in order to pass -Wself-move.
- v = std::move(*std::addressof(v));
- // nothing happens
- EXPECT_EQ(tracker.moves(), 0);
- EXPECT_EQ(tracker.live_instances(), 3);
+ // Obfuscated in order to pass -Wself-move.
+ v = std::move(*std::addressof(v));
+ // nothing happens
+ EXPECT_EQ(tracker.moves(), 0);
+ EXPECT_EQ(tracker.live_instances(), 3);
- EXPECT_THAT(v, Pointwise(HasValue(), {1, 2, 3}));
- }
+ EXPECT_THAT(v, Pointwise(HasValue(), {1, 2, 3}));
+}
+
+class NonSwappableInstance : public absl::test_internal::BaseCountedInstance {
+ public:
+ explicit NonSwappableInstance(int x) : BaseCountedInstance(x) {}
+ NonSwappableInstance(const NonSwappableInstance& other) = default;
+ NonSwappableInstance& operator=(const NonSwappableInstance& other) = default;
+ NonSwappableInstance(NonSwappableInstance&& other) = default;
+ NonSwappableInstance& operator=(NonSwappableInstance&& other) = default;
+};
+
+void swap(NonSwappableInstance&, NonSwappableInstance&) = delete;
+
+TEST(NonSwappableSwapTest, InlineAndAllocatedTransferStorageAndMove) {
+ using X = NonSwappableInstance;
+ InstanceTracker tracker;
+ absl::InlinedVector<X, 2> inlined;
+ inlined.emplace_back(1);
+ absl::InlinedVector<X, 2> allocated;
+ allocated.emplace_back(1);
+ allocated.emplace_back(2);
+ allocated.emplace_back(3);
+ tracker.ResetCopiesMovesSwaps();
+
+ inlined.swap(allocated);
+ EXPECT_EQ(tracker.moves(), 1);
+ EXPECT_EQ(tracker.live_instances(), 4);
+
+ EXPECT_THAT(inlined, Pointwise(HasValue(), {1, 2, 3}));
+}
+
+TEST(NonSwappableSwapTest, InlineAndInlineMoveIndividualElements) {
+ using X = NonSwappableInstance;
+ InstanceTracker tracker;
+ absl::InlinedVector<X, 2> inlined_a;
+ inlined_a.emplace_back(1);
+ absl::InlinedVector<X, 2> inlined_b;
+ inlined_b.emplace_back(2);
+ tracker.ResetCopiesMovesSwaps();
+
+ inlined_a.swap(inlined_b);
+ EXPECT_EQ(tracker.moves(), 3);
+ EXPECT_EQ(tracker.live_instances(), 2);
+
+ EXPECT_THAT(inlined_a, Pointwise(HasValue(), {2}));
+ EXPECT_THAT(inlined_b, Pointwise(HasValue(), {1}));
+}
+
+TEST(NonSwappableSwapTest, AllocatedAndAllocatedOnlyTransferStorage) {
+ using X = NonSwappableInstance;
+ InstanceTracker tracker;
+ absl::InlinedVector<X, 2> allocated_a;
+ allocated_a.emplace_back(1);
+ allocated_a.emplace_back(2);
+ allocated_a.emplace_back(3);
+ absl::InlinedVector<X, 2> allocated_b;
+ allocated_b.emplace_back(4);
+ allocated_b.emplace_back(5);
+ allocated_b.emplace_back(6);
+ allocated_b.emplace_back(7);
+ tracker.ResetCopiesMovesSwaps();
+
+ allocated_a.swap(allocated_b);
+ EXPECT_EQ(tracker.moves(), 0);
+ EXPECT_EQ(tracker.live_instances(), 7);
+
+ EXPECT_THAT(allocated_a, Pointwise(HasValue(), {4, 5, 6, 7}));
+ EXPECT_THAT(allocated_b, Pointwise(HasValue(), {1, 2, 3}));
+}
+
+TEST(NonSwappableSwapTest, SwapThis) {
+ using X = NonSwappableInstance;
+ InstanceTracker tracker;
+ absl::InlinedVector<X, 2> v;
+ v.emplace_back(1);
+ v.emplace_back(2);
+ v.emplace_back(3);
+
+ tracker.ResetCopiesMovesSwaps();
+
+ v.swap(v);
+ EXPECT_EQ(tracker.moves(), 0);
+ EXPECT_EQ(tracker.live_instances(), 3);
+
+ EXPECT_THAT(v, Pointwise(HasValue(), {1, 2, 3}));
}
} // anonymous namespace
diff --git a/absl/container/internal/inlined_vector.h b/absl/container/internal/inlined_vector.h
index f623494c..e2dd843f 100644
--- a/absl/container/internal/inlined_vector.h
+++ b/absl/container/internal/inlined_vector.h
@@ -85,6 +85,8 @@ using IsMemcpyOk =
template <typename A>
using IsMoveAssignOk = std::is_move_assignable<ValueType<A>>;
+template <typename A>
+using IsSwapOk = absl::type_traits_internal::IsSwappable<ValueType<A>>;
template <typename T>
struct TypeIdentity {
@@ -300,6 +302,20 @@ class ConstructionTransaction {
template <typename T, size_t N, typename A>
class Storage {
public:
+ struct MemcpyPolicy {};
+ struct ElementwiseAssignPolicy {};
+ struct ElementwiseSwapPolicy {};
+ struct ElementwiseConstructPolicy {};
+
+ using MoveAssignmentPolicy = absl::conditional_t<
+ IsMemcpyOk<A>::value, MemcpyPolicy,
+ absl::conditional_t<IsMoveAssignOk<A>::value, ElementwiseAssignPolicy,
+ ElementwiseConstructPolicy>>;
+ using SwapPolicy = absl::conditional_t<
+ IsMemcpyOk<A>::value, MemcpyPolicy,
+ absl::conditional_t<IsSwapOk<A>::value, ElementwiseSwapPolicy,
+ ElementwiseConstructPolicy>>;
+
static SizeType<A> NextCapacity(SizeType<A> current_capacity) {
return current_capacity * 2;
}
@@ -476,6 +492,13 @@ class Storage {
Inlined inlined;
};
+ void SwapN(ElementwiseSwapPolicy, Storage* other, SizeType<A> n);
+ void SwapN(ElementwiseConstructPolicy, Storage* other, SizeType<A> n);
+
+ void SwapInlinedElements(MemcpyPolicy, Storage* other);
+ template <typename NotMemcpyPolicy>
+ void SwapInlinedElements(NotMemcpyPolicy, Storage* other);
+
template <typename... Args>
ABSL_ATTRIBUTE_NOINLINE Reference<A> EmplaceBackSlow(Args&&... args);
@@ -889,26 +912,7 @@ auto Storage<T, N, A>::Swap(Storage* other_storage_ptr) -> void {
if (GetIsAllocated() && other_storage_ptr->GetIsAllocated()) {
swap(data_.allocated, other_storage_ptr->data_.allocated);
} else if (!GetIsAllocated() && !other_storage_ptr->GetIsAllocated()) {
- Storage* small_ptr = this;
- Storage* large_ptr = other_storage_ptr;
- if (small_ptr->GetSize() > large_ptr->GetSize()) swap(small_ptr, large_ptr);
-
- for (SizeType<A> i = 0; i < small_ptr->GetSize(); ++i) {
- swap(small_ptr->GetInlinedData()[i], large_ptr->GetInlinedData()[i]);
- }
-
- IteratorValueAdapter<A, MoveIterator<A>> move_values(
- MoveIterator<A>(large_ptr->GetInlinedData() + small_ptr->GetSize()));
-
- ConstructElements<A>(large_ptr->GetAllocator(),
- small_ptr->GetInlinedData() + small_ptr->GetSize(),
- move_values,
- large_ptr->GetSize() - small_ptr->GetSize());
-
- DestroyAdapter<A>::DestroyElements(
- large_ptr->GetAllocator(),
- large_ptr->GetInlinedData() + small_ptr->GetSize(),
- large_ptr->GetSize() - small_ptr->GetSize());
+ SwapInlinedElements(SwapPolicy{}, other_storage_ptr);
} else {
Storage* allocated_ptr = this;
Storage* inlined_ptr = other_storage_ptr;
@@ -944,6 +948,68 @@ auto Storage<T, N, A>::Swap(Storage* other_storage_ptr) -> void {
swap(GetAllocator(), other_storage_ptr->GetAllocator());
}
+template <typename T, size_t N, typename A>
+void Storage<T, N, A>::SwapN(ElementwiseSwapPolicy, Storage* other,
+ SizeType<A> n) {
+ std::swap_ranges(GetInlinedData(), GetInlinedData() + n,
+ other->GetInlinedData());
+}
+
+template <typename T, size_t N, typename A>
+void Storage<T, N, A>::SwapN(ElementwiseConstructPolicy, Storage* other,
+ SizeType<A> n) {
+ Pointer<A> a = GetInlinedData();
+ Pointer<A> b = other->GetInlinedData();
+ // see note on allocators in `SwapInlinedElements`.
+ A& allocator_a = GetAllocator();
+ A& allocator_b = other->GetAllocator();
+ for (SizeType<A> i = 0; i < n; ++i, ++a, ++b) {
+ ValueType<A> tmp(std::move(*a));
+
+ AllocatorTraits<A>::destroy(allocator_a, a);
+ AllocatorTraits<A>::construct(allocator_b, a, std::move(*b));
+
+ AllocatorTraits<A>::destroy(allocator_b, b);
+ AllocatorTraits<A>::construct(allocator_a, b, std::move(tmp));
+ }
+}
+
+template <typename T, size_t N, typename A>
+void Storage<T, N, A>::SwapInlinedElements(MemcpyPolicy, Storage* other) {
+ Data tmp = data_;
+ data_ = other->data_;
+ other->data_ = tmp;
+}
+
+template <typename T, size_t N, typename A>
+template <typename NotMemcpyPolicy>
+void Storage<T, N, A>::SwapInlinedElements(NotMemcpyPolicy policy,
+ Storage* other) {
+ // Note: `destroy` needs to use pre-swap allocator while `construct` -
+ // post-swap allocator. Allocators will be swaped later on outside of
+ // `SwapInlinedElements`.
+ Storage* small_ptr = this;
+ Storage* large_ptr = other;
+ if (small_ptr->GetSize() > large_ptr->GetSize()) {
+ std::swap(small_ptr, large_ptr);
+ }
+
+ auto small_size = small_ptr->GetSize();
+ auto diff = large_ptr->GetSize() - small_size;
+ SwapN(policy, other, small_size);
+
+ IteratorValueAdapter<A, MoveIterator<A>> move_values(
+ MoveIterator<A>(large_ptr->GetInlinedData() + small_size));
+
+ ConstructElements<A>(large_ptr->GetAllocator(),
+ small_ptr->GetInlinedData() + small_size, move_values,
+ diff);
+
+ DestroyAdapter<A>::DestroyElements(large_ptr->GetAllocator(),
+ large_ptr->GetInlinedData() + small_size,
+ diff);
+}
+
// End ignore "array-bounds"
#if !defined(__clang__) && defined(__GNUC__)
#pragma GCC diagnostic pop
generated by cgit v1.2.3 (git 2.39.1) at 2024-12-27 12:39:00 +0000