summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--absl/container/inlined_vector.h173
-rw-r--r--absl/container/internal/inlined_vector.h116
2 files changed, 229 insertions, 60 deletions
diff --git a/absl/container/inlined_vector.h b/absl/container/inlined_vector.h
index 42a4f946..f5b819a1 100644
--- a/absl/container/inlined_vector.h
+++ b/absl/container/inlined_vector.h
@@ -77,8 +77,6 @@ class InlinedVector {
template <typename TheA>
using MoveIterator = inlined_vector_internal::MoveIterator<TheA>;
template <typename TheA>
- using IsMemcpyOk = inlined_vector_internal::IsMemcpyOk<TheA>;
- template <typename TheA>
using IsMoveAssignOk = inlined_vector_internal::IsMoveAssignOk<TheA>;
template <typename TheA, typename Iterator>
@@ -182,14 +180,33 @@ class InlinedVector {
// provided `allocator`.
InlinedVector(const InlinedVector& other, const allocator_type& allocator)
: storage_(allocator) {
+ // Fast path: if the other vector is empty, there's nothing for us to do.
if (other.empty()) {
- // Empty; nothing to do.
- } else if (IsMemcpyOk<A>::value && !other.storage_.GetIsAllocated()) {
- // Memcpy-able and do not need allocation.
+ return;
+ }
+
+ // Fast path: if the value type is trivially copy constructible, we know the
+ // allocator doesn't do anything fancy, and there is nothing on the heap
+ // then we know it is legal for us to simply memcpy the other vector's
+ // inlined bytes to form our copy of its elements.
+ //
+ // TODO(b/274984172): the condition on copy-assignability is here only for
+ // historical reasons. It doesn't make semantic sense: we don't need to be
+ // able to copy assign here, we are doing an "as-if" copy construction.
+ //
+ // TODO(b/274984172): the condition on trivial destructibility is here only
+ // for historical reasons. It doesn't make sense: there is no destruction
+ // here.
+ if (absl::is_trivially_copy_constructible<value_type>::value &&
+ std::is_same<A, std::allocator<value_type>>::value &&
+ absl::is_trivially_copy_assignable<value_type>::value &&
+ absl::is_trivially_destructible<value_type>::value &&
+ !other.storage_.GetIsAllocated()) {
storage_.MemcpyFrom(other.storage_);
- } else {
- storage_.InitFrom(other.storage_);
+ return;
}
+
+ storage_.InitFrom(other.storage_);
}
// Creates an inlined vector by moving in the contents of `other` without
@@ -210,26 +227,57 @@ class InlinedVector {
absl::allocator_is_nothrow<allocator_type>::value ||
std::is_nothrow_move_constructible<value_type>::value)
: storage_(other.storage_.GetAllocator()) {
- if (IsMemcpyOk<A>::value) {
+ // Fast path: if the value type can be trivally move constructed and
+ // destroyed, and we know the allocator doesn't do anything fancy, then it's
+ // safe for us to simply adopt the contents of the storage for `other` and
+ // remove its own reference to them. It's as if we had individually
+ // move-constructed each value and then destroyed the original.
+ //
+ // TODO(b/274984172): we check for copy-constructibility here only for
+ // historical reasons. This is too strict: we are simulating move
+ // construction here. In fact this is arguably incorrect, since in theory a
+ // type might be trivially copy-constructible but not trivially
+ // move-constructible.
+ //
+ // TODO(b/274984172): the condition on copy-assignability is here only for
+ // historical reasons. It doesn't make semantic sense: we don't need to be
+ // able to copy assign here, we are doing an "as-if" move construction.
+ //
+ // TODO(b/274984172): a move construction followed by destroying the source
+ // is a "relocation" in the language of P1144R4. So actually the minimum
+ // condition we need here (in addition to the allocator) is "trivially
+ // relocatable". Relaxing this would allow using memcpy with types like
+ // std::unique_ptr that opt in to declaring themselves trivially relocatable
+ // despite not being trivially move-constructible and/oror destructible.
+ if (absl::is_trivially_copy_constructible<value_type>::value &&
+ absl::is_trivially_destructible<value_type>::value &&
+ std::is_same<A, std::allocator<value_type>>::value &&
+ absl::is_trivially_copy_assignable<value_type>::value) {
storage_.MemcpyFrom(other.storage_);
-
other.storage_.SetInlinedSize(0);
- } else if (other.storage_.GetIsAllocated()) {
+ return;
+ }
+
+ // Fast path: if the other vector is on the heap, we can simply take over
+ // its allocation.
+ if (other.storage_.GetIsAllocated()) {
storage_.SetAllocation({other.storage_.GetAllocatedData(),
other.storage_.GetAllocatedCapacity()});
storage_.SetAllocatedSize(other.storage_.GetSize());
other.storage_.SetInlinedSize(0);
- } else {
- IteratorValueAdapter<A, MoveIterator<A>> other_values(
- MoveIterator<A>(other.storage_.GetInlinedData()));
+ return;
+ }
- inlined_vector_internal::ConstructElements<A>(
- storage_.GetAllocator(), storage_.GetInlinedData(), other_values,
- other.storage_.GetSize());
+ // Otherwise we must move each element individually.
+ IteratorValueAdapter<A, MoveIterator<A>> other_values(
+ MoveIterator<A>(other.storage_.GetInlinedData()));
- storage_.SetInlinedSize(other.storage_.GetSize());
- }
+ inlined_vector_internal::ConstructElements<A>(
+ storage_.GetAllocator(), storage_.GetInlinedData(), other_values,
+ other.storage_.GetSize());
+
+ storage_.SetInlinedSize(other.storage_.GetSize());
}
// Creates an inlined vector by moving in the contents of `other` with a copy
@@ -244,22 +292,53 @@ class InlinedVector {
const allocator_type&
allocator) noexcept(absl::allocator_is_nothrow<allocator_type>::value)
: storage_(allocator) {
- if (IsMemcpyOk<A>::value) {
+ // Fast path: if the value type can be trivally move constructed and
+ // destroyed and we know the allocator doesn't do anything fancy, then it's
+ // safe for us to simply adopt the contents of the storage for `other` and
+ // remove its own reference to them. It's as if we had individually
+ // move-constructed each value and then destroyed the original.
+ //
+ // TODO(b/274984172): we check for copy-constructibility here only for
+ // historical reasons. This is too strict: we are simulating move
+ // construction here. In fact this is arguably incorrect, since in theory a
+ // type might be trivially copy-constructible but not trivially
+ // move-constructible.
+ //
+ // TODO(b/274984172): the condition on copy-assignability is here only for
+ // historical reasons. It doesn't make semantic sense: we don't need to be
+ // able to copy assign here, we are doing an "as-if" move construction.
+ //
+ // TODO(b/274984172): a move construction followed by destroying the source
+ // is a "relocation" in the language of P1144R4. So actually the minimum
+ // condition we need here (in addition to the allocator) is "trivially
+ // relocatable". Relaxing this would allow using memcpy with types like
+ // std::unique_ptr that opt in to declaring themselves trivially relocatable
+ // despite not being trivially move-constructible and/oror destructible.
+ if (absl::is_trivially_copy_constructible<value_type>::value &&
+ absl::is_trivially_destructible<value_type>::value &&
+ std::is_same<A, std::allocator<value_type>>::value &&
+ absl::is_trivially_copy_assignable<value_type>::value) {
storage_.MemcpyFrom(other.storage_);
-
other.storage_.SetInlinedSize(0);
- } else if ((storage_.GetAllocator() == other.storage_.GetAllocator()) &&
- other.storage_.GetIsAllocated()) {
+ return;
+ }
+
+ // Fast path: if the other vector is on the heap and shared the same
+ // allocator, we can simply take over its allocation.
+ if ((storage_.GetAllocator() == other.storage_.GetAllocator()) &&
+ other.storage_.GetIsAllocated()) {
storage_.SetAllocation({other.storage_.GetAllocatedData(),
other.storage_.GetAllocatedCapacity()});
storage_.SetAllocatedSize(other.storage_.GetSize());
other.storage_.SetInlinedSize(0);
- } else {
- storage_.Initialize(IteratorValueAdapter<A, MoveIterator<A>>(
- MoveIterator<A>(other.data())),
- other.size());
+ return;
}
+
+ // Otherwise we must move each element individually.
+ storage_.Initialize(
+ IteratorValueAdapter<A, MoveIterator<A>>(MoveIterator<A>(other.data())),
+ other.size());
}
~InlinedVector() {}
@@ -784,6 +863,10 @@ class InlinedVector {
friend H AbslHashValue(H h, const absl::InlinedVector<TheT, TheN, TheA>& a);
void MoveAssignment(MemcpyPolicy, InlinedVector&& other) {
+ // TODO(b/274984172): we shouldn't need to do this. We already know the
+ // elements are trivially destructible when our move-assignment policy is
+ // MemcpyPolicy. Except the other overloads of MoveAssignment call this one.
+ // Make them not.
inlined_vector_internal::DestroyAdapter<A>::DestroyElements(
storage_.GetAllocator(), data(), size());
storage_.DeallocateIfAllocated();
@@ -793,30 +876,38 @@ class InlinedVector {
}
void MoveAssignment(ElementwiseAssignPolicy, InlinedVector&& other) {
+ // Fast path: if the other vector is on the heap then we don't worry about
+ // actually move-assigning each element. Instead we only throw away our own
+ // existing elements and adopt the heap allocation of the other vector.
if (other.storage_.GetIsAllocated()) {
MoveAssignment(MemcpyPolicy{}, std::move(other));
- } else {
- storage_.Assign(IteratorValueAdapter<A, MoveIterator<A>>(
- MoveIterator<A>(other.storage_.GetInlinedData())),
- other.size());
+ return;
}
+
+ storage_.Assign(IteratorValueAdapter<A, MoveIterator<A>>(
+ MoveIterator<A>(other.storage_.GetInlinedData())),
+ other.size());
}
void MoveAssignment(ElementwiseConstructPolicy, InlinedVector&& other) {
+ // Fast path: if the other vector is on the heap then we don't worry about
+ // actually move-assigning each element. Instead we only throw away our own
+ // existing elements and adopt the heap allocation of the other vector.
if (other.storage_.GetIsAllocated()) {
MoveAssignment(MemcpyPolicy{}, std::move(other));
- } else {
- inlined_vector_internal::DestroyAdapter<A>::DestroyElements(
- storage_.GetAllocator(), data(), size());
- storage_.DeallocateIfAllocated();
-
- IteratorValueAdapter<A, MoveIterator<A>> other_values(
- MoveIterator<A>(other.storage_.GetInlinedData()));
- inlined_vector_internal::ConstructElements<A>(
- storage_.GetAllocator(), storage_.GetInlinedData(), other_values,
- other.storage_.GetSize());
- storage_.SetInlinedSize(other.storage_.GetSize());
+ return;
}
+
+ inlined_vector_internal::DestroyAdapter<A>::DestroyElements(
+ storage_.GetAllocator(), data(), size());
+ storage_.DeallocateIfAllocated();
+
+ IteratorValueAdapter<A, MoveIterator<A>> other_values(
+ MoveIterator<A>(other.storage_.GetInlinedData()));
+ inlined_vector_internal::ConstructElements<A>(
+ storage_.GetAllocator(), storage_.GetInlinedData(), other_values,
+ other.storage_.GetSize());
+ storage_.SetInlinedSize(other.storage_.GetSize());
}
Storage storage_;
diff --git a/absl/container/internal/inlined_vector.h b/absl/container/internal/inlined_vector.h
index 0398f530..3cd69b55 100644
--- a/absl/container/internal/inlined_vector.h
+++ b/absl/container/internal/inlined_vector.h
@@ -77,13 +77,6 @@ using IsAtLeastForwardIterator = std::is_convertible<
std::forward_iterator_tag>;
template <typename A>
-using IsMemcpyOk =
- absl::conjunction<std::is_same<A, std::allocator<ValueType<A>>>,
- absl::is_trivially_copy_constructible<ValueType<A>>,
- absl::is_trivially_copy_assignable<ValueType<A>>,
- absl::is_trivially_destructible<ValueType<A>>>;
-
-template <typename A>
using IsMoveAssignOk = std::is_move_assignable<ValueType<A>>;
template <typename A>
using IsSwapOk = absl::type_traits_internal::IsSwappable<ValueType<A>>;
@@ -308,11 +301,51 @@ class Storage {
struct ElementwiseConstructPolicy {};
using MoveAssignmentPolicy = absl::conditional_t<
- IsMemcpyOk<A>::value, MemcpyPolicy,
+ // Fast path: if the value type can be trivally move assigned and
+ // destroyed, and we know the allocator doesn't do anything fancy, then
+ // it's safe for us to simply adopt the contents of the storage for
+ // `other` and remove its own reference to them. It's as if we had
+ // individually move-assigned each value and then destroyed the original.
+ //
+ // TODO(b/274984172): we check for copy-assignability here only for
+ // historical reasons. This is too strict: we are simulating move
+ // assignment here.
+ //
+ // TODO(b/274984172): the condition on copy-constructibility is here only
+ // for historical reasons. It doesn't make semantic sense: we don't need
+ // to be able to copy construct here, we are doing an "as-if" move
+ // assignment.
+ absl::conjunction<
+ absl::is_trivially_copy_assignable<ValueType<A>>,
+ absl::is_trivially_destructible<ValueType<A>>,
+ std::is_same<A, std::allocator<ValueType<A>>>,
+ absl::is_trivially_copy_constructible<ValueType<A>>>::value,
+ MemcpyPolicy,
+ // Otherwise we use move assignment if possible. If not, we simulate
+ // move assignment using move construction.
+ //
+ // Note that this is in contrast to e.g. std::vector and std::optional,
+ // which are themselves not move-assignable when their contained type is
+ // not.
absl::conditional_t<IsMoveAssignOk<A>::value, ElementwiseAssignPolicy,
ElementwiseConstructPolicy>>;
- using SwapPolicy = absl::conditional_t<
- IsMemcpyOk<A>::value, MemcpyPolicy,
+
+ // The policy to be used specifically when swapping inlined elements.
+ using SwapInlinedElementsPolicy = absl::conditional_t<
+ // Fast path: if the value type can be trivally move constructed/assigned
+ // and destroyed, and we know the allocator doesn't do anything fancy,
+ // then it's safe for us to simply swap the bytes in the inline storage.
+ // It's as if we had move-constructed a temporary vector, move-assigned
+ // one to the other, then move-assigned the first from the temporary.
+ //
+ // TODO(b/274984172): we check for copy-constructability and
+ // -assignability here only for historical reasons. This is too strict: we
+ // are simulating move operations here.
+ absl::conjunction<absl::is_trivially_copy_constructible<ValueType<A>>,
+ absl::is_trivially_copy_assignable<ValueType<A>>,
+ absl::is_trivially_destructible<ValueType<A>>,
+ std::is_same<A, std::allocator<ValueType<A>>>>::value,
+ MemcpyPolicy,
absl::conditional_t<IsSwapOk<A>::value, ElementwiseSwapPolicy,
ElementwiseConstructPolicy>>;
@@ -335,14 +368,26 @@ class Storage {
: metadata_(allocator, /* size and is_allocated */ 0u) {}
~Storage() {
+ // Fast path: if we are empty and not allocated, there's nothing to do.
if (GetSizeAndIsAllocated() == 0) {
- // Empty and not allocated; nothing to do.
- } else if (IsMemcpyOk<A>::value) {
- // No destructors need to be run; just deallocate if necessary.
+ return;
+ }
+
+ // Fast path: if no destructors need to be run and we know the allocator
+ // doesn't do anything fancy, then all we need to do is allocate (and maybe
+ // not even that).
+ //
+ // TODO(b/274984172): the conditions on copy constructibility/assignability
+ // are unnecessary, and are here only for historical reasons. Remove them.
+ if (absl::is_trivially_destructible<ValueType<A>>::value &&
+ std::is_same<A, std::allocator<ValueType<A>>>::value &&
+ absl::is_trivially_copy_constructible<ValueType<A>>::value &&
+ absl::is_trivially_copy_assignable<ValueType<A>>::value) {
DeallocateIfAllocated();
- } else {
- DestroyContents();
+ return;
}
+
+ DestroyContents();
}
// ---------------------------------------------------------------------------
@@ -461,8 +506,25 @@ class Storage {
}
void MemcpyFrom(const Storage& other_storage) {
- ABSL_HARDENING_ASSERT(IsMemcpyOk<A>::value ||
- other_storage.GetIsAllocated());
+ // Assumption check: it doesn't make sense to memcpy inlined elements unless
+ // we know the allocator doesn't do anything fancy, and one of the following
+ // holds:
+ //
+ // * It's possible to trivially move construct/assign the elements and
+ // then destroy the source.
+ //
+ // * It's possible to trivially copy construct/assign the elements.
+ //
+ // TODO(b/274984172): the conditions here, preserved from historical ones,
+ // don't actually implement this. They are far too conservative (they don't
+ // work for move-only types, and require both copyability and
+ // assignability).
+ ABSL_HARDENING_ASSERT(
+ other_storage.GetIsAllocated() ||
+ (std::is_same<A, std::allocator<ValueType<A>>>::value &&
+ absl::is_trivially_copy_constructible<ValueType<A>>::value &&
+ absl::is_trivially_copy_assignable<ValueType<A>>::value &&
+ absl::is_trivially_destructible<ValueType<A>>::value));
GetSizeAndIsAllocated() = other_storage.GetSizeAndIsAllocated();
data_ = other_storage.data_;
@@ -542,13 +604,29 @@ void Storage<T, N, A>::InitFrom(const Storage& other) {
dst = allocation.data;
src = other.GetAllocatedData();
}
- if (IsMemcpyOk<A>::value) {
+
+ // Fast path: if the value type is trivially copy constructible and we know
+ // the allocator doesn't do anything fancy, then we know it is legal for us to
+ // simply memcpy the other vector's elements.
+ //
+ // TODO(b/274984172): the condition on copy-assignability is here only for
+ // historical reasons. It doesn't make semantic sense: we don't need to be
+ // able to copy assign here, we are doing an "as-if" copy construction.
+ //
+ // TODO(b/274984172): the condition on trivial destructibility is here only
+ // for historical reasons. It doesn't make sense: there is no destruction
+ // here.
+ if (absl::is_trivially_copy_constructible<ValueType<A>>::value &&
+ std::is_same<A, std::allocator<ValueType<A>>>::value &&
+ absl::is_trivially_copy_assignable<ValueType<A>>::value &&
+ absl::is_trivially_destructible<ValueType<A>>::value) {
std::memcpy(reinterpret_cast<char*>(dst),
reinterpret_cast<const char*>(src), n * sizeof(ValueType<A>));
} else {
auto values = IteratorValueAdapter<A, ConstPointer<A>>(src);
ConstructElements<A>(GetAllocator(), dst, values, n);
}
+
GetSizeAndIsAllocated() = other.GetSizeAndIsAllocated();
}
@@ -921,7 +999,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()) {
- SwapInlinedElements(SwapPolicy{}, other_storage_ptr);
+ SwapInlinedElements(SwapInlinedElementsPolicy{}, other_storage_ptr);
} else {
Storage* allocated_ptr = this;
Storage* inlined_ptr = other_storage_ptr;