diff options
author | Alexander Rutkovsky <alexvru@mail.ru> | 2022-02-10 16:47:39 +0300 |
---|---|---|
committer | Daniil Cherednik <dcherednik@yandex-team.ru> | 2022-02-10 16:47:39 +0300 |
commit | f3646f91e0de459836a7800b9ce3e8dc57a2ab3a (patch) | |
tree | 25c1423200152570c1f8307e5b8304b9bc3840c5 /library/cpp/actors/util | |
parent | fccc62e9bfdce9be2fe7e0f23479da3a5512211a (diff) | |
download | ydb-f3646f91e0de459836a7800b9ce3e8dc57a2ab3a.tar.gz |
Restoring authorship annotation for Alexander Rutkovsky <alexvru@mail.ru>. Commit 1 of 2.
Diffstat (limited to 'library/cpp/actors/util')
-rw-r--r-- | library/cpp/actors/util/named_tuple.h | 46 | ||||
-rw-r--r-- | library/cpp/actors/util/rope.h | 2000 | ||||
-rw-r--r-- | library/cpp/actors/util/rope_cont_deque.h | 362 | ||||
-rw-r--r-- | library/cpp/actors/util/rope_cont_list.h | 318 | ||||
-rw-r--r-- | library/cpp/actors/util/rope_ut.cpp | 460 | ||||
-rw-r--r-- | library/cpp/actors/util/ut/ya.make | 14 | ||||
-rw-r--r-- | library/cpp/actors/util/ya.make | 6 |
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 67f185bba8..bd8e7c44b2 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 f5595efbaa..9d3c3896c8 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 d1d122c49c..856995ebfa 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 18c136284e..7b58089be1 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 cabeed9230..a6ad078f1c 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 3b08b77984..6e69c4aec3 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 37488c3962..c258dbf021 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 |