code/include/swoc/Vectray.h

// SPDX-License-Identifier: Apache-2.0
// Copyright Apache Software Foundation 2019
/** @file

    Container that acts like a vector but has static storage to avoid memory allocation for
    some specified number of elements.
*/

#pragma once

#include <array>
#include <vector>
#include <variant>
#include <new>
#include <cstddef>

#include <swoc/MemSpan.h>
#include <swoc/swoc_meta.h>

namespace swoc { inline namespace SWOC_VERSION_NS {

/** Vectray provides a combination of static and dynamic storage modeled as an array.
 *
 * @tparam T Type of elements in the array.
 * @tparam N Number of statically allocated elements.
 * @tparam A Allocator.
 *
 * The goal is to provide static storage for the common case, avoiding memory allocation, while
 * still handling exceptional cases that need more storage. A common case is for @a N == 1 where
 * there is almost always a single value, but it is possible to have multiple values. @c Vectray
 * makes the single value case require no allocation while transparently handling the multiple
 * value case.
 *
 * The interface is designed to mimic that of @c std::vector.
 */
template < typename T, size_t N, class A = std::allocator<T> >
class Vectray {
  using self_type = Vectray; ///< Self reference type.
  using vector_type = std::vector<T, A>; ///< Internal dynamic storage type.

public: // STL compliance types.
  using value_type = T; ///< Element type for container.
  using reference = std::remove_reference<T>&; ///< Reference to element.
  using const_reference = std::remove_reference<T> const&; ///< Reference to constant element.
  using pointer = std::remove_reference<T>*; ///< Pointer to element.
  using const_pointer = std::remove_reference<T> const*; ///< Pointer to constant element.
  using allocator_type = A; ///< Dynamic storage allocator.
  using size_type = typename vector_type::size_type; ///< Type for element count.
  using difference_type = typename vector_type::difference_type; ///< Iterator difference.
  using iterator = typename swoc::MemSpan<T>::iterator; ///< Element iteration.
  using const_iterator = typename swoc::MemSpan<const T>::iterator; ///< Constant element iteration.
  // Need to add reverse iterators - @c reverse_iterator and @c const_reverse_iterator

  /// Internal (fixed) storage.
  struct FixedStore {
    std::array<std::byte, sizeof(T) * N> _raw; ///< Raw memory for element storage.
    size_t _count = 0; ///< Number of valid elements.
    allocator_type _a; ///< Allocator instance - used for construction.

    FixedStore() = default; ///< Default construct - empty.

    /** Construct with specific allocator @a a.
     *
     * @param a Allocator.
     */
    explicit FixedStore(allocator_type const& a) : _a(a) {}

    ~FixedStore();

    /// @return A span containing the valid elements.
    MemSpan<T> span();

    /// @return A pointer to the data.
    T * data();

    /// @return A pointer to the data.
    T const * data() const;
  };

  using DynamicStore = vector_type; ///< Dynamic (heap) storage.

  /// Element access.
  using span = swoc::MemSpan<T>;
  /// Constant element access.
  using const_span = swoc::MemSpan<T const>;

public:
  /// Default constructor, construct an empty container.
  Vectray();
  /// Destructor - destructs all contained elements.
  /// @internal The internal store takes care of the details.
  ~Vectray() = default;

  /// Construct empty instance with allocator.
  constexpr explicit Vectray(allocator_type const& a) : _store(std::in_place_type_t<FixedStore>{}, a) {}

  /** Construct with @a n default constructed elements.
   *
   * @param n Number of elements.
   * @param alloc Allocator (optional - default constructed if not a parameter).
   */
  explicit Vectray(size_type n, allocator_type const& alloc = allocator_type{});

  /// Move constructor for difference static sized instance.
  template < size_t M > Vectray(Vectray<T, M, A> && that);

  /// Move constructor.
  Vectray(self_type && that, allocator_type const& a);

  /// @return The number of elements in the container.
  size_type size() const;

  /// @return A pointer to the data.
  T * data();

  /// @return A pointer to the data.
  T const * data() const;

  /// @return @c true if no valid elements, @c false if at least one valid element.
  bool empty() const;

  /// Implicitly convert to a @c MemSpan.
  operator span () { return this->items(); }
  /// Implicitly convert to a @c MemSpan.
  operator const_span () const { return this->items(); }

  /** Index operator.
   *
   * @param idx Index of element.
   * @return A reference to the element.
   */
  T& operator[](size_type idx);

  /** Index operator (const).
   *
   * @param idx Index of element.
   * @return A @c const reference to the element.
   */
  T const& operator[](size_type idx) const;

  /// @return A reference to the first element.
  T const& front() const {
    return (*this)[0];
  }

  /// @return A reference to the first element.
  T & front()  {
    return (*this)[0];
  }

  /// @return A reference to the last element.
  T const& back() const {
    return (*this)[this->size()-1];
  }

  /// @return A reference to the last element.
  T & back()  {
    return (*this)[this->size()-1];
  }
  /** Append an element by copy.
   *
   * @param t Element to add.
   * @return @a this.
   */
  self_type& push_back(T const& t);

  /** Append an element by move.
   *
   * @param t Element to add.
   * @return @a this.
   */
  self_type& push_back(T && t);

  /** Append an element by direct construction.
   *
   * @tparam Args Constructor parameter types.
   * @param args Constructor arguments.
   * @return @a this
   */
  template < typename ... Args> self_type & emplace_back(Args && ... args);

  /** Remove an element from the end of the current elements.
   *
   * @return @a this.
   */
  self_type& pop_back();

  /// Iterator for first element.
  const_iterator begin() const;

  /// Iterator past last element.
  const_iterator end() const;

  /// Iterator for last element.
  iterator begin();

  /// Iterator past last element.
  iterator end();

  /// Force at internal storage to hold at least @a n items.
  void reserve(size_type n);

protected:
  /// Content storage.
  /// @note This is constructed as fixed but can change to dynamic. It can never change back.
  std::variant<FixedStore, DynamicStore> _store;

  static constexpr auto FIXED = 0; ///< Variant index for fixed storage.
  static constexpr auto DYNAMIC = 1; ///< Variant index for dynamic storage.

  /// Get the span of the valid items.
  span items();
  /// Get the span of the valid items.
  const_span items() const;

  /// Default size to reserve in the vector when switching to dynamic.
  static constexpr size_type BASE_DYNAMIC_SIZE = (7 * N) / 5;


  /** Transfer from fixed storage to dynamic storage.
   *
   * @param rN Numer of elements of storage to reserve in the vector.
   *
   * @note Must be called at most once for any instance.
   */
  void transfer(size_type rN = BASE_DYNAMIC_SIZE);
};

// --- Implementation ---

template<typename T, size_t N, typename A>
Vectray<T,N,A>::Vectray() {}

template<typename T, size_t N, class A>
Vectray<T, N, A>::Vectray(Vectray::size_type n, allocator_type const& alloc) : Vectray() {
  this->reserve(n);
  while (n-- > 0) {
    this->emplace_back();
  }
}

template <typename T, size_t N, class A> template <size_t M> Vectray<T, N, A>::Vectray(Vectray<T, M, A> &&that) {
  // If @a that is already a vector, always move that here.
  if (DYNAMIC == that._store.index()) {
    _store = std::move(std::get<DYNAMIC>(that._store));
  } else {
    auto span = std::get<FIXED>(that._store).span();
    if (span.size() > N) {

    } else {
      for ( auto && item : span ) {
        this->template emplace_back(std::move(item));
      }
    }
  }
}

template <typename T, size_t N, class A> Vectray<T, N, A>::FixedStore::~FixedStore() {
  for ( auto & item : this->span() ) {
    std::destroy_at(std::addressof(item));
  }
}

template<typename T, size_t N, class A>
MemSpan<T> Vectray<T, N, A>::FixedStore::span() {
  return MemSpan<std::byte>(_raw).template rebind<T>();
}

template<typename T, size_t N, class A>
T * Vectray<T, N, A>::FixedStore::data() {
  return reinterpret_cast<T*>(_raw.data());
}

template<typename T, size_t N, class A>
T const * Vectray<T, N, A>::FixedStore::data() const {
  return reinterpret_cast<T*>(_raw.data());
}

template<typename T, size_t N, typename A>
T& Vectray<T,N,A>::operator[](size_type idx) {
  return this->items()[idx];
}

template<typename T, size_t N, typename A>
T const& Vectray<T,N,A>::operator[](size_type idx) const {
  return this->items[idx];
}

template<typename T, size_t N, typename A>
auto Vectray<T,N,A>::push_back(const T& t) -> self_type& {
  std::visit(swoc::meta::vary{
      [&](FixedStore& fs) -> void {
        if (fs._count < N) {
          new(reinterpret_cast<T*>(fs._raw.data()) + fs._count++) T(t); // A::traits ?
        } else {
          this->transfer();
          std::get<DYNAMIC>(_store).push_back(t);
        }
      }
      , [&](DynamicStore& ds) -> void {
        ds.push_back(t);
      }
  }, _store);
  return *this;
}

template<typename T, size_t N, typename A>
auto Vectray<T,N,A>::push_back(T && t) -> self_type& {
  std::visit(swoc::meta::vary{
               [&](FixedStore& fs) -> void {
                 if (fs._count < N) {
                   new(reinterpret_cast<T*>(fs._raw.data()) + fs._count++) T(std::move(t)); // A::traits ?
                 } else {
                   this->transfer();
                   std::get<DYNAMIC>(_store).push_back(t);
                 }
               }
               , [&](DynamicStore& ds) -> void {
                 ds.push_back(std::move(t));
               }
             }, _store);
  return *this;
}

template<typename T, size_t N, class A>
template<typename... Args>
typename Vectray<T,N,A>::self_type & Vectray<T, N, A>::emplace_back(Args && ... args) {
  if (_store.index() == FIXED) {
    auto& fs{std::get<FIXED>(_store)};
    if (fs._count < N) {
      new(reinterpret_cast<T*>(fs._raw.data()) + fs._count++) T(std::forward<Args>(args)...); // A::traits ?
      return *this;
    }
    this->transfer(); // transfer to dynamic and fall through to add item.
  }
  std::get<DYNAMIC>(_store).emplace_back(std::forward<Args>(args)...);
  return *this;
}

template<typename T, size_t N, class A>
auto Vectray<T, N, A>::pop_back() -> self_type & {
  std::visit(swoc::meta::vary{
               [&](FixedStore& fs) -> void { std::destroy_at(fs.span()[--fs._count]); }
             , [&](DynamicStore& ds) -> void { ds.pop_back(); }
             }, _store);
  return *this;
}

template<typename T, size_t N, typename A>
auto Vectray<T,N,A>::size() const -> size_type {
  return std::visit(swoc::meta::vary{
        [](FixedStore const& fs) { return fs._count; }
      , [](DynamicStore const& ds) { return ds.size(); }
  }, _store);
}

template<typename T, size_t N, typename A>
bool Vectray<T,N,A>::empty() const {
  return std::visit(swoc::meta::vary{
           [](FixedStore const& fs) { return fs._count == 0; }
         , [](DynamicStore const& ds) { return ds.empty(); }
         }, _store);
}

// --- iterators
template<typename T, size_t N, typename A>
auto  Vectray<T,N,A>::begin() const -> const_iterator { return this->items().begin(); }

template<typename T, size_t N, typename A>
auto Vectray<T,N,A>::end() const -> const_iterator { return this->items().end(); }

template<typename T, size_t N, typename A>
auto  Vectray<T,N,A>::begin() -> iterator { return this->items().begin(); }

template<typename T, size_t N, typename A>
auto Vectray<T,N,A>::end() -> iterator { return this->items().end(); }
// --- iterators

template<typename T, size_t N, class A>
void Vectray<T, N, A>::transfer(size_type rN) {
  DynamicStore tmp{std::get<FIXED>(_store)._a};
  tmp.reserve(rN);

  for (auto&& item : this->items()) {
    tmp.emplace_back(std::move(item)); // move if supported, copy if not.
  }
  // Fixed elements destroyed here, by variant.
  _store = std::move(tmp);
}

template<typename T, size_t N, class A>
auto Vectray<T, N, A>::items() const -> const_span {
  return std::visit(swoc::meta::vary{
      [](FixedStore const& fs) { fs.span(); }
      , [](DynamicStore const& ds) { return const_span(ds.data(), ds.size()); }
  }, _store);
}

template<typename T, size_t N, class A>
T * Vectray<T, N, A>::data() {
  return std::visit(swoc::meta::vary{
                      [](FixedStore const& fs) { fs.data(); }
                      , [](DynamicStore const& ds) { return ds.data(); }
                    }, _store);
}

template<typename T, size_t N, class A>
T const * Vectray<T, N, A>::data() const {
  return std::visit(swoc::meta::vary{
                      [](FixedStore const& fs) { fs.data(); }
                      , [](DynamicStore const& ds) { return ds.data(); }
                    }, _store);
}

template<typename T, size_t N, class A>
auto Vectray<T, N, A>::items() -> span {
  return std::visit(swoc::meta::vary{
      [](FixedStore & fs) { return fs.span(); }
      , [](DynamicStore & ds) { return span(ds.data(), ds.size()); }
  }, _store);
}

template<typename T, size_t N, class A>
void Vectray<T, N, A>::reserve(Vectray::size_type n) {
  if (DYNAMIC == _store.index()) {
    std::get<DYNAMIC>(_store).reserve(n);
  } else if (n > N) {
    this->transfer(n);
  }
}

}} // namespace swoc