str/buf: Add allocation reducing string buffer
Enables constructing strings with minimal allocations, and follows best
practices of using stack optimized for storing smaller string buffers.
Change-Id: If3b9e0d9e14147aadf282fe5ddeea8f7f9ef5837
Signed-off-by: William A. Kennington III <wak@google.com>
diff --git a/include/meson.build b/include/meson.build
index d7cf82b..5909aa0 100644
--- a/include/meson.build
+++ b/include/meson.build
@@ -16,6 +16,7 @@
'stdplus/pinned.hpp',
'stdplus/raw.hpp',
'stdplus/signal.hpp',
+ 'stdplus/str/buf.hpp',
'stdplus/str/cat.hpp',
'stdplus/str/cexpr.hpp',
'stdplus/str/maps.hpp',
diff --git a/include/stdplus/str/buf.hpp b/include/stdplus/str/buf.hpp
new file mode 100644
index 0000000..834f154
--- /dev/null
+++ b/include/stdplus/str/buf.hpp
@@ -0,0 +1,398 @@
+#pragma once
+#include <cstdint>
+#include <limits>
+#include <memory>
+#include <string_view>
+
+namespace stdplus
+{
+
+namespace detail
+{
+
+template <typename CharT, std::size_t BufLen, auto Endian = std::endian::native>
+union StrBufStore;
+
+template <typename CharT, std::size_t BufLen>
+union StrBufStore<CharT, BufLen, std::endian::little>
+{
+ struct Inl
+ {
+ CharT ptr[BufLen];
+ std::make_unsigned_t<CharT> len;
+ static_assert(BufLen <= std::numeric_limits<decltype(len)>::max() / 2);
+ } inl;
+ struct Dyn
+ {
+ std::uint8_t
+ rsvd[offsetof(Inl, len) - sizeof(CharT*) - sizeof(std::size_t) * 2];
+ CharT* ptr;
+ std::size_t cap;
+ std::size_t len;
+ } dyn;
+ static_assert(offsetof(Inl, len) + sizeof(Inl::len) ==
+ offsetof(Dyn, len) + sizeof(Dyn::len));
+};
+
+template <typename CharT, std::size_t BufLen>
+union StrBufStore<CharT, BufLen, std::endian::big>
+{
+ struct Inl
+ {
+ std::make_unsigned_t<CharT> len;
+ CharT ptr[BufLen];
+ static_assert(BufLen <= std::numeric_limits<decltype(len)>::max() / 2);
+ } inl;
+ struct Dyn
+ {
+ std::size_t len;
+ std::size_t cap;
+ CharT* ptr;
+ } dyn;
+};
+
+template <typename CharT, std::size_t ObjSize, typename Allocator>
+struct StrBufAS : Allocator
+{
+ static inline constexpr std::size_t buf_len =
+ (ObjSize -
+ sizeof(std::declval<detail::StrBufStore<CharT, 63>>().inl.len) -
+ (std::is_empty_v<Allocator> ? 0 : sizeof(Allocator))) /
+ sizeof(CharT);
+ using Store = detail::StrBufStore<CharT, buf_len>;
+ static_assert(sizeof(std::declval<Store>().inl) >=
+ sizeof(std::declval<Store>().dyn));
+
+ static inline constexpr auto dyn_mask = std::size_t{1}
+ << ((sizeof(std::size_t) << 3) - 1);
+ static inline constexpr auto inl_mask =
+ decltype(Store::Inl::len){1} << ((sizeof(Store::Inl::len) << 3) - 1);
+
+ Store store;
+
+ constexpr bool isDyn() const noexcept
+ {
+ if (std::is_constant_evaluated())
+ {
+ return true;
+ }
+ return store.inl.len & inl_mask;
+ }
+
+ constexpr std::size_t dynLen() const noexcept
+ {
+ return store.dyn.len & ~dyn_mask;
+ }
+
+ constexpr void dynLen(std::size_t len) noexcept
+ {
+ store.dyn.len = len | dyn_mask;
+ }
+
+ constexpr auto inlLen() const noexcept
+ {
+ return store.inl.len;
+ }
+
+ constexpr void inlLen(decltype(Store::Inl::len) len) noexcept
+ {
+ store.inl.len = len;
+ }
+
+ constexpr CharT* allocate(std::size_t n)
+ {
+ auto ptr = static_cast<Allocator&>(*this).allocate(n);
+ if (std::is_constant_evaluated())
+ {
+ for (std::size_t i = 0; i < n; ++i)
+ {
+ std::construct_at(ptr + i);
+ }
+ }
+ return ptr;
+ }
+
+ constexpr void zeroInit() noexcept
+ {
+ if (std::is_constant_evaluated())
+ {
+ store.dyn.ptr = allocate(buf_len);
+ store.dyn.cap = buf_len;
+ dynLen(0);
+ }
+ else
+ {
+ inlLen(0);
+ }
+ }
+
+ constexpr StrBufAS(Allocator&& a) noexcept : Allocator(std::move(a))
+ {
+ if (std::is_constant_evaluated())
+ {
+ std::construct_at(&store.dyn);
+ }
+ zeroInit();
+ }
+
+ constexpr StrBufAS& operator=(Allocator&& a) noexcept
+ {
+ *static_cast<Allocator*>(this) = a;
+ return *this;
+ }
+};
+
+} // namespace detail
+
+template <typename CharT, std::size_t ObjSize = 128,
+ typename Allocator = std::allocator<CharT>>
+class BasicStrBuf
+{
+ private:
+ detail::StrBufAS<CharT, ObjSize, Allocator> as;
+
+ template <bool assign>
+ constexpr void inlcopy(const BasicStrBuf& other) noexcept
+ {
+ const auto optr = other.as.store.inl.ptr;
+ const auto olen = other.as.inlLen();
+ if (assign || std::is_constant_evaluated())
+ {
+ if (as.isDyn())
+ {
+ as.dynLen(olen);
+ std::copy(optr, optr + olen, as.store.dyn.ptr);
+ return;
+ }
+ }
+ as.store.inl.len = other.as.store.inl.len;
+ std::copy(optr, optr + olen, as.store.inl.ptr);
+ }
+
+ template <bool assign>
+ constexpr void move(BasicStrBuf&& other) noexcept
+ {
+ if (!other.as.isDyn())
+ {
+ inlcopy<assign>(other);
+ other.as.zeroInit();
+ return;
+ }
+ if (assign || std::is_constant_evaluated())
+ {
+ if (as.isDyn())
+ {
+ as.deallocate(as.store.dyn.ptr, as.store.dyn.cap);
+ }
+ }
+ as.store.dyn = other.as.store.dyn;
+ other.as.zeroInit();
+ }
+
+ template <bool assign>
+ constexpr void copy(const BasicStrBuf& other)
+ {
+ if (!other.as.isDyn())
+ {
+ inlcopy<assign>(other);
+ return;
+ }
+ const auto optr = other.as.store.dyn.ptr;
+ const std::size_t olen = other.as.dynLen();
+ if (assign || std::is_constant_evaluated())
+ {
+ if (as.isDyn())
+ {
+ if (olen <= as.store.dyn.cap)
+ {
+ as.store.dyn.len = other.as.store.dyn.len;
+ std::copy(optr, optr + olen, as.store.dyn.ptr);
+ return;
+ }
+ else
+ {
+ as.deallocate(as.store.dyn.ptr, as.store.dyn.cap);
+ }
+ }
+ }
+ if (olen <= as.buf_len)
+ {
+ std::copy(optr, optr + olen, as.store.inl.ptr);
+ as.inlLen(olen);
+ return;
+ }
+ as.store.dyn.cap = other.as.store.dyn.cap;
+ as.store.dyn.ptr = as.allocate(as.store.dyn.cap);
+ as.store.dyn.len = other.as.store.dyn.len;
+ std::copy(optr, optr + olen, as.store.dyn.ptr);
+ }
+
+ public:
+ using value_type = CharT;
+
+ constexpr BasicStrBuf() noexcept : as({}) {}
+
+ constexpr BasicStrBuf(BasicStrBuf&& other) noexcept :
+ as(static_cast<Allocator&&>(other.as))
+ {
+ move</*assign=*/false>(std::move(other));
+ }
+
+ constexpr BasicStrBuf(const BasicStrBuf& other) :
+ as(std::allocator_traits<Allocator>::
+ select_on_container_copy_construction(
+ static_cast<const Allocator&>(other.as)))
+ {
+ copy</*assign=*/false>(other);
+ }
+
+ constexpr BasicStrBuf& operator=(BasicStrBuf&& other) noexcept
+ {
+ if (this != &other)
+ {
+ if constexpr (typename std::allocator_traits<Allocator>::
+ propagate_on_container_move_assignment())
+ {
+ as = static_cast<Allocator&&>(other.as);
+ }
+ move</*assign=*/true>(std::move(other));
+ }
+ return *this;
+ }
+
+ constexpr BasicStrBuf& operator=(const BasicStrBuf& other)
+ {
+ if (this != &other)
+ {
+ if constexpr (typename std::allocator_traits<Allocator>::
+ propagate_on_container_copy_assignment())
+ {
+ as = static_cast<const Allocator&>(other.as);
+ }
+ copy</*assign=*/true>(other);
+ }
+ return *this;
+ }
+
+ constexpr ~BasicStrBuf()
+ {
+ if (as.isDyn())
+ {
+ as.deallocate(as.store.dyn.ptr, as.store.dyn.cap);
+ }
+ }
+
+ constexpr std::size_t size() const noexcept
+ {
+ return as.isDyn() ? as.dynLen() : as.inlLen();
+ }
+
+ constexpr operator std::basic_string_view<CharT>() const noexcept
+ {
+ return std::basic_string_view<CharT>(begin(), size());
+ }
+
+ constexpr CharT* append(std::size_t amt)
+ {
+ if (!as.isDyn())
+ {
+ const std::size_t oldlen = as.inlLen();
+ const std::size_t newlen = oldlen + amt;
+ if (newlen <= as.buf_len)
+ {
+ as.inlLen(newlen);
+ return as.store.inl.ptr + oldlen;
+ }
+ const std::size_t newcap = newlen + (newlen >> 1);
+ const auto ptr = as.allocate(newcap);
+ std::copy(as.store.inl.ptr, as.store.inl.ptr + oldlen, ptr);
+
+ as.store.dyn.ptr = ptr;
+ as.store.dyn.cap = newcap;
+ as.dynLen(newlen);
+ return ptr + oldlen;
+ }
+ const std::size_t oldlen = as.dynLen();
+ const std::size_t newlen = oldlen + amt;
+ if (newlen > as.store.dyn.cap)
+ {
+ const std::size_t newcap = newlen + (newlen >> 1);
+ const auto ptr = as.allocate(newcap);
+ std::copy(as.store.dyn.ptr, as.store.dyn.ptr + oldlen, ptr);
+ as.deallocate(as.store.dyn.ptr, as.store.dyn.cap);
+
+ as.store.dyn.ptr = ptr;
+ as.store.dyn.cap = newcap;
+ }
+ as.dynLen(newlen);
+ return as.store.dyn.ptr + oldlen;
+ }
+
+ constexpr void shrink(std::size_t amt) noexcept
+ {
+ if (as.isDyn())
+ {
+ as.store.dyn.len -= amt;
+ }
+ else
+ {
+ as.store.inl.len -= amt;
+ }
+ }
+
+ constexpr void reset() noexcept
+ {
+ if (as.isDyn())
+ {
+ as.dynLen(0);
+ }
+ else
+ {
+ as.inlLen(0);
+ }
+ }
+
+ constexpr CharT* begin() noexcept
+ {
+ return as.isDyn() ? as.store.dyn.ptr : as.store.inl.ptr;
+ }
+
+ constexpr const CharT* begin() const noexcept
+ {
+ return as.isDyn() ? as.store.dyn.ptr : as.store.inl.ptr;
+ }
+
+ constexpr CharT* end() noexcept
+ {
+ return begin() + size();
+ }
+
+ constexpr const CharT* end() const noexcept
+ {
+ return begin() + size();
+ }
+
+ constexpr const CharT* cbegin() const noexcept
+ {
+ return begin();
+ }
+
+ constexpr const CharT* cend() const noexcept
+ {
+ return end();
+ }
+
+ constexpr bool
+ operator==(std::basic_string_view<CharT> other) const noexcept
+ {
+ return std::basic_string_view<CharT>{*this} == other;
+ }
+};
+
+static_assert(sizeof(BasicStrBuf<char, 128>) == 128);
+static_assert(sizeof(BasicStrBuf<wchar_t, 256>) == 256);
+
+using StrBuf = BasicStrBuf<char>;
+using WStrBuf = BasicStrBuf<wchar_t>;
+
+} // namespace stdplus
diff --git a/src/meson.build b/src/meson.build
index 47fcd33..a064f14 100644
--- a/src/meson.build
+++ b/src/meson.build
@@ -57,6 +57,7 @@
'pinned.cpp',
'raw.cpp',
'signal.cpp',
+ 'str/buf.cpp',
'str/cat.cpp',
'str/cexpr.cpp',
'str/maps.cpp',
diff --git a/src/str/buf.cpp b/src/str/buf.cpp
new file mode 100644
index 0000000..b0eb177
--- /dev/null
+++ b/src/str/buf.cpp
@@ -0,0 +1,9 @@
+#include <stdplus/str/buf.hpp>
+
+namespace stdplus
+{
+
+template class BasicStrBuf<char>;
+template class BasicStrBuf<wchar_t>;
+
+} // namespace stdplus
diff --git a/test/meson.build b/test/meson.build
index 8403e0f..a92e411 100644
--- a/test/meson.build
+++ b/test/meson.build
@@ -13,6 +13,7 @@
'pinned': [stdplus_dep, gtest_main_dep],
'raw': [stdplus_dep, gmock_dep, gtest_main_dep],
'signal': [stdplus_dep, gtest_main_dep],
+ 'str/buf': [stdplus_dep, gtest_main_dep],
'str/cat': [stdplus_dep, gtest_main_dep],
'str/cexpr': [stdplus_dep, gtest_main_dep],
'str/maps': [stdplus_dep, gmock_dep, gtest_main_dep],
diff --git a/test/str/buf.cpp b/test/str/buf.cpp
new file mode 100644
index 0000000..dc94e2c
--- /dev/null
+++ b/test/str/buf.cpp
@@ -0,0 +1,183 @@
+#include <stdplus/str/buf.hpp>
+#include <stdplus/str/cexpr.hpp>
+
+#include <gtest/gtest.h>
+
+namespace stdplus
+{
+
+static constexpr auto makeIncStr(std::size_t len)
+{
+ stdplus::StrBuf ret;
+ auto ptr = ret.append(len);
+ for (std::size_t i = 0; i < len; i++)
+ {
+ ptr[i] = 'A' + (i % 26);
+ }
+ return ret;
+}
+
+constexpr auto data = cexprSv<[]() { return makeIncStr(sizeof(StrBuf) + 10); }>;
+// constexpr auto data = cexprSv<[]() { return makeIncStr(32); }>;
+
+TEST(StrBuf, BasicInline)
+{
+ StrBuf buf;
+ EXPECT_EQ(buf.size(), 0);
+ auto old_ptr = buf.begin();
+
+ // Ensure that we inline small amounts of data only
+ std::copy(data.begin(), data.begin() + 4, buf.append(4));
+ EXPECT_EQ(buf.begin(), old_ptr);
+ EXPECT_EQ(buf.size(), 4);
+ EXPECT_EQ(std::string_view(data).substr(0, 4), buf);
+
+ // Ensure that the max data size inline doesn't dynamically allocate
+ constexpr std::size_t max_size = sizeof(StrBuf) - sizeof(std::size_t);
+ buf.append(max_size - 4);
+ EXPECT_EQ(buf.begin(), old_ptr);
+ EXPECT_EQ(buf.size(), max_size);
+}
+
+TEST(StrBuf, DynamicAppend)
+{
+ constexpr std::size_t seg = 15;
+
+ StrBuf buf;
+ auto old_ptr = buf.begin();
+ std::copy(data.begin(), data.begin() + seg, buf.append(seg));
+
+ // Ensure that inline -> dynamic is working
+ std::copy(data.begin() + seg, data.end(), buf.append(data.size() - seg));
+ EXPECT_NE(buf.begin(), old_ptr);
+ EXPECT_EQ(data, buf);
+ EXPECT_EQ(data.size(), buf.size());
+
+ // Ensure dynamic allocation is large enough to allow additional
+ // small appends with no reallocation
+ old_ptr = buf.begin();
+ std::copy(data.begin(), data.begin() + seg, buf.append(seg));
+ EXPECT_EQ(buf.begin(), old_ptr);
+ EXPECT_EQ(data.size() + seg, buf.size());
+ EXPECT_EQ(data.substr(0, seg), std::string_view{buf}.substr(data.size()));
+
+ // Ensure new dynamic allocations copy
+ std::copy(data.begin() + seg, data.end(), buf.append(data.size() - seg));
+ EXPECT_NE(buf.begin(), old_ptr);
+ EXPECT_EQ(data.size() << 1, buf.size());
+ EXPECT_EQ(data, std::string_view{buf}.substr(0, data.size()));
+ EXPECT_EQ(data, std::string_view{buf}.substr(data.size()));
+}
+
+TEST(StrBuf, CopiesInline)
+{
+ StrBuf buf1;
+ buf1.append(1)[0] = 'a';
+ StrBuf buf2 = buf1;
+ EXPECT_EQ(buf1, buf2);
+ buf1.append(1)[0] = 'b';
+ StrBuf buf3 = buf1;
+ EXPECT_EQ("ab", buf3);
+ EXPECT_EQ("ab", buf1);
+ EXPECT_EQ("a", buf2);
+ buf3 = buf2;
+ EXPECT_EQ("a", buf3);
+ EXPECT_EQ("ab", buf1);
+ EXPECT_EQ("a", buf2);
+}
+
+TEST(StrBuf, MoveInline)
+{
+ StrBuf buf1;
+ buf1.append(1)[0] = 'a';
+ StrBuf buf2 = std::move(buf1);
+ EXPECT_EQ("a", std::string_view{buf2});
+ buf2.append(1)[0] = 'b';
+ // NOLINTNEXTLINE(clang-analyzer-cplusplus.Move)
+ EXPECT_EQ(0, buf1.size());
+ StrBuf buf3 = buf1;
+ EXPECT_EQ(0, buf3.size());
+ buf3 = std::move(buf2);
+ // NOLINTNEXTLINE(clang-analyzer-cplusplus.Move)
+ EXPECT_EQ(0, buf2.size());
+ EXPECT_EQ("ab", std::string_view{buf3});
+}
+
+TEST(StrBuf, CopyInlToDyn)
+{
+ StrBuf buf1;
+ buf1.append(1)[0] = 'a';
+ StrBuf buf2;
+ buf2.append(sizeof(StrBuf) + 10);
+ buf2 = buf1;
+ EXPECT_EQ("a", buf2);
+}
+
+TEST(StrBuf, MoveInlToDyn)
+{
+ StrBuf buf1;
+ buf1.append(1)[0] = 'a';
+ StrBuf buf2;
+ buf2.append(sizeof(StrBuf) + 10);
+ // NOLINTNEXTLINE(clang-analyzer-cplusplus.Move)
+ buf2 = std::move(buf1);
+ EXPECT_EQ("", buf1);
+ EXPECT_EQ("a", buf2);
+}
+
+TEST(StrBuf, MoveDynToInl)
+{
+ StrBuf buf1;
+ std::copy(data.begin(), data.end(), buf1.append(data.size()));
+ StrBuf buf2;
+ buf2.append(1)[0] = 'a';
+ // NOLINTNEXTLINE(clang-analyzer-cplusplus.Move)
+ buf2 = std::move(buf1);
+ EXPECT_EQ("", buf1);
+ EXPECT_EQ(data, buf2);
+}
+
+TEST(StrBuf, MoveDynToDyn)
+{
+ StrBuf buf1;
+ std::copy(data.begin(), data.end(), buf1.append(data.size()));
+ StrBuf buf2;
+ buf2.append(data.size());
+ // NOLINTNEXTLINE(clang-analyzer-cplusplus.Move)
+ buf2 = std::move(buf1);
+ EXPECT_EQ("", buf1);
+ EXPECT_EQ(data, buf2);
+}
+
+TEST(StrBuf, CopyDynToInl)
+{
+ StrBuf buf1;
+ buf1.append(data.size());
+ buf1.reset();
+ buf1.append(1)[0] = 'a';
+ StrBuf buf2 = buf1;
+ StrBuf buf3;
+ buf3.append(1)[0] = 'b';
+ buf3 = buf1;
+ EXPECT_EQ("a", buf1);
+ EXPECT_EQ("a", buf2);
+ EXPECT_EQ("a", buf3);
+}
+
+TEST(StrBuf, CopyDynToDyn)
+{
+ StrBuf buf1;
+ std::copy(data.begin(), data.end(), buf1.append(data.size()));
+ std::copy(data.begin(), data.end(), buf1.append(data.size()));
+ StrBuf buf2 = buf1;
+ StrBuf buf3;
+ std::copy(data.begin(), data.end(), buf3.append(data.size()));
+ buf3 = buf1;
+ EXPECT_EQ(buf2, buf1);
+ EXPECT_EQ(buf3, buf1);
+ buf3.append(1)[0] = 'a';
+ buf1 = buf3;
+ EXPECT_EQ(buf3, buf1);
+}
+
+} // namespace stdplus