diff --git a/llvm/include/llvm/ADT/STLExtras.h b/llvm/include/llvm/ADT/STLExtras.h --- a/llvm/include/llvm/ADT/STLExtras.h +++ b/llvm/include/llvm/ADT/STLExtras.h @@ -72,7 +72,6 @@ }; namespace detail { -template using void_t = void; template class Op, class... Args> struct detector { using value_t = std::false_type; }; diff --git a/llvm/include/llvm/ADT/STLForwardCompat.h b/llvm/include/llvm/ADT/STLForwardCompat.h --- a/llvm/include/llvm/ADT/STLForwardCompat.h +++ b/llvm/include/llvm/ADT/STLForwardCompat.h @@ -63,6 +63,9 @@ explicit in_place_index_t() = default; }; +template +using void_t = void; // NOLINT(readability-identifier-naming) + //===----------------------------------------------------------------------===// // Features from C++20 //===----------------------------------------------------------------------===// diff --git a/llvm/include/llvm/ADT/StaticVector.h b/llvm/include/llvm/ADT/StaticVector.h new file mode 100644 --- /dev/null +++ b/llvm/include/llvm/ADT/StaticVector.h @@ -0,0 +1,2051 @@ +//===- StaticVector.h - Fixed-sized vector implementation ----------C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +/// +/// \file StaticVector.h +/// `llvm::StaticVector` class definition. +/// +//===----------------------------------------------------------------------===// + +#pragma once +#ifndef LLVM_ADT_STATICVECTOR_H +#define LLVM_ADT_STATICVECTOR_H + +#include "llvm/ADT/ArrayRef.h" +#include "llvm/ADT/STLExtras.h" +#include "llvm/ADT/STLForwardCompat.h" +#include "llvm/Support/MathExtras.h" + +#include +#include +#include +#include +#include +#include +#include + +namespace llvm { + +namespace detail { +template +class is_iterator : public std::false_type {}; + +template +class is_iterator>::iterator_category>> + : public std::true_type {}; +} // namespace detail + +/// Determine whether a type is an iterator (i.e. belongs to any iterator +/// category). +template using is_iterator = detail::is_iterator; + +/// Determine whether a type belongs to the specified iterator category. +/// +/// @tparam T Iterator type to query. +/// @tparam Cat Iterator category `T` must belong to. +template ::value> +class is_iterator_category : public std::false_type {}; + +template +class is_iterator_category + : public // clang-format off + std::is_base_of< + Cat, + typename std::iterator_traits< + std::remove_reference_t + >::iterator_category + > // clang-format on +{}; + +template +using is_input_iterator = is_iterator_category; + +namespace detail { +template +class has_begin_member : public std::false_type {}; + +template +class has_begin_member().begin())>> + : public std::true_type {}; + +template +class has_begin_adl : public std::false_type {}; + +template +class has_begin_adl()))>> + : public std::true_type {}; + +template +class has_begin_std : public std::false_type {}; + +template +class has_begin_std()))>> + : public std::true_type {}; + +template +class has_end_member : public std::false_type {}; + +template +class has_end_member().end())>> + : public std::true_type {}; + +template +class has_end_adl : public std::false_type {}; + +template +class has_end_adl()))>> + : public std::true_type {}; + +template +class has_end_std : public std::false_type {}; + +template +class has_end_std()))>> + : public std::true_type {}; +} // namespace detail + +template +using has_begin = + llvm::disjunction, detail::has_begin_adl, + detail::has_begin_std>; + +template +using has_end = + llvm::disjunction, detail::has_end_adl, + detail::has_end_std>; + +namespace detail { +/// Determine the return type of the `begin` function associated with a +/// container type. +/// +/// The type evaluates to `void` if no `begin` function is available. +template ::value, + bool ADL = has_begin_adl::value, + bool STL = has_begin_std::value> +struct get_begin_type { + using type = void; +}; + +template +struct get_begin_type { + using type = decltype(std::declval().begin()); +}; + +template +struct get_begin_type { + using type = decltype(begin(std::declval())); +}; + +template +struct get_begin_type { + using type = decltype(std::begin(std::declval())); +}; + +/// Determine the return type of the `end` function associated with a +/// container type. +/// +/// The type evaluates to `void` if no `end` function is available. +template ::value, + bool ADL = has_end_adl::value, + bool STL = has_end_std::value> +struct get_end_type { + using type = void; +}; + +template +struct get_end_type { + using type = decltype(std::declval().end()); +}; + +template +struct get_end_type { + using type = decltype(end(std::declval())); +}; + +template +struct get_end_type { + using type = decltype(std::end(std::declval())); +}; +} // namespace detail + +template +using get_begin_type = detail::get_begin_type; + +template +using get_begin_type_t = typename get_begin_type::type; + +template +using get_end_type = detail::get_end_type; + +template +using get_end_type_t = typename get_end_type::type; + +/// Determine whether a presumed container type can be iterated in the forward +/// direction. +/// +/// The container type must have begin + end functions that return the same +/// type, and both those return types must belong to the input iterator +/// category. +template +using is_forward_iterable = // clang-format off + llvm::conjunction< + std::is_same, get_end_type_t>, + is_input_iterator< + get_begin_type_t + > + >; // clang-format on + +namespace detail { +template +class is_dereferenceable : public std::false_type {}; + +template +class is_dereferenceable())>> + : public std::true_type {}; +} // namespace detail +template using is_dereferenceable = detail::is_dereferenceable; + +namespace detail { +template ::value> +class is_convertible_input_iterator : public std::false_type {}; + +template +class is_convertible_input_iterator + : public std::is_convertible()), To> {}; +} // namespace detail +template +using is_convertible_input_iterator = + detail::is_convertible_input_iterator; + +template +using is_forward_iterable_and_convertible = // clang-format off + llvm::conjunction< + is_forward_iterable, + is_convertible_input_iterator,To> + >; // clang-format on + +namespace static_vector_detail { + +template class EmplaceImplSelector; + +} // namespace static_vector_detail + +template class StaticVectorStorage { +public: + using value_type = T; + using pointer = T *; + using reference = T &; + using const_pointer = T const *; + using const_reference = T const &; + using size_type = size_t; + + static constexpr size_type Capacity = C; + +private: + // Choose the minmally sized unsigned integer which can represent the capacity + // of the StaticVector. + // clang-format off + using MinSizeStorageT = + std::conditional_t(Capacity), uint8_t, + std::conditional_t(Capacity), uint16_t, + std::conditional_t(Capacity), uint32_t, + size_type + > + > + >; + // clang-format on + + // Determine whether 'l' < 'r' at compile-time. + // + // Only defined because you can't use a '<' in a template argument without + // triggering a parse error. + static constexpr bool lessThan(size_t L, size_t R) { return L < R; } + + // Only use the minimal storage size if it will actually reduce sizeof(*this). + using SizeStorageT = + std::conditional_t; + +private: + SizeStorageT Size; + std::aligned_storage_t Data[Capacity]; + +public: + constexpr StaticVectorStorage(size_t S = 0) : Size(S) {} + + class ZeroInitTag {}; + constexpr StaticVectorStorage(ZeroInitTag, size_t S = 0) : Size(S), Data{0} {} + + pointer data() { return reinterpret_cast(Data); } + + constexpr const_pointer data() const { + return reinterpret_cast(Data); + } + + constexpr size_type size() const { return Size; } + constexpr size_type capacity() const { return Capacity; } + + constexpr SizeStorageT rawSize() const { return Size; } + + void setSize(size_type NewSize) { + assert(NewSize <= capacity()); + Size = static_cast(NewSize); + } +}; + +template class StaticVectorStorage { +public: + using value_type = T; + using pointer = T *; + using reference = T &; + using const_pointer = T const *; + using const_reference = T const &; + using size_type = size_t; + + static constexpr size_type Capacity = 0; + + constexpr StaticVectorStorage(size_type S = 0) {} + + class ZeroInitTag {}; + constexpr StaticVectorStorage(ZeroInitTag) {} + + pointer data() { return nullptr; } + constexpr const_pointer data() const { return nullptr; } + + constexpr size_type size() const { return 0; } + constexpr size_type capacity() const { return 0; } + + constexpr size_type rawSize() const { return 0; } + void setSize(size_type NewSize) { assert(NewSize == 0); } +}; + +/// +/// Implements a version of the `vector` container with capacity fixed at +/// compile-time. +/// +/// Mostly follows the spec at: +/// http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p0843r2.html +/// +/// @tparam T Type of data to be stored in the `StaticVector`. +/// @tparam C Capacity of the `StaticVector` container in number of elements. +/// +/// @warning A large `C` implies a large `sizeof(StaticVector)`. Be mindful +/// of this relationship when declaring this container on the stack. +/// +/// This container will not heap-allocate any storage. All the storage is +/// determined up-front at compile-time and resides within this container. +/// +/// Essentially this container implements the `vector` API over top of a +/// C-array with some special care taken to ensure that `T` need not be default +/// constructible. +/// +/// You can emplace elements on the back at low cost, and the container will +/// track the number of valid elements for you. +/// +template +class StaticVector : private StaticVectorStorage { + using StorageT = StaticVectorStorage; + +public: + /// @name Basic container types + /// @{ + + /// Type of values stored in `StaticVector`. + using value_type = typename StorageT::value_type; + + /// Pointer type of values stored in `StaticVector`. + using pointer = typename StorageT::pointer; + + /// Reference type of values stored in `StaticVector`. + using reference = typename StorageT::reference; + + /// const-qualified pointer type of values stored in `StaticVector`. + using const_pointer = typename StorageT::const_pointer; + + /// const-qualified reference type of values stored in `StaticVector`. + using const_reference = typename StorageT::const_reference; + + /// Integer type used to represent size. + using size_type = typename StorageT::size_type; + /// @} + + /// @name Iterator types. + /// @{ + + /// Forward iterator for the `StaticVector` class. + using iterator = pointer; + + /// Forward const-iterator for the `StaticVector` class. + using const_iterator = const_pointer; + + /// Reverse iterator for the `StaticVector` class. + using reverse_iterator = std::reverse_iterator; + + /// Reverse const-iterator for the `StaticVector` class. + using const_reverse_iterator = std::reverse_iterator; + + /// @} + + enum : size_type { Capacity = StorageT::Capacity }; + +private: + /// True if it's cheap enough to take parameters by value. Doing so avoids + /// overhead related to mitigations for reference invalidation. + static constexpr bool TakesParamByValue = + std::is_trivially_copyable::value && sizeof(T) <= 2 * sizeof(void *); + + /// Either const T& or T, depending on whether it's cheap enough to take + /// parameters by value. + using ValueParamT = typename std::conditional::type; + +public: + /// @name Constructors + /// @{ + constexpr StaticVector() = default; + + StaticVector(StaticVector const &Other); + + StaticVector(StaticVector &&Other); + + explicit StaticVector(size_type N); + + StaticVector(size_type N, ValueParamT Val); + + template ::value> + * = nullptr> + StaticVector(InputIt First, InputIt Last); + + // clang-format off + template < + typename ContainerT, + std::enable_if_t< + llvm::conjunction< + negation>, + is_forward_iterable_and_convertible + >::value + > * = nullptr + > // clang-format on + StaticVector(ContainerT &&Container); + + template ::value> * = nullptr> + StaticVector(std::initializer_list IL); + /// @} + + /// @name Destructor + /// @{ + ~StaticVector(); + /// @} + + /// @name Assignment operators and methods + /// @{ + auto operator=(StaticVector const &Other) -> StaticVector &; + auto operator=(StaticVector &&Other) -> StaticVector &; + + template < // clang-format off + typename ContainerT, + std::enable_if_t< + conjunction< + negation>, + is_forward_iterable_and_convertible + >::value + > * = nullptr + > // clang-format on + auto operator=(ContainerT &&Container) -> StaticVector &; + + template ::value> + * = nullptr> + auto assign(InputIt First, InputIt Last) -> StaticVector &; + + auto assign(size_type N, ValueParamT Val) -> StaticVector &; + + template ::value> * = nullptr> + auto assign(std::initializer_list IL) -> StaticVector &; + + template < // clang-format off + typename ContainerT, + std::enable_if_t< + is_forward_iterable_and_convertible::value + > * = nullptr + > // clang-format on + auto assign(ContainerT &&Container) -> StaticVector &; + + /// @} + + /// @name Begin & End methods + /// @{ + auto begin() -> iterator; + auto end() -> iterator; + constexpr auto begin() const -> const_iterator; + constexpr auto end() const -> const_iterator; + constexpr auto cbegin() const -> const_iterator; + constexpr auto cend() const -> const_iterator; + + auto rbegin() -> reverse_iterator; + auto rend() -> reverse_iterator; + constexpr auto rbegin() const -> const_reverse_iterator; + constexpr auto rend() const -> const_reverse_iterator; + constexpr auto crbegin() const -> const_reverse_iterator; + constexpr auto crend() const -> const_reverse_iterator; + /// @} + + /// @name Element access methods + /// @{ + auto operator[](size_type Offs) -> reference; + auto operator[](size_type Offs) const -> const_reference; + + auto front() -> reference; + auto front() const -> const_reference; + + auto back() -> reference; + auto back() const -> const_reference; + + auto data() -> pointer; + constexpr auto data() const -> const_pointer; + /// @} + + /// @name Container queries + /// @{ + constexpr auto size() const -> size_type; + constexpr auto capacity() const -> size_type; + constexpr bool empty() const; + /// @} + + /// @name Container content manipulation methods + /// @{ + void resize(size_type NewSize); + void resize_for_overwrite( // NOLINT(readability-identifier-naming) + size_type NewSize); + + void resize(size_type, ValueParamT Val); + + template + void resize_emplace(size_type NewSize, + ArgsT &&...Args); // NOLINT(readability-identifier-naming) + + auto push_back(value_type &&Val) + -> reference; // NOLINT(readability-identifier-naming) + auto push_back(const_reference Val) + -> reference; // NOLINT(readability-identifier-naming) + + template + auto emplace_back(ArgsT &&...Args) + -> reference; // NOLINT(readability-identifier-naming) + + template + auto emplace(const_iterator Pos, ArgsT &&...Args) -> iterator; + + auto append(size_type N, ValueParamT Val) -> iterator; + + template ::value> + * = nullptr> + auto append(InputIt First, InputIt Last) -> iterator; + + template ::value> * = nullptr> + auto append(std::initializer_list IL) -> iterator; + + template < // clang-format off + typename ContainerT, + std::enable_if_t< + is_forward_iterable_and_convertible::value + > * = nullptr + > // clang-format on + auto append(ContainerT &&Container) -> iterator; + + auto insert(const_iterator Pos, const_reference Val) -> iterator; + auto insert(const_iterator Pos, value_type &&Val) -> iterator; + auto insert(const_iterator Pos, size_type N, ValueParamT Val) -> iterator; + + template ::value> + * = nullptr> + auto insert(const_iterator Pos, InputIt First, InputIt Last) -> iterator; + + template < // clang-format off + typename ContainerT, + std::enable_if_t< + is_forward_iterable_and_convertible::value + > * = nullptr + > // clang-format on + auto insert(const_iterator Pos, ContainerT &&Container) -> iterator; + + void clear(); + + void pop_back(); // NOLINT(readability-identifier-naming) + void pop_back_n(size_type N); // NOLINT(readability-identifier-naming) + auto pop_back_val() -> value_type; // NOLINT(readability-identifier-naming) + + auto erase(const_iterator Pos) -> iterator; + auto erase(const_iterator First, const_iterator Last) -> iterator; + /// @} + + /// @name Comparison operators + /// @{ + bool operator==(StaticVector const &RHS) const; + bool operator!=(StaticVector const &RHS) const; + bool operator<(StaticVector const &RHS) const; + bool operator>(StaticVector const &RHS) const; + bool operator<=(StaticVector const &RHS) const; + bool operator>=(StaticVector const &RHS) const; + /// @} + + operator ArrayRef() const { return {data(), size()}; } + operator MutableArrayRef() { return {data(), size()}; } + +private: + using StorageT::setSize; + + template + auto emplaceSingleArgImpl(const_iterator Pos, ArgT &&Args) -> iterator; + + template + auto emplaceImpl(const_iterator Pos, ArgsT &&...Args) -> iterator; + + template + friend class static_vector_detail::EmplaceImplSelector; + + template + static void construct(U *Ptr, ArgsT &&...Args) { + ::new ((void *)Ptr) U(std::forward(Args)...); + } + + template + static void constructRange(iterator B, iterator E, ArgsT &&...Args) { + for (; B != E; ++B) { + construct(B, std::forward(Args)...); + } + } + + template static void destroy(U *Ptr); + + static void destroyRange(iterator B, iterator E); + + template + static bool aliases(pointer B, pointer E, ArgsT &&...Args); +}; + +namespace static_vector_detail { + +template ::value> +class Destroy { +public: + void operator()(T *P) const { P->~T(); } + + void operator()(T *B, T *E) const { + for (auto *P = E - 1; P >= B; --P) + P->~T(); + } +}; + +// Trivial specialization. +template class Destroy { +public: + void operator()(T *P) const {} + void operator()(T *B, T *E) const {} +}; + +template +constexpr int aliasesSingle(T *B, T *E, bool &Result, ArgT &&Arg) { + return (Result |= std::addressof(Arg) >= B && std::addressof(Arg) <= E, 0); +} + +template constexpr void eval(Tn &&...) {} + +// Emplace implementation selector template. +// +// Special case implementation to deal with aliased copy insertion if the size +// of the parameter pack == 1. +template class EmplaceImplSelector { +public: + template + typename StaticVecT::iterator + operator()(StaticVecT &Vec, typename StaticVecT::const_iterator Pos, + ArgsT &&...Args) { + return Vec.emplaceImpl(Pos, std::forward(Args)...); + } +}; + +template class EmplaceImplSelector<1, ArgsT...> { +public: + template + typename StaticVecT::iterator + operator()(StaticVecT &Vec, typename StaticVecT::const_iterator Pos, + ArgsT &&...Args) { + return Vec.emplaceSingleArgImpl(Pos, std::forward(Args)...); + } +}; + +template +using GetEmplaceSelector = EmplaceImplSelector; + +} // namespace static_vector_detail + +/// +/// Destroy the object at the specified location. +/// +/// This function will generate no code if `T` is trivially destructible. +/// +/// @param Ptr Pointer to the object to destroy. +/// +template +template +inline void StaticVector::destroy(U *Ptr) { + static_vector_detail::Destroy()(Ptr); +} + +/// +/// Destroy elements in a specified range. +/// +/// This function will generate no code if `T` is trivially destructible. +/// +/// @param B Beginning of the range of elements to destroy. +/// @param E End of the range of elements to destroy. +/// +template +inline void StaticVector::destroyRange(iterator First, iterator Last) { + static_vector_detail::Destroy()(First, Last); +} + +/// +/// Determine whether any of the references in the parameter pack alias with the +/// specified range. +/// +/// @param B Beginning of the range to check for aliasing +/// @param E End of the range to check for aliasing. +/// @param Args Parameter pack to check for aliasing range `[B,E)`. +/// +/// @return `true` if any reference in the parameter pack aliases `[B,E)`; +/// `false` otherwise. +/// +template +template +inline bool StaticVector::aliases(pointer B, pointer E, ArgsT &&...Args) { + bool Result = false; + // evaluation order does not matter, so use a dummy function. + static_vector_detail::eval(static_vector_detail::aliasesSingle( + B, E, Result, std::forward(Args))...); + return Result; +} + +/// +/// Constructor with initial size specifier. +/// +/// @param N Number of default-constructed elements to add during +/// construction. +/// +/// @note Complexity = O(n) +/// +template +inline StaticVector::StaticVector(size_type N) : StorageT(N) { + constructRange(begin(), end()); +} + +/// +/// Constructor with initial size + value specifiers. +/// +/// @param N Number of elements to add during construction. +/// @param Val Value to copy while adding elements. +/// +/// @note Complexity = O(n) +/// +template +inline StaticVector::StaticVector(size_type N, ValueParamT Val) + : StorageT(N) { + std::uninitialized_fill_n(begin(), N, Val); +} + +/// +/// Copy constructor. +/// +/// Copy contents of another `StaticVector`. +/// +/// @param Other `StaticVector` object to copy. +/// +/// @note Complexity = O(n) +/// +template +inline StaticVector::StaticVector(StaticVector const &Other) + : StorageT(Other.size()) { + std::uninitialized_copy(Other.begin(), Other.end(), begin()); +} + +/// +/// Move constructor. +/// +/// Move all the elements from another `StaticVector` into this one. +/// +/// @param Other `StaticVector` object to copy. +/// +/// Notice that a move construction is not as fast as if the container were +/// heap allocated. We do need to visit all elements in `Other`. +/// +/// @note Complexity = O(n) +/// +template +inline StaticVector::StaticVector(StaticVector &&Other) + : StorageT(Other.size()) { + auto *First = Other.begin(); + auto *Last = Other.end(); + std::uninitialized_copy(std::make_move_iterator(First), + std::make_move_iterator(Last), begin()); +} + +/// +/// Copy range constructor +/// +/// Copy all the elements in the range `[first, Last). +/// +/// @param First First element to copy. +/// @param Last One-past the last element to copy. +/// +/// @note Complexity = O(n) +/// +template +template ::value> *> +inline StaticVector::StaticVector(InputIt First, InputIt Last) + : StorageT(static_cast(std::distance(First, Last))) { + std::uninitialized_copy(First, Last, begin()); +} + +/// +/// Copy from an unknown container type which is input iterable. +/// +/// @param Container The container to copy from. +/// +/// @note Complexity = O(n) +/// +template +template < // clang-format off + typename ContainerT, + std::enable_if_t< + llvm::conjunction< + negation,ContainerT>>, + is_forward_iterable_and_convertible + >::value + > * +> // clang-format on +inline StaticVector::StaticVector(ContainerT &&Container) + : StaticVector(adl_begin(Container), adl_end(Container)) {} + +/// +/// Initializer list constructor. +/// +/// Initialize the `StaticVector` to contain copies of elements in the +/// specified `initializer_list`. +/// +/// @param IL Initializer list to copy elements from. +/// +/// @note Complexity = O(n) +/// +template +template ::value> *> +inline StaticVector::StaticVector(std::initializer_list IL) + : StaticVector(IL.begin(), IL.end()) {} + +/// +/// Destructor. +/// +/// Destroy all currently valid elements in the container. This code will +/// evaluate to nothing if `ValueType` is trivially destructrible. +/// +/// @note Complexity = O(n) if `T` is non-trivially destructible; O(1) +/// otherwise. +/// +template inline StaticVector::~StaticVector() { + destroyRange(begin(), end()); +} + +/// +/// Copy assignment operator. +/// +/// Clear current contents and then copy elements from another `StaticVector`. +/// +/// @param Other `StaticVector` to copy contents from. +/// +/// @return A reference to this `StaticVector`. +/// +/// @note Complexity = O(n) +/// +template +inline auto StaticVector::operator=(StaticVector const &Other) + -> StaticVector & { + assign(Other.begin(), Other.end()); + return *this; +} + +/// +/// Move assignment operator. +/// +/// Clear current contents and then move elements from another `StaticVector`. +/// +/// @param Other `StaticVector` to move contents from. +/// +/// Notice that a move assignment is not as fast as if the container were heap +/// allocated. We do need to visit all elements in `Other`. +/// +/// @return A reference to this `StaticVector`. +/// +/// @note Complexity = O(n) +/// +template +inline auto StaticVector::operator=(StaticVector &&Other) + -> StaticVector & { + + size_type OtherSize = Other.size(); + size_type ThisSize = size(); + + if (ThisSize >= OtherSize) { + // assign common elements. + iterator NewEnd = begin(); + if (OtherSize) + NewEnd = std::move(Other.begin(), Other.end(), NewEnd); + + // Destroy extra elements. + destroyRange(NewEnd, end()); + } else { + // Move assign over current elements. + if (ThisSize) { + std::move(Other.begin(), Other.begin() + ThisSize, begin()); + } + // Move construct the new elements in place. + std::uninitialized_copy(std::make_move_iterator(Other.begin() + ThisSize), + std::make_move_iterator(Other.end()), + begin() + ThisSize); + } + setSize(OtherSize); + return *this; +} + +/// +/// Container assignment operator. +/// +/// Clear current contents and then copy elements from another container. +/// +/// This operator is only enabled when the `ContainerT` is forward iterable and +/// the type obtained from dereferencing the iterator is convertible to `T`. +/// +/// @return A reference to this `StaticVector`. +/// +/// @note Complexity = O(n) +/// +template +template < // clang-format off + typename ContainerT, + std::enable_if_t< + llvm::conjunction< + negation, ContainerT>>, + is_forward_iterable_and_convertible + >::value + > * +> // clang-format on +inline auto StaticVector::operator=(ContainerT &&Container) + -> StaticVector & { + assign(Container); + return *this; +} + +/// +/// Assign contents between specified input iterators. +/// +/// @param First iterator referring to the first element to copy. +/// @param Last iterator referring to one-past the last element to copy. +/// +/// @return A reference to this `StaticVector`. +/// +/// @note Complexity = O(n) +/// +template +template ::value> *> +inline auto StaticVector::assign(InputIt First, InputIt Last) + -> StaticVector & { + clear(); + append(First, Last); + return *this; +} + +/// +/// Assign contents to a specified number of values. +/// +/// Clear current contents and then assign `N` elements to `Val` at the front +/// of the container. +/// +/// @param N Number of elements to create during the assignment. +/// @param Val Value to assign to newly created elements. +/// +/// @return A reference to this `StaticVector`. +/// +/// @note Complexity = O(n) +/// +template +inline auto StaticVector::assign(size_type N, ValueParamT Val) + -> StaticVector & { + clear(); + append(N, Val); + return *this; +} + +/// +/// Copy assign from a std::initializer_list which holds elements of a type +/// which is convertible to `T`. +/// +/// @param IL `std::initializer_list` to copy assign from. +/// +/// @return A reference to this `StaticVector`. +/// +template +template ::value> *> +inline auto StaticVector::assign(std::initializer_list IL) + -> StaticVector & { + return assign(IL.begin(), IL.end()); +} + +/// +/// Copy assign from an arbitrary container which holds elements of a type which +/// is convertible to `T`. +/// +/// @param Container Reference to the container to copy assign from. +/// +/// @return A reference to this `StaticVector`. +/// +template +template < // clang-format off + typename ContainerT, + std::enable_if_t< + is_forward_iterable_and_convertible::value + > * +> // clang-format on +inline auto StaticVector::assign(ContainerT &&Container) + -> StaticVector & { + return assign(adl_begin(Container), adl_end(Container)); +} + +/// +/// Access a specified element in the `StaticVector`. +/// +/// An assertion will trigger when specified index is out of bounds. +/// +/// @param Offs Index of the element to access. +/// +/// @return A reference to the element at the specified index. +/// +/// @note Complexity = O(1) +/// +template +inline auto StaticVector::operator[](size_type Offs) -> reference { + assert(Offs < size()); + return data()[Offs]; +} + +/// +/// Access a specified element in the const-qualified `StaticVector`. +/// +/// An assertion will trigger when specified index is out of bounds. +/// +/// @param Offs Index of the element to access. +/// +/// @return A const-qualified reference to the element at the specified index. +/// +/// @note Complexity = O(1) +/// +template +inline auto StaticVector::operator[](size_type Offs) const + -> const_reference { + assert(Offs < size()); + return data()[Offs]; +} + +/// +/// Access the first element in the `StaticVector`. +/// +/// An assertion will trigger if the container is `Empty`. +/// +/// @return A reference to the first element in the `StaticVector`. +/// +/// @note Complexity = O(1) +/// +template +inline auto StaticVector::front() -> reference { + return operator[](0); +} + +/// +/// Access the first element in the const-qualified `StaticVector`. +/// +/// An assertion will trigger if the container is `Empty`. +/// +/// @return A const-qualified reference to the first element in the +/// `StaticVector`. +/// +/// @note Complexity = O(1) +/// +template +inline auto StaticVector::front() const -> const_reference { + return operator[](0); +} + +/// +/// Access the last element in the `StaticVector`. +/// +/// An assertion will trigger if the container is `Empty`. +/// +/// @return A reference to the last element in the `StaticVector`. +/// +/// @note Complexity = O(1) +/// +template +inline auto StaticVector::back() -> reference { + return operator[](size() - 1); +} + +/// +/// Access the last element in the const-qualified `StaticVector`. +/// +/// An assertion will trigger if the container is `Empty`. +/// +/// @return A const-qualified reference to the last element in the +/// `StaticVector`. +/// +/// @note Complexity = O(1) +/// +template +inline auto StaticVector::back() const -> const_reference { + return operator[](size() - 1); +} + +/// +/// Return a pointer to the data buffer. +/// +/// This method is provided to allow interoperation with C-APIs. +/// +/// @note Complexity = O(1) +/// +template +inline auto StaticVector::data() -> pointer { + return StorageT::data(); +} + +/// +/// Return a const-qualified pointer to the data buffer. +/// +/// This method is provided to allow interoperation with C-APIs. +/// +/// @note Complexity = O(1) +/// +template +constexpr auto StaticVector::data() const -> const_pointer { + return StorageT::data(); +} + +/// +/// Report the number of elements that can be accommodated by the storage. +/// +/// @return The maximum number of elements the container can store. +/// +/// @note Complexity = O(1) +/// +template +constexpr auto StaticVector::capacity() const -> size_type { + return StorageT::capacity(); +} + +/// +/// Report the current number of valid elements in the `StaticVector`. +/// +/// @return The number of elements currently contained by the `StaticVector`. +/// +/// @note Complexity = O(1) +/// +template +constexpr auto StaticVector::size() const -> size_type { + return StorageT::size(); +} + +/// +/// Report whether the `StaticVector` contains no elements. +/// +/// @return `true` if no elements are currently inserted into the container; +/// `false` otherwise. +/// +/// @note Complexity = O(1) +/// +template +constexpr bool StaticVector::empty() const { + return StorageT::rawSize() == 0; +} + +/// +/// Return a forward iterator corresponding to the front of the +/// `StaticVector`. +/// +/// @note Complexity = O(1) +/// +template +inline auto StaticVector::begin() -> iterator { + return data(); +} + +/// +/// Return a forward iterator corresponding to one-past the last valid +/// element in the `StaticVector`. +/// +/// @note Complexity = O(1) +/// +template +inline auto StaticVector::end() -> iterator { + return data() + size(); +} + +/// +/// Return a forward const-iterator corresponding to the front of the +/// `StaticVector`. +/// +/// @note Complexity = O(1) +/// +template +constexpr auto StaticVector::begin() const -> const_iterator { + return data(); +} + +/// +/// Return a forward constiterator corresponding to one-past the +/// last valid element in the `StaticVector`. +/// +/// @note Complexity = O(1) +/// +template +constexpr auto StaticVector::end() const -> const_iterator { + return data() + size(); +} + +/// +/// Return a forward const-iterator corresponding to the front of the +/// `StaticVector`. +/// +/// @note Complexity = O(1) +/// +template +constexpr auto StaticVector::cbegin() const -> const_iterator { + return begin(); +} + +/// +/// Return a forward constiterator corresponding to one-past the +/// last valid element in the `StaticVector`. +/// +/// @note Complexity = O(1) +/// +template +constexpr auto StaticVector::cend() const -> const_iterator { + return end(); +} + +/// +/// Return a reverse iterator corresponding to the back of the +/// `StaticVector`. +/// +/// @note Complexity = O(1) +/// +template +inline auto StaticVector::rbegin() -> reverse_iterator { + return reverse_iterator(end()); +} + +/// +/// Return a reverse iterator corresponding to one-before the first +/// valid element in the `StaticVector`. +/// +/// @note Complexity = O(1) +/// +template +inline auto StaticVector::rend() -> reverse_iterator { + return reverse_iterator(begin()); +} + +/// +/// Return a reverse const-iterator corresponding to the back of the +/// `StaticVector`. +/// +/// @note Complexity = O(1) +/// +template +constexpr auto StaticVector::rbegin() const -> const_reverse_iterator { + return const_reverse_iterator(end()); +} + +/// +/// Return a reverse const-iterator corresponding to one-before the +/// first valid element in the `StaticVector`. +/// +/// @note Complexity = O(1) +/// +template +constexpr auto StaticVector::rend() const -> const_reverse_iterator { + return const_reverse_iterator(begin()); +} + +/// +/// Return a reverse const-iterator corresponding to the back of the +/// `StaticVector`. +/// +/// @note Complexity = O(1) +/// +template +constexpr auto StaticVector::crbegin() const -> const_reverse_iterator { + return rbegin(); +} + +/// +/// Return a reverse const-iterator corresponding to one-before the +/// first valid element in the `StaticVector`. +/// +/// @note Complexity = O(1) +/// +template +constexpr auto StaticVector::crend() const -> const_reverse_iterator { + return rend(); +} + +/// +/// Resize the conainer to a specified size; emplace newly created +/// elements (if any). +/// +/// If the specified number of elements is smaller than the current capacity, +/// then elements at the back are destroyed (if applicable) and the container's +/// size is updated; no values are written / copied. +/// +/// New members of the `StaticVector` are constructed via perfect-forwarding +/// specified arguments in the `Args` parameter pack. +/// +/// @param NewSize New size of the `StaticVector`. +/// @param Args Parameter pack of constructor arguments to use while +/// constructing new elements (if any). +/// +/// @note Complexity = O(n) +/// +template +template +inline void StaticVector::resize_emplace(size_type NewSize, + ArgsT &&...Args) { + assert(NewSize <= capacity()); + + if (NewSize > size()) { + constructRange(end(), begin() + NewSize, std::forward(Args)...); + } else { + destroyRange(begin() + NewSize, end()); + } + + setSize(NewSize); +} + +/// +/// Resize the conainer to a specified size; default construct newly +/// created elements (if any). +/// +/// If the specified number of elements is smaller than the current capacity, +/// then elements at the back are destroyed (if applicable) and the container's +/// size is updated; no values are written / copied. +/// +/// New members of the `StaticVector` are default constructed. +/// +/// @param NewSize New size of the `StaticVector`. +/// +/// @note Complexity = O(m); where 'm' is the number of elements destroyed +/// or constructed. +/// +template +inline void StaticVector::resize(size_type NewSize) { + resize_emplace(NewSize); +} + +/// +/// Resize the conainer to a specified size; copy construct newly +/// created elements from specified value. +/// +/// If the specified number of elements is smaller than the current capacity, +/// then elements at the back are destroyed (if applicable) and the container's +/// size is updated; no values are written / copied. +/// +/// New members of the `StaticVector` are copy constructed. +/// +/// @param NewSize New size of the `StaticVector`. +/// @param Val Value to copy construct into new elements. +/// +/// @note Complexity = O(m); where 'm' is the number of elements destroyed +/// or constructed. +/// +template +inline void StaticVector::resize(size_type NewSize, ValueParamT Val) { + resize_emplace(NewSize, Val); +} + +/// +/// Resize the buffer, but POD data types will be left uninitialized. +/// +/// @param NewSize New number of elements to size of the storage buffer. +/// +/// @note Complexity = O(m); where 'm' is the number of elements destroyed or +/// constructed. +template +inline void StaticVector::resize_for_overwrite(size_type NewSize) { + + if (NewSize < size()) { + destroyRange(data() + NewSize, data() + size()); + setSize(NewSize); + } else if (NewSize > size()) { + assert(NewSize <= capacity()); + + for (auto I = end(), E = begin() + NewSize; I != E; ++I) + ::new (I) value_type; + + setSize(NewSize); + } +} + +/// +/// Insert a new element at the back, constructed with specified +/// arguments (saves creation of a temporary). +/// +/// @param Args Parameter pack of arguments to pass to the constructor of +/// the new element. +/// +/// @return A `reference` to the newly inserted object. +/// +/// @note Complexity = O(1) +/// +template +template +inline auto StaticVector::emplace_back(ArgsT &&...Args) -> reference { + assert(size() < capacity()); + construct(data() + size(), std::forward(Args)...); + + setSize(size() + 1); + return back(); +} + +/// +/// Move a new element to the back. +/// +/// @param Val Object to move into the new back element. +/// +/// @return A `reference` to the newly inserted object. +/// +/// @note Complexity = O(1) +/// +template +inline auto StaticVector::push_back(value_type &&Val) -> reference { + return emplace_back(std::move(Val)); +} + +/// +/// Copy a new element at the back. +/// +/// @param Val Object to copy to the new back element. +/// +/// @return A `reference` to the newly inserted object. +/// +/// @note Complexity = O(1) +/// +template +inline auto StaticVector::push_back(const_reference Val) -> reference { + return emplace_back(Val); +} + +/// +/// Insert an object constructed via specified arguments into this +/// `StaticVector` before a specified position. +/// +/// If `Pos == end()`, then the new members are inserted at the back of +/// the `StaticVector`. +/// +/// @param Pos Position in the current `StaticVector` to insert before. +/// @param Args Parameter pack of constructor args to pass to the newly +/// create element. +/// +/// @return An `iterator` which represents the newly inserted element. +/// +/// @note Complexity = O(m); where `m` is the number of items between +/// `Pos` and end(). +/// +template +template +auto StaticVector::emplace(const_iterator Pos, ArgsT &&...Args) + -> iterator { + using SelectorT = static_vector_detail::GetEmplaceSelector; + return SelectorT()(*this, Pos, std::forward(Args)...); +} + +/// +/// General implementation of emplace used for most parameter pack sizes. +/// +/// @param Pos Position in `this` to insert before. +/// @param Args Parameter pack used to construct the new element in place. +/// +/// @return An `iterator` which represents the newly inserted element. +/// +template +template +auto StaticVector::emplaceImpl(const_iterator Pos, ArgsT &&...Args) + -> iterator { + assert(size() < capacity()); + + size_type Idx = std::distance(cbegin(), Pos); + pointer PIns = data() + Idx; + std::aligned_storage_t AliasTmp; + + bool Aliases = aliases(PIns, end(), std::forward(Args)...); + + if (Aliases) { + // One of the constructor args aliases the buffer we're about to move. + // Construct a temporary and then move that into the final position after + // moving existing elements up. + construct(reinterpret_cast(std::addressof(AliasTmp)), + std::forward(Args)...); + } + + if (Idx != size()) { + construct(this->end(), std::move(back())); + std::move_backward(PIns, end() - 1, end()); + destroy(PIns); + } + + if (Aliases) { + construct(PIns, std::move(reinterpret_cast(AliasTmp))); + destroy((pointer)std::addressof(AliasTmp)); + } else { + construct(PIns, std::forward(Args)...); + } + + setSize(size() + 1); + + return PIns; +} + +/// +/// Specialized implementation of emplace used for size==1 parameter packs. +/// +/// This specialized implementation allows us to more efficiently handle the +/// case where the parameter aliases with the back range of the `StaticVector` +/// which will be moved upwards during the insertion. +/// +/// @param Pos Position in `this` to insert before. +/// @param Arg Parameter used to construct the new element in place. +/// +/// @return An `iterator` which represents the newly inserted element. +/// +template +template +auto StaticVector::emplaceSingleArgImpl(const_iterator Pos, ArgT &&Arg) + -> iterator { + assert(size() < capacity()); + + size_type Idx = std::distance(cbegin(), Pos); + pointer PIns = data() + Idx; + auto *ConstructPtr = std::addressof(Arg); + + bool Aliases = aliases(PIns, end(), std::forward(Arg)); + + if (Idx != size()) { + construct(this->end(), std::move(back())); + std::move_backward(PIns, end() - 1, end()); + destroy(PIns); + } + + if (Aliases) { + // Adjust the pointer... 'ConstructPtr' might not be a pointer to a + // `value_type`. It could be a member of a `value_type` which is + // convertible to a `value_type`. Therefore, we need to cast to char and + // adjust by sizeof(value_type) to ensure we're pointing at the right thing. + char *AdjustPtr = const_cast((char const *)ConstructPtr); + AdjustPtr += sizeof(value_type); + ConstructPtr = (decltype(ConstructPtr))(AdjustPtr); + } + + construct(PIns, std::forward(*ConstructPtr)); + + setSize(size() + 1); + + return PIns; +} + +/// +/// Insert a new elements by copy before the specified position. +/// +/// If `Pos == end()`, the new member is appended. +/// +/// @param Pos Position in the `StaticVector` to insert before. +/// @param Val Object to copy-construct into new elements inserted. +/// +/// @return `Pos` if `n == 0`; otherwise an `iterator` which represents +/// the first newly inserted item. +/// +/// @note Complexity = O(m + N); where `m` is `std::distance(Pos, end())`. +/// +template +auto StaticVector::insert(const_iterator Pos, const_reference Val) + -> iterator { + return emplace(Pos, Val); +} + +/// +/// Insert a new elements via move construction before the specified position. +/// +/// If `Pos == end()`, the new member is appended. +/// +/// @param Pos Position in the `StaticVector` to insert before. +/// @param Val Object to copy-construct into new elements inserted. +/// +/// @return `Pos` if `n == 0`; otherwise an `iterator` which represents +/// the first newly inserted item. +/// +/// @note Complexity = O(m + N); where `m` is `std::distance(Pos, end())`. +/// +template +auto StaticVector::insert(const_iterator Pos, value_type &&Val) + -> iterator { + return emplace(Pos, std::move(Val)); +} + +/// +/// Insert `N` new elements before the specified position. +/// +/// If `Pos == end()`, then the new members are inserted at the back +/// of the `StaticVector`. +/// +/// @param Pos Position in the `StaticVector` to insert before. +/// @param N Number of elements to insert. +/// @param Val Object to copy-construct into new elements inserted. +/// +/// @return `Pos` if `n == 0`; otherwise an `iterator` which represents +/// the first newly inserted item. +/// +/// @note Complexity = O(m + N); where `m` is `std::distance(Pos, end())`. +/// +template +auto StaticVector::insert(const_iterator Pos, size_type N, + ValueParamT Val) -> iterator { + assert(Pos >= cbegin()); + assert(Pos <= cend()); + assert(size() + N <= capacity()); + + iterator I = begin() + std::distance(cbegin(), Pos); + iterator OldEnd = end(); + + value_type const *CopyPtr = std::addressof(Val); + + if (size_t(OldEnd - I) >= N) { + // If there are more elements between the insertion point and the end of the + // range than there are being inserted, we can use a simple approach to + // insertion. Since we already reserved space, we know that this won't + // reallocate the vector. + append(std::make_move_iterator(OldEnd - N), + std::make_move_iterator(OldEnd)); + + // Copy the existing elements that get replaced. + std::move_backward(I, OldEnd - N, OldEnd); + + // If we just moved the element we're inserting, be sure to update + // the reference (never happens if TakesParamByValue). + if (!TakesParamByValue && I <= CopyPtr && CopyPtr < OldEnd) + CopyPtr += N; + + std::fill_n(I, N, *CopyPtr); + } else { + // Otherwise, we're inserting more elements than exist already, and we're + // not inserting at the end. + + // Move over the elements that we're about to overwrite. + setSize(size() + N); + size_t NumOverwritten = OldEnd - I; + + std::uninitialized_copy(std::make_move_iterator(I), + std::make_move_iterator(OldEnd), end() - N); + + // If we just moved the element we're inserting, be sure to update + // the reference (never happens if TakesParamByValue). + if (!TakesParamByValue && I <= CopyPtr && CopyPtr < end()) + CopyPtr += N; + + // Replace the overwritten part. + std::fill_n(I, NumOverwritten, *CopyPtr); + + // Insert the non-overwritten middle part. + std::uninitialized_fill_n(OldEnd, N - NumOverwritten, *CopyPtr); + } + + return I; +} + +/// +/// Insert new elements from an iterator range. +/// +/// Insert new vector members which are copies of values described by +/// input iterator range `[First, Last)` before the specified position +/// (`Pos`). If `Pos == end()`, then the new members are inserted at +/// the back of the `StaticVector`. +/// +/// @param Pos Position in the `StaticVector` to insert before. +/// @param First Input iterator referencing the first element to insert. +/// @param Last Input iterator referencing one-past the last element to insert. +/// +/// @return `Pos` if `First == Last`; otherwise an `iterator` which +/// represents the first newly inserted item. +/// +/// @note Complexity = O(m + `std::distance(First, Last)`); where `m` is the +/// number of items between `Pos` and `end()`. +/// +template +template ::value> *> +auto StaticVector::insert(const_iterator Pos, InputIt First, InputIt Last) + -> iterator { + iterator I = begin() + std::distance(cbegin(), Pos); + iterator OldEnd = end(); + + if (I == OldEnd) { + append(First, Last); + } else { + + size_t N = std::distance(First, Last); + assert(size() + N <= capacity()); + + // If there are more elements between the insertion point and the end of the + // range than there are being inserted, we can use a simple approach to + // insertion. Since we already reserved space, we know that this won't + // reallocate the vector. + if (size_t(OldEnd - I) >= N) { + append(std::make_move_iterator(end() - N), + std::make_move_iterator(end())); + + // Copy the existing elements that get replaced. + std::move_backward(I, OldEnd - N, OldEnd); + + std::copy(First, Last, I); + } else { + // Otherwise, we're inserting more elements than exist already, and we're + // not inserting at the end. + + // Move over the elements that we're about to overwrite. + setSize(size() + N); + size_t NumOverwritten = OldEnd - I; + std::uninitialized_copy(std::make_move_iterator(I), + std::make_move_iterator(OldEnd), + end() - NumOverwritten); + + // Replace the overwritten part. + for (T *J = I; NumOverwritten > 0; --NumOverwritten) { + *J = *First; + ++J; + ++First; + } + + // Insert the non-overwritten middle part. + std::uninitialized_copy(First, Last, OldEnd); + } + } + return I; +} + +/// +/// Insert a copy of values in the specified container before the +/// specified position. +/// +/// @note Shortcut method for common call: +/// `insert(Pos, container.begin(), container.end());` +/// +/// @param Pos Position in the `StaticVector` to insert before. +/// @param Container Container whose contents to insert before `Pos`. +/// +/// @return `Pos` if `Container` is empty; otherwise an `iterator` which +/// represents the first newly inserted item. +/// +/// @note Complexity = O(m + n); +/// where `m` is the number of items between `Pos` and `end()`. +/// +template +template < // clang-format off + typename ContainerT, + std::enable_if_t< + is_forward_iterable_and_convertible::value + > * +> // clang-format on +inline auto StaticVector::insert(const_iterator Pos, + ContainerT &&Container) -> iterator { + return insert(Pos, adl_begin(Container), adl_end(Container)); +} + +/// +/// Append `N` new elements before the specified position. +/// +/// @param N Number of elements to append. +/// @param Val Object to copy-construct into new elements inserted. +/// +/// @return `Pos` if `n == 0`; otherwise an `iterator` which represents +/// the first newly inserted item. +/// +/// @note Complexity = O(N) +/// +template +inline auto StaticVector::append(size_type N, ValueParamT Val) + -> iterator { + auto I = end(); + resize_emplace(size() + N, Val); + return I; +} + +/// +/// Append copies of values in a range. +/// +/// @param First First position in the range to copy +/// @param Last One-past the last position to copy. +/// +/// @note Complexity = O(std::distance(First, Last)) +/// +template +template ::value> *> +auto StaticVector::append(InputIt First, InputIt Last) -> iterator { + + size_type Count = std::distance(First, Last); + assert(Count + size() <= capacity()); + + auto *NewElemPos = end(); + std::uninitialized_copy(First, Last, NewElemPos); + setSize(size() + Count); + + return NewElemPos; +} + +/// +/// Append copies of elements in a `std::initializer_list` holding a type which +/// is convertible to `T`. +/// +/// @param IL initializer_list to append copies from. +/// +/// @note Complexity = O(n) +/// +template +template ::value> *> +inline auto StaticVector::append(std::initializer_list IL) + -> iterator { + return append(IL.begin(), IL.end()); +} + +/// +/// Append copies of elements in an arbitrary container holding a type which is +/// convertible to `T`. +/// +/// @param Container The container to append copies from. +/// +/// @note Complexity = O(n) +/// +// clang-format off +template +template < + typename ContainerT, + std::enable_if_t< + is_forward_iterable_and_convertible::value + > * +> // clang-format on +inline auto StaticVector::append(ContainerT &&Container) -> iterator { + return append(adl_begin(Container), adl_end(Container)); +} + +/// +/// Mark the current `StaticVector` as empty and destroy all elememts. +/// +/// @note Complexity = O(1) if `T` is trivially destructible; +/// O(n) otherwise. +/// +template inline void StaticVector::clear() { + destroyRange(begin(), end()); + setSize(0); +} + +/// +/// Decrease the size of the container by `1`, removing the last element. +/// +/// Asserts if the container is `Empty()`. +/// +/// @note Complexity = O(1) +/// +template inline void StaticVector::pop_back() { + assert(size() >= 1); + setSize(size() - 1); + destroy(end()); +} + +/// +/// Decrease the size of the container by `N`, removing the last elements. +/// +/// Asserts if the container does not have `N` elements to remove. +/// +/// @note Complexity = O(1) +/// +template +inline void StaticVector::pop_back_n(size_type N) { + assert(size() >= N); + destroyRange(end() - N, end()); + setSize(size() - N); +} + +/// +/// Decrease the size of the container by `1`, removing the last element. +/// +/// Asserts if the container is `empty()`. +/// +/// @note Complexity = O(1) +/// +template +inline auto StaticVector::pop_back_val() -> value_type { + auto OldBack = back(); + pop_back(); + return OldBack; +} + +/// +/// Erase a single element at a specified position from the +/// `StaticVector`. +/// +/// If `Pos == end()`, then no member is removed. +/// +/// @param Pos Position of the element to erase from the `StaticVector`. +/// +/// @return An `iterator` referring to the new location of the element that +/// followed the erased element. This is `end()` if the operation erased +/// the last element. +/// +/// @note Complexity = O(m); where `m` is the number of items between `Pos` +/// and `end()`. +/// +template +auto StaticVector::erase(const_iterator Pos) -> iterator { + assert(Pos >= cbegin()); + assert(Pos <= cend()); + + auto I = const_cast(Pos); + std::move(I + 1, end(), I); + pop_back(); + return I; +} + +/// +/// Erase a sequence of elements in the range `[First, Last)` from the +/// `StaticVector`. +/// +/// If `First == Last`, then no member is erased. +/// +/// @param First The first element in the `StaticVector` to erase. +/// @param Last One-past the last element in the `StaticVector` to erase. +/// +/// @return An `iterator` referring to the new location of the element that +/// followed the erased element(s). This is `end()` if the operation +/// erased the last element. +/// +/// @note Complexity = O(m); where `m` is the number of items between `First` +/// and `end()`. +/// +template +auto StaticVector::erase(const_iterator First, const_iterator Last) + -> iterator { + assert(First <= Last); + assert(First >= cbegin()); + assert(First < cend()); + assert(Last >= cbegin()); + assert(Last <= cend()); + + auto F = const_cast(First); + auto L = const_cast(Last); + + iterator I = std::move(L, end(), F); + destroyRange(I, end()); + setSize(std::distance(begin(), I)); + return F; +} + +/// +/// Compare two `StaticVector`s for equality. +/// +/// @return `true` if the containers are equal in size and value; `false` +/// otherwise. +/// +/// @note Complexity = O(n) +/// +template +inline bool StaticVector::operator==(StaticVector const &RHS) const { + return size() == RHS.size() && + std::equal(begin(), end(), RHS.begin(), RHS.end()); +} + +/// +/// Compare two `StaticVector`s for inequality. +/// +/// @return `false` if the containers are equal in size and value; `true` +/// otherwise. +/// +/// @note Complexity = O(n) +/// +template +inline bool StaticVector::operator!=(StaticVector const &RHS) const { + return !operator==(RHS); +} + +/// +/// Compare to another `StaticVector` for less-than relation using +/// lexicographical comparison. +/// +/// @note Complexity = O(n) +/// +template +inline bool StaticVector::operator<(StaticVector const &RHS) const { + return std::lexicographical_compare(begin(), end(), RHS.begin(), RHS.end()); +} + +/// +/// Compare to another `StaticVector` for greater-than relation using +/// lexicographical comparison. +/// +/// @note Complexity = O(n) +/// +template +inline bool StaticVector::operator>(StaticVector const &RHS) const { + return RHS.operator<(*this); +} + +/// +/// Compare to another `StaticVector` for less-than or equal relation using +/// lexicographical comparison. +/// +/// @note Complexity = O(n) +/// +template +inline bool StaticVector::operator<=(StaticVector const &RHS) const { + return !RHS.operator<(*this); +} + +/// +/// Compare to another `StaticVector` for greater-than or equal +/// relation using lexicographical comparison. +/// +/// @note Complexity = O(n) +/// +template +inline bool StaticVector::operator>=(StaticVector const &RHS) const { + return !operator<(RHS); +} + +} // namespace llvm + +#endif // LLVM_ADT_STATICVECTOR_H diff --git a/llvm/include/llvm/DebugInfo/CodeView/TypeRecord.h b/llvm/include/llvm/DebugInfo/CodeView/TypeRecord.h --- a/llvm/include/llvm/DebugInfo/CodeView/TypeRecord.h +++ b/llvm/include/llvm/DebugInfo/CodeView/TypeRecord.h @@ -12,7 +12,7 @@ #include "llvm/ADT/APSInt.h" #include "llvm/ADT/ArrayRef.h" #include "llvm/ADT/Optional.h" -#include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/StaticVector.h" #include "llvm/ADT/StringRef.h" #include "llvm/DebugInfo/CodeView/CVRecord.h" #include "llvm/DebugInfo/CodeView/CodeView.h" @@ -683,7 +683,7 @@ MaxArgs }; - SmallVector ArgIndices; + StaticVector ArgIndices; }; // LF_VFTABLE diff --git a/llvm/include/llvm/Support/YAMLTraits.h b/llvm/include/llvm/Support/YAMLTraits.h --- a/llvm/include/llvm/Support/YAMLTraits.h +++ b/llvm/include/llvm/Support/YAMLTraits.h @@ -11,6 +11,7 @@ #include "llvm/ADT/Optional.h" #include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/StaticVector.h" #include "llvm/ADT/StringExtras.h" #include "llvm/ADT/StringMap.h" #include "llvm/ADT/StringRef.h" @@ -1937,6 +1938,11 @@ SmallVectorImpl, std::enable_if_t::flow>::value>> : SequenceTraitsImpl, SequenceElementTraits::flow> {}; +template +struct SequenceTraits< + StaticVector, + std::enable_if_t::flow>::value>> + : SequenceTraitsImpl, SequenceElementTraits::flow> {}; // Sequences of fundamental types use flow formatting. template diff --git a/llvm/lib/Target/X86/X86ISelLowering.cpp b/llvm/lib/Target/X86/X86ISelLowering.cpp --- a/llvm/lib/Target/X86/X86ISelLowering.cpp +++ b/llvm/lib/Target/X86/X86ISelLowering.cpp @@ -23,6 +23,7 @@ #include "X86TargetObjectFile.h" #include "llvm/ADT/SmallBitVector.h" #include "llvm/ADT/SmallSet.h" +#include "llvm/ADT/StaticVector.h" #include "llvm/ADT/Statistic.h" #include "llvm/ADT/StringExtras.h" #include "llvm/ADT/StringSwitch.h" @@ -27954,7 +27955,7 @@ /* 8 */ 0, /* 9 */ 0, /* a */ 0, /* b */ 0, /* c */ 0, /* d */ 0, /* e */ 0, /* f */ 0}; - SmallVector LUTVec; + StaticVector LUTVec; for (int i = 0; i < NumBytes; ++i) LUTVec.push_back(DAG.getConstant(LUT[i % 16], DL, MVT::i8)); SDValue InRegLUT = DAG.getBuildVector(CurrVT, DL, LUTVec); diff --git a/llvm/unittests/ADT/CMakeLists.txt b/llvm/unittests/ADT/CMakeLists.txt --- a/llvm/unittests/ADT/CMakeLists.txt +++ b/llvm/unittests/ADT/CMakeLists.txt @@ -67,6 +67,7 @@ SparseBitVectorTest.cpp SparseMultiSetTest.cpp SparseSetTest.cpp + StaticVectorTest.cpp StatisticTest.cpp StringExtrasTest.cpp StringMapTest.cpp diff --git a/llvm/unittests/ADT/StaticVectorTest.cpp b/llvm/unittests/ADT/StaticVectorTest.cpp new file mode 100644 --- /dev/null +++ b/llvm/unittests/ADT/StaticVectorTest.cpp @@ -0,0 +1,1150 @@ +//===- llvm/unittest/ADT/StaticVectorTest.cpp -------------------*- C++ -*-===// +// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "llvm/ADT/StaticVector.h" +#include "llvm/ADT/ArrayRef.h" +#include "llvm/Support/Compiler.h" +#include "gtest/gtest.h" +#include +#include + +using namespace llvm; + +namespace { + +/// An llvm::ArrayRef derived class which is only forward iterable via adl begin +/// and end functions. +template class ForceADL : private ArrayRef { + using BaseT = ArrayRef; + +public: + using BaseT::BaseT; + using iterator = typename BaseT::iterator; + + friend iterator begin(ForceADL const &AR) { + return reinterpret_cast(AR).begin(); + } + + friend iterator end(ForceADL const &AR) { + return reinterpret_cast(AR).end(); + } +}; + +/// A helper class that counts the total number of constructor and +/// destructor calls. +class Constructable { +private: + static int numConstructorCalls; + static int numMoveConstructorCalls; + static int numCopyConstructorCalls; + static int numDestructorCalls; + static int numAssignmentCalls; + static int numMoveAssignmentCalls; + static int numCopyAssignmentCalls; + + bool constructed; + int value; + +public: + Constructable() : constructed(true), value(0) { ++numConstructorCalls; } + + Constructable(int val) : constructed(true), value(val) { + ++numConstructorCalls; + } + + Constructable(const Constructable &src) : constructed(true) { + value = src.value; + ++numConstructorCalls; + ++numCopyConstructorCalls; + } + + Constructable(Constructable &&src) : constructed(true) { + value = src.value; + src.value = 0; + ++numConstructorCalls; + ++numMoveConstructorCalls; + } + + ~Constructable() { + EXPECT_TRUE(constructed); + ++numDestructorCalls; + constructed = false; + } + + Constructable &operator=(const Constructable &src) { + EXPECT_TRUE(constructed); + value = src.value; + ++numAssignmentCalls; + ++numCopyAssignmentCalls; + return *this; + } + + Constructable &operator=(Constructable &&src) { + EXPECT_TRUE(constructed); + value = src.value; + src.value = 0; + ++numAssignmentCalls; + ++numMoveAssignmentCalls; + return *this; + } + + int getValue() const { return abs(value); } + + static void reset() { + numConstructorCalls = 0; + numMoveConstructorCalls = 0; + numCopyConstructorCalls = 0; + numDestructorCalls = 0; + numAssignmentCalls = 0; + numMoveAssignmentCalls = 0; + numCopyAssignmentCalls = 0; + } + + static int getNumConstructorCalls() { return numConstructorCalls; } + + static int getNumMoveConstructorCalls() { return numMoveConstructorCalls; } + + static int getNumCopyConstructorCalls() { return numCopyConstructorCalls; } + + static int getNumDestructorCalls() { return numDestructorCalls; } + + static int getNumAssignmentCalls() { return numAssignmentCalls; } + + static int getNumMoveAssignmentCalls() { return numMoveAssignmentCalls; } + + static int getNumCopyAssignmentCalls() { return numCopyAssignmentCalls; } + + friend bool operator==(const Constructable &c0, const Constructable &c1) { + return c0.getValue() == c1.getValue(); + } + + friend bool LLVM_ATTRIBUTE_UNUSED operator!=(const Constructable &c0, + const Constructable &c1) { + return c0.getValue() != c1.getValue(); + } +}; + +int Constructable::numConstructorCalls; +int Constructable::numCopyConstructorCalls; +int Constructable::numMoveConstructorCalls; +int Constructable::numDestructorCalls; +int Constructable::numAssignmentCalls; +int Constructable::numCopyAssignmentCalls; +int Constructable::numMoveAssignmentCalls; + +struct NonCopyable { + NonCopyable() {} + NonCopyable(NonCopyable &&) {} + NonCopyable &operator=(NonCopyable &&) { return *this; } + +private: + NonCopyable(const NonCopyable &) = delete; + NonCopyable &operator=(const NonCopyable &) = delete; +}; + +LLVM_ATTRIBUTE_USED void CompileTest() { + StaticVector V; + V.resize(42); +} + +class StaticVectorTestBase : public testing::Test { +protected: + void SetUp() override { Constructable::reset(); } + + template void assertEmpty(VectorT &v) { + // Size tests + EXPECT_EQ(0u, v.size()); + EXPECT_TRUE(v.empty()); + + // Iterator tests + EXPECT_TRUE(v.begin() == v.end()); + } + + // Assert that v contains the specified values, in order. + template + void assertValuesInOrder(VectorT &v, size_t size, ...) { + EXPECT_EQ(size, v.size()); + + va_list ap; + va_start(ap, size); + for (size_t i = 0; i < size; ++i) { + int value = va_arg(ap, int); + EXPECT_EQ(value, v[i].getValue()); + } + + va_end(ap); + } + + template + void assertValuesInOrder(VectorT &v, llvm::ArrayRef AR) { + EXPECT_EQ(AR.size(), v.size()); + + auto I1 = AR.begin(); + auto E1 = AR.end(); + + auto I2 = v.begin(); + auto E2 = v.end(); + + for (; I1 != E1 && I2 != E2; ++I1, ++I2) { + auto Expected = *I1; + auto Value = I2->getValue(); + EXPECT_EQ(Value, Expected); + } + } + + // Generate a sequence of values to initialize the vector. + template + void makeSequence(VectorT &v, int start, int end) { + for (int i = start; i <= end; ++i) { + v.push_back(Constructable(i)); + } + } +}; + +// Test fixture class +template +class StaticVectorTest : public StaticVectorTestBase { +protected: + VectorT theVector; + VectorT otherVector; +}; + +typedef ::testing::Types, + StaticVector, + StaticVector> + StaticVectorTestTypes; +TYPED_TEST_SUITE(StaticVectorTest, StaticVectorTestTypes, ); + +// Constructor test. +TYPED_TEST(StaticVectorTest, ConstructorNonIterTest) { + SCOPED_TRACE("ConstructorTest"); + this->theVector = StaticVector(2, 2); + this->assertValuesInOrder(this->theVector, 2u, 2, 2); +} + +// Constructor test. +TYPED_TEST(StaticVectorTest, ConstructorIterTest) { + SCOPED_TRACE("ConstructorTest"); + int arr[] = {1, 2, 3}; + this->theVector = + StaticVector(std::begin(arr), std::end(arr)); + this->assertValuesInOrder(this->theVector, 3u, 1, 2, 3); +} + +// New vector test. +TYPED_TEST(StaticVectorTest, EmptyVectorTest) { + SCOPED_TRACE("EmptyVectorTest"); + this->assertEmpty(this->theVector); + EXPECT_TRUE(this->theVector.rbegin() == this->theVector.rend()); + EXPECT_EQ(0, Constructable::getNumConstructorCalls()); + EXPECT_EQ(0, Constructable::getNumDestructorCalls()); +} + +// Simple insertions and deletions. +TYPED_TEST(StaticVectorTest, PushPopTest) { + SCOPED_TRACE("PushPopTest"); + + // Track whether the vector will potentially have to grow. + bool const RequiresGrowth = this->theVector.capacity() < 3; + if (RequiresGrowth) + return; + + // Push an element + this->theVector.emplace_back(1); + + EXPECT_EQ(1, Constructable::getNumConstructorCalls()); + + // Size tests + this->assertValuesInOrder(this->theVector, 1u, 1); + EXPECT_FALSE(this->theVector.begin() == this->theVector.end()); + EXPECT_FALSE(this->theVector.empty()); + + // Push another element + this->theVector.push_back(Constructable(2)); + this->assertValuesInOrder(this->theVector, 2u, 1, 2); + + // Insert at beginning. Reserve space to avoid reference invalidation from + // this->theVector[1]. + this->theVector.insert(this->theVector.begin(), this->theVector[1]); + this->assertValuesInOrder(this->theVector, 3u, 2, 1, 2); + + // Pop one element + this->theVector.pop_back(); + this->assertValuesInOrder(this->theVector, 2u, 2, 1); + + // Pop remaining elements + this->theVector.pop_back_n(2); + this->assertEmpty(this->theVector); + + // Check number of constructor calls. Should be 2 for each list element, + // one for the argument to push_back, one for the argument to insert, + // and one for the list element itself. + if (!RequiresGrowth) { + EXPECT_EQ(5, Constructable::getNumConstructorCalls()); + EXPECT_EQ(5, Constructable::getNumDestructorCalls()); + } else { + // If we had to grow the vector, these only have a lower bound, but should + // always be equal. + EXPECT_LE(5, Constructable::getNumConstructorCalls()); + EXPECT_EQ(Constructable::getNumConstructorCalls(), + Constructable::getNumDestructorCalls()); + } +} + +// Clear test. +TYPED_TEST(StaticVectorTest, ClearTest) { + SCOPED_TRACE("ClearTest"); + + this->makeSequence(this->theVector, 1, 2); + this->theVector.clear(); + + this->assertEmpty(this->theVector); + EXPECT_EQ(4, Constructable::getNumConstructorCalls()); + EXPECT_EQ(4, Constructable::getNumDestructorCalls()); +} + +// Resize smaller test. +TYPED_TEST(StaticVectorTest, ResizeShrinkTest) { + SCOPED_TRACE("ResizeShrinkTest"); + + this->makeSequence(this->theVector, 1, 3); + this->theVector.resize(1); + + this->assertValuesInOrder(this->theVector, 1u, 1); + EXPECT_EQ(6, Constructable::getNumConstructorCalls()); + EXPECT_EQ(5, Constructable::getNumDestructorCalls()); +} + +// Resize bigger test. +TYPED_TEST(StaticVectorTest, ResizeGrowTest) { + SCOPED_TRACE("ResizeGrowTest"); + + this->theVector.resize(2); + + EXPECT_EQ(2, Constructable::getNumConstructorCalls()); + EXPECT_EQ(0, Constructable::getNumDestructorCalls()); + EXPECT_EQ(2u, this->theVector.size()); +} + +TYPED_TEST(StaticVectorTest, ResizeWithElementsTest) { + this->theVector.resize(2); + + Constructable::reset(); + + this->theVector.resize(4); + + size_t Ctors = Constructable::getNumConstructorCalls(); + EXPECT_TRUE(Ctors == 2 || Ctors == 4); + size_t MoveCtors = Constructable::getNumMoveConstructorCalls(); + EXPECT_TRUE(MoveCtors == 0 || MoveCtors == 2); + size_t Dtors = Constructable::getNumDestructorCalls(); + EXPECT_TRUE(Dtors == 0 || Dtors == 2); +} + +// Resize with fill value. +TYPED_TEST(StaticVectorTest, ResizeFillTest) { + SCOPED_TRACE("ResizeFillTest"); + + this->theVector.resize(3, Constructable(77)); + this->assertValuesInOrder(this->theVector, 3u, 77, 77, 77); +} + +TEST(StaticVectorTest, ResizeForOverwrite) { + // Inline storage. + StaticVector V; + V.push_back(5U); + V.pop_back(); + V.resize_for_overwrite(V.size() + 1U); + EXPECT_EQ(5U, V.back()); + V.pop_back(); + V.resize(V.size() + 1); + EXPECT_EQ(0U, V.back()); +} + +// Iteration tests. +TYPED_TEST(StaticVectorTest, IterationTest) { + this->makeSequence(this->theVector, 1, 2); + + // Forward Iteration + typename TypeParam::iterator it = this->theVector.begin(); + EXPECT_TRUE(*it == this->theVector.front()); + EXPECT_TRUE(*it == this->theVector[0]); + EXPECT_EQ(1, it->getValue()); + ++it; + EXPECT_TRUE(*it == this->theVector[1]); + EXPECT_TRUE(*it == this->theVector.back()); + EXPECT_EQ(2, it->getValue()); + ++it; + EXPECT_TRUE(it == this->theVector.end()); + --it; + EXPECT_TRUE(*it == this->theVector[1]); + EXPECT_EQ(2, it->getValue()); + --it; + EXPECT_TRUE(*it == this->theVector[0]); + EXPECT_EQ(1, it->getValue()); + + // Reverse Iteration + typename TypeParam::reverse_iterator rit = this->theVector.rbegin(); + EXPECT_TRUE(*rit == this->theVector[1]); + EXPECT_EQ(2, rit->getValue()); + ++rit; + EXPECT_TRUE(*rit == this->theVector[0]); + EXPECT_EQ(1, rit->getValue()); + ++rit; + EXPECT_TRUE(rit == this->theVector.rend()); + --rit; + EXPECT_TRUE(*rit == this->theVector[0]); + EXPECT_EQ(1, rit->getValue()); + --rit; + EXPECT_TRUE(*rit == this->theVector[1]); + EXPECT_EQ(2, rit->getValue()); +} + +// Swap test. +TYPED_TEST(StaticVectorTest, SwapTest) { + SCOPED_TRACE("SwapTest"); + + this->makeSequence(this->theVector, 1, 2); + std::swap(this->theVector, this->otherVector); + + this->assertEmpty(this->theVector); + this->assertValuesInOrder(this->otherVector, 2u, 1, 2); +} + +// Append test +TYPED_TEST(StaticVectorTest, AppendTest) { + SCOPED_TRACE("AppendTest"); + + this->makeSequence(this->otherVector, 2, 3); + + this->theVector.push_back(Constructable(1)); + this->theVector.append(this->otherVector.begin(), this->otherVector.end()); + + this->assertValuesInOrder(this->theVector, 3u, 1, 2, 3); +} + +// Append repeated test +TYPED_TEST(StaticVectorTest, AppendRepeatedTest) { + SCOPED_TRACE("AppendRepeatedTest"); + + this->theVector.push_back(Constructable(1)); + this->theVector.append(2, Constructable(77)); + this->assertValuesInOrder(this->theVector, 3u, 1, 77, 77); +} + +// Append test +TYPED_TEST(StaticVectorTest, AppendNonIterTest) { + SCOPED_TRACE("AppendRepeatedTest"); + + this->theVector.push_back(Constructable(1)); + this->theVector.append(2, 7); + this->assertValuesInOrder(this->theVector, 3u, 1, 7, 7); +} + +struct output_iterator { + typedef std::output_iterator_tag iterator_category; + typedef int value_type; + typedef int difference_type; + typedef value_type *pointer; + typedef value_type &reference; + operator int() { return 2; } + operator Constructable() { return 7; } +}; + +TYPED_TEST(StaticVectorTest, AppendRepeatedNonForwardIterator) { + SCOPED_TRACE("AppendRepeatedTest"); + + this->theVector.push_back(Constructable(1)); + this->theVector.append(output_iterator(), output_iterator()); + this->assertValuesInOrder(this->theVector, 3u, 1, 7, 7); +} + +TYPED_TEST(StaticVectorTest, AppendStaticVector) { + SCOPED_TRACE("AppendStaticVector"); + + StaticVector otherVector = {7, 7}; + this->theVector.push_back(Constructable(1)); + this->theVector.append(otherVector); + this->assertValuesInOrder(this->theVector, 3u, 1, 7, 7); +} + +TYPED_TEST(StaticVectorTest, AppendArrayRefTest) { + SCOPED_TRACE("AppendArrayRefTest"); + auto IL = {1, 2, 3}; + ArrayRef AR(IL); + this->theVector.append(AR); + this->assertValuesInOrder(this->theVector, IL); +} + +TYPED_TEST(StaticVectorTest, AppendInitializerListTest) { + SCOPED_TRACE("AppendInitializerListTest"); + auto IL = {1, 2, 3}; + this->theVector.append(IL); + this->assertValuesInOrder(this->theVector, IL); +} + +TYPED_TEST(StaticVectorTest, AppendContainerADL) { + SCOPED_TRACE("AppendContainerADL"); + int iarr[]{1, 2, 3}; + this->theVector.append(ForceADL(iarr)); + this->assertValuesInOrder(this->theVector, {1, 2, 3}); +} + +TYPED_TEST(StaticVectorTest, AppendRangeTest) { + SCOPED_TRACE("AppendRangeTest"); + int iarr[]{1, 2, 3}; + this->theVector.append(make_range(std::begin(iarr), std::end(iarr))); + this->assertValuesInOrder(this->theVector, {1, 2, 3}); +} + +TYPED_TEST(StaticVectorTest, AppendCArrayTest) { + SCOPED_TRACE("AppendCArrayTest"); + const int iarr[]{1, 2, 3}; + this->theVector.append(iarr); + this->assertValuesInOrder(this->theVector, iarr); +} + +// Assign test +TYPED_TEST(StaticVectorTest, AssignTest) { + SCOPED_TRACE("AssignTest"); + + this->theVector.push_back(Constructable(1)); + this->theVector.assign(2, Constructable(77)); + this->assertValuesInOrder(this->theVector, 2u, 77, 77); +} + +// Assign test +TYPED_TEST(StaticVectorTest, AssignRangeTest) { + SCOPED_TRACE("AssignTest"); + + this->theVector.push_back(Constructable(1)); + int arr[] = {1, 2, 3}; + this->theVector.assign(std::begin(arr), std::end(arr)); + this->assertValuesInOrder(this->theVector, 3u, 1, 2, 3); +} + +// Assign test +TYPED_TEST(StaticVectorTest, AssignNonIterTest) { + SCOPED_TRACE("AssignTest"); + + this->theVector.push_back(Constructable(1)); + this->theVector.assign(2, 7); + this->assertValuesInOrder(this->theVector, 2u, 7, 7); +} + +TYPED_TEST(StaticVectorTest, AssignStaticVector) { + SCOPED_TRACE("AssignStaticVector"); + + StaticVector otherVector = {7, 7}; + this->theVector.push_back(Constructable(1)); + this->theVector.assign(otherVector); + this->assertValuesInOrder(this->theVector, 2u, 7, 7); +} + +TYPED_TEST(StaticVectorTest, AssignCArrayVector) { + SCOPED_TRACE("AssignCArrayVector"); + + int Arr[]{1, 3, 5}; + + this->theVector.emplace_back(1); + + // Us the assign() member function to assign. + this->theVector.assign(Arr); + this->assertValuesInOrder(this->theVector, Arr); + + this->theVector.clear(); + this->theVector.emplace_back(1); + + // Use operator=() to assign. + this->theVector = Arr; + this->assertValuesInOrder(this->theVector, Arr); +} + +TYPED_TEST(StaticVectorTest, AssignInitializerList) { + SCOPED_TRACE("AssignInitializerList"); + + this->theVector.emplace_back(1); + this->theVector.assign({2, 4, 6, 8}); + this->assertValuesInOrder(this->theVector, {2, 4, 6, 8}); + + this->theVector.clear(); + this->theVector.emplace_back(1); + this->theVector = {2, 4, 6, 8}; + this->assertValuesInOrder(this->theVector, {2, 4, 6, 8}); +} + +TYPED_TEST(StaticVectorTest, AssignArrayRef) { + SCOPED_TRACE("AssignArrayRef"); + + auto IL = {2, 4, 6, 8}; + ArrayRef AR(IL); + + this->theVector.emplace_back(1); + this->theVector.assign(AR); + this->assertValuesInOrder(this->theVector, AR); + + this->theVector.clear(); + + this->theVector.emplace_back(1); + this->theVector = AR; + this->assertValuesInOrder(this->theVector, AR); +} + +// Move-assign test +TYPED_TEST(StaticVectorTest, MoveAssignTest) { + SCOPED_TRACE("MoveAssignTest"); + + // Set up our vector with a single element, but enough capacity for 4. + this->theVector.emplace_back(1); + + // Set up the other vector with 2 elements. + this->otherVector.push_back(Constructable(2)); + this->otherVector.push_back(Constructable(3)); + + // Move-assign from the other vector. + this->theVector = std::move(this->otherVector); + + // Make sure we have the right result. + this->assertValuesInOrder(this->theVector, 2u, 2, 3); + + // Make sure the # of constructor/destructor calls line up. There + // are two live objects after clearing the other vector. + this->otherVector.clear(); + EXPECT_EQ(Constructable::getNumConstructorCalls() - 2, + Constructable::getNumDestructorCalls()); + + // There shouldn't be any live objects any more. + this->theVector.clear(); + EXPECT_EQ(Constructable::getNumConstructorCalls(), + Constructable::getNumDestructorCalls()); +} + +// Erase a single element +TYPED_TEST(StaticVectorTest, EraseTest) { + SCOPED_TRACE("EraseTest"); + + this->makeSequence(this->theVector, 1, 3); + const auto &theConstVector = this->theVector; + this->theVector.erase(theConstVector.begin()); + this->assertValuesInOrder(this->theVector, {2, 3}); +} + +// Erase a range of elements +TYPED_TEST(StaticVectorTest, EraseRangeTest) { + SCOPED_TRACE("EraseRangeTest"); + + this->makeSequence(this->theVector, 1, 3); + const auto &theConstVector = this->theVector; + this->theVector.erase(theConstVector.begin(), theConstVector.begin() + 2); + this->assertValuesInOrder(this->theVector, 1u, 3); +} + +// Insert a single element. +TYPED_TEST(StaticVectorTest, InsertTest) { + SCOPED_TRACE("InsertTest"); + + this->makeSequence(this->theVector, 1, 3); + typename TypeParam::iterator I = + this->theVector.insert(this->theVector.begin() + 1, Constructable(77)); + EXPECT_EQ(this->theVector.begin() + 1, I); + this->assertValuesInOrder(this->theVector, {1, 77, 2, 3}); +} + +// Insert a copy of a single element. +TYPED_TEST(StaticVectorTest, InsertCopy) { + SCOPED_TRACE("InsertTest"); + + this->makeSequence(this->theVector, 1, 3); + Constructable C(77); + typename TypeParam::iterator I = + this->theVector.insert(this->theVector.begin() + 1, C); + EXPECT_EQ(this->theVector.begin() + 1, I); + this->assertValuesInOrder(this->theVector, {1, 77, 2, 3}); +} + +// Insert repeated elements. +TYPED_TEST(StaticVectorTest, InsertRepeatedTest) { + SCOPED_TRACE("InsertRepeatedTest"); + + if (this->theVector.capacity() < 6) + return; + + this->makeSequence(this->theVector, 1, 4); + Constructable::reset(); + auto I = + this->theVector.insert(this->theVector.begin() + 1, 2, Constructable(16)); + // Move construct the top element into newly allocated space, and optionally + // reallocate the whole buffer, move constructing into it. + // FIXME: This is inefficient, we shouldn't move things into newly allocated + // space, then move them up/around, there should only be 2 or 4 move + // constructions here. + EXPECT_TRUE(Constructable::getNumMoveConstructorCalls() == 2 || + Constructable::getNumMoveConstructorCalls() == 6); + // Move assign the next two to shift them up and make a gap. + EXPECT_EQ(1, Constructable::getNumMoveAssignmentCalls()); + // Copy construct the two new elements from the parameter. + EXPECT_EQ(2, Constructable::getNumCopyAssignmentCalls()); + // All without any copy construction. + EXPECT_EQ(0, Constructable::getNumCopyConstructorCalls()); + EXPECT_EQ(this->theVector.begin() + 1, I); + this->assertValuesInOrder(this->theVector, {1, 16, 16, 2, 3, 4}); +} + +TYPED_TEST(StaticVectorTest, InsertRepeatedNonIterTest) { + SCOPED_TRACE("InsertRepeatedNonIterTest"); + + if (this->theVector.capacity() < 6) + return; + + this->makeSequence(this->theVector, 1, 4); + Constructable::reset(); + auto I = this->theVector.insert(this->theVector.begin() + 1, 2, 7); + EXPECT_EQ(this->theVector.begin() + 1, I); + this->assertValuesInOrder(this->theVector, {1, 7, 7, 2, 3, 4}); +} + +TYPED_TEST(StaticVectorTest, InsertRepeatedAtEndTest) { + SCOPED_TRACE("InsertRepeatedAtEndTest"); + + if (this->theVector.capacity() < 6) + return; + + this->makeSequence(this->theVector, 1, 4); + Constructable::reset(); + auto I = this->theVector.insert(this->theVector.end(), 2, Constructable(16)); + // Just copy construct them into newly allocated space + EXPECT_EQ(2, Constructable::getNumCopyConstructorCalls()); + // Move everything across if reallocation is needed. + EXPECT_TRUE(Constructable::getNumMoveConstructorCalls() == 0 || + Constructable::getNumMoveConstructorCalls() == 4); + // Without ever moving or copying anything else. + EXPECT_EQ(0, Constructable::getNumCopyAssignmentCalls()); + EXPECT_EQ(0, Constructable::getNumMoveAssignmentCalls()); + + EXPECT_EQ(this->theVector.begin() + 4, I); + this->assertValuesInOrder(this->theVector, {1, 2, 3, 4, 16, 16}); +} + +TYPED_TEST(StaticVectorTest, InsertRepeatedEmptyTest) { + SCOPED_TRACE("InsertRepeatedEmptyTest"); + + if (this->theVector.capacity() < 4) + return; + + auto I = this->theVector.insert(this->theVector.end(), 2, 10); + EXPECT_EQ(I, this->theVector.begin()); + EXPECT_EQ(0, Constructable::getNumMoveConstructorCalls()); + EXPECT_EQ(2, Constructable::getNumCopyConstructorCalls()); + EXPECT_EQ(0, Constructable::getNumMoveAssignmentCalls()); + EXPECT_EQ(0, Constructable::getNumCopyAssignmentCalls()); + this->assertValuesInOrder(this->theVector, {10, 10}); + + this->makeSequence(this->theVector, 12, 13); + + // Empty insert. + EXPECT_EQ( + this->theVector.end(), + this->theVector.insert(this->theVector.end(), 0, Constructable(42))); + EXPECT_EQ(this->theVector.begin() + 1, + this->theVector.insert(this->theVector.begin() + 1, 0, + Constructable(42))); +} + +// Insert range. +TYPED_TEST(StaticVectorTest, InsertRangeTest) { + SCOPED_TRACE("InsertRangeTest"); + + if (this->theVector.capacity() < 6) + return; + + Constructable Arr[3] = {Constructable(77), Constructable(77), + Constructable(77)}; + + this->makeSequence(this->theVector, 1, 3); + Constructable::reset(); + auto I = this->theVector.insert(this->theVector.begin() + 1, Arr, Arr + 3); + // Move construct the top 3 elements into newly allocated space. + // Possibly move the whole sequence into new space first. + // FIXME: This is inefficient, we shouldn't move things into newly allocated + // space, then move them up/around, there should only be 2 or 3 move + // constructions here. + EXPECT_TRUE(Constructable::getNumMoveConstructorCalls() == 2 || + Constructable::getNumMoveConstructorCalls() == 5); + // Copy assign the lower 2 new elements into existing space. + EXPECT_EQ(2, Constructable::getNumCopyAssignmentCalls()); + // Copy construct the third element into newly allocated space. + EXPECT_EQ(1, Constructable::getNumCopyConstructorCalls()); + EXPECT_EQ(this->theVector.begin() + 1, I); + this->assertValuesInOrder(this->theVector, 6u, 1, 77, 77, 77, 2, 3); +} + +TYPED_TEST(StaticVectorTest, InsertRangeAtEndTest) { + SCOPED_TRACE("InsertRangeAtEndTest"); + + if (this->theVector.capacity() < 6) + return; + + Constructable Arr[3] = {Constructable(77), Constructable(77), + Constructable(77)}; + + this->makeSequence(this->theVector, 1, 3); + + // Insert at end. + Constructable::reset(); + auto I = this->theVector.insert(this->theVector.end(), Arr, Arr + 3); + // Copy construct the 3 elements into new space at the top. + EXPECT_EQ(3, Constructable::getNumCopyConstructorCalls()); + // Don't copy/move anything else. + EXPECT_EQ(0, Constructable::getNumCopyAssignmentCalls()); + // Reallocation might occur, causing all elements to be moved into the new + // buffer. + EXPECT_TRUE(Constructable::getNumMoveConstructorCalls() == 0 || + Constructable::getNumMoveConstructorCalls() == 3); + EXPECT_EQ(0, Constructable::getNumMoveAssignmentCalls()); + EXPECT_EQ(this->theVector.begin() + 3, I); + this->assertValuesInOrder(this->theVector, 6u, 1, 2, 3, 77, 77, 77); +} + +TYPED_TEST(StaticVectorTest, InsertEmptyRangeTest) { + SCOPED_TRACE("InsertRangeTest"); + auto IL = {1, 2, 3}; + auto I = + this->theVector.insert(this->theVector.begin(), IL.begin(), IL.end()); + EXPECT_EQ(I, this->theVector.begin()); + this->assertValuesInOrder(this->theVector, IL); + + // Empty insert. + EXPECT_EQ(this->theVector.end(), + this->theVector.insert(this->theVector.end(), + this->theVector.begin(), + this->theVector.begin())); + EXPECT_EQ(this->theVector.begin() + 1, + this->theVector.insert(this->theVector.begin() + 1, + this->theVector.begin(), + this->theVector.begin())); +} + +TYPED_TEST(StaticVectorTest, InsertCArrayTest) { + SCOPED_TRACE("InsertCArrayTest"); + const int Arr[]{1, 2, 3}; + + this->theVector.emplace_back(4); + + auto I = this->theVector.insert(this->theVector.begin(), Arr); + EXPECT_EQ(I, this->theVector.begin()); + this->assertValuesInOrder(this->theVector, {1, 2, 3, 4}); +} + +TYPED_TEST(StaticVectorTest, InsertInializerListTest) { + SCOPED_TRACE("InsertInializerListTest"); + auto IL = {1, 2, 3}; + + this->theVector.emplace_back(4); + + auto I = this->theVector.insert(this->theVector.begin(), IL); + EXPECT_EQ(I, this->theVector.begin()); + this->assertValuesInOrder(this->theVector, {1, 2, 3, 4}); +} + +TYPED_TEST(StaticVectorTest, InsertArrayRefTest) { + SCOPED_TRACE("InsertArrayRefTest"); + auto IL = {2, 3, 4}; + + this->theVector.emplace_back(1); + + auto I = this->theVector.insert(this->theVector.end(), IL); + EXPECT_EQ(I, this->theVector.begin() + 1); + this->assertValuesInOrder(this->theVector, {1, 2, 3, 4}); +} + +// Comparison tests. +TYPED_TEST(StaticVectorTest, ComparisonTest) { + SCOPED_TRACE("ComparisonTest"); + + this->makeSequence(this->theVector, 1, 3); + this->makeSequence(this->otherVector, 1, 3); + + EXPECT_TRUE(this->theVector == this->otherVector); + EXPECT_FALSE(this->theVector != this->otherVector); + + this->otherVector.clear(); + this->makeSequence(this->otherVector, 2, 4); + + EXPECT_FALSE(this->theVector == this->otherVector); + EXPECT_TRUE(this->theVector != this->otherVector); +} + +// Constant vector tests. +TYPED_TEST(StaticVectorTest, ConstVectorTest) { + const TypeParam constVector; + + EXPECT_EQ(0u, constVector.size()); + EXPECT_TRUE(constVector.empty()); + EXPECT_TRUE(constVector.begin() == constVector.end()); +} + +// Direct array access. +TYPED_TEST(StaticVectorTest, DirectVectorTest) { + EXPECT_EQ(0u, this->theVector.size()); + // this->theVector.reserve(4); + // if (this->theVector.capacity() < 4U) + // return; + EXPECT_LE(4u, this->theVector.capacity()); + EXPECT_EQ(0, Constructable::getNumConstructorCalls()); + this->theVector.push_back(1); + this->theVector.push_back(2); + this->theVector.push_back(3); + this->theVector.push_back(4); + EXPECT_EQ(4u, this->theVector.size()); + EXPECT_EQ(8, Constructable::getNumConstructorCalls()); + EXPECT_EQ(1, this->theVector[0].getValue()); + EXPECT_EQ(2, this->theVector[1].getValue()); + EXPECT_EQ(3, this->theVector[2].getValue()); + EXPECT_EQ(4, this->theVector[3].getValue()); +} + +TYPED_TEST(StaticVectorTest, IteratorTest) { + std::list L; + this->theVector.insert(this->theVector.end(), L.begin(), L.end()); +} + +template class DualStaticVectorsTest; + +template +class DualStaticVectorsTest> + : public StaticVectorTestBase { +protected: + VectorT1 theVector; + VectorT2 otherVector; + + template + static unsigned NumBuiltinElts(const StaticVector &) { + return N; + } +}; + +typedef ::testing::Types< + // Small mode -> Small mode. + std::pair, StaticVector>> + DualStaticVectorTestTypes; + +TYPED_TEST_SUITE(DualStaticVectorsTest, DualStaticVectorTestTypes, ); + +TYPED_TEST(DualStaticVectorsTest, MoveAssignment) { + SCOPED_TRACE("MoveAssignTest-DualVectorTypes"); + + // Set up our vector with four elements. + for (unsigned I = 0; I < 4; ++I) + this->otherVector.push_back(Constructable(I)); + + const Constructable *OrigDataPtr = this->otherVector.data(); + + // Move-assign from the other vector. + this->theVector = std::move(this->otherVector); + + // Make sure we have the right result. + this->assertValuesInOrder(this->theVector, 4u, 0, 1, 2, 3); + + // Make sure the # of constructor/destructor calls line up. There + // are two live objects after clearing the other vector. + this->otherVector.clear(); + EXPECT_EQ(Constructable::getNumConstructorCalls() - 4, + Constructable::getNumDestructorCalls()); + + // If the source vector (otherVector) was in small-mode, assert that we just + // moved the data pointer over. + EXPECT_TRUE(this->NumBuiltinElts(this->otherVector) == 4 || + this->theVector.data() == OrigDataPtr); + + // There shouldn't be any live objects any more. + this->theVector.clear(); + EXPECT_EQ(Constructable::getNumConstructorCalls(), + Constructable::getNumDestructorCalls()); + + // We shouldn't have copied anything in this whole process. + EXPECT_EQ(Constructable::getNumCopyConstructorCalls(), 0); +} + +struct notassignable { + int &x; + notassignable(int &x) : x(x) {} +}; + +TEST(StaticVectorCustomTest, NoAssignTest) { + int x = 0; + StaticVector vec; + vec.push_back(notassignable(x)); + x = 42; + EXPECT_EQ(42, vec.pop_back_val().x); +} + +struct MovedFrom { + bool hasValue; + MovedFrom() : hasValue(true) {} + MovedFrom(MovedFrom &&m) : hasValue(m.hasValue) { m.hasValue = false; } + MovedFrom &operator=(MovedFrom &&m) { + hasValue = m.hasValue; + m.hasValue = false; + return *this; + } +}; + +TEST(StaticVectorTest, MidInsert) { + StaticVector v; + v.push_back(MovedFrom()); + v.insert(v.begin(), MovedFrom()); + for (MovedFrom &m : v) + EXPECT_TRUE(m.hasValue); +} +enum EmplaceableArgState { + EAS_Defaulted, + EAS_Arg, + EAS_LValue, + EAS_RValue, + EAS_Failure +}; + +template struct EmplaceableArg { + EmplaceableArgState State; + EmplaceableArg() : State(EAS_Defaulted) {} + EmplaceableArg(EmplaceableArg &&X) + : State(X.State == EAS_Arg ? EAS_RValue : EAS_Failure) {} + EmplaceableArg(EmplaceableArg &X) + : State(X.State == EAS_Arg ? EAS_LValue : EAS_Failure) {} + + explicit EmplaceableArg(bool) : State(EAS_Arg) {} + +private: + EmplaceableArg &operator=(EmplaceableArg &&) = delete; + EmplaceableArg &operator=(const EmplaceableArg &) = delete; +}; + +enum EmplaceableState { ES_Emplaced, ES_Moved }; +struct Emplaceable { + EmplaceableArg<0> A0; + EmplaceableArg<1> A1; + EmplaceableArg<2> A2; + EmplaceableArg<3> A3; + EmplaceableState State; + + Emplaceable() : State(ES_Emplaced) {} + + template + explicit Emplaceable(A0Ty &&A0) + : A0(std::forward(A0)), State(ES_Emplaced) {} + + template + Emplaceable(A0Ty &&A0, A1Ty &&A1) + : A0(std::forward(A0)), A1(std::forward(A1)), + State(ES_Emplaced) {} + + template + Emplaceable(A0Ty &&A0, A1Ty &&A1, A2Ty &&A2) + : A0(std::forward(A0)), A1(std::forward(A1)), + A2(std::forward(A2)), State(ES_Emplaced) {} + + template + Emplaceable(A0Ty &&A0, A1Ty &&A1, A2Ty &&A2, A3Ty &&A3) + : A0(std::forward(A0)), A1(std::forward(A1)), + A2(std::forward(A2)), A3(std::forward(A3)), + State(ES_Emplaced) {} + + Emplaceable(Emplaceable &&) : State(ES_Moved) {} + Emplaceable &operator=(Emplaceable &&) { + State = ES_Moved; + return *this; + } + +private: + Emplaceable(const Emplaceable &) = delete; + Emplaceable &operator=(const Emplaceable &) = delete; +}; + +TEST(StaticVectorTest, EmplaceBack) { + EmplaceableArg<0> A0(true); + EmplaceableArg<1> A1(true); + EmplaceableArg<2> A2(true); + EmplaceableArg<3> A3(true); + { + StaticVector V; + Emplaceable &back = V.emplace_back(); + EXPECT_TRUE(&back == &V.back()); + EXPECT_TRUE(V.size() == 1); + EXPECT_TRUE(back.State == ES_Emplaced); + EXPECT_TRUE(back.A0.State == EAS_Defaulted); + EXPECT_TRUE(back.A1.State == EAS_Defaulted); + EXPECT_TRUE(back.A2.State == EAS_Defaulted); + EXPECT_TRUE(back.A3.State == EAS_Defaulted); + } + { + StaticVector V; + Emplaceable &back = V.emplace_back(std::move(A0)); + EXPECT_TRUE(&back == &V.back()); + EXPECT_TRUE(V.size() == 1); + EXPECT_TRUE(back.State == ES_Emplaced); + EXPECT_TRUE(back.A0.State == EAS_RValue); + EXPECT_TRUE(back.A1.State == EAS_Defaulted); + EXPECT_TRUE(back.A2.State == EAS_Defaulted); + EXPECT_TRUE(back.A3.State == EAS_Defaulted); + } + { + StaticVector V; + Emplaceable &back = V.emplace_back(A0); + EXPECT_TRUE(&back == &V.back()); + EXPECT_TRUE(V.size() == 1); + EXPECT_TRUE(back.State == ES_Emplaced); + EXPECT_TRUE(back.A0.State == EAS_LValue); + EXPECT_TRUE(back.A1.State == EAS_Defaulted); + EXPECT_TRUE(back.A2.State == EAS_Defaulted); + EXPECT_TRUE(back.A3.State == EAS_Defaulted); + } + { + StaticVector V; + Emplaceable &back = V.emplace_back(A0, A1); + EXPECT_TRUE(&back == &V.back()); + EXPECT_TRUE(V.size() == 1); + EXPECT_TRUE(back.State == ES_Emplaced); + EXPECT_TRUE(back.A0.State == EAS_LValue); + EXPECT_TRUE(back.A1.State == EAS_LValue); + EXPECT_TRUE(back.A2.State == EAS_Defaulted); + EXPECT_TRUE(back.A3.State == EAS_Defaulted); + } + { + StaticVector V; + Emplaceable &back = V.emplace_back(std::move(A0), std::move(A1)); + EXPECT_TRUE(&back == &V.back()); + EXPECT_TRUE(V.size() == 1); + EXPECT_TRUE(back.State == ES_Emplaced); + EXPECT_TRUE(back.A0.State == EAS_RValue); + EXPECT_TRUE(back.A1.State == EAS_RValue); + EXPECT_TRUE(back.A2.State == EAS_Defaulted); + EXPECT_TRUE(back.A3.State == EAS_Defaulted); + } + { + StaticVector V; + Emplaceable &back = V.emplace_back(std::move(A0), A1, std::move(A2), A3); + EXPECT_TRUE(&back == &V.back()); + EXPECT_TRUE(V.size() == 1); + EXPECT_TRUE(back.State == ES_Emplaced); + EXPECT_TRUE(back.A0.State == EAS_RValue); + EXPECT_TRUE(back.A1.State == EAS_LValue); + EXPECT_TRUE(back.A2.State == EAS_RValue); + EXPECT_TRUE(back.A3.State == EAS_LValue); + } + { + StaticVector V; + V.emplace_back(); + V.emplace_back(42); + EXPECT_EQ(2U, V.size()); + EXPECT_EQ(0, V[0]); + EXPECT_EQ(42, V[1]); + } +} + +} // namespace diff --git a/llvm/utils/LLVMVisualizers/llvm.natvis b/llvm/utils/LLVMVisualizers/llvm.natvis --- a/llvm/utils/LLVMVisualizers/llvm.natvis +++ b/llvm/utils/LLVMVisualizers/llvm.natvis @@ -31,6 +31,29 @@ + + + {((pointer)Data)[0]}{*this,view(elt1)} + + , {((pointer)Data)[1]}{*this,view(elt2)} + + , {((pointer)Data)[2]}{*this,view(elt3)} + + , {((pointer)Data)[3]}{*this,view(elt4)} + + , /* {Size - 4} more*/ + empty + {{{*this,view(elt0)}}} + Uninitialized + + Size,d + Capacity,d + + Size + (pointer)Data + + + {U.VAL}