diff options
Diffstat (limited to 'absl/container/inlined_vector.h')
| -rw-r--r-- | absl/container/inlined_vector.h | 1504 |
1 files changed, 451 insertions, 1053 deletions
diff --git a/absl/container/inlined_vector.h b/absl/container/inlined_vector.h index 37714baf..27186b15 100644 --- a/absl/container/inlined_vector.h +++ b/absl/container/inlined_vector.h @@ -1,10 +1,10 @@ -// Copyright 2018 The Abseil Authors. +// 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 // -// http://www.apache.org/licenses/LICENSE-2.0 +// 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, @@ -50,11 +50,11 @@ #include "absl/base/internal/throw_delegate.h" #include "absl/base/optimization.h" #include "absl/base/port.h" +#include "absl/container/internal/inlined_vector.h" #include "absl/memory/memory.h" namespace absl { -inline namespace lts_2018_12_18 { - +inline namespace lts_2019_08_08 { // ----------------------------------------------------------------------------- // InlinedVector // ----------------------------------------------------------------------------- @@ -67,119 +67,181 @@ inline namespace lts_2018_12_18 { // 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 { - static_assert(N > 0, "InlinedVector requires inline capacity greater than 0"); - constexpr static typename A::size_type inlined_capacity() { - return static_cast<typename A::size_type>(N); - } + static_assert(N > 0, "`absl::InlinedVector` requires an inlined capacity."); - template <typename Iterator> - using DisableIfIntegral = - absl::enable_if_t<!std::is_integral<Iterator>::value>; + using Storage = inlined_vector_internal::Storage<T, N, A>; + using rvalue_reference = typename Storage::rvalue_reference; + using MoveIterator = typename Storage::MoveIterator; + using AllocatorTraits = typename Storage::AllocatorTraits; + using IsMemcpyOk = typename Storage::IsMemcpyOk; template <typename Iterator> - using EnableIfInputIterator = absl::enable_if_t<std::is_convertible< - typename std::iterator_traits<Iterator>::iterator_category, - std::input_iterator_tag>::value>; + using IteratorValueAdapter = + typename Storage::template IteratorValueAdapter<Iterator>; + using CopyValueAdapter = typename Storage::CopyValueAdapter; + using DefaultValueAdapter = typename Storage::DefaultValueAdapter; template <typename Iterator> - using IteratorCategory = - typename std::iterator_traits<Iterator>::iterator_category; - - using rvalue_reference = typename A::value_type&&; + using EnableIfAtLeastForwardIterator = absl::enable_if_t< + inlined_vector_internal::IsAtLeastForwardIterator<Iterator>::value>; + template <typename Iterator> + using DisableIfAtLeastForwardIterator = absl::enable_if_t< + !inlined_vector_internal::IsAtLeastForwardIterator<Iterator>::value>; public: - using allocator_type = A; - using value_type = typename allocator_type::value_type; - using pointer = typename allocator_type::pointer; - using const_pointer = typename allocator_type::const_pointer; - using reference = typename allocator_type::reference; - using const_reference = typename allocator_type::const_reference; - using size_type = typename allocator_type::size_type; - using difference_type = typename allocator_type::difference_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 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 reference = typename Storage::reference; + using const_reference = typename Storage::const_reference; + using size_type = typename Storage::size_type; + using difference_type = typename Storage::difference_type; + 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; // --------------------------------------------------------------------------- // InlinedVector Constructors and Destructor // --------------------------------------------------------------------------- - // Creates an empty inlined vector with a default initialized allocator. - InlinedVector() noexcept(noexcept(allocator_type())) - : allocator_and_tag_(allocator_type()) {} + // Creates an empty inlined vector with a value-initialized allocator. + InlinedVector() noexcept(noexcept(allocator_type())) : storage_() {} - // Creates an empty inlined vector with a specified allocator. + // Creates an empty inlined vector with a copy of `alloc`. explicit InlinedVector(const allocator_type& alloc) noexcept - : allocator_and_tag_(alloc) {} + : storage_(alloc) {} // Creates an inlined vector with `n` copies of `value_type()`. explicit InlinedVector(size_type n, const allocator_type& alloc = allocator_type()) - : allocator_and_tag_(alloc) { - InitAssign(n); + : storage_(alloc) { + storage_.Initialize(DefaultValueAdapter(), n); } // Creates an inlined vector with `n` copies of `v`. InlinedVector(size_type n, const_reference v, const allocator_type& alloc = allocator_type()) - : allocator_and_tag_(alloc) { - InitAssign(n, v); + : storage_(alloc) { + storage_.Initialize(CopyValueAdapter(v), n); } - // Creates an inlined vector of copies of the values in `init_list`. - InlinedVector(std::initializer_list<value_type> init_list, + // Creates an inlined vector with copies of the elements of `list`. + InlinedVector(std::initializer_list<value_type> list, const allocator_type& alloc = allocator_type()) - : allocator_and_tag_(alloc) { - AppendRange(init_list.begin(), init_list.end(), - IteratorCategory<decltype(init_list.begin())>{}); - } + : InlinedVector(list.begin(), list.end(), alloc) {} // Creates an inlined vector with elements constructed from the provided - // Iterator range [`first`, `last`). + // forward iterator range [`first`, `last`). // - // NOTE: The `enable_if` prevents ambiguous interpretation between a call to + // NOTE: the `enable_if` prevents ambiguous interpretation between a call to // this constructor with two integral arguments and a call to the above // `InlinedVector(size_type, const_reference)` constructor. - template <typename InputIterator, DisableIfIntegral<InputIterator>* = nullptr> + template <typename ForwardIterator, + EnableIfAtLeastForwardIterator<ForwardIterator>* = nullptr> + InlinedVector(ForwardIterator first, ForwardIterator last, + const allocator_type& alloc = allocator_type()) + : storage_(alloc) { + storage_.Initialize(IteratorValueAdapter<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> InlinedVector(InputIterator first, InputIterator last, const allocator_type& alloc = allocator_type()) - : allocator_and_tag_(alloc) { - AppendRange(first, last, IteratorCategory<InputIterator>{}); + : storage_(alloc) { + std::copy(first, last, std::back_inserter(*this)); } - // Creates a copy of `other` using `other`'s allocator. - InlinedVector(const InlinedVector& other); + // Creates an inlined vector by copying the contents of `other` using + // `other`'s allocator. + InlinedVector(const InlinedVector& other) + : InlinedVector(other, *other.storage_.GetAllocPtr()) {} - // Creates a copy of `other` but with a specified allocator. - InlinedVector(const InlinedVector& other, const allocator_type& alloc); + // 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()) { + storage_.MemcpyFrom(other.storage_); + } else { + storage_.Initialize(IteratorValueAdapter<const_pointer>(other.data()), + other.size()); + } + } - // Creates an inlined vector by moving in the contents of `other`. + // Creates an inlined vector by moving in the contents of `other` without + // allocating. If `other` contains allocated memory, the newly-created inlined + // vector will take ownership of that memory. However, if `other` does not + // contain allocated memory, the newly-created inlined vector will perform + // element-wise move construction of the contents of `other`. // - // NOTE: This move constructor does not allocate and only moves the underlying - // objects, so its `noexcept` specification depends on whether moving the - // underlying objects can throw or not. We assume: - // a) move constructors should only throw due to allocation failure and + // NOTE: since no allocation is performed for the inlined vector in either + // case, the `noexcept(...)` specification depends on whether moving the + // underlying objects can throw. It is assumed assumed that... + // a) move constructors should only throw due to allocation failure. // b) if `value_type`'s move constructor allocates, it uses the same - // allocation function as the `InlinedVector`'s allocator, so the move - // constructor is non-throwing if the allocator is non-throwing or - // `value_type`'s move constructor is specified as `noexcept`. - InlinedVector(InlinedVector&& v) noexcept( + // allocation function as the inlined vector's allocator. + // Thus, the move constructor is non-throwing if the allocator is non-throwing + // or `value_type`'s move constructor is specified as `noexcept`. + InlinedVector(InlinedVector&& other) noexcept( absl::allocator_is_nothrow<allocator_type>::value || - std::is_nothrow_move_constructible<value_type>::value); + std::is_nothrow_move_constructible<value_type>::value) + : storage_(*other.storage_.GetAllocPtr()) { + if (IsMemcpyOk::value) { + storage_.MemcpyFrom(other.storage_); + + other.storage_.SetInlinedSize(0); + } else if (other.storage_.GetIsAllocated()) { + storage_.SetAllocatedData(other.storage_.GetAllocatedData(), + other.storage_.GetAllocatedCapacity()); + storage_.SetAllocatedSize(other.storage_.GetSize()); + + other.storage_.SetInlinedSize(0); + } else { + IteratorValueAdapter<MoveIterator> other_values( + MoveIterator(other.storage_.GetInlinedData())); + + inlined_vector_internal::ConstructElements( + storage_.GetAllocPtr(), storage_.GetInlinedData(), &other_values, + other.storage_.GetSize()); - // Creates an inlined vector by moving in the contents of `other`. + storage_.SetInlinedSize(other.storage_.GetSize()); + } + } + + // Creates an inlined vector by moving in the contents of `other` with a copy + // of `alloc`. // - // NOTE: This move constructor allocates and subsequently moves the underlying - // objects, so its `noexcept` specification depends on whether the allocation - // can throw and whether moving the underlying objects can throw. Based on the - // same assumptions as above, the `noexcept` specification is dominated by - // whether the allocation can throw regardless of whether `value_type`'s move - // constructor is specified as `noexcept`. - InlinedVector(InlinedVector&& v, const allocator_type& alloc) noexcept( - absl::allocator_is_nothrow<allocator_type>::value); + // NOTE: if `other`'s allocator is not equal to `alloc`, 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) { + storage_.MemcpyFrom(other.storage_); + + other.storage_.SetInlinedSize(0); + } else if ((*storage_.GetAllocPtr() == *other.storage_.GetAllocPtr()) && + other.storage_.GetIsAllocated()) { + storage_.SetAllocatedData(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()); + } + } - ~InlinedVector() { clear(); } + ~InlinedVector() {} // --------------------------------------------------------------------------- // InlinedVector Member Accessors @@ -187,87 +249,102 @@ class InlinedVector { // `InlinedVector::empty()` // - // Checks if the inlined vector has no elements. + // Returns whether the inlined vector contains no elements. bool empty() const noexcept { return !size(); } // `InlinedVector::size()` // // Returns the number of elements in the inlined vector. - size_type size() const noexcept { return tag().size(); } + size_type size() const noexcept { return storage_.GetSize(); } // `InlinedVector::max_size()` // - // Returns the maximum number of elements the vector can hold. + // Returns the maximum number of elements the inlined vector can hold. size_type max_size() const noexcept { // One bit of the size storage is used to indicate whether the inlined - // vector is allocated. As a result, the maximum size of the container that - // we can express is half of the max for `size_type`. + // vector contains allocated memory. As a result, the maximum size that the + // inlined vector can express is half of the max for `size_type`. return (std::numeric_limits<size_type>::max)() / 2; } // `InlinedVector::capacity()` // - // Returns the number of elements that can be stored in the inlined vector - // without requiring a reallocation of underlying memory. + // Returns the number of elements that could be stored in the inlined vector + // without requiring a reallocation. // - // NOTE: For most inlined vectors, `capacity()` should equal - // `inlined_capacity()`. For inlined vectors which exceed this capacity, they - // will no longer be inlined and `capacity()` will equal its capacity on the - // allocated heap. + // NOTE: for most inlined vectors, `capacity()` should be equal to the + // template parameter `N`. For inlined vectors which exceed this capacity, + // they will no longer be inlined and `capacity()` will equal the capactity of + // the allocated memory. size_type capacity() const noexcept { - return allocated() ? allocation().capacity() : inlined_capacity(); + return storage_.GetIsAllocated() ? storage_.GetAllocatedCapacity() + : storage_.GetInlinedCapacity(); } // `InlinedVector::data()` // - // Returns a `pointer` to elements of the inlined vector. This pointer can be - // used to access and modify the contained elements. - // Only results within the range [`0`, `size()`) are defined. + // Returns a `pointer` to the elements of the inlined vector. This pointer + // can be used to access and modify the contained elements. + // + // NOTE: only elements within [`data()`, `data() + size()`) are valid. pointer data() noexcept { - return allocated() ? allocated_space() : inlined_space(); + return storage_.GetIsAllocated() ? storage_.GetAllocatedData() + : storage_.GetInlinedData(); } - // Overload of `InlinedVector::data()` to return a `const_pointer` to elements - // of the inlined vector. This pointer can be used to access (but not modify) - // the contained elements. + // Overload of `InlinedVector::data()` that returns a `const_pointer` to the + // elements of the inlined vector. This pointer can be used to access but not + // modify the contained elements. + // + // NOTE: only elements within [`data()`, `data() + size()`) are valid. const_pointer data() const noexcept { - return allocated() ? allocated_space() : inlined_space(); + return storage_.GetIsAllocated() ? storage_.GetAllocatedData() + : storage_.GetInlinedData(); } - // `InlinedVector::operator[]()` + // `InlinedVector::operator[](...)` // - // Returns a `reference` to the `i`th element of the inlined vector using the - // array operator. + // Returns a `reference` to the `i`th element of the inlined vector. reference operator[](size_type i) { assert(i < size()); + return data()[i]; } - // Overload of `InlinedVector::operator[]()` to return a `const_reference` to - // the `i`th element of the inlined vector. + // 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()); + return data()[i]; } - // `InlinedVector::at()` + // `InlinedVector::at(...)` // // Returns a `reference` to the `i`th element of the inlined vector. + // + // NOTE: if `i` is not within the required range of `InlinedVector::at(...)`, + // in both debug and non-debug builds, `std::out_of_range` will be thrown. reference at(size_type i) { if (ABSL_PREDICT_FALSE(i >= size())) { base_internal::ThrowStdOutOfRange( - "InlinedVector::at() failed bounds check"); + "`InlinedVector::at(size_type)` failed bounds check"); } + return data()[i]; } - // Overload of `InlinedVector::at()` to return a `const_reference` to the - // `i`th element of the inlined vector. + // Overload of `InlinedVector::at(...)` that returns a `const_reference` to + // the `i`th element of the inlined vector. + // + // NOTE: if `i` is not within the required range of `InlinedVector::at(...)`, + // in both debug and non-debug builds, `std::out_of_range` will be thrown. const_reference at(size_type i) const { if (ABSL_PREDICT_FALSE(i >= size())) { base_internal::ThrowStdOutOfRange( - "InlinedVector::at() failed bounds check"); + "`InlinedVector::at(size_type) const` failed bounds check"); } + return data()[i]; } @@ -276,13 +353,15 @@ class InlinedVector { // Returns a `reference` to the first element of the inlined vector. reference front() { assert(!empty()); + return at(0); } - // Overload of `InlinedVector::front()` returns a `const_reference` to the - // first element of the inlined vector. + // 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); } @@ -291,13 +370,15 @@ class InlinedVector { // Returns a `reference` to the last element of the inlined vector. reference back() { assert(!empty()); + return at(size() - 1); } - // Overload of `InlinedVector::back()` to return a `const_reference` to the + // 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); } @@ -306,7 +387,7 @@ class InlinedVector { // Returns an `iterator` to the beginning of the inlined vector. iterator begin() noexcept { return data(); } - // Overload of `InlinedVector::begin()` to return a `const_iterator` to + // Overload of `InlinedVector::begin()` that returns a `const_iterator` to // the beginning of the inlined vector. const_iterator begin() const noexcept { return data(); } @@ -315,7 +396,7 @@ class InlinedVector { // Returns an `iterator` to the end of the inlined vector. iterator end() noexcept { return data() + size(); } - // Overload of `InlinedVector::end()` to return a `const_iterator` to the + // Overload of `InlinedVector::end()` that returns a `const_iterator` to the // end of the inlined vector. const_iterator end() const noexcept { return data() + size(); } @@ -334,7 +415,7 @@ class InlinedVector { // Returns a `reverse_iterator` from the end of the inlined vector. reverse_iterator rbegin() noexcept { return reverse_iterator(end()); } - // Overload of `InlinedVector::rbegin()` to return a + // Overload of `InlinedVector::rbegin()` that returns a // `const_reverse_iterator` from the end of the inlined vector. const_reverse_iterator rbegin() const noexcept { return const_reverse_iterator(end()); @@ -345,7 +426,7 @@ class InlinedVector { // Returns a `reverse_iterator` from the beginning of the inlined vector. reverse_iterator rend() noexcept { return reverse_iterator(begin()); } - // Overload of `InlinedVector::rend()` to return a `const_reverse_iterator` + // Overload of `InlinedVector::rend()` that returns a `const_reverse_iterator` // from the beginning of the inlined vector. const_reverse_iterator rend() const noexcept { return const_reverse_iterator(begin()); @@ -364,1086 +445,403 @@ class InlinedVector { // `InlinedVector::get_allocator()` // - // Returns a copy of the allocator of the inlined vector. - allocator_type get_allocator() const { return allocator(); } + // Returns a copy of the inlined vector's allocator. + allocator_type get_allocator() const { return *storage_.GetAllocPtr(); } // --------------------------------------------------------------------------- // InlinedVector Member Mutators // --------------------------------------------------------------------------- - // `InlinedVector::operator=()` + // `InlinedVector::operator=(...)` // - // Replaces the contents of the inlined vector with copies of the elements in - // the provided `std::initializer_list`. - InlinedVector& operator=(std::initializer_list<value_type> init_list) { - AssignRange(init_list.begin(), init_list.end(), - IteratorCategory<decltype(init_list.begin())>{}); + // Replaces the elements of the inlined vector with copies of the elements of + // `list`. + InlinedVector& operator=(std::initializer_list<value_type> list) { + assign(list.begin(), list.end()); + return *this; } - // Overload of `InlinedVector::operator=()` to replace the contents of the - // inlined vector with the contents of `other`. + // Overload of `InlinedVector::operator=(...)` that replaces the elements of + // the inlined vector with copies of the elements of `other`. InlinedVector& operator=(const InlinedVector& other) { - if (ABSL_PREDICT_FALSE(this == &other)) return *this; - - // Optimized to avoid reallocation. - // Prefer reassignment to copy construction for elements. - if (size() < other.size()) { // grow - reserve(other.size()); - std::copy(other.begin(), other.begin() + size(), begin()); - std::copy(other.begin() + size(), other.end(), std::back_inserter(*this)); - } else { // maybe shrink - erase(begin() + other.size(), end()); - std::copy(other.begin(), other.end(), begin()); + if (ABSL_PREDICT_TRUE(this != std::addressof(other))) { + const_pointer other_data = other.data(); + assign(other_data, other_data + other.size()); } + return *this; } - // Overload of `InlinedVector::operator=()` to replace the contents of the - // inlined vector with the contents of `other`. + // Overload of `InlinedVector::operator=(...)` that moves the elements of + // `other` into the inlined vector. // - // NOTE: As a result of calling this overload, `other` may be empty or it's - // contents may be left in a moved-from state. + // NOTE: as a result of calling this overload, `other` is left in a valid but + // unspecified state. InlinedVector& operator=(InlinedVector&& other) { - if (ABSL_PREDICT_FALSE(this == &other)) return *this; - - if (other.allocated()) { - clear(); - tag().set_allocated_size(other.size()); - init_allocation(other.allocation()); - other.tag() = Tag(); - } else { - if (allocated()) clear(); - // Both are inlined now. - if (size() < other.size()) { - auto mid = std::make_move_iterator(other.begin() + size()); - std::copy(std::make_move_iterator(other.begin()), mid, begin()); - UninitializedCopy(mid, std::make_move_iterator(other.end()), end()); + if (ABSL_PREDICT_TRUE(this != std::addressof(other))) { + if (IsMemcpyOk::value || other.storage_.GetIsAllocated()) { + inlined_vector_internal::DestroyElements(storage_.GetAllocPtr(), data(), + size()); + storage_.DeallocateIfAllocated(); + storage_.MemcpyFrom(other.storage_); + + other.storage_.SetInlinedSize(0); } else { - auto new_end = std::copy(std::make_move_iterator(other.begin()), - std::make_move_iterator(other.end()), begin()); - Destroy(new_end, end()); + storage_.Assign(IteratorValueAdapter<MoveIterator>( + MoveIterator(other.storage_.GetInlinedData())), + other.size()); } - tag().set_inline_size(other.size()); } + return *this; } - // `InlinedVector::assign()` + // `InlinedVector::assign(...)` // // Replaces the contents of the inlined vector with `n` copies of `v`. void assign(size_type n, const_reference v) { - if (n <= size()) { // Possibly shrink - std::fill_n(begin(), n, v); - erase(begin() + n, end()); - return; - } - // Grow - reserve(n); - std::fill_n(begin(), size(), v); - if (allocated()) { - UninitializedFill(allocated_space() + size(), allocated_space() + n, v); - tag().set_allocated_size(n); - } else { - UninitializedFill(inlined_space() + size(), inlined_space() + n, v); - tag().set_inline_size(n); - } + storage_.Assign(CopyValueAdapter(v), n); + } + + // Overload of `InlinedVector::assign(...)` that replaces the contents of the + // inlined vector with copies of the elements of `list`. + void assign(std::initializer_list<value_type> list) { + assign(list.begin(), list.end()); } - // Overload of `InlinedVector::assign()` to replace the contents of the - // inlined vector with copies of the values in the provided - // `std::initializer_list`. - void assign(std::initializer_list<value_type> init_list) { - AssignRange(init_list.begin(), init_list.end(), - IteratorCategory<decltype(init_list.begin())>{}); + // Overload of `InlinedVector::assign(...)` to replace the contents of the + // inlined vector with the range [`first`, `last`). + // + // NOTE: this overload is for iterators that are "forward" category or better. + template <typename ForwardIterator, + EnableIfAtLeastForwardIterator<ForwardIterator>* = nullptr> + void assign(ForwardIterator first, ForwardIterator last) { + storage_.Assign(IteratorValueAdapter<ForwardIterator>(first), + std::distance(first, last)); } - // Overload of `InlinedVector::assign()` to replace the contents of the - // inlined vector with values constructed from the range [`first`, `last`). - template <typename InputIterator, DisableIfIntegral<InputIterator>* = nullptr> + // Overload of `InlinedVector::assign(...)` to replace the contents of the + // inlined vector with the range [`first`, `last`). + // + // NOTE: this overload is for iterators that are "input" category. + template <typename InputIterator, + DisableIfAtLeastForwardIterator<InputIterator>* = nullptr> void assign(InputIterator first, InputIterator last) { - AssignRange(first, last, IteratorCategory<InputIterator>{}); + size_type i = 0; + for (; i < size() && first != last; ++i, static_cast<void>(++first)) { + at(i) = *first; + } + + erase(data() + i, data() + size()); + + std::copy(first, last, std::back_inserter(*this)); } - // `InlinedVector::resize()` + // `InlinedVector::resize(...)` + // + // Resizes the inlined vector to contain `n` elements. // - // Resizes the inlined vector to contain `n` elements. If `n` is smaller than - // the inlined vector's current size, extra elements are destroyed. If `n` is - // larger than the initial size, new elements are value-initialized. - void resize(size_type 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); } - // Overload of `InlinedVector::resize()` to resize the inlined vector to - // contain `n` elements where, if `n` is larger than `size()`, the new values - // will be copy-constructed from `v`. - void resize(size_type n, const_reference v); + // Overload of `InlinedVector::resize(...)` that resizes the inlined vector to + // contain `n` elements. + // + // 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); + } - // `InlinedVector::insert()` + // `InlinedVector::insert(...)` // - // Copies `v` into `position`, returning an `iterator` pointing to the newly + // Inserts a copy of `v` at `pos`, returning an `iterator` to the newly // inserted element. - iterator insert(const_iterator position, const_reference v) { - return emplace(position, v); + iterator insert(const_iterator pos, const_reference v) { + return emplace(pos, v); } - // Overload of `InlinedVector::insert()` for moving `v` into `position`, - // returning an iterator pointing to the newly inserted element. - iterator insert(const_iterator position, rvalue_reference v) { - return emplace(position, std::move(v)); + // 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, rvalue_reference v) { + return emplace(pos, std::move(v)); } - // Overload of `InlinedVector::insert()` for inserting `n` contiguous copies - // of `v` starting at `position`. Returns an `iterator` pointing to the first - // of the newly inserted elements. - iterator insert(const_iterator position, size_type n, const_reference v) { - return InsertWithCount(position, n, v); + // Overload of `InlinedVector::insert(...)` that inserts `n` contiguous copies + // 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()); + + if (ABSL_PREDICT_TRUE(n != 0)) { + value_type dealias = v; + return storage_.Insert(pos, CopyValueAdapter(dealias), n); + } else { + return const_cast<iterator>(pos); + } } - // Overload of `InlinedVector::insert()` for copying the contents of the - // `std::initializer_list` into the vector starting at `position`. Returns an - // `iterator` pointing to the first of the newly inserted elements. - iterator insert(const_iterator position, - std::initializer_list<value_type> init_list) { - return insert(position, init_list.begin(), init_list.end()); + // Overload of `InlinedVector::insert(...)` that inserts copies of the + // elements of `list` starting at `pos`, returning an `iterator` pointing to + // the first of the newly inserted elements. + iterator insert(const_iterator pos, std::initializer_list<value_type> list) { + return insert(pos, list.begin(), list.end()); + } + + // Overload of `InlinedVector::insert(...)` that inserts the range [`first`, + // `last`) starting at `pos`, returning an `iterator` pointing to the first + // of the newly inserted elements. + // + // NOTE: this overload is for iterators that are "forward" category or better. + template <typename ForwardIterator, + EnableIfAtLeastForwardIterator<ForwardIterator>* = nullptr> + iterator insert(const_iterator pos, ForwardIterator first, + ForwardIterator last) { + assert(pos >= begin()); + assert(pos <= end()); + + if (ABSL_PREDICT_TRUE(first != last)) { + return storage_.Insert(pos, IteratorValueAdapter<ForwardIterator>(first), + std::distance(first, last)); + } else { + return const_cast<iterator>(pos); + } } - // Overload of `InlinedVector::insert()` for inserting elements constructed - // from the range [`first`, `last`). Returns an `iterator` pointing to the - // first of the newly inserted elements. + // Overload of `InlinedVector::insert(...)` that inserts the range [`first`, + // `last`) starting at `pos`, returning an `iterator` pointing to the first + // of the newly inserted elements. // - // NOTE: The `enable_if` is intended to disambiguate the two three-argument - // overloads of `insert()`. + // NOTE: this overload is for iterators that are "input" category. template <typename InputIterator, - typename = EnableIfInputIterator<InputIterator>> - iterator insert(const_iterator position, InputIterator first, - InputIterator last) { - return InsertWithRange(position, first, last, - IteratorCategory<InputIterator>()); + DisableIfAtLeastForwardIterator<InputIterator>* = nullptr> + iterator insert(const_iterator pos, InputIterator first, InputIterator last) { + assert(pos >= begin()); + assert(pos <= end()); + + size_type index = std::distance(cbegin(), pos); + for (size_type i = index; first != last; ++i, static_cast<void>(++first)) { + insert(data() + i, *first); + } + + return iterator(data() + index); } - // `InlinedVector::emplace()` + // `InlinedVector::emplace(...)` // - // Constructs and inserts an object in the inlined vector at the given - // `position`, returning an `iterator` pointing to the newly emplaced element. + // Constructs and inserts an element using `args...` in the inlined vector at + // `pos`, returning an `iterator` pointing to the newly emplaced element. template <typename... Args> - iterator emplace(const_iterator position, Args&&... args); + iterator emplace(const_iterator pos, Args&&... args) { + assert(pos >= begin()); + assert(pos <= end()); - // `InlinedVector::emplace_back()` + value_type dealias(std::forward<Args>(args)...); + return storage_.Insert(pos, + IteratorValueAdapter<MoveIterator>( + MoveIterator(std::addressof(dealias))), + 1); + } + + // `InlinedVector::emplace_back(...)` // - // Constructs and appends a new element to the end of the inlined vector, - // returning a `reference` to the emplaced element. + // Constructs and inserts an element using `args...` in the inlined vector at + // `end()`, returning a `reference` to the newly emplaced element. template <typename... Args> reference emplace_back(Args&&... args) { - size_type s = size(); - assert(s <= capacity()); - if (ABSL_PREDICT_FALSE(s == capacity())) { - return GrowAndEmplaceBack(std::forward<Args>(args)...); - } - assert(s < capacity()); - - pointer space; - if (allocated()) { - tag().set_allocated_size(s + 1); - space = allocated_space(); - } else { - tag().set_inline_size(s + 1); - space = inlined_space(); - } - return Construct(space + s, std::forward<Args>(args)...); + return storage_.EmplaceBack(std::forward<Args>(args)...); } - // `InlinedVector::push_back()` + // `InlinedVector::push_back(...)` // - // Appends a copy of `v` to the end of the inlined vector. + // Inserts a copy of `v` in the inlined vector at `end()`. void push_back(const_reference v) { static_cast<void>(emplace_back(v)); } - // Overload of `InlinedVector::push_back()` for moving `v` into a newly - // appended element. + // Overload of `InlinedVector::push_back(...)` for inserting `v` at `end()` + // using move semantics. void push_back(rvalue_reference v) { static_cast<void>(emplace_back(std::move(v))); } // `InlinedVector::pop_back()` // - // Destroys the element at the end of the inlined vector and shrinks the size - // by `1` (unless the inlined vector is empty, in which case this is a no-op). + // Destroys the element at `back()`, reducing the size by `1`. void pop_back() noexcept { assert(!empty()); - size_type s = size(); - if (allocated()) { - Destroy(allocated_space() + s - 1, allocated_space() + s); - tag().set_allocated_size(s - 1); - } else { - Destroy(inlined_space() + s - 1, inlined_space() + s); - tag().set_inline_size(s - 1); - } + + AllocatorTraits::destroy(*storage_.GetAllocPtr(), data() + (size() - 1)); + storage_.SubtractSize(1); } - // `InlinedVector::erase()` + // `InlinedVector::erase(...)` // - // Erases the element at `position` of the inlined vector, returning an - // `iterator` pointing to the first element following the erased element. + // Erases the element at `pos`, returning an `iterator` pointing to where the + // erased element was located. // - // NOTE: May return the end iterator, which is not dereferencable. - iterator erase(const_iterator position) { - assert(position >= begin()); - assert(position < end()); - - iterator pos = const_cast<iterator>(position); - std::move(pos + 1, end(), pos); - pop_back(); - return pos; + // NOTE: may return `end()`, which is not dereferencable. + iterator erase(const_iterator pos) { + assert(pos >= begin()); + assert(pos < end()); + + return storage_.Erase(pos, pos + 1); } - // Overload of `InlinedVector::erase()` for erasing all elements in the - // range [`from`, `to`) in the inlined vector. Returns an `iterator` pointing - // to the first element following the range erased or the end iterator if `to` - // was the end iterator. - iterator erase(const_iterator from, const_iterator to); + // Overload of `InlinedVector::erase(...)` that erases every element in the + // range [`from`, `to`), returning an `iterator` pointing to where the first + // erased element was located. + // + // 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()); + + if (ABSL_PREDICT_TRUE(from != to)) { + return storage_.Erase(from, to); + } else { + return const_cast<iterator>(from); + } + } // `InlinedVector::clear()` // - // Destroys all elements in the inlined vector, sets the size of `0` and - // deallocates the heap allocation if the inlined vector was allocated. + // Destroys all elements in the inlined vector, setting the size to `0` and + // deallocating any held memory. void clear() noexcept { - size_type s = size(); - if (allocated()) { - Destroy(allocated_space(), allocated_space() + s); - allocation().Dealloc(allocator()); - } else if (s != 0) { // do nothing for empty vectors - Destroy(inlined_space(), inlined_space() + s); - } - tag() = Tag(); + inlined_vector_internal::DestroyElements(storage_.GetAllocPtr(), data(), + size()); + storage_.DeallocateIfAllocated(); + storage_.SetInlinedSize(0); } - // `InlinedVector::reserve()` + // `InlinedVector::reserve(...)` // - // Enlarges the underlying representation of the inlined vector so it can hold - // at least `n` elements. This method does not change `size()` or the actual - // contents of the vector. - // - // NOTE: If `n` does not exceed `capacity()`, `reserve()` will have no - // effects. Otherwise, `reserve()` will reallocate, performing an n-time - // element-wise move of everything contained. - void reserve(size_type n) { - if (n > capacity()) { - // Make room for new elements - EnlargeBy(n - size()); - } - } + // Ensures that there is enough room for at least `n` elements. + void reserve(size_type n) { storage_.Reserve(n); } // `InlinedVector::shrink_to_fit()` // - // Reduces memory usage by freeing unused memory. After this call, calls to - // `capacity()` will be equal to `(std::max)(inlined_capacity(), size())`. + // Reduces memory usage by freeing unused memory. After being called, calls to + // `capacity()` will be equal to `max(N, size())`. // - // If `size() <= inlined_capacity()` and the elements are currently stored on - // the heap, they will be moved to the inlined storage and the heap memory + // 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() > inlined_capacity()` and `size() < capacity()` the elements - // will be moved to a smaller heap allocation. + // If `size() > N` and `size() < capacity()`, the elements will be moved to a + // smaller allocation. void shrink_to_fit() { - const auto s = size(); - if (ABSL_PREDICT_FALSE(!allocated() || s == capacity())) return; - - if (s <= inlined_capacity()) { - // Move the elements to the inlined storage. - // We have to do this using a temporary, because `inlined_storage` and - // `allocation_storage` are in a union field. - auto temp = std::move(*this); - assign(std::make_move_iterator(temp.begin()), - std::make_move_iterator(temp.end())); - return; + if (storage_.GetIsAllocated()) { + storage_.ShrinkToFit(); } - - // Reallocate storage and move elements. - // We can't simply use the same approach as above, because `assign()` would - // call into `reserve()` internally and reserve larger capacity than we need - Allocation new_allocation(allocator(), s); - UninitializedCopy(std::make_move_iterator(allocated_space()), - std::make_move_iterator(allocated_space() + s), - new_allocation.buffer()); - ResetAllocation(new_allocation, s); } - // `InlinedVector::swap()` + // `InlinedVector::swap(...)` // - // Swaps the contents of this inlined vector with the contents of `other`. - void swap(InlinedVector& other); - - template <typename Hash> - friend Hash AbslHashValue(Hash hash, const InlinedVector& inlined_vector) { - const_pointer p = inlined_vector.data(); - size_type n = inlined_vector.size(); - return Hash::combine(Hash::combine_contiguous(std::move(hash), p, n), n); - } - - private: - // Holds whether the vector is allocated or not in the lowest bit and the size - // in the high bits: - // `size_ = (size << 1) | is_allocated;` - class Tag { - public: - Tag() : size_(0) {} - size_type size() const { return size_ / 2; } - void add_size(size_type n) { size_ += n * 2; } - void set_inline_size(size_type n) { size_ = n * 2; } - void set_allocated_size(size_type n) { size_ = (n * 2) + 1; } - bool allocated() const { return size_ % 2; } - - private: - size_type size_; - }; - - // Derives from `allocator_type` to use the empty base class optimization. - // If the `allocator_type` is stateless, we can store our instance for free. - class AllocatorAndTag : private allocator_type { - public: - explicit AllocatorAndTag(const allocator_type& a) : allocator_type(a) {} - - Tag& tag() { return tag_; } - const Tag& tag() const { return tag_; } - - allocator_type& allocator() { return *this; } - const allocator_type& allocator() const { return *this; } - - private: - Tag tag_; - }; - - class Allocation { - public: - Allocation(allocator_type& a, size_type capacity) - : capacity_(capacity), buffer_(Create(a, capacity)) {} - - void Dealloc(allocator_type& a) { - std::allocator_traits<allocator_type>::deallocate(a, buffer_, capacity_); - } - - size_type capacity() const { return capacity_; } - - const_pointer buffer() const { return buffer_; } - - pointer buffer() { return buffer_; } - - private: - static pointer Create(allocator_type& a, size_type n) { - return std::allocator_traits<allocator_type>::allocate(a, n); + // Swaps the contents of the inlined vector with `other`. + void swap(InlinedVector& other) { + if (ABSL_PREDICT_TRUE(this != std::addressof(other))) { + storage_.Swap(std::addressof(other.storage_)); } - - size_type capacity_; - pointer buffer_; - }; - - const Tag& tag() const { return allocator_and_tag_.tag(); } - - Tag& tag() { return allocator_and_tag_.tag(); } - - Allocation& allocation() { - return reinterpret_cast<Allocation&>(rep_.allocation_storage.allocation); - } - - const Allocation& allocation() const { - return reinterpret_cast<const Allocation&>( - rep_.allocation_storage.allocation); - } - - void init_allocation(const Allocation& allocation) { - new (&rep_.allocation_storage.allocation) Allocation(allocation); - } - - // TODO(absl-team): investigate whether the reinterpret_cast is appropriate. - pointer inlined_space() { - return reinterpret_cast<pointer>( - std::addressof(rep_.inlined_storage.inlined[0])); - } - - const_pointer inlined_space() const { - return reinterpret_cast<const_pointer>( - std::addressof(rep_.inlined_storage.inlined[0])); - } - - pointer allocated_space() { return allocation().buffer(); } - - const_pointer allocated_space() const { return allocation().buffer(); } - - const allocator_type& allocator() const { - return allocator_and_tag_.allocator(); } - allocator_type& allocator() { return allocator_and_tag_.allocator(); } - - bool allocated() const { return tag().allocated(); } - - // Enlarge the underlying representation so we can store `size_ + delta` elems - // in allocated space. The size is not changed, and any newly added memory is - // not initialized. - void EnlargeBy(size_type delta); - - // Shift all elements from `position` to `end()` by `n` places to the right. - // If the vector needs to be enlarged, memory will be allocated. - // Returns `iterator`s pointing to the start of the previously-initialized - // portion and the start of the uninitialized portion of the created gap. - // The number of initialized spots is `pair.second - pair.first`. The number - // of raw spots is `n - (pair.second - pair.first)`. - // - // Updates the size of the InlinedVector internally. - std::pair<iterator, iterator> ShiftRight(const_iterator position, - size_type n); - - void ResetAllocation(Allocation new_allocation, size_type new_size) { - if (allocated()) { - Destroy(allocated_space(), allocated_space() + size()); - assert(begin() == allocated_space()); - allocation().Dealloc(allocator()); - allocation() = new_allocation; - } else { - Destroy(inlined_space(), inlined_space() + size()); - init_allocation(new_allocation); // bug: only init once - } - tag().set_allocated_size(new_size); - } - - template <typename... Args> - reference GrowAndEmplaceBack(Args&&... args) { - assert(size() == capacity()); - const size_type s = size(); - - Allocation new_allocation(allocator(), 2 * capacity()); - - reference new_element = - Construct(new_allocation.buffer() + s, std::forward<Args>(args)...); - UninitializedCopy(std::make_move_iterator(data()), - std::make_move_iterator(data() + s), - new_allocation.buffer()); - - ResetAllocation(new_allocation, s + 1); - - return new_element; - } - - void InitAssign(size_type n); - - void InitAssign(size_type n, const_reference v); - - template <typename... Args> - reference Construct(pointer p, Args&&... args) { - std::allocator_traits<allocator_type>::construct( - allocator(), p, std::forward<Args>(args)...); - return *p; - } - - template <typename Iterator> - void UninitializedCopy(Iterator src, Iterator src_last, pointer dst) { - for (; src != src_last; ++dst, ++src) Construct(dst, *src); - } - - template <typename... Args> - void UninitializedFill(pointer dst, pointer dst_last, const Args&... args) { - for (; dst != dst_last; ++dst) Construct(dst, args...); - } - - // Destroy [`from`, `to`) in place. - void Destroy(pointer from, pointer to); - - template <typename Iterator> - void AppendRange(Iterator first, Iterator last, std::forward_iterator_tag); - - template <typename Iterator> - void AppendRange(Iterator first, Iterator last, std::input_iterator_tag); - - template <typename Iterator> - void AssignRange(Iterator first, Iterator last, std::forward_iterator_tag); + private: + template <typename H, typename TheT, size_t TheN, typename TheA> + friend H AbslHashValue(H h, const absl::InlinedVector<TheT, TheN, TheA>& a); - template <typename Iterator> - void AssignRange(Iterator first, Iterator last, std::input_iterator_tag); - - iterator InsertWithCount(const_iterator position, size_type n, - const_reference v); - - template <typename ForwardIterator> - iterator InsertWithRange(const_iterator position, ForwardIterator first, - ForwardIterator last, std::forward_iterator_tag); - - template <typename InputIterator> - iterator InsertWithRange(const_iterator position, InputIterator first, - InputIterator last, std::input_iterator_tag); - - // Stores either the inlined or allocated representation - union Rep { - using ValueTypeBuffer = - absl::aligned_storage_t<sizeof(value_type), alignof(value_type)>; - using AllocationBuffer = - absl::aligned_storage_t<sizeof(Allocation), alignof(Allocation)>; - - // Structs wrap the buffers to perform indirection that solves a bizarre - // compilation error on Visual Studio (all known versions). - struct InlinedRep { - ValueTypeBuffer inlined[N]; - }; - struct AllocatedRep { - AllocationBuffer allocation; - }; - - InlinedRep inlined_storage; - AllocatedRep allocation_storage; - }; - - AllocatorAndTag allocator_and_tag_; - Rep rep_; + Storage storage_; }; // ----------------------------------------------------------------------------- // InlinedVector Non-Member Functions // ----------------------------------------------------------------------------- -// `swap()` +// `swap(...)` // -// Swaps the contents of two inlined vectors. This convenience function -// simply calls `InlinedVector::swap()`. +// Swaps the contents of two inlined vectors. template <typename T, size_t N, typename A> -void swap(InlinedVector<T, N, A>& a, - InlinedVector<T, N, A>& b) noexcept(noexcept(a.swap(b))) { +void swap(absl::InlinedVector<T, N, A>& a, + absl::InlinedVector<T, N, A>& b) noexcept(noexcept(a.swap(b))) { a.swap(b); } -// `operator==()` +// `operator==(...)` // -// Tests the equivalency of the contents of two inlined vectors. +// Tests for value-equality of two inlined vectors. template <typename T, size_t N, typename A> -bool operator==(const InlinedVector<T, N, A>& a, - const InlinedVector<T, N, A>& b) { - return absl::equal(a.begin(), a.end(), b.begin(), b.end()); +bool operator==(const absl::InlinedVector<T, N, A>& a, + const absl::InlinedVector<T, N, A>& b) { + auto a_data = a.data(); + auto b_data = b.data(); + return absl::equal(a_data, a_data + a.size(), b_data, b_data + b.size()); } -// `operator!=()` +// `operator!=(...)` // -// Tests the inequality of the contents of two inlined vectors. +// Tests for value-inequality of two inlined vectors. template <typename T, size_t N, typename A> -bool operator!=(const InlinedVector<T, N, A>& a, - const InlinedVector<T, N, A>& b) { +bool operator!=(const absl::InlinedVector<T, N, A>& a, + const absl::InlinedVector<T, N, A>& b) { return !(a == b); } -// `operator<()` +// `operator<(...)` // -// Tests whether the contents of one inlined vector are less than the contents -// of another through a lexicographical comparison operation. +// Tests whether the value of an inlined vector is less than the value of +// another inlined vector using a lexicographical comparison algorithm. template <typename T, size_t N, typename A> -bool operator<(const InlinedVector<T, N, A>& a, - const InlinedVector<T, N, A>& b) { - return std::lexicographical_compare(a.begin(), a.end(), b.begin(), b.end()); +bool operator<(const absl::InlinedVector<T, N, A>& a, + const absl::InlinedVector<T, N, A>& b) { + auto a_data = a.data(); + auto b_data = b.data(); + return std::lexicographical_compare(a_data, a_data + a.size(), b_data, + b_data + b.size()); } -// `operator>()` +// `operator>(...)` // -// Tests whether the contents of one inlined vector are greater than the -// contents of another through a lexicographical comparison operation. +// Tests whether the value of an inlined vector is greater than the value of +// another inlined vector using a lexicographical comparison algorithm. template <typename T, size_t N, typename A> -bool operator>(const InlinedVector<T, N, A>& a, - const InlinedVector<T, N, A>& b) { +bool operator>(const absl::InlinedVector<T, N, A>& a, + const absl::InlinedVector<T, N, A>& b) { return b < a; } -// `operator<=()` +// `operator<=(...)` // -// Tests whether the contents of one inlined vector are less than or equal to -// the contents of another through a lexicographical comparison operation. +// Tests whether the value of an inlined vector is less than or equal to the +// value of another inlined vector using a lexicographical comparison algorithm. template <typename T, size_t N, typename A> -bool operator<=(const InlinedVector<T, N, A>& a, - const InlinedVector<T, N, A>& b) { +bool operator<=(const absl::InlinedVector<T, N, A>& a, + const absl::InlinedVector<T, N, A>& b) { return !(b < a); } -// `operator>=()` +// `operator>=(...)` // -// Tests whether the contents of one inlined vector are greater than or equal to -// the contents of another through a lexicographical comparison operation. +// Tests whether the value of an inlined vector is greater than or equal to the +// value of another inlined vector using a lexicographical comparison algorithm. template <typename T, size_t N, typename A> -bool operator>=(const InlinedVector<T, N, A>& a, - const InlinedVector<T, N, A>& b) { +bool operator>=(const absl::InlinedVector<T, N, A>& a, + const absl::InlinedVector<T, N, A>& b) { return !(a < b); } -// ----------------------------------------------------------------------------- -// Implementation of InlinedVector +// `AbslHashValue(...)` // -// Do not depend on any below implementation details! -// ----------------------------------------------------------------------------- - -template <typename T, size_t N, typename A> -InlinedVector<T, N, A>::InlinedVector(const InlinedVector& other) - : allocator_and_tag_(other.allocator()) { - reserve(other.size()); - if (allocated()) { - UninitializedCopy(other.begin(), other.end(), allocated_space()); - tag().set_allocated_size(other.size()); - } else { - UninitializedCopy(other.begin(), other.end(), inlined_space()); - tag().set_inline_size(other.size()); - } -} - -template <typename T, size_t N, typename A> -InlinedVector<T, N, A>::InlinedVector(const InlinedVector& other, - const allocator_type& alloc) - : allocator_and_tag_(alloc) { - reserve(other.size()); - if (allocated()) { - UninitializedCopy(other.begin(), other.end(), allocated_space()); - tag().set_allocated_size(other.size()); - } else { - UninitializedCopy(other.begin(), other.end(), inlined_space()); - tag().set_inline_size(other.size()); - } -} - -template <typename T, size_t N, typename A> -InlinedVector<T, N, A>::InlinedVector(InlinedVector&& other) noexcept( - absl::allocator_is_nothrow<allocator_type>::value || - std::is_nothrow_move_constructible<value_type>::value) - : allocator_and_tag_(other.allocator_and_tag_) { - if (other.allocated()) { - // We can just steal the underlying buffer from the source. - // That leaves the source empty, so we clear its size. - init_allocation(other.allocation()); - other.tag() = Tag(); - } else { - UninitializedCopy( - std::make_move_iterator(other.inlined_space()), - std::make_move_iterator(other.inlined_space() + other.size()), - inlined_space()); - } -} - -template <typename T, size_t N, typename A> -InlinedVector<T, N, A>::InlinedVector(InlinedVector&& other, - const allocator_type& alloc) noexcept( // - absl::allocator_is_nothrow<allocator_type>::value) - : allocator_and_tag_(alloc) { - if (other.allocated()) { - if (alloc == other.allocator()) { - // We can just steal the allocation from the source. - tag() = other.tag(); - init_allocation(other.allocation()); - other.tag() = Tag(); - } else { - // We need to use our own allocator - reserve(other.size()); - UninitializedCopy(std::make_move_iterator(other.begin()), - std::make_move_iterator(other.end()), - allocated_space()); - tag().set_allocated_size(other.size()); - } - } else { - UninitializedCopy( - std::make_move_iterator(other.inlined_space()), - std::make_move_iterator(other.inlined_space() + other.size()), - inlined_space()); - tag().set_inline_size(other.size()); - } -} - -template <typename T, size_t N, typename A> -void InlinedVector<T, N, A>::InitAssign(size_type n, const_reference v) { - if (n > inlined_capacity()) { - Allocation new_allocation(allocator(), n); - init_allocation(new_allocation); - UninitializedFill(allocated_space(), allocated_space() + n, v); - tag().set_allocated_size(n); - } else { - UninitializedFill(inlined_space(), inlined_space() + n, v); - tag().set_inline_size(n); - } -} - -template <typename T, size_t N, typename A> -void InlinedVector<T, N, A>::InitAssign(size_type n) { - if (n > inlined_capacity()) { - Allocation new_allocation(allocator(), n); - init_allocation(new_allocation); - UninitializedFill(allocated_space(), allocated_space() + n); - tag().set_allocated_size(n); - } else { - UninitializedFill(inlined_space(), inlined_space() + n); - tag().set_inline_size(n); - } -} - -template <typename T, size_t N, typename A> -void InlinedVector<T, N, A>::resize(size_type n) { - size_type s = size(); - if (n < s) { - erase(begin() + n, end()); - return; - } - reserve(n); - assert(capacity() >= n); - - // Fill new space with elements constructed in-place. - if (allocated()) { - UninitializedFill(allocated_space() + s, allocated_space() + n); - tag().set_allocated_size(n); - } else { - UninitializedFill(inlined_space() + s, inlined_space() + n); - tag().set_inline_size(n); - } -} - -template <typename T, size_t N, typename A> -void InlinedVector<T, N, A>::resize(size_type n, const_reference v) { - size_type s = size(); - if (n < s) { - erase(begin() + n, end()); - return; - } - reserve(n); - assert(capacity() >= n); - - // Fill new space with copies of 'v'. - if (allocated()) { - UninitializedFill(allocated_space() + s, allocated_space() + n, v); - tag().set_allocated_size(n); - } else { - UninitializedFill(inlined_space() + s, inlined_space() + n, v); - tag().set_inline_size(n); - } -} - -template <typename T, size_t N, typename A> -template <typename... Args> -auto InlinedVector<T, N, A>::emplace(const_iterator position, Args&&... args) - -> iterator { - assert(position >= begin()); - assert(position <= end()); - if (ABSL_PREDICT_FALSE(position == end())) { - emplace_back(std::forward<Args>(args)...); - return end() - 1; - } - - T new_t = T(std::forward<Args>(args)...); - - auto range = ShiftRight(position, 1); - if (range.first == range.second) { - // constructing into uninitialized memory - Construct(range.first, std::move(new_t)); - } else { - // assigning into moved-from object - *range.first = T(std::move(new_t)); - } - - return range.first; -} - -template <typename T, size_t N, typename A> -auto InlinedVector<T, N, A>::erase(const_iterator from, const_iterator to) - -> iterator { - assert(begin() <= from); - assert(from <= to); - assert(to <= end()); - - iterator range_start = const_cast<iterator>(from); - iterator range_end = const_cast<iterator>(to); - - size_type s = size(); - ptrdiff_t erase_gap = std::distance(range_start, range_end); - if (erase_gap > 0) { - pointer space; - if (allocated()) { - space = allocated_space(); - tag().set_allocated_size(s - erase_gap); - } else { - space = inlined_space(); - tag().set_inline_size(s - erase_gap); - } - std::move(range_end, space + s, range_start); - Destroy(space + s - erase_gap, space + s); - } - return range_start; -} - -template <typename T, size_t N, typename A> -void InlinedVector<T, N, A>::swap(InlinedVector& other) { - using std::swap; // Augment ADL with `std::swap`. - if (ABSL_PREDICT_FALSE(this == &other)) return; - - if (allocated() && other.allocated()) { - // Both out of line, so just swap the tag, allocation, and allocator. - swap(tag(), other.tag()); - swap(allocation(), other.allocation()); - swap(allocator(), other.allocator()); - return; - } - if (!allocated() && !other.allocated()) { - // Both inlined: swap up to smaller size, then move remaining elements. - InlinedVector* a = this; - InlinedVector* b = &other; - if (size() < other.size()) { - swap(a, b); - } - - const size_type a_size = a->size(); - const size_type b_size = b->size(); - assert(a_size >= b_size); - // `a` is larger. Swap the elements up to the smaller array size. - std::swap_ranges(a->inlined_space(), a->inlined_space() + b_size, - b->inlined_space()); - - // Move the remaining elements: - // [`b_size`, `a_size`) from `a` -> [`b_size`, `a_size`) from `b` - b->UninitializedCopy(a->inlined_space() + b_size, - a->inlined_space() + a_size, - b->inlined_space() + b_size); - a->Destroy(a->inlined_space() + b_size, a->inlined_space() + a_size); - - swap(a->tag(), b->tag()); - swap(a->allocator(), b->allocator()); - assert(b->size() == a_size); - assert(a->size() == b_size); - return; - } - - // One is out of line, one is inline. - // We first move the elements from the inlined vector into the - // inlined space in the other vector. We then put the other vector's - // pointer/capacity into the originally inlined vector and swap - // the tags. - InlinedVector* a = this; - InlinedVector* b = &other; - if (a->allocated()) { - swap(a, b); - } - assert(!a->allocated()); - assert(b->allocated()); - const size_type a_size = a->size(); - const size_type b_size = b->size(); - // In an optimized build, `b_size` would be unused. - static_cast<void>(b_size); - - // Made Local copies of `size()`, don't need `tag()` accurate anymore - swap(a->tag(), b->tag()); - - // Copy `b_allocation` out before `b`'s union gets clobbered by `inline_space` - Allocation b_allocation = b->allocation(); - - b->UninitializedCopy(a->inlined_space(), a->inlined_space() + a_size, - b->inlined_space()); - a->Destroy(a->inlined_space(), a->inlined_space() + a_size); - - a->allocation() = b_allocation; - - if (a->allocator() != b->allocator()) { - swap(a->allocator(), b->allocator()); - } - - assert(b->size() == a_size); - assert(a->size() == b_size); -} - -template <typename T, size_t N, typename A> -void InlinedVector<T, N, A>::EnlargeBy(size_type delta) { - const size_type s = size(); - assert(s <= capacity()); - - size_type target = std::max(inlined_capacity(), s + delta); - - // Compute new capacity by repeatedly doubling current capacity - // TODO(psrc): Check and avoid overflow? - size_type new_capacity = capacity(); - while (new_capacity < target) { - new_capacity <<= 1; - } - - Allocation new_allocation(allocator(), new_capacity); - - UninitializedCopy(std::make_move_iterator(data()), - std::make_move_iterator(data() + s), - new_allocation.buffer()); - - ResetAllocation(new_allocation, s); -} - -template <typename T, size_t N, typename A> -auto InlinedVector<T, N, A>::ShiftRight(const_iterator position, size_type n) - -> std::pair<iterator, iterator> { - iterator start_used = const_cast<iterator>(position); - iterator start_raw = const_cast<iterator>(position); - size_type s = size(); - size_type required_size = s + n; - - if (required_size > capacity()) { - // Compute new capacity by repeatedly doubling current capacity - size_type new_capacity = capacity(); - while (new_capacity < required_size) { - new_capacity <<= 1; - } - // Move everyone into the new allocation, leaving a gap of `n` for the - // requested shift. - Allocation new_allocation(allocator(), new_capacity); - size_type index = position - begin(); - UninitializedCopy(std::make_move_iterator(data()), - std::make_move_iterator(data() + index), - new_allocation.buffer()); - UninitializedCopy(std::make_move_iterator(data() + index), - std::make_move_iterator(data() + s), - new_allocation.buffer() + index + n); - ResetAllocation(new_allocation, s); - - // New allocation means our iterator is invalid, so we'll recalculate. - // Since the entire gap is in new space, there's no used space to reuse. - start_raw = begin() + index; - start_used = start_raw; - } else { - // If we had enough space, it's a two-part move. Elements going into - // previously-unoccupied space need an `UninitializedCopy()`. Elements - // going into a previously-occupied space are just a `std::move()`. - iterator pos = const_cast<iterator>(position); - iterator raw_space = end(); - size_type slots_in_used_space = raw_space - pos; - size_type new_elements_in_used_space = std::min(n, slots_in_used_space); - size_type new_elements_in_raw_space = n - new_elements_in_used_space; - size_type old_elements_in_used_space = - slots_in_used_space - new_elements_in_used_space; - - UninitializedCopy(std::make_move_iterator(pos + old_elements_in_used_space), - std::make_move_iterator(raw_space), - raw_space + new_elements_in_raw_space); - std::move_backward(pos, pos + old_elements_in_used_space, raw_space); - - // If the gap is entirely in raw space, the used space starts where the raw - // space starts, leaving no elements in used space. If the gap is entirely - // in used space, the raw space starts at the end of the gap, leaving all - // elements accounted for within the used space. - start_used = pos; - start_raw = pos + new_elements_in_used_space; - } - tag().add_size(n); - return std::make_pair(start_used, start_raw); -} - -template <typename T, size_t N, typename A> -void InlinedVector<T, N, A>::Destroy(pointer from, pointer to) { - for (pointer cur = from; cur != to; ++cur) { - std::allocator_traits<allocator_type>::destroy(allocator(), cur); - } -#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. - if (from != to) { - auto len = sizeof(value_type) * std::distance(from, to); - std::memset(reinterpret_cast<void*>(from), 0xab, len); - } -#endif -} - -template <typename T, size_t N, typename A> -template <typename Iterator> -void InlinedVector<T, N, A>::AppendRange(Iterator first, Iterator last, - std::forward_iterator_tag) { - auto length = std::distance(first, last); - reserve(size() + length); - if (allocated()) { - UninitializedCopy(first, last, allocated_space() + size()); - tag().set_allocated_size(size() + length); - } else { - UninitializedCopy(first, last, inlined_space() + size()); - tag().set_inline_size(size() + length); - } -} - -template <typename T, size_t N, typename A> -template <typename Iterator> -void InlinedVector<T, N, A>::AppendRange(Iterator first, Iterator last, - std::input_iterator_tag) { - std::copy(first, last, std::back_inserter(*this)); -} - -template <typename T, size_t N, typename A> -template <typename Iterator> -void InlinedVector<T, N, A>::AssignRange(Iterator first, Iterator last, - std::forward_iterator_tag) { - auto length = std::distance(first, last); - // Prefer reassignment to copy construction for elements. - if (static_cast<size_type>(length) <= size()) { - erase(std::copy(first, last, begin()), end()); - return; - } - reserve(length); - iterator out = begin(); - for (; out != end(); ++first, ++out) *out = *first; - if (allocated()) { - UninitializedCopy(first, last, out); - tag().set_allocated_size(length); - } else { - UninitializedCopy(first, last, out); - tag().set_inline_size(length); - } -} - -template <typename T, size_t N, typename A> -template <typename Iterator> -void InlinedVector<T, N, A>::AssignRange(Iterator first, Iterator last, - std::input_iterator_tag) { - // Optimized to avoid reallocation. - // Prefer reassignment to copy construction for elements. - iterator out = begin(); - for (; first != last && out != end(); ++first, ++out) { - *out = *first; - } - erase(out, end()); - std::copy(first, last, std::back_inserter(*this)); -} - -template <typename T, size_t N, typename A> -auto InlinedVector<T, N, A>::InsertWithCount(const_iterator position, - size_type n, const_reference v) - -> iterator { - assert(position >= begin() && position <= end()); - if (ABSL_PREDICT_FALSE(n == 0)) return const_cast<iterator>(position); - - value_type copy = v; - std::pair<iterator, iterator> it_pair = ShiftRight(position, n); - std::fill(it_pair.first, it_pair.second, copy); - UninitializedFill(it_pair.second, it_pair.first + n, copy); - - return it_pair.first; -} - -template <typename T, size_t N, typename A> -template <typename ForwardIterator> -auto InlinedVector<T, N, A>::InsertWithRange(const_iterator position, - ForwardIterator first, - ForwardIterator last, - std::forward_iterator_tag) - -> iterator { - assert(position >= begin() && position <= end()); - if (ABSL_PREDICT_FALSE(first == last)) return const_cast<iterator>(position); - - auto n = std::distance(first, last); - std::pair<iterator, iterator> it_pair = ShiftRight(position, n); - size_type used_spots = it_pair.second - it_pair.first; - ForwardIterator open_spot = std::next(first, used_spots); - std::copy(first, open_spot, it_pair.first); - UninitializedCopy(open_spot, last, it_pair.second); - return it_pair.first; -} - -template <typename T, size_t N, typename A> -template <typename InputIterator> -auto InlinedVector<T, N, A>::InsertWithRange(const_iterator position, - InputIterator first, - InputIterator last, - std::input_iterator_tag) - -> iterator { - assert(position >= begin() && position <= end()); - size_type index = position - cbegin(); - size_type i = index; - while (first != last) insert(begin() + i++, *first++); - return begin() + index; +// Provides `absl::Hash` support for `absl::InlinedVector`. It is uncommon to +// call this directly. +template <typename H, typename T, size_t N, typename A> +H AbslHashValue(H h, const absl::InlinedVector<T, N, A>& a) { + auto size = a.size(); + return H::combine(H::combine_contiguous(std::move(h), a.data(), size), size); } -} // inline namespace lts_2018_12_18 +} // inline namespace lts_2019_08_08 } // namespace absl #endif // ABSL_CONTAINER_INLINED_VECTOR_H_ |