summaryrefslogtreecommitdiff
path: root/absl/container/internal/inlined_vector.h
diff options
context:
space:
mode:
authorGravatar Abseil Team <absl-team@google.com>2019-06-24 18:35:20 -0700
committerGravatar Shaindel Schwartz <shaindel@google.com>2019-06-24 22:04:35 -0400
commitd65e19dfcd8697076f68598c0131c6930cdcd74d (patch)
treedbbfc92204c9c2f0bc950af9a8f2c26985d8654c /absl/container/internal/inlined_vector.h
parent5162fc83d2f3b79a9753ed59594c43966afdd37a (diff)
Export of internal Abseil changes.
-- 2f187776e55fe7741882d64aa4fb04d361dcd1da by Shaindel Schwartz <shaindel@google.com>: Fix spaces. PiperOrigin-RevId: 254880665 -- 50a2c390c1e56bec574e9418a6d0c5765f2e1d56 by CJ Johnson <johnsoncj@google.com>: Fixes a ubsan violation bug report: https://github.com/abseil/abseil-cpp/issues/337 PiperOrigin-RevId: 254846112 -- 563fee16ee0ac32a93292c3b2d1cf9543bad4758 by CJ Johnson <johnsoncj@google.com>: In the InlinedVector copy-assignment operator, substitutes-in a call to DeallocateIfAllocated() (which was not previously available) PiperOrigin-RevId: 254835012 -- d07f4d91b43242c5e8bd90f1e93f55f7972eed04 by Shaindel Schwartz <shaindel@google.com>: #336 PiperOrigin-RevId: 254833534 -- 1ad0fe00169a794176605a897f15fad8625339bd by Shaindel Schwartz <shaindel@google.com>: #335 PiperOrigin-RevId: 254826748 -- 436a29591c60c6ac9bb7b98e4906c0a7466611c1 by Shaindel Schwartz <shaindel@google.com>: Import of CCTZ from GitHub. PiperOrigin-RevId: 254820333 -- e782a5387a750319eb6ed5d9927ec2463bd68ebb by CJ Johnson <johnsoncj@google.com>: Updates the definition of InlinedVector::resize(...) to be exception safe and adds exception safety tests PiperOrigin-RevId: 254818993 -- 6d2f8538fb06a09af47232d86b32dfc020b62133 by CJ Johnson <johnsoncj@google.com>: Removes unnecessary transaction object from the implementation of InlinedVector::reserve(n) PiperOrigin-RevId: 254804166 -- 9a3a806702679a7442837089469cf171194da776 by Abseil Team <absl-team@google.com>: Internal Change. PiperOrigin-RevId: 254489023 -- ded1463ef81f3257645becc6be58df3b433ea21f by CJ Johnson <johnsoncj@google.com>: 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
Diffstat (limited to 'absl/container/internal/inlined_vector.h')
-rw-r--r--absl/container/internal/inlined_vector.h166
1 files changed, 156 insertions, 10 deletions
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 <typename AllocatorType, typename ValueType, typename SizeType>
void DestroyElements(AllocatorType* alloc_ptr, ValueType* destroy_first,
SizeType destroy_size) {
using AllocatorTraits = absl::allocator_traits<AllocatorType>;
- 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<void*>(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<void*>(destroy_first);
+ auto memory_size = sizeof(ValueType) * destroy_size;
+ std::memset(memory_ptr, 0xab, memory_size);
#endif // NDEBUG
+ }
}
template <typename AllocatorType, typename ValueType, typename ValueAdapter,
@@ -191,6 +195,46 @@ class AllocationTransaction {
size_type capacity_ = 0;
};
+template <typename AllocatorType>
+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 <typename ValueAdapter>
+ 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<AllocatorType, pointer> alloc_data_;
+ size_type size_ = 0;
+};
+
template <typename T, size_t N, typename A>
class Storage {
public:
@@ -223,6 +267,8 @@ class Storage {
using AllocationTransaction =
inlined_vector_internal::AllocationTransaction<allocator_type>;
+ using ConstructionTransaction =
+ inlined_vector_internal::ConstructionTransaction<allocator_type>;
Storage() : metadata_() {}
@@ -339,6 +385,11 @@ class Storage {
template <typename ValueAdapter>
void Assign(ValueAdapter values, size_type new_size);
+ template <typename ValueAdapter>
+ 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<allocator_type, size_type>;
@@ -434,11 +495,70 @@ auto Storage<T, N, A>::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 <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();
+
+ AllocationTransaction allocation_tx(GetAllocPtr());
+ ConstructionTransaction construction_tx(GetAllocPtr());
+
+ IteratorValueAdapter<MoveIterator> move_values(
+ MoveIterator(storage_view.data));
+
+ absl::Span<value_type> construct_loop;
+ absl::Span<value_type> move_construct_loop;
+ absl::Span<value_type> 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);
@@ -449,6 +569,31 @@ auto Storage<T, N, A>::Assign(ValueAdapter values, size_type new_size) -> void {
}
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));
+
+ 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 <typename T, size_t N, typename A>
auto Storage<T, N, A>::ShrinkToFit() -> void {
// May only be called on allocated instances!
assert(GetIsAllocated());
@@ -484,6 +629,7 @@ auto Storage<T, N, A>::ShrinkToFit() -> void {
inlined_vector_internal::DestroyElements(GetAllocPtr(), storage_view.data,
storage_view.size);
+
AllocatorTraits::deallocate(*GetAllocPtr(), storage_view.data,
storage_view.capacity);