intermediate changes

ref:cde9a383711a11544ce7e107a78147fb96cc4029

1 files changed, 872 insertions, 0 deletions

diff --git a/util/generic/intrlist.h b/util/generic/intrlist.h
new file mode 100644
index 0000000000..b5d3f2051b
--- /dev/null
+++ b/util/generic/intrlist.h
@@ -0,0 +1,872 @@
+#pragma once
+
+#include "utility.h"
+
+#include <util/system/yassert.h>
+#include <iterator>
+
+struct TIntrusiveListDefaultTag {};
+
+/*
+ * two-way linked list
+ */
+template <class T, class Tag = TIntrusiveListDefaultTag>
+class TIntrusiveListItem {
+private:
+    using TListItem = TIntrusiveListItem<T, Tag>;
+
+public:
+    inline TIntrusiveListItem() noexcept
+        : Next_(this)
+        , Prev_(Next_)
+    {
+    }
+
+    inline ~TIntrusiveListItem() {
+        Unlink();
+    }
+
+public:
+    Y_PURE_FUNCTION inline bool Empty() const noexcept {
+        return (Prev_ == this) && (Next_ == this);
+    }
+
+    inline void Unlink() noexcept {
+        if (Empty()) {
+            return;
+        }
+
+        Prev_->SetNext(Next_);
+        Next_->SetPrev(Prev_);
+
+        SetEnd();
+    }
+
+    inline void LinkBefore(TListItem* before) noexcept {
+        Unlink();
+        LinkBeforeNoUnlink(before);
+    }
+
+    inline void LinkBeforeNoUnlink(TListItem* before) noexcept {
+        TListItem* const after = before->Prev();
+
+        after->SetNext(this);
+        SetPrev(after);
+        SetNext(before);
+        before->SetPrev(this);
+    }
+
+    inline void LinkBefore(TListItem& before) noexcept {
+        LinkBefore(&before);
+    }
+
+    inline void LinkAfter(TListItem* after) noexcept {
+        Unlink();
+        LinkBeforeNoUnlink(after->Next());
+    }
+
+    inline void LinkAfter(TListItem& after) noexcept {
+        LinkAfter(&after);
+    }
+
+public:
+    inline TListItem* Prev() noexcept {
+        return Prev_;
+    }
+
+    inline const TListItem* Prev() const noexcept {
+        return Prev_;
+    }
+
+    inline TListItem* Next() noexcept {
+        return Next_;
+    }
+
+    inline const TListItem* Next() const noexcept {
+        return Next_;
+    }
+
+public:
+    inline void SetEnd() noexcept {
+        Prev_ = this;
+        Next_ = Prev_;
+    }
+
+    inline void SetNext(TListItem* item) noexcept {
+        Next_ = item;
+    }
+
+    inline void SetPrev(TListItem* item) noexcept {
+        Prev_ = item;
+    }
+
+public:
+    inline T* Node() noexcept {
+        return static_cast<T*>(this);
+    }
+
+    inline const T* Node() const noexcept {
+        return static_cast<const T*>(this);
+    }
+
+private:
+    inline TIntrusiveListItem(const TIntrusiveListItem&) = delete;
+    inline TIntrusiveListItem& operator=(const TIntrusiveListItem&) = delete;
+
+private:
+    TListItem* Next_;
+    TListItem* Prev_;
+};
+
+template <class T, class Tag>
+class TIntrusiveList {
+private:
+    using TListItem = TIntrusiveListItem<T, Tag>;
+
+    template <class TListItem, class TNode>
+    class TIteratorBase {
+    public:
+        using TItem = TListItem;
+        using TReference = TNode&;
+        using TPointer = TNode*;
+
+        using iterator_category = std::bidirectional_iterator_tag;
+        using difference_type = ptrdiff_t;
+
+        using value_type = TNode;
+        using reference = TReference;
+        using pointer = TPointer;
+
+        inline TIteratorBase() noexcept
+            : Item_(nullptr)
+        {
+        }
+
+        template <class TListItem_, class TNode_>
+        inline TIteratorBase(const TIteratorBase<TListItem_, TNode_>& right) noexcept
+            : Item_(right.Item())
+        {
+        }
+
+        inline TIteratorBase(TItem* item) noexcept
+            : Item_(item)
+        {
+        }
+
+        inline TItem* Item() const noexcept {
+            return Item_;
+        }
+
+        inline void Next() noexcept {
+            Item_ = Item_->Next();
+        }
+
+        inline void Prev() noexcept {
+            Item_ = Item_->Prev();
+        }
+
+        template <class TListItem_, class TNode_>
+        inline bool operator==(const TIteratorBase<TListItem_, TNode_>& right) const noexcept {
+            return Item() == right.Item();
+        }
+
+        template <class TListItem_, class TNode_>
+        inline bool operator!=(const TIteratorBase<TListItem_, TNode_>& right) const noexcept {
+            return Item() != right.Item();
+        }
+
+        inline TIteratorBase& operator++() noexcept {
+            Next();
+
+            return *this;
+        }
+
+        inline TIteratorBase operator++(int) noexcept {
+            TIteratorBase ret(*this);
+
+            Next();
+
+            return ret;
+        }
+
+        inline TIteratorBase& operator--() noexcept {
+            Prev();
+
+            return *this;
+        }
+
+        inline TIteratorBase operator--(int) noexcept {
+            TIteratorBase ret(*this);
+
+            Prev();
+
+            return ret;
+        }
+
+        inline TReference operator*() const noexcept {
+            return *Item_->Node();
+        }
+
+        inline TPointer operator->() const noexcept {
+            return Item_->Node();
+        }
+
+    private:
+        TItem* Item_;
+    };
+
+    template <class TIterator>
+    class TReverseIteratorBase {
+    public:
+        using TItem = typename TIterator::TItem;
+        using TReference = typename TIterator::TReference;
+        using TPointer = typename TIterator::TPointer;
+
+        using iterator_category = typename TIterator::iterator_category;
+        using difference_type = typename TIterator::difference_type;
+
+        using value_type = typename TIterator::value_type;
+        using reference = typename TIterator::reference;
+        using pointer = typename TIterator::pointer;
+
+        inline TReverseIteratorBase() noexcept = default;
+
+        template <class TIterator_>
+        inline TReverseIteratorBase(const TReverseIteratorBase<TIterator_>& right) noexcept
+            : Current_(right.Base())
+        {
+        }
+
+        inline explicit TReverseIteratorBase(TIterator item) noexcept
+            : Current_(item)
+        {
+        }
+
+        inline TIterator Base() const noexcept {
+            return Current_;
+        }
+
+        inline TItem* Item() const noexcept {
+            TIterator ret = Current_;
+
+            return (--ret).Item();
+        }
+
+        inline void Next() noexcept {
+            Current_.Prev();
+        }
+
+        inline void Prev() noexcept {
+            Current_.Next();
+        }
+
+        template <class TIterator_>
+        inline bool operator==(const TReverseIteratorBase<TIterator_>& right) const noexcept {
+            return Base() == right.Base();
+        }
+
+        template <class TIterator_>
+        inline bool operator!=(const TReverseIteratorBase<TIterator_>& right) const noexcept {
+            return Base() != right.Base();
+        }
+
+        inline TReverseIteratorBase& operator++() noexcept {
+            Next();
+
+            return *this;
+        }
+
+        inline TReverseIteratorBase operator++(int) noexcept {
+            TReverseIteratorBase ret(*this);
+
+            Next();
+
+            return ret;
+        }
+
+        inline TReverseIteratorBase& operator--() noexcept {
+            Prev();
+
+            return *this;
+        }
+
+        inline TReverseIteratorBase operator--(int) noexcept {
+            TReverseIteratorBase ret(*this);
+
+            Prev();
+
+            return ret;
+        }
+
+        inline TReference operator*() const noexcept {
+            TIterator ret = Current_;
+
+            return *--ret;
+        }
+
+        inline TPointer operator->() const noexcept {
+            TIterator ret = Current_;
+
+            return &*--ret;
+        }
+
+    private:
+        TIterator Current_;
+    };
+
+public:
+    using TIterator = TIteratorBase<TListItem, T>;
+    using TConstIterator = TIteratorBase<const TListItem, const T>;
+
+    using TReverseIterator = TReverseIteratorBase<TIterator>;
+    using TConstReverseIterator = TReverseIteratorBase<TConstIterator>;
+
+    using iterator = TIterator;
+    using const_iterator = TConstIterator;
+
+    using reverse_iterator = TReverseIterator;
+    using const_reverse_iterator = TConstReverseIterator;
+
+public:
+    inline void Swap(TIntrusiveList& right) noexcept {
+        TIntrusiveList temp;
+
+        temp.Append(right);
+        Y_ASSERT(right.Empty());
+        right.Append(*this);
+        Y_ASSERT(this->Empty());
+        this->Append(temp);
+        Y_ASSERT(temp.Empty());
+    }
+
+public:
+    inline TIntrusiveList() noexcept = default;
+
+    inline ~TIntrusiveList() = default;
+
+    inline TIntrusiveList(TIntrusiveList&& right) noexcept {
+        this->Swap(right);
+    }
+
+    inline TIntrusiveList& operator=(TIntrusiveList&& rhs) noexcept {
+        this->Swap(rhs);
+        return *this;
+    }
+
+    inline explicit operator bool() const noexcept {
+        return !Empty();
+    }
+
+    Y_PURE_FUNCTION inline bool Empty() const noexcept {
+        return End_.Empty();
+    }
+
+    inline size_t Size() const noexcept {
+        return std::distance(Begin(), End());
+    }
+
+    inline void Remove(TListItem* item) noexcept {
+        item->Unlink();
+    }
+
+    inline void Clear() noexcept {
+        End_.Unlink();
+    }
+
+public:
+    inline TIterator Begin() noexcept {
+        return ++End();
+    }
+
+    inline TIterator End() noexcept {
+        return TIterator(&End_);
+    }
+
+    inline TConstIterator Begin() const noexcept {
+        return ++End();
+    }
+
+    inline TConstIterator End() const noexcept {
+        return TConstIterator(&End_);
+    }
+
+    inline TReverseIterator RBegin() noexcept {
+        return TReverseIterator(End());
+    }
+
+    inline TReverseIterator REnd() noexcept {
+        return TReverseIterator(Begin());
+    }
+
+    inline TConstReverseIterator RBegin() const noexcept {
+        return TConstReverseIterator(End());
+    }
+
+    inline TConstReverseIterator REnd() const noexcept {
+        return TConstReverseIterator(Begin());
+    }
+
+    inline TConstIterator CBegin() const noexcept {
+        return Begin();
+    }
+
+    inline TConstIterator CEnd() const noexcept {
+        return End();
+    }
+
+    inline TConstReverseIterator CRBegin() const noexcept {
+        return RBegin();
+    }
+
+    inline TConstReverseIterator CREnd() const noexcept {
+        return REnd();
+    }
+
+public:
+    inline iterator begin() noexcept {
+        return Begin();
+    }
+
+    inline iterator end() noexcept {
+        return End();
+    }
+
+    inline const_iterator begin() const noexcept {
+        return Begin();
+    }
+
+    inline const_iterator end() const noexcept {
+        return End();
+    }
+
+    inline reverse_iterator rbegin() noexcept {
+        return RBegin();
+    }
+
+    inline reverse_iterator rend() noexcept {
+        return REnd();
+    }
+
+    inline const_iterator cbegin() const noexcept {
+        return CBegin();
+    }
+
+    inline const_iterator cend() const noexcept {
+        return CEnd();
+    }
+
+    inline const_reverse_iterator crbegin() const noexcept {
+        return CRBegin();
+    }
+
+    inline const_reverse_iterator crend() const noexcept {
+        return CREnd();
+    }
+
+public:
+    inline T* Back() noexcept {
+        return End_.Prev()->Node();
+    }
+
+    inline T* Front() noexcept {
+        return End_.Next()->Node();
+    }
+
+    inline const T* Back() const noexcept {
+        return End_.Prev()->Node();
+    }
+
+    inline const T* Front() const noexcept {
+        return End_.Next()->Node();
+    }
+
+    inline void PushBack(TListItem* item) noexcept {
+        item->LinkBefore(End_);
+    }
+
+    inline void PushFront(TListItem* item) noexcept {
+        item->LinkAfter(End_);
+    }
+
+    inline T* PopBack() noexcept {
+        TListItem* const ret = End_.Prev();
+
+        ret->Unlink();
+
+        return ret->Node();
+    }
+
+    inline T* PopFront() noexcept {
+        TListItem* const ret = End_.Next();
+
+        ret->Unlink();
+
+        return ret->Node();
+    }
+
+    inline void Append(TIntrusiveList& list) noexcept {
+        Cut(list.Begin(), list.End(), End());
+    }
+
+    inline static void Cut(TIterator begin, TIterator end, TIterator pasteBefore) noexcept {
+        if (begin == end) {
+            return;
+        }
+
+        TListItem* const cutFront = begin.Item();
+        TListItem* const gapBack = end.Item();
+
+        TListItem* const gapFront = cutFront->Prev();
+        TListItem* const cutBack = gapBack->Prev();
+
+        gapFront->SetNext(gapBack);
+        gapBack->SetPrev(gapFront);
+
+        TListItem* const pasteBack = pasteBefore.Item();
+        TListItem* const pasteFront = pasteBack->Prev();
+
+        pasteFront->SetNext(cutFront);
+        cutFront->SetPrev(pasteFront);
+
+        cutBack->SetNext(pasteBack);
+        pasteBack->SetPrev(cutBack);
+    }
+
+public:
+    template <class TFunctor>
+    inline void ForEach(TFunctor&& functor) {
+        TIterator i = Begin();
+
+        while (i != End()) {
+            functor(&*(i++));
+        }
+    }
+
+    template <class TFunctor>
+    inline void ForEach(TFunctor&& functor) const {
+        TConstIterator i = Begin();
+
+        while (i != End()) {
+            functor(&*(i++));
+        }
+    }
+
+    template <class TComparer>
+    inline void QuickSort(TComparer&& comparer) {
+        if (Begin() == End() || ++Begin() == End()) {
+            return;
+        }
+
+        T* const pivot = PopFront();
+        TIntrusiveList bigger;
+        TIterator i = Begin();
+
+        while (i != End()) {
+            if (comparer(*pivot, *i)) {
+                bigger.PushBack(&*i++);
+            } else {
+                ++i;
+            }
+        }
+
+        this->QuickSort(comparer);
+        bigger.QuickSort(comparer);
+
+        PushBack(pivot);
+        Append(bigger);
+    }
+
+private:
+    inline TIntrusiveList(const TIntrusiveList&) = delete;
+    inline TIntrusiveList& operator=(const TIntrusiveList&) = delete;
+
+private:
+    TListItem End_;
+};
+
+template <class T, class D, class Tag>
+class TIntrusiveListWithAutoDelete: public TIntrusiveList<T, Tag> {
+public:
+    using TIterator = typename TIntrusiveList<T, Tag>::TIterator;
+    using TConstIterator = typename TIntrusiveList<T, Tag>::TConstIterator;
+
+    using TReverseIterator = typename TIntrusiveList<T, Tag>::TReverseIterator;
+    using TConstReverseIterator = typename TIntrusiveList<T, Tag>::TConstReverseIterator;
+
+    using iterator = TIterator;
+    using const_iterator = TConstIterator;
+
+    using reverse_iterator = TReverseIterator;
+    using const_reverse_iterator = TConstReverseIterator;
+
+public:
+    inline TIntrusiveListWithAutoDelete() noexcept = default;
+
+    inline TIntrusiveListWithAutoDelete(TIntrusiveListWithAutoDelete&& right) noexcept
+        : TIntrusiveList<T, Tag>(std::move(right))
+    {
+    }
+
+    inline ~TIntrusiveListWithAutoDelete() {
+        this->Clear();
+    }
+
+    TIntrusiveListWithAutoDelete& operator=(TIntrusiveListWithAutoDelete&& rhs) noexcept {
+        TIntrusiveList<T, Tag>::operator=(std::move(rhs));
+        return *this;
+    }
+
+public:
+    inline void Clear() noexcept {
+        this->ForEach([](auto* item) {
+            D::Destroy(item);
+        });
+    }
+
+    inline static void Cut(TIterator begin, TIterator end) noexcept {
+        TIntrusiveListWithAutoDelete<T, D, Tag> temp;
+        Cut(begin, end, temp.End());
+    }
+
+    inline static void Cut(TIterator begin, TIterator end, TIterator pasteBefore) noexcept {
+        TIntrusiveList<T, Tag>::Cut(begin, end, pasteBefore);
+    }
+};
+
+/*
+ * one-way linked list
+ */
+template <class T, class Tag = TIntrusiveListDefaultTag>
+class TIntrusiveSListItem {
+private:
+    using TListItem = TIntrusiveSListItem<T, Tag>;
+
+public:
+    inline TIntrusiveSListItem() noexcept
+        : Next_(nullptr)
+    {
+    }
+
+    inline ~TIntrusiveSListItem() = default;
+
+    inline bool IsEnd() const noexcept {
+        return Next_ == nullptr;
+    }
+
+    inline TListItem* Next() noexcept {
+        return Next_;
+    }
+
+    inline const TListItem* Next() const noexcept {
+        return Next_;
+    }
+
+    inline void SetNext(TListItem* item) noexcept {
+        Next_ = item;
+    }
+
+public:
+    inline T* Node() noexcept {
+        return static_cast<T*>(this);
+    }
+
+    inline const T* Node() const noexcept {
+        return static_cast<const T*>(this);
+    }
+
+private:
+    TListItem* Next_;
+};
+
+template <class T, class Tag>
+class TIntrusiveSList {
+private:
+    using TListItem = TIntrusiveSListItem<T, Tag>;
+
+public:
+    template <class TListItem, class TNode>
+    class TIteratorBase {
+    public:
+        using TItem = TListItem;
+        using TReference = TNode&;
+        using TPointer = TNode*;
+
+        using difference_type = std::ptrdiff_t;
+        using value_type = TNode;
+        using pointer = TPointer;
+        using reference = TReference;
+        using iterator_category = std::forward_iterator_tag;
+
+        inline TIteratorBase(TListItem* item) noexcept
+            : Item_(item)
+        {
+        }
+
+        inline void Next() noexcept {
+            Item_ = Item_->Next();
+        }
+
+        inline bool operator==(const TIteratorBase& right) const noexcept {
+            return Item_ == right.Item_;
+        }
+
+        inline bool operator!=(const TIteratorBase& right) const noexcept {
+            return Item_ != right.Item_;
+        }
+
+        inline TIteratorBase& operator++() noexcept {
+            Next();
+
+            return *this;
+        }
+
+        inline TIteratorBase operator++(int) noexcept {
+            TIteratorBase ret(*this);
+
+            Next();
+
+            return ret;
+        }
+
+        inline TNode& operator*() noexcept {
+            return *Item_->Node();
+        }
+
+        inline TNode* operator->() noexcept {
+            return Item_->Node();
+        }
+
+    private:
+        TListItem* Item_;
+    };
+
+public:
+    using TIterator = TIteratorBase<TListItem, T>;
+    using TConstIterator = TIteratorBase<const TListItem, const T>;
+
+    using iterator = TIterator;
+    using const_iterator = TConstIterator;
+
+public:
+    inline TIntrusiveSList() noexcept
+        : Begin_(nullptr)
+    {
+    }
+
+    inline void Swap(TIntrusiveSList& right) noexcept {
+        DoSwap(Begin_, right.Begin_);
+    }
+
+    inline explicit operator bool() const noexcept {
+        return !Empty();
+    }
+
+    Y_PURE_FUNCTION inline bool Empty() const noexcept {
+        return Begin_ == nullptr;
+    }
+
+    inline size_t Size() const noexcept {
+        return std::distance(Begin(), End());
+    }
+
+    inline void Clear() noexcept {
+        Begin_ = nullptr;
+    }
+
+    inline TIterator Begin() noexcept {
+        return TIterator(Begin_);
+    }
+
+    inline TIterator End() noexcept {
+        return TIterator(nullptr);
+    }
+
+    inline TConstIterator Begin() const noexcept {
+        return TConstIterator(Begin_);
+    }
+
+    inline TConstIterator End() const noexcept {
+        return TConstIterator(nullptr);
+    }
+
+    inline TConstIterator CBegin() const noexcept {
+        return Begin();
+    }
+
+    inline TConstIterator CEnd() const noexcept {
+        return End();
+    }
+
+    //compat methods
+    inline iterator begin() noexcept {
+        return Begin();
+    }
+
+    inline iterator end() noexcept {
+        return End();
+    }
+
+    inline const_iterator begin() const noexcept {
+        return Begin();
+    }
+
+    inline const_iterator end() const noexcept {
+        return End();
+    }
+
+    inline const_iterator cbegin() const noexcept {
+        return CBegin();
+    }
+
+    inline const_iterator cend() const noexcept {
+        return CEnd();
+    }
+
+    inline T* Front() noexcept {
+        Y_ASSERT(Begin_);
+        return Begin_->Node();
+    }
+
+    inline const T* Front() const noexcept {
+        Y_ASSERT(Begin_);
+        return Begin_->Node();
+    }
+
+    inline void PushFront(TListItem* item) noexcept {
+        item->SetNext(Begin_);
+        Begin_ = item;
+    }
+
+    inline T* PopFront() noexcept {
+        Y_ASSERT(Begin_);
+
+        TListItem* const ret = Begin_;
+        Begin_ = Begin_->Next();
+
+        return ret->Node();
+    }
+
+    inline void Reverse() noexcept {
+        TIntrusiveSList temp;
+
+        while (!Empty()) {
+            temp.PushFront(PopFront());
+        }
+
+        this->Swap(temp);
+    }
+
+    template <class TFunctor>
+    inline void ForEach(TFunctor&& functor) const noexcept(noexcept(functor(std::declval<TListItem>().Node()))) {
+        TListItem* i = Begin_;
+
+        while (i) {
+            TListItem* const next = i->Next();
+            functor(i->Node());
+            i = next;
+        }
+    }
+
+private:
+    TListItem* Begin_;
+};