From 36d37ab992038f52276ca66b9da80c1cf0f57dc2 Mon Sep 17 00:00:00 2001 From: Abseil Team Date: Thu, 25 Jul 2019 04:03:57 -0700 Subject: Export of internal Abseil changes. -- 1224e58a45e4d016b18f5a6cf5762ba33027017a by CJ Johnson : Unifies the growth factor of InlinedVector's mutating members to max(2 * capacity, req_capacity). In doing so, LegacyNextCapacityFrom(...) is removed thus removing a loop from several callsites. PiperOrigin-RevId: 259920301 -- 945fc0bf27b67ea77d39144dcb6a483dc879ceda by Laramie Leavitt : Cleanup header guards which do not reflect the correct style. PiperOrigin-RevId: 259881520 -- 8c7d0532ba9a9aabfd57f67552572b2b1bedda97 by Derek Mauro : Move log_severity sources to the new log_severity target. PiperOrigin-RevId: 259837015 GitOrigin-RevId: 1224e58a45e4d016b18f5a6cf5762ba33027017a Change-Id: Id19506c3b8db71a0d4391ee917bfef3e802d550d --- absl/container/internal/inlined_vector.h | 89 +++++++++++++++++++------------- 1 file changed, 52 insertions(+), 37 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 7954b2b..b241d0e 100644 --- a/absl/container/internal/inlined_vector.h +++ b/absl/container/internal/inlined_vector.h @@ -15,6 +15,7 @@ #ifndef ABSL_CONTAINER_INTERNAL_INLINED_VECTOR_INTERNAL_H_ #define ABSL_CONTAINER_INTERNAL_INLINED_VECTOR_INTERNAL_H_ +#include #include #include #include @@ -301,15 +302,17 @@ class Storage { return data_.allocated.allocated_data; } + size_type GetInlinedCapacity() const { return static_cast(N); } + size_type GetAllocatedCapacity() const { return data_.allocated.allocated_capacity; } StorageView MakeStorageView() { - return GetIsAllocated() ? StorageView{GetAllocatedData(), GetSize(), - GetAllocatedCapacity()} - : StorageView{GetInlinedData(), GetSize(), - static_cast(N)}; + return GetIsAllocated() + ? StorageView{GetAllocatedData(), GetSize(), + GetAllocatedCapacity()} + : StorageView{GetInlinedData(), GetSize(), GetInlinedCapacity()}; } allocator_type* GetAllocPtr() { @@ -402,18 +405,13 @@ class Storage { return metadata_.template get<1>(); } - static size_type NextCapacityFrom(size_type current_capacity) { + static size_type NextCapacity(size_type current_capacity) { return current_capacity * 2; } - 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 ComputeCapacity(size_type current_capacity, + size_type requested_capacity) { + return (std::max)(NextCapacity(current_capacity), requested_capacity); } using Metadata = @@ -449,13 +447,17 @@ auto Storage::Initialize(ValueAdapter values, size_type new_size) pointer construct_data; - if (new_size > static_cast(N)) { + if (new_size > GetInlinedCapacity()) { // 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); + size_type new_capacity = ComputeCapacity(GetInlinedCapacity(), new_size); + pointer new_data = AllocatorTraits::allocate(*GetAllocPtr(), new_capacity); + + SetAllocatedData(new_data, new_capacity); SetIsAllocated(); + + construct_data = new_data; } else { construct_data = GetInlinedData(); } @@ -481,7 +483,10 @@ auto Storage::Assign(ValueAdapter values, size_type new_size) -> void { absl::Span destroy_loop; if (new_size > storage_view.capacity) { - construct_loop = {allocation_tx.Allocate(new_size), new_size}; + size_type new_capacity = ComputeCapacity(storage_view.capacity, new_size); + pointer new_data = allocation_tx.Allocate(new_capacity); + + construct_loop = {new_data, new_size}; destroy_loop = {storage_view.data, storage_view.size}; } else if (new_size > storage_view.size) { assign_loop = {storage_view.data, storage_view.size}; @@ -526,8 +531,8 @@ 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)); + size_type new_capacity = ComputeCapacity(storage_view.capacity, new_size); + pointer new_data = allocation_tx.Allocate(new_capacity); // Construct new objects in `new_data` construct_loop = {new_data + storage_view.size, @@ -586,8 +591,8 @@ auto Storage::Insert(const_iterator pos, ValueAdapter values, IteratorValueAdapter move_values( MoveIterator(storage_view.data)); - pointer new_data = allocation_tx.Allocate( - LegacyNextCapacityFrom(storage_view.capacity, new_size)); + size_type new_capacity = ComputeCapacity(storage_view.capacity, new_size); + pointer new_data = allocation_tx.Allocate(new_capacity); construction_tx.Construct(new_data + insert_index, &values, insert_count); @@ -670,14 +675,20 @@ auto Storage::EmplaceBack(Args&&... args) -> reference { 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 construct_data; - pointer last_ptr = construct_data + storage_view.size; - AllocatorTraits::construct(*GetAllocPtr(), last_ptr, - std::forward(args)...); + if (storage_view.size == storage_view.capacity) { + size_type new_capacity = NextCapacity(storage_view.capacity); + pointer new_data = allocation_tx.Allocate(new_capacity); + + construct_data = new_data; + } else { + construct_data = storage_view.data; + } + + pointer end = construct_data + storage_view.size; + + AllocatorTraits::construct(*GetAllocPtr(), end, std::forward(args)...); if (allocation_tx.DidAllocate()) { ABSL_INTERNAL_TRY { @@ -686,7 +697,7 @@ auto Storage::EmplaceBack(Args&&... args) -> reference { storage_view.size); } ABSL_INTERNAL_CATCH_ANY { - AllocatorTraits::destroy(*GetAllocPtr(), last_ptr); + AllocatorTraits::destroy(*GetAllocPtr(), end); ABSL_INTERNAL_RETHROW; } @@ -699,7 +710,7 @@ auto Storage::EmplaceBack(Args&&... args) -> reference { } AddSize(1); - return *last_ptr; + return *end; } template @@ -740,8 +751,9 @@ 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)); + size_type new_capacity = + ComputeCapacity(storage_view.capacity, requested_capacity); + pointer new_data = allocation_tx.Allocate(new_capacity); inlined_vector_internal::ConstructElements(GetAllocPtr(), new_data, &move_values, storage_view.size); @@ -762,6 +774,8 @@ auto Storage::ShrinkToFit() -> void { StorageView storage_view{GetAllocatedData(), GetSize(), GetAllocatedCapacity()}; + if (ABSL_PREDICT_FALSE(storage_view.size == storage_view.capacity)) return; + AllocationTransaction allocation_tx(GetAllocPtr()); IteratorValueAdapter move_values( @@ -769,12 +783,13 @@ auto Storage::ShrinkToFit() -> void { pointer construct_data; - if (storage_view.size <= static_cast(N)) { - construct_data = GetInlinedData(); - } else if (storage_view.size < GetAllocatedCapacity()) { - construct_data = allocation_tx.Allocate(storage_view.size); + if (storage_view.size > GetInlinedCapacity()) { + size_type new_capacity = storage_view.size; + pointer new_data = allocation_tx.Allocate(new_capacity); + + construct_data = new_data; } else { - return; + construct_data = GetInlinedData(); } ABSL_INTERNAL_TRY { -- cgit v1.2.3