diff options
Diffstat (limited to 'third_party/abseil-cpp/absl/container/inlined_vector.h')
| -rw-r--r-- | third_party/abseil-cpp/absl/container/inlined_vector.h | 275 |
1 files changed, 141 insertions, 134 deletions
diff --git a/third_party/abseil-cpp/absl/container/inlined_vector.h b/third_party/abseil-cpp/absl/container/inlined_vector.h index 2388d471dc..df9e09917d 100644 --- a/third_party/abseil-cpp/absl/container/inlined_vector.h +++ b/third_party/abseil-cpp/absl/container/inlined_vector.h @@ -48,6 +48,7 @@ #include "absl/algorithm/algorithm.h" #include "absl/base/internal/throw_delegate.h" +#include "absl/base/macros.h" #include "absl/base/optimization.h" #include "absl/base/port.h" #include "absl/container/internal/inlined_vector.h" @@ -63,7 +64,7 @@ ABSL_NAMESPACE_BEGIN // `std::vector` for use cases where the vector's size is sufficiently small // that it can be inlined. If the inlined vector does grow beyond its estimated // capacity, it will trigger an initial allocation on the heap, and will behave -// as a `std:vector`. The API of the `absl::InlinedVector` within this file is +// as a `std::vector`. The API of the `absl::InlinedVector` within this file is // designed to cover the same API footprint as covered by `std::vector`. template <typename T, size_t N, typename A = std::allocator<T>> class InlinedVector { @@ -71,37 +72,43 @@ class InlinedVector { using Storage = inlined_vector_internal::Storage<T, N, A>; - using AllocatorTraits = typename Storage::AllocatorTraits; - using RValueReference = typename Storage::RValueReference; - using MoveIterator = typename Storage::MoveIterator; - using IsMemcpyOk = typename Storage::IsMemcpyOk; + template <typename TheA> + using AllocatorTraits = inlined_vector_internal::AllocatorTraits<TheA>; + template <typename TheA> + using MoveIterator = inlined_vector_internal::MoveIterator<TheA>; + template <typename TheA> + using IsMemcpyOk = inlined_vector_internal::IsMemcpyOk<TheA>; - template <typename Iterator> + template <typename TheA, typename Iterator> using IteratorValueAdapter = - typename Storage::template IteratorValueAdapter<Iterator>; - using CopyValueAdapter = typename Storage::CopyValueAdapter; - using DefaultValueAdapter = typename Storage::DefaultValueAdapter; + inlined_vector_internal::IteratorValueAdapter<TheA, Iterator>; + template <typename TheA> + using CopyValueAdapter = inlined_vector_internal::CopyValueAdapter<TheA>; + template <typename TheA> + using DefaultValueAdapter = + inlined_vector_internal::DefaultValueAdapter<TheA>; template <typename Iterator> using EnableIfAtLeastForwardIterator = absl::enable_if_t< - inlined_vector_internal::IsAtLeastForwardIterator<Iterator>::value>; + inlined_vector_internal::IsAtLeastForwardIterator<Iterator>::value, int>; template <typename Iterator> using DisableIfAtLeastForwardIterator = absl::enable_if_t< - !inlined_vector_internal::IsAtLeastForwardIterator<Iterator>::value>; + !inlined_vector_internal::IsAtLeastForwardIterator<Iterator>::value, int>; public: - using allocator_type = typename Storage::allocator_type; - using value_type = typename Storage::value_type; - using pointer = typename Storage::pointer; - using const_pointer = typename Storage::const_pointer; - using size_type = typename Storage::size_type; - using difference_type = typename Storage::difference_type; - using reference = typename Storage::reference; - using const_reference = typename Storage::const_reference; - using iterator = typename Storage::iterator; - using const_iterator = typename Storage::const_iterator; - using reverse_iterator = typename Storage::reverse_iterator; - using const_reverse_iterator = typename Storage::const_reverse_iterator; + using allocator_type = A; + using value_type = inlined_vector_internal::ValueType<A>; + using pointer = inlined_vector_internal::Pointer<A>; + using const_pointer = inlined_vector_internal::ConstPointer<A>; + using size_type = inlined_vector_internal::SizeType<A>; + using difference_type = inlined_vector_internal::DifferenceType<A>; + using reference = inlined_vector_internal::Reference<A>; + using const_reference = inlined_vector_internal::ConstReference<A>; + using iterator = inlined_vector_internal::Iterator<A>; + using const_iterator = inlined_vector_internal::ConstIterator<A>; + using reverse_iterator = inlined_vector_internal::ReverseIterator<A>; + using const_reverse_iterator = + inlined_vector_internal::ConstReverseIterator<A>; // --------------------------------------------------------------------------- // InlinedVector Constructors and Destructor @@ -110,28 +117,28 @@ class InlinedVector { // Creates an empty inlined vector with a value-initialized allocator. InlinedVector() noexcept(noexcept(allocator_type())) : storage_() {} - // Creates an empty inlined vector with a copy of `alloc`. - explicit InlinedVector(const allocator_type& alloc) noexcept - : storage_(alloc) {} + // Creates an empty inlined vector with a copy of `allocator`. + explicit InlinedVector(const allocator_type& allocator) noexcept + : storage_(allocator) {} // Creates an inlined vector with `n` copies of `value_type()`. explicit InlinedVector(size_type n, - const allocator_type& alloc = allocator_type()) - : storage_(alloc) { - storage_.Initialize(DefaultValueAdapter(), n); + const allocator_type& allocator = allocator_type()) + : storage_(allocator) { + storage_.Initialize(DefaultValueAdapter<A>(), n); } // Creates an inlined vector with `n` copies of `v`. InlinedVector(size_type n, const_reference v, - const allocator_type& alloc = allocator_type()) - : storage_(alloc) { - storage_.Initialize(CopyValueAdapter(v), n); + const allocator_type& allocator = allocator_type()) + : storage_(allocator) { + storage_.Initialize(CopyValueAdapter<A>(std::addressof(v)), n); } // Creates an inlined vector with copies of the elements of `list`. InlinedVector(std::initializer_list<value_type> list, - const allocator_type& alloc = allocator_type()) - : InlinedVector(list.begin(), list.end(), alloc) {} + const allocator_type& allocator = allocator_type()) + : InlinedVector(list.begin(), list.end(), allocator) {} // Creates an inlined vector with elements constructed from the provided // forward iterator range [`first`, `last`). @@ -140,37 +147,40 @@ class InlinedVector { // this constructor with two integral arguments and a call to the above // `InlinedVector(size_type, const_reference)` constructor. template <typename ForwardIterator, - EnableIfAtLeastForwardIterator<ForwardIterator>* = nullptr> + EnableIfAtLeastForwardIterator<ForwardIterator> = 0> InlinedVector(ForwardIterator first, ForwardIterator last, - const allocator_type& alloc = allocator_type()) - : storage_(alloc) { - storage_.Initialize(IteratorValueAdapter<ForwardIterator>(first), + const allocator_type& allocator = allocator_type()) + : storage_(allocator) { + storage_.Initialize(IteratorValueAdapter<A, ForwardIterator>(first), std::distance(first, last)); } // Creates an inlined vector with elements constructed from the provided input // iterator range [`first`, `last`). template <typename InputIterator, - DisableIfAtLeastForwardIterator<InputIterator>* = nullptr> + DisableIfAtLeastForwardIterator<InputIterator> = 0> InlinedVector(InputIterator first, InputIterator last, - const allocator_type& alloc = allocator_type()) - : storage_(alloc) { + const allocator_type& allocator = allocator_type()) + : storage_(allocator) { std::copy(first, last, std::back_inserter(*this)); } // Creates an inlined vector by copying the contents of `other` using // `other`'s allocator. InlinedVector(const InlinedVector& other) - : InlinedVector(other, *other.storage_.GetAllocPtr()) {} - - // Creates an inlined vector by copying the contents of `other` using `alloc`. - InlinedVector(const InlinedVector& other, const allocator_type& alloc) - : storage_(alloc) { - if (IsMemcpyOk::value && !other.storage_.GetIsAllocated()) { + : InlinedVector(other, other.storage_.GetAllocator()) {} + + // Creates an inlined vector by copying the contents of `other` using the + // provided `allocator`. + InlinedVector(const InlinedVector& other, const allocator_type& allocator) + : storage_(allocator) { + if (other.empty()) { + // Empty; nothing to do. + } else if (IsMemcpyOk<A>::value && !other.storage_.GetIsAllocated()) { + // Memcpy-able and do not need allocation. storage_.MemcpyFrom(other.storage_); } else { - storage_.Initialize(IteratorValueAdapter<const_pointer>(other.data()), - other.size()); + storage_.InitFrom(other.storage_); } } @@ -191,23 +201,23 @@ class InlinedVector { InlinedVector(InlinedVector&& other) noexcept( absl::allocator_is_nothrow<allocator_type>::value || std::is_nothrow_move_constructible<value_type>::value) - : storage_(*other.storage_.GetAllocPtr()) { - if (IsMemcpyOk::value) { + : storage_(other.storage_.GetAllocator()) { + if (IsMemcpyOk<A>::value) { storage_.MemcpyFrom(other.storage_); 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); } else { - IteratorValueAdapter<MoveIterator> other_values( - MoveIterator(other.storage_.GetInlinedData())); + IteratorValueAdapter<A, MoveIterator<A>> other_values( + MoveIterator<A>(other.storage_.GetInlinedData())); - inlined_vector_internal::ConstructElements( - storage_.GetAllocPtr(), storage_.GetInlinedData(), &other_values, + inlined_vector_internal::ConstructElements<A>( + storage_.GetAllocator(), storage_.GetInlinedData(), other_values, other.storage_.GetSize()); storage_.SetInlinedSize(other.storage_.GetSize()); @@ -215,30 +225,32 @@ class InlinedVector { } // Creates an inlined vector by moving in the contents of `other` with a copy - // of `alloc`. + // of `allocator`. // - // NOTE: if `other`'s allocator is not equal to `alloc`, even if `other` + // NOTE: if `other`'s allocator is not equal to `allocator`, even if `other` // contains allocated memory, this move constructor will still allocate. Since // allocation is performed, this constructor can only be `noexcept` if the // specified allocator is also `noexcept`. - InlinedVector(InlinedVector&& other, const allocator_type& alloc) noexcept( - absl::allocator_is_nothrow<allocator_type>::value) - : storage_(alloc) { - if (IsMemcpyOk::value) { + InlinedVector( + InlinedVector&& other, + const allocator_type& allocator) + noexcept(absl::allocator_is_nothrow<allocator_type>::value) + : storage_(allocator) { + if (IsMemcpyOk<A>::value) { storage_.MemcpyFrom(other.storage_); other.storage_.SetInlinedSize(0); - } else if ((*storage_.GetAllocPtr() == *other.storage_.GetAllocPtr()) && + } 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); } else { - storage_.Initialize( - IteratorValueAdapter<MoveIterator>(MoveIterator(other.data())), - other.size()); + storage_.Initialize(IteratorValueAdapter<A, MoveIterator<A>>( + MoveIterator<A>(other.data())), + other.size()); } } @@ -307,16 +319,14 @@ class InlinedVector { // // Returns a `reference` to the `i`th element of the inlined vector. reference operator[](size_type i) { - assert(i < size()); - + ABSL_HARDENING_ASSERT(i < size()); return data()[i]; } // Overload of `InlinedVector::operator[](...)` that returns a // `const_reference` to the `i`th element of the inlined vector. const_reference operator[](size_type i) const { - assert(i < size()); - + ABSL_HARDENING_ASSERT(i < size()); return data()[i]; } @@ -331,7 +341,6 @@ class InlinedVector { base_internal::ThrowStdOutOfRange( "`InlinedVector::at(size_type)` failed bounds check"); } - return data()[i]; } @@ -345,7 +354,6 @@ class InlinedVector { base_internal::ThrowStdOutOfRange( "`InlinedVector::at(size_type) const` failed bounds check"); } - return data()[i]; } @@ -353,34 +361,30 @@ class InlinedVector { // // Returns a `reference` to the first element of the inlined vector. reference front() { - assert(!empty()); - - return at(0); + ABSL_HARDENING_ASSERT(!empty()); + return data()[0]; } // Overload of `InlinedVector::front()` that returns a `const_reference` to // the first element of the inlined vector. const_reference front() const { - assert(!empty()); - - return at(0); + ABSL_HARDENING_ASSERT(!empty()); + return data()[0]; } // `InlinedVector::back()` // // Returns a `reference` to the last element of the inlined vector. reference back() { - assert(!empty()); - - return at(size() - 1); + ABSL_HARDENING_ASSERT(!empty()); + return data()[size() - 1]; } // Overload of `InlinedVector::back()` that returns a `const_reference` to the // last element of the inlined vector. const_reference back() const { - assert(!empty()); - - return at(size() - 1); + ABSL_HARDENING_ASSERT(!empty()); + return data()[size() - 1]; } // `InlinedVector::begin()` @@ -447,7 +451,7 @@ class InlinedVector { // `InlinedVector::get_allocator()` // // Returns a copy of the inlined vector's allocator. - allocator_type get_allocator() const { return *storage_.GetAllocPtr(); } + allocator_type get_allocator() const { return storage_.GetAllocator(); } // --------------------------------------------------------------------------- // InlinedVector Member Mutators @@ -481,16 +485,16 @@ class InlinedVector { // unspecified state. InlinedVector& operator=(InlinedVector&& other) { if (ABSL_PREDICT_TRUE(this != std::addressof(other))) { - if (IsMemcpyOk::value || other.storage_.GetIsAllocated()) { - inlined_vector_internal::DestroyElements(storage_.GetAllocPtr(), data(), - size()); + if (IsMemcpyOk<A>::value || other.storage_.GetIsAllocated()) { + inlined_vector_internal::DestroyElements<A>(storage_.GetAllocator(), + data(), size()); storage_.DeallocateIfAllocated(); storage_.MemcpyFrom(other.storage_); other.storage_.SetInlinedSize(0); } else { - storage_.Assign(IteratorValueAdapter<MoveIterator>( - MoveIterator(other.storage_.GetInlinedData())), + storage_.Assign(IteratorValueAdapter<A, MoveIterator<A>>( + MoveIterator<A>(other.storage_.GetInlinedData())), other.size()); } } @@ -502,7 +506,7 @@ class InlinedVector { // // Replaces the contents of the inlined vector with `n` copies of `v`. void assign(size_type n, const_reference v) { - storage_.Assign(CopyValueAdapter(v), n); + storage_.Assign(CopyValueAdapter<A>(std::addressof(v)), n); } // Overload of `InlinedVector::assign(...)` that replaces the contents of the @@ -516,9 +520,9 @@ class InlinedVector { // // NOTE: this overload is for iterators that are "forward" category or better. template <typename ForwardIterator, - EnableIfAtLeastForwardIterator<ForwardIterator>* = nullptr> + EnableIfAtLeastForwardIterator<ForwardIterator> = 0> void assign(ForwardIterator first, ForwardIterator last) { - storage_.Assign(IteratorValueAdapter<ForwardIterator>(first), + storage_.Assign(IteratorValueAdapter<A, ForwardIterator>(first), std::distance(first, last)); } @@ -527,11 +531,11 @@ class InlinedVector { // // NOTE: this overload is for iterators that are "input" category. template <typename InputIterator, - DisableIfAtLeastForwardIterator<InputIterator>* = nullptr> + DisableIfAtLeastForwardIterator<InputIterator> = 0> void assign(InputIterator first, InputIterator last) { size_type i = 0; for (; i < size() && first != last; ++i, static_cast<void>(++first)) { - at(i) = *first; + data()[i] = *first; } erase(data() + i, data() + size()); @@ -542,9 +546,12 @@ class InlinedVector { // // Resizes the inlined vector to contain `n` elements. // - // NOTE: if `n` is smaller than `size()`, extra elements are destroyed. If `n` + // NOTE: If `n` is smaller than `size()`, extra elements are destroyed. If `n` // is larger than `size()`, new elements are value-initialized. - void resize(size_type n) { storage_.Resize(DefaultValueAdapter(), n); } + void resize(size_type n) { + ABSL_HARDENING_ASSERT(n <= max_size()); + storage_.Resize(DefaultValueAdapter<A>(), n); + } // Overload of `InlinedVector::resize(...)` that resizes the inlined vector to // contain `n` elements. @@ -552,7 +559,8 @@ class InlinedVector { // NOTE: if `n` is smaller than `size()`, extra elements are destroyed. If `n` // is larger than `size()`, new elements are copied-constructed from `v`. void resize(size_type n, const_reference v) { - storage_.Resize(CopyValueAdapter(v), n); + ABSL_HARDENING_ASSERT(n <= max_size()); + storage_.Resize(CopyValueAdapter<A>(std::addressof(v)), n); } // `InlinedVector::insert(...)` @@ -565,7 +573,7 @@ class InlinedVector { // Overload of `InlinedVector::insert(...)` that inserts `v` at `pos` using // move semantics, returning an `iterator` to the newly inserted element. - iterator insert(const_iterator pos, RValueReference v) { + iterator insert(const_iterator pos, value_type&& v) { return emplace(pos, std::move(v)); } @@ -573,12 +581,13 @@ class InlinedVector { // of `v` starting at `pos`, returning an `iterator` pointing to the first of // the newly inserted elements. iterator insert(const_iterator pos, size_type n, const_reference v) { - assert(pos >= begin()); - assert(pos <= end()); + ABSL_HARDENING_ASSERT(pos >= begin()); + ABSL_HARDENING_ASSERT(pos <= end()); if (ABSL_PREDICT_TRUE(n != 0)) { value_type dealias = v; - return storage_.Insert(pos, CopyValueAdapter(dealias), n); + return storage_.Insert(pos, CopyValueAdapter<A>(std::addressof(dealias)), + n); } else { return const_cast<iterator>(pos); } @@ -597,14 +606,15 @@ class InlinedVector { // // NOTE: this overload is for iterators that are "forward" category or better. template <typename ForwardIterator, - EnableIfAtLeastForwardIterator<ForwardIterator>* = nullptr> + EnableIfAtLeastForwardIterator<ForwardIterator> = 0> iterator insert(const_iterator pos, ForwardIterator first, ForwardIterator last) { - assert(pos >= begin()); - assert(pos <= end()); + ABSL_HARDENING_ASSERT(pos >= begin()); + ABSL_HARDENING_ASSERT(pos <= end()); if (ABSL_PREDICT_TRUE(first != last)) { - return storage_.Insert(pos, IteratorValueAdapter<ForwardIterator>(first), + return storage_.Insert(pos, + IteratorValueAdapter<A, ForwardIterator>(first), std::distance(first, last)); } else { return const_cast<iterator>(pos); @@ -617,10 +627,10 @@ class InlinedVector { // // NOTE: this overload is for iterators that are "input" category. template <typename InputIterator, - DisableIfAtLeastForwardIterator<InputIterator>* = nullptr> + DisableIfAtLeastForwardIterator<InputIterator> = 0> iterator insert(const_iterator pos, InputIterator first, InputIterator last) { - assert(pos >= begin()); - assert(pos <= end()); + ABSL_HARDENING_ASSERT(pos >= begin()); + ABSL_HARDENING_ASSERT(pos <= end()); size_type index = std::distance(cbegin(), pos); for (size_type i = index; first != last; ++i, static_cast<void>(++first)) { @@ -636,13 +646,13 @@ class InlinedVector { // `pos`, returning an `iterator` pointing to the newly emplaced element. template <typename... Args> iterator emplace(const_iterator pos, Args&&... args) { - assert(pos >= begin()); - assert(pos <= end()); + ABSL_HARDENING_ASSERT(pos >= begin()); + ABSL_HARDENING_ASSERT(pos <= end()); value_type dealias(std::forward<Args>(args)...); return storage_.Insert(pos, - IteratorValueAdapter<MoveIterator>( - MoveIterator(std::addressof(dealias))), + IteratorValueAdapter<A, MoveIterator<A>>( + MoveIterator<A>(std::addressof(dealias))), 1); } @@ -662,7 +672,7 @@ class InlinedVector { // Overload of `InlinedVector::push_back(...)` for inserting `v` at `end()` // using move semantics. - void push_back(RValueReference v) { + void push_back(value_type&& v) { static_cast<void>(emplace_back(std::move(v))); } @@ -670,9 +680,9 @@ class InlinedVector { // // Destroys the element at `back()`, reducing the size by `1`. void pop_back() noexcept { - assert(!empty()); + ABSL_HARDENING_ASSERT(!empty()); - AllocatorTraits::destroy(*storage_.GetAllocPtr(), data() + (size() - 1)); + AllocatorTraits<A>::destroy(storage_.GetAllocator(), data() + (size() - 1)); storage_.SubtractSize(1); } @@ -683,8 +693,8 @@ class InlinedVector { // // NOTE: may return `end()`, which is not dereferencable. iterator erase(const_iterator pos) { - assert(pos >= begin()); - assert(pos < end()); + ABSL_HARDENING_ASSERT(pos >= begin()); + ABSL_HARDENING_ASSERT(pos < end()); return storage_.Erase(pos, pos + 1); } @@ -695,9 +705,9 @@ class InlinedVector { // // NOTE: may return `end()`, which is not dereferencable. iterator erase(const_iterator from, const_iterator to) { - assert(from >= begin()); - assert(from <= to); - assert(to <= end()); + ABSL_HARDENING_ASSERT(from >= begin()); + ABSL_HARDENING_ASSERT(from <= to); + ABSL_HARDENING_ASSERT(to <= end()); if (ABSL_PREDICT_TRUE(from != to)) { return storage_.Erase(from, to); @@ -711,8 +721,8 @@ class InlinedVector { // Destroys all elements in the inlined vector, setting the size to `0` and // deallocating any held memory. void clear() noexcept { - inlined_vector_internal::DestroyElements(storage_.GetAllocPtr(), data(), - size()); + inlined_vector_internal::DestroyElements<A>(storage_.GetAllocator(), data(), + size()); storage_.DeallocateIfAllocated(); storage_.SetInlinedSize(0); @@ -725,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())`. - // - // 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. + // 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 `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(); |