diff options
Diffstat (limited to 'absl/container/inlined_vector.h')
| -rw-r--r-- | absl/container/inlined_vector.h | 1330 |
1 files changed, 1330 insertions, 0 deletions
diff --git a/absl/container/inlined_vector.h b/absl/container/inlined_vector.h new file mode 100644 index 00000000..f060f5c5 --- /dev/null +++ b/absl/container/inlined_vector.h @@ -0,0 +1,1330 @@ +// Copyright 2017 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 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. +// +// ----------------------------------------------------------------------------- +// File: inlined_vector.h +// ----------------------------------------------------------------------------- +// +// This header file contains the declaration and definition of an "inlined +// vector" which behaves in an equivalent fashion to a `std::vector`, except +// that storage for small sequences of the vector are provided inline without +// requiring any heap allocation. + +// An `absl::InlinedVector<T,N>` specifies the size N at which to inline as one +// of its template parameters. Vectors of length <= N are provided inline. +// Typically N is very small (e.g., 4) so that sequences that are expected to be +// short do not require allocations. + +// An `absl::InlinedVector` does not usually require a specific allocator; if +// the inlined vector grows beyond its initial constraints, it will need to +// allocate (as any normal `std::vector` would) and it will generally use the +// default allocator in that case; optionally, a custom allocator may be +// specified using an `absl::InlinedVector<T,N,A>` construction. + +#ifndef ABSL_CONTAINER_INLINED_VECTOR_H_ +#define ABSL_CONTAINER_INLINED_VECTOR_H_ + +#include <algorithm> +#include <cassert> +#include <cstddef> +#include <cstdlib> +#include <cstring> +#include <initializer_list> +#include <iterator> +#include <memory> +#include <type_traits> +#include <utility> + +#include "absl/algorithm/algorithm.h" +#include "absl/base/internal/throw_delegate.h" +#include "absl/base/optimization.h" +#include "absl/base/port.h" +#include "absl/memory/memory.h" + +namespace absl { + +// ----------------------------------------------------------------------------- +// InlinedVector +// ----------------------------------------------------------------------------- +// +// An `absl::InlinedVector` is designed to be a drop-in replacement for +// `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 +// size, 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 +// 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 { + using AllocatorTraits = std::allocator_traits<A>; + + 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>; + + InlinedVector() noexcept(noexcept(allocator_type())) + : allocator_and_tag_(allocator_type()) {} + + explicit InlinedVector(const allocator_type& alloc) noexcept + : allocator_and_tag_(alloc) {} + + // Create a vector with n copies of value_type(). + explicit InlinedVector(size_type n) : allocator_and_tag_(allocator_type()) { + InitAssign(n); + } + + // Create a vector with n copies of elem + InlinedVector(size_type n, const value_type& elem, + const allocator_type& alloc = allocator_type()) + : allocator_and_tag_(alloc) { + InitAssign(n, elem); + } + + // Create and initialize with the elements [first .. last). + // The unused enable_if argument restricts this constructor so that it is + // elided when value_type is an integral type. This prevents ambiguous + // interpretation between a call to this constructor with two integral + // arguments and a call to the preceding (n, elem) constructor. + template <typename InputIterator> + InlinedVector( + InputIterator first, InputIterator last, + const allocator_type& alloc = allocator_type(), + typename std::enable_if<!std::is_integral<InputIterator>::value>::type* = + nullptr) + : allocator_and_tag_(alloc) { + AppendRange(first, last); + } + + InlinedVector(std::initializer_list<value_type> init, + const allocator_type& alloc = allocator_type()) + : allocator_and_tag_(alloc) { + AppendRange(init.begin(), init.end()); + } + + InlinedVector(const InlinedVector& v); + InlinedVector(const InlinedVector& v, const allocator_type& alloc); + + InlinedVector(InlinedVector&& v) noexcept( + absl::allocator_is_nothrow<allocator_type>::value || + std::is_nothrow_move_constructible<value_type>::value); + InlinedVector(InlinedVector&& v, const allocator_type& alloc) noexcept( + absl::allocator_is_nothrow<allocator_type>::value); + + ~InlinedVector() { clear(); } + + InlinedVector& operator=(const InlinedVector& v) { + // Optimized to avoid reallocation. + // Prefer reassignment to copy construction for elements. + if (size() < v.size()) { // grow + reserve(v.size()); + std::copy(v.begin(), v.begin() + size(), begin()); + std::copy(v.begin() + size(), v.end(), std::back_inserter(*this)); + } else { // maybe shrink + erase(begin() + v.size(), end()); + std::copy(v.begin(), v.end(), begin()); + } + return *this; + } + + InlinedVector& operator=(InlinedVector&& v) { + if (this == &v) { + return *this; + } + if (v.allocated()) { + clear(); + tag().set_allocated_size(v.size()); + init_allocation(v.allocation()); + v.tag() = Tag(); + } else { + if (allocated()) clear(); + // Both are inlined now. + if (size() < v.size()) { + auto mid = std::make_move_iterator(v.begin() + size()); + std::copy(std::make_move_iterator(v.begin()), mid, begin()); + UninitializedCopy(mid, std::make_move_iterator(v.end()), end()); + } else { + auto new_end = std::copy(std::make_move_iterator(v.begin()), + std::make_move_iterator(v.end()), begin()); + Destroy(new_end, end()); + } + tag().set_inline_size(v.size()); + } + return *this; + } + + InlinedVector& operator=(std::initializer_list<value_type> init) { + AssignRange(init.begin(), init.end()); + return *this; + } + + // InlinedVector::assign() + // + // Replaces the contents of the inlined vector with copies of those in the + // iterator range [first, last). + template <typename InputIterator> + void assign( + InputIterator first, InputIterator last, + typename std::enable_if<!std::is_integral<InputIterator>::value>::type* = + nullptr) { + AssignRange(first, last); + } + + // Overload of `InlinedVector::assign()` to take values from elements of an + // initializer list + void assign(std::initializer_list<value_type> init) { + AssignRange(init.begin(), init.end()); + } + + // Overload of `InlinedVector::assign()` to replace the first `n` elements of + // the inlined vector with `elem` values. + void assign(size_type n, const value_type& elem) { + if (n <= size()) { // Possibly shrink + std::fill_n(begin(), n, elem); + erase(begin() + n, end()); + return; + } + // Grow + reserve(n); + std::fill_n(begin(), size(), elem); + if (allocated()) { + UninitializedFill(allocated_space() + size(), allocated_space() + n, + elem); + tag().set_allocated_size(n); + } else { + UninitializedFill(inlined_space() + size(), inlined_space() + n, elem); + tag().set_inline_size(n); + } + } + + // InlinedVector::size() + // + // Returns the number of elements in the inlined vector. + size_type size() const noexcept { return tag().size(); } + + // InlinedVector::empty() + // + // Checks if the inlined vector has no elements. + bool empty() const noexcept { return (size() == 0); } + + // InlinedVector::capacity() + // + // Returns the number of elements that can be stored in an inlined vector + // without requiring a reallocation of underlying memory. Note that for + // most inlined vectors, `capacity()` should equal its initial size `N`; for + // inlined vectors which exceed this capacity, they will no longer be inlined, + // and `capacity()` will equal its capacity on the allocated heap. + size_type capacity() const noexcept { + return allocated() ? allocation().capacity() : N; + } + + // InlinedVector::max_size() + // + // Returns the maximum number of elements the 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 our size type. + return std::numeric_limits<size_type>::max() / 2; + } + + // InlinedVector::data() + // + // Returns a const T* pointer to elements of the inlined vector. This pointer + // can be used to access (but not modify) the contained elements. + // Only results within the range `[0,size())` are defined. + const_pointer data() const noexcept { + return allocated() ? allocated_space() : inlined_space(); + } + + // Overload of InlinedVector::data() to return a T* pointer to elements of the + // inlined vector. This pointer can be used to access and modify the contained + // elements. + pointer data() noexcept { + return allocated() ? allocated_space() : inlined_space(); + } + + // InlinedVector::clear() + // + // Removes all elements from the inlined vector. + 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(); + } + + // InlinedVector::at() + // + // Returns the ith element of an inlined vector. + const value_type& at(size_type i) const { + if (ABSL_PREDICT_FALSE(i >= size())) { + base_internal::ThrowStdOutOfRange( + "InlinedVector::at failed bounds check"); + } + return data()[i]; + } + + // InlinedVector::operator[] + // + // Returns the ith element of an inlined vector using the array operator. + const value_type& operator[](size_type i) const { + assert(i < size()); + return data()[i]; + } + + // Overload of InlinedVector::at() to return the ith element of an inlined + // vector. + value_type& at(size_type i) { + if (i >= size()) { + base_internal::ThrowStdOutOfRange( + "InlinedVector::at failed bounds check"); + } + return data()[i]; + } + + // Overload of InlinedVector::operator[] to return the ith element of an + // inlined vector. + value_type& operator[](size_type i) { + assert(i < size()); + return data()[i]; + } + + // InlinedVector::back() + // + // Returns a reference to the last element of an inlined vector. + value_type& back() { + assert(!empty()); + return at(size() - 1); + } + + // Overload of InlinedVector::back() returns a reference to the last element + // of an inlined vector of const values. + const value_type& back() const { + assert(!empty()); + return at(size() - 1); + } + + // InlinedVector::front() + // + // Returns a reference to the first element of an inlined vector. + value_type& front() { + assert(!empty()); + return at(0); + } + + // Overload of InlinedVector::front() returns a reference to the first element + // of an inlined vector of const values. + const value_type& front() const { + assert(!empty()); + return at(0); + } + + // InlinedVector::emplace_back() + // + // Constructs and appends an object to the inlined vector. + template <typename... Args> + void emplace_back(Args&&... args) { + size_type s = size(); + assert(s <= capacity()); + if (ABSL_PREDICT_FALSE(s == capacity())) { + GrowAndEmplaceBack(std::forward<Args>(args)...); + return; + } + assert(s < capacity()); + + value_type* space; + if (allocated()) { + tag().set_allocated_size(s + 1); + space = allocated_space(); + } else { + tag().set_inline_size(s + 1); + space = inlined_space(); + } + Construct(space + s, std::forward<Args>(args)...); + } + + // InlinedVector::push_back() + // + // Appends a const element to the inlined vector. + void push_back(const value_type& t) { emplace_back(t); } + + // Overload of InlinedVector::push_back() to append a move-only element to the + // inlined vector. + void push_back(value_type&& t) { emplace_back(std::move(t)); } + + // InlinedVector::pop_back() + // + // Removes the last element (which is destroyed) in the inlined vector. + void pop_back() { + 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); + } + } + + // InlinedVector::resize() + // + // 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); + + // Overload of InlinedVector::resize() to resize the inlined vector to contain + // `n` elements. If `n` is larger than the current size, enough copies of + // `elem` are appended to increase its size to `n`. + void resize(size_type n, const value_type& elem); + + // InlinedVector::begin() + // + // Returns an iterator to the beginning of the inlined vector. + iterator begin() noexcept { return data(); } + + // Overload of InlinedVector::begin() for returning a const iterator to the + // beginning of the inlined vector. + const_iterator begin() const noexcept { return data(); } + + // InlinedVector::cbegin() + // + // Returns a const iterator to the beginning of the inlined vector. + const_iterator cbegin() const noexcept { return begin(); } + + // InlinedVector::end() + // + // Returns an iterator to the end of the inlined vector. + iterator end() noexcept { return data() + size(); } + + // Overload of InlinedVector::end() for returning a const iterator to the end + // of the inlined vector. + const_iterator end() const noexcept { return data() + size(); } + + // InlinedVector::cend() + // + // Returns a const iterator to the end of the inlined vector. + const_iterator cend() const noexcept { return end(); } + + // InlinedVector::rbegin() + // + // Returns a reverse iterator from the end of the inlined vector. + reverse_iterator rbegin() noexcept { return reverse_iterator(end()); } + + // Overload of InlinedVector::rbegin() for returning a const reverse iterator + // from the end of the inlined vector. + const_reverse_iterator rbegin() const noexcept { + return const_reverse_iterator(end()); + } + + // InlinedVector::crbegin() + // + // Returns a const reverse iterator from the end of the inlined vector. + const_reverse_iterator crbegin() const noexcept { return rbegin(); } + + // InlinedVector::rend() + // + // Returns a reverse iterator from the beginning of the inlined vector. + reverse_iterator rend() noexcept { return reverse_iterator(begin()); } + + // Overload of InlinedVector::rend() for returning a const reverse iterator + // from the beginning of the inlined vector. + const_reverse_iterator rend() const noexcept { + return const_reverse_iterator(begin()); + } + + // InlinedVector::crend() + // + // Returns a reverse iterator from the beginning of the inlined vector. + const_reverse_iterator crend() const noexcept { return rend(); } + + // InlinedVector::emplace() + // + // Constructs and inserts an object to the inlined vector at the given + // `position`, returning an iterator pointing to the newly emplaced element. + template <typename... Args> + iterator emplace(const_iterator position, Args&&... args); + + // InlinedVector::insert() + // + // Inserts an element of the specified value at `position`, returning an + // iterator pointing to the newly inserted element. + iterator insert(const_iterator position, const value_type& v) { + return emplace(position, v); + } + + // Overload of InlinedVector::insert() for inserting an element of the + // specified rvalue, returning an iterator pointing to the newly inserted + // element. + iterator insert(const_iterator position, value_type&& v) { + return emplace(position, std::move(v)); + } + + // Overload of InlinedVector::insert() for inserting `n` elements of the + // specified value at `position`, returning an iterator pointing to the first + // of the newly inserted elements. + iterator insert(const_iterator position, size_type n, const value_type& v) { + return InsertWithCount(position, n, v); + } + + // Overload of `InlinedVector::insert()` to disambiguate the two + // three-argument overloads of `insert()`, returning an iterator pointing to + // the first of the newly inserted elements. + template <typename InputIterator, + typename = typename std::enable_if<std::is_convertible< + typename std::iterator_traits<InputIterator>::iterator_category, + std::input_iterator_tag>::value>::type> + iterator insert(const_iterator position, InputIterator first, + InputIterator last) { + using IterType = + typename std::iterator_traits<InputIterator>::iterator_category; + return InsertWithRange(position, first, last, IterType()); + } + + // Overload of InlinedVector::insert() for inserting a list of elements at + // `position`, returning an iterator pointing to the first of the newly + // inserted elements. + iterator insert(const_iterator position, + std::initializer_list<value_type> init) { + return insert(position, init.begin(), init.end()); + } + + // InlinedVector::erase() + // + // Erases the element at `position` of the inlined vector, returning an + // iterator pointing to the following element or the container's end if the + // last element was erased. + 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; + } + + // Overload of InlinedVector::erase() for erasing all elements in the + // iteraror range [first, last) in the inlined vector, returning an iterator + // pointing to the first element following the range erased, or the + // container's end if range included the container's last element. + iterator erase(const_iterator first, const_iterator last); + + // 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 that if `n` does not exceed the inlined vector's initial size `N`, + // `reserve()` will have no effect; if it does exceed its initial size, + // `reserve()` will trigger an initial allocation and move the inlined vector + // onto the heap. If the vector already exists on the heap and the requested + // size exceeds it, a reallocation will be performed. + void reserve(size_type n) { + if (n > capacity()) { + // Make room for new elements + EnlargeBy(n - size()); + } + } + + // InlinedVector::swap() + // + // Swaps the contents of this inlined vector with the contents of `other`. + void swap(InlinedVector& other); + + // InlinedVector::get_allocator() + // + // Returns the allocator of this inlined vector. + allocator_type get_allocator() const { return allocator(); } + + private: + static_assert(N > 0, "inlined vector with nonpositive size"); + + // It holds whether the vector is allocated or not in the lowest bit. + // The size is held in the high bits: + // size_ = (size << 1) | is_allocated; + class Tag { + public: + Tag() : size_(0) {} + size_type size() const { return size_ >> 1; } + void add_size(size_type n) { size_ += n << 1; } + void set_inline_size(size_type n) { size_ = n << 1; } + void set_allocated_size(size_type n) { size_ = (n << 1) | 1; } + bool allocated() const { return size_ & 1; } + + 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 of it for free. + class AllocatorAndTag : private allocator_type { + public: + explicit AllocatorAndTag(const allocator_type& a, Tag t = Tag()) + : allocator_type(a), tag_(t) { + } + 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, // NOLINT(runtime/references) + size_type capacity) + : capacity_(capacity), + buffer_(AllocatorTraits::allocate(a, capacity_)) {} + + void Dealloc(allocator_type& a) { // NOLINT(runtime/references) + AllocatorTraits::deallocate(a, buffer(), capacity()); + } + + size_type capacity() const { return capacity_; } + const value_type* buffer() const { return buffer_; } + value_type* buffer() { return buffer_; } + + private: + size_type capacity_; + value_type* 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); + } + + value_type* inlined_space() { + return reinterpret_cast<value_type*>(&rep_.inlined_storage.inlined); + } + const value_type* inlined_space() const { + return reinterpret_cast<const value_type*>(&rep_.inlined_storage.inlined); + } + + value_type* allocated_space() { + return allocation().buffer(); + } + const value_type* 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. + // 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() n places to the right. + // If the vector needs to be enlarged, memory will be allocated. + // Returns iterators 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). + 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> + void GrowAndEmplaceBack(Args&&... args) { + assert(size() == capacity()); + const size_type s = size(); + + Allocation new_allocation(allocator(), 2 * capacity()); + + 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); + } + + void InitAssign(size_type n); + void InitAssign(size_type n, const value_type& t); + + template <typename... Args> + void Construct(pointer p, Args&&... args) { + AllocatorTraits::construct(allocator(), p, std::forward<Args>(args)...); + } + + template <typename Iter> + void UninitializedCopy(Iter src, Iter src_last, value_type* dst) { + for (; src != src_last; ++dst, ++src) Construct(dst, *src); + } + + template <typename... Args> + void UninitializedFill(value_type* dst, value_type* dst_last, + const Args&... args) { + for (; dst != dst_last; ++dst) Construct(dst, args...); + } + + // Destroy [ptr, ptr_last) in place. + void Destroy(value_type* ptr, value_type* ptr_last); + + template <typename Iter> + void AppendRange(Iter first, Iter last, std::input_iterator_tag) { + std::copy(first, last, std::back_inserter(*this)); + } + + // Faster path for forward iterators. + template <typename Iter> + void AppendRange(Iter first, Iter last, std::forward_iterator_tag); + + template <typename Iter> + void AppendRange(Iter first, Iter last) { + using IterTag = typename std::iterator_traits<Iter>::iterator_category; + AppendRange(first, last, IterTag()); + } + + template <typename Iter> + void AssignRange(Iter first, Iter last, std::input_iterator_tag); + + // Faster path for forward iterators. + template <typename Iter> + void AssignRange(Iter first, Iter last, std::forward_iterator_tag); + + template <typename Iter> + void AssignRange(Iter first, Iter last) { + using IterTag = typename std::iterator_traits<Iter>::iterator_category; + AssignRange(first, last, IterTag()); + } + + iterator InsertWithCount(const_iterator position, size_type n, + const value_type& v); + + template <typename InputIter> + iterator InsertWithRange(const_iterator position, InputIter first, + InputIter last, std::input_iterator_tag); + template <typename ForwardIter> + iterator InsertWithRange(const_iterator position, ForwardIter first, + ForwardIter last, std::forward_iterator_tag); + + AllocatorAndTag allocator_and_tag_; + + // Either the inlined or allocated representation + union Rep { + // Use struct to perform indirection that solves a bizarre compilation + // error on Visual Studio (all known versions). + struct { + typename std::aligned_storage<sizeof(value_type), + alignof(value_type)>::type inlined[N]; + } inlined_storage; + struct { + typename std::aligned_storage<sizeof(Allocation), + alignof(Allocation)>::type allocation; + } allocation_storage; + } rep_; +}; + +// ----------------------------------------------------------------------------- +// InlinedVector Non-Member Functions +// ----------------------------------------------------------------------------- + +// swap() +// +// Swaps the contents of two inlined vectors. This convenience function +// simply calls InlinedVector::swap(other_inlined_vector). +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))) { + a.swap(b); +} + +// operator==() +// +// Tests the equivalency of the contents 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()); +} + +// operator!=() +// +// Tests the inequality of the contents 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 !(a == b); +} + +// operator<() +// +// Tests whether the contents of one inlined vector are less than the contents +// of another through a lexicographical comparison operation. +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()); +} + +// operator>() +// +// Tests whether the contents of one inlined vector are greater than the +// contents of another through a lexicographical comparison operation. +template <typename T, size_t N, typename A> +bool operator>(const InlinedVector<T, N, A>& a, + const InlinedVector<T, N, A>& b) { + return b < a; +} + +// operator<=() +// +// Tests whether the contents of one inlined vector are less than or equal to +// the contents of another through a lexicographical comparison operation. +template <typename T, size_t N, typename A> +bool operator<=(const InlinedVector<T, N, A>& a, + const InlinedVector<T, N, A>& b) { + return !(b < a); +} + +// operator>=() +// +// Tests whether the contents of one inlined vector are greater than or equal to +// the contents of another through a lexicographical comparison operation. +template <typename T, size_t N, typename A> +bool operator>=(const InlinedVector<T, N, A>& a, + const InlinedVector<T, N, A>& b) { + return !(a < b); +} + +// ----------------------------------------------------------------------------- +// Implementation of InlinedVector +// ----------------------------------------------------------------------------- +// +// Do not depend on any implementation details below this line. + +template <typename T, size_t N, typename A> +InlinedVector<T, N, A>::InlinedVector(const InlinedVector& v) + : allocator_and_tag_(v.allocator()) { + reserve(v.size()); + if (allocated()) { + UninitializedCopy(v.begin(), v.end(), allocated_space()); + tag().set_allocated_size(v.size()); + } else { + UninitializedCopy(v.begin(), v.end(), inlined_space()); + tag().set_inline_size(v.size()); + } +} + +template <typename T, size_t N, typename A> +InlinedVector<T, N, A>::InlinedVector(const InlinedVector& v, + const allocator_type& alloc) + : allocator_and_tag_(alloc) { + reserve(v.size()); + if (allocated()) { + UninitializedCopy(v.begin(), v.end(), allocated_space()); + tag().set_allocated_size(v.size()); + } else { + UninitializedCopy(v.begin(), v.end(), inlined_space()); + tag().set_inline_size(v.size()); + } +} + +template <typename T, size_t N, typename A> +InlinedVector<T, N, A>::InlinedVector(InlinedVector&& v) noexcept( + absl::allocator_is_nothrow<allocator_type>::value || + std::is_nothrow_move_constructible<value_type>::value) + : allocator_and_tag_(v.allocator_and_tag_) { + if (v.allocated()) { + // We can just steal the underlying buffer from the source. + // That leaves the source empty, so we clear its size. + init_allocation(v.allocation()); + v.tag() = Tag(); + } else { + UninitializedCopy(std::make_move_iterator(v.inlined_space()), + std::make_move_iterator(v.inlined_space() + v.size()), + inlined_space()); + } +} + +template <typename T, size_t N, typename A> +InlinedVector<T, N, A>::InlinedVector( + InlinedVector&& v, + const allocator_type& + alloc) noexcept(absl::allocator_is_nothrow<allocator_type>::value) + : allocator_and_tag_(alloc) { + if (v.allocated()) { + if (alloc == v.allocator()) { + // We can just steal the allocation from the source. + tag() = v.tag(); + init_allocation(v.allocation()); + v.tag() = Tag(); + } else { + // We need to use our own allocator + reserve(v.size()); + UninitializedCopy(std::make_move_iterator(v.begin()), + std::make_move_iterator(v.end()), allocated_space()); + tag().set_allocated_size(v.size()); + } + } else { + UninitializedCopy(std::make_move_iterator(v.inlined_space()), + std::make_move_iterator(v.inlined_space() + v.size()), + inlined_space()); + tag().set_inline_size(v.size()); + } +} + +template <typename T, size_t N, typename A> +void InlinedVector<T, N, A>::InitAssign(size_type n, const value_type& t) { + if (n > static_cast<size_type>(N)) { + Allocation new_allocation(allocator(), n); + init_allocation(new_allocation); + UninitializedFill(allocated_space(), allocated_space() + n, t); + tag().set_allocated_size(n); + } else { + UninitializedFill(inlined_space(), inlined_space() + n, t); + tag().set_inline_size(n); + } +} + +template <typename T, size_t N, typename A> +void InlinedVector<T, N, A>::InitAssign(size_type n) { + if (n > static_cast<size_type>(N)) { + 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 value_type& elem) { + size_type s = size(); + if (n < s) { + erase(begin() + n, end()); + return; + } + reserve(n); + assert(capacity() >= n); + + // Fill new space with copies of 'elem'. + if (allocated()) { + UninitializedFill(allocated_space() + s, allocated_space() + n, elem); + tag().set_allocated_size(n); + } else { + UninitializedFill(inlined_space() + s, inlined_space() + n, elem); + tag().set_inline_size(n); + } +} + +template <typename T, size_t N, typename A> +template <typename... Args> +typename InlinedVector<T, N, A>::iterator InlinedVector<T, N, A>::emplace( + const_iterator position, Args&&... args) { + assert(position >= begin()); + assert(position <= end()); + if (position == end()) { + emplace_back(std::forward<Args>(args)...); + return end() - 1; + } + size_type s = size(); + size_type idx = std::distance(cbegin(), position); + if (s == capacity()) { + EnlargeBy(1); + } + assert(s < capacity()); + iterator pos = begin() + idx; // Set 'pos' to a post-enlarge iterator. + + pointer space; + if (allocated()) { + tag().set_allocated_size(s + 1); + space = allocated_space(); + } else { + tag().set_inline_size(s + 1); + space = inlined_space(); + } + Construct(space + s, std::move(space[s - 1])); + std::move_backward(pos, space + s - 1, space + s); + Destroy(pos, pos + 1); + Construct(pos, std::forward<Args>(args)...); + + return pos; +} + +template <typename T, size_t N, typename A> +typename InlinedVector<T, N, A>::iterator InlinedVector<T, N, A>::erase( + const_iterator first, const_iterator last) { + assert(begin() <= first); + assert(first <= last); + assert(last <= end()); + + iterator range_start = const_cast<iterator>(first); + iterator range_end = const_cast<iterator>(last); + + 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 (&other == this) { + 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: A[b_size,a_size) -> B[b_size,a_size) + 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. + (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(static_cast<size_type>(N), 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 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; + } + return std::make_pair(start_used, start_raw); +} + +template <typename T, size_t N, typename A> +void InlinedVector<T, N, A>::Destroy(value_type* ptr, value_type* ptr_last) { + for (value_type* p = ptr; p != ptr_last; ++p) { + AllocatorTraits::destroy(allocator(), p); + } + + // 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. +#ifndef NDEBUG + if (ptr != ptr_last) { + memset(reinterpret_cast<void*>(ptr), 0xab, + sizeof(*ptr) * (ptr_last - ptr)); + } +#endif +} + +template <typename T, size_t N, typename A> +template <typename Iter> +void InlinedVector<T, N, A>::AppendRange(Iter first, Iter last, + std::forward_iterator_tag) { + using Length = typename std::iterator_traits<Iter>::difference_type; + Length 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 Iter> +void InlinedVector<T, N, A>::AssignRange(Iter first, Iter 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> +template <typename Iter> +void InlinedVector<T, N, A>::AssignRange(Iter first, Iter last, + std::forward_iterator_tag) { + using Length = typename std::iterator_traits<Iter>::difference_type; + Length 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> +auto InlinedVector<T, N, A>::InsertWithCount(const_iterator position, + size_type n, const value_type& v) + -> iterator { + assert(position >= begin() && position <= end()); + if (n == 0) return const_cast<iterator>(position); + std::pair<iterator, iterator> it_pair = ShiftRight(position, n); + std::fill(it_pair.first, it_pair.second, v); + UninitializedFill(it_pair.second, it_pair.first + n, v); + tag().add_size(n); + return it_pair.first; +} + +template <typename T, size_t N, typename A> +template <typename InputIter> +auto InlinedVector<T, N, A>::InsertWithRange(const_iterator position, + InputIter first, InputIter 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; +} + +// Overload of InlinedVector::InsertWithRange() +template <typename T, size_t N, typename A> +template <typename ForwardIter> +auto InlinedVector<T, N, A>::InsertWithRange(const_iterator position, + ForwardIter first, + ForwardIter last, + std::forward_iterator_tag) + -> iterator { + assert(position >= begin() && position <= end()); + if (first == last) { + return const_cast<iterator>(position); + } + using Length = typename std::iterator_traits<ForwardIter>::difference_type; + Length n = std::distance(first, last); + std::pair<iterator, iterator> it_pair = ShiftRight(position, n); + size_type used_spots = it_pair.second - it_pair.first; + ForwardIter open_spot = std::next(first, used_spots); + std::copy(first, open_spot, it_pair.first); + UninitializedCopy(open_spot, last, it_pair.second); + tag().add_size(n); + return it_pair.first; +} + +} // namespace absl + +#endif // ABSL_CONTAINER_INLINED_VECTOR_H_ |