From 020619c4aa68d13dfbdd6107a373912bb5ea85af Mon Sep 17 00:00:00 2001 From: Abseil Team Date: Wed, 22 Sep 2021 12:57:35 -0700 Subject: Export of internal Abseil changes -- 336f161ad8cb2cc3e1a6bbcbbb8c5b692ee59789 by Derek Mauro : Internal change PiperOrigin-RevId: 398308807 -- 80d512823d17561a45feca81f37713a91a175349 by Abseil Team : Internal change. PiperOrigin-RevId: 398257218 -- f1f9792000355eb1d0c11b17800048491662a218 by Abseil Team : Fix documentation for btree_multi{map,set}::merge to match behavior for elements with equivalent keys. PiperOrigin-RevId: 398071060 -- 8a9a302aebf2419e83f0c7dc5a63c33d26b807a3 by James Y Knight : Silence -Wunused-value warning newly emitted by ToT Clang. The value is being intentionally ignored, as the purpose of the call is only to eliminate this overload via SFINAE when `GenT{}` is not constant evaluable. PiperOrigin-RevId: 397861294 GitOrigin-RevId: 336f161ad8cb2cc3e1a6bbcbbb8c5b692ee59789 Change-Id: I946e1d22619f92ce6a424c8c13a20a50b39ed463 --- absl/container/btree_map.h | 5 +- absl/container/btree_set.h | 5 +- absl/container/inlined_vector.h | 21 +++-- absl/container/internal/inlined_vector.h | 135 ++++++++++++++++++++----------- 4 files changed, 100 insertions(+), 66 deletions(-) (limited to 'absl/container') diff --git a/absl/container/btree_map.h b/absl/container/btree_map.h index 6bbf414e..f0a8d4a6 100644 --- a/absl/container/btree_map.h +++ b/absl/container/btree_map.h @@ -693,9 +693,8 @@ class btree_multimap // btree_multimap::merge() // - // Extracts elements from a given `source` btree_multimap into this - // `btree_multimap`. If the destination `btree_multimap` already contains an - // element with an equivalent key, that element is not extracted. + // Extracts all elements from a given `source` btree_multimap into this + // `btree_multimap`. using Base::merge; // btree_multimap::swap(btree_multimap& other) diff --git a/absl/container/btree_set.h b/absl/container/btree_set.h index c07ccd91..89739006 100644 --- a/absl/container/btree_set.h +++ b/absl/container/btree_set.h @@ -604,9 +604,8 @@ class btree_multiset // btree_multiset::merge() // - // Extracts elements from a given `source` btree_multiset into this - // `btree_multiset`. If the destination `btree_multiset` already contains an - // element with an equivalent key, that element is not extracted. + // Extracts all elements from a given `source` btree_multiset into this + // `btree_multiset`. using Base::merge; // btree_multiset::swap(btree_multiset& other) diff --git a/absl/container/inlined_vector.h b/absl/container/inlined_vector.h index 37e5fef8..df9e0991 100644 --- a/absl/container/inlined_vector.h +++ b/absl/container/inlined_vector.h @@ -207,8 +207,8 @@ class InlinedVector { other.storage_.SetInlinedSize(0); } else if (other.storage_.GetIsAllocated()) { - storage_.SetAllocatedData(other.storage_.GetAllocatedData(), - other.storage_.GetAllocatedCapacity()); + storage_.SetAllocation({other.storage_.GetAllocatedData(), + other.storage_.GetAllocatedCapacity()}); storage_.SetAllocatedSize(other.storage_.GetSize()); other.storage_.SetInlinedSize(0); @@ -242,8 +242,8 @@ class InlinedVector { other.storage_.SetInlinedSize(0); } else if ((storage_.GetAllocator() == other.storage_.GetAllocator()) && other.storage_.GetIsAllocated()) { - storage_.SetAllocatedData(other.storage_.GetAllocatedData(), - other.storage_.GetAllocatedCapacity()); + storage_.SetAllocation({other.storage_.GetAllocatedData(), + other.storage_.GetAllocatedCapacity()}); storage_.SetAllocatedSize(other.storage_.GetSize()); other.storage_.SetInlinedSize(0); @@ -735,15 +735,12 @@ class InlinedVector { // `InlinedVector::shrink_to_fit()` // - // Reduces memory usage by freeing unused memory. After being called, calls to - // `capacity()` will be equal to `max(N, size())`. + // Attempts to reduce memory usage by moving elements to (or keeping elements + // in) the smallest available buffer sufficient for containing `size()` + // elements. // - // If `size() <= N` and the inlined vector contains allocated memory, the - // elements will all be moved to the inlined space and the allocated memory - // will be deallocated. - // - // If `size() > N` and `size() < capacity()`, the elements will be moved to a - // smaller allocation. + // If `size()` is sufficiently small, the elements will be moved into (or kept + // in) the inlined space. void shrink_to_fit() { if (storage_.GetIsAllocated()) { storage_.ShrinkToFit(); diff --git a/absl/container/internal/inlined_vector.h b/absl/container/internal/inlined_vector.h index 1cfba9b2..bb365b80 100644 --- a/absl/container/internal/inlined_vector.h +++ b/absl/container/internal/inlined_vector.h @@ -21,8 +21,11 @@ #include #include #include +#include +#include #include +#include "absl/base/attributes.h" #include "absl/base/macros.h" #include "absl/container/internal/compressed_tuple.h" #include "absl/memory/memory.h" @@ -102,6 +105,27 @@ void DestroyElements(NoTypeDeduction& allocator, Pointer destroy_first, } } +template +struct Allocation { + Pointer data; + SizeType capacity; +}; + +template ) > ABSL_INTERNAL_DEFAULT_NEW_ALIGNMENT)> +struct MallocAdapter { + static Allocation Allocate(A& allocator, SizeType requested_capacity) { + return {AllocatorTraits::allocate(allocator, requested_capacity), + requested_capacity}; + } + + static void Deallocate(A& allocator, Pointer pointer, + SizeType capacity) { + AllocatorTraits::deallocate(allocator, pointer, capacity); + } +}; + // If kUseMemcpy is true, memcpy(dst, src, n); else do nothing. // Useful to avoid compiler warnings when memcpy() is used for T values // that are not trivially copyable in non-reachable code. @@ -201,7 +225,7 @@ class AllocationTransaction { ~AllocationTransaction() { if (DidAllocate()) { - AllocatorTraits::deallocate(GetAllocator(), GetData(), GetCapacity()); + MallocAdapter::Deallocate(GetAllocator(), GetData(), GetCapacity()); } } @@ -213,18 +237,27 @@ class AllocationTransaction { SizeType& GetCapacity() { return capacity_; } bool DidAllocate() { return GetData() != nullptr; } - Pointer Allocate(SizeType capacity) { - GetData() = AllocatorTraits::allocate(GetAllocator(), capacity); - GetCapacity() = capacity; - return GetData(); + + Pointer Allocate(SizeType requested_capacity) { + Allocation result = + MallocAdapter::Allocate(GetAllocator(), requested_capacity); + GetData() = result.data; + GetCapacity() = result.capacity; + return result.data; + } + + ABSL_MUST_USE_RESULT Allocation Release() && { + Allocation result = {GetData(), GetCapacity()}; + Reset(); + return result; } + private: void Reset() { GetData() = nullptr; GetCapacity() = 0; } - private: container_internal::CompressedTuple> allocator_data_; SizeType capacity_; }; @@ -405,15 +438,9 @@ class Storage { GetSizeAndIsAllocated() -= count << static_cast>(1); } - void SetAllocatedData(Pointer data, SizeType capacity) { - data_.allocated.allocated_data = data; - data_.allocated.allocated_capacity = capacity; - } - - void AcquireAllocatedData(AllocationTransaction& allocation_tx) { - SetAllocatedData(allocation_tx.GetData(), allocation_tx.GetCapacity()); - - allocation_tx.Reset(); + void SetAllocation(Allocation allocation) { + data_.allocated.allocated_data = allocation.data; + data_.allocated.allocated_capacity = allocation.capacity; } void MemcpyFrom(const Storage& other_storage) { @@ -425,8 +452,8 @@ class Storage { void DeallocateIfAllocated() { if (GetIsAllocated()) { - AllocatorTraits::deallocate(GetAllocator(), GetAllocatedData(), - GetAllocatedCapacity()); + MallocAdapter::Deallocate(GetAllocator(), GetAllocatedData(), + GetAllocatedCapacity()); } } @@ -476,9 +503,11 @@ void Storage::InitFrom(const Storage& other) { // 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()`. - SizeType new_capacity = ComputeCapacity(GetInlinedCapacity(), n); - dst = AllocatorTraits::allocate(GetAllocator(), new_capacity); - SetAllocatedData(dst, new_capacity); + SizeType requested_capacity = ComputeCapacity(GetInlinedCapacity(), n); + Allocation allocation = + MallocAdapter::Allocate(GetAllocator(), requested_capacity); + SetAllocation(allocation); + dst = allocation.data; src = other.GetAllocatedData(); } if (IsMemcpyOk::value) { @@ -503,9 +532,12 @@ auto Storage::Initialize(ValueAdapter values, SizeType new_size) // 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()`. - SizeType new_capacity = ComputeCapacity(GetInlinedCapacity(), new_size); - construct_data = AllocatorTraits::allocate(GetAllocator(), new_capacity); - SetAllocatedData(construct_data, new_capacity); + SizeType requested_capacity = + ComputeCapacity(GetInlinedCapacity(), new_size); + Allocation allocation = + MallocAdapter::Allocate(GetAllocator(), requested_capacity); + construct_data = allocation.data; + SetAllocation(allocation); SetIsAllocated(); } else { construct_data = GetInlinedData(); @@ -532,8 +564,9 @@ auto Storage::Assign(ValueAdapter values, SizeType new_size) absl::Span> destroy_loop; if (new_size > storage_view.capacity) { - SizeType new_capacity = ComputeCapacity(storage_view.capacity, new_size); - construct_loop = {allocation_tx.Allocate(new_capacity), new_size}; + SizeType requested_capacity = + ComputeCapacity(storage_view.capacity, new_size); + construct_loop = {allocation_tx.Allocate(requested_capacity), 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}; @@ -553,7 +586,7 @@ auto Storage::Assign(ValueAdapter values, SizeType new_size) if (allocation_tx.DidAllocate()) { DeallocateIfAllocated(); - AcquireAllocatedData(allocation_tx); + SetAllocation(std::move(allocation_tx).Release()); SetIsAllocated(); } @@ -583,8 +616,9 @@ auto Storage::Resize(ValueAdapter values, SizeType new_size) // Use transactional wrappers for the first two steps so we can roll // back if necessary due to exceptions. AllocationTransaction allocation_tx(alloc); - SizeType new_capacity = ComputeCapacity(storage_view.capacity, new_size); - Pointer new_data = allocation_tx.Allocate(new_capacity); + SizeType requested_capacity = + ComputeCapacity(storage_view.capacity, new_size); + Pointer new_data = allocation_tx.Allocate(requested_capacity); ConstructionTransaction construction_tx(alloc); construction_tx.Construct(new_data + size, values, new_size - size); @@ -596,7 +630,7 @@ auto Storage::Resize(ValueAdapter values, SizeType new_size) DestroyElements(alloc, base, size); construction_tx.Commit(); DeallocateIfAllocated(); - AcquireAllocatedData(allocation_tx); + SetAllocation(std::move(allocation_tx).Release()); SetIsAllocated(); } SetSize(new_size); @@ -621,8 +655,9 @@ auto Storage::Insert(ConstIterator pos, ValueAdapter values, IteratorValueAdapter> move_values( MoveIterator(storage_view.data)); - SizeType new_capacity = ComputeCapacity(storage_view.capacity, new_size); - Pointer new_data = allocation_tx.Allocate(new_capacity); + SizeType requested_capacity = + ComputeCapacity(storage_view.capacity, new_size); + Pointer new_data = allocation_tx.Allocate(requested_capacity); construction_tx.Construct(new_data + insert_index, values, insert_count); @@ -636,7 +671,7 @@ auto Storage::Insert(ConstIterator pos, ValueAdapter values, construction_tx.Commit(); move_construction_tx.Commit(); DeallocateIfAllocated(); - AcquireAllocatedData(allocation_tx); + SetAllocation(std::move(allocation_tx).Release()); SetAllocatedSize(new_size); return Iterator(new_data + insert_index); @@ -717,8 +752,8 @@ auto Storage::EmplaceBackSlow(Args&&... args) -> Reference { AllocationTransaction allocation_tx(GetAllocator()); IteratorValueAdapter> move_values( MoveIterator(storage_view.data)); - SizeType new_capacity = NextCapacity(storage_view.capacity); - Pointer construct_data = allocation_tx.Allocate(new_capacity); + SizeType requested_capacity = NextCapacity(storage_view.capacity); + Pointer construct_data = allocation_tx.Allocate(requested_capacity); Pointer last_ptr = construct_data + storage_view.size; // Construct new element. @@ -737,7 +772,7 @@ auto Storage::EmplaceBackSlow(Args&&... args) -> Reference { DestroyElements(GetAllocator(), storage_view.data, storage_view.size); DeallocateIfAllocated(); - AcquireAllocatedData(allocation_tx); + SetAllocation(std::move(allocation_tx).Release()); SetIsAllocated(); AddSize(1); return *last_ptr; @@ -778,9 +813,9 @@ auto Storage::Reserve(SizeType requested_capacity) -> void { IteratorValueAdapter> move_values( MoveIterator(storage_view.data)); - SizeType new_capacity = + SizeType new_requested_capacity = ComputeCapacity(storage_view.capacity, requested_capacity); - Pointer new_data = allocation_tx.Allocate(new_capacity); + Pointer new_data = allocation_tx.Allocate(new_requested_capacity); ConstructElements(GetAllocator(), new_data, move_values, storage_view.size); @@ -788,7 +823,7 @@ auto Storage::Reserve(SizeType requested_capacity) -> void { DestroyElements(GetAllocator(), storage_view.data, storage_view.size); DeallocateIfAllocated(); - AcquireAllocatedData(allocation_tx); + SetAllocation(std::move(allocation_tx).Release()); SetIsAllocated(); } @@ -809,8 +844,12 @@ auto Storage::ShrinkToFit() -> void { Pointer construct_data; if (storage_view.size > GetInlinedCapacity()) { - SizeType new_capacity = storage_view.size; - construct_data = allocation_tx.Allocate(new_capacity); + SizeType requested_capacity = storage_view.size; + construct_data = allocation_tx.Allocate(requested_capacity); + if (allocation_tx.GetCapacity() >= storage_view.capacity) { + // Already using the smallest available heap allocation. + return; + } } else { construct_data = GetInlinedData(); } @@ -820,17 +859,17 @@ auto Storage::ShrinkToFit() -> void { storage_view.size); } ABSL_INTERNAL_CATCH_ANY { - SetAllocatedData(storage_view.data, storage_view.capacity); + SetAllocation({storage_view.data, storage_view.capacity}); ABSL_INTERNAL_RETHROW; } DestroyElements(GetAllocator(), storage_view.data, storage_view.size); - AllocatorTraits::deallocate(GetAllocator(), storage_view.data, - storage_view.capacity); + MallocAdapter::Deallocate(GetAllocator(), storage_view.data, + storage_view.capacity); if (allocation_tx.DidAllocate()) { - AcquireAllocatedData(allocation_tx); + SetAllocation(std::move(allocation_tx).Release()); } else { UnsetIsAllocated(); } @@ -881,16 +920,16 @@ auto Storage::Swap(Storage* other_storage_ptr) -> void { inlined_ptr->GetSize()); } ABSL_INTERNAL_CATCH_ANY { - allocated_ptr->SetAllocatedData(allocated_storage_view.data, - allocated_storage_view.capacity); + allocated_ptr->SetAllocation( + {allocated_storage_view.data, allocated_storage_view.capacity}); ABSL_INTERNAL_RETHROW; } DestroyElements(inlined_ptr->GetAllocator(), inlined_ptr->GetInlinedData(), inlined_ptr->GetSize()); - inlined_ptr->SetAllocatedData(allocated_storage_view.data, - allocated_storage_view.capacity); + inlined_ptr->SetAllocation( + {allocated_storage_view.data, allocated_storage_view.capacity}); } swap(GetSizeAndIsAllocated(), other_storage_ptr->GetSizeAndIsAllocated()); -- cgit v1.2.3