Add rope embedded list option

4 files changed, 426 insertions, 188 deletions

diff --git a/library/cpp/actors/util/rope.h b/library/cpp/actors/util/rope.h
index 036e7a4274..c207e8aaf9 100644
--- a/library/cpp/actors/util/rope.h
+++ b/library/cpp/actors/util/rope.h
@@ -8,7 +8,8 @@
 #include <util/system/valgrind.h>
 
 // exactly one of them must be included
-#include "rope_cont_list.h"
+#include "rope_cont_embedded_list.h"
+//#include "rope_cont_list.h"
 //#include "rope_cont_deque.h"
 
 struct IRopeChunkBackend : TThrRefBase {
@@ -114,7 +115,7 @@ class TRope {
             uintptr_t Owner = 0; // lower bits contain type of the owner
 
         public:
-            TBackend() = delete;
+            TBackend() = default;
 
             TBackend(const TBackend& other)
                 : Owner(Clone(other.Owner))
@@ -188,6 +189,10 @@ class TRope {
                 });
             }
 
+            explicit operator bool() const {
+                return Owner;
+            }
+
         private:
             static constexpr uintptr_t TypeMask = (1 << 3) - 1;
             static constexpr uintptr_t ValueMask = ~TypeMask;
@@ -270,6 +275,11 @@ class TRope {
 
         static constexpr struct TSlice {} Slice{};
 
+        TChunk()
+            : Begin(nullptr)
+            , End(nullptr)
+        {}
+
         template<typename T>
         TChunk(T&& backend, const IRopeChunkBackend::TData& data)
             : Backend(std::forward<T>(backend))
@@ -318,14 +328,6 @@ class TRope {
             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();
         }
@@ -382,6 +384,7 @@ private:
         void CheckValid() const {
 #ifndef NDEBUG
             Y_VERIFY(ValidityToken == Rope->GetValidityToken());
+            Y_VERIFY(Iter == Rope->Chain.end() || Iter->Backend);
 #endif
         }
 
@@ -688,22 +691,25 @@ public:
         }
         Size -= num;
         dest->Size += num;
-        TChunkList::iterator it, first = Chain.begin();
+
+        TChunkList::iterator first = Chain.begin();
+
+        if (num >= first->GetSize() && dest->Chain) { // see if we can glue first chunk to the destination rope
+            auto& last = dest->Chain.GetLastChunk();
+            if (last.Backend == first->Backend && last.End == first->Begin) {
+                last.End = first->End;
+                num -= first->GetSize();
+                first = Chain.Erase(first);
+            }
+        }
+
+        TChunkList::iterator it;
         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();
+        first = dest->Chain.Splice(dest->Chain.end(), Chain, first, it);
+
+        if (num) { // still more data to extract
             if (dest->Chain) {
                 auto& last = dest->Chain.GetLastChunk();
                 if (last.Backend == first->Backend && last.End == first->Begin) {
@@ -712,8 +718,8 @@ public:
                     return;
                 }
             }
-            dest->Chain.PutToEnd(TChunk::Slice, it->Begin, it->Begin + num, *it);
-            it->Begin += num;
+            dest->Chain.PutToEnd(TChunk::Slice, first->Begin, first->Begin + num, *first);
+            first->Begin += num;
         }
     }
 
@@ -820,13 +826,14 @@ public:
         Size -= len;
         while (len) {
             auto& chunk = Chain.GetFirstChunk();
+            Y_VERIFY_DEBUG(chunk.Backend);
             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());
+                Chain.EraseFront();
             }
         }
         InvalidateIterators();
diff --git a/library/cpp/actors/util/rope_cont_embedded_list.h b/library/cpp/actors/util/rope_cont_embedded_list.h
new file mode 100644
index 0000000000..94d50d5236
--- /dev/null
+++ b/library/cpp/actors/util/rope_cont_embedded_list.h
@@ -0,0 +1,391 @@
+#pragma once
+
+#include <util/generic/intrlist.h>
+
+#include <util/random/random.h>
+
+namespace NRopeDetails {
+
+template<typename TChunk>
+class TChunkList {
+    struct TItem : TChunk {
+        TItem *Next = nullptr;
+        TItem *Prev = nullptr;
+#ifndef NDEBUG
+        ui64 ValidityToken = RandomNumber<ui64>();
+#endif
+
+        template<typename... TArgs> TItem(TArgs&&... args) : TChunk(std::forward<TArgs>(args)...) {}
+
+        ~TItem() {
+            Invalidate();
+            if (IsInUse()) {
+                Unlink();
+            }
+        }
+
+        void LinkBefore(TItem *item) {
+            Next = item;
+            Prev = item->Prev;
+            Next->Prev = Prev->Next = this;
+        }
+
+        void Unlink() {
+            Next->Prev = Prev;
+            Prev->Next = Next;
+        }
+
+        bool IsInUse() const {
+            return Next != nullptr;
+        }
+
+        void ClearSingleItem() {
+            Y_VERIFY_DEBUG(Next == this && Prev == this);
+            static_cast<TChunk&>(*this) = {};
+            Next = Prev = nullptr;
+        }
+
+        template<typename... TArgs>
+        TItem *PrepareForUse(TArgs&&... args) {
+            Y_VERIFY_DEBUG(!IsInUse());
+            static_cast<TChunk&>(*this) = {std::forward<TArgs>(args)...};
+            Next = Prev = this;
+            Invalidate();
+            return this;
+        }
+
+        static void TransferRange(TItem *insertBefore, TItem *first, TItem *last) { // [first, last] -> insertBefore
+            first->Prev->Next = last->Next;
+            last->Next->Prev = first->Prev;
+            first->Prev = insertBefore->Prev;
+            last->Next = insertBefore;
+            first->Prev->Next = first;
+            last->Next->Prev = last;
+        }
+
+        void Invalidate() {
+#ifndef NDEBUG
+            ValidityToken = RandomNumber<ui64>();
+#endif
+        }
+    };
+
+    // There are three possible states for the list:
+    // 1. It is empty. Next = Prev = nullptr, TChunk is default-constructed.
+    // 2. It contains single item. Next = Prev = &Root, TChunk contains data.
+    // 3. It has more than one item. Next and Prev make up a double-linked list starting with Root item; TChunk contains
+    //    first item.
+    // This container scheme leads to the following properties:
+    // 1. Deleting first item in the list invalidates iterators to the first two items.
+    // 2. Inserting something before the first item also invalidates iterators to the first two items.
+    // This happens because Root is always the first element of the list and when inserting before the Root, we have to
+    // shift original Root element to the allocated item and replace Root with newly inserted value.
+    // This also makes right-to-left traversing more efficient in some cases.
+    TItem Root;
+
+    template<typename... TArgs>
+    TItem *AllocateItem(TArgs&&... args) {
+        return Root.IsInUse()
+            ? new TItem{std::forward<TArgs>(args)...}
+            : Root.PrepareForUse(std::forward<TArgs>(args)...);
+    }
+
+private:
+    template<bool IsConst>
+    class TIterator {
+        friend class TChunkList;
+
+        using TChunkListType = std::conditional_t<IsConst, const TChunkList, TChunkList>;
+        using TItemType = std::conditional_t<IsConst, const TItem, TItem>;
+        using TChunkType = std::conditional_t<IsConst, const TChunk, TChunk>;
+
+        TChunkListType *Cont = nullptr;
+        TItemType *Item = nullptr;
+#ifndef NDEBUG
+        ui64 ValidityToken = 0;
+#endif
+
+    private:
+        TIterator(TChunkListType *cont, TItemType *item)
+            : Cont(cont)
+            , Item(item)
+        {
+            UpdateValidityToken();
+        }
+
+    public:
+        TIterator() = default;
+
+        template<bool OtherIsConst, typename = std::enable_if_t<OtherIsConst <= IsConst>>
+        TIterator(const TIterator<OtherIsConst>& other)
+            : Cont(other.Cont)
+            , Item(other.Item)
+        {
+            UpdateValidityToken();
+        }
+
+        TChunkType& operator *() const {
+            CheckValid();
+            return *Item;
+        }
+
+        TChunkType *operator ->() const {
+            CheckValid();
+            return Item;
+        }
+
+        TIterator& operator++() {
+            CheckValid();
+            Y_VERIFY_DEBUG(Item);
+            Item = Item->Next;
+            if (Item == &Cont->Root) {
+                Item = nullptr; // make it end
+            }
+            UpdateValidityToken();
+            return *this;
+        }
+
+        TIterator operator ++(int) {
+            TIterator res(*this);
+            ++*this;
+            return res;
+        }
+
+        TIterator& operator--() {
+            CheckValid();
+            if (!Item) {
+                Y_VERIFY_DEBUG(*Cont);
+                Item = Cont->Root.Prev;
+            } else {
+                Y_VERIFY_DEBUG(Item != &Cont->Root);
+                Item = Item->Prev;
+            }
+            UpdateValidityToken();
+            return *this;
+        }
+
+        TIterator operator --(int) {
+            TIterator res(*this);
+            --*this;
+            return res;
+        }
+
+        friend bool operator ==(const TIterator& x, const TIterator& y) {
+            Y_VERIFY_DEBUG(x.Cont == y.Cont);
+            x.CheckValid();
+            y.CheckValid();
+            return x.Item == y.Item;
+        }
+
+        friend bool operator !=(const TIterator& x, const TIterator& y) {
+            return !(x == y);
+        }
+
+    private:
+        void CheckValid() const {
+#ifndef NDEBUG
+            Y_VERIFY_DEBUG(ValidityToken == (Item ? Item->ValidityToken : 0));
+            Y_VERIFY_DEBUG(Cont && (Item != &Cont->Root || *Cont));
+#endif
+        }
+
+        void UpdateValidityToken() {
+#ifndef NDEBUG
+            ValidityToken = Item ? Item->ValidityToken : 0;
+#endif
+            CheckValid();
+        }
+    };
+
+public:
+    using iterator = TIterator<false>;
+    using const_iterator = TIterator<true>;
+
+public:
+    TChunkList()
+    {}
+
+    ~TChunkList() {
+        Erase(begin(), end());
+        Y_VERIFY_DEBUG(!*this);
+    }
+
+    TChunkList(const TChunkList& other) {
+        *this = other;
+    }
+
+    TChunkList(TChunkList&& other) {
+        *this = std::move(other);
+    }
+
+    TChunkList& operator=(const TChunkList& other) {
+        if (this != &other) {
+            Erase(begin(), end());
+            for (const TChunk& chunk : other) {
+                PutToEnd(TChunk(chunk));
+            }
+        }
+        return *this;
+    }
+
+    TChunkList& operator=(TChunkList&& other) {
+        if (this != &other) {
+            Erase(begin(), end());
+            Y_VERIFY_DEBUG(!*this);
+            if (other.Root.IsInUse()) { // do we have something to move?
+                Root.PrepareForUse(std::move(static_cast<TChunk&>(other.Root)));
+                if (other.Root.Next != &other.Root) { // does other contain more than one item?
+                    TItem::TransferRange(&Root, other.Root.Next, other.Root.Prev);
+                }
+                other.Root.ClearSingleItem();
+            }
+        }
+        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)...);
+        if (item == &Root) {
+            // this is the first item, we don't do anything about it
+        } else if (pos.Item != &Root) {
+            item->LinkBefore(pos.Item ? pos.Item : &Root);
+        } else {
+            item->LinkBefore(Root.Next);
+            std::swap(static_cast<TChunk&>(*item), static_cast<TChunk&>(Root));
+            item = &Root;
+            Root.Invalidate();
+        }
+        return {this, item};
+    }
+
+    iterator Erase(iterator pos) {
+        Pop(pos);
+        return pos;
+    }
+
+    iterator Erase(iterator first, iterator last) {
+        if (first == last) {
+            return last;
+        }
+        for (;;) {
+            if (last == begin()) {
+                EraseFront();
+                return begin();
+            } else if (--last == first) {
+                return Erase(last);
+            } else {
+                last = Erase(last);
+            }
+        }
+    }
+
+    void EraseFront() {
+        PopFront();
+    }
+
+    void EraseBack() {
+        Y_VERIFY_DEBUG(*this);
+        if (Root.Prev != &Root) {
+            delete Root.Prev;
+        } else {
+            EraseFront();
+        }
+    }
+
+    // Splice moves elements from the 'from' list in the range [first, last) to *this, inserting them before 'pos'. It
+    // returns iterator of the next remaining item in the 'from' list.
+    iterator Splice(iterator pos, TChunkList& from, iterator first, iterator last) {
+        if (first == last) { // the source range is empty
+            return last;
+        }
+
+        const bool fromBegin = first == from.begin();
+        if (fromBegin) { // remember we have to transfer the first item before returning
+            ++first;
+        }
+
+        // 'first' here either equals to 'last' or points to the middle of the 'from' list
+
+        const bool toBegin = pos == begin();
+        if (toBegin && first != last) {
+            // we are inserting item to the begin of the list, so move the first item of the range; it is important here
+            // that 'last' iterator doesn't get invalidated
+            pos = InsertBefore(begin(), from.Pop(first));
+            ++pos;
+        }
+
+        const auto temp = last;
+        if (first != last) {
+            --last; // set 'last' pointing to the actual last element of the source range
+
+            Y_VERIFY_DEBUG(first.Item != &from.Root);
+            Y_VERIFY_DEBUG(pos.Item != &Root);
+
+            TItem* const firstItem = first.Item;
+            TItem* const lastItem = last.Item;
+            TItem* const posItem = pos.Item ? pos.Item : &Root;
+
+            TItem::TransferRange(posItem, firstItem, lastItem);
+
+            // adjust 'pos' to point to the first inserted item
+            pos = {this, firstItem};
+        }
+
+        if (fromBegin) {
+            InsertBefore(toBegin ? begin() : pos, from.PopFront());
+            return from.begin();
+        } else {
+            return temp;
+        }
+    }
+
+    operator bool() const { return Root.IsInUse(); }
+
+    TChunk& GetFirstChunk() { Y_VERIFY_DEBUG(*this); return Root; }
+    const TChunk& GetFirstChunk() const { Y_VERIFY_DEBUG(*this); return Root; }
+    TChunk& GetLastChunk() { Y_VERIFY_DEBUG(*this); return *Root.Prev; }
+
+    iterator begin() { return *this ? iterator(this, &Root) : end(); }
+    const_iterator begin() const { return *this ? const_iterator(this, &Root) : end(); }
+    iterator end() { return {this, nullptr}; }
+    const_iterator end() const { return {this, nullptr}; }
+
+private:
+    TChunk Pop(iterator& pos) {
+        pos.CheckValid();
+        Y_VERIFY_DEBUG(pos.Item);
+
+        if (pos.Item == &Root) {
+            TChunk res = PopFront();
+            pos = begin();
+            return res;
+        } else {
+            Y_VERIFY_DEBUG(pos != end());
+            TItem* const item = pos++.Item;
+            TChunk res = std::move(static_cast<TChunk&>(*item));
+            delete item;
+            return res;
+        }
+    }
+
+    TChunk PopFront() {
+        Y_VERIFY_DEBUG(*this);
+        TChunk res = std::move(static_cast<TChunk&>(Root));
+        if (Root.Next != &Root) {
+            static_cast<TChunk&>(Root) = std::move(static_cast<TChunk&>(*Root.Next));
+            delete Root.Next;
+            Root.Invalidate();
+        } else {
+            Root.ClearSingleItem();
+        }
+        return res;
+    }
+};
+
+} // NRopeDetails
diff --git a/library/cpp/actors/util/rope_cont_list.h b/library/cpp/actors/util/rope_cont_list.h
deleted file mode 100644
index 18c136284e..0000000000
--- a/library/cpp/actors/util/rope_cont_list.h
+++ /dev/null
@@ -1,159 +0,0 @@
-#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..2d39938915 100644
--- a/library/cpp/actors/util/rope_ut.cpp
+++ b/library/cpp/actors/util/rope_ut.cpp
@@ -145,13 +145,12 @@ Y_UNIT_TEST_SUITE(TRope) {
         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());
+                rope.ExtractFrontPlain(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));
+                UNIT_ASSERT_VALUES_EQUAL(RopeToString(rope), buffer.substr(len));
                 buffer = buffer.substr(len);
                 remain -= len;
             }