multibuf_v2.h

// Copyright 2025 The Pigweed Authors
//
// Licensed under the Apache License, Version 2.0 (the "License"); you may not
// use this file except in compliance with the License. You may obtain a copy of
// the License at
//
//     https://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
// WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
// License for the specific language governing permissions and limitations under
// the License.
#pragma once
 
//         __      ___   ___ _  _ ___ _  _  ___
//         \ \    / /_\ | _ \ \| |_ _| \| |/ __|
//          \ \/\/ / _ \|   / .` || || .` | (_ |
//           \_/\_/_/ \_\_|_\_|\_|___|_|\_|\___|
//  _____  _____ ___ ___ ___ __  __ ___ _  _ _____ _   _
// | __\ \/ / _ \ __| _ \_ _|  \/  | __| \| |_   _/_\ | |
// | _| >  <|  _/ _||   /| || |\/| | _|| .` | | |/ _ \| |__
// |___/_/\_\_| |___|_|_\___|_|  |_|___|_|\_| |_/_/ \_\____|
//
// MultiBuf version 2 is in an early, experimental state. The APIs are in flux
// and may change without notice. Please do not rely on it in production code,
// but feel free to explore and share feedback with the Pigweed team!
 
#include <cstddef>
#include <cstdint>
#include <numeric>
#include <type_traits>
 
#include "pw_allocator/allocator.h"
#include "pw_bytes/span.h"
#include "pw_containers/dynamic_deque.h"
#include "pw_multibuf/internal/byte_iterator.h"
#include "pw_multibuf/internal/chunk_iterator.h"
#include "pw_multibuf/internal/entry.h"
#include "pw_multibuf/observer.h"
#include "pw_multibuf/properties.h"
#include "pw_span/span.h"
 
namespace pw {
 
// Forward declarations.
template <MultiBufProperty...>
class BasicMultiBuf;
 
namespace multibuf_impl {
 
template <typename>
class Instance;
 
class GenericMultiBuf;
 
}  // namespace multibuf_impl
 
 
// Type aliases for convenience, listed here for easier discoverability.
 
using FlatMultiBuf = BasicMultiBuf<>;
 
using FlatConstMultiBuf = BasicMultiBuf<MultiBufProperty::kConst>;
 
using MultiBuf = BasicMultiBuf<MultiBufProperty::kLayerable>;
 
using ConstMultiBuf =
    BasicMultiBuf<MultiBufProperty::kConst, MultiBufProperty::kLayerable>;
 
using TrackedFlatMultiBuf = BasicMultiBuf<MultiBufProperty::kObservable>;
 
using TrackedFlatConstMultiBuf =
    BasicMultiBuf<MultiBufProperty::kConst, MultiBufProperty::kObservable>;
 
using TrackedMultiBuf =
    BasicMultiBuf<MultiBufProperty::kLayerable, MultiBufProperty::kObservable>;
 
using TrackedConstMultiBuf = BasicMultiBuf<MultiBufProperty::kConst,
                                           MultiBufProperty::kLayerable,
                                           MultiBufProperty::kObservable>;
 
template <MultiBufProperty... kProperties>
class BasicMultiBuf {
 protected:
  using Deque = DynamicDeque<multibuf_impl::Entry>;
  using ChunksType = multibuf_impl::Chunks<typename Deque::size_type>;
  using ConstChunksType = multibuf_impl::ConstChunks<typename Deque::size_type>;
  using GenericMultiBuf = multibuf_impl::GenericMultiBuf;
 
  using Property = MultiBufProperty;
 
 public:
  [[nodiscard]] static constexpr bool is_const() {
    return ((kProperties == Property::kConst) || ...);
  }
 
  [[nodiscard]] static constexpr bool is_layerable() {
    return ((kProperties == Property::kLayerable) || ...);
  }
 
  [[nodiscard]] static constexpr bool is_observable() {
    return ((kProperties == Property::kObservable) || ...);
  }
 
  using size_type = typename Deque::size_type;
  using difference_type = typename Deque::difference_type;
  using iterator = multibuf_impl::ByteIterator<size_type, /*kIsConst=*/false>;
  using const_iterator =
      multibuf_impl::ByteIterator<size_type, /*kIsConst=*/true>;
  using pointer = iterator::pointer;
  using const_pointer = const_iterator::pointer;
  using reference = iterator::reference;
  using const_reference = const_iterator::reference;
  using value_type = std::conditional_t<is_const(),
                                        const_iterator::value_type,
                                        iterator::value_type>;
 
  using Instance = multibuf_impl::Instance<BasicMultiBuf>;
 
  // Interfaces are not copyable or movable; copy and move `Instance`s instead.
 
  BasicMultiBuf(const BasicMultiBuf&) = delete;
 
  template <Property... kOtherProperties>
  BasicMultiBuf(const BasicMultiBuf<kOtherProperties...>&) = delete;
 
  BasicMultiBuf& operator=(const BasicMultiBuf&) = delete;
 
  template <Property... kOtherProperties>
  BasicMultiBuf& operator=(const BasicMultiBuf<kOtherProperties...>&) = delete;
 
  BasicMultiBuf(BasicMultiBuf&&) = delete;
 
  BasicMultiBuf& operator=(BasicMultiBuf&&) = delete;
 
  // Conversions
 
  template <typename OtherMultiBuf>
  OtherMultiBuf& as() & {
    multibuf_impl::AssertIsConvertible<BasicMultiBuf, OtherMultiBuf>();
    return generic().template as<OtherMultiBuf>();
  }
 
  template <typename OtherMultiBuf>
  const OtherMultiBuf& as() const& {
    multibuf_impl::AssertIsConvertible<BasicMultiBuf, OtherMultiBuf>();
    return generic().template as<OtherMultiBuf>();
  }
 
  template <typename OtherMultiBuf>
  OtherMultiBuf&& as() && {
    multibuf_impl::AssertIsConvertible<BasicMultiBuf, OtherMultiBuf>();
    return std::move(generic().template as<OtherMultiBuf>());
  }
 
  template <typename OtherMultiBuf>
  const OtherMultiBuf&& as() const&& {
    multibuf_impl::AssertIsConvertible<BasicMultiBuf, OtherMultiBuf>();
    return std::move(generic().template as<OtherMultiBuf>());
  }
 
  template <typename OtherMultiBuf,
            typename = multibuf_impl::EnableIfConvertible<BasicMultiBuf,
                                                          OtherMultiBuf>>
  operator OtherMultiBuf&() & {
    return as<OtherMultiBuf>();
  }
 
  template <typename OtherMultiBuf,
            typename = multibuf_impl::EnableIfConvertible<BasicMultiBuf,
                                                          OtherMultiBuf>>
  operator const OtherMultiBuf&() const& {
    return as<OtherMultiBuf>();
  }
 
  template <typename OtherMultiBuf,
            typename = multibuf_impl::EnableIfConvertible<BasicMultiBuf,
                                                          OtherMultiBuf>>
  operator OtherMultiBuf&&() && {
    return std::move(as<OtherMultiBuf>());
  }
 
  template <typename OtherMultiBuf,
            typename = multibuf_impl::EnableIfConvertible<BasicMultiBuf,
                                                          OtherMultiBuf>>
  operator const OtherMultiBuf&&() const&& {
    return std::move(as<OtherMultiBuf>());
  }
 
  // Accessors
 
  constexpr bool empty() const { return generic().empty(); }
 
  constexpr size_t size() const { return generic().size(); }
 
  template <bool kMutable = !is_const()>
  std::enable_if_t<kMutable, reference> at(size_t index) {
    return *(begin() + static_cast<int>(index));
  }
  const_reference at(size_t index) const {
    return *(begin() + static_cast<int>(index));
  }
 
  template <bool kMutable = !is_const()>
  std::enable_if_t<kMutable, reference> operator[](size_t index) {
    return at(index);
  }
  const_reference operator[](size_t index) const { return at(index); }
 
  template <bool kMutable = !is_const()>
  constexpr std::enable_if_t<kMutable, ChunksType> Chunks() {
    return generic().Chunks();
  }
  ConstChunksType Chunks() const { return generic().ConstChunks(); }
  ConstChunksType ConstChunks() const { return generic().ConstChunks(); }
 
  // Iterators.
 
  template <bool kMutable = !is_const()>
  constexpr std::enable_if_t<kMutable, iterator> begin() {
    return generic().begin();
  }
  constexpr const_iterator begin() const { return cbegin(); }
  constexpr const_iterator cbegin() const { return generic().cbegin(); }
 
  template <bool kMutable = !is_const()>
  constexpr std::enable_if_t<kMutable, iterator> end() {
    return generic().end();
  }
  constexpr const_iterator end() const { return cend(); }
  constexpr const_iterator cend() const { return generic().cend(); }
 
  // Other methods
 
  bool IsCompatible(const BasicMultiBuf& mb) const {
    return generic().IsCompatible(mb.generic());
  }
 
  bool IsCompatible(const UniquePtr<std::byte[]>& bytes) const {
    return generic().IsCompatible(bytes.deallocator());
  }
  bool IsCompatible(const UniquePtr<const std::byte[]>& bytes) const {
    return generic().IsCompatible(bytes.deallocator());
  }
 
  bool IsCompatible(const SharedPtr<std::byte[]>& bytes) const {
    return generic().IsCompatible(bytes.control_block());
  }
  bool IsCompatible(const SharedPtr<const std::byte[]>& bytes) const {
    return generic().IsCompatible(bytes.control_block());
  }
 
  [[nodiscard]] bool TryReserveChunks(size_t num_chunks) {
    return generic().TryReserveChunks(num_chunks);
  }
 
  // Mutators
 
  template <Property... kOtherProperties>
  [[nodiscard]] bool TryReserveForInsert(
      const_iterator pos, const BasicMultiBuf<kOtherProperties...>& mb);
 
  template <
      int&... kExplicitGuard,
      typename T,
      typename =
          std::enable_if_t<std::is_constructible_v<ConstByteSpan, T>, int>>
  [[nodiscard]] bool TryReserveForInsert(const_iterator pos, const T& bytes);
 
  [[nodiscard]] bool TryReserveForInsert(const_iterator pos,
                                         const UniquePtr<std::byte[]>& bytes);
  [[nodiscard]] bool TryReserveForInsert(
      const_iterator pos, const UniquePtr<const std::byte[]>& bytes);
 
  [[nodiscard]] bool TryReserveForInsert(const_iterator pos,
                                         const SharedPtr<std::byte[]>& bytes);
  [[nodiscard]] bool TryReserveForInsert(
      const_iterator pos, const SharedPtr<const std::byte[]>& bytes);
 
  template <Property... kOtherProperties>
  void Insert(const_iterator pos, BasicMultiBuf<kOtherProperties...>&& mb);
 
  template <
      int&... kExplicitGuard,
      typename T,
      typename =
          std::enable_if_t<std::is_constructible_v<ConstByteSpan, T>, int>>
  void Insert(const_iterator pos, const T& bytes);
 
  void Insert(const_iterator pos, UniquePtr<std::byte[]>&& bytes) {
    Insert(pos, std::move(bytes), 0);
  }
  void Insert(const_iterator pos, UniquePtr<const std::byte[]>&& bytes) {
    Insert(pos, std::move(bytes), 0);
  }
 
  void Insert(const_iterator pos,
              UniquePtr<std::byte[]>&& bytes,
              size_t offset,
              size_t length = dynamic_extent);
  void Insert(const_iterator pos,
              UniquePtr<const std::byte[]>&& bytes,
              size_t offset,
              size_t length = dynamic_extent);
 
  void Insert(const_iterator pos, const SharedPtr<std::byte[]>& bytes) {
    Insert(pos, bytes, 0);
  }
  void Insert(const_iterator pos, const SharedPtr<const std::byte[]>& bytes) {
    Insert(pos, bytes, 0);
  }
 
  void Insert(const_iterator pos,
              const SharedPtr<std::byte[]>& bytes,
              size_t offset,
              size_t length = dynamic_extent);
  void Insert(const_iterator pos,
              const SharedPtr<const std::byte[]>& bytes,
              size_t offset,
              size_t length = dynamic_extent);
 
  template <Property... kOtherProperties>
  [[nodiscard]] bool TryReserveForPushBack(
      const BasicMultiBuf<kOtherProperties...>& mb);
 
  template <
      int&... kExplicitGuard,
      typename T,
      typename =
          std::enable_if_t<std::is_constructible_v<ConstByteSpan, T>, int>>
  [[nodiscard]] bool TryReserveForPushBack(const T& bytes);
 
  [[nodiscard]] bool TryReserveForPushBack(const UniquePtr<std::byte[]>& bytes);
  [[nodiscard]] bool TryReserveForPushBack(
      const UniquePtr<const std::byte[]>& bytes);
 
  [[nodiscard]] bool TryReserveForPushBack(const SharedPtr<std::byte[]>& bytes);
  [[nodiscard]] bool TryReserveForPushBack(
      const SharedPtr<const std::byte[]>& bytes);
 
  template <Property... kOtherProperties>
  void PushBack(BasicMultiBuf<kOtherProperties...>&& mb);
 
  template <
      int&... kExplicitGuard,
      typename T,
      typename =
          std::enable_if_t<std::is_constructible_v<ConstByteSpan, T>, int>>
  void PushBack(const T& bytes);
 
  void PushBack(UniquePtr<std::byte[]>&& bytes) {
    PushBack(std::move(bytes), 0);
  }
  void PushBack(UniquePtr<const std::byte[]>&& bytes) {
    PushBack(std::move(bytes), 0);
  }
 
  void PushBack(UniquePtr<std::byte[]>&& bytes,
                size_t offset,
                size_t length = dynamic_extent);
 
  void PushBack(UniquePtr<const std::byte[]>&& bytes,
                size_t offset,
                size_t length = dynamic_extent);
 
  void PushBack(const SharedPtr<std::byte[]>& bytes) { PushBack(bytes, 0); }
  void PushBack(const SharedPtr<const std::byte[]>& bytes) {
    PushBack(bytes, 0);
  }
 
  void PushBack(const SharedPtr<std::byte[]>& bytes,
                size_t offset,
                size_t length = dynamic_extent);
  void PushBack(const SharedPtr<const std::byte[]>& bytes,
                size_t offset,
                size_t length = dynamic_extent);
 
  [[nodiscard]] bool IsRemovable(const_iterator pos, size_t size) const {
    return generic().IsRemovable(pos, size);
  }
 
  Result<Instance> Remove(const_iterator pos, size_t size);
 
  Result<Instance> PopFrontFragment();
 
  Result<const_iterator> Discard(const_iterator pos, size_t size) {
    return generic().Discard(pos, size);
  }
 
  [[nodiscard]] bool IsReleasable(const_iterator pos) const {
    return generic().IsReleasable(pos);
  }
 
  UniquePtr<value_type[]> Release(const_iterator pos);
 
  [[nodiscard]] bool IsShareable(const_iterator pos) const {
    return generic().IsShareable(pos);
  }
 
  SharedPtr<value_type[]> Share(const_iterator pos);
 
  size_t CopyTo(ByteSpan dst, size_t offset = 0) const {
    return generic().CopyTo(dst, offset);
  }
 
  size_t CopyFrom(ConstByteSpan src, size_t offset = 0) {
    static_assert(!is_const(),
                  "`CopyFrom` may only be called on mutable MultiBufs");
    return generic().CopyFrom(src, offset);
  }
 
  ConstByteSpan Get(ByteSpan copy, size_t offset = 0) const {
    return generic().Get(copy, offset);
  }
 
  template <int&... kExplicitGuard, typename Visitor>
  auto Visit(Visitor visitor, ByteSpan copy, size_t offset) {
    return visitor(Get(copy, offset));
  }
 
  void Clear() { generic().Clear(); }
 
  // Observable methods.
 
  constexpr MultiBufObserver* observer() const {
    static_assert(is_observable(),
                  "`observer` may only be called on observable MultiBufs");
    return generic().observer_;
  }
 
  void set_observer(MultiBufObserver* observer) {
    static_assert(is_observable(),
                  "`set_observer` may only be called on observable MultiBufs");
    generic().observer_ = observer;
  }
 
  // Layerable methods.
 
  size_type NumFragments() const {
    static_assert(is_layerable(),
                  "`NumFragments` may only be called on layerable MultiBufs");
    return generic().NumFragments();
  }
 
  constexpr size_type NumLayers() const {
    static_assert(is_layerable(),
                  "`NumLayers` may only be called on layerable MultiBufs");
    return generic().NumLayers();
  }
 
  [[nodiscard]] bool TryReserveLayers(size_t num_layers,
                                      size_t num_chunks = 1) {
    return generic().TryReserveLayers(num_layers, num_chunks);
  }
 
  [[nodiscard]] bool AddLayer(size_t offset, size_t length = dynamic_extent) {
    static_assert(is_layerable(),
                  "`AddLayer` may only be called on layerable MultiBufs");
    return generic().AddLayer(offset, length);
  }
 
  void SealTopLayer() {
    static_assert(is_layerable(),
                  "`SealTopLayer` may only be called on layerable MultiBufs");
    return generic().SealTopLayer();
  }
 
  void UnsealTopLayer() {
    static_assert(is_layerable(),
                  "`UnsealTopLayer` may only be called on layerable MultiBufs");
    return generic().UnsealTopLayer();
  }
 
  [[nodiscard]] bool IsTopLayerSealed() {
    static_assert(
        is_layerable(),
        "`IsTopLayerSealed` may only be called on layerable MultiBufs");
    return generic().IsTopLayerSealed();
  }
 
  void TruncateTopLayer(size_t length) {
    static_assert(
        is_layerable(),
        "`TruncateTopLayer` may only be called on layerable MultiBufs");
    generic().TruncateTopLayer(length);
  }
 
  void SetTopLayer(ConstByteSpan src) {
    static_assert(!is_const() && is_layerable(),
                  "`SetTopLayer` may only be called on mutable, layerable "
                  "MultiBufs");
    PW_ASSERT(src.size() <= size());
    CopyFrom(src);
    TruncateTopLayer(src.size());
  }
 
  void PopLayer() {
    static_assert(is_layerable(),
                  "`PopLayer` may only be called on layerable MultiBufs");
    generic().PopLayer();
  }
 
 protected:
  constexpr BasicMultiBuf() { multibuf_impl::PropertiesAreValid(); }
 
 private:
  template <Property...>
  friend class BasicMultiBuf;
 
  constexpr GenericMultiBuf& generic() {
    return static_cast<GenericMultiBuf&>(*this);
  }
  constexpr const GenericMultiBuf& generic() const {
    return static_cast<const GenericMultiBuf&>(*this);
  }
};
 
namespace multibuf_impl {
 
// A generic MultiBuf implementation that provides the functionality of any
// `BasicMultiBuf<kProperties>` type.
//
// This class should not be instantiated directly. Instead, use `Instance` as
// described below. This is the base class for all `Instance` types, and derives
// from every supported `BasicMultiBuf` type. It implements the MultiBuf
// behavior in one type, and allows for performing conversions from `Instance`s
// and `BasicMultiBuf`s to `BasicMultiBuf`s with different yet compatible
// propreties.
class GenericMultiBuf final
    : private BasicMultiBuf<>,
      private BasicMultiBuf<MultiBufProperty::kObservable>,
      private BasicMultiBuf<MultiBufProperty::kLayerable>,
      private BasicMultiBuf<MultiBufProperty::kConst>,
      private BasicMultiBuf<MultiBufProperty::kConst,
                            MultiBufProperty::kObservable>,
      private BasicMultiBuf<MultiBufProperty::kConst,
                            MultiBufProperty::kLayerable>,
      private BasicMultiBuf<MultiBufProperty::kLayerable,
                            MultiBufProperty::kObservable>,
      private BasicMultiBuf<MultiBufProperty::kConst,
                            MultiBufProperty::kLayerable,
                            MultiBufProperty::kObservable> {
 private:
  using typename BasicMultiBuf<>::ChunksType;
  using typename BasicMultiBuf<>::ConstChunksType;
  using ControlBlock = allocator::internal::ControlBlock;
  using typename BasicMultiBuf<>::Deque;
 
 public:
  using typename BasicMultiBuf<>::const_iterator;
  using typename BasicMultiBuf<>::const_pointer;
  using typename BasicMultiBuf<>::const_reference;
  using typename BasicMultiBuf<>::difference_type;
  using typename BasicMultiBuf<>::iterator;
  using typename BasicMultiBuf<>::pointer;
  using typename BasicMultiBuf<>::reference;
  using typename BasicMultiBuf<>::size_type;
 
  ~GenericMultiBuf() { Clear(); }
 
  // Not copyable.
  GenericMultiBuf(const GenericMultiBuf&) = delete;
  GenericMultiBuf& operator=(const GenericMultiBuf&) = delete;
 
  // Movable.
  GenericMultiBuf(GenericMultiBuf&& other)
      : GenericMultiBuf(other.deque_.get_allocator()) {
    *this = std::move(other);
  }
  GenericMultiBuf& operator=(GenericMultiBuf&& other);
 
 private:
  template <MultiBufProperty...>
  friend class ::pw::BasicMultiBuf;
 
  template <typename>
  friend class ::pw::multibuf_impl::Instance;
 
  constexpr explicit GenericMultiBuf(Allocator& allocator)
      : deque_(allocator) {}
 
  template <typename MultiBufType>
  MultiBufType& as() {
    return *this;
  }
 
  template <typename MultiBufType>
  const MultiBufType& as() const {
    return *this;
  }
 
  // Accessors.
 
  constexpr bool empty() const { return deque_.empty(); }
 
  constexpr size_t size() const {
    return static_cast<size_t>(cend() - cbegin());
  }
 
  constexpr bool has_deallocator() const {
    return memory_tag_ == MemoryTag::kDeallocator || has_control_block();
  }
 
  constexpr bool has_control_block() const {
    return memory_tag_ == MemoryTag::kControlBlock;
  }
 
  // Iterators.
 
  constexpr ChunksType Chunks() { return ChunksType(deque_, depth_); }
  constexpr ConstChunksType ConstChunks() const {
    return ConstChunksType(deque_, depth_);
  }
 
  constexpr iterator begin() { return iterator(Chunks().begin(), 0); }
  constexpr const_iterator cbegin() const {
    return const_iterator(ConstChunks().cbegin(), 0);
  }
 
  constexpr iterator end() { return iterator(Chunks().end(), 0); }
  constexpr const_iterator cend() const {
    return const_iterator(ConstChunks().cend(), 0);
  }
 
  // Mutators.
 
  bool IsCompatible(const GenericMultiBuf& other) const;
  bool IsCompatible(const Deallocator* other) const;
  bool IsCompatible(const ControlBlock* other) const;
 
  [[nodiscard]] bool TryReserveChunks(size_t num_chunks);
 
  [[nodiscard]] bool TryReserveForInsert(const_iterator pos,
                                         const GenericMultiBuf& mb);
  [[nodiscard]] bool TryReserveForInsert(const_iterator pos, size_t size);
  [[nodiscard]] bool TryReserveForInsert(const_iterator pos,
                                         size_t size,
                                         const Deallocator* deallocator);
  [[nodiscard]] bool TryReserveForInsert(const_iterator pos,
                                         size_t size,
                                         const ControlBlock* control_block);
 
  void Insert(const_iterator pos, GenericMultiBuf&& mb);
  void Insert(const_iterator pos, ConstByteSpan bytes);
  void Insert(const_iterator pos,
              ConstByteSpan bytes,
              size_t offset,
              size_t length,
              Deallocator* deallocator);
  void Insert(const_iterator pos,
              ConstByteSpan bytes,
              size_t offset,
              size_t length,
              ControlBlock* control_block);
 
  [[nodiscard]] bool IsRemovable(const_iterator pos, size_t size) const;
 
  Result<GenericMultiBuf> Remove(const_iterator pos, size_t size);
 
  Result<GenericMultiBuf> PopFrontFragment();
 
  Result<const_iterator> Discard(const_iterator pos, size_t size);
 
  [[nodiscard]] bool IsReleasable(const_iterator pos) const;
 
  UniquePtr<std::byte[]> Release(const_iterator pos);
 
  [[nodiscard]] bool IsShareable(const_iterator pos) const;
 
  std::byte* Share(const_iterator pos);
 
  size_t CopyTo(ByteSpan dst, size_t offset) const;
 
  size_t CopyFrom(ConstByteSpan src, size_t offset);
 
  ConstByteSpan Get(ByteSpan copy, size_t offset) const;
 
  void Clear();
 
  // Layerable methods.
 
  size_type NumFragments() const;
 
  constexpr size_type NumLayers() const { return depth_ - 1; }
 
  [[nodiscard]] bool TryReserveLayers(size_t num_layers, size_t num_chunks = 1);
 
  [[nodiscard]] bool AddLayer(size_t offset, size_t length = dynamic_extent);
 
  void SealTopLayer();
 
  void UnsealTopLayer();
 
  void TruncateTopLayer(size_t length);
 
  void PopLayer();
 
  // Implementation methods.
  //
  // These methods are used to implement the methods above, and should not be
  // called directly by BasicMultiBuf<>.
 
  static size_t CheckRange(size_t offset, size_t length, size_t size);
 
  constexpr std::byte* GetData(size_type index) const {
    return deque_[index].data;
  }
 
  constexpr bool IsOwned(size_type index) const {
    return deque_[index + 1].base_view.owned;
  }
 
  constexpr bool IsShared(size_type index) const {
    return deque_[index + 1].base_view.shared;
  }
 
  constexpr bool IsSealed(size_type index) const {
    return depth_ == 2 ? false : deque_[index + depth_ - 1].view.sealed;
  }
 
  constexpr bool IsBoundary(size_type index) const {
    return depth_ == 2 ? true : deque_[index + depth_ - 1].view.boundary;
  }
 
  constexpr size_type GetOffset(size_type index, uint16_t layer) const {
    return layer == 1 ? deque_[index + 1].base_view.offset
                      : deque_[index + layer].view.offset;
  }
 
  constexpr size_type GetOffset(size_type index) const {
    return GetOffset(index, NumLayers());
  }
 
  constexpr size_type GetRelativeOffset(size_type index) const {
    uint16_t layer = NumLayers();
    if (layer == 1) {
      return GetOffset(index, layer);
    }
    return GetOffset(index, layer) - GetOffset(index, layer - 1);
  }
 
  constexpr size_type GetLength(size_type index) const {
    return depth_ == 2 ? deque_[index + 1].base_view.length
                       : deque_[index + depth_ - 1].view.length;
  }
 
  constexpr ByteSpan GetView(size_type index) const {
    return ByteSpan(GetData(index) + GetOffset(index), GetLength(index));
  }
 
  Deallocator* GetDeallocator() const;
 
  void SetDeallocator(Deallocator* deallocator);
 
  ControlBlock* GetControlBlock() const;
 
  void SetControlBlock(ControlBlock* control_block);
 
  void CopyMemoryContext(const GenericMultiBuf& other);
 
  void ClearMemoryContext();
 
  std::pair<size_type, size_type> GetIndexAndOffset(const_iterator pos) const;
 
  bool TryReserveEntries(const_iterator pos, size_type num_entries);
  bool TryReserveEntries(size_type num_entries, bool split = false);
 
  size_type InsertEntries(const_iterator pos, size_type num_entries);
 
  size_type Insert(const_iterator pos,
                   ConstByteSpan bytes,
                   size_t offset,
                   size_t length);
 
  void SplitBase(size_type index, Deque& out_deque, size_type out_index);
 
  void SplitBefore(size_type index,
                   size_type split,
                   Deque& out_deque,
                   size_type out_index);
 
  void SplitBefore(size_type index, size_type split);
 
  void SplitAfter(size_type index,
                  size_type split,
                  Deque& out_deque,
                  size_type out_index);
 
  void SplitAfter(size_type index, size_type split);
 
  [[nodiscard]] bool TryReserveForRemove(const_iterator pos,
                                         size_t size,
                                         GenericMultiBuf* out);
 
  void CopyRange(const_iterator pos, size_t size, GenericMultiBuf& out);
 
  void ClearRange(const_iterator pos, size_t size);
 
  void EraseRange(const_iterator pos, size_t size);
 
  size_type FindShared(size_type index, size_type start);
 
  size_t CopyToImpl(ByteSpan dst, size_t offset, size_type start) const;
 
  [[nodiscard]] bool IsTopLayerSealed() const;
 
  void SetLayer(size_t offset, size_t length);
 
  // Describes the memory and views to that in a one-dimensional sequence.
  // Every `depth_`-th entry holds a pointer to memory, each entry for a given
  // offset less than `depth_` after that entry is a view that is part of the
  // same "layer" in the MultiBuf.
  //
  // This base type will always have 0 or 2 layers, but derived classes may add
  // more.
  //
  // For example, a MultiBuf that has had 3 `Chunk`s and two additional layers
  // added would have a `deque_` resembling the following:
  //
  //          buffer 0:         buffer 1:         buffer 2:
  // layer 3: deque_[0x3].view  deque_[0x7].view  deque_[0xB].view
  // layer 2: deque_[0x2].view  deque_[0x6].view  deque_[0xA].view
  // layer 1: deque_[0x1].view  deque_[0x5].view  deque_[0x9].view
  // layer 0: deque_[0x0].data  deque_[0x4].data  deque_[0x8].data
  Deque deque_;
 
  // Number of entries per chunk in this MultiBuf.
  size_type depth_ = 2;
 
  enum class MemoryTag : uint8_t {
    kEmpty,
    kDeallocator,
    kControlBlock,
  } memory_tag_ = MemoryTag::kEmpty;
 
  union MemoryContext {
    Deallocator* deallocator;
    ControlBlock* control_block;
  } memory_context_ = {.deallocator = nullptr};
 
  MultiBufObserver* observer_ = nullptr;
};
 
template <typename MultiBufType>
class Instance {
 public:
  constexpr explicit Instance(Allocator& allocator) : base_(allocator) {}
 
  constexpr Instance(Instance&&) = default;
  constexpr Instance& operator=(Instance&&) = default;
 
  constexpr Instance(MultiBufType&& mb)
      : base_(std::move(static_cast<GenericMultiBuf&>(mb))) {}
 
  constexpr Instance& operator=(MultiBufType&& mb) {
    base_ = std::move(static_cast<GenericMultiBuf&>(mb));
    return *this;
  }
 
  MultiBufType* operator->() { return &base_.as<MultiBufType>(); }
  const MultiBufType* operator->() const { return &base_.as<MultiBufType>(); }
 
  MultiBufType& operator*() & { return base_.as<MultiBufType>(); }
  const MultiBufType& operator*() const& { return base_.as<MultiBufType>(); }
 
  MultiBufType&& operator*() && { return std::move(base_.as<MultiBufType>()); }
  const MultiBufType&& operator*() const&& {
    return std::move(base_.as<MultiBufType>());
  }
 
  operator MultiBufType&() & { return base_.as<MultiBufType>(); }
  operator const MultiBufType&() const& { return base_.as<MultiBufType>(); }
 
  operator MultiBufType&&() && { return std::move(base_.as<MultiBufType>()); }
  operator const MultiBufType&&() const&& {
    return std::move(base_.as<MultiBufType>());
  }
 
 private:
  GenericMultiBuf base_;
};
 
}  // namespace multibuf_impl
 
 
 
// Template method implementations.
 
template <MultiBufProperty... kProperties>
template <MultiBufProperty... kOtherProperties>
bool BasicMultiBuf<kProperties...>::TryReserveForInsert(
    const_iterator pos, const BasicMultiBuf<kOtherProperties...>& mb) {
  multibuf_impl::AssertIsConvertible<BasicMultiBuf<kOtherProperties...>,
                                     BasicMultiBuf>();
  return generic().TryReserveForInsert(pos,
                                       static_cast<const GenericMultiBuf&>(mb));
}
 
template <MultiBufProperty... kProperties>
template <int&... kExplicitGuard, typename T, typename>
bool BasicMultiBuf<kProperties...>::TryReserveForInsert(const_iterator pos,
                                                        const T& bytes) {
  using data_ptr_type = decltype(std::data(std::declval<T&>()));
  static_assert(std::is_same_v<data_ptr_type, std::byte*> || is_const(),
                "Cannot `Insert` read-only bytes into mutable MultiBuf");
  return generic().TryReserveForInsert(pos, bytes.size());
}
 
template <MultiBufProperty... kProperties>
bool BasicMultiBuf<kProperties...>::TryReserveForInsert(
    const_iterator pos, const UniquePtr<std::byte[]>& bytes) {
  return generic().TryReserveForInsert(pos, bytes.size(), bytes.deallocator());
}
 
template <MultiBufProperty... kProperties>
bool BasicMultiBuf<kProperties...>::TryReserveForInsert(
    const_iterator pos, const UniquePtr<const std::byte[]>& bytes) {
  static_assert(is_const(),
                "Cannot `Insert` read-only bytes into mutable MultiBuf");
  return generic().TryReserveForInsert(pos, bytes.size(), bytes.deallocator());
}
 
template <MultiBufProperty... kProperties>
bool BasicMultiBuf<kProperties...>::TryReserveForInsert(
    const_iterator pos, const SharedPtr<std::byte[]>& bytes) {
  return generic().TryReserveForInsert(
      pos, bytes.size(), bytes.control_block());
}
 
template <MultiBufProperty... kProperties>
bool BasicMultiBuf<kProperties...>::TryReserveForInsert(
    const_iterator pos, const SharedPtr<const std::byte[]>& bytes) {
  static_assert(is_const(),
                "Cannot `Insert` read-only bytes into mutable MultiBuf");
  return generic().TryReserveForInsert(
      pos, bytes.size(), bytes.control_block());
}
 
template <MultiBufProperty... kProperties>
template <MultiBufProperty... kOtherProperties>
void BasicMultiBuf<kProperties...>::Insert(
    const_iterator pos, BasicMultiBuf<kOtherProperties...>&& mb) {
  multibuf_impl::AssertIsConvertible<BasicMultiBuf<kOtherProperties...>,
                                     BasicMultiBuf>();
  generic().Insert(pos, std::move(mb.generic()));
}
 
template <MultiBufProperty... kProperties>
template <int&... kExplicitGuard, typename T, typename>
void BasicMultiBuf<kProperties...>::Insert(const_iterator pos, const T& bytes) {
  using data_ptr_type = decltype(std::data(std::declval<T&>()));
  static_assert(std::is_same_v<data_ptr_type, std::byte*> || is_const(),
                "Cannot `Insert` read-only bytes into mutable MultiBuf");
  generic().Insert(pos, bytes);
}
 
template <MultiBufProperty... kProperties>
void BasicMultiBuf<kProperties...>::Insert(const_iterator pos,
                                           UniquePtr<std::byte[]>&& bytes,
                                           size_t offset,
                                           size_t length) {
  ConstByteSpan chunk(bytes.get(), bytes.size());
  generic().Insert(pos, chunk, offset, length, bytes.deallocator());
  bytes.Release();
}
 
template <MultiBufProperty... kProperties>
void BasicMultiBuf<kProperties...>::Insert(const_iterator pos,
                                           UniquePtr<const std::byte[]>&& bytes,
                                           size_t offset,
                                           size_t length) {
  static_assert(is_const(),
                "Cannot `Insert` read-only bytes into mutable MultiBuf");
  ConstByteSpan chunk(bytes.get(), bytes.size());
  generic().Insert(pos, chunk, offset, length, bytes.deallocator());
  bytes.Release();
}
 
template <MultiBufProperty... kProperties>
void BasicMultiBuf<kProperties...>::Insert(const_iterator pos,
                                           const SharedPtr<std::byte[]>& bytes,
                                           size_t offset,
                                           size_t length) {
  ConstByteSpan chunk(bytes.get(), bytes.size());
  generic().Insert(pos, chunk, offset, length, bytes.control_block());
}
 
template <MultiBufProperty... kProperties>
void BasicMultiBuf<kProperties...>::Insert(
    const_iterator pos,
    const SharedPtr<const std::byte[]>& bytes,
    size_t offset,
    size_t length) {
  static_assert(is_const(),
                "Cannot `Insert` read-only bytes into mutable MultiBuf");
  ConstByteSpan chunk(bytes.get(), bytes.size());
  generic().Insert(pos, chunk, offset, length, bytes.control_block());
}
 
template <MultiBufProperty... kProperties>
template <MultiBufProperty... kOtherProperties>
bool BasicMultiBuf<kProperties...>::TryReserveForPushBack(
    const BasicMultiBuf<kOtherProperties...>& mb) {
  return TryReserveForInsert(end(), mb);
}
 
template <MultiBufProperty... kProperties>
template <int&... kExplicitGuard, typename T, typename>
bool BasicMultiBuf<kProperties...>::TryReserveForPushBack(const T& bytes) {
  using data_ptr_type = decltype(std::data(std::declval<T&>()));
  static_assert(std::is_same_v<data_ptr_type, std::byte*> || is_const(),
                "Cannot `PushBack` read-only bytes into mutable MultiBuf");
  return TryReserveForInsert(end(), bytes);
}
 
template <MultiBufProperty... kProperties>
bool BasicMultiBuf<kProperties...>::TryReserveForPushBack(
    const UniquePtr<std::byte[]>& bytes) {
  return TryReserveForInsert(end(), std::move(bytes));
}
 
template <MultiBufProperty... kProperties>
bool BasicMultiBuf<kProperties...>::TryReserveForPushBack(
    const UniquePtr<const std::byte[]>& bytes) {
  static_assert(is_const(),
                "Cannot `PushBack` read-only bytes into mutable MultiBuf");
  return TryReserveForInsert(end(), std::move(bytes));
}
 
template <MultiBufProperty... kProperties>
bool BasicMultiBuf<kProperties...>::TryReserveForPushBack(
    const SharedPtr<std::byte[]>& bytes) {
  return TryReserveForInsert(end(), bytes);
}
 
template <MultiBufProperty... kProperties>
bool BasicMultiBuf<kProperties...>::TryReserveForPushBack(
    const SharedPtr<const std::byte[]>& bytes) {
  static_assert(is_const(),
                "Cannot `PushBack` read-only bytes into mutable MultiBuf");
  return TryReserveForInsert(end(), bytes);
}
 
template <MultiBufProperty... kProperties>
template <MultiBufProperty... kOtherProperties>
void BasicMultiBuf<kProperties...>::PushBack(
    BasicMultiBuf<kOtherProperties...>&& mb) {
  Insert(end(), std::move(mb));
}
 
template <MultiBufProperty... kProperties>
template <int&... kExplicitGuard, typename T, typename>
void BasicMultiBuf<kProperties...>::PushBack(const T& bytes) {
  using data_ptr_type = decltype(std::data(std::declval<T&>()));
  static_assert(std::is_same_v<data_ptr_type, std::byte*> || is_const(),
                "Cannot `PushBack` read-only bytes into mutable MultiBuf");
  Insert(end(), bytes);
}
 
template <MultiBufProperty... kProperties>
void BasicMultiBuf<kProperties...>::PushBack(UniquePtr<std::byte[]>&& bytes,
                                             size_t offset,
                                             size_t length) {
  Insert(end(), std::move(bytes), offset, length);
}
 
template <MultiBufProperty... kProperties>
void BasicMultiBuf<kProperties...>::PushBack(
    UniquePtr<const std::byte[]>&& bytes, size_t offset, size_t length) {
  static_assert(is_const(),
                "Cannot `PushBack` read-only bytes into mutable MultiBuf");
  Insert(end(), std::move(bytes), offset, length);
}
 
template <MultiBufProperty... kProperties>
void BasicMultiBuf<kProperties...>::PushBack(
    const SharedPtr<std::byte[]>& bytes, size_t offset, size_t length) {
  Insert(end(), bytes, offset, length);
}
 
template <MultiBufProperty... kProperties>
void BasicMultiBuf<kProperties...>::PushBack(
    const SharedPtr<const std::byte[]>& bytes, size_t offset, size_t length) {
  static_assert(is_const(),
                "Cannot `PushBack` read-only bytes into mutable MultiBuf");
  Insert(end(), bytes, offset, length);
}
 
template <MultiBufProperty... kProperties>
Result<multibuf_impl::Instance<BasicMultiBuf<kProperties...>>>
BasicMultiBuf<kProperties...>::Remove(const_iterator pos, size_t size) {
  auto result = generic().Remove(pos, size);
  if (!result.ok()) {
    return result.status();
  }
  return Instance(std::move(*result));
}
 
template <MultiBufProperty... kProperties>
Result<multibuf_impl::Instance<BasicMultiBuf<kProperties...>>>
BasicMultiBuf<kProperties...>::PopFrontFragment() {
  Result<GenericMultiBuf> result = generic().PopFrontFragment();
  if (!result.ok()) {
    return result.status();
  }
  return Instance(std::move(*result));
}
 
template <MultiBufProperty... kProperties>
UniquePtr<typename BasicMultiBuf<kProperties...>::value_type[]>
BasicMultiBuf<kProperties...>::Release(const_iterator pos) {
  UniquePtr<std::byte[]> bytes = generic().Release(pos);
  if constexpr (is_const()) {
    UniquePtr<const std::byte[]> const_bytes(
        bytes.get(), bytes.size(), *(bytes.deallocator()));
    bytes.Release();
    return const_bytes;
  } else {
    return bytes;
  }
}
 
template <MultiBufProperty... kProperties>
SharedPtr<typename BasicMultiBuf<kProperties...>::value_type[]>
BasicMultiBuf<kProperties...>::Share(const_iterator pos) {
  return SharedPtr<value_type[]>(generic().Share(pos),
                                 generic().GetControlBlock());
}
 
}  // namespace pw