From 43ef2148c0936ebf7cb4be6b19927a9d9d145b8f Mon Sep 17 00:00:00 2001 From: Abseil Team Date: Tue, 18 Jun 2019 13:05:50 -0700 Subject: Export of internal Abseil changes. -- 635146be541d732fbf2e9c93c6bec89035552484 by Gennadiy Rozental : Merge external PR #324 PiperOrigin-RevId: 253849839 -- 7a37f87f0f419ab535e59c7dae7961546586671a by Gennadiy Rozental : Merge external PR #323 PiperOrigin-RevId: 253849558 -- 75455e93e1f3987c926f35fbe80a0ea84e4ba35b by CJ Johnson : Removes `ivi` namespace typedef to reduce reader confusion PiperOrigin-RevId: 253789534 -- 2f99d27194468129767c48ab621b952660427493 by CJ Johnson : New benchmarks the various overloads of InlinedVector::assign(...)/InlinedVector::operator=(...) PiperOrigin-RevId: 253787316 -- a0949eb100b93aae22b85b4a4820e4bf9a5a2dbb by CJ Johnson : Updates the definition of `InlinedVector::pop_back(...)` to be cleaner and more direct (hiding the is_allocated branch behind a single call to `data()`) Adds exception safety test for `InlinedVector::pop_back(...)` PiperOrigin-RevId: 253607385 -- 2dbc728ddf84835dcb6341f9a166f1c9bde103b9 by CJ Johnson : Adds the remaining constructor exception safety tests for InlinedVector PiperOrigin-RevId: 253592324 -- 40d88e0d6232c93af5e008088f69ad41cb44e4ce by CJ Johnson : Updates the constructors of InlinedVector to new, exception-safe and more-performant implementations. PiperOrigin-RevId: 253294508 GitOrigin-RevId: 635146be541d732fbf2e9c93c6bec89035552484 Change-Id: I7d37a749632084f5d7fa56d42392e622a9d0180d --- absl/container/internal/inlined_vector.h | 132 ++++++++++++++++++++++++++++++- 1 file changed, 129 insertions(+), 3 deletions(-) (limited to 'absl/container/internal') diff --git a/absl/container/internal/inlined_vector.h b/absl/container/internal/inlined_vector.h index f4eb92ec169a..92c21ab96571 100644 --- a/absl/container/internal/inlined_vector.h +++ b/absl/container/internal/inlined_vector.h @@ -21,6 +21,7 @@ #include #include +#include "absl/base/macros.h" #include "absl/container/internal/compressed_tuple.h" #include "absl/memory/memory.h" #include "absl/meta/type_traits.h" @@ -33,6 +34,14 @@ using IsAtLeastForwardIterator = std::is_convertible< typename std::iterator_traits::iterator_category, std::forward_iterator_tag>; +template +using IsMemcpyOk = absl::conjunction< + std::is_same, + AllocatorType>, + absl::is_trivially_copy_constructible, + absl::is_trivially_copy_assignable, + absl::is_trivially_destructible>; + template void DestroyElements(AllocatorType* alloc_ptr, ValueType* destroy_first, SizeType destroy_size) { @@ -52,6 +61,23 @@ void DestroyElements(AllocatorType* alloc_ptr, ValueType* destroy_first, #endif // NDEBUG } +template +void ConstructElements(AllocatorType* alloc_ptr, ValueType* construct_first, + ValueAdapter* values_ptr, SizeType construct_size) { + // If any construction fails, all completed constructions are rolled back. + for (SizeType i = 0; i < construct_size; ++i) { + ABSL_INTERNAL_TRY { + values_ptr->ConstructNext(alloc_ptr, construct_first + i); + } + ABSL_INTERNAL_CATCH_ANY { + inlined_vector_internal::DestroyElements(alloc_ptr, construct_first, i); + + ABSL_INTERNAL_RETHROW; + } + } +} + template struct StorageView { using pointer = typename AllocatorType::pointer; @@ -62,6 +88,55 @@ struct StorageView { size_type capacity; }; +template +class IteratorValueAdapter { + using pointer = typename AllocatorType::pointer; + using AllocatorTraits = absl::allocator_traits; + + public: + explicit IteratorValueAdapter(const Iterator& it) : it_(it) {} + + void ConstructNext(AllocatorType* alloc_ptr, pointer construct_at) { + AllocatorTraits::construct(*alloc_ptr, construct_at, *it_); + ++it_; + } + + private: + Iterator it_; +}; + +template +class CopyValueAdapter { + using pointer = typename AllocatorType::pointer; + using const_pointer = typename AllocatorType::const_pointer; + using const_reference = typename AllocatorType::const_reference; + using AllocatorTraits = absl::allocator_traits; + + public: + explicit CopyValueAdapter(const_reference v) : ptr_(std::addressof(v)) {} + + void ConstructNext(AllocatorType* alloc_ptr, pointer construct_at) { + AllocatorTraits::construct(*alloc_ptr, construct_at, *ptr_); + } + + private: + const_pointer ptr_; +}; + +template +class DefaultValueAdapter { + using pointer = typename AllocatorType::pointer; + using value_type = typename AllocatorType::value_type; + using AllocatorTraits = absl::allocator_traits; + + public: + explicit DefaultValueAdapter() {} + + void ConstructNext(AllocatorType* alloc_ptr, pointer construct_at) { + AllocatorTraits::construct(*alloc_ptr, construct_at); + } +}; + template class Storage { public: @@ -78,10 +153,20 @@ class Storage { using const_iterator = const_pointer; using reverse_iterator = std::reverse_iterator; using const_reverse_iterator = std::reverse_iterator; + using MoveIterator = std::move_iterator; using AllocatorTraits = absl::allocator_traits; + using IsMemcpyOk = inlined_vector_internal::IsMemcpyOk; using StorageView = inlined_vector_internal::StorageView; + template + using IteratorValueAdapter = + inlined_vector_internal::IteratorValueAdapter; + using CopyValueAdapter = + inlined_vector_internal::CopyValueAdapter; + using DefaultValueAdapter = + inlined_vector_internal::DefaultValueAdapter; + Storage() : metadata_() {} explicit Storage(const allocator_type& alloc) @@ -128,6 +213,8 @@ class Storage { return std::addressof(metadata_.template get<0>()); } + void SetIsAllocated() { GetSizeAndIsAllocated() |= 1; } + void SetAllocatedSize(size_type size) { GetSizeAndIsAllocated() = (size << 1) | static_cast(1); } @@ -151,8 +238,18 @@ class Storage { swap(data_.allocated, other->data_.allocated); } + void MemcpyContents(const Storage& other) { + assert(IsMemcpyOk::value); + + GetSizeAndIsAllocated() = other.GetSizeAndIsAllocated(); + data_ = other.data_; + } + void DestroyAndDeallocate(); + template + void Initialize(ValueAdapter values, size_type new_size); + private: size_type& GetSizeAndIsAllocated() { return metadata_.template get<1>(); } @@ -185,11 +282,10 @@ class Storage { template void Storage::DestroyAndDeallocate() { - namespace ivi = inlined_vector_internal; - StorageView storage_view = MakeStorageView(); - ivi::DestroyElements(GetAllocPtr(), storage_view.data, storage_view.size); + inlined_vector_internal::DestroyElements(GetAllocPtr(), storage_view.data, + storage_view.size); if (GetIsAllocated()) { AllocatorTraits::deallocate(*GetAllocPtr(), storage_view.data, @@ -197,6 +293,36 @@ void Storage::DestroyAndDeallocate() { } } +template +template +auto Storage::Initialize(ValueAdapter values, size_type new_size) + -> void { + // Only callable from constructors! + assert(!GetIsAllocated()); + assert(GetSize() == 0); + + pointer construct_data; + + if (new_size > static_cast(N)) { + // Because this is only called from the `InlinedVector` constructors, it's + // safe to take on the allocation with size `0`. If `ConstructElements(...)` + // throws, deallocation will be automatically handled by `~Storage()`. + construct_data = AllocatorTraits::allocate(*GetAllocPtr(), new_size); + SetAllocatedData(construct_data, new_size); + SetIsAllocated(); + } else { + construct_data = GetInlinedData(); + } + + inlined_vector_internal::ConstructElements(GetAllocPtr(), construct_data, + &values, new_size); + + // Since the initial size was guaranteed to be `0` and the allocated bit is + // already correct for either case, *adding* `new_size` gives us the correct + // result faster than setting it directly. + AddSize(new_size); +} + } // namespace inlined_vector_internal } // namespace absl -- cgit 1.4.1