| // Copyright 2019 The Abseil Authors. |
| // |
| // Licensed under the Apache License, Version 2.0 (the "License"); |
| // you may not use this file except in compliance with the License. |
| // You may obtain a copy of the License at |
| // |
| // https://www.apache.org/licenses/LICENSE-2.0 |
| // |
| // Unless required by applicable law or agreed to in writing, software |
| // distributed under the License is distributed on an "AS IS" BASIS, |
| // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| // See the License for the specific language governing permissions and |
| // limitations under the License. |
| |
| #ifndef ABSL_CONTAINER_INTERNAL_INLINED_VECTOR_INTERNAL_H_ |
| #define ABSL_CONTAINER_INTERNAL_INLINED_VECTOR_INTERNAL_H_ |
| |
| #include <algorithm> |
| #include <cstddef> |
| #include <cstring> |
| #include <iterator> |
| #include <limits> |
| #include <memory> |
| #include <utility> |
| |
| #include "absl/base/macros.h" |
| #include "absl/container/internal/compressed_tuple.h" |
| #include "absl/memory/memory.h" |
| #include "absl/meta/type_traits.h" |
| #include "absl/types/span.h" |
| |
| namespace absl { |
| ABSL_NAMESPACE_BEGIN |
| namespace inlined_vector_internal { |
| |
| // GCC does not deal very well with the below code |
| #if !defined(__clang__) && defined(__GNUC__) |
| #pragma GCC diagnostic push |
| #pragma GCC diagnostic ignored "-Wmaybe-uninitialized" |
| #endif |
| |
| template <typename Iterator> |
| using IsAtLeastForwardIterator = std::is_convertible< |
| typename std::iterator_traits<Iterator>::iterator_category, |
| std::forward_iterator_tag>; |
| |
| template <typename AllocatorType, |
| typename ValueType = |
| typename absl::allocator_traits<AllocatorType>::value_type> |
| using IsMemcpyOk = |
| absl::conjunction<std::is_same<AllocatorType, std::allocator<ValueType>>, |
| absl::is_trivially_copy_constructible<ValueType>, |
| absl::is_trivially_copy_assignable<ValueType>, |
| absl::is_trivially_destructible<ValueType>>; |
| |
| template <typename AllocatorType, typename Pointer, typename SizeType> |
| void DestroyElements(AllocatorType* alloc_ptr, Pointer destroy_first, |
| SizeType destroy_size) { |
| using AllocatorTraits = absl::allocator_traits<AllocatorType>; |
| |
| if (destroy_first != nullptr) { |
| for (auto i = destroy_size; i != 0;) { |
| --i; |
| AllocatorTraits::destroy(*alloc_ptr, destroy_first + i); |
| } |
| |
| #if !defined(NDEBUG) |
| { |
| using ValueType = typename AllocatorTraits::value_type; |
| |
| // 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_ptr = destroy_first; |
| auto memory_size = destroy_size * sizeof(ValueType); |
| std::memset(memory_ptr, 0xab, memory_size); |
| } |
| #endif // !defined(NDEBUG) |
| } |
| } |
| |
| // 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. |
| template <bool kUseMemcpy> |
| inline void MemcpyIfAllowed(void* dst, const void* src, size_t n); |
| |
| // memcpy when allowed. |
| template <> |
| inline void MemcpyIfAllowed<true>(void* dst, const void* src, size_t n) { |
| memcpy(dst, src, n); |
| } |
| |
| // Do nothing for types that are not memcpy-able. This function is only |
| // called from non-reachable branches. |
| template <> |
| inline void MemcpyIfAllowed<false>(void*, const void*, size_t) {} |
| |
| template <typename AllocatorType, typename Pointer, typename ValueAdapter, |
| typename SizeType> |
| void ConstructElements(AllocatorType* alloc_ptr, Pointer construct_first, |
| ValueAdapter* values_ptr, SizeType construct_size) { |
| 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 <typename Pointer, typename ValueAdapter, typename SizeType> |
| void AssignElements(Pointer assign_first, ValueAdapter* values_ptr, |
| SizeType assign_size) { |
| for (SizeType i = 0; i < assign_size; ++i) { |
| values_ptr->AssignNext(assign_first + i); |
| } |
| } |
| |
| template <typename AllocatorType> |
| struct StorageView { |
| using AllocatorTraits = absl::allocator_traits<AllocatorType>; |
| using Pointer = typename AllocatorTraits::pointer; |
| using SizeType = typename AllocatorTraits::size_type; |
| |
| Pointer data; |
| SizeType size; |
| SizeType capacity; |
| }; |
| |
| template <typename AllocatorType, typename Iterator> |
| class IteratorValueAdapter { |
| using AllocatorTraits = absl::allocator_traits<AllocatorType>; |
| using Pointer = typename AllocatorTraits::pointer; |
| |
| public: |
| explicit IteratorValueAdapter(const Iterator& it) : it_(it) {} |
| |
| void ConstructNext(AllocatorType* alloc_ptr, Pointer construct_at) { |
| AllocatorTraits::construct(*alloc_ptr, construct_at, *it_); |
| ++it_; |
| } |
| |
| void AssignNext(Pointer assign_at) { |
| *assign_at = *it_; |
| ++it_; |
| } |
| |
| private: |
| Iterator it_; |
| }; |
| |
| template <typename AllocatorType> |
| class CopyValueAdapter { |
| using AllocatorTraits = absl::allocator_traits<AllocatorType>; |
| using ValueType = typename AllocatorTraits::value_type; |
| using Pointer = typename AllocatorTraits::pointer; |
| using ConstPointer = typename AllocatorTraits::const_pointer; |
| |
| public: |
| explicit CopyValueAdapter(const ValueType& v) : ptr_(std::addressof(v)) {} |
| |
| void ConstructNext(AllocatorType* alloc_ptr, Pointer construct_at) { |
| AllocatorTraits::construct(*alloc_ptr, construct_at, *ptr_); |
| } |
| |
| void AssignNext(Pointer assign_at) { *assign_at = *ptr_; } |
| |
| private: |
| ConstPointer ptr_; |
| }; |
| |
| template <typename AllocatorType> |
| class DefaultValueAdapter { |
| using AllocatorTraits = absl::allocator_traits<AllocatorType>; |
| using ValueType = typename AllocatorTraits::value_type; |
| using Pointer = typename AllocatorTraits::pointer; |
| |
| public: |
| explicit DefaultValueAdapter() {} |
| |
| void ConstructNext(AllocatorType* alloc_ptr, Pointer construct_at) { |
| AllocatorTraits::construct(*alloc_ptr, construct_at); |
| } |
| |
| void AssignNext(Pointer assign_at) { *assign_at = ValueType(); } |
| }; |
| |
| template <typename AllocatorType> |
| class AllocationTransaction { |
| using AllocatorTraits = absl::allocator_traits<AllocatorType>; |
| using Pointer = typename AllocatorTraits::pointer; |
| using SizeType = typename AllocatorTraits::size_type; |
| |
| public: |
| explicit AllocationTransaction(AllocatorType* alloc_ptr) |
| : alloc_data_(*alloc_ptr, nullptr) {} |
| |
| ~AllocationTransaction() { |
| if (DidAllocate()) { |
| AllocatorTraits::deallocate(GetAllocator(), GetData(), GetCapacity()); |
| } |
| } |
| |
| AllocationTransaction(const AllocationTransaction&) = delete; |
| void operator=(const AllocationTransaction&) = delete; |
| |
| AllocatorType& GetAllocator() { return alloc_data_.template get<0>(); } |
| Pointer& GetData() { return alloc_data_.template get<1>(); } |
| SizeType& GetCapacity() { return capacity_; } |
| |
| bool DidAllocate() { return GetData() != nullptr; } |
| Pointer Allocate(SizeType capacity) { |
| GetData() = AllocatorTraits::allocate(GetAllocator(), capacity); |
| GetCapacity() = capacity; |
| return GetData(); |
| } |
| |
| void Reset() { |
| GetData() = nullptr; |
| GetCapacity() = 0; |
| } |
| |
| private: |
| container_internal::CompressedTuple<AllocatorType, Pointer> alloc_data_; |
| SizeType capacity_ = 0; |
| }; |
| |
| template <typename AllocatorType> |
| class ConstructionTransaction { |
| using AllocatorTraits = absl::allocator_traits<AllocatorType>; |
| using Pointer = typename AllocatorTraits::pointer; |
| using SizeType = typename AllocatorTraits::size_type; |
| |
| public: |
| explicit ConstructionTransaction(AllocatorType* alloc_ptr) |
| : alloc_data_(*alloc_ptr, nullptr) {} |
| |
| ~ConstructionTransaction() { |
| if (DidConstruct()) { |
| inlined_vector_internal::DestroyElements(std::addressof(GetAllocator()), |
| GetData(), GetSize()); |
| } |
| } |
| |
| ConstructionTransaction(const ConstructionTransaction&) = delete; |
| void operator=(const ConstructionTransaction&) = delete; |
| |
| AllocatorType& GetAllocator() { return alloc_data_.template get<0>(); } |
| Pointer& GetData() { return alloc_data_.template get<1>(); } |
| SizeType& GetSize() { return size_; } |
| |
| bool DidConstruct() { return GetData() != nullptr; } |
| template <typename ValueAdapter> |
| void Construct(Pointer data, ValueAdapter* values_ptr, SizeType size) { |
| inlined_vector_internal::ConstructElements(std::addressof(GetAllocator()), |
| data, values_ptr, size); |
| GetData() = data; |
| GetSize() = size; |
| } |
| void Commit() { |
| GetData() = nullptr; |
| GetSize() = 0; |
| } |
| |
| private: |
| container_internal::CompressedTuple<AllocatorType, Pointer> alloc_data_; |
| SizeType size_ = 0; |
| }; |
| |
| template <typename T, size_t N, typename A> |
| class Storage { |
| public: |
| using AllocatorTraits = absl::allocator_traits<A>; |
| using allocator_type = typename AllocatorTraits::allocator_type; |
| using value_type = typename AllocatorTraits::value_type; |
| using pointer = typename AllocatorTraits::pointer; |
| using const_pointer = typename AllocatorTraits::const_pointer; |
| using size_type = typename AllocatorTraits::size_type; |
| using difference_type = typename AllocatorTraits::difference_type; |
| |
| using reference = value_type&; |
| using const_reference = const value_type&; |
| using RValueReference = value_type&&; |
| using iterator = pointer; |
| using const_iterator = const_pointer; |
| using reverse_iterator = std::reverse_iterator<iterator>; |
| using const_reverse_iterator = std::reverse_iterator<const_iterator>; |
| using MoveIterator = std::move_iterator<iterator>; |
| using IsMemcpyOk = inlined_vector_internal::IsMemcpyOk<allocator_type>; |
| |
| using StorageView = inlined_vector_internal::StorageView<allocator_type>; |
| |
| template <typename Iterator> |
| using IteratorValueAdapter = |
| inlined_vector_internal::IteratorValueAdapter<allocator_type, Iterator>; |
| using CopyValueAdapter = |
| inlined_vector_internal::CopyValueAdapter<allocator_type>; |
| using DefaultValueAdapter = |
| inlined_vector_internal::DefaultValueAdapter<allocator_type>; |
| |
| using AllocationTransaction = |
| inlined_vector_internal::AllocationTransaction<allocator_type>; |
| using ConstructionTransaction = |
| inlined_vector_internal::ConstructionTransaction<allocator_type>; |
| |
| static size_type NextCapacity(size_type current_capacity) { |
| return current_capacity * 2; |
| } |
| |
| static size_type ComputeCapacity(size_type current_capacity, |
| size_type requested_capacity) { |
| return (std::max)(NextCapacity(current_capacity), requested_capacity); |
| } |
| |
| // --------------------------------------------------------------------------- |
| // Storage Constructors and Destructor |
| // --------------------------------------------------------------------------- |
| |
| Storage() : metadata_(allocator_type(), /* size and is_allocated */ 0) {} |
| |
| explicit Storage(const allocator_type& alloc) |
| : metadata_(alloc, /* size and is_allocated */ 0) {} |
| |
| ~Storage() { |
| if (GetSizeAndIsAllocated() == 0) { |
| // Empty and not allocated; nothing to do. |
| } else if (IsMemcpyOk::value) { |
| // No destructors need to be run; just deallocate if necessary. |
| DeallocateIfAllocated(); |
| } else { |
| DestroyContents(); |
| } |
| } |
| |
| // --------------------------------------------------------------------------- |
| // Storage Member Accessors |
| // --------------------------------------------------------------------------- |
| |
| size_type& GetSizeAndIsAllocated() { return metadata_.template get<1>(); } |
| |
| const size_type& GetSizeAndIsAllocated() const { |
| return metadata_.template get<1>(); |
| } |
| |
| size_type GetSize() const { return GetSizeAndIsAllocated() >> 1; } |
| |
| bool GetIsAllocated() const { return GetSizeAndIsAllocated() & 1; } |
| |
| pointer GetAllocatedData() { return data_.allocated.allocated_data; } |
| |
| const_pointer GetAllocatedData() const { |
| return data_.allocated.allocated_data; |
| } |
| |
| pointer GetInlinedData() { |
| return reinterpret_cast<pointer>( |
| std::addressof(data_.inlined.inlined_data[0])); |
| } |
| |
| const_pointer GetInlinedData() const { |
| return reinterpret_cast<const_pointer>( |
| std::addressof(data_.inlined.inlined_data[0])); |
| } |
| |
| size_type GetAllocatedCapacity() const { |
| return data_.allocated.allocated_capacity; |
| } |
| |
| size_type GetInlinedCapacity() const { return static_cast<size_type>(N); } |
| |
| StorageView MakeStorageView() { |
| return GetIsAllocated() |
| ? StorageView{GetAllocatedData(), GetSize(), |
| GetAllocatedCapacity()} |
| : StorageView{GetInlinedData(), GetSize(), GetInlinedCapacity()}; |
| } |
| |
| allocator_type* GetAllocPtr() { |
| return std::addressof(metadata_.template get<0>()); |
| } |
| |
| const allocator_type* GetAllocPtr() const { |
| return std::addressof(metadata_.template get<0>()); |
| } |
| |
| // --------------------------------------------------------------------------- |
| // Storage Member Mutators |
| // --------------------------------------------------------------------------- |
| |
| ABSL_ATTRIBUTE_NOINLINE void InitFrom(const Storage& other); |
| |
| template <typename ValueAdapter> |
| void Initialize(ValueAdapter values, size_type new_size); |
| |
| template <typename ValueAdapter> |
| void Assign(ValueAdapter values, size_type new_size); |
| |
| template <typename ValueAdapter> |
| void Resize(ValueAdapter values, size_type new_size); |
| |
| template <typename ValueAdapter> |
| iterator Insert(const_iterator pos, ValueAdapter values, |
| size_type insert_count); |
| |
| template <typename... Args> |
| 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); |
| |
| void SetIsAllocated() { |
| GetSizeAndIsAllocated() |= static_cast<size_type>(1); |
| } |
| |
| void UnsetIsAllocated() { |
| GetSizeAndIsAllocated() &= ((std::numeric_limits<size_type>::max)() - 1); |
| } |
| |
| void SetSize(size_type size) { |
| GetSizeAndIsAllocated() = |
| (size << 1) | static_cast<size_type>(GetIsAllocated()); |
| } |
| |
| void SetAllocatedSize(size_type size) { |
| GetSizeAndIsAllocated() = (size << 1) | static_cast<size_type>(1); |
| } |
| |
| void SetInlinedSize(size_type size) { |
| GetSizeAndIsAllocated() = size << static_cast<size_type>(1); |
| } |
| |
| void AddSize(size_type count) { |
| GetSizeAndIsAllocated() += count << static_cast<size_type>(1); |
| } |
| |
| void SubtractSize(size_type count) { |
| assert(count <= GetSize()); |
| |
| GetSizeAndIsAllocated() -= count << static_cast<size_type>(1); |
| } |
| |
| void SetAllocatedData(pointer data, size_type capacity) { |
| data_.allocated.allocated_data = data; |
| data_.allocated.allocated_capacity = capacity; |
| } |
| |
| void AcquireAllocatedData(AllocationTransaction* allocation_tx_ptr) { |
| SetAllocatedData(allocation_tx_ptr->GetData(), |
| allocation_tx_ptr->GetCapacity()); |
| |
| allocation_tx_ptr->Reset(); |
| } |
| |
| void MemcpyFrom(const Storage& other_storage) { |
| assert(IsMemcpyOk::value || other_storage.GetIsAllocated()); |
| |
| GetSizeAndIsAllocated() = other_storage.GetSizeAndIsAllocated(); |
| data_ = other_storage.data_; |
| } |
| |
| void DeallocateIfAllocated() { |
| if (GetIsAllocated()) { |
| AllocatorTraits::deallocate(*GetAllocPtr(), GetAllocatedData(), |
| GetAllocatedCapacity()); |
| } |
| } |
| |
| private: |
| ABSL_ATTRIBUTE_NOINLINE void DestroyContents(); |
| |
| using Metadata = |
| container_internal::CompressedTuple<allocator_type, size_type>; |
| |
| struct Allocated { |
| pointer allocated_data; |
| size_type allocated_capacity; |
| }; |
| |
| struct Inlined { |
| alignas(value_type) char inlined_data[sizeof(value_type[N])]; |
| }; |
| |
| union Data { |
| Allocated allocated; |
| Inlined inlined; |
| }; |
| |
| template <typename... Args> |
| ABSL_ATTRIBUTE_NOINLINE reference EmplaceBackSlow(Args&&... args); |
| |
| Metadata metadata_; |
| Data data_; |
| }; |
| |
| template <typename T, size_t N, typename A> |
| void Storage<T, N, A>::DestroyContents() { |
| pointer data = GetIsAllocated() ? GetAllocatedData() : GetInlinedData(); |
| inlined_vector_internal::DestroyElements(GetAllocPtr(), data, GetSize()); |
| DeallocateIfAllocated(); |
| } |
| |
| template <typename T, size_t N, typename A> |
| void Storage<T, N, A>::InitFrom(const Storage& other) { |
| const auto n = other.GetSize(); |
| assert(n > 0); // Empty sources handled handled in caller. |
| const_pointer src; |
| pointer dst; |
| if (!other.GetIsAllocated()) { |
| dst = GetInlinedData(); |
| src = other.GetInlinedData(); |
| } else { |
| // 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()`. |
| size_type new_capacity = ComputeCapacity(GetInlinedCapacity(), n); |
| dst = AllocatorTraits::allocate(*GetAllocPtr(), new_capacity); |
| SetAllocatedData(dst, new_capacity); |
| src = other.GetAllocatedData(); |
| } |
| if (IsMemcpyOk::value) { |
| MemcpyIfAllowed<IsMemcpyOk::value>(dst, src, sizeof(dst[0]) * n); |
| } else { |
| auto values = IteratorValueAdapter<const_pointer>(src); |
| inlined_vector_internal::ConstructElements(GetAllocPtr(), dst, &values, n); |
| } |
| GetSizeAndIsAllocated() = other.GetSizeAndIsAllocated(); |
| } |
| |
| template <typename T, size_t N, typename A> |
| template <typename ValueAdapter> |
| auto Storage<T, N, A>::Initialize(ValueAdapter values, size_type new_size) |
| -> void { |
| // Only callable from constructors! |
| assert(!GetIsAllocated()); |
| assert(GetSize() == 0); |
| |
| pointer construct_data; |
| 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()`. |
| size_type new_capacity = ComputeCapacity(GetInlinedCapacity(), new_size); |
| construct_data = AllocatorTraits::allocate(*GetAllocPtr(), new_capacity); |
| SetAllocatedData(construct_data, new_capacity); |
| 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); |
| } |
| |
| template <typename T, size_t N, typename A> |
| template <typename ValueAdapter> |
| auto Storage<T, N, A>::Assign(ValueAdapter values, size_type new_size) -> void { |
| StorageView storage_view = MakeStorageView(); |
| |
| AllocationTransaction allocation_tx(GetAllocPtr()); |
| |
| absl::Span<value_type> assign_loop; |
| absl::Span<value_type> construct_loop; |
| absl::Span<value_type> destroy_loop; |
| |
| if (new_size > storage_view.capacity) { |
| size_type new_capacity = ComputeCapacity(storage_view.capacity, new_size); |
| construct_loop = {allocation_tx.Allocate(new_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}; |
| construct_loop = {storage_view.data + storage_view.size, |
| new_size - storage_view.size}; |
| } else { |
| assign_loop = {storage_view.data, new_size}; |
| destroy_loop = {storage_view.data + new_size, storage_view.size - new_size}; |
| } |
| |
| 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(); |
| AcquireAllocatedData(&allocation_tx); |
| SetIsAllocated(); |
| } |
| |
| SetSize(new_size); |
| } |
| |
| template <typename T, size_t N, typename A> |
| template <typename ValueAdapter> |
| auto Storage<T, N, A>::Resize(ValueAdapter values, size_type new_size) -> void { |
| StorageView storage_view = MakeStorageView(); |
| auto* const base = storage_view.data; |
| const size_type size = storage_view.size; |
| auto* alloc = GetAllocPtr(); |
| if (new_size <= size) { |
| // Destroy extra old elements. |
| inlined_vector_internal::DestroyElements(alloc, base + new_size, |
| size - new_size); |
| } else if (new_size <= storage_view.capacity) { |
| // Construct new elements in place. |
| inlined_vector_internal::ConstructElements(alloc, base + size, &values, |
| new_size - size); |
| } else { |
| // Steps: |
| // a. Allocate new backing store. |
| // b. Construct new elements in new backing store. |
| // c. Move existing elements from old backing store to now. |
| // d. Destroy all elements in old backing store. |
| // Use transactional wrappers for the first two steps so we can roll |
| // back if necessary due to exceptions. |
| AllocationTransaction allocation_tx(alloc); |
| size_type new_capacity = ComputeCapacity(storage_view.capacity, new_size); |
| pointer new_data = allocation_tx.Allocate(new_capacity); |
| |
| ConstructionTransaction construction_tx(alloc); |
| construction_tx.Construct(new_data + size, &values, new_size - size); |
| |
| IteratorValueAdapter<MoveIterator> move_values((MoveIterator(base))); |
| inlined_vector_internal::ConstructElements(alloc, new_data, &move_values, |
| size); |
| |
| inlined_vector_internal::DestroyElements(alloc, base, size); |
| construction_tx.Commit(); |
| DeallocateIfAllocated(); |
| AcquireAllocatedData(&allocation_tx); |
| SetIsAllocated(); |
| } |
| SetSize(new_size); |
| } |
| |
| template <typename T, size_t N, typename A> |
| template <typename ValueAdapter> |
| auto Storage<T, N, A>::Insert(const_iterator pos, ValueAdapter values, |
| size_type insert_count) -> iterator { |
| StorageView storage_view = MakeStorageView(); |
| |
| size_type insert_index = |
| std::distance(const_iterator(storage_view.data), pos); |
| size_type insert_end_index = insert_index + insert_count; |
| size_type new_size = storage_view.size + insert_count; |
| |
| if (new_size > storage_view.capacity) { |
| AllocationTransaction allocation_tx(GetAllocPtr()); |
| ConstructionTransaction construction_tx(GetAllocPtr()); |
| ConstructionTransaction move_construciton_tx(GetAllocPtr()); |
| |
| IteratorValueAdapter<MoveIterator> move_values( |
| MoveIterator(storage_view.data)); |
| |
| 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); |
| |
| move_construciton_tx.Construct(new_data, &move_values, insert_index); |
| |
| inlined_vector_internal::ConstructElements( |
| GetAllocPtr(), new_data + insert_end_index, &move_values, |
| storage_view.size - insert_index); |
| |
| inlined_vector_internal::DestroyElements(GetAllocPtr(), storage_view.data, |
| storage_view.size); |
| |
| construction_tx.Commit(); |
| move_construciton_tx.Commit(); |
| DeallocateIfAllocated(); |
| AcquireAllocatedData(&allocation_tx); |
| |
| SetAllocatedSize(new_size); |
| return iterator(new_data + insert_index); |
| } else { |
| size_type move_construction_destination_index = |
| (std::max)(insert_end_index, storage_view.size); |
| |
| ConstructionTransaction move_construction_tx(GetAllocPtr()); |
| |
| IteratorValueAdapter<MoveIterator> move_construction_values( |
| MoveIterator(storage_view.data + |
| (move_construction_destination_index - insert_count))); |
| absl::Span<value_type> move_construction = { |
| storage_view.data + move_construction_destination_index, |
| new_size - move_construction_destination_index}; |
| |
| pointer move_assignment_values = storage_view.data + insert_index; |
| absl::Span<value_type> move_assignment = { |
| storage_view.data + insert_end_index, |
| move_construction_destination_index - insert_end_index}; |
| |
| absl::Span<value_type> insert_assignment = {move_assignment_values, |
| move_construction.size()}; |
| |
| absl::Span<value_type> insert_construction = { |
| insert_assignment.data() + insert_assignment.size(), |
| insert_count - insert_assignment.size()}; |
| |
| move_construction_tx.Construct(move_construction.data(), |
| &move_construction_values, |
| move_construction.size()); |
| |
| for (pointer destination = move_assignment.data() + move_assignment.size(), |
| last_destination = move_assignment.data(), |
| source = move_assignment_values + move_assignment.size(); |
| ;) { |
| --destination; |
| --source; |
| if (destination < last_destination) break; |
| *destination = std::move(*source); |
| } |
| |
| inlined_vector_internal::AssignElements(insert_assignment.data(), &values, |
| insert_assignment.size()); |
| |
| inlined_vector_internal::ConstructElements( |
| GetAllocPtr(), insert_construction.data(), &values, |
| insert_construction.size()); |
| |
| move_construction_tx.Commit(); |
| |
| AddSize(insert_count); |
| return iterator(storage_view.data + insert_index); |
| } |
| } |
| |
| template <typename T, size_t N, typename A> |
| template <typename... Args> |
| auto Storage<T, N, A>::EmplaceBack(Args&&... args) -> reference { |
| StorageView storage_view = MakeStorageView(); |
| const auto n = storage_view.size; |
| if (ABSL_PREDICT_TRUE(n != storage_view.capacity)) { |
| // Fast path; new element fits. |
| pointer last_ptr = storage_view.data + n; |
| AllocatorTraits::construct(*GetAllocPtr(), last_ptr, |
| std::forward<Args>(args)...); |
| AddSize(1); |
| return *last_ptr; |
| } |
| // TODO(b/173712035): Annotate with musttail attribute to prevent regression. |
| return EmplaceBackSlow(std::forward<Args>(args)...); |
| } |
| |
| template <typename T, size_t N, typename A> |
| template <typename... Args> |
| auto Storage<T, N, A>::EmplaceBackSlow(Args&&... args) -> reference { |
| StorageView storage_view = MakeStorageView(); |
| AllocationTransaction allocation_tx(GetAllocPtr()); |
| IteratorValueAdapter<MoveIterator> move_values( |
| MoveIterator(storage_view.data)); |
| size_type new_capacity = NextCapacity(storage_view.capacity); |
| pointer construct_data = allocation_tx.Allocate(new_capacity); |
| pointer last_ptr = construct_data + storage_view.size; |
| |
| // Construct new element. |
| AllocatorTraits::construct(*GetAllocPtr(), last_ptr, |
| std::forward<Args>(args)...); |
| // Move elements from old backing store to new backing store. |
| 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; |
| } |
| // Destroy elements in old backing store. |
| inlined_vector_internal::DestroyElements(GetAllocPtr(), storage_view.data, |
| storage_view.size); |
| |
| DeallocateIfAllocated(); |
| AcquireAllocatedData(&allocation_tx); |
| SetIsAllocated(); |
| AddSize(1); |
| return *last_ptr; |
| } |
| |
| template <typename T, size_t N, typename A> |
| auto Storage<T, N, A>::Erase(const_iterator from, const_iterator to) |
| -> iterator { |
| 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<MoveIterator> 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 <typename T, size_t N, typename A> |
| auto Storage<T, N, A>::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<MoveIterator> move_values( |
| MoveIterator(storage_view.data)); |
| |
| 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); |
| |
| inlined_vector_internal::DestroyElements(GetAllocPtr(), storage_view.data, |
| storage_view.size); |
| |
| DeallocateIfAllocated(); |
| AcquireAllocatedData(&allocation_tx); |
| SetIsAllocated(); |
| } |
| |
| template <typename T, size_t N, typename A> |
| auto Storage<T, N, A>::ShrinkToFit() -> void { |
| // May only be called on allocated instances! |
| assert(GetIsAllocated()); |
| |
| StorageView storage_view{GetAllocatedData(), GetSize(), |
| GetAllocatedCapacity()}; |
| |
| if (ABSL_PREDICT_FALSE(storage_view.size == storage_view.capacity)) return; |
| |
| AllocationTransaction allocation_tx(GetAllocPtr()); |
| |
| IteratorValueAdapter<MoveIterator> move_values( |
| MoveIterator(storage_view.data)); |
| |
| pointer construct_data; |
| if (storage_view.size > GetInlinedCapacity()) { |
| size_type new_capacity = storage_view.size; |
| construct_data = allocation_tx.Allocate(new_capacity); |
| } else { |
| construct_data = GetInlinedData(); |
| } |
| |
| ABSL_INTERNAL_TRY { |
| inlined_vector_internal::ConstructElements(GetAllocPtr(), construct_data, |
| &move_values, storage_view.size); |
| } |
| ABSL_INTERNAL_CATCH_ANY { |
| SetAllocatedData(storage_view.data, storage_view.capacity); |
| ABSL_INTERNAL_RETHROW; |
| } |
| |
| inlined_vector_internal::DestroyElements(GetAllocPtr(), storage_view.data, |
| storage_view.size); |
| |
| AllocatorTraits::deallocate(*GetAllocPtr(), storage_view.data, |
| storage_view.capacity); |
| |
| if (allocation_tx.DidAllocate()) { |
| AcquireAllocatedData(&allocation_tx); |
| } else { |
| UnsetIsAllocated(); |
| } |
| } |
| |
| template <typename T, size_t N, typename A> |
| auto Storage<T, N, A>::Swap(Storage* other_storage_ptr) -> void { |
| using std::swap; |
| assert(this != other_storage_ptr); |
| |
| if (GetIsAllocated() && other_storage_ptr->GetIsAllocated()) { |
| swap(data_.allocated, other_storage_ptr->data_.allocated); |
| } else if (!GetIsAllocated() && !other_storage_ptr->GetIsAllocated()) { |
| 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<MoveIterator> 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 { |
| 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<MoveIterator> 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 { |
| 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); |
| } |
| |
| swap(GetSizeAndIsAllocated(), other_storage_ptr->GetSizeAndIsAllocated()); |
| swap(*GetAllocPtr(), *other_storage_ptr->GetAllocPtr()); |
| } |
| |
| // End ignore "maybe-uninitialized" |
| #if !defined(__clang__) && defined(__GNUC__) |
| #pragma GCC diagnostic pop |
| #endif |
| |
| } // namespace inlined_vector_internal |
| ABSL_NAMESPACE_END |
| } // namespace absl |
| |
| #endif // ABSL_CONTAINER_INTERNAL_INLINED_VECTOR_INTERNAL_H_ |