aboutsummaryrefslogtreecommitdiffstats
path: root/library/cpp/actors/util
diff options
context:
space:
mode:
authorAlexander Rutkovsky <alexvru@mail.ru>2022-02-10 16:47:40 +0300
committerDaniil Cherednik <dcherednik@yandex-team.ru>2022-02-10 16:47:40 +0300
commit667a4ee7da2e004784b9c3cfab824a81e96f4d66 (patch)
treec0748b5dcbade83af788c0abfa89c0383d6b779c /library/cpp/actors/util
parentf3646f91e0de459836a7800b9ce3e8dc57a2ab3a (diff)
downloadydb-667a4ee7da2e004784b9c3cfab824a81e96f4d66.tar.gz
Restoring authorship annotation for Alexander Rutkovsky <alexvru@mail.ru>. Commit 2 of 2.
Diffstat (limited to 'library/cpp/actors/util')
-rw-r--r--library/cpp/actors/util/named_tuple.h46
-rw-r--r--library/cpp/actors/util/rope.h2000
-rw-r--r--library/cpp/actors/util/rope_cont_deque.h362
-rw-r--r--library/cpp/actors/util/rope_cont_list.h318
-rw-r--r--library/cpp/actors/util/rope_ut.cpp460
-rw-r--r--library/cpp/actors/util/ut/ya.make14
-rw-r--r--library/cpp/actors/util/ya.make6
7 files changed, 1603 insertions, 1603 deletions
diff --git a/library/cpp/actors/util/named_tuple.h b/library/cpp/actors/util/named_tuple.h
index bd8e7c44b2..67f185bba8 100644
--- a/library/cpp/actors/util/named_tuple.h
+++ b/library/cpp/actors/util/named_tuple.h
@@ -1,30 +1,30 @@
-#pragma once
-
-#include "defs.h"
-
+#pragma once
+
+#include "defs.h"
+
template <typename TDerived>
-struct TNamedTupleBase {
+struct TNamedTupleBase {
friend bool operator==(const TDerived& x, const TDerived& y) {
- return x.ConvertToTuple() == y.ConvertToTuple();
- }
-
+ return x.ConvertToTuple() == y.ConvertToTuple();
+ }
+
friend bool operator!=(const TDerived& x, const TDerived& y) {
- return x.ConvertToTuple() != y.ConvertToTuple();
- }
-
+ return x.ConvertToTuple() != y.ConvertToTuple();
+ }
+
friend bool operator<(const TDerived& x, const TDerived& y) {
- return x.ConvertToTuple() < y.ConvertToTuple();
- }
-
+ return x.ConvertToTuple() < y.ConvertToTuple();
+ }
+
friend bool operator<=(const TDerived& x, const TDerived& y) {
- return x.ConvertToTuple() <= y.ConvertToTuple();
- }
-
+ return x.ConvertToTuple() <= y.ConvertToTuple();
+ }
+
friend bool operator>(const TDerived& x, const TDerived& y) {
- return x.ConvertToTuple() > y.ConvertToTuple();
- }
-
+ return x.ConvertToTuple() > y.ConvertToTuple();
+ }
+
friend bool operator>=(const TDerived& x, const TDerived& y) {
- return x.ConvertToTuple() >= y.ConvertToTuple();
- }
-};
+ return x.ConvertToTuple() >= y.ConvertToTuple();
+ }
+};
diff --git a/library/cpp/actors/util/rope.h b/library/cpp/actors/util/rope.h
index 9d3c3896c8..f5595efbaa 100644
--- a/library/cpp/actors/util/rope.h
+++ b/library/cpp/actors/util/rope.h
@@ -1,998 +1,998 @@
-#pragma once
-
-#include <util/generic/ptr.h>
-#include <util/generic/string.h>
-#include <util/generic/hash_set.h>
-#include <util/stream/str.h>
+#pragma once
+
+#include <util/generic/ptr.h>
+#include <util/generic/string.h>
+#include <util/generic/hash_set.h>
+#include <util/stream/str.h>
#include <util/system/sanitizers.h>
#include <util/system/valgrind.h>
-
-// exactly one of them must be included
-#include "rope_cont_list.h"
-//#include "rope_cont_deque.h"
-
-struct IRopeChunkBackend : TThrRefBase {
- using TData = std::tuple<const char*, size_t>;
- virtual ~IRopeChunkBackend() = default;
- virtual TData GetData() const = 0;
- virtual size_t GetCapacity() const = 0;
- using TPtr = TIntrusivePtr<IRopeChunkBackend>;
-};
-
-class TRopeAlignedBuffer : public IRopeChunkBackend {
- static constexpr size_t Alignment = 16;
- static constexpr size_t MallocAlignment = sizeof(size_t);
-
- ui32 Size;
- const ui32 Capacity;
- const ui32 Offset;
- alignas(Alignment) char Data[];
-
- TRopeAlignedBuffer(size_t size)
- : Size(size)
- , Capacity(size)
- , Offset((Alignment - reinterpret_cast<uintptr_t>(Data)) & (Alignment - 1))
- {
- Y_VERIFY(Offset <= Alignment - MallocAlignment);
- }
-
-public:
- static TIntrusivePtr<TRopeAlignedBuffer> Allocate(size_t size) {
- return new(malloc(sizeof(TRopeAlignedBuffer) + size + Alignment - MallocAlignment)) TRopeAlignedBuffer(size);
- }
-
- void *operator new(size_t) {
- Y_FAIL();
- }
-
- void *operator new(size_t, void *ptr) {
- return ptr;
- }
-
- void operator delete(void *ptr) {
- free(ptr);
- }
-
+
+// exactly one of them must be included
+#include "rope_cont_list.h"
+//#include "rope_cont_deque.h"
+
+struct IRopeChunkBackend : TThrRefBase {
+ using TData = std::tuple<const char*, size_t>;
+ virtual ~IRopeChunkBackend() = default;
+ virtual TData GetData() const = 0;
+ virtual size_t GetCapacity() const = 0;
+ using TPtr = TIntrusivePtr<IRopeChunkBackend>;
+};
+
+class TRopeAlignedBuffer : public IRopeChunkBackend {
+ static constexpr size_t Alignment = 16;
+ static constexpr size_t MallocAlignment = sizeof(size_t);
+
+ ui32 Size;
+ const ui32 Capacity;
+ const ui32 Offset;
+ alignas(Alignment) char Data[];
+
+ TRopeAlignedBuffer(size_t size)
+ : Size(size)
+ , Capacity(size)
+ , Offset((Alignment - reinterpret_cast<uintptr_t>(Data)) & (Alignment - 1))
+ {
+ Y_VERIFY(Offset <= Alignment - MallocAlignment);
+ }
+
+public:
+ static TIntrusivePtr<TRopeAlignedBuffer> Allocate(size_t size) {
+ return new(malloc(sizeof(TRopeAlignedBuffer) + size + Alignment - MallocAlignment)) TRopeAlignedBuffer(size);
+ }
+
+ void *operator new(size_t) {
+ Y_FAIL();
+ }
+
+ void *operator new(size_t, void *ptr) {
+ return ptr;
+ }
+
+ void operator delete(void *ptr) {
+ free(ptr);
+ }
+
void operator delete(void* p, void* ptr) {
Y_UNUSED(p);
Y_UNUSED(ptr);
}
- TData GetData() const override {
- return {Data + Offset, Size};
- }
-
- size_t GetCapacity() const override {
- return Capacity;
- }
-
- char *GetBuffer() {
- return Data + Offset;
- }
-
- void AdjustSize(size_t size) {
- Y_VERIFY(size <= Capacity);
- Size = size;
- }
-};
-
-namespace NRopeDetails {
-
- template<bool IsConst, typename TRope, typename TList>
- struct TIteratorTraits;
-
- template<typename TRope, typename TList>
- struct TIteratorTraits<true, TRope, TList> {
- using TRopePtr = const TRope*;
- using TListIterator = typename TList::const_iterator;
- };
-
- template<typename TRope, typename TList>
- struct TIteratorTraits<false, TRope, TList> {
- using TRopePtr = TRope*;
- using TListIterator = typename TList::iterator;
- };
-
-} // NRopeDetails
-
-class TRopeArena;
-
-template<typename T>
-struct always_false : std::false_type {};
-
-class TRope {
- friend class TRopeArena;
-
- struct TChunk
- {
- class TBackend {
- enum class EType : uintptr_t {
- STRING,
- ROPE_CHUNK_BACKEND,
- };
-
- uintptr_t Owner = 0; // lower bits contain type of the owner
-
- public:
- TBackend() = delete;
-
- TBackend(const TBackend& other)
- : Owner(Clone(other.Owner))
- {}
-
- TBackend(TBackend&& other)
- : Owner(std::exchange(other.Owner, 0))
- {}
-
- TBackend(TString s)
- : Owner(Construct<TString>(EType::STRING, std::move(s)))
- {}
-
- TBackend(IRopeChunkBackend::TPtr backend)
- : Owner(Construct<IRopeChunkBackend::TPtr>(EType::ROPE_CHUNK_BACKEND, std::move(backend)))
- {}
-
- ~TBackend() {
- if (Owner) {
- Destroy(Owner);
- }
- }
-
- TBackend& operator =(const TBackend& other) {
- if (Owner) {
- Destroy(Owner);
- }
- Owner = Clone(other.Owner);
- return *this;
- }
-
- TBackend& operator =(TBackend&& other) {
- if (Owner) {
- Destroy(Owner);
- }
- Owner = std::exchange(other.Owner, 0);
- return *this;
- }
-
- bool operator ==(const TBackend& other) const {
- return Owner == other.Owner;
- }
-
- const void *UniqueId() const {
- return reinterpret_cast<const void*>(Owner);
- }
-
- const IRopeChunkBackend::TData GetData() const {
- return Visit(Owner, [](EType, auto& value) -> IRopeChunkBackend::TData {
- using T = std::decay_t<decltype(value)>;
- if constexpr (std::is_same_v<T, TString>) {
- return {value.data(), value.size()};
- } else if constexpr (std::is_same_v<T, IRopeChunkBackend::TPtr>) {
- return value->GetData();
- } else {
- return {};
- }
- });
- }
-
- size_t GetCapacity() const {
- return Visit(Owner, [](EType, auto& value) {
- using T = std::decay_t<decltype(value)>;
- if constexpr (std::is_same_v<T, TString>) {
- return value.capacity();
- } else if constexpr (std::is_same_v<T, IRopeChunkBackend::TPtr>) {
- return value->GetCapacity();
- } else {
- Y_FAIL();
- }
- });
- }
-
- private:
- static constexpr uintptr_t TypeMask = (1 << 3) - 1;
- static constexpr uintptr_t ValueMask = ~TypeMask;
-
- template<typename T>
- struct TObjectHolder {
- struct TWrappedObject : TThrRefBase {
- T Value;
- TWrappedObject(T&& value)
- : Value(std::move(value))
- {}
- };
- TIntrusivePtr<TWrappedObject> Object;
-
- TObjectHolder(T&& object)
- : Object(MakeIntrusive<TWrappedObject>(std::move(object)))
- {}
- };
-
- template<typename TObject>
- static uintptr_t Construct(EType type, TObject object) {
- if constexpr (sizeof(TObject) <= sizeof(uintptr_t)) {
- uintptr_t res = 0;
- new(&res) TObject(std::move(object));
- Y_VERIFY_DEBUG((res & ValueMask) == res);
- return res | static_cast<uintptr_t>(type);
- } else {
- return Construct<TObjectHolder<TObject>>(type, TObjectHolder<TObject>(std::move(object)));
- }
- }
-
- template<typename TCallback>
- static std::invoke_result_t<TCallback, EType, TString&> VisitRaw(uintptr_t value, TCallback&& callback) {
- Y_VERIFY_DEBUG(value);
- const EType type = static_cast<EType>(value & TypeMask);
- value &= ValueMask;
- auto caller = [&](auto& value) { return std::invoke(std::forward<TCallback>(callback), type, value); };
- auto wrapper = [&](auto& value) {
- using T = std::decay_t<decltype(value)>;
- if constexpr (sizeof(T) <= sizeof(uintptr_t)) {
- return caller(value);
- } else {
- return caller(reinterpret_cast<TObjectHolder<T>&>(value));
- }
- };
- switch (type) {
- case EType::STRING: return wrapper(reinterpret_cast<TString&>(value));
- case EType::ROPE_CHUNK_BACKEND: return wrapper(reinterpret_cast<IRopeChunkBackend::TPtr&>(value));
- }
+ TData GetData() const override {
+ return {Data + Offset, Size};
+ }
+
+ size_t GetCapacity() const override {
+ return Capacity;
+ }
+
+ char *GetBuffer() {
+ return Data + Offset;
+ }
+
+ void AdjustSize(size_t size) {
+ Y_VERIFY(size <= Capacity);
+ Size = size;
+ }
+};
+
+namespace NRopeDetails {
+
+ template<bool IsConst, typename TRope, typename TList>
+ struct TIteratorTraits;
+
+ template<typename TRope, typename TList>
+ struct TIteratorTraits<true, TRope, TList> {
+ using TRopePtr = const TRope*;
+ using TListIterator = typename TList::const_iterator;
+ };
+
+ template<typename TRope, typename TList>
+ struct TIteratorTraits<false, TRope, TList> {
+ using TRopePtr = TRope*;
+ using TListIterator = typename TList::iterator;
+ };
+
+} // NRopeDetails
+
+class TRopeArena;
+
+template<typename T>
+struct always_false : std::false_type {};
+
+class TRope {
+ friend class TRopeArena;
+
+ struct TChunk
+ {
+ class TBackend {
+ enum class EType : uintptr_t {
+ STRING,
+ ROPE_CHUNK_BACKEND,
+ };
+
+ uintptr_t Owner = 0; // lower bits contain type of the owner
+
+ public:
+ TBackend() = delete;
+
+ TBackend(const TBackend& other)
+ : Owner(Clone(other.Owner))
+ {}
+
+ TBackend(TBackend&& other)
+ : Owner(std::exchange(other.Owner, 0))
+ {}
+
+ TBackend(TString s)
+ : Owner(Construct<TString>(EType::STRING, std::move(s)))
+ {}
+
+ TBackend(IRopeChunkBackend::TPtr backend)
+ : Owner(Construct<IRopeChunkBackend::TPtr>(EType::ROPE_CHUNK_BACKEND, std::move(backend)))
+ {}
+
+ ~TBackend() {
+ if (Owner) {
+ Destroy(Owner);
+ }
+ }
+
+ TBackend& operator =(const TBackend& other) {
+ if (Owner) {
+ Destroy(Owner);
+ }
+ Owner = Clone(other.Owner);
+ return *this;
+ }
+
+ TBackend& operator =(TBackend&& other) {
+ if (Owner) {
+ Destroy(Owner);
+ }
+ Owner = std::exchange(other.Owner, 0);
+ return *this;
+ }
+
+ bool operator ==(const TBackend& other) const {
+ return Owner == other.Owner;
+ }
+
+ const void *UniqueId() const {
+ return reinterpret_cast<const void*>(Owner);
+ }
+
+ const IRopeChunkBackend::TData GetData() const {
+ return Visit(Owner, [](EType, auto& value) -> IRopeChunkBackend::TData {
+ using T = std::decay_t<decltype(value)>;
+ if constexpr (std::is_same_v<T, TString>) {
+ return {value.data(), value.size()};
+ } else if constexpr (std::is_same_v<T, IRopeChunkBackend::TPtr>) {
+ return value->GetData();
+ } else {
+ return {};
+ }
+ });
+ }
+
+ size_t GetCapacity() const {
+ return Visit(Owner, [](EType, auto& value) {
+ using T = std::decay_t<decltype(value)>;
+ if constexpr (std::is_same_v<T, TString>) {
+ return value.capacity();
+ } else if constexpr (std::is_same_v<T, IRopeChunkBackend::TPtr>) {
+ return value->GetCapacity();
+ } else {
+ Y_FAIL();
+ }
+ });
+ }
+
+ private:
+ static constexpr uintptr_t TypeMask = (1 << 3) - 1;
+ static constexpr uintptr_t ValueMask = ~TypeMask;
+
+ template<typename T>
+ struct TObjectHolder {
+ struct TWrappedObject : TThrRefBase {
+ T Value;
+ TWrappedObject(T&& value)
+ : Value(std::move(value))
+ {}
+ };
+ TIntrusivePtr<TWrappedObject> Object;
+
+ TObjectHolder(T&& object)
+ : Object(MakeIntrusive<TWrappedObject>(std::move(object)))
+ {}
+ };
+
+ template<typename TObject>
+ static uintptr_t Construct(EType type, TObject object) {
+ if constexpr (sizeof(TObject) <= sizeof(uintptr_t)) {
+ uintptr_t res = 0;
+ new(&res) TObject(std::move(object));
+ Y_VERIFY_DEBUG((res & ValueMask) == res);
+ return res | static_cast<uintptr_t>(type);
+ } else {
+ return Construct<TObjectHolder<TObject>>(type, TObjectHolder<TObject>(std::move(object)));
+ }
+ }
+
+ template<typename TCallback>
+ static std::invoke_result_t<TCallback, EType, TString&> VisitRaw(uintptr_t value, TCallback&& callback) {
+ Y_VERIFY_DEBUG(value);
+ const EType type = static_cast<EType>(value & TypeMask);
+ value &= ValueMask;
+ auto caller = [&](auto& value) { return std::invoke(std::forward<TCallback>(callback), type, value); };
+ auto wrapper = [&](auto& value) {
+ using T = std::decay_t<decltype(value)>;
+ if constexpr (sizeof(T) <= sizeof(uintptr_t)) {
+ return caller(value);
+ } else {
+ return caller(reinterpret_cast<TObjectHolder<T>&>(value));
+ }
+ };
+ switch (type) {
+ case EType::STRING: return wrapper(reinterpret_cast<TString&>(value));
+ case EType::ROPE_CHUNK_BACKEND: return wrapper(reinterpret_cast<IRopeChunkBackend::TPtr&>(value));
+ }
Y_FAIL("Unexpected type# %" PRIu64, static_cast<ui64>(type));
- }
-
- template<typename TCallback>
- static std::invoke_result_t<TCallback, EType, TString&> Visit(uintptr_t value, TCallback&& callback) {
- return VisitRaw(value, [&](EType type, auto& value) {
- return std::invoke(std::forward<TCallback>(callback), type, Unwrap(value));
- });
- }
-
- template<typename T> static T& Unwrap(T& object) { return object; }
- template<typename T> static T& Unwrap(TObjectHolder<T>& holder) { return holder.Object->Value; }
-
- static uintptr_t Clone(uintptr_t value) {
- return VisitRaw(value, [](EType type, auto& value) { return Construct(type, value); });
- }
-
- static void Destroy(uintptr_t value) {
- VisitRaw(value, [](EType, auto& value) { CallDtor(value); });
- }
-
- template<typename T>
- static void CallDtor(T& value) {
- value.~T();
- }
- };
-
- TBackend Backend; // who actually holds the data
- const char *Begin; // data start
- const char *End; // data end
-
- static constexpr struct TSlice {} Slice{};
-
- template<typename T>
- TChunk(T&& backend, const IRopeChunkBackend::TData& data)
- : Backend(std::move(backend))
- , Begin(std::get<0>(data))
- , End(Begin + std::get<1>(data))
- {
- Y_VERIFY_DEBUG(Begin != End);
- }
-
- TChunk(TString s)
- : Backend(std::move(s))
- {
- size_t size;
- std::tie(Begin, size) = Backend.GetData();
- End = Begin + size;
- }
-
- TChunk(IRopeChunkBackend::TPtr backend)
- : TChunk(backend, backend->GetData())
- {}
-
- TChunk(TSlice, const char *data, size_t size, const TChunk& from)
- : TChunk(from.Backend, {data, size})
- {}
-
- TChunk(TSlice, const char *begin, const char *end, const TChunk& from)
- : TChunk(Slice, begin, end - begin, from)
- {}
-
- explicit TChunk(const TChunk& other)
- : Backend(other.Backend)
- , Begin(other.Begin)
- , End(other.End)
- {}
-
- TChunk(TChunk&& other)
- : Backend(std::move(other.Backend))
- , Begin(other.Begin)
- , End(other.End)
- {}
-
- TChunk& operator =(const TChunk&) = default;
- TChunk& operator =(TChunk&&) = default;
-
- size_t GetSize() const {
- return End - Begin;
- }
-
- static void Clear(TChunk& chunk) {
- chunk.Begin = nullptr;
- }
-
- static bool IsInUse(const TChunk& chunk) {
- return chunk.Begin != nullptr;
- }
-
- size_t GetCapacity() const {
- return Backend.GetCapacity();
- }
- };
-
- using TChunkList = NRopeDetails::TChunkList<TChunk>;
-
-private:
- // we use list here to store chain items as we have to keep valid iterators when erase/insert operations are invoked;
- // iterator uses underlying container's iterator, so we have to use container that keeps valid iterators on delete,
- // thus, the list
- TChunkList Chain;
- size_t Size = 0;
-
-private:
- template<bool IsConst>
- class TIteratorImpl {
- using TTraits = NRopeDetails::TIteratorTraits<IsConst, TRope, TChunkList>;
-
- typename TTraits::TRopePtr Rope;
- typename TTraits::TListIterator Iter;
- const char *Ptr; // ptr is always nullptr when iterator is positioned at the rope end
-
-#ifndef NDEBUG
- ui32 ValidityToken;
-#endif
-
- private:
- TIteratorImpl(typename TTraits::TRopePtr rope, typename TTraits::TListIterator iter, const char *ptr = nullptr)
- : Rope(rope)
- , Iter(iter)
- , Ptr(ptr)
-#ifndef NDEBUG
- , ValidityToken(Rope->GetValidityToken())
-#endif
- {}
-
- public:
- TIteratorImpl()
- : Rope(nullptr)
- , Ptr(nullptr)
- {}
-
- template<bool IsOtherConst>
- TIteratorImpl(const TIteratorImpl<IsOtherConst>& other)
- : Rope(other.Rope)
- , Iter(other.Iter)
- , Ptr(other.Ptr)
-#ifndef NDEBUG
- , ValidityToken(other.ValidityToken)
-#endif
- {}
-
- void CheckValid() const {
-#ifndef NDEBUG
- Y_VERIFY(ValidityToken == Rope->GetValidityToken());
-#endif
- }
-
- TIteratorImpl& operator +=(size_t amount) {
- CheckValid();
-
- while (amount) {
- Y_VERIFY_DEBUG(Valid());
- const size_t max = ContiguousSize();
- const size_t num = std::min(amount, max);
- amount -= num;
- Ptr += num;
- if (Ptr == Iter->End) {
- AdvanceToNextContiguousBlock();
- }
- }
-
- return *this;
- }
-
- TIteratorImpl operator +(size_t amount) const {
- CheckValid();
-
- return TIteratorImpl(*this) += amount;
- }
-
- TIteratorImpl& operator -=(size_t amount) {
- CheckValid();
-
- while (amount) {
- const size_t num = Ptr ? std::min<size_t>(amount, Ptr - Iter->Begin) : 0;
- amount -= num;
- Ptr -= num;
- if (amount) {
- Y_VERIFY_DEBUG(Iter != GetChainBegin());
- --Iter;
- Ptr = Iter->End;
- }
- }
-
- return *this;
- }
-
- TIteratorImpl operator -(size_t amount) const {
- CheckValid();
- return TIteratorImpl(*this) -= amount;
- }
-
- std::pair<const char*, size_t> operator *() const {
- return {ContiguousData(), ContiguousSize()};
- }
-
- TIteratorImpl& operator ++() {
- AdvanceToNextContiguousBlock();
- return *this;
- }
-
- TIteratorImpl operator ++(int) const {
- auto it(*this);
- it.AdvanceToNextContiguousBlock();
- return it;
- }
-
- ////////////////////////////////////////////////////////////////////////////////////////////////////////////////
- // Operation with contiguous data
- ////////////////////////////////////////////////////////////////////////////////////////////////////////////////
-
- // Get the pointer to the contiguous block of data; valid locations are [Data; Data + Size).
- const char *ContiguousData() const {
- CheckValid();
- return Ptr;
- }
-
- // Get the amount of contiguous block.
- size_t ContiguousSize() const {
- CheckValid();
- return Ptr ? Iter->End - Ptr : 0;
- }
-
+ }
+
+ template<typename TCallback>
+ static std::invoke_result_t<TCallback, EType, TString&> Visit(uintptr_t value, TCallback&& callback) {
+ return VisitRaw(value, [&](EType type, auto& value) {
+ return std::invoke(std::forward<TCallback>(callback), type, Unwrap(value));
+ });
+ }
+
+ template<typename T> static T& Unwrap(T& object) { return object; }
+ template<typename T> static T& Unwrap(TObjectHolder<T>& holder) { return holder.Object->Value; }
+
+ static uintptr_t Clone(uintptr_t value) {
+ return VisitRaw(value, [](EType type, auto& value) { return Construct(type, value); });
+ }
+
+ static void Destroy(uintptr_t value) {
+ VisitRaw(value, [](EType, auto& value) { CallDtor(value); });
+ }
+
+ template<typename T>
+ static void CallDtor(T& value) {
+ value.~T();
+ }
+ };
+
+ TBackend Backend; // who actually holds the data
+ const char *Begin; // data start
+ const char *End; // data end
+
+ static constexpr struct TSlice {} Slice{};
+
+ template<typename T>
+ TChunk(T&& backend, const IRopeChunkBackend::TData& data)
+ : Backend(std::move(backend))
+ , Begin(std::get<0>(data))
+ , End(Begin + std::get<1>(data))
+ {
+ Y_VERIFY_DEBUG(Begin != End);
+ }
+
+ TChunk(TString s)
+ : Backend(std::move(s))
+ {
+ size_t size;
+ std::tie(Begin, size) = Backend.GetData();
+ End = Begin + size;
+ }
+
+ TChunk(IRopeChunkBackend::TPtr backend)
+ : TChunk(backend, backend->GetData())
+ {}
+
+ TChunk(TSlice, const char *data, size_t size, const TChunk& from)
+ : TChunk(from.Backend, {data, size})
+ {}
+
+ TChunk(TSlice, const char *begin, const char *end, const TChunk& from)
+ : TChunk(Slice, begin, end - begin, from)
+ {}
+
+ explicit TChunk(const TChunk& other)
+ : Backend(other.Backend)
+ , Begin(other.Begin)
+ , End(other.End)
+ {}
+
+ TChunk(TChunk&& other)
+ : Backend(std::move(other.Backend))
+ , Begin(other.Begin)
+ , End(other.End)
+ {}
+
+ TChunk& operator =(const TChunk&) = default;
+ TChunk& operator =(TChunk&&) = default;
+
+ size_t GetSize() const {
+ return End - Begin;
+ }
+
+ static void Clear(TChunk& chunk) {
+ chunk.Begin = nullptr;
+ }
+
+ static bool IsInUse(const TChunk& chunk) {
+ return chunk.Begin != nullptr;
+ }
+
+ size_t GetCapacity() const {
+ return Backend.GetCapacity();
+ }
+ };
+
+ using TChunkList = NRopeDetails::TChunkList<TChunk>;
+
+private:
+ // we use list here to store chain items as we have to keep valid iterators when erase/insert operations are invoked;
+ // iterator uses underlying container's iterator, so we have to use container that keeps valid iterators on delete,
+ // thus, the list
+ TChunkList Chain;
+ size_t Size = 0;
+
+private:
+ template<bool IsConst>
+ class TIteratorImpl {
+ using TTraits = NRopeDetails::TIteratorTraits<IsConst, TRope, TChunkList>;
+
+ typename TTraits::TRopePtr Rope;
+ typename TTraits::TListIterator Iter;
+ const char *Ptr; // ptr is always nullptr when iterator is positioned at the rope end
+
+#ifndef NDEBUG
+ ui32 ValidityToken;
+#endif
+
+ private:
+ TIteratorImpl(typename TTraits::TRopePtr rope, typename TTraits::TListIterator iter, const char *ptr = nullptr)
+ : Rope(rope)
+ , Iter(iter)
+ , Ptr(ptr)
+#ifndef NDEBUG
+ , ValidityToken(Rope->GetValidityToken())
+#endif
+ {}
+
+ public:
+ TIteratorImpl()
+ : Rope(nullptr)
+ , Ptr(nullptr)
+ {}
+
+ template<bool IsOtherConst>
+ TIteratorImpl(const TIteratorImpl<IsOtherConst>& other)
+ : Rope(other.Rope)
+ , Iter(other.Iter)
+ , Ptr(other.Ptr)
+#ifndef NDEBUG
+ , ValidityToken(other.ValidityToken)
+#endif
+ {}
+
+ void CheckValid() const {
+#ifndef NDEBUG
+ Y_VERIFY(ValidityToken == Rope->GetValidityToken());
+#endif
+ }
+
+ TIteratorImpl& operator +=(size_t amount) {
+ CheckValid();
+
+ while (amount) {
+ Y_VERIFY_DEBUG(Valid());
+ const size_t max = ContiguousSize();
+ const size_t num = std::min(amount, max);
+ amount -= num;
+ Ptr += num;
+ if (Ptr == Iter->End) {
+ AdvanceToNextContiguousBlock();
+ }
+ }
+
+ return *this;
+ }
+
+ TIteratorImpl operator +(size_t amount) const {
+ CheckValid();
+
+ return TIteratorImpl(*this) += amount;
+ }
+
+ TIteratorImpl& operator -=(size_t amount) {
+ CheckValid();
+
+ while (amount) {
+ const size_t num = Ptr ? std::min<size_t>(amount, Ptr - Iter->Begin) : 0;
+ amount -= num;
+ Ptr -= num;
+ if (amount) {
+ Y_VERIFY_DEBUG(Iter != GetChainBegin());
+ --Iter;
+ Ptr = Iter->End;
+ }
+ }
+
+ return *this;
+ }
+
+ TIteratorImpl operator -(size_t amount) const {
+ CheckValid();
+ return TIteratorImpl(*this) -= amount;
+ }
+
+ std::pair<const char*, size_t> operator *() const {
+ return {ContiguousData(), ContiguousSize()};
+ }
+
+ TIteratorImpl& operator ++() {
+ AdvanceToNextContiguousBlock();
+ return *this;
+ }
+
+ TIteratorImpl operator ++(int) const {
+ auto it(*this);
+ it.AdvanceToNextContiguousBlock();
+ return it;
+ }
+
+ ////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+ // Operation with contiguous data
+ ////////////////////////////////////////////////////////////////////////////////////////////////////////////////
+
+ // Get the pointer to the contiguous block of data; valid locations are [Data; Data + Size).
+ const char *ContiguousData() const {
+ CheckValid();
+ return Ptr;
+ }
+
+ // Get the amount of contiguous block.
+ size_t ContiguousSize() const {
+ CheckValid();
+ return Ptr ? Iter->End - Ptr : 0;
+ }
+
size_t ChunkOffset() const {
return Ptr ? Ptr - Iter->Begin : 0;
}
- // Advance to next contiguous block of data.
- void AdvanceToNextContiguousBlock() {
- CheckValid();
- Y_VERIFY_DEBUG(Valid());
- ++Iter;
- Ptr = Iter != GetChainEnd() ? Iter->Begin : nullptr;
- }
-
- // Extract some data and advance. Size is not checked here, to it must be provided valid.
- void ExtractPlainDataAndAdvance(void *buffer, size_t len) {
- CheckValid();
-
- while (len) {
- Y_VERIFY_DEBUG(Ptr);
-
- // calculate amount of bytes we need to move
- const size_t max = ContiguousSize();
- const size_t num = std::min(len, max);
-
- // copy data to the buffer and advance buffer pointers
- memcpy(buffer, Ptr, num);
- buffer = static_cast<char*>(buffer) + num;
- len -= num;
-
- // advance iterator itself
- Ptr += num;
- if (Ptr == Iter->End) {
- AdvanceToNextContiguousBlock();
- }
- }
- }
-
- // Checks if the iterator points to the end of the rope or not.
- bool Valid() const {
- CheckValid();
- return Ptr;
- }
-
- template<bool IsOtherConst>
- bool operator ==(const TIteratorImpl<IsOtherConst>& other) const {
- Y_VERIFY_DEBUG(Rope == other.Rope);
- CheckValid();
- other.CheckValid();
- return Iter == other.Iter && Ptr == other.Ptr;
- }
-
- template<bool IsOtherConst>
- bool operator !=(const TIteratorImpl<IsOtherConst>& other) const {
- CheckValid();
- other.CheckValid();
- return !(*this == other);
- }
-
- private:
- friend class TRope;
-
- typename TTraits::TListIterator operator ->() const {
- CheckValid();
- return Iter;
- }
-
- const TChunk& GetChunk() const {
- CheckValid();
- return *Iter;
- }
-
- typename TTraits::TListIterator GetChainBegin() const {
- CheckValid();
- return Rope->Chain.begin();
- }
-
- typename TTraits::TListIterator GetChainEnd() const {
- CheckValid();
- return Rope->Chain.end();
- }
-
- bool PointsToChunkMiddle() const {
- CheckValid();
- return Ptr && Ptr != Iter->Begin;
- }
- };
-
-public:
-#ifndef NDEBUG
- ui32 ValidityToken = 0;
- ui32 GetValidityToken() const { return ValidityToken; }
- void InvalidateIterators() { ++ValidityToken; }
-#else
- void InvalidateIterators() {}
-#endif
-
-public:
- using TConstIterator = TIteratorImpl<true>;
- using TIterator = TIteratorImpl<false>;
-
-public:
- TRope() = default;
- TRope(const TRope& rope) = default;
-
- TRope(TRope&& rope)
- : Chain(std::move(rope.Chain))
- , Size(std::exchange(rope.Size, 0))
- {
- rope.InvalidateIterators();
- }
-
- TRope(TString s) {
- if (s) {
- Size = s.size();
+ // Advance to next contiguous block of data.
+ void AdvanceToNextContiguousBlock() {
+ CheckValid();
+ Y_VERIFY_DEBUG(Valid());
+ ++Iter;
+ Ptr = Iter != GetChainEnd() ? Iter->Begin : nullptr;
+ }
+
+ // Extract some data and advance. Size is not checked here, to it must be provided valid.
+ void ExtractPlainDataAndAdvance(void *buffer, size_t len) {
+ CheckValid();
+
+ while (len) {
+ Y_VERIFY_DEBUG(Ptr);
+
+ // calculate amount of bytes we need to move
+ const size_t max = ContiguousSize();
+ const size_t num = std::min(len, max);
+
+ // copy data to the buffer and advance buffer pointers
+ memcpy(buffer, Ptr, num);
+ buffer = static_cast<char*>(buffer) + num;
+ len -= num;
+
+ // advance iterator itself
+ Ptr += num;
+ if (Ptr == Iter->End) {
+ AdvanceToNextContiguousBlock();
+ }
+ }
+ }
+
+ // Checks if the iterator points to the end of the rope or not.
+ bool Valid() const {
+ CheckValid();
+ return Ptr;
+ }
+
+ template<bool IsOtherConst>
+ bool operator ==(const TIteratorImpl<IsOtherConst>& other) const {
+ Y_VERIFY_DEBUG(Rope == other.Rope);
+ CheckValid();
+ other.CheckValid();
+ return Iter == other.Iter && Ptr == other.Ptr;
+ }
+
+ template<bool IsOtherConst>
+ bool operator !=(const TIteratorImpl<IsOtherConst>& other) const {
+ CheckValid();
+ other.CheckValid();
+ return !(*this == other);
+ }
+
+ private:
+ friend class TRope;
+
+ typename TTraits::TListIterator operator ->() const {
+ CheckValid();
+ return Iter;
+ }
+
+ const TChunk& GetChunk() const {
+ CheckValid();
+ return *Iter;
+ }
+
+ typename TTraits::TListIterator GetChainBegin() const {
+ CheckValid();
+ return Rope->Chain.begin();
+ }
+
+ typename TTraits::TListIterator GetChainEnd() const {
+ CheckValid();
+ return Rope->Chain.end();
+ }
+
+ bool PointsToChunkMiddle() const {
+ CheckValid();
+ return Ptr && Ptr != Iter->Begin;
+ }
+ };
+
+public:
+#ifndef NDEBUG
+ ui32 ValidityToken = 0;
+ ui32 GetValidityToken() const { return ValidityToken; }
+ void InvalidateIterators() { ++ValidityToken; }
+#else
+ void InvalidateIterators() {}
+#endif
+
+public:
+ using TConstIterator = TIteratorImpl<true>;
+ using TIterator = TIteratorImpl<false>;
+
+public:
+ TRope() = default;
+ TRope(const TRope& rope) = default;
+
+ TRope(TRope&& rope)
+ : Chain(std::move(rope.Chain))
+ , Size(std::exchange(rope.Size, 0))
+ {
+ rope.InvalidateIterators();
+ }
+
+ TRope(TString s) {
+ if (s) {
+ Size = s.size();
s.reserve(32);
- Chain.PutToEnd(std::move(s));
- }
- }
-
- TRope(IRopeChunkBackend::TPtr item) {
- std::tie(std::ignore, Size) = item->GetData();
- Chain.PutToEnd(std::move(item));
- }
-
- TRope(TConstIterator begin, TConstIterator end) {
- Y_VERIFY_DEBUG(begin.Rope == end.Rope);
- if (begin.Rope == this) {
- TRope temp(begin, end);
- *this = std::move(temp);
- return;
- }
-
- while (begin.Iter != end.Iter) {
- const size_t size = begin.ContiguousSize();
- Chain.PutToEnd(TChunk::Slice, begin.ContiguousData(), size, begin.GetChunk());
- begin.AdvanceToNextContiguousBlock();
- Size += size;
- }
-
- if (begin != end && end.PointsToChunkMiddle()) {
- Chain.PutToEnd(TChunk::Slice, begin.Ptr, end.Ptr, begin.GetChunk());
- Size += end.Ptr - begin.Ptr;
- }
- }
-
- ~TRope() {
- }
-
- // creates a copy of rope with chunks with inefficient storage ratio being copied with arena allocator
- static TRope CopySpaceOptimized(TRope&& origin, size_t worstRatioPer1k, TRopeArena& arena);
-
- TRope& operator=(const TRope& other) {
- Chain = other.Chain;
- Size = other.Size;
- return *this;
- }
-
- TRope& operator=(TRope&& other) {
- Chain = std::move(other.Chain);
- Size = std::exchange(other.Size, 0);
- InvalidateIterators();
- other.InvalidateIterators();
- return *this;
- }
-
- size_t GetSize() const {
- return Size;
- }
-
- bool IsEmpty() const {
- return !Size;
- }
-
- operator bool() const {
- return Chain;
- }
-
- TIterator Begin() {
- return *this ? TIterator(this, Chain.begin(), Chain.GetFirstChunk().Begin) : End();
- }
-
- TIterator End() {
- return TIterator(this, Chain.end());
- }
-
- TIterator Iterator(TChunkList::iterator it) {
- return TIterator(this, it, it != Chain.end() ? it->Begin : nullptr);
- }
-
- TIterator Position(size_t index) {
- return Begin() + index;
- }
-
- TConstIterator Begin() const {
- return *this ? TConstIterator(this, Chain.begin(), Chain.GetFirstChunk().Begin) : End();
- }
-
- TConstIterator End() const {
- return TConstIterator(this, Chain.end());
- }
-
- TConstIterator Position(size_t index) const {
- return Begin() + index;
- }
-
- TConstIterator begin() const { return Begin(); }
- TConstIterator end() const { return End(); }
-
- void Erase(TIterator begin, TIterator end) {
- Cut(begin, end, nullptr);
- }
-
- TRope Extract(TIterator begin, TIterator end) {
- TRope res;
- Cut(begin, end, &res);
- return res;
- }
-
- void ExtractFront(size_t num, TRope *dest) {
- Y_VERIFY(Size >= num);
- if (num == Size && !*dest) {
- *dest = std::move(*this);
- return;
- }
- Size -= num;
- dest->Size += num;
- TChunkList::iterator it, first = Chain.begin();
- for (it = first; num && num >= it->GetSize(); ++it) {
- num -= it->GetSize();
- }
- if (it != first) {
- if (dest->Chain) {
- auto& last = dest->Chain.GetLastChunk();
- if (last.Backend == first->Backend && last.End == first->Begin) {
- last.End = first->End;
- first = Chain.Erase(first); // TODO(alexvru): "it" gets invalidated here on some containers
- }
- }
- dest->Chain.Splice(dest->Chain.end(), Chain, first, it);
- }
- if (num) {
- auto it = Chain.begin();
- if (dest->Chain) {
- auto& last = dest->Chain.GetLastChunk();
- if (last.Backend == first->Backend && last.End == first->Begin) {
- first->Begin += num;
- last.End = first->Begin;
- return;
- }
- }
- dest->Chain.PutToEnd(TChunk::Slice, it->Begin, it->Begin + num, *it);
- it->Begin += num;
- }
- }
-
- void Insert(TIterator pos, TRope&& rope) {
- Y_VERIFY_DEBUG(this == pos.Rope);
- Y_VERIFY_DEBUG(this != &rope);
-
- if (!rope) {
- return; // do nothing for empty rope
- }
-
- // adjust size
- Size += std::exchange(rope.Size, 0);
-
- // check if we have to split the block
- if (pos.PointsToChunkMiddle()) {
- pos.Iter = Chain.InsertBefore(pos.Iter, TChunk::Slice, pos->Begin, pos.Ptr, pos.GetChunk());
- ++pos.Iter;
- pos->Begin = pos.Ptr;
- }
-
- // perform glueing if possible
- TChunk *ropeLeft = &rope.Chain.GetFirstChunk();
- TChunk *ropeRight = &rope.Chain.GetLastChunk();
- bool gluedLeft = false, gluedRight = false;
- if (pos.Iter != Chain.begin()) { // glue left part whenever possible
- // obtain iterator to previous chunk
- auto prev(pos.Iter);
- --prev;
- if (prev->End == ropeLeft->Begin && prev->Backend == ropeLeft->Backend) { // it is glueable
- prev->End = ropeLeft->End;
- gluedLeft = true;
- }
- }
- if (pos.Iter != Chain.end() && ropeRight->End == pos->Begin && ropeRight->Backend == pos->Backend) {
- pos->Begin = ropeRight->Begin;
- gluedRight = true;
- }
- if (gluedLeft) {
- rope.Chain.EraseFront();
- }
- if (gluedRight) {
- if (rope) {
- rope.Chain.EraseBack();
- } else { // it looks like double-glueing for the same chunk, we have to drop previous one
- auto prev(pos.Iter);
- --prev;
- pos->Begin = prev->Begin;
- pos.Iter = Chain.Erase(prev);
- }
- }
- if (rope) { // insert remains
- Chain.Splice(pos.Iter, rope.Chain, rope.Chain.begin(), rope.Chain.end());
- }
- Y_VERIFY_DEBUG(!rope);
- InvalidateIterators();
- }
-
- void EraseFront(size_t len) {
- Y_VERIFY_DEBUG(Size >= len);
- Size -= len;
-
- while (len) {
- Y_VERIFY_DEBUG(Chain);
- TChunk& item = Chain.GetFirstChunk();
- const size_t itemSize = item.GetSize();
- if (len >= itemSize) {
- Chain.EraseFront();
- len -= itemSize;
- } else {
- item.Begin += len;
- break;
- }
- }
-
- InvalidateIterators();
- }
-
- void EraseBack(size_t len) {
- Y_VERIFY_DEBUG(Size >= len);
- Size -= len;
-
- while (len) {
- Y_VERIFY_DEBUG(Chain);
- TChunk& item = Chain.GetLastChunk();
- const size_t itemSize = item.GetSize();
- if (len >= itemSize) {
- Chain.EraseBack();
- len -= itemSize;
- } else {
- item.End -= len;
- break;
- }
- }
-
- InvalidateIterators();
- }
-
- bool ExtractFrontPlain(void *buffer, size_t len) {
- // check if we have enough data in the rope
- if (Size < len) {
- return false;
- }
- Size -= len;
- while (len) {
- auto& chunk = Chain.GetFirstChunk();
- const size_t num = Min(len, chunk.GetSize());
- memcpy(buffer, chunk.Begin, num);
- buffer = static_cast<char*>(buffer) + num;
- len -= num;
- chunk.Begin += num;
- if (chunk.Begin == chunk.End) {
- Chain.Erase(Chain.begin());
- }
- }
- InvalidateIterators();
- return true;
- }
-
- bool FetchFrontPlain(char **ptr, size_t *remain) {
- const size_t num = Min(*remain, Size);
- ExtractFrontPlain(*ptr, num);
- *ptr += num;
- *remain -= num;
- return !*remain;
- }
-
- static int Compare(const TRope& x, const TRope& y) {
- TConstIterator xIter = x.Begin(), yIter = y.Begin();
- while (xIter.Valid() && yIter.Valid()) {
- const size_t step = std::min(xIter.ContiguousSize(), yIter.ContiguousSize());
- if (int res = memcmp(xIter.ContiguousData(), yIter.ContiguousData(), step)) {
- return res;
- }
- xIter += step;
- yIter += step;
- }
- return xIter.Valid() - yIter.Valid();
- }
-
- // Use this method carefully -- it may significantly reduce performance when misused.
- TString ConvertToString() const {
- TString res = TString::Uninitialized(GetSize());
- Begin().ExtractPlainDataAndAdvance(res.Detach(), res.size());
- return res;
- }
-
- TString DebugString() const {
- TStringStream s;
- s << "{Size# " << Size;
- for (const auto& chunk : Chain) {
- const char *data;
- std::tie(data, std::ignore) = chunk.Backend.GetData();
- s << " [" << chunk.Begin - data << ", " << chunk.End - data << ")@" << chunk.Backend.UniqueId();
- }
- s << "}";
- return s.Str();
- }
-
- friend bool operator==(const TRope& x, const TRope& y) { return Compare(x, y) == 0; }
- friend bool operator!=(const TRope& x, const TRope& y) { return Compare(x, y) != 0; }
- friend bool operator< (const TRope& x, const TRope& y) { return Compare(x, y) < 0; }
- friend bool operator<=(const TRope& x, const TRope& y) { return Compare(x, y) <= 0; }
- friend bool operator> (const TRope& x, const TRope& y) { return Compare(x, y) > 0; }
- friend bool operator>=(const TRope& x, const TRope& y) { return Compare(x, y) >= 0; }
-
-private:
- void Cut(TIterator begin, TIterator end, TRope *target) {
- // ensure all iterators are belong to us
- Y_VERIFY_DEBUG(this == begin.Rope && this == end.Rope);
-
- // if begin and end are equal, we do nothing -- checking this case allows us to find out that begin does not
- // point to End(), for example
- if (begin == end) {
- return;
- }
-
- auto addBlock = [&](const TChunk& from, const char *begin, const char *end) {
- if (target) {
- target->Chain.PutToEnd(TChunk::Slice, begin, end, from);
- target->Size += end - begin;
- }
- Size -= end - begin;
- };
-
- // consider special case -- when begin and end point to the same block; in this case we have to split up this
- // block into two parts
- if (begin.Iter == end.Iter) {
- addBlock(begin.GetChunk(), begin.Ptr, end.Ptr);
- const char *firstChunkBegin = begin.PointsToChunkMiddle() ? begin->Begin : nullptr;
- begin->Begin = end.Ptr; // this affects both begin and end iterator pointed values
- if (firstChunkBegin) {
- Chain.InsertBefore(begin.Iter, TChunk::Slice, firstChunkBegin, begin.Ptr, begin.GetChunk());
- }
- } else {
- // check the first iterator -- if it starts not from the begin of the block, we have to adjust end of the
- // first block to match begin iterator and switch to next block
- if (begin.PointsToChunkMiddle()) {
- addBlock(begin.GetChunk(), begin.Ptr, begin->End);
- begin->End = begin.Ptr;
- begin.AdvanceToNextContiguousBlock();
- }
-
- // now drop full blocks
- size_t rangeSize = 0;
- for (auto it = begin.Iter; it != end.Iter; ++it) {
- Y_VERIFY_DEBUG(it->GetSize());
- rangeSize += it->GetSize();
- }
- if (rangeSize) {
- if (target) {
- end.Iter = target->Chain.Splice(target->Chain.end(), Chain, begin.Iter, end.Iter);
- target->Size += rangeSize;
- } else {
- end.Iter = Chain.Erase(begin.Iter, end.Iter);
- }
- Size -= rangeSize;
- }
-
- // and cut the last block if necessary
- if (end.PointsToChunkMiddle()) {
- addBlock(end.GetChunk(), end->Begin, end.Ptr);
- end->Begin = end.Ptr;
- }
- }
-
- InvalidateIterators();
- }
-};
-
-class TRopeArena {
- using TAllocateCallback = std::function<TIntrusivePtr<IRopeChunkBackend>()>;
-
- TAllocateCallback Allocator;
- TRope Arena;
- size_t Size = 0;
- THashSet<const void*> AccountedBuffers;
-
-public:
- TRopeArena(TAllocateCallback&& allocator)
- : Allocator(std::move(allocator))
- {}
-
- TRope CreateRope(const void *buffer, size_t len) {
- TRope res;
-
- while (len) {
- if (Arena) {
- auto iter = Arena.Begin();
- Y_VERIFY_DEBUG(iter.Valid());
- char *dest = const_cast<char*>(iter.ContiguousData());
- const size_t bytesToCopy = std::min(len, iter.ContiguousSize());
- memcpy(dest, buffer, bytesToCopy);
- buffer = static_cast<const char*>(buffer) + bytesToCopy;
- len -= bytesToCopy;
- res.Insert(res.End(), Arena.Extract(Arena.Begin(), Arena.Position(bytesToCopy)));
- } else {
- Arena.Insert(Arena.End(), TRope(Allocator()));
- }
- }
-
- // align arena on 8-byte boundary
- const size_t align = 8;
- if (const size_t padding = Arena.GetSize() % align) {
- Arena.EraseFront(padding);
- }
-
- return res;
- }
-
- size_t GetSize() const {
- return Size;
- }
-
- void AccountChunk(const TRope::TChunk& chunk) {
- if (AccountedBuffers.insert(chunk.Backend.UniqueId()).second) {
- Size += chunk.GetCapacity();
- }
- }
-};
-
+ Chain.PutToEnd(std::move(s));
+ }
+ }
+
+ TRope(IRopeChunkBackend::TPtr item) {
+ std::tie(std::ignore, Size) = item->GetData();
+ Chain.PutToEnd(std::move(item));
+ }
+
+ TRope(TConstIterator begin, TConstIterator end) {
+ Y_VERIFY_DEBUG(begin.Rope == end.Rope);
+ if (begin.Rope == this) {
+ TRope temp(begin, end);
+ *this = std::move(temp);
+ return;
+ }
+
+ while (begin.Iter != end.Iter) {
+ const size_t size = begin.ContiguousSize();
+ Chain.PutToEnd(TChunk::Slice, begin.ContiguousData(), size, begin.GetChunk());
+ begin.AdvanceToNextContiguousBlock();
+ Size += size;
+ }
+
+ if (begin != end && end.PointsToChunkMiddle()) {
+ Chain.PutToEnd(TChunk::Slice, begin.Ptr, end.Ptr, begin.GetChunk());
+ Size += end.Ptr - begin.Ptr;
+ }
+ }
+
+ ~TRope() {
+ }
+
+ // creates a copy of rope with chunks with inefficient storage ratio being copied with arena allocator
+ static TRope CopySpaceOptimized(TRope&& origin, size_t worstRatioPer1k, TRopeArena& arena);
+
+ TRope& operator=(const TRope& other) {
+ Chain = other.Chain;
+ Size = other.Size;
+ return *this;
+ }
+
+ TRope& operator=(TRope&& other) {
+ Chain = std::move(other.Chain);
+ Size = std::exchange(other.Size, 0);
+ InvalidateIterators();
+ other.InvalidateIterators();
+ return *this;
+ }
+
+ size_t GetSize() const {
+ return Size;
+ }
+
+ bool IsEmpty() const {
+ return !Size;
+ }
+
+ operator bool() const {
+ return Chain;
+ }
+
+ TIterator Begin() {
+ return *this ? TIterator(this, Chain.begin(), Chain.GetFirstChunk().Begin) : End();
+ }
+
+ TIterator End() {
+ return TIterator(this, Chain.end());
+ }
+
+ TIterator Iterator(TChunkList::iterator it) {
+ return TIterator(this, it, it != Chain.end() ? it->Begin : nullptr);
+ }
+
+ TIterator Position(size_t index) {
+ return Begin() + index;
+ }
+
+ TConstIterator Begin() const {
+ return *this ? TConstIterator(this, Chain.begin(), Chain.GetFirstChunk().Begin) : End();
+ }
+
+ TConstIterator End() const {
+ return TConstIterator(this, Chain.end());
+ }
+
+ TConstIterator Position(size_t index) const {
+ return Begin() + index;
+ }
+
+ TConstIterator begin() const { return Begin(); }
+ TConstIterator end() const { return End(); }
+
+ void Erase(TIterator begin, TIterator end) {
+ Cut(begin, end, nullptr);
+ }
+
+ TRope Extract(TIterator begin, TIterator end) {
+ TRope res;
+ Cut(begin, end, &res);
+ return res;
+ }
+
+ void ExtractFront(size_t num, TRope *dest) {
+ Y_VERIFY(Size >= num);
+ if (num == Size && !*dest) {
+ *dest = std::move(*this);
+ return;
+ }
+ Size -= num;
+ dest->Size += num;
+ TChunkList::iterator it, first = Chain.begin();
+ for (it = first; num && num >= it->GetSize(); ++it) {
+ num -= it->GetSize();
+ }
+ if (it != first) {
+ if (dest->Chain) {
+ auto& last = dest->Chain.GetLastChunk();
+ if (last.Backend == first->Backend && last.End == first->Begin) {
+ last.End = first->End;
+ first = Chain.Erase(first); // TODO(alexvru): "it" gets invalidated here on some containers
+ }
+ }
+ dest->Chain.Splice(dest->Chain.end(), Chain, first, it);
+ }
+ if (num) {
+ auto it = Chain.begin();
+ if (dest->Chain) {
+ auto& last = dest->Chain.GetLastChunk();
+ if (last.Backend == first->Backend && last.End == first->Begin) {
+ first->Begin += num;
+ last.End = first->Begin;
+ return;
+ }
+ }
+ dest->Chain.PutToEnd(TChunk::Slice, it->Begin, it->Begin + num, *it);
+ it->Begin += num;
+ }
+ }
+
+ void Insert(TIterator pos, TRope&& rope) {
+ Y_VERIFY_DEBUG(this == pos.Rope);
+ Y_VERIFY_DEBUG(this != &rope);
+
+ if (!rope) {
+ return; // do nothing for empty rope
+ }
+
+ // adjust size
+ Size += std::exchange(rope.Size, 0);
+
+ // check if we have to split the block
+ if (pos.PointsToChunkMiddle()) {
+ pos.Iter = Chain.InsertBefore(pos.Iter, TChunk::Slice, pos->Begin, pos.Ptr, pos.GetChunk());
+ ++pos.Iter;
+ pos->Begin = pos.Ptr;
+ }
+
+ // perform glueing if possible
+ TChunk *ropeLeft = &rope.Chain.GetFirstChunk();
+ TChunk *ropeRight = &rope.Chain.GetLastChunk();
+ bool gluedLeft = false, gluedRight = false;
+ if (pos.Iter != Chain.begin()) { // glue left part whenever possible
+ // obtain iterator to previous chunk
+ auto prev(pos.Iter);
+ --prev;
+ if (prev->End == ropeLeft->Begin && prev->Backend == ropeLeft->Backend) { // it is glueable
+ prev->End = ropeLeft->End;
+ gluedLeft = true;
+ }
+ }
+ if (pos.Iter != Chain.end() && ropeRight->End == pos->Begin && ropeRight->Backend == pos->Backend) {
+ pos->Begin = ropeRight->Begin;
+ gluedRight = true;
+ }
+ if (gluedLeft) {
+ rope.Chain.EraseFront();
+ }
+ if (gluedRight) {
+ if (rope) {
+ rope.Chain.EraseBack();
+ } else { // it looks like double-glueing for the same chunk, we have to drop previous one
+ auto prev(pos.Iter);
+ --prev;
+ pos->Begin = prev->Begin;
+ pos.Iter = Chain.Erase(prev);
+ }
+ }
+ if (rope) { // insert remains
+ Chain.Splice(pos.Iter, rope.Chain, rope.Chain.begin(), rope.Chain.end());
+ }
+ Y_VERIFY_DEBUG(!rope);
+ InvalidateIterators();
+ }
+
+ void EraseFront(size_t len) {
+ Y_VERIFY_DEBUG(Size >= len);
+ Size -= len;
+
+ while (len) {
+ Y_VERIFY_DEBUG(Chain);
+ TChunk& item = Chain.GetFirstChunk();
+ const size_t itemSize = item.GetSize();
+ if (len >= itemSize) {
+ Chain.EraseFront();
+ len -= itemSize;
+ } else {
+ item.Begin += len;
+ break;
+ }
+ }
+
+ InvalidateIterators();
+ }
+
+ void EraseBack(size_t len) {
+ Y_VERIFY_DEBUG(Size >= len);
+ Size -= len;
+
+ while (len) {
+ Y_VERIFY_DEBUG(Chain);
+ TChunk& item = Chain.GetLastChunk();
+ const size_t itemSize = item.GetSize();
+ if (len >= itemSize) {
+ Chain.EraseBack();
+ len -= itemSize;
+ } else {
+ item.End -= len;
+ break;
+ }
+ }
+
+ InvalidateIterators();
+ }
+
+ bool ExtractFrontPlain(void *buffer, size_t len) {
+ // check if we have enough data in the rope
+ if (Size < len) {
+ return false;
+ }
+ Size -= len;
+ while (len) {
+ auto& chunk = Chain.GetFirstChunk();
+ const size_t num = Min(len, chunk.GetSize());
+ memcpy(buffer, chunk.Begin, num);
+ buffer = static_cast<char*>(buffer) + num;
+ len -= num;
+ chunk.Begin += num;
+ if (chunk.Begin == chunk.End) {
+ Chain.Erase(Chain.begin());
+ }
+ }
+ InvalidateIterators();
+ return true;
+ }
+
+ bool FetchFrontPlain(char **ptr, size_t *remain) {
+ const size_t num = Min(*remain, Size);
+ ExtractFrontPlain(*ptr, num);
+ *ptr += num;
+ *remain -= num;
+ return !*remain;
+ }
+
+ static int Compare(const TRope& x, const TRope& y) {
+ TConstIterator xIter = x.Begin(), yIter = y.Begin();
+ while (xIter.Valid() && yIter.Valid()) {
+ const size_t step = std::min(xIter.ContiguousSize(), yIter.ContiguousSize());
+ if (int res = memcmp(xIter.ContiguousData(), yIter.ContiguousData(), step)) {
+ return res;
+ }
+ xIter += step;
+ yIter += step;
+ }
+ return xIter.Valid() - yIter.Valid();
+ }
+
+ // Use this method carefully -- it may significantly reduce performance when misused.
+ TString ConvertToString() const {
+ TString res = TString::Uninitialized(GetSize());
+ Begin().ExtractPlainDataAndAdvance(res.Detach(), res.size());
+ return res;
+ }
+
+ TString DebugString() const {
+ TStringStream s;
+ s << "{Size# " << Size;
+ for (const auto& chunk : Chain) {
+ const char *data;
+ std::tie(data, std::ignore) = chunk.Backend.GetData();
+ s << " [" << chunk.Begin - data << ", " << chunk.End - data << ")@" << chunk.Backend.UniqueId();
+ }
+ s << "}";
+ return s.Str();
+ }
+
+ friend bool operator==(const TRope& x, const TRope& y) { return Compare(x, y) == 0; }
+ friend bool operator!=(const TRope& x, const TRope& y) { return Compare(x, y) != 0; }
+ friend bool operator< (const TRope& x, const TRope& y) { return Compare(x, y) < 0; }
+ friend bool operator<=(const TRope& x, const TRope& y) { return Compare(x, y) <= 0; }
+ friend bool operator> (const TRope& x, const TRope& y) { return Compare(x, y) > 0; }
+ friend bool operator>=(const TRope& x, const TRope& y) { return Compare(x, y) >= 0; }
+
+private:
+ void Cut(TIterator begin, TIterator end, TRope *target) {
+ // ensure all iterators are belong to us
+ Y_VERIFY_DEBUG(this == begin.Rope && this == end.Rope);
+
+ // if begin and end are equal, we do nothing -- checking this case allows us to find out that begin does not
+ // point to End(), for example
+ if (begin == end) {
+ return;
+ }
+
+ auto addBlock = [&](const TChunk& from, const char *begin, const char *end) {
+ if (target) {
+ target->Chain.PutToEnd(TChunk::Slice, begin, end, from);
+ target->Size += end - begin;
+ }
+ Size -= end - begin;
+ };
+
+ // consider special case -- when begin and end point to the same block; in this case we have to split up this
+ // block into two parts
+ if (begin.Iter == end.Iter) {
+ addBlock(begin.GetChunk(), begin.Ptr, end.Ptr);
+ const char *firstChunkBegin = begin.PointsToChunkMiddle() ? begin->Begin : nullptr;
+ begin->Begin = end.Ptr; // this affects both begin and end iterator pointed values
+ if (firstChunkBegin) {
+ Chain.InsertBefore(begin.Iter, TChunk::Slice, firstChunkBegin, begin.Ptr, begin.GetChunk());
+ }
+ } else {
+ // check the first iterator -- if it starts not from the begin of the block, we have to adjust end of the
+ // first block to match begin iterator and switch to next block
+ if (begin.PointsToChunkMiddle()) {
+ addBlock(begin.GetChunk(), begin.Ptr, begin->End);
+ begin->End = begin.Ptr;
+ begin.AdvanceToNextContiguousBlock();
+ }
+
+ // now drop full blocks
+ size_t rangeSize = 0;
+ for (auto it = begin.Iter; it != end.Iter; ++it) {
+ Y_VERIFY_DEBUG(it->GetSize());
+ rangeSize += it->GetSize();
+ }
+ if (rangeSize) {
+ if (target) {
+ end.Iter = target->Chain.Splice(target->Chain.end(), Chain, begin.Iter, end.Iter);
+ target->Size += rangeSize;
+ } else {
+ end.Iter = Chain.Erase(begin.Iter, end.Iter);
+ }
+ Size -= rangeSize;
+ }
+
+ // and cut the last block if necessary
+ if (end.PointsToChunkMiddle()) {
+ addBlock(end.GetChunk(), end->Begin, end.Ptr);
+ end->Begin = end.Ptr;
+ }
+ }
+
+ InvalidateIterators();
+ }
+};
+
+class TRopeArena {
+ using TAllocateCallback = std::function<TIntrusivePtr<IRopeChunkBackend>()>;
+
+ TAllocateCallback Allocator;
+ TRope Arena;
+ size_t Size = 0;
+ THashSet<const void*> AccountedBuffers;
+
+public:
+ TRopeArena(TAllocateCallback&& allocator)
+ : Allocator(std::move(allocator))
+ {}
+
+ TRope CreateRope(const void *buffer, size_t len) {
+ TRope res;
+
+ while (len) {
+ if (Arena) {
+ auto iter = Arena.Begin();
+ Y_VERIFY_DEBUG(iter.Valid());
+ char *dest = const_cast<char*>(iter.ContiguousData());
+ const size_t bytesToCopy = std::min(len, iter.ContiguousSize());
+ memcpy(dest, buffer, bytesToCopy);
+ buffer = static_cast<const char*>(buffer) + bytesToCopy;
+ len -= bytesToCopy;
+ res.Insert(res.End(), Arena.Extract(Arena.Begin(), Arena.Position(bytesToCopy)));
+ } else {
+ Arena.Insert(Arena.End(), TRope(Allocator()));
+ }
+ }
+
+ // align arena on 8-byte boundary
+ const size_t align = 8;
+ if (const size_t padding = Arena.GetSize() % align) {
+ Arena.EraseFront(padding);
+ }
+
+ return res;
+ }
+
+ size_t GetSize() const {
+ return Size;
+ }
+
+ void AccountChunk(const TRope::TChunk& chunk) {
+ if (AccountedBuffers.insert(chunk.Backend.UniqueId()).second) {
+ Size += chunk.GetCapacity();
+ }
+ }
+};
+
struct TRopeUtils {
static void Memset(TRope::TConstIterator dst, char c, size_t size) {
while (size) {
@@ -1117,24 +1117,24 @@ public:
}
};
-inline TRope TRope::CopySpaceOptimized(TRope&& origin, size_t worstRatioPer1k, TRopeArena& arena) {
- TRope res;
- for (TChunk& chunk : origin.Chain) {
- size_t ratio = chunk.GetSize() * 1024 / chunk.GetCapacity();
- if (ratio < 1024 - worstRatioPer1k) {
- res.Insert(res.End(), arena.CreateRope(chunk.Begin, chunk.GetSize()));
- } else {
- res.Chain.PutToEnd(std::move(chunk));
- }
- }
- res.Size = origin.Size;
- origin = TRope();
- for (const TChunk& chunk : res.Chain) {
- arena.AccountChunk(chunk);
- }
- return res;
-}
-
+inline TRope TRope::CopySpaceOptimized(TRope&& origin, size_t worstRatioPer1k, TRopeArena& arena) {
+ TRope res;
+ for (TChunk& chunk : origin.Chain) {
+ size_t ratio = chunk.GetSize() * 1024 / chunk.GetCapacity();
+ if (ratio < 1024 - worstRatioPer1k) {
+ res.Insert(res.End(), arena.CreateRope(chunk.Begin, chunk.GetSize()));
+ } else {
+ res.Chain.PutToEnd(std::move(chunk));
+ }
+ }
+ res.Size = origin.Size;
+ origin = TRope();
+ for (const TChunk& chunk : res.Chain) {
+ arena.AccountChunk(chunk);
+ }
+ return res;
+}
+
#if defined(WITH_VALGRIND) || defined(_msan_enabled_)
diff --git a/library/cpp/actors/util/rope_cont_deque.h b/library/cpp/actors/util/rope_cont_deque.h
index 856995ebfa..d1d122c49c 100644
--- a/library/cpp/actors/util/rope_cont_deque.h
+++ b/library/cpp/actors/util/rope_cont_deque.h
@@ -1,181 +1,181 @@
-#pragma once
-
-#include <library/cpp/containers/stack_vector/stack_vec.h>
-#include <deque>
-
-namespace NRopeDetails {
-
-template<typename TChunk>
-class TChunkList {
- std::deque<TChunk> Chunks;
-
- static constexpr size_t MaxInplaceItems = 4;
- using TInplace = TStackVec<TChunk, MaxInplaceItems>;
- TInplace Inplace;
-
-private:
- template<typename TChunksIt, typename TInplaceIt, typename TValue>
- struct TIterator {
- TChunksIt ChunksIt;
- TInplaceIt InplaceIt;
-
- TIterator() = default;
-
- TIterator(TChunksIt chunksIt, TInplaceIt inplaceIt)
- : ChunksIt(std::move(chunksIt))
- , InplaceIt(inplaceIt)
- {}
-
- template<typename A, typename B, typename C>
- TIterator(const TIterator<A, B, C>& other)
- : ChunksIt(other.ChunksIt)
- , InplaceIt(other.InplaceIt)
- {}
-
- TIterator(const TIterator&) = default;
- TIterator(TIterator&&) = default;
- TIterator& operator =(const TIterator&) = default;
- TIterator& operator =(TIterator&&) = default;
-
- TValue& operator *() const { return InplaceIt != TInplaceIt() ? *InplaceIt : *ChunksIt; }
- TValue* operator ->() const { return InplaceIt != TInplaceIt() ? &*InplaceIt : &*ChunksIt; }
-
- TIterator& operator ++() {
- if (InplaceIt != TInplaceIt()) {
- ++InplaceIt;
- } else {
- ++ChunksIt;
- }
- return *this;
- }
-
- TIterator& operator --() {
- if (InplaceIt != TInplaceIt()) {
- --InplaceIt;
- } else {
- --ChunksIt;
- }
- return *this;
- }
-
- template<typename A, typename B, typename C>
- bool operator ==(const TIterator<A, B, C>& other) const {
- return ChunksIt == other.ChunksIt && InplaceIt == other.InplaceIt;
- }
-
- template<typename A, typename B, typename C>
- bool operator !=(const TIterator<A, B, C>& other) const {
- return ChunksIt != other.ChunksIt || InplaceIt != other.InplaceIt;
- }
- };
-
-public:
- using iterator = TIterator<typename std::deque<TChunk>::iterator, typename TInplace::iterator, TChunk>;
- using const_iterator = TIterator<typename std::deque<TChunk>::const_iterator, typename TInplace::const_iterator, const TChunk>;
-
-public:
- TChunkList() = default;
- TChunkList(const TChunkList& other) = default;
- TChunkList(TChunkList&& other) = default;
- TChunkList& operator=(const TChunkList& other) = default;
- TChunkList& operator=(TChunkList&& other) = default;
-
- template<typename... TArgs>
- void PutToEnd(TArgs&&... args) {
- InsertBefore(end(), std::forward<TArgs>(args)...);
- }
-
- template<typename... TArgs>
- iterator InsertBefore(iterator pos, TArgs&&... args) {
- if (!Inplace) {
- pos.InplaceIt = Inplace.end();
- }
- if (Chunks.empty() && Inplace.size() < MaxInplaceItems) {
- return {{}, Inplace.emplace(pos.InplaceIt, std::forward<TArgs>(args)...)};
- } else {
- if (Inplace) {
- Y_VERIFY_DEBUG(Chunks.empty());
- for (auto& item : Inplace) {
- Chunks.push_back(std::move(item));
- }
- pos.ChunksIt = pos.InplaceIt - Inplace.begin() + Chunks.begin();
- Inplace.clear();
- }
- return {Chunks.emplace(pos.ChunksIt, std::forward<TArgs>(args)...), {}};
- }
- }
-
- iterator Erase(iterator pos) {
- if (Inplace) {
- return {{}, Inplace.erase(pos.InplaceIt)};
- } else {
- return {Chunks.erase(pos.ChunksIt), {}};
- }
- }
-
- iterator Erase(iterator first, iterator last) {
- if (Inplace) {
- return {{}, Inplace.erase(first.InplaceIt, last.InplaceIt)};
- } else {
- return {Chunks.erase(first.ChunksIt, last.ChunksIt), {}};
- }
- }
-
- void EraseFront() {
- if (Inplace) {
- Inplace.erase(Inplace.begin());
- } else {
- Chunks.pop_front();
- }
- }
-
- void EraseBack() {
- if (Inplace) {
- Inplace.pop_back();
- } else {
- Chunks.pop_back();
- }
- }
-
- iterator Splice(iterator pos, TChunkList& from, iterator first, iterator last) {
- if (!Inplace) {
- pos.InplaceIt = Inplace.end();
- }
- size_t n = 0;
- for (auto it = first; it != last; ++it, ++n)
- {}
- if (Chunks.empty() && Inplace.size() + n <= MaxInplaceItems) {
- if (first.InplaceIt != typename TInplace::iterator()) {
- Inplace.insert(pos.InplaceIt, first.InplaceIt, last.InplaceIt);
- } else {
- Inplace.insert(pos.InplaceIt, first.ChunksIt, last.ChunksIt);
- }
- } else {
- if (Inplace) {
- Y_VERIFY_DEBUG(Chunks.empty());
- for (auto& item : Inplace) {
- Chunks.push_back(std::move(item));
- }
- pos.ChunksIt = pos.InplaceIt - Inplace.begin() + Chunks.begin();
- Inplace.clear();
- }
- if (first.InplaceIt != typename TInplace::iterator()) {
- Chunks.insert(pos.ChunksIt, first.InplaceIt, last.InplaceIt);
- } else {
- Chunks.insert(pos.ChunksIt, first.ChunksIt, last.ChunksIt);
- }
- }
- return from.Erase(first, last);
- }
-
- operator bool() const { return !Inplace.empty() || !Chunks.empty(); }
- TChunk& GetFirstChunk() { return Inplace ? Inplace.front() : Chunks.front(); }
- const TChunk& GetFirstChunk() const { return Inplace ? Inplace.front() : Chunks.front(); }
- TChunk& GetLastChunk() { return Inplace ? Inplace.back() : Chunks.back(); }
- iterator begin() { return {Chunks.begin(), Inplace ? Inplace.begin() : typename TInplace::iterator()}; }
- const_iterator begin() const { return {Chunks.begin(), Inplace ? Inplace.begin() : typename TInplace::const_iterator()}; }
- iterator end() { return {Chunks.end(), Inplace ? Inplace.end() : typename TInplace::iterator()}; }
- const_iterator end() const { return {Chunks.end(), Inplace ? Inplace.end() : typename TInplace::const_iterator()}; }
-};
-
-} // NRopeDetails
+#pragma once
+
+#include <library/cpp/containers/stack_vector/stack_vec.h>
+#include <deque>
+
+namespace NRopeDetails {
+
+template<typename TChunk>
+class TChunkList {
+ std::deque<TChunk> Chunks;
+
+ static constexpr size_t MaxInplaceItems = 4;
+ using TInplace = TStackVec<TChunk, MaxInplaceItems>;
+ TInplace Inplace;
+
+private:
+ template<typename TChunksIt, typename TInplaceIt, typename TValue>
+ struct TIterator {
+ TChunksIt ChunksIt;
+ TInplaceIt InplaceIt;
+
+ TIterator() = default;
+
+ TIterator(TChunksIt chunksIt, TInplaceIt inplaceIt)
+ : ChunksIt(std::move(chunksIt))
+ , InplaceIt(inplaceIt)
+ {}
+
+ template<typename A, typename B, typename C>
+ TIterator(const TIterator<A, B, C>& other)
+ : ChunksIt(other.ChunksIt)
+ , InplaceIt(other.InplaceIt)
+ {}
+
+ TIterator(const TIterator&) = default;
+ TIterator(TIterator&&) = default;
+ TIterator& operator =(const TIterator&) = default;
+ TIterator& operator =(TIterator&&) = default;
+
+ TValue& operator *() const { return InplaceIt != TInplaceIt() ? *InplaceIt : *ChunksIt; }
+ TValue* operator ->() const { return InplaceIt != TInplaceIt() ? &*InplaceIt : &*ChunksIt; }
+
+ TIterator& operator ++() {
+ if (InplaceIt != TInplaceIt()) {
+ ++InplaceIt;
+ } else {
+ ++ChunksIt;
+ }
+ return *this;
+ }
+
+ TIterator& operator --() {
+ if (InplaceIt != TInplaceIt()) {
+ --InplaceIt;
+ } else {
+ --ChunksIt;
+ }
+ return *this;
+ }
+
+ template<typename A, typename B, typename C>
+ bool operator ==(const TIterator<A, B, C>& other) const {
+ return ChunksIt == other.ChunksIt && InplaceIt == other.InplaceIt;
+ }
+
+ template<typename A, typename B, typename C>
+ bool operator !=(const TIterator<A, B, C>& other) const {
+ return ChunksIt != other.ChunksIt || InplaceIt != other.InplaceIt;
+ }
+ };
+
+public:
+ using iterator = TIterator<typename std::deque<TChunk>::iterator, typename TInplace::iterator, TChunk>;
+ using const_iterator = TIterator<typename std::deque<TChunk>::const_iterator, typename TInplace::const_iterator, const TChunk>;
+
+public:
+ TChunkList() = default;
+ TChunkList(const TChunkList& other) = default;
+ TChunkList(TChunkList&& other) = default;
+ TChunkList& operator=(const TChunkList& other) = default;
+ TChunkList& operator=(TChunkList&& other) = default;
+
+ template<typename... TArgs>
+ void PutToEnd(TArgs&&... args) {
+ InsertBefore(end(), std::forward<TArgs>(args)...);
+ }
+
+ template<typename... TArgs>
+ iterator InsertBefore(iterator pos, TArgs&&... args) {
+ if (!Inplace) {
+ pos.InplaceIt = Inplace.end();
+ }
+ if (Chunks.empty() && Inplace.size() < MaxInplaceItems) {
+ return {{}, Inplace.emplace(pos.InplaceIt, std::forward<TArgs>(args)...)};
+ } else {
+ if (Inplace) {
+ Y_VERIFY_DEBUG(Chunks.empty());
+ for (auto& item : Inplace) {
+ Chunks.push_back(std::move(item));
+ }
+ pos.ChunksIt = pos.InplaceIt - Inplace.begin() + Chunks.begin();
+ Inplace.clear();
+ }
+ return {Chunks.emplace(pos.ChunksIt, std::forward<TArgs>(args)...), {}};
+ }
+ }
+
+ iterator Erase(iterator pos) {
+ if (Inplace) {
+ return {{}, Inplace.erase(pos.InplaceIt)};
+ } else {
+ return {Chunks.erase(pos.ChunksIt), {}};
+ }
+ }
+
+ iterator Erase(iterator first, iterator last) {
+ if (Inplace) {
+ return {{}, Inplace.erase(first.InplaceIt, last.InplaceIt)};
+ } else {
+ return {Chunks.erase(first.ChunksIt, last.ChunksIt), {}};
+ }
+ }
+
+ void EraseFront() {
+ if (Inplace) {
+ Inplace.erase(Inplace.begin());
+ } else {
+ Chunks.pop_front();
+ }
+ }
+
+ void EraseBack() {
+ if (Inplace) {
+ Inplace.pop_back();
+ } else {
+ Chunks.pop_back();
+ }
+ }
+
+ iterator Splice(iterator pos, TChunkList& from, iterator first, iterator last) {
+ if (!Inplace) {
+ pos.InplaceIt = Inplace.end();
+ }
+ size_t n = 0;
+ for (auto it = first; it != last; ++it, ++n)
+ {}
+ if (Chunks.empty() && Inplace.size() + n <= MaxInplaceItems) {
+ if (first.InplaceIt != typename TInplace::iterator()) {
+ Inplace.insert(pos.InplaceIt, first.InplaceIt, last.InplaceIt);
+ } else {
+ Inplace.insert(pos.InplaceIt, first.ChunksIt, last.ChunksIt);
+ }
+ } else {
+ if (Inplace) {
+ Y_VERIFY_DEBUG(Chunks.empty());
+ for (auto& item : Inplace) {
+ Chunks.push_back(std::move(item));
+ }
+ pos.ChunksIt = pos.InplaceIt - Inplace.begin() + Chunks.begin();
+ Inplace.clear();
+ }
+ if (first.InplaceIt != typename TInplace::iterator()) {
+ Chunks.insert(pos.ChunksIt, first.InplaceIt, last.InplaceIt);
+ } else {
+ Chunks.insert(pos.ChunksIt, first.ChunksIt, last.ChunksIt);
+ }
+ }
+ return from.Erase(first, last);
+ }
+
+ operator bool() const { return !Inplace.empty() || !Chunks.empty(); }
+ TChunk& GetFirstChunk() { return Inplace ? Inplace.front() : Chunks.front(); }
+ const TChunk& GetFirstChunk() const { return Inplace ? Inplace.front() : Chunks.front(); }
+ TChunk& GetLastChunk() { return Inplace ? Inplace.back() : Chunks.back(); }
+ iterator begin() { return {Chunks.begin(), Inplace ? Inplace.begin() : typename TInplace::iterator()}; }
+ const_iterator begin() const { return {Chunks.begin(), Inplace ? Inplace.begin() : typename TInplace::const_iterator()}; }
+ iterator end() { return {Chunks.end(), Inplace ? Inplace.end() : typename TInplace::iterator()}; }
+ const_iterator end() const { return {Chunks.end(), Inplace ? Inplace.end() : typename TInplace::const_iterator()}; }
+};
+
+} // NRopeDetails
diff --git a/library/cpp/actors/util/rope_cont_list.h b/library/cpp/actors/util/rope_cont_list.h
index 7b58089be1..18c136284e 100644
--- a/library/cpp/actors/util/rope_cont_list.h
+++ b/library/cpp/actors/util/rope_cont_list.h
@@ -1,159 +1,159 @@
-#pragma once
-
-#include <util/generic/intrlist.h>
-
-namespace NRopeDetails {
-
-template<typename TChunk>
-class TChunkList {
- struct TItem : TIntrusiveListItem<TItem>, TChunk {
- // delegating constructor
- template<typename... TArgs> TItem(TArgs&&... args) : TChunk(std::forward<TArgs>(args)...) {}
- };
-
- using TList = TIntrusiveList<TItem>;
- TList List;
-
- static constexpr size_t NumInplaceItems = 2;
- char InplaceItems[sizeof(TItem) * NumInplaceItems];
-
- template<typename... TArgs>
- TItem *AllocateItem(TArgs&&... args) {
- for (size_t index = 0; index < NumInplaceItems; ++index) {
- TItem *chunk = GetInplaceItemPtr(index);
- if (!TItem::IsInUse(*chunk)) {
- return new(chunk) TItem(std::forward<TArgs>(args)...);
- }
- }
- return new TItem(std::forward<TArgs>(args)...);
- }
-
- void ReleaseItem(TItem *chunk) {
- if (IsInplaceItem(chunk)) {
- chunk->~TItem();
- TItem::Clear(*chunk);
- } else {
- delete chunk;
- }
- }
-
- void ReleaseItems(TList& list) {
- while (list) {
- ReleaseItem(list.Front());
- }
- }
-
- void Prepare() {
- for (size_t index = 0; index < NumInplaceItems; ++index) {
- TItem::Clear(*GetInplaceItemPtr(index));
- }
- }
-
- TItem *GetInplaceItemPtr(size_t index) { return reinterpret_cast<TItem*>(InplaceItems + index * sizeof(TItem)); }
- bool IsInplaceItem(TItem *chunk) { return chunk >= GetInplaceItemPtr(0) && chunk < GetInplaceItemPtr(NumInplaceItems); }
-
-public:
- using iterator = typename TList::iterator;
- using const_iterator = typename TList::const_iterator;
-
-public:
- TChunkList() {
- Prepare();
- }
-
- ~TChunkList() {
- ReleaseItems(List);
-#ifndef NDEBUG
- for (size_t index = 0; index < NumInplaceItems; ++index) {
- Y_VERIFY(!TItem::IsInUse(*GetInplaceItemPtr(index)));
- }
-#endif
- }
-
- TChunkList(const TChunkList& other) {
- Prepare();
- for (const TItem& chunk : other.List) {
- PutToEnd(TChunk(chunk));
- }
- }
-
- TChunkList(TChunkList&& other) {
- Prepare();
- Splice(end(), other, other.begin(), other.end());
- }
-
- TChunkList& operator=(const TChunkList& other) {
- if (this != &other) {
- ReleaseItems(List);
- for (const TItem& chunk : other.List) {
- PutToEnd(TChunk(chunk));
- }
- }
- return *this;
- }
-
- TChunkList& operator=(TChunkList&& other) {
- if (this != &other) {
- ReleaseItems(List);
- Splice(end(), other, other.begin(), other.end());
- }
- return *this;
- }
-
- template<typename... TArgs>
- void PutToEnd(TArgs&&... args) {
- InsertBefore(end(), std::forward<TArgs>(args)...);
- }
-
- template<typename... TArgs>
- iterator InsertBefore(iterator pos, TArgs&&... args) {
- TItem *item = AllocateItem<TArgs...>(std::forward<TArgs>(args)...);
- item->LinkBefore(pos.Item());
- return item;
- }
-
- iterator Erase(iterator pos) {
- ReleaseItem(&*pos++);
- return pos;
- }
-
- iterator Erase(iterator first, iterator last) {
- TList temp;
- TList::Cut(first, last, temp.end());
- ReleaseItems(temp);
- return last;
- }
-
- void EraseFront() {
- ReleaseItem(List.PopFront());
- }
-
- void EraseBack() {
- ReleaseItem(List.PopBack());
- }
-
- iterator Splice(iterator pos, TChunkList& from, iterator first, iterator last) {
- for (auto it = first; it != last; ) {
- if (from.IsInplaceItem(&*it)) {
- TList::Cut(first, it, pos);
- InsertBefore(pos, std::move(*it));
- it = first = from.Erase(it);
- } else {
- ++it;
- }
- }
- TList::Cut(first, last, pos);
- return last;
- }
-
- operator bool() const { return static_cast<bool>(List); }
- TChunk& GetFirstChunk() { return *List.Front(); }
- const TChunk& GetFirstChunk() const { return *List.Front(); }
- TChunk& GetLastChunk() { return *List.Back(); }
- iterator begin() { return List.begin(); }
- const_iterator begin() const { return List.begin(); }
- iterator end() { return List.end(); }
- const_iterator end() const { return List.end(); }
-};
-
-} // NRopeDetails
+#pragma once
+
+#include <util/generic/intrlist.h>
+
+namespace NRopeDetails {
+
+template<typename TChunk>
+class TChunkList {
+ struct TItem : TIntrusiveListItem<TItem>, TChunk {
+ // delegating constructor
+ template<typename... TArgs> TItem(TArgs&&... args) : TChunk(std::forward<TArgs>(args)...) {}
+ };
+
+ using TList = TIntrusiveList<TItem>;
+ TList List;
+
+ static constexpr size_t NumInplaceItems = 2;
+ char InplaceItems[sizeof(TItem) * NumInplaceItems];
+
+ template<typename... TArgs>
+ TItem *AllocateItem(TArgs&&... args) {
+ for (size_t index = 0; index < NumInplaceItems; ++index) {
+ TItem *chunk = GetInplaceItemPtr(index);
+ if (!TItem::IsInUse(*chunk)) {
+ return new(chunk) TItem(std::forward<TArgs>(args)...);
+ }
+ }
+ return new TItem(std::forward<TArgs>(args)...);
+ }
+
+ void ReleaseItem(TItem *chunk) {
+ if (IsInplaceItem(chunk)) {
+ chunk->~TItem();
+ TItem::Clear(*chunk);
+ } else {
+ delete chunk;
+ }
+ }
+
+ void ReleaseItems(TList& list) {
+ while (list) {
+ ReleaseItem(list.Front());
+ }
+ }
+
+ void Prepare() {
+ for (size_t index = 0; index < NumInplaceItems; ++index) {
+ TItem::Clear(*GetInplaceItemPtr(index));
+ }
+ }
+
+ TItem *GetInplaceItemPtr(size_t index) { return reinterpret_cast<TItem*>(InplaceItems + index * sizeof(TItem)); }
+ bool IsInplaceItem(TItem *chunk) { return chunk >= GetInplaceItemPtr(0) && chunk < GetInplaceItemPtr(NumInplaceItems); }
+
+public:
+ using iterator = typename TList::iterator;
+ using const_iterator = typename TList::const_iterator;
+
+public:
+ TChunkList() {
+ Prepare();
+ }
+
+ ~TChunkList() {
+ ReleaseItems(List);
+#ifndef NDEBUG
+ for (size_t index = 0; index < NumInplaceItems; ++index) {
+ Y_VERIFY(!TItem::IsInUse(*GetInplaceItemPtr(index)));
+ }
+#endif
+ }
+
+ TChunkList(const TChunkList& other) {
+ Prepare();
+ for (const TItem& chunk : other.List) {
+ PutToEnd(TChunk(chunk));
+ }
+ }
+
+ TChunkList(TChunkList&& other) {
+ Prepare();
+ Splice(end(), other, other.begin(), other.end());
+ }
+
+ TChunkList& operator=(const TChunkList& other) {
+ if (this != &other) {
+ ReleaseItems(List);
+ for (const TItem& chunk : other.List) {
+ PutToEnd(TChunk(chunk));
+ }
+ }
+ return *this;
+ }
+
+ TChunkList& operator=(TChunkList&& other) {
+ if (this != &other) {
+ ReleaseItems(List);
+ Splice(end(), other, other.begin(), other.end());
+ }
+ return *this;
+ }
+
+ template<typename... TArgs>
+ void PutToEnd(TArgs&&... args) {
+ InsertBefore(end(), std::forward<TArgs>(args)...);
+ }
+
+ template<typename... TArgs>
+ iterator InsertBefore(iterator pos, TArgs&&... args) {
+ TItem *item = AllocateItem<TArgs...>(std::forward<TArgs>(args)...);
+ item->LinkBefore(pos.Item());
+ return item;
+ }
+
+ iterator Erase(iterator pos) {
+ ReleaseItem(&*pos++);
+ return pos;
+ }
+
+ iterator Erase(iterator first, iterator last) {
+ TList temp;
+ TList::Cut(first, last, temp.end());
+ ReleaseItems(temp);
+ return last;
+ }
+
+ void EraseFront() {
+ ReleaseItem(List.PopFront());
+ }
+
+ void EraseBack() {
+ ReleaseItem(List.PopBack());
+ }
+
+ iterator Splice(iterator pos, TChunkList& from, iterator first, iterator last) {
+ for (auto it = first; it != last; ) {
+ if (from.IsInplaceItem(&*it)) {
+ TList::Cut(first, it, pos);
+ InsertBefore(pos, std::move(*it));
+ it = first = from.Erase(it);
+ } else {
+ ++it;
+ }
+ }
+ TList::Cut(first, last, pos);
+ return last;
+ }
+
+ operator bool() const { return static_cast<bool>(List); }
+ TChunk& GetFirstChunk() { return *List.Front(); }
+ const TChunk& GetFirstChunk() const { return *List.Front(); }
+ TChunk& GetLastChunk() { return *List.Back(); }
+ iterator begin() { return List.begin(); }
+ const_iterator begin() const { return List.begin(); }
+ iterator end() { return List.end(); }
+ const_iterator end() const { return List.end(); }
+};
+
+} // NRopeDetails
diff --git a/library/cpp/actors/util/rope_ut.cpp b/library/cpp/actors/util/rope_ut.cpp
index a6ad078f1c..cabeed9230 100644
--- a/library/cpp/actors/util/rope_ut.cpp
+++ b/library/cpp/actors/util/rope_ut.cpp
@@ -1,231 +1,231 @@
-#include "rope.h"
+#include "rope.h"
#include <library/cpp/testing/unittest/registar.h>
-#include <util/random/random.h>
-
-class TRopeStringBackend : public IRopeChunkBackend {
- TString Buffer;
-
-public:
- TRopeStringBackend(TString buffer)
- : Buffer(std::move(buffer))
- {}
-
- TData GetData() const override {
- return {Buffer.data(), Buffer.size()};
- }
-
- size_t GetCapacity() const override {
- return Buffer.capacity();
- }
-};
-
-TRope CreateRope(TString s, size_t sliceSize) {
- TRope res;
- for (size_t i = 0; i < s.size(); ) {
- size_t len = std::min(sliceSize, s.size() - i);
- if (i % 2) {
- res.Insert(res.End(), TRope(MakeIntrusive<TRopeStringBackend>(s.substr(i, len))));
- } else {
- res.Insert(res.End(), TRope(s.substr(i, len)));
- }
- i += len;
- }
- return res;
-}
-
-TString RopeToString(const TRope& rope) {
- TString res;
- auto iter = rope.Begin();
- while (iter != rope.End()) {
- res.append(iter.ContiguousData(), iter.ContiguousSize());
- iter.AdvanceToNextContiguousBlock();
- }
-
- UNIT_ASSERT_VALUES_EQUAL(rope.GetSize(), res.size());
-
- TString temp = TString::Uninitialized(rope.GetSize());
- rope.Begin().ExtractPlainDataAndAdvance(temp.Detach(), temp.size());
- UNIT_ASSERT_VALUES_EQUAL(temp, res);
-
- return res;
-}
-
-TString Text = "No elements are copied or moved, only the internal pointers of the list nodes are re-pointed.";
-
-Y_UNIT_TEST_SUITE(TRope) {
-
- Y_UNIT_TEST(Leak) {
- const size_t begin = 10, end = 20;
- TRope rope = CreateRope(Text, 10);
- rope.Erase(rope.Begin() + begin, rope.Begin() + end);
- }
-
- Y_UNIT_TEST(BasicRange) {
- TRope rope = CreateRope(Text, 10);
- for (size_t begin = 0; begin < Text.size(); ++begin) {
- for (size_t end = begin; end <= Text.size(); ++end) {
- TRope::TIterator rBegin = rope.Begin() + begin;
- TRope::TIterator rEnd = rope.Begin() + end;
- UNIT_ASSERT_VALUES_EQUAL(RopeToString(TRope(rBegin, rEnd)), Text.substr(begin, end - begin));
- }
- }
- }
-
- Y_UNIT_TEST(Erase) {
- for (size_t begin = 0; begin < Text.size(); ++begin) {
- for (size_t end = begin; end <= Text.size(); ++end) {
- TRope rope = CreateRope(Text, 10);
- rope.Erase(rope.Begin() + begin, rope.Begin() + end);
- TString text = Text;
- text.erase(text.begin() + begin, text.begin() + end);
- UNIT_ASSERT_VALUES_EQUAL(RopeToString(rope), text);
- }
- }
- }
-
- Y_UNIT_TEST(Insert) {
- TRope rope = CreateRope(Text, 10);
- for (size_t begin = 0; begin < Text.size(); ++begin) {
- for (size_t end = begin; end <= Text.size(); ++end) {
- TRope part = TRope(rope.Begin() + begin, rope.Begin() + end);
- for (size_t where = 0; where <= Text.size(); ++where) {
- TRope x(rope);
- x.Insert(x.Begin() + where, TRope(part));
- UNIT_ASSERT_VALUES_EQUAL(x.GetSize(), rope.GetSize() + part.GetSize());
- TString text = Text;
- text.insert(text.begin() + where, Text.begin() + begin, Text.begin() + end);
- UNIT_ASSERT_VALUES_EQUAL(RopeToString(x), text);
- }
- }
- }
- }
-
- Y_UNIT_TEST(Extract) {
- for (size_t begin = 0; begin < Text.size(); ++begin) {
- for (size_t end = begin; end <= Text.size(); ++end) {
- TRope rope = CreateRope(Text, 10);
- TRope part = rope.Extract(rope.Begin() + begin, rope.Begin() + end);
- TString text = Text;
- text.erase(text.begin() + begin, text.begin() + end);
- UNIT_ASSERT_VALUES_EQUAL(RopeToString(rope), text);
- UNIT_ASSERT_VALUES_EQUAL(RopeToString(part), Text.substr(begin, end - begin));
- }
- }
- }
-
- Y_UNIT_TEST(EraseFront) {
- for (size_t pos = 0; pos <= Text.size(); ++pos) {
- TRope rope = CreateRope(Text, 10);
- rope.EraseFront(pos);
- UNIT_ASSERT_VALUES_EQUAL(RopeToString(rope), Text.substr(pos));
- }
- }
-
- Y_UNIT_TEST(EraseBack) {
- for (size_t pos = 0; pos <= Text.size(); ++pos) {
- TRope rope = CreateRope(Text, 10);
- rope.EraseBack(pos);
- UNIT_ASSERT_VALUES_EQUAL(RopeToString(rope), Text.substr(0, Text.size() - pos));
- }
- }
-
- Y_UNIT_TEST(ExtractFront) {
- for (size_t step = 1; step <= Text.size(); ++step) {
- TRope rope = CreateRope(Text, 10);
- TRope out;
- while (const size_t len = Min(step, rope.GetSize())) {
- rope.ExtractFront(len, &out);
- UNIT_ASSERT(rope.GetSize() + out.GetSize() == Text.size());
- UNIT_ASSERT_VALUES_EQUAL(RopeToString(out), Text.substr(0, out.GetSize()));
- }
- }
- }
-
- Y_UNIT_TEST(ExtractFrontPlain) {
- for (size_t step = 1; step <= Text.size(); ++step) {
- TRope rope = CreateRope(Text, 10);
- TString buffer = Text;
- auto it = rope.Begin();
- size_t remain = rope.GetSize();
- while (const size_t len = Min(step, remain)) {
- TString data = TString::Uninitialized(len);
- it.ExtractPlainDataAndAdvance(data.Detach(), data.size());
- UNIT_ASSERT_VALUES_EQUAL(data, buffer.substr(0, len));
- UNIT_ASSERT_VALUES_EQUAL(RopeToString(TRope(it, rope.End())), buffer.substr(len));
- buffer = buffer.substr(len);
- remain -= len;
- }
- }
- }
-
- Y_UNIT_TEST(FetchFrontPlain) {
- char s[10];
- char *data = s;
- size_t remain = sizeof(s);
- TRope rope = TRope(TString("HELLO"));
- UNIT_ASSERT(!rope.FetchFrontPlain(&data, &remain));
- UNIT_ASSERT(!rope);
- rope.Insert(rope.End(), TRope(TString("WORLD!!!")));
- UNIT_ASSERT(rope.FetchFrontPlain(&data, &remain));
- UNIT_ASSERT(!remain);
- UNIT_ASSERT(rope.GetSize() == 3);
- UNIT_ASSERT_VALUES_EQUAL(rope.ConvertToString(), "!!!");
- UNIT_ASSERT(!strncmp(s, "HELLOWORLD", 10));
- }
-
- Y_UNIT_TEST(Glueing) {
- TRope rope = CreateRope(Text, 10);
- for (size_t begin = 0; begin <= Text.size(); ++begin) {
- for (size_t end = begin; end <= Text.size(); ++end) {
- TString repr = rope.DebugString();
- TRope temp = rope.Extract(rope.Position(begin), rope.Position(end));
- rope.Insert(rope.Position(begin), std::move(temp));
- UNIT_ASSERT_VALUES_EQUAL(repr, rope.DebugString());
- UNIT_ASSERT_VALUES_EQUAL(RopeToString(rope), Text);
- }
- }
- }
-
- Y_UNIT_TEST(IterWalk) {
- TRope rope = CreateRope(Text, 10);
- for (size_t step1 = 0; step1 <= rope.GetSize(); ++step1) {
- for (size_t step2 = 0; step2 <= step1; ++step2) {
- TRope::TConstIterator iter = rope.Begin();
- iter += step1;
- iter -= step2;
- UNIT_ASSERT(iter == rope.Position(step1 - step2));
- }
- }
- }
-
- Y_UNIT_TEST(Compare) {
- auto check = [](const TString& x, const TString& y) {
- const TRope xRope = CreateRope(x, 7);
- const TRope yRope = CreateRope(y, 11);
- UNIT_ASSERT_VALUES_EQUAL(xRope == yRope, x == y);
- UNIT_ASSERT_VALUES_EQUAL(xRope != yRope, x != y);
- UNIT_ASSERT_VALUES_EQUAL(xRope < yRope, x < y);
- UNIT_ASSERT_VALUES_EQUAL(xRope <= yRope, x <= y);
- UNIT_ASSERT_VALUES_EQUAL(xRope > yRope, x > y);
- UNIT_ASSERT_VALUES_EQUAL(xRope >= yRope, x >= y);
- };
-
- TVector<TString> pool;
- for (size_t k = 0; k < 10; ++k) {
- size_t len = RandomNumber<size_t>(100) + 100;
- TString s = TString::Uninitialized(len);
- char *p = s.Detach();
- for (size_t j = 0; j < len; ++j) {
- *p++ = RandomNumber<unsigned char>();
- }
- pool.push_back(std::move(s));
- }
-
- for (const TString& x : pool) {
- for (const TString& y : pool) {
- check(x, y);
- }
- }
- }
-
-}
+#include <util/random/random.h>
+
+class TRopeStringBackend : public IRopeChunkBackend {
+ TString Buffer;
+
+public:
+ TRopeStringBackend(TString buffer)
+ : Buffer(std::move(buffer))
+ {}
+
+ TData GetData() const override {
+ return {Buffer.data(), Buffer.size()};
+ }
+
+ size_t GetCapacity() const override {
+ return Buffer.capacity();
+ }
+};
+
+TRope CreateRope(TString s, size_t sliceSize) {
+ TRope res;
+ for (size_t i = 0; i < s.size(); ) {
+ size_t len = std::min(sliceSize, s.size() - i);
+ if (i % 2) {
+ res.Insert(res.End(), TRope(MakeIntrusive<TRopeStringBackend>(s.substr(i, len))));
+ } else {
+ res.Insert(res.End(), TRope(s.substr(i, len)));
+ }
+ i += len;
+ }
+ return res;
+}
+
+TString RopeToString(const TRope& rope) {
+ TString res;
+ auto iter = rope.Begin();
+ while (iter != rope.End()) {
+ res.append(iter.ContiguousData(), iter.ContiguousSize());
+ iter.AdvanceToNextContiguousBlock();
+ }
+
+ UNIT_ASSERT_VALUES_EQUAL(rope.GetSize(), res.size());
+
+ TString temp = TString::Uninitialized(rope.GetSize());
+ rope.Begin().ExtractPlainDataAndAdvance(temp.Detach(), temp.size());
+ UNIT_ASSERT_VALUES_EQUAL(temp, res);
+
+ return res;
+}
+
+TString Text = "No elements are copied or moved, only the internal pointers of the list nodes are re-pointed.";
+
+Y_UNIT_TEST_SUITE(TRope) {
+
+ Y_UNIT_TEST(Leak) {
+ const size_t begin = 10, end = 20;
+ TRope rope = CreateRope(Text, 10);
+ rope.Erase(rope.Begin() + begin, rope.Begin() + end);
+ }
+
+ Y_UNIT_TEST(BasicRange) {
+ TRope rope = CreateRope(Text, 10);
+ for (size_t begin = 0; begin < Text.size(); ++begin) {
+ for (size_t end = begin; end <= Text.size(); ++end) {
+ TRope::TIterator rBegin = rope.Begin() + begin;
+ TRope::TIterator rEnd = rope.Begin() + end;
+ UNIT_ASSERT_VALUES_EQUAL(RopeToString(TRope(rBegin, rEnd)), Text.substr(begin, end - begin));
+ }
+ }
+ }
+
+ Y_UNIT_TEST(Erase) {
+ for (size_t begin = 0; begin < Text.size(); ++begin) {
+ for (size_t end = begin; end <= Text.size(); ++end) {
+ TRope rope = CreateRope(Text, 10);
+ rope.Erase(rope.Begin() + begin, rope.Begin() + end);
+ TString text = Text;
+ text.erase(text.begin() + begin, text.begin() + end);
+ UNIT_ASSERT_VALUES_EQUAL(RopeToString(rope), text);
+ }
+ }
+ }
+
+ Y_UNIT_TEST(Insert) {
+ TRope rope = CreateRope(Text, 10);
+ for (size_t begin = 0; begin < Text.size(); ++begin) {
+ for (size_t end = begin; end <= Text.size(); ++end) {
+ TRope part = TRope(rope.Begin() + begin, rope.Begin() + end);
+ for (size_t where = 0; where <= Text.size(); ++where) {
+ TRope x(rope);
+ x.Insert(x.Begin() + where, TRope(part));
+ UNIT_ASSERT_VALUES_EQUAL(x.GetSize(), rope.GetSize() + part.GetSize());
+ TString text = Text;
+ text.insert(text.begin() + where, Text.begin() + begin, Text.begin() + end);
+ UNIT_ASSERT_VALUES_EQUAL(RopeToString(x), text);
+ }
+ }
+ }
+ }
+
+ Y_UNIT_TEST(Extract) {
+ for (size_t begin = 0; begin < Text.size(); ++begin) {
+ for (size_t end = begin; end <= Text.size(); ++end) {
+ TRope rope = CreateRope(Text, 10);
+ TRope part = rope.Extract(rope.Begin() + begin, rope.Begin() + end);
+ TString text = Text;
+ text.erase(text.begin() + begin, text.begin() + end);
+ UNIT_ASSERT_VALUES_EQUAL(RopeToString(rope), text);
+ UNIT_ASSERT_VALUES_EQUAL(RopeToString(part), Text.substr(begin, end - begin));
+ }
+ }
+ }
+
+ Y_UNIT_TEST(EraseFront) {
+ for (size_t pos = 0; pos <= Text.size(); ++pos) {
+ TRope rope = CreateRope(Text, 10);
+ rope.EraseFront(pos);
+ UNIT_ASSERT_VALUES_EQUAL(RopeToString(rope), Text.substr(pos));
+ }
+ }
+
+ Y_UNIT_TEST(EraseBack) {
+ for (size_t pos = 0; pos <= Text.size(); ++pos) {
+ TRope rope = CreateRope(Text, 10);
+ rope.EraseBack(pos);
+ UNIT_ASSERT_VALUES_EQUAL(RopeToString(rope), Text.substr(0, Text.size() - pos));
+ }
+ }
+
+ Y_UNIT_TEST(ExtractFront) {
+ for (size_t step = 1; step <= Text.size(); ++step) {
+ TRope rope = CreateRope(Text, 10);
+ TRope out;
+ while (const size_t len = Min(step, rope.GetSize())) {
+ rope.ExtractFront(len, &out);
+ UNIT_ASSERT(rope.GetSize() + out.GetSize() == Text.size());
+ UNIT_ASSERT_VALUES_EQUAL(RopeToString(out), Text.substr(0, out.GetSize()));
+ }
+ }
+ }
+
+ Y_UNIT_TEST(ExtractFrontPlain) {
+ for (size_t step = 1; step <= Text.size(); ++step) {
+ TRope rope = CreateRope(Text, 10);
+ TString buffer = Text;
+ auto it = rope.Begin();
+ size_t remain = rope.GetSize();
+ while (const size_t len = Min(step, remain)) {
+ TString data = TString::Uninitialized(len);
+ it.ExtractPlainDataAndAdvance(data.Detach(), data.size());
+ UNIT_ASSERT_VALUES_EQUAL(data, buffer.substr(0, len));
+ UNIT_ASSERT_VALUES_EQUAL(RopeToString(TRope(it, rope.End())), buffer.substr(len));
+ buffer = buffer.substr(len);
+ remain -= len;
+ }
+ }
+ }
+
+ Y_UNIT_TEST(FetchFrontPlain) {
+ char s[10];
+ char *data = s;
+ size_t remain = sizeof(s);
+ TRope rope = TRope(TString("HELLO"));
+ UNIT_ASSERT(!rope.FetchFrontPlain(&data, &remain));
+ UNIT_ASSERT(!rope);
+ rope.Insert(rope.End(), TRope(TString("WORLD!!!")));
+ UNIT_ASSERT(rope.FetchFrontPlain(&data, &remain));
+ UNIT_ASSERT(!remain);
+ UNIT_ASSERT(rope.GetSize() == 3);
+ UNIT_ASSERT_VALUES_EQUAL(rope.ConvertToString(), "!!!");
+ UNIT_ASSERT(!strncmp(s, "HELLOWORLD", 10));
+ }
+
+ Y_UNIT_TEST(Glueing) {
+ TRope rope = CreateRope(Text, 10);
+ for (size_t begin = 0; begin <= Text.size(); ++begin) {
+ for (size_t end = begin; end <= Text.size(); ++end) {
+ TString repr = rope.DebugString();
+ TRope temp = rope.Extract(rope.Position(begin), rope.Position(end));
+ rope.Insert(rope.Position(begin), std::move(temp));
+ UNIT_ASSERT_VALUES_EQUAL(repr, rope.DebugString());
+ UNIT_ASSERT_VALUES_EQUAL(RopeToString(rope), Text);
+ }
+ }
+ }
+
+ Y_UNIT_TEST(IterWalk) {
+ TRope rope = CreateRope(Text, 10);
+ for (size_t step1 = 0; step1 <= rope.GetSize(); ++step1) {
+ for (size_t step2 = 0; step2 <= step1; ++step2) {
+ TRope::TConstIterator iter = rope.Begin();
+ iter += step1;
+ iter -= step2;
+ UNIT_ASSERT(iter == rope.Position(step1 - step2));
+ }
+ }
+ }
+
+ Y_UNIT_TEST(Compare) {
+ auto check = [](const TString& x, const TString& y) {
+ const TRope xRope = CreateRope(x, 7);
+ const TRope yRope = CreateRope(y, 11);
+ UNIT_ASSERT_VALUES_EQUAL(xRope == yRope, x == y);
+ UNIT_ASSERT_VALUES_EQUAL(xRope != yRope, x != y);
+ UNIT_ASSERT_VALUES_EQUAL(xRope < yRope, x < y);
+ UNIT_ASSERT_VALUES_EQUAL(xRope <= yRope, x <= y);
+ UNIT_ASSERT_VALUES_EQUAL(xRope > yRope, x > y);
+ UNIT_ASSERT_VALUES_EQUAL(xRope >= yRope, x >= y);
+ };
+
+ TVector<TString> pool;
+ for (size_t k = 0; k < 10; ++k) {
+ size_t len = RandomNumber<size_t>(100) + 100;
+ TString s = TString::Uninitialized(len);
+ char *p = s.Detach();
+ for (size_t j = 0; j < len; ++j) {
+ *p++ = RandomNumber<unsigned char>();
+ }
+ pool.push_back(std::move(s));
+ }
+
+ for (const TString& x : pool) {
+ for (const TString& y : pool) {
+ check(x, y);
+ }
+ }
+ }
+
+}
diff --git a/library/cpp/actors/util/ut/ya.make b/library/cpp/actors/util/ut/ya.make
index 6e69c4aec3..3b08b77984 100644
--- a/library/cpp/actors/util/ut/ya.make
+++ b/library/cpp/actors/util/ut/ya.make
@@ -1,5 +1,5 @@
UNITTEST_FOR(library/cpp/actors/util)
-
+
IF (WITH_VALGRIND)
TIMEOUT(600)
SIZE(MEDIUM)
@@ -9,10 +9,10 @@ OWNER(
alexvru
g:kikimr
)
-
-SRCS(
- rope_ut.cpp
+
+SRCS(
+ rope_ut.cpp
unordered_cache_ut.cpp
-)
-
-END()
+)
+
+END()
diff --git a/library/cpp/actors/util/ya.make b/library/cpp/actors/util/ya.make
index c258dbf021..37488c3962 100644
--- a/library/cpp/actors/util/ya.make
+++ b/library/cpp/actors/util/ya.make
@@ -11,15 +11,15 @@ SRCS(
cpumask.h
datetime.h
defs.h
- funnel_queue.h
+ funnel_queue.h
futex.h
intrinsics.h
local_process_key.h
named_tuple.h
queue_chunk.h
queue_oneone_inplace.h
- recentwnd.h
- rope.h
+ recentwnd.h
+ rope.h
should_continue.cpp
should_continue.h
thread.h