pw_multibuf: Add basic MultiBuf operations
This change introduces the essential operators for creating, inserting
chunks into, removing chunks from, and iterating over MultiBufs.
Later changes will add higher-level convenience functions for inserting
new blocks of bytes within a MultiBuf, as well as the MultiBufAllocator
interface.
Change-Id: I9c9af1d887df5145482a74c7f6dacfd987c86a4d
Reviewed-on: https://pigweed-review.googlesource.com/c/pigweed/pigweed/+/178036
Commit-Queue: Taylor Cramer <cramertj@google.com>
Reviewed-by: Carlos Chinchilla <cachinchilla@google.com>
Presubmit-Verified: CQ Bot Account <pigweed-scoped@luci-project-accounts.iam.gserviceaccount.com>
Reviewed-by: Alexei Frolov <frolv@google.com>
diff --git a/pw_multibuf/BUILD.bazel b/pw_multibuf/BUILD.bazel
index 8a37f50..c078e60 100644
--- a/pw_multibuf/BUILD.bazel
+++ b/pw_multibuf/BUILD.bazel
@@ -36,13 +36,24 @@
],
)
+pw_cc_library(
+ name = "test_utils",
+ hdrs = ["public/pw_multibuf/internal/test_utils.h"],
+ includes = ["public"],
+ visibility = [":__subpackages__"],
+ deps = [
+ ":chunk",
+ "//pw_allocator:allocator_metric_proxy",
+ "//pw_allocator:split_free_list_allocator",
+ ],
+)
+
pw_cc_test(
name = "chunk_test",
srcs = ["chunk_test.cc"],
deps = [
":chunk",
- "//pw_allocator:allocator_metric_proxy",
- "//pw_allocator:split_free_list_allocator",
+ ":test_utils",
"//pw_unit_test",
],
)
@@ -59,6 +70,7 @@
srcs = ["multibuf_test.cc"],
deps = [
":pw_multibuf",
+ ":test_utils",
"//pw_unit_test",
],
)
diff --git a/pw_multibuf/BUILD.gn b/pw_multibuf/BUILD.gn
index bfdc05f..41a9f20 100644
--- a/pw_multibuf/BUILD.gn
+++ b/pw_multibuf/BUILD.gn
@@ -37,12 +37,21 @@
deps = [ "$dir_pw_assert:check" ]
}
-pw_test("chunk_test") {
- deps = [
+pw_source_set("test_utils") {
+ public_configs = [ ":public_include_path" ]
+ public = [ "public/pw_multibuf/internal/test_utils.h" ]
+ public_deps = [
":chunk",
"$dir_pw_allocator:allocator_metric_proxy",
"$dir_pw_allocator:split_free_list_allocator",
]
+}
+
+pw_test("chunk_test") {
+ deps = [
+ ":chunk",
+ ":test_utils",
+ ]
sources = [ "chunk_test.cc" ]
}
@@ -54,7 +63,10 @@
}
pw_test("multibuf_test") {
- deps = [ ":pw_multibuf" ]
+ deps = [
+ ":pw_multibuf",
+ ":test_utils",
+ ]
sources = [ "multibuf_test.cc" ]
}
diff --git a/pw_multibuf/CMakeLists.txt b/pw_multibuf/CMakeLists.txt
index 4c20592..217b70a 100644
--- a/pw_multibuf/CMakeLists.txt
+++ b/pw_multibuf/CMakeLists.txt
@@ -31,12 +31,22 @@
chunk.cc
)
-pw_add_test(pw_multibuf.chunk
+pw_add_library(pw_multibuf.test_utils STATIC
+ HEADERS
+ public/pw_multibuf/internal/test_utils.h
+ PUBLIC_INCLUDES
+ public
+ PUBLIC_DEPS
+ pw_multibuf.chunk
+ pw_allocator.allocator_metric_proxy
+ pw_allocator.split_free_list_allocator
+
+pw_add_test(pw_multibuf.chunk_test STATIC
SOURCES
chunk_test.cc
PRIVATE_DEPS
- pw_allocator.allocator_metric_proxy
- pw_allocator.split_free_list_allocator
+ pw_multibuf.chunk
+ pw_multibuf.test_utils
GROUPS
modules
pw_multibuf
@@ -58,6 +68,7 @@
multibuf_test.cc
PRIVATE_DEPS
pw_multibuf.multibuf
+ pw_multibuf.test_utils
GROUPS
modules
pw_multibuf
diff --git a/pw_multibuf/chunk_test.cc b/pw_multibuf/chunk_test.cc
index e4f2c08..23ff0e3 100644
--- a/pw_multibuf/chunk_test.cc
+++ b/pw_multibuf/chunk_test.cc
@@ -21,126 +21,13 @@
#endif // __cplusplus >= 202002L
#include "gtest/gtest.h"
-#include "pw_allocator/allocator_metric_proxy.h"
-#include "pw_allocator/split_free_list_allocator.h"
+#include "pw_multibuf/internal/test_utils.h"
namespace pw::multibuf {
namespace {
-class TrackingAllocator : public pw::allocator::Allocator {
- public:
- TrackingAllocator(ByteSpan span) : alloc_stats_(kFakeToken) {
- Status status = alloc_.Init(span, kFakeThreshold);
- EXPECT_EQ(status, OkStatus());
- alloc_stats_.Initialize(alloc_);
- }
-
- size_t count() const { return alloc_stats_.count(); }
- size_t used() const { return alloc_stats_.used(); }
-
- protected:
- void* DoAllocate(size_t size, size_t alignment) override {
- return alloc_stats_.AllocateUnchecked(size, alignment);
- }
- bool DoResize(void* ptr,
- size_t old_size,
- size_t old_align,
- size_t new_size) override {
- return alloc_stats_.ResizeUnchecked(ptr, old_size, old_align, new_size);
- }
- void DoDeallocate(void* ptr, size_t size, size_t alignment) override {
- alloc_stats_.DeallocateUnchecked(ptr, size, alignment);
- }
-
- private:
- const size_t kFakeThreshold = 0;
- const int32_t kFakeToken = 0;
-
- pw::allocator::SplitFreeListAllocator<> alloc_;
- pw::allocator::AllocatorMetricProxy alloc_stats_;
-};
-
-template <auto NumBytes>
-class TrackingAllocatorWithMemory : public pw::allocator::Allocator {
- public:
- TrackingAllocatorWithMemory() : mem_(), alloc_(mem_) {}
- size_t count() const { return alloc_.count(); }
- size_t used() const { return alloc_.used(); }
- void* DoAllocate(size_t size, size_t alignment) override {
- return alloc_.AllocateUnchecked(size, alignment);
- }
- bool DoResize(void* ptr,
- size_t old_size,
- size_t old_align,
- size_t new_size) override {
- return alloc_.ResizeUnchecked(ptr, old_size, old_align, new_size);
- }
- void DoDeallocate(void* ptr, size_t size, size_t alignment) override {
- alloc_.DeallocateUnchecked(ptr, size, alignment);
- }
-
- private:
- std::array<std::byte, NumBytes> mem_;
- TrackingAllocator alloc_;
-};
-
-class HeaderChunkRegionTracker final : public ChunkRegionTracker {
- public:
- static std::optional<OwnedChunk> AllocateRegionAsChunk(
- pw::allocator::Allocator* alloc, size_t size) {
- HeaderChunkRegionTracker* tracker = AllocateRegion(alloc, size);
- if (tracker == nullptr) {
- return std::nullopt;
- }
- std::optional<OwnedChunk> chunk = Chunk::CreateFirstForRegion(*tracker);
- if (!chunk.has_value()) {
- tracker->Destroy();
- return std::nullopt;
- }
- return chunk;
- }
-
- static HeaderChunkRegionTracker* AllocateRegion(
- pw::allocator::Allocator* alloc, size_t size) {
- size_t alloc_size = size + sizeof(HeaderChunkRegionTracker);
- size_t align = alignof(HeaderChunkRegionTracker);
- void* ptr = alloc->AllocateUnchecked(alloc_size, align);
- if (ptr == nullptr) {
- return nullptr;
- }
- std::byte* data =
- reinterpret_cast<std::byte*>(ptr) + sizeof(HeaderChunkRegionTracker);
- return new (ptr) HeaderChunkRegionTracker(ByteSpan(data, size), alloc);
- }
-
- ByteSpan Region() const final { return region_; }
- ~HeaderChunkRegionTracker() final {}
-
- protected:
- void Destroy() final {
- std::byte* ptr = reinterpret_cast<std::byte*>(this);
- size_t size = sizeof(HeaderChunkRegionTracker) + region_.size();
- size_t align = alignof(HeaderChunkRegionTracker);
- auto alloc = alloc_;
- std::destroy_at(this);
- alloc->DeallocateUnchecked(ptr, size, align);
- }
- void* AllocateChunkClass() final {
- return alloc_->Allocate(pw::allocator::Layout::Of<Chunk>());
- }
- void DeallocateChunkClass(void* ptr) final {
- alloc_->Deallocate(ptr, pw::allocator::Layout::Of<Chunk>());
- }
-
- private:
- ByteSpan region_;
- pw::allocator::Allocator* alloc_;
-
- // NOTE: `region` must directly follow this `FakeChunkRegionTracker`
- // in memory allocated by allocated by `alloc`.
- HeaderChunkRegionTracker(ByteSpan region, pw::allocator::Allocator* alloc)
- : region_(region), alloc_(alloc) {}
-};
+using ::pw::multibuf::internal::HeaderChunkRegionTracker;
+using ::pw::multibuf::internal::TrackingAllocatorWithMemory;
/// Returns literal with ``_size`` suffix as a ``size_t``.
///
diff --git a/pw_multibuf/docs.rst b/pw_multibuf/docs.rst
index 78d8919..e19f8e7 100644
--- a/pw_multibuf/docs.rst
+++ b/pw_multibuf/docs.rst
@@ -55,7 +55,8 @@
``MultiBuf`` s consist of a number of ``Chunk`` s of contiguous memory.
These ``Chunk`` s can be grown, shrunk, modified, or extracted from the
-``MultiBuf``.
+``MultiBuf``. ``MultiBuf`` exposes an ``std::byte`` iterator interface as well
+as a ``Chunk`` iterator available through the ``Chunks()`` method.
An RAII-style ``OwnedChunk`` is also provided, and manages the lifetime of
``Chunk`` s which are not currently stored inside of a ``MultiBuf``.
diff --git a/pw_multibuf/multibuf.cc b/pw_multibuf/multibuf.cc
index e69de29..b1eb805 100644
--- a/pw_multibuf/multibuf.cc
+++ b/pw_multibuf/multibuf.cc
@@ -0,0 +1,129 @@
+// Copyright 2023 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.
+
+#include "pw_multibuf/multibuf.h"
+
+#include "pw_assert/check.h"
+
+namespace pw::multibuf {
+
+void MultiBuf::Release() noexcept {
+ while (first_ != nullptr) {
+ Chunk* removed = first_;
+ first_ = first_->next_in_buf_;
+ removed->Free();
+ }
+}
+
+size_t MultiBuf::size() const {
+ size_t len = 0;
+ for (const auto& chunk : Chunks()) {
+ len += chunk.size();
+ }
+ return len;
+}
+
+void MultiBuf::PushFrontChunk(OwnedChunk chunk) {
+ PW_DCHECK(chunk->next_in_buf_ == nullptr);
+ Chunk* new_chunk = std::move(chunk).Take();
+ Chunk* old_first = first_;
+ new_chunk->next_in_buf_ = old_first;
+ first_ = new_chunk;
+}
+
+MultiBuf::ChunkIterator MultiBuf::InsertChunk(ChunkIterator position,
+ OwnedChunk chunk) {
+ // Note: this also catches the cases where ``first_ == nullptr``
+ PW_DCHECK(chunk->next_in_buf_ == nullptr);
+ if (position == ChunkBegin()) {
+ PushFrontChunk(std::move(chunk));
+ return ChunkIterator(first_);
+ }
+ Chunk* previous = Previous(position.chunk_);
+ Chunk* old_next = previous->next_in_buf_;
+ Chunk* new_chunk = std::move(chunk).Take();
+ new_chunk->next_in_buf_ = old_next;
+ previous->next_in_buf_ = new_chunk;
+ return ChunkIterator(new_chunk);
+}
+
+std::tuple<MultiBuf::ChunkIterator, OwnedChunk> MultiBuf::TakeChunk(
+ ChunkIterator position) {
+ Chunk* chunk = position.chunk_;
+ if (position == ChunkBegin()) {
+ Chunk* old_first = first_;
+ first_ = old_first->next_in_buf_;
+ old_first->next_in_buf_ = nullptr;
+ return std::make_tuple(ChunkIterator(first_), OwnedChunk(old_first));
+ }
+ Chunk* previous = Previous(chunk);
+ previous->next_in_buf_ = chunk->next_in_buf_;
+ chunk->next_in_buf_ = nullptr;
+ return std::make_tuple(ChunkIterator(previous->next_in_buf_),
+ OwnedChunk(chunk));
+}
+
+Chunk* MultiBuf::Previous(Chunk* chunk) const {
+ Chunk* previous = first_;
+ while (previous != nullptr && previous->next_in_buf_ != chunk) {
+ previous = previous->next_in_buf_;
+ }
+ return previous;
+}
+
+MultiBuf::iterator& MultiBuf::iterator::operator++() {
+ if (byte_index_ + 1 == chunk_->size()) {
+ chunk_ = chunk_->next_in_buf_;
+ byte_index_ = 0;
+ AdvanceToData();
+ } else {
+ ++byte_index_;
+ }
+ return *this;
+}
+
+void MultiBuf::iterator::AdvanceToData() {
+ while (chunk_ != nullptr && chunk_->size() == 0) {
+ chunk_ = chunk_->next_in_buf_;
+ }
+}
+
+MultiBuf::const_iterator& MultiBuf::const_iterator::operator++() {
+ if (byte_index_ + 1 == chunk_->size()) {
+ chunk_ = chunk_->next_in_buf_;
+ byte_index_ = 0;
+ AdvanceToData();
+ } else {
+ ++byte_index_;
+ }
+ return *this;
+}
+
+void MultiBuf::const_iterator::AdvanceToData() {
+ while (chunk_ != nullptr && chunk_->size() == 0) {
+ chunk_ = chunk_->next_in_buf_;
+ }
+}
+
+size_t MultiBuf::ChunkIterable::size() const {
+ Chunk* current = first_;
+ size_t i = 0;
+ while (current != nullptr) {
+ ++i;
+ current = current->next_in_buf_;
+ }
+ return i;
+}
+
+} // namespace pw::multibuf
diff --git a/pw_multibuf/multibuf_test.cc b/pw_multibuf/multibuf_test.cc
index 285b572..d1bfe96 100644
--- a/pw_multibuf/multibuf_test.cc
+++ b/pw_multibuf/multibuf_test.cc
@@ -15,4 +15,200 @@
#include "pw_multibuf/multibuf.h"
#include "gtest/gtest.h"
-#include "pw_multibuf/chunk.h"
+#include "pw_bytes/suffix.h"
+#include "pw_multibuf/internal/test_utils.h"
+
+namespace pw::multibuf {
+namespace {
+
+using ::pw::multibuf::internal::HeaderChunkRegionTracker;
+using ::pw::multibuf::internal::TrackingAllocatorWithMemory;
+
+const size_t kArbitraryAllocatorSize = 1024;
+const size_t kArbitraryChunkSize = 32;
+
+#if __cplusplus >= 202002L
+static_assert(std::forward_iterator<MultiBuf::iterator>);
+static_assert(std::forward_iterator<MultiBuf::const_iterator>);
+static_assert(std::forward_iterator<MultiBuf::ChunkIterator>);
+static_assert(std::forward_iterator<MultiBuf::ConstChunkIterator>);
+#endif // __cplusplus >= 202002L
+
+OwnedChunk MakeChunk(pw::allocator::Allocator& alloc, size_t size) {
+ std::optional<OwnedChunk> chunk =
+ HeaderChunkRegionTracker::AllocateRegionAsChunk(&alloc, size);
+ assert(chunk.has_value());
+ return std::move(*chunk);
+}
+
+TEST(MultiBuf, IsDefaultConstructible) { [[maybe_unused]] MultiBuf buf; }
+
+TEST(MultiBuf, WithOneChunkReleases) {
+ TrackingAllocatorWithMemory<kArbitraryAllocatorSize> alloc;
+ MultiBuf buf;
+ buf.PushFrontChunk(MakeChunk(alloc, kArbitraryChunkSize));
+ EXPECT_EQ(alloc.count(), 2U);
+ buf.Release();
+ EXPECT_EQ(alloc.count(), 0U);
+}
+
+TEST(MultiBuf, WithOneChunkReleasesOnDestruction) {
+ TrackingAllocatorWithMemory<kArbitraryAllocatorSize> alloc;
+ {
+ MultiBuf buf;
+ buf.PushFrontChunk(MakeChunk(alloc, kArbitraryChunkSize));
+ EXPECT_EQ(alloc.count(), 2U);
+ }
+ EXPECT_EQ(alloc.count(), 0U);
+}
+
+TEST(MultiBuf, WithMultipleChunksReleasesAllOnDestruction) {
+ TrackingAllocatorWithMemory<kArbitraryAllocatorSize> alloc;
+ {
+ MultiBuf buf;
+ buf.PushFrontChunk(MakeChunk(alloc, kArbitraryChunkSize));
+ buf.PushFrontChunk(MakeChunk(alloc, kArbitraryChunkSize));
+ EXPECT_EQ(alloc.count(), 4U);
+ }
+ EXPECT_EQ(alloc.count(), 0U);
+}
+
+TEST(MultiBuf, SizeReturnsNumberOfBytes) {
+ TrackingAllocatorWithMemory<kArbitraryAllocatorSize> alloc;
+ MultiBuf buf;
+ EXPECT_EQ(buf.size(), 0U);
+ buf.PushFrontChunk(MakeChunk(alloc, kArbitraryChunkSize));
+ EXPECT_EQ(buf.size(), kArbitraryChunkSize);
+ buf.PushFrontChunk(MakeChunk(alloc, kArbitraryChunkSize));
+ EXPECT_EQ(buf.size(), kArbitraryChunkSize * 2);
+}
+
+TEST(MultiBuf, PushFrontChunkAddsBytesToFront) {
+ TrackingAllocatorWithMemory<kArbitraryAllocatorSize> alloc;
+ MultiBuf buf;
+
+ const std::array<std::byte, 3> kBytesOne = {0_b, 1_b, 2_b};
+ auto chunk_one = MakeChunk(alloc, kBytesOne.size());
+ std::copy(kBytesOne.begin(), kBytesOne.end(), chunk_one->begin());
+ buf.PushFrontChunk(std::move(chunk_one));
+
+ size_t i = 0;
+ auto buf_iter = buf.begin();
+ for (; i < kBytesOne.size(); i++, buf_iter++) {
+ ASSERT_NE(buf_iter, buf.end());
+ EXPECT_EQ(*buf_iter, kBytesOne[i]);
+ }
+
+ const std::array<std::byte, 4> kBytesTwo = {9_b, 10_b, 11_b, 12_b};
+ auto chunk_two = MakeChunk(alloc, kBytesTwo.size());
+ std::copy(kBytesTwo.begin(), kBytesTwo.end(), chunk_two->begin());
+ buf.PushFrontChunk(std::move(chunk_two));
+
+ std::array<std::byte, 7> expected = {
+ 9_b,
+ 10_b,
+ 11_b,
+ 12_b,
+ 0_b,
+ 1_b,
+ 2_b,
+ };
+ i = 0;
+ buf_iter = buf.begin();
+ for (; i < expected.size(); i++, buf_iter++) {
+ ASSERT_NE(buf_iter, buf.end());
+ EXPECT_EQ(*buf_iter, expected[i]);
+ }
+}
+
+TEST(MultiBuf, InsertChunkOnEmptyBufAddsFirstChunk) {
+ TrackingAllocatorWithMemory<kArbitraryAllocatorSize> alloc;
+ MultiBuf buf;
+
+ const std::array<std::byte, 3> kBytes = {0_b, 1_b, 2_b};
+ auto chunk = MakeChunk(alloc, kBytes.size());
+ std::copy(kBytes.begin(), kBytes.end(), chunk->begin());
+ auto inserted_iter = buf.InsertChunk(buf.Chunks().begin(), std::move(chunk));
+ EXPECT_EQ(inserted_iter, buf.Chunks().begin());
+
+ size_t i = 0;
+ auto buf_iter = buf.begin();
+ for (; i < kBytes.size(); i++, buf_iter++) {
+ ASSERT_NE(buf_iter, buf.end());
+ EXPECT_EQ(*buf_iter, kBytes[i]);
+ }
+
+ EXPECT_EQ(++inserted_iter, buf.Chunks().end());
+}
+
+TEST(MultiBuf, InsertChunkAtEndOfBufAddsLastChunk) {
+ TrackingAllocatorWithMemory<kArbitraryAllocatorSize> alloc;
+ MultiBuf buf;
+
+ // Add a chunk to the beginning
+ buf.PushFrontChunk(MakeChunk(alloc, kArbitraryChunkSize));
+
+ const std::array<std::byte, 3> kBytes = {0_b, 1_b, 2_b};
+ auto chunk = MakeChunk(alloc, kBytes.size());
+ std::copy(kBytes.begin(), kBytes.end(), chunk->begin());
+ auto inserted_iter = buf.InsertChunk(buf.Chunks().end(), std::move(chunk));
+ EXPECT_EQ(inserted_iter, ++buf.Chunks().begin());
+ EXPECT_EQ(++inserted_iter, buf.Chunks().end());
+
+ size_t i = 0;
+ auto buf_iter = buf.Chunks().begin();
+ buf_iter++;
+ auto chunk_iter = buf_iter->begin();
+ for (; i < kBytes.size(); i++, chunk_iter++) {
+ ASSERT_NE(chunk_iter, buf_iter->end());
+ EXPECT_EQ(*chunk_iter, kBytes[i]);
+ }
+}
+
+TEST(MultiBuf, TakeChunkAtBeginRemovesAndReturnsFirstChunk) {
+ TrackingAllocatorWithMemory<kArbitraryAllocatorSize> alloc;
+ MultiBuf buf;
+ auto insert_iter = buf.Chunks().begin();
+ insert_iter = buf.InsertChunk(insert_iter, MakeChunk(alloc, 2));
+ insert_iter = buf.InsertChunk(++insert_iter, MakeChunk(alloc, 4));
+
+ auto [chunk_iter, chunk] = buf.TakeChunk(buf.Chunks().begin());
+ EXPECT_EQ(chunk.size(), 2U);
+ EXPECT_EQ(chunk_iter->size(), 4U);
+ chunk_iter++;
+ EXPECT_EQ(chunk_iter, buf.Chunks().end());
+}
+
+TEST(MultiBuf, TakeChunkOnLastInsertedIterReturnsLastInserted) {
+ TrackingAllocatorWithMemory<kArbitraryAllocatorSize> alloc;
+ MultiBuf buf;
+ auto iter = buf.Chunks().begin();
+ iter = buf.InsertChunk(iter, MakeChunk(alloc, 42));
+ iter = buf.InsertChunk(++iter, MakeChunk(alloc, 11));
+ iter = buf.InsertChunk(++iter, MakeChunk(alloc, 65));
+ OwnedChunk chunk;
+ std::tie(iter, chunk) = buf.TakeChunk(iter);
+ EXPECT_EQ(iter, buf.Chunks().end());
+ EXPECT_EQ(chunk.size(), 65U);
+}
+
+TEST(MultiBuf, RangeBasedForLoopsCompile) {
+ MultiBuf buf;
+ for ([[maybe_unused]] std::byte& byte : buf) {
+ }
+ for ([[maybe_unused]] const std::byte& byte : buf) {
+ }
+ for ([[maybe_unused]] Chunk& chunk : buf.Chunks()) {
+ }
+ for ([[maybe_unused]] const Chunk& chunk : buf.Chunks()) {
+ }
+
+ const MultiBuf const_buf;
+ for ([[maybe_unused]] const std::byte& byte : const_buf) {
+ }
+ for ([[maybe_unused]] const Chunk& chunk : const_buf.Chunks()) {
+ }
+}
+
+} // namespace
+} // namespace pw::multibuf
diff --git a/pw_multibuf/public/pw_multibuf/chunk.h b/pw_multibuf/public/pw_multibuf/chunk.h
index 7dd7ed6..9747b94 100644
--- a/pw_multibuf/public/pw_multibuf/chunk.h
+++ b/pw_multibuf/public/pw_multibuf/chunk.h
@@ -66,9 +66,9 @@
ConstByteSpan span() const { return span_; }
std::byte& operator[](size_t index) { return span_[index]; }
- std::byte operator[](size_t index) const { return span_[index]; }
+ const std::byte& operator[](size_t index) const { return span_[index]; }
- // Iterator declarations
+ // Container declarations
using element_type = std::byte;
using value_type = std::byte;
using size_type = size_t;
@@ -223,7 +223,7 @@
/// last element of a ``MultiBuf``.
//
// reserved for use by the MultiBuf class.
- // Chunk* next_in_buf_;
+ Chunk* next_in_buf_;
/// Pointer to the sub-region to which this chunk has exclusive access.
///
@@ -240,6 +240,7 @@
ByteSpan span_;
friend class OwnedChunk; // for ``Free``.
+ friend class MultiBuf; // for ``Free`` and ``next_in_buf_``.
};
/// An object that manages a single allocated region which is referenced by one
@@ -347,6 +348,14 @@
/// This method will acquire a mutex and is not IRQ safe.
void Release();
+ /// Returns the contained ``Chunk*`` and empties this ``OwnedChunk`` without
+ /// releasing the underlying ``Chunk``.
+ Chunk* Take() && {
+ Chunk* result = inner_;
+ inner_ = nullptr;
+ return result;
+ }
+
private:
/// Constructs a new ``OwnedChunk`` from an existing ``Chunk*``.
OwnedChunk(Chunk* inner) : inner_(inner) {}
@@ -354,9 +363,10 @@
/// A pointer to the owned ``Chunk``.
Chunk* inner_;
- /// Allow ``Chunk`` to create an ``OwnedChunk`` using the private constructor
- /// above.
+ /// Allow ``Chunk`` and ``MultiBuf`` to create ``OwnedChunk``s using the
+ /// private constructor above.
friend class Chunk;
+ friend class MultiBuf;
};
} // namespace pw::multibuf
diff --git a/pw_multibuf/public/pw_multibuf/internal/test_utils.h b/pw_multibuf/public/pw_multibuf/internal/test_utils.h
new file mode 100644
index 0000000..3e713ff
--- /dev/null
+++ b/pw_multibuf/public/pw_multibuf/internal/test_utils.h
@@ -0,0 +1,164 @@
+// Copyright 2023 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
+
+#include <memory>
+
+#include "pw_allocator/allocator_metric_proxy.h"
+#include "pw_allocator/split_free_list_allocator.h"
+#include "pw_multibuf/chunk.h"
+
+namespace pw::multibuf::internal {
+
+/// A basic ``Allocator`` implementation that reports the number and size of
+/// allocations.
+class TrackingAllocator : public pw::allocator::Allocator {
+ public:
+ /// Constructs a new ``TrackingAllocator`` which allocates from the provided
+ /// region of memory.
+ TrackingAllocator(ByteSpan span) : alloc_stats_(kFakeToken) {
+ Status status = alloc_.Init(span, kFakeThreshold);
+ EXPECT_EQ(status, OkStatus());
+ alloc_stats_.Initialize(alloc_);
+ }
+
+ /// Returns the number of current allocations.
+ size_t count() const { return alloc_stats_.count(); }
+
+ /// Returns the combined size in bytes of all current allocations.
+ size_t used() const { return alloc_stats_.used(); }
+
+ protected:
+ void* DoAllocate(size_t size, size_t alignment) override {
+ return alloc_stats_.AllocateUnchecked(size, alignment);
+ }
+ bool DoResize(void* ptr,
+ size_t old_size,
+ size_t old_align,
+ size_t new_size) override {
+ return alloc_stats_.ResizeUnchecked(ptr, old_size, old_align, new_size);
+ }
+ void DoDeallocate(void* ptr, size_t size, size_t alignment) override {
+ alloc_stats_.DeallocateUnchecked(ptr, size, alignment);
+ }
+
+ private:
+ const size_t kFakeThreshold = 0;
+ const int32_t kFakeToken = 0;
+
+ pw::allocator::SplitFreeListAllocator<> alloc_;
+ pw::allocator::AllocatorMetricProxy alloc_stats_;
+};
+
+/// A ``TrackingAllocator`` which holds an internal buffer of size `num_buffer`
+/// for its allocations.
+template <auto num_bytes>
+class TrackingAllocatorWithMemory : public pw::allocator::Allocator {
+ public:
+ TrackingAllocatorWithMemory() : mem_(), alloc_(mem_) {}
+ size_t count() const { return alloc_.count(); }
+ size_t used() const { return alloc_.used(); }
+ void* DoAllocate(size_t size, size_t alignment) override {
+ return alloc_.AllocateUnchecked(size, alignment);
+ }
+ bool DoResize(void* ptr,
+ size_t old_size,
+ size_t old_align,
+ size_t new_size) override {
+ return alloc_.ResizeUnchecked(ptr, old_size, old_align, new_size);
+ }
+ void DoDeallocate(void* ptr, size_t size, size_t alignment) override {
+ alloc_.DeallocateUnchecked(ptr, size, alignment);
+ }
+
+ private:
+ std::array<std::byte, num_bytes> mem_;
+ TrackingAllocator alloc_;
+};
+
+/// A ``ChunkRegionTracker`` which stores its ``Chunk`` and region metadata
+/// in a ``pw::allocator::Allocator`` allocation alongside the data.
+class HeaderChunkRegionTracker final : public ChunkRegionTracker {
+ public:
+ /// Allocates a new ``Chunk`` region of ``size`` bytes in ``alloc``.
+ ///
+ /// The underlyiing allocation will also store the
+ /// ``HeaderChunkRegionTracker`` itself.
+ ///
+ /// Returns the newly-created ``OwnedChunk`` if successful.
+ static std::optional<OwnedChunk> AllocateRegionAsChunk(
+ pw::allocator::Allocator* alloc, size_t size) {
+ HeaderChunkRegionTracker* tracker = AllocateRegion(alloc, size);
+ if (tracker == nullptr) {
+ return std::nullopt;
+ }
+ std::optional<OwnedChunk> chunk = Chunk::CreateFirstForRegion(*tracker);
+ if (!chunk.has_value()) {
+ tracker->Destroy();
+ return std::nullopt;
+ }
+ return chunk;
+ }
+
+ /// Allocates a new ``Chunk`` region of ``size`` bytes in ``alloc``.
+ ///
+ /// The underlyiing allocation will also store the
+ /// ``HeaderChunkRegionTracker`` itself.
+ ///
+ /// Returns a pointer to the newly-created ``HeaderChunkRegionTracker``
+ /// or ``nullptr`` if the allocation failed.
+ static HeaderChunkRegionTracker* AllocateRegion(
+ pw::allocator::Allocator* alloc, size_t size) {
+ const size_t alloc_size = size + sizeof(HeaderChunkRegionTracker);
+ const size_t align = alignof(HeaderChunkRegionTracker);
+ void* ptr = alloc->AllocateUnchecked(alloc_size, align);
+ if (ptr == nullptr) {
+ return nullptr;
+ }
+ std::byte* data =
+ reinterpret_cast<std::byte*>(ptr) + sizeof(HeaderChunkRegionTracker);
+ return new (ptr) HeaderChunkRegionTracker(ByteSpan(data, size), alloc);
+ }
+
+ ByteSpan Region() const final { return region_; }
+ ~HeaderChunkRegionTracker() final {}
+
+ protected:
+ void Destroy() final {
+ std::byte* ptr = reinterpret_cast<std::byte*>(this);
+ const size_t size = sizeof(HeaderChunkRegionTracker) + region_.size();
+ const size_t align = alignof(HeaderChunkRegionTracker);
+ auto alloc = alloc_;
+ std::destroy_at(this);
+ alloc->DeallocateUnchecked(ptr, size, align);
+ }
+ void* AllocateChunkClass() final {
+ return alloc_->Allocate(pw::allocator::Layout::Of<Chunk>());
+ }
+ void DeallocateChunkClass(void* ptr) final {
+ alloc_->Deallocate(ptr, pw::allocator::Layout::Of<Chunk>());
+ }
+
+ private:
+ ByteSpan region_;
+ pw::allocator::Allocator* alloc_;
+
+ // NOTE: `region` must directly follow this `FakeChunkRegionTracker`
+ // in memory allocated by allocated by `alloc`.
+ HeaderChunkRegionTracker(ByteSpan region, pw::allocator::Allocator* alloc)
+ : region_(region), alloc_(alloc) {}
+};
+
+} // namespace pw::multibuf::internal
diff --git a/pw_multibuf/public/pw_multibuf/multibuf.h b/pw_multibuf/public/pw_multibuf/multibuf.h
index 3d037e1..a48ce6f 100644
--- a/pw_multibuf/public/pw_multibuf/multibuf.h
+++ b/pw_multibuf/public/pw_multibuf/multibuf.h
@@ -13,17 +13,359 @@
// the License.
#pragma once
+#include <tuple>
+
#include "pw_multibuf/chunk.h"
namespace pw::multibuf {
/// A buffer optimized for zero-copy data transfer.
///
-/// A ``MultiBuf`` consists of one or more ``Chunk`` s of data.
+/// A ``MultiBuf`` consists of multiple ``Chunk`` s of data.
class MultiBuf {
public:
+ class iterator;
+ class const_iterator;
+ class ChunkIterator;
+ class ConstChunkIterator;
+ class ChunkIterable;
+ class ConstChunkIterable;
+
+ constexpr MultiBuf() : first_(nullptr) {}
+ constexpr MultiBuf(MultiBuf&& other) noexcept : first_(other.first_) {
+ other.first_ = nullptr;
+ }
+ MultiBuf& operator=(MultiBuf&& other) noexcept {
+ Release();
+ first_ = other.first_;
+ other.first_ = nullptr;
+ return *this;
+ }
+
+ /// Decrements the reference count on the underlying chunks of data and
+ /// empties this ``MultiBuf`` so that ``size() == 0``.
+ ///
+ /// Does not modify the underlying data, but may cause it to be deallocated
+ ///
+ /// This method is equivalent to ``{ MultiBuf _unused = std::move(multibuf);
+ /// }``
+ ///
+ /// This method will acquire a mutex and is not IRQ safe.
+ void Release() noexcept;
+
+ /// This destructor will acquire a mutex and is not IRQ safe.
+ ~MultiBuf() { Release(); }
+
+ /// Returns the number of bytes in this container.
+ ///
+ /// This method's complexity is ``O(Chunks().size())``.
+ [[nodiscard]] size_t size() const;
+
+ /// Pushes ``Chunk`` onto the front of the ``MultiBuf``.
+ ///
+ /// This operation does not move any data and is ``O(1)``.
+ void PushFrontChunk(OwnedChunk chunk);
+
+ /// Inserts ``chunk`` into the specified position in the ``MultiBuf``.
+ ///
+ /// This operation does not move any data and is ``O(Chunks().size())``.
+ ///
+ /// Returns an iterator pointing to the newly-inserted ``Chunk``.
+ //
+ // Implementation note: ``Chunks().size()`` should be remain relatively
+ // small, but this could be made ``O(1)`` in the future by adding a ``prev``
+ // pointer to the ``ChunkIterator``.
+ ChunkIterator InsertChunk(ChunkIterator position, OwnedChunk chunk);
+
+ /// Removes a ``Chunk`` from the specified position.
+ ///
+ /// This operation does not move any data and is ``O(Chunks().size())``.
+ ///
+ /// Returns an iterator pointing to the ``Chunk`` after the removed
+ /// ``Chunk``, or ``Chunks().end()`` if this was the last ``Chunk`` in the
+ /// ``MultiBuf``.
+ //
+ // Implementation note: ``Chunks().size()`` should be remain relatively
+ // small, but this could be made ``O(1)`` in the future by adding a ``prev``
+ // pointer to the ``ChunkIterator``.
+ std::tuple<ChunkIterator, OwnedChunk> TakeChunk(ChunkIterator position);
+
+ /// Returns an iterator pointing to the first byte of this ``MultiBuf`.
+ iterator begin() { return iterator(first_, 0); }
+ /// Returns a const iterator pointing to the first byte of this ``MultiBuf`.
+ const_iterator begin() const { return const_iterator(first_, 0); }
+ /// Returns a const iterator pointing to the first byte of this ``MultiBuf`.
+ const_iterator cbegin() const { return const_iterator(first_, 0); }
+
+ /// Returns an iterator pointing to the end of this ``MultiBuf``.
+ iterator end() { return iterator::end(); }
+ /// Returns a const iterator pointing to the end of this ``MultiBuf``.
+ const_iterator end() const { return const_iterator::end(); }
+ /// Returns a const iterator pointing to the end of this ``MultiBuf``.
+ const_iterator cend() const { return const_iterator::end(); }
+
+ /// Returns an iterable container which yields the ``Chunk``s in this
+ /// ``MultiBuf``.
+ constexpr ChunkIterable Chunks() { return ChunkIterable(first_); }
+
+ /// Returns an iterable container which yields the ``const Chunk``s in
+ /// this ``MultiBuf``.
+ constexpr const ChunkIterable Chunks() const { return ChunkIterable(first_); }
+
+ /// Returns an iterator pointing to the first ``Chunk`` in this ``MultiBuf``.
+ constexpr ChunkIterator ChunkBegin() { return ChunkIterator(first_); }
+ /// Returns an iterator pointing to the end of the ``Chunk``s in this
+ /// ``MultiBuf``.
+ constexpr ChunkIterator ChunkEnd() { return ChunkIterator::end(); }
+ /// Returns a const iterator pointing to the first ``Chunk`` in this
+ /// ``MultiBuf``.
+ constexpr ConstChunkIterator ConstChunkBegin() {
+ return ConstChunkIterator(first_);
+ }
+ /// Returns a const iterator pointing to the end of the ``Chunk``s in this
+ /// ``MultiBuf``.
+ constexpr ConstChunkIterator ConstChunkEnd() {
+ return ConstChunkIterator::end();
+ }
+
+ ///////////////////////////////////////////////////////////////////
+ //--------------------- Iterator details ------------------------//
+ ///////////////////////////////////////////////////////////////////
+
+ using element_type = std::byte;
+ using value_type = std::byte;
+ using pointer = std::byte*;
+ using const_pointer = const std::byte*;
+ using reference = std::byte&;
+ using const_reference = const std::byte&;
+ using difference_type = std::ptrdiff_t;
+ using size_type = std::size_t;
+
+ /// An ``std::forward_iterator`` over the bytes of a ``MultiBuf``.
+ class iterator {
+ public:
+ using value_type = std::byte;
+ using difference_type = std::ptrdiff_t;
+ using reference = std::byte&;
+ using pointer = std::byte*;
+ using iterator_category = std::forward_iterator_tag;
+
+ constexpr iterator() = default;
+ iterator(Chunk* chunk, size_t byte_index)
+ : chunk_(chunk), byte_index_(byte_index) {
+ AdvanceToData();
+ }
+ static iterator end() { return iterator(nullptr, 0); }
+
+ reference operator*() const { return (*chunk_)[byte_index_]; }
+ pointer operator->() const { return &(*chunk_)[byte_index_]; }
+
+ iterator& operator++();
+ iterator operator++(int) {
+ iterator tmp = *this;
+ ++(*this);
+ return tmp;
+ }
+ constexpr bool operator==(const iterator& other) const {
+ return chunk_ == other.chunk_ && byte_index_ == other.byte_index_;
+ }
+ constexpr bool operator!=(const iterator& other) const {
+ return chunk_ != other.chunk_ || byte_index_ != other.byte_index_;
+ }
+
+ /// Returns the current ``Chunk`` pointed to by this `iterator`.
+ constexpr Chunk* chunk() const { return chunk_; }
+
+ /// Returns the index of the byte pointed to by this `iterator` within the
+ /// current ``Chunk``.
+ constexpr size_t byte_index() const { return byte_index_; }
+
+ private:
+ void AdvanceToData();
+
+ Chunk* chunk_ = nullptr;
+ size_t byte_index_ = 0;
+ };
+
+ /// A const ``std::forward_iterator`` over the bytes of a ``MultiBuf``.
+ class const_iterator {
+ public:
+ using value_type = std::byte;
+ using difference_type = std::ptrdiff_t;
+ using reference = const std::byte&;
+ using pointer = const std::byte*;
+ using iterator_category = std::forward_iterator_tag;
+
+ constexpr const_iterator() = default;
+ const_iterator(const Chunk* chunk, size_t byte_index)
+ : chunk_(chunk), byte_index_(byte_index) {
+ AdvanceToData();
+ }
+ static const_iterator end() { return const_iterator(nullptr, 0); }
+
+ reference operator*() const { return (*chunk_)[byte_index_]; }
+ pointer operator->() const { return &(*chunk_)[byte_index_]; }
+
+ const_iterator& operator++();
+ const_iterator operator++(int) {
+ const_iterator tmp = *this;
+ ++(*this);
+ return tmp;
+ }
+
+ constexpr bool operator==(const const_iterator& other) const {
+ return chunk_ == other.chunk_ && byte_index_ == other.byte_index_;
+ }
+
+ constexpr bool operator!=(const const_iterator& other) const {
+ return chunk_ != other.chunk_ || byte_index_ != other.byte_index_;
+ }
+
+ /// Returns the current ``Chunk`` pointed to by this `iterator`.
+ constexpr const Chunk* chunk() const { return chunk_; }
+
+ /// Returns the index of the byte pointed to by this `iterator` within the
+ /// current ``Chunk``.
+ constexpr size_t byte_index() const { return byte_index_; }
+
+ private:
+ void AdvanceToData();
+
+ const Chunk* chunk_ = nullptr;
+ size_t byte_index_ = 0;
+ };
+
+ /// An iterable containing the ``Chunk`` s of a ``MultiBuf``.
+ class ChunkIterable {
+ public:
+ using element_type = Chunk;
+ using value_type = Chunk;
+ using pointer = Chunk*;
+ using reference = Chunk&;
+ using const_pointer = const Chunk*;
+ using difference_type = std::ptrdiff_t;
+ using const_reference = const Chunk&;
+ using size_type = std::size_t;
+
+ constexpr ChunkIterator begin() { return ChunkIterator(first_); }
+ constexpr ConstChunkIterator begin() const { return cbegin(); }
+ constexpr ConstChunkIterator cbegin() const {
+ return ConstChunkIterator(first_);
+ }
+ constexpr ChunkIterator end() { return ChunkIterator::end(); }
+ constexpr ConstChunkIterator end() const { return cend(); }
+ constexpr ConstChunkIterator cend() const {
+ return ConstChunkIterator::end();
+ }
+
+ /// Returns the number of ``Chunk``s in this iterable.
+ size_t size() const;
+
+ private:
+ Chunk* first_ = nullptr;
+ constexpr ChunkIterable(Chunk* chunk) : first_(chunk) {}
+ friend class MultiBuf;
+ };
+
+ /// A ``std::forward_iterator`` over the ``Chunk``s of a ``MultiBuf``.
+ class ChunkIterator {
+ public:
+ using value_type = Chunk;
+ using difference_type = std::ptrdiff_t;
+ using reference = Chunk&;
+ using pointer = Chunk*;
+ using iterator_category = std::forward_iterator_tag;
+
+ constexpr ChunkIterator() = default;
+
+ constexpr reference operator*() const { return *chunk_; }
+ constexpr pointer operator->() const { return chunk_; }
+
+ constexpr ChunkIterator& operator++() {
+ chunk_ = chunk_->next_in_buf_;
+ return *this;
+ }
+
+ constexpr ChunkIterator operator++(int) {
+ ChunkIterator tmp = *this;
+ ++(*this);
+ return tmp;
+ }
+
+ constexpr bool operator==(const ChunkIterator& other) const {
+ return chunk_ == other.chunk_;
+ }
+
+ constexpr bool operator!=(const ChunkIterator& other) const {
+ return chunk_ != other.chunk_;
+ }
+
+ constexpr Chunk* chunk() const { return chunk_; }
+
+ private:
+ constexpr ChunkIterator(Chunk* chunk) : chunk_(chunk) {}
+ static constexpr ChunkIterator end() { return ChunkIterator(nullptr); }
+ Chunk* chunk_ = nullptr;
+ friend class MultiBuf;
+ friend class ChunkIterable;
+ };
+
+ /// A const ``std::forward_iterator`` over the ``Chunk``s of a ``MultiBuf``.
+ class ConstChunkIterator {
+ public:
+ using value_type = const Chunk;
+ using difference_type = std::ptrdiff_t;
+ using reference = const Chunk&;
+ using pointer = const Chunk*;
+ using iterator_category = std::forward_iterator_tag;
+
+ constexpr ConstChunkIterator() = default;
+
+ constexpr reference operator*() const { return *chunk_; }
+ constexpr pointer operator->() const { return chunk_; }
+
+ constexpr ConstChunkIterator& operator++() {
+ chunk_ = chunk_->next_in_buf_;
+ return *this;
+ }
+
+ constexpr ConstChunkIterator operator++(int) {
+ ConstChunkIterator tmp = *this;
+ ++(*this);
+ return tmp;
+ }
+
+ constexpr bool operator==(const ConstChunkIterator& other) const {
+ return chunk_ == other.chunk_;
+ }
+
+ constexpr bool operator!=(const ConstChunkIterator& other) const {
+ return chunk_ != other.chunk_;
+ }
+
+ constexpr const Chunk* chunk() const { return chunk_; }
+
+ private:
+ constexpr ConstChunkIterator(const Chunk* chunk) : chunk_(chunk) {}
+ static constexpr ConstChunkIterator end() {
+ return ConstChunkIterator(nullptr);
+ }
+ const Chunk* chunk_ = nullptr;
+ friend class MultiBuf;
+ friend class ChunkIterable;
+ };
+
private:
- OwnedChunk chunk_;
+ /// Returns the ``Chunk`` preceding ``chunk`` in this ``MultiBuf``.
+ ///
+ /// Requires that this ``MultiBuf`` is not empty, and that ``chunk``
+ /// is either in ``MultiBuf`` or is ``nullptr``, in which case the last
+ /// ``Chunk`` in ``MultiBuf`` will be returned.
+ ///
+ /// This operation is ``O(Chunks().size())``.
+ Chunk* Previous(Chunk* chunk) const;
+
+ Chunk* first_;
};
class MultiBufAllocator {};
