From c964fcffac27bd4a9ff67fe393410dd1146ef8b8 Mon Sep 17 00:00:00 2001 From: Abseil Team Date: Thu, 27 Jun 2019 17:24:26 -0700 Subject: Export of internal Abseil changes. -- c321829735accc2e6beb81e6a5a4421e5647b876 by CJ Johnson : Updates the definition of InlinedVector::swap(InlinedVector&) to be exception safe and adds exception safety tests PiperOrigin-RevId: 255511536 -- 0d86445891748efb09430eb9ede267b54185a246 by CJ Johnson : Updates the definition of InlinedVector::erase(...) to be exception safe and adds an exception safety test for it. PiperOrigin-RevId: 255492671 -- f07e8fa62dfe9eb0d025b27fca8c6db43c5a328f by CJ Johnson : Updates the implementation of InlinedVector::emplace_back(...) to be exception safe and adds exception safety tests PiperOrigin-RevId: 255422837 -- 4c3be92bfe4c1636a03cef8fd5aa802fed0d2c61 by Abseil Team : Internal Change PiperOrigin-RevId: 255422693 -- 6df38ea42f00678c357a539016163f8ac4c084e6 by Gennadiy Rozental : Introduce public interfaces for setting and getting program usage messages. PiperOrigin-RevId: 255291467 -- 8f21d594aed3971d37db70226847c693eb548edb by Laramie Leavitt : Move absl/random's copy of ABSL_ATTRIBUTE_FORCE_INLINE and ABSL_ATTRIBUTE_NEVER_INLINE into .cc files and rename to prevent conflicts. https://github.com/abseil/abseil-cpp/issues/343 PiperOrigin-RevId: 255288599 -- 6b7430ad0c8bd860fb9394894f5eeedd1acc9f77 by CJ Johnson : Updates the ScopedAllocatorWorks test for InlinedVector to not rely on the byte count allocated by the standard library In doing so, removes LegacyNextCapacityFrom(...) impl function from InlinedVector Also applies clang-format to the test file PiperOrigin-RevId: 255207606 GitOrigin-RevId: c321829735accc2e6beb81e6a5a4421e5647b876 Change-Id: I7438211c36c4549fca2e866658f8d579c65d7d52 --- absl/container/internal/inlined_vector.h | 182 +++++++++++++++++++++++++++---- 1 file changed, 158 insertions(+), 24 deletions(-) (limited to 'absl/container/internal/inlined_vector.h') diff --git a/absl/container/internal/inlined_vector.h b/absl/container/internal/inlined_vector.h index c2802c8..84b9779 100644 --- a/absl/container/internal/inlined_vector.h +++ b/absl/container/internal/inlined_vector.h @@ -364,16 +364,6 @@ class Storage { allocation_tx_ptr->GetCapacity() = 0; } - void SwapSizeAndIsAllocated(Storage* other) { - using std::swap; - swap(GetSizeAndIsAllocated(), other->GetSizeAndIsAllocated()); - } - - void SwapAllocatedSizeAndCapacity(Storage* other) { - using std::swap; - swap(data_.allocated, other->data_.allocated); - } - void MemcpyFrom(const Storage& other_storage) { assert(IsMemcpyOk::value || other_storage.GetIsAllocated()); @@ -390,10 +380,17 @@ class Storage { template void Resize(ValueAdapter values, size_type new_size); + template + reference EmplaceBack(Args&&... args); + + iterator Erase(const_iterator from, const_iterator to); + void Reserve(size_type requested_capacity); void ShrinkToFit(); + void Swap(Storage* other_storage_ptr); + private: size_type& GetSizeAndIsAllocated() { return metadata_.template get<1>(); } @@ -401,14 +398,8 @@ class Storage { return metadata_.template get<1>(); } - static size_type LegacyNextCapacityFrom(size_type current_capacity, - size_type requested_capacity) { - // TODO(johnsoncj): Get rid of this old behavior. - size_type new_capacity = current_capacity; - while (new_capacity < requested_capacity) { - new_capacity *= 2; - } - return new_capacity; + static size_type NextCapacityFrom(size_type current_capacity) { + return current_capacity * 2; } using Metadata = @@ -521,8 +512,7 @@ auto Storage::Resize(ValueAdapter values, size_type new_size) -> void { absl::Span destroy_loop; if (new_size > storage_view.capacity) { - pointer new_data = allocation_tx.Allocate( - LegacyNextCapacityFrom(storage_view.capacity, new_size)); + pointer new_data = allocation_tx.Allocate(new_size); // Construct new objects in `new_data` construct_loop = {new_data + storage_view.size, @@ -562,6 +552,75 @@ auto Storage::Resize(ValueAdapter values, size_type new_size) -> void { SetSize(new_size); } +template +template +auto Storage::EmplaceBack(Args&&... args) -> reference { + StorageView storage_view = MakeStorageView(); + + AllocationTransaction allocation_tx(GetAllocPtr()); + + IteratorValueAdapter move_values( + MoveIterator(storage_view.data)); + + pointer construct_data = + (storage_view.size == storage_view.capacity + ? allocation_tx.Allocate(NextCapacityFrom(storage_view.capacity)) + : storage_view.data); + + pointer last_ptr = construct_data + storage_view.size; + AllocatorTraits::construct(*GetAllocPtr(), last_ptr, + std::forward(args)...); + + if (allocation_tx.DidAllocate()) { + ABSL_INTERNAL_TRY { + inlined_vector_internal::ConstructElements( + GetAllocPtr(), allocation_tx.GetData(), &move_values, + storage_view.size); + } + ABSL_INTERNAL_CATCH_ANY { + AllocatorTraits::destroy(*GetAllocPtr(), last_ptr); + ABSL_INTERNAL_RETHROW; + } + + inlined_vector_internal::DestroyElements(GetAllocPtr(), storage_view.data, + storage_view.size); + + DeallocateIfAllocated(); + AcquireAllocation(&allocation_tx); + SetIsAllocated(); + } + + AddSize(1); + return *last_ptr; +} + +template +auto Storage::Erase(const_iterator from, const_iterator to) + -> iterator { + assert(from != to); + + StorageView storage_view = MakeStorageView(); + + size_type erase_size = std::distance(from, to); + size_type erase_index = + std::distance(const_iterator(storage_view.data), from); + size_type erase_end_index = erase_index + erase_size; + + IteratorValueAdapter move_values( + MoveIterator(storage_view.data + erase_end_index)); + + inlined_vector_internal::AssignElements(storage_view.data + erase_index, + &move_values, + storage_view.size - erase_end_index); + + inlined_vector_internal::DestroyElements( + GetAllocPtr(), storage_view.data + (storage_view.size - erase_size), + erase_size); + + SubtractSize(erase_size); + return iterator(storage_view.data + erase_index); +} + template auto Storage::Reserve(size_type requested_capacity) -> void { StorageView storage_view = MakeStorageView(); @@ -573,8 +632,7 @@ auto Storage::Reserve(size_type requested_capacity) -> void { IteratorValueAdapter move_values( MoveIterator(storage_view.data)); - pointer new_data = allocation_tx.Allocate( - LegacyNextCapacityFrom(storage_view.capacity, requested_capacity)); + pointer new_data = allocation_tx.Allocate(requested_capacity); inlined_vector_internal::ConstructElements(GetAllocPtr(), new_data, &move_values, storage_view.size); @@ -592,8 +650,8 @@ auto Storage::ShrinkToFit() -> void { // May only be called on allocated instances! assert(GetIsAllocated()); - StorageView storage_view = {GetAllocatedData(), GetSize(), - GetAllocatedCapacity()}; + StorageView storage_view{GetAllocatedData(), GetSize(), + GetAllocatedCapacity()}; AllocationTransaction allocation_tx(GetAllocPtr()); @@ -634,6 +692,82 @@ auto Storage::ShrinkToFit() -> void { } } +template +auto Storage::Swap(Storage* other_storage_ptr) -> void { + using std::swap; + assert(this != other_storage_ptr); + + if (GetIsAllocated() && other_storage_ptr->GetIsAllocated()) { + // Both are allocated, thus we can swap the allocations at the top level. + + swap(data_.allocated, other_storage_ptr->data_.allocated); + } else if (!GetIsAllocated() && !other_storage_ptr->GetIsAllocated()) { + // Both are inlined, thus element-wise swap up to smaller size, then move + // the remaining elements. + + Storage* small_ptr = this; + Storage* large_ptr = other_storage_ptr; + if (small_ptr->GetSize() > large_ptr->GetSize()) swap(small_ptr, large_ptr); + + for (size_type i = 0; i < small_ptr->GetSize(); ++i) { + swap(small_ptr->GetInlinedData()[i], large_ptr->GetInlinedData()[i]); + } + + IteratorValueAdapter move_values( + MoveIterator(large_ptr->GetInlinedData() + small_ptr->GetSize())); + + inlined_vector_internal::ConstructElements( + large_ptr->GetAllocPtr(), + small_ptr->GetInlinedData() + small_ptr->GetSize(), &move_values, + large_ptr->GetSize() - small_ptr->GetSize()); + + inlined_vector_internal::DestroyElements( + large_ptr->GetAllocPtr(), + large_ptr->GetInlinedData() + small_ptr->GetSize(), + large_ptr->GetSize() - small_ptr->GetSize()); + } else { + // One is allocated and the other is inlined, thus we first move the + // elements from the inlined instance to the inlined space in the allocated + // instance and then we can finish by having the other vector take on the + // allocation. + + Storage* allocated_ptr = this; + Storage* inlined_ptr = other_storage_ptr; + if (!allocated_ptr->GetIsAllocated()) swap(allocated_ptr, inlined_ptr); + + StorageView allocated_storage_view{allocated_ptr->GetAllocatedData(), + allocated_ptr->GetSize(), + allocated_ptr->GetAllocatedCapacity()}; + + IteratorValueAdapter move_values( + MoveIterator(inlined_ptr->GetInlinedData())); + + ABSL_INTERNAL_TRY { + inlined_vector_internal::ConstructElements( + inlined_ptr->GetAllocPtr(), allocated_ptr->GetInlinedData(), + &move_values, inlined_ptr->GetSize()); + } + ABSL_INTERNAL_CATCH_ANY { + // Writing to inlined data will trample on the existing state, thus it + // needs to be restored when a construction fails. + allocated_ptr->SetAllocatedData(allocated_storage_view.data, + allocated_storage_view.capacity); + ABSL_INTERNAL_RETHROW; + } + + inlined_vector_internal::DestroyElements(inlined_ptr->GetAllocPtr(), + inlined_ptr->GetInlinedData(), + inlined_ptr->GetSize()); + + inlined_ptr->SetAllocatedData(allocated_storage_view.data, + allocated_storage_view.capacity); + } + + // All cases swap the size, `is_allocated` boolean and the allocator. + swap(GetSizeAndIsAllocated(), other_storage_ptr->GetSizeAndIsAllocated()); + swap(*GetAllocPtr(), *other_storage_ptr->GetAllocPtr()); +} + } // namespace inlined_vector_internal } // namespace absl -- cgit v1.2.3