From d65e19dfcd8697076f68598c0131c6930cdcd74d Mon Sep 17 00:00:00 2001 From: Abseil Team Date: Mon, 24 Jun 2019 18:35:20 -0700 Subject: Export of internal Abseil changes. -- 2f187776e55fe7741882d64aa4fb04d361dcd1da by Shaindel Schwartz : Fix spaces. PiperOrigin-RevId: 254880665 -- 50a2c390c1e56bec574e9418a6d0c5765f2e1d56 by CJ Johnson : Fixes a ubsan violation bug report: https://github.com/abseil/abseil-cpp/issues/337 PiperOrigin-RevId: 254846112 -- 563fee16ee0ac32a93292c3b2d1cf9543bad4758 by CJ Johnson : In the InlinedVector copy-assignment operator, substitutes-in a call to DeallocateIfAllocated() (which was not previously available) PiperOrigin-RevId: 254835012 -- d07f4d91b43242c5e8bd90f1e93f55f7972eed04 by Shaindel Schwartz : #336 PiperOrigin-RevId: 254833534 -- 1ad0fe00169a794176605a897f15fad8625339bd by Shaindel Schwartz : #335 PiperOrigin-RevId: 254826748 -- 436a29591c60c6ac9bb7b98e4906c0a7466611c1 by Shaindel Schwartz : Import of CCTZ from GitHub. PiperOrigin-RevId: 254820333 -- e782a5387a750319eb6ed5d9927ec2463bd68ebb by CJ Johnson : Updates the definition of InlinedVector::resize(...) to be exception safe and adds exception safety tests PiperOrigin-RevId: 254818993 -- 6d2f8538fb06a09af47232d86b32dfc020b62133 by CJ Johnson : Removes unnecessary transaction object from the implementation of InlinedVector::reserve(n) PiperOrigin-RevId: 254804166 -- 9a3a806702679a7442837089469cf171194da776 by Abseil Team : Internal Change. PiperOrigin-RevId: 254489023 -- ded1463ef81f3257645becc6be58df3b433ea21f by CJ Johnson : Updates the definition of InlinedVector::reserve(size_type) to be exception safe and adds exception safety tests PiperOrigin-RevId: 254463057 GitOrigin-RevId: 2f187776e55fe7741882d64aa4fb04d361dcd1da Change-Id: Id41fc5a62c8d71021e803721ecdbfb3ce60ef574 --- absl/container/internal/inlined_vector.h | 166 +++++++++++++++++++++++++++++-- 1 file changed, 156 insertions(+), 10 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 f117ee0c..a84b5255 100644 --- a/absl/container/internal/inlined_vector.h +++ b/absl/container/internal/inlined_vector.h @@ -47,19 +47,23 @@ template void DestroyElements(AllocatorType* alloc_ptr, ValueType* destroy_first, SizeType destroy_size) { using AllocatorTraits = absl::allocator_traits; - for (SizeType i = 0; i < destroy_size; ++i) { - AllocatorTraits::destroy(*alloc_ptr, destroy_first + i); - } + + if (destroy_first != nullptr) { + for (auto i = destroy_size; i != 0;) { + --i; + AllocatorTraits::destroy(*alloc_ptr, destroy_first + i); + } #ifndef NDEBUG - // Overwrite unused memory with `0xab` so we can catch uninitialized usage. - // - // Cast to `void*` to tell the compiler that we don't care that we might be - // scribbling on a vtable pointer. - void* memory = reinterpret_cast(destroy_first); - size_t memory_size = sizeof(ValueType) * destroy_size; - std::memset(memory, 0xab, memory_size); + // Overwrite unused memory with `0xab` so we can catch uninitialized usage. + // + // Cast to `void*` to tell the compiler that we don't care that we might be + // scribbling on a vtable pointer. + auto* memory_ptr = static_cast(destroy_first); + auto memory_size = sizeof(ValueType) * destroy_size; + std::memset(memory_ptr, 0xab, memory_size); #endif // NDEBUG + } } template +class ConstructionTransaction { + using pointer = typename AllocatorType::pointer; + using size_type = typename AllocatorType::size_type; + + public: + explicit ConstructionTransaction(AllocatorType* alloc_ptr) + : alloc_data_(*alloc_ptr, nullptr) {} + + ConstructionTransaction(const ConstructionTransaction&) = delete; + void operator=(const ConstructionTransaction&) = delete; + + template + void Construct(pointer data, ValueAdapter* values_ptr, size_type size) { + inlined_vector_internal::ConstructElements(std::addressof(GetAllocator()), + data, values_ptr, size); + GetData() = data; + GetSize() = size; + } + void Commit() { + GetData() = nullptr; + GetSize() = 0; + } + + ~ConstructionTransaction() { + if (GetData() != nullptr) { + inlined_vector_internal::DestroyElements(std::addressof(GetAllocator()), + GetData(), GetSize()); + } + } + + private: + AllocatorType& GetAllocator() { return alloc_data_.template get<0>(); } + pointer& GetData() { return alloc_data_.template get<1>(); } + size_type& GetSize() { return size_; } + + container_internal::CompressedTuple alloc_data_; + size_type size_ = 0; +}; + template class Storage { public: @@ -223,6 +267,8 @@ class Storage { using AllocationTransaction = inlined_vector_internal::AllocationTransaction; + using ConstructionTransaction = + inlined_vector_internal::ConstructionTransaction; Storage() : metadata_() {} @@ -339,6 +385,11 @@ class Storage { template void Assign(ValueAdapter values, size_type new_size); + template + void Resize(ValueAdapter values, size_type new_size); + + void Reserve(size_type requested_capacity); + void ShrinkToFit(); private: @@ -348,6 +399,16 @@ 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; + } + using Metadata = container_internal::CompressedTuple; @@ -434,11 +495,70 @@ auto Storage::Assign(ValueAdapter values, size_type new_size) -> void { inlined_vector_internal::AssignElements(assign_loop.data(), &values, assign_loop.size()); + inlined_vector_internal::ConstructElements( GetAllocPtr(), construct_loop.data(), &values, construct_loop.size()); + + inlined_vector_internal::DestroyElements(GetAllocPtr(), destroy_loop.data(), + destroy_loop.size()); + + if (allocation_tx.DidAllocate()) { + DeallocateIfAllocated(); + AcquireAllocation(&allocation_tx); + SetIsAllocated(); + } + + SetSize(new_size); +} + +template +template +auto Storage::Resize(ValueAdapter values, size_type new_size) -> void { + StorageView storage_view = MakeStorageView(); + + AllocationTransaction allocation_tx(GetAllocPtr()); + ConstructionTransaction construction_tx(GetAllocPtr()); + + IteratorValueAdapter move_values( + MoveIterator(storage_view.data)); + + absl::Span construct_loop; + absl::Span move_construct_loop; + absl::Span destroy_loop; + + if (new_size > storage_view.capacity) { + pointer new_data = allocation_tx.Allocate( + LegacyNextCapacityFrom(storage_view.capacity, new_size)); + + // Construct new objects in `new_data` + construct_loop = {new_data + storage_view.size, + new_size - storage_view.size}; + + // Move all existing objects into `new_data` + move_construct_loop = {new_data, storage_view.size}; + + // Destroy all existing objects in `storage_view.data` + destroy_loop = {storage_view.data, storage_view.size}; + } else if (new_size > storage_view.size) { + // Construct new objects in `storage_view.data` + construct_loop = {storage_view.data + storage_view.size, + new_size - storage_view.size}; + } else { + // Destroy end `storage_view.size - new_size` objects in `storage_view.data` + destroy_loop = {storage_view.data + new_size, storage_view.size - new_size}; + } + + construction_tx.Construct(construct_loop.data(), &values, + construct_loop.size()); + + inlined_vector_internal::ConstructElements( + GetAllocPtr(), move_construct_loop.data(), &move_values, + move_construct_loop.size()); + inlined_vector_internal::DestroyElements(GetAllocPtr(), destroy_loop.data(), destroy_loop.size()); + construction_tx.Commit(); if (allocation_tx.DidAllocate()) { DeallocateIfAllocated(); AcquireAllocation(&allocation_tx); @@ -448,6 +568,31 @@ auto Storage::Assign(ValueAdapter values, size_type new_size) -> void { SetSize(new_size); } +template +auto Storage::Reserve(size_type requested_capacity) -> void { + StorageView storage_view = MakeStorageView(); + + if (ABSL_PREDICT_FALSE(requested_capacity <= storage_view.capacity)) return; + + AllocationTransaction allocation_tx(GetAllocPtr()); + + IteratorValueAdapter move_values( + MoveIterator(storage_view.data)); + + pointer new_data = allocation_tx.Allocate( + LegacyNextCapacityFrom(storage_view.capacity, requested_capacity)); + + inlined_vector_internal::ConstructElements(GetAllocPtr(), new_data, + &move_values, storage_view.size); + + inlined_vector_internal::DestroyElements(GetAllocPtr(), storage_view.data, + storage_view.size); + + DeallocateIfAllocated(); + AcquireAllocation(&allocation_tx); + SetIsAllocated(); +} + template auto Storage::ShrinkToFit() -> void { // May only be called on allocated instances! @@ -484,6 +629,7 @@ auto Storage::ShrinkToFit() -> void { inlined_vector_internal::DestroyElements(GetAllocPtr(), storage_view.data, storage_view.size); + AllocatorTraits::deallocate(*GetAllocPtr(), storage_view.data, storage_view.capacity); -- cgit v1.2.3