From 429b6eb2ffcbdd0b30d0058d01cc19570e3e6b4b Mon Sep 17 00:00:00 2001 From: Stefan Boberg Date: Mon, 24 May 2021 13:26:27 +0200 Subject: Initial implementation of CompositeBuffer A CompositeBuffer is a non-contiguous buffer composed of zero or more immutable shared buffers --- zencore/compositebuffer.cpp | 341 ++++++++++++++++++++++++++++++ zencore/include/zencore/compositebuffer.h | 127 +++++++++++ zencore/zencore.cpp | 20 +- zencore/zencore.vcxproj | 3 + zencore/zencore.vcxproj.filters | 3 + 5 files changed, 485 insertions(+), 9 deletions(-) create mode 100644 zencore/compositebuffer.cpp create mode 100644 zencore/include/zencore/compositebuffer.h diff --git a/zencore/compositebuffer.cpp b/zencore/compositebuffer.cpp new file mode 100644 index 000000000..9349c014f --- /dev/null +++ b/zencore/compositebuffer.cpp @@ -0,0 +1,341 @@ +// Copyright Epic Games, Inc. All Rights Reserved. + +#include + +#include + +#include + +namespace zen { + +const CompositeBuffer CompositeBuffer::Null; + +void +CompositeBuffer::Reset() +{ + m_Segments.clear(); +} + +uint64_t +CompositeBuffer::GetSize() const +{ + uint64_t Accum = 0; + + for (const SharedBuffer& It : m_Segments) + { + Accum += It.GetSize(); + } + + return Accum; +} + +bool +CompositeBuffer::IsOwned() const +{ + for (const SharedBuffer& It : m_Segments) + { + if (It.IsOwned() == false) + { + return false; + } + } + return true; +} + +CompositeBuffer +CompositeBuffer::MakeOwned() const& +{ + return CompositeBuffer(*this).MakeOwned(); +} + +CompositeBuffer +CompositeBuffer::MakeOwned() && +{ + for (SharedBuffer& Segment : m_Segments) + { + Segment = std::move(Segment).MakeOwned(); + } + return std::move(*this); +} + +SharedBuffer +CompositeBuffer::Flatten() const& +{ + switch (m_Segments.size()) + { + case 0: + return SharedBuffer(); + case 1: + return m_Segments[0]; + default: + UniqueBuffer Buffer = UniqueBuffer::Alloc(GetSize()); + MutableMemoryView OutView = Buffer.GetMutableView(); + + for (const SharedBuffer& Segment : m_Segments) + { + OutView.CopyFrom(Segment.GetView()); + OutView += Segment.GetSize(); + } + + return Buffer.MoveToShared(); + } +} + +SharedBuffer +CompositeBuffer::Flatten() && +{ + return m_Segments.size() == 1 ? std::move(m_Segments[0]) : std::as_const(*this).Flatten(); +} + +CompositeBuffer +CompositeBuffer::Mid(uint64_t Offset, uint64_t Size) const +{ + const uint64_t BufferSize = GetSize(); + Offset = zen::Min(Offset, BufferSize); + Size = zen::Min(Size, BufferSize - Offset); + CompositeBuffer Buffer; + IterateRange(Offset, Size, [&Buffer](MemoryView View, const SharedBuffer& ViewOuter) { + Buffer.m_Segments.push_back(SharedBuffer::MakeView(View, ViewOuter)); + }); + return Buffer; +} + +MemoryView +CompositeBuffer::ViewOrCopyRange(uint64_t Offset, uint64_t Size, UniqueBuffer& CopyBuffer) const +{ + MemoryView View; + IterateRange(Offset, Size, [Size, &View, &CopyBuffer, WriteView = MutableMemoryView()](MemoryView Segment) mutable { + if (Size == Segment.GetSize()) + { + View = Segment; + } + else + { + if (WriteView.IsEmpty()) + { + if (CopyBuffer.GetSize() < Size) + { + CopyBuffer = UniqueBuffer::Alloc(Size); + } + View = WriteView = CopyBuffer.GetMutableView().Left(Size); + } + WriteView = WriteView.CopyFrom(Segment); + } + }); + return View; +} + +void +CompositeBuffer::CopyTo(MutableMemoryView Target, uint64_t Offset) const +{ + IterateRange(Offset, Target.GetSize(), [Target](MemoryView View, [[maybe_unused]] const SharedBuffer& ViewOuter) mutable { + Target = Target.CopyFrom(View); + }); +} + +void +CompositeBuffer::IterateRange(uint64_t Offset, uint64_t Size, std::function Visitor) const +{ + IterateRange(Offset, Size, [Visitor](MemoryView View, [[maybe_unused]] const SharedBuffer& ViewOuter) { Visitor(View); }); +} + +void +CompositeBuffer::IterateRange(uint64_t Offset, + uint64_t Size, + std::function Visitor) const +{ + ZEN_ASSERT(Offset + Size <= GetSize()); + for (const SharedBuffer& Segment : m_Segments) + { + if (const uint64_t SegmentSize = Segment.GetSize(); Offset <= SegmentSize) + { + const MemoryView View = Segment.GetView().Mid(Offset, Size); + Offset = 0; + if (Size == 0 || !View.IsEmpty()) + { + Visitor(View, Segment); + } + Size -= View.GetSize(); + if (Size == 0) + { + break; + } + } + else + { + Offset -= SegmentSize; + } + } +} + +TEST_CASE("CompositeBuffer Null") +{ + CompositeBuffer Buffer; + CHECK(Buffer.IsNull()); + CHECK(Buffer.IsOwned()); + CHECK(Buffer.MakeOwned().IsNull()); + CHECK(Buffer.Flatten().IsNull()); + CHECK(Buffer.Mid(0, 0).IsNull()); + CHECK(Buffer.GetSize() == 0); + CHECK(Buffer.GetSegments().size() == 0); + + UniqueBuffer CopyBuffer; + CHECK(Buffer.ViewOrCopyRange(0, 0, CopyBuffer).IsEmpty()); + CHECK(CopyBuffer.IsNull()); + + MutableMemoryView CopyView; + Buffer.CopyTo(CopyView); + + uint32_t VisitCount = 0; + Buffer.IterateRange(0, 0, [&VisitCount](MemoryView) { ++VisitCount; }); + CHECK(VisitCount == 0); +} + +TEST_CASE("CompositeBuffer Empty") +{ + const uint8_t EmptyArray[]{0}; + const SharedBuffer EmptyView = SharedBuffer::MakeView(EmptyArray, 0); + CompositeBuffer Buffer(EmptyView); + CHECK(Buffer.IsNull() == false); + CHECK(Buffer.IsOwned() == false); + CHECK(Buffer.MakeOwned().IsNull() == false); + CHECK(Buffer.MakeOwned().IsOwned() == true); + CHECK(Buffer.Flatten() == EmptyView); + CHECK(Buffer.Mid(0, 0).Flatten() == EmptyView); + CHECK(Buffer.GetSize() == 0); + CHECK(Buffer.GetSegments().size() == 1); + CHECK(Buffer.GetSegments()[0] == EmptyView); + + UniqueBuffer CopyBuffer; + CHECK(Buffer.ViewOrCopyRange(0, 0, CopyBuffer) == EmptyView.GetView()); + CHECK(CopyBuffer.IsNull()); + + MutableMemoryView CopyView; + Buffer.CopyTo(CopyView); + + uint32_t VisitCount = 0; + Buffer.IterateRange(0, 0, [&VisitCount](MemoryView) { ++VisitCount; }); + CHECK(VisitCount == 1); +} + +TEST_CASE("CompositeBuffer Empty[1]") +{ + const uint8_t EmptyArray[1]{}; + const SharedBuffer EmptyView1 = SharedBuffer::MakeView(EmptyArray, 0); + const SharedBuffer EmptyView2 = SharedBuffer::MakeView(EmptyArray + 1, 0); + CompositeBuffer Buffer(EmptyView1, EmptyView2); + CHECK(Buffer.Mid(0, 0).Flatten() == EmptyView1); + CHECK(Buffer.GetSize() == 0); + CHECK(Buffer.GetSegments().size() == 2); + CHECK(Buffer.GetSegments()[0] == EmptyView1); + CHECK(Buffer.GetSegments()[1] == EmptyView2); + + UniqueBuffer CopyBuffer; + CHECK(Buffer.ViewOrCopyRange(0, 0, CopyBuffer) == EmptyView1.GetView()); + CHECK(CopyBuffer.IsNull()); + + MutableMemoryView CopyView; + Buffer.CopyTo(CopyView); + + uint32_t VisitCount = 0; + Buffer.IterateRange(0, 0, [&VisitCount](MemoryView) { ++VisitCount; }); + CHECK(VisitCount == 1); +} + +TEST_CASE("CompositeBuffer Flat") +{ + const uint8_t FlatArray[]{1, 2, 3, 4, 5, 6, 7, 8}; + const SharedBuffer FlatView = SharedBuffer::Clone(MakeMemoryView(FlatArray)); + CompositeBuffer Buffer(FlatView); + + CHECK(Buffer.IsNull() == false); + CHECK(Buffer.IsOwned() == true); + CHECK(Buffer.Flatten() == FlatView); + CHECK(Buffer.MakeOwned().Flatten() == FlatView); + CHECK(Buffer.Mid(0).Flatten() == FlatView); + CHECK(Buffer.Mid(4).Flatten().GetView() == FlatView.GetView().Mid(4)); + CHECK(Buffer.Mid(8).Flatten().GetView() == FlatView.GetView().Mid(8)); + CHECK(Buffer.Mid(4, 2).Flatten().GetView() == FlatView.GetView().Mid(4, 2)); + CHECK(Buffer.Mid(8, 0).Flatten().GetView() == FlatView.GetView().Mid(8, 0)); + CHECK(Buffer.GetSize() == sizeof(FlatArray)); + CHECK(Buffer.GetSegments().size() == 1); + CHECK(Buffer.GetSegments()[0] == FlatView); + + UniqueBuffer CopyBuffer; + CHECK(Buffer.ViewOrCopyRange(0, sizeof(FlatArray), CopyBuffer) == FlatView.GetView()); + CHECK(CopyBuffer.IsNull()); + + uint8_t CopyArray[sizeof(FlatArray) - 3]; + Buffer.CopyTo(MakeMutableMemoryView(CopyArray), 3); + CHECK(MakeMemoryView(CopyArray).EqualBytes(MakeMemoryView(FlatArray) + 3)); + + uint32_t VisitCount = 0; + Buffer.IterateRange(0, sizeof(FlatArray), [&VisitCount](MemoryView) { ++VisitCount; }); + CHECK(VisitCount == 1); +} + +TEST_CASE("CompositeBuffer Composite") +{ + const uint8_t FlatArray[]{1, 2, 3, 4, 5, 6, 7, 8}; + const SharedBuffer FlatView1 = SharedBuffer::MakeView(MakeMemoryView(FlatArray).Left(4)); + const SharedBuffer FlatView2 = SharedBuffer::MakeView(MakeMemoryView(FlatArray).Right(4)); + CompositeBuffer Buffer(FlatView1, FlatView2); + + CHECK(Buffer.IsNull() == false); + CHECK(Buffer.IsOwned() == false); + CHECK(Buffer.Flatten().GetView().EqualBytes(MakeMemoryView(FlatArray))); + CHECK(Buffer.Mid(2, 4).Flatten().GetView().EqualBytes(MakeMemoryView(FlatArray).Mid(2, 4))); + CHECK(Buffer.Mid(0, 4).Flatten() == FlatView1); + CHECK(Buffer.Mid(4, 4).Flatten() == FlatView2); + CHECK(Buffer.GetSize() == sizeof(FlatArray)); + CHECK(Buffer.GetSegments().size() == 2); + CHECK(Buffer.GetSegments()[0] == FlatView1); + CHECK(Buffer.GetSegments()[1] == FlatView2); + + UniqueBuffer CopyBuffer; + + CHECK(Buffer.ViewOrCopyRange(0, 4, CopyBuffer) == FlatView1.GetView()); + CHECK(CopyBuffer.IsNull() == true); + CHECK(Buffer.ViewOrCopyRange(4, 4, CopyBuffer) == FlatView2.GetView()); + CHECK(CopyBuffer.IsNull() == true); + CHECK(Buffer.ViewOrCopyRange(3, 2, CopyBuffer).EqualBytes(MakeMemoryView(FlatArray).Mid(3, 2))); + CHECK(CopyBuffer.GetSize() == 2); + CHECK(Buffer.ViewOrCopyRange(1, 6, CopyBuffer).EqualBytes(MakeMemoryView(FlatArray).Mid(1, 6))); + CHECK(CopyBuffer.GetSize() == 6); + CHECK(Buffer.ViewOrCopyRange(2, 4, CopyBuffer).EqualBytes(MakeMemoryView(FlatArray).Mid(2, 4))); + CHECK(CopyBuffer.GetSize() == 6); + + uint8_t CopyArray[4]; + Buffer.CopyTo(MakeMutableMemoryView(CopyArray), 2); + CHECK(MakeMemoryView(CopyArray).EqualBytes(MakeMemoryView(FlatArray).Mid(2, 4))); + + uint32_t VisitCount = 0; + Buffer.IterateRange(0, sizeof(FlatArray), [&VisitCount](MemoryView) { ++VisitCount; }); + CHECK(VisitCount == 2); + + const auto TestIterateRange = + [&Buffer](uint64_t Offset, uint64_t Size, MemoryView ExpectedView, const SharedBuffer& ExpectedViewOuter) { + uint32_t VisitCount = 0; + MemoryView ActualView; + SharedBuffer ActualViewOuter; + Buffer.IterateRange(Offset, Size, [&VisitCount, &ActualView, &ActualViewOuter](MemoryView View, const SharedBuffer& ViewOuter) { + ++VisitCount; + ActualView = View; + ActualViewOuter = ViewOuter; + }); + CHECK(VisitCount == 1); + CHECK(ActualView == ExpectedView); + CHECK(ActualViewOuter == ExpectedViewOuter); + }; + TestIterateRange(0, 4, MakeMemoryView(FlatArray).Mid(0, 4), FlatView1); + TestIterateRange(4, 0, MakeMemoryView(FlatArray).Mid(4, 0), FlatView1); + TestIterateRange(4, 4, MakeMemoryView(FlatArray).Mid(4, 4), FlatView2); + TestIterateRange(8, 0, MakeMemoryView(FlatArray).Mid(8, 0), FlatView2); +} + +void +compositebuffer_forcelink() +{ +} + +} // namespace zen diff --git a/zencore/include/zencore/compositebuffer.h b/zencore/include/zencore/compositebuffer.h new file mode 100644 index 000000000..7b2bbf48f --- /dev/null +++ b/zencore/include/zencore/compositebuffer.h @@ -0,0 +1,127 @@ +// Copyright Epic Games, Inc. All Rights Reserved. + +#pragma once + +#include +#include + +#include +#include +#include + +namespace zen { + +/** + * CompositeBuffer is a non-contiguous buffer composed of zero or more immutable shared buffers. + * + * A composite buffer is most efficient when its segments are consumed as they are, but it can be + * flattened into a contiguous buffer, when necessary, by calling Flatten(). Ownership of segment + * buffers is not changed on construction, but if ownership of segments is required then that can + * be guaranteed by calling MakeOwned(). + */ + +class CompositeBuffer +{ +public: + /** + * Construct a composite buffer by concatenating the buffers. Does not enforce ownership. + * + * Buffer parameters may be SharedBuffer, CompositeBuffer, or std::vector. + */ + template + inline explicit CompositeBuffer(BufferTypes&&... Buffers) + { + if constexpr (sizeof...(Buffers) > 0) + { + m_Segments.reserve((GetBufferCount(std::forward(Buffers)) + ...)); + (AppendBuffers(std::forward(Buffers)), ...); + std::erase_if(m_Segments, [](const SharedBuffer& It) { return It.IsNull(); }); + } + } + + /** Reset this to null. */ + ZENCORE_API void Reset(); + + /** Returns the total size of the composite buffer in bytes. */ + [[nodiscard]] ZENCORE_API uint64_t GetSize() const; + + /** Returns the segments that the buffer is composed from. */ + [[nodiscard]] inline std::span GetSegments() const { return std::span{m_Segments}; } + + /** Returns true if the composite buffer is not null. */ + [[nodiscard]] inline explicit operator bool() const { return !IsNull(); } + + /** Returns true if the composite buffer is null. */ + [[nodiscard]] inline bool IsNull() const { return m_Segments.empty(); } + + /** Returns true if every segment in the composite buffer is owned. */ + [[nodiscard]] ZENCORE_API bool IsOwned() const; + + /** Returns a copy of the buffer where every segment is owned. */ + [[nodiscard]] ZENCORE_API CompositeBuffer MakeOwned() const&; + [[nodiscard]] ZENCORE_API CompositeBuffer MakeOwned() &&; + + /** Returns the concatenation of the segments into a contiguous buffer. */ + [[nodiscard]] ZENCORE_API SharedBuffer Flatten() const&; + [[nodiscard]] ZENCORE_API SharedBuffer Flatten() &&; + + /** Returns the middle part of the buffer by taking the size starting at the offset. */ + [[nodiscard]] ZENCORE_API CompositeBuffer Mid(uint64_t Offset, uint64_t Size = ~uint64_t(0)) const; + + /** + * Returns a view of the range if contained by one segment, otherwise a view of a copy of the range. + * + * @note CopyBuffer is reused if large enough, and otherwise allocated when needed. + * + * @param Offset The byte offset in this buffer that the range starts at. + * @param Size The number of bytes in the range to view or copy. + * @param CopyBuffer The buffer to write the copy into if a copy is required. + */ + [[nodiscard]] ZENCORE_API MemoryView ViewOrCopyRange(uint64_t Offset, uint64_t Size, UniqueBuffer& CopyBuffer) const; + + /** + * Copies a range of the buffer to a contiguous region of memory. + * + * @param Target The view to copy to. Must be no larger than the data available at the offset. + * @param Offset The byte offset in this buffer to start copying from. + */ + ZENCORE_API void CopyTo(MutableMemoryView Target, uint64_t Offset = 0) const; + + /** + * Invokes a visitor with a view of each segment that intersects with a range. + * + * @param Offset The byte offset in this buffer to start visiting from. + * @param Size The number of bytes in the range to visit. + * @param Visitor The visitor to invoke from zero to GetSegments().Num() times. + */ + ZENCORE_API void IterateRange(uint64_t Offset, uint64_t Size, std::function Visitor) const; + ZENCORE_API void IterateRange(uint64_t Offset, + uint64_t Size, + std::function Visitor) const; + + /** A null composite buffer. */ + static const CompositeBuffer Null; + +private: + static inline size_t GetBufferCount(const CompositeBuffer& Buffer) { return Buffer.m_Segments.size(); } + inline void AppendBuffers(const CompositeBuffer& Buffer) + { + m_Segments.insert(m_Segments.end(), begin(Buffer.m_Segments), end(Buffer.m_Segments)); + } + inline void AppendBuffers(CompositeBuffer&& Buffer) + { + // TODO: this operates just like the by-reference version above + m_Segments.insert(m_Segments.end(), begin(Buffer.m_Segments), end(Buffer.m_Segments)); + } + + static inline size_t GetBufferCount(const SharedBuffer&) { return 1; } + inline void AppendBuffers(const SharedBuffer& Buffer) { m_Segments.push_back(Buffer); } + inline void AppendBuffers(SharedBuffer&& Buffer) { m_Segments.push_back(std::move(Buffer)); } + +private: + std::vector m_Segments; +}; + +void compositebuffer_forcelink(); // internal + +} // namespace zen diff --git a/zencore/zencore.cpp b/zencore/zencore.cpp index d4853b043..4648aac9e 100644 --- a/zencore/zencore.cpp +++ b/zencore/zencore.cpp @@ -8,6 +8,7 @@ #include #include #include +#include #include #include #include @@ -51,20 +52,21 @@ RequestApplicationExit(int ExitCode) void zencore_forcelinktests() { - zen::sha1_forcelink(); zen::blake3_forcelink(); - zen::trace_forcelink(); - zen::timer_forcelink(); - zen::uid_forcelink(); - zen::string_forcelink(); - zen::thread_forcelink(); - zen::stream_forcelink(); + zen::compositebuffer_forcelink(); + zen::iobuffer_forcelink(); + zen::memory_forcelink(); zen::refcount_forcelink(); + zen::sha1_forcelink(); zen::snapshotmanifest_forcelink(); - zen::iobuffer_forcelink(); zen::stats_forcelink(); + zen::stream_forcelink(); + zen::string_forcelink(); + zen::thread_forcelink(); + zen::timer_forcelink(); + zen::trace_forcelink(); + zen::uid_forcelink(); zen::uson_forcelink(); zen::usonbuilder_forcelink(); zen::usonpackage_forcelink(); - zen::memory_forcelink(); } diff --git a/zencore/zencore.vcxproj b/zencore/zencore.vcxproj index c9d51e0bb..f761e1769 100644 --- a/zencore/zencore.vcxproj +++ b/zencore/zencore.vcxproj @@ -112,6 +112,8 @@ + + @@ -150,6 +152,7 @@ + diff --git a/zencore/zencore.vcxproj.filters b/zencore/zencore.vcxproj.filters index c25f99e77..0dd32424b 100644 --- a/zencore/zencore.vcxproj.filters +++ b/zencore/zencore.vcxproj.filters @@ -38,6 +38,8 @@ + + @@ -69,6 +71,7 @@ + -- cgit v1.2.3