ydb/util/generic/intrlist_ut.cpp

#include "intrlist.h"

#include <library/cpp/testing/unittest/registar.h>

#include <util/stream/output.h>

class TListTest: public TTestBase {
    UNIT_TEST_SUITE(TListTest);
    UNIT_TEST(TestIterate);
    UNIT_TEST(TestRIterate);
    UNIT_TEST(TestForEach);
    UNIT_TEST(TestForEachWithDelete);
    UNIT_TEST(TestSize);
    UNIT_TEST(TestQuickSort);
    UNIT_TEST(TestCut);
    UNIT_TEST(TestAppend);
    UNIT_TEST(TestMoveCtor);
    UNIT_TEST(TestMoveOpEq);
    UNIT_TEST(TestListWithAutoDelete);
    UNIT_TEST(TestListWithAutoDeleteMoveCtor);
    UNIT_TEST(TestListWithAutoDeleteMoveOpEq);
    UNIT_TEST(TestListWithAutoDeleteClear);
    UNIT_TEST(TestSecondTag);
    UNIT_TEST_SUITE_END();

private:
    void TestSize();
    void TestIterate();
    void TestRIterate();
    void TestForEach();
    void TestForEachWithDelete();
    void TestQuickSort();
    void TestCut();
    void TestAppend();
    void TestMoveCtor();
    void TestMoveOpEq();
    void TestListWithAutoDelete();
    void TestListWithAutoDeleteMoveCtor();
    void TestListWithAutoDeleteMoveOpEq();
    void TestListWithAutoDeleteClear();
    void TestSecondTag();
};

UNIT_TEST_SUITE_REGISTRATION(TListTest);

class TInt: public TIntrusiveListItem<TInt> {
public:
    inline TInt(int value) noexcept
        : Value_(value)
    {
    }

    TInt(TInt&& rhs) noexcept
        : Value_(rhs.Value_)
    {
        rhs.Value_ = 0xDEAD;
    }

    TInt& operator=(TInt&& rhs) noexcept {
        Value_ = rhs.Value_;
        rhs.Value_ = 0xBEEF;
        return *this;
    }

    inline operator int&() noexcept {
        return Value_;
    }

    inline operator const int&() const noexcept {
        return Value_;
    }

private:
    int Value_;
};

class TMyList: public TIntrusiveList<TInt> {
public:
    inline TMyList(int count) {
        while (count > 0) {
            PushFront(new TInt(count--));
        }
    }

    // TMyList(const TMyList& rhs) = default;
    TMyList(TMyList&& rhs) noexcept = default;

    // operator=(const TMyList& rhs) = default;
    TMyList& operator=(TMyList&& rhs) noexcept = default;

    inline ~TMyList() {
        while (!Empty()) {
            delete PopBack();
        }
    }
};

struct TIntGreater: private TGreater<int> {
    inline bool operator()(const TInt& l, const TInt& r) const noexcept {
        return TGreater<int>::operator()(l, r);
    }
};

void TListTest::TestQuickSort() {
    TMyList l(1000);
    size_t c = 0;

    l.QuickSort(TIntGreater());

    UNIT_ASSERT_EQUAL(l.Size(), 1000);

    for (TMyList::TIterator it = l.Begin(); it != l.End(); ++it) {
        UNIT_ASSERT_EQUAL(*it, int(1000 - c++));
    }
}

void TListTest::TestSize() {
    TMyList l(1024);

    UNIT_ASSERT_EQUAL(l.Size(), 1024);
}

void TListTest::TestIterate() {
    TMyList l(1000);
    size_t c = 0;

    for (TMyList::TIterator it = l.Begin(); it != l.End(); ++it) {
        ++c;

        UNIT_ASSERT_EQUAL(*it, (int)c);
    }

    UNIT_ASSERT_EQUAL(c, 1000);
}

void TListTest::TestRIterate() {
    TMyList l(1000);
    size_t c = 1000;

    UNIT_ASSERT_EQUAL(l.RBegin(), TMyList::TReverseIterator(l.End()));
    UNIT_ASSERT_EQUAL(l.REnd(), TMyList::TReverseIterator(l.Begin()));

    for (TMyList::TReverseIterator it = l.RBegin(); it != l.REnd(); ++it) {
        UNIT_ASSERT_EQUAL(*it, (int)c--);
    }

    UNIT_ASSERT_EQUAL(c, 0);
}

class TSum {
public:
    inline TSum(size_t& sum)
        : Sum_(sum)
    {
    }

    inline void operator()(const TInt* v) noexcept {
        Sum_ += *v;
    }

private:
    size_t& Sum_;
};

class TSumWithDelete {
public:
    inline TSumWithDelete(size_t& sum)
        : Sum_(sum)
    {
    }

    inline void operator()(TInt* v) noexcept {
        if (*v % 2) {
            Sum_ += *v;
        } else {
            delete v;
        }
    }

private:
    size_t& Sum_;
};

void TListTest::TestForEach() {
    TMyList l(1000);
    size_t sum = 0;
    TSum functor(sum);

    l.ForEach(functor);

    UNIT_ASSERT_EQUAL(sum, 1000 * 1001 / 2);
}

void TListTest::TestForEachWithDelete() {
    TMyList l(1000);
    size_t sum = 0;
    TSumWithDelete functor(sum);

    l.ForEach(functor);

    UNIT_ASSERT_EQUAL(sum, 500 * 500 /*== n * (x + y * (n - 1) / 2), x == 1, y == 2*/);
}

static void CheckIterationAfterCut(const TMyList& l, const TMyList& l2, size_t N, size_t M) {
    size_t c = 0;
    for (TMyList::TConstIterator it = l.Begin(); it != l.End(); ++it) {
        ++c;

        UNIT_ASSERT_EQUAL(*it, (int)c);
    }

    UNIT_ASSERT_EQUAL(c, M);

    for (TMyList::TConstIterator it = l2.Begin(); it != l2.End(); ++it) {
        ++c;

        UNIT_ASSERT_EQUAL(*it, (int)c);
    }

    UNIT_ASSERT_EQUAL(c, N);

    for (TMyList::TConstIterator it = l2.End(); it != l2.Begin(); --c) {
        --it;

        UNIT_ASSERT_EQUAL(*it, (int)c);
    }

    UNIT_ASSERT_EQUAL(c, M);

    for (TMyList::TConstIterator it = l.End(); it != l.Begin(); --c) {
        --it;

        UNIT_ASSERT_EQUAL(*it, (int)c);
    }

    UNIT_ASSERT_EQUAL(c, 0);
}

static void TestCutFront(int N, int M) {
    TMyList l(N);
    TMyList l2(0);

    TMyList::TIterator it = l.Begin();
    for (int i = 0; i < M; ++i) {
        ++it;
    }

    TMyList::Cut(l.Begin(), it, l2.End());
    CheckIterationAfterCut(l2, l, N, M);
}

static void TestCutBack(int N, int M) {
    TMyList l(N);
    TMyList l2(0);

    TMyList::TIterator it = l.Begin();
    for (int i = 0; i < M; ++i) {
        ++it;
    }

    TMyList::Cut(it, l.End(), l2.End());
    CheckIterationAfterCut(l, l2, N, M);
}

void TListTest::TestCut() {
    TestCutFront(1000, 500);
    TestCutBack(1000, 500);
    TestCutFront(1, 0);
    TestCutBack(1, 0);
    TestCutFront(1, 1);
    TestCutBack(1, 1);
    TestCutFront(2, 0);
    TestCutBack(2, 0);
    TestCutFront(2, 1);
    TestCutBack(2, 1);
    TestCutFront(2, 2);
    TestCutBack(2, 2);
}

static void CheckIterationAfterAppend(const TMyList& l, size_t N, size_t M) {
    TMyList::TConstIterator it = l.Begin();

    for (size_t i = 1; i <= N; ++i, ++it) {
        UNIT_ASSERT_EQUAL((int)i, *it);
    }

    for (size_t i = 1; i <= M; ++i, ++it) {
        UNIT_ASSERT_EQUAL((int)i, *it);
    }

    UNIT_ASSERT_EQUAL(it, l.End());
}

static void TestAppend(int N, int M) {
    TMyList l(N);
    TMyList l2(M);
    l.Append(l2);

    UNIT_ASSERT(l2.Empty());
    CheckIterationAfterAppend(l, N, M);
}

void TListTest::TestAppend() {
    ::TestAppend(500, 500);
    ::TestAppend(0, 0);
    ::TestAppend(1, 0);
    ::TestAppend(0, 1);
    ::TestAppend(1, 1);
}

template <typename TListType>
static void CheckList(const TListType& lst) {
    int i = 1;
    for (typename TListType::TConstIterator it = lst.Begin(); it != lst.End(); ++it, ++i) {
        UNIT_ASSERT_EQUAL(*it, i);
    }
}

void TListTest::TestMoveCtor() {
    const int N{42};
    TMyList lst{N};
    UNIT_ASSERT(!lst.Empty());
    UNIT_ASSERT_EQUAL(lst.Size(), N);

    CheckList(lst);
    TMyList nextLst{std::move(lst)};
    UNIT_ASSERT(lst.Empty());
    CheckList(nextLst);
}

void TListTest::TestMoveOpEq() {
    const int N{42};
    TMyList lst{N};
    UNIT_ASSERT(!lst.Empty());
    UNIT_ASSERT_EQUAL(lst.Size(), N);
    CheckList(lst);

    const int M{2};
    TMyList nextLst(M);
    UNIT_ASSERT(!nextLst.Empty());
    UNIT_ASSERT_EQUAL(nextLst.Size(), M);
    CheckList(nextLst);

    nextLst = std::move(lst);
    UNIT_ASSERT(!nextLst.Empty());
    UNIT_ASSERT_EQUAL(nextLst.Size(), N);
    CheckList(nextLst);
}

class TSelfCountingInt: public TIntrusiveListItem<TSelfCountingInt> {
public:
    TSelfCountingInt(int& counter, int value) noexcept
        : Counter_(counter)
        , Value_(value)
    {
        ++Counter_;
    }

    TSelfCountingInt(TSelfCountingInt&& rhs) noexcept
        : Counter_(rhs.Counter_)
        , Value_(rhs.Value_)
    {
        rhs.Value_ = 0xDEAD;
    }

    TSelfCountingInt& operator=(TSelfCountingInt&& rhs) noexcept {
        Value_ = rhs.Value_;
        rhs.Value_ = 0xBEEF;
        return *this;
    }

    ~TSelfCountingInt() noexcept {
        --Counter_;
    }

    inline operator int&() noexcept {
        return Value_;
    }

    inline operator const int&() const noexcept {
        return Value_;
    }

private:
    int& Counter_;
    int Value_;
};

struct TSelfCountingIntDelete {
    static void Destroy(TSelfCountingInt* i) noexcept {
        delete i;
    }
};

void TListTest::TestListWithAutoDelete() {
    using TListType = TIntrusiveListWithAutoDelete<TSelfCountingInt, TSelfCountingIntDelete>;
    int counter{0};
    {
        TListType lst;
        UNIT_ASSERT(lst.Empty());
        lst.PushFront(new TSelfCountingInt(counter, 2));
        UNIT_ASSERT_EQUAL(lst.Size(), 1);
        UNIT_ASSERT_EQUAL(counter, 1);
        lst.PushFront(new TSelfCountingInt(counter, 1));
        UNIT_ASSERT_EQUAL(lst.Size(), 2);
        UNIT_ASSERT_EQUAL(counter, 2);
        CheckList(lst);
    }

    UNIT_ASSERT_EQUAL(counter, 0);
}

void TListTest::TestListWithAutoDeleteMoveCtor() {
    using TListType = TIntrusiveListWithAutoDelete<TSelfCountingInt, TSelfCountingIntDelete>;
    int counter{0};
    {
        TListType lst;
        lst.PushFront(new TSelfCountingInt(counter, 2));
        lst.PushFront(new TSelfCountingInt(counter, 1));
        UNIT_ASSERT_EQUAL(lst.Size(), 2);
        UNIT_ASSERT_EQUAL(counter, 2);
        CheckList(lst);

        TListType nextList(std::move(lst));
        UNIT_ASSERT_EQUAL(nextList.Size(), 2);
        CheckList(nextList);
        UNIT_ASSERT_EQUAL(counter, 2);
    }

    UNIT_ASSERT_EQUAL(counter, 0);
}

void TListTest::TestListWithAutoDeleteMoveOpEq() {
    using TListType = TIntrusiveListWithAutoDelete<TSelfCountingInt, TSelfCountingIntDelete>;
    int counter{0};
    {
        TListType lst;
        lst.PushFront(new TSelfCountingInt(counter, 2));
        lst.PushFront(new TSelfCountingInt(counter, 1));
        UNIT_ASSERT_EQUAL(lst.Size(), 2);
        UNIT_ASSERT_EQUAL(counter, 2);
        CheckList(lst);

        TListType nextList;
        UNIT_ASSERT(nextList.Empty());
        nextList = std::move(lst);
        UNIT_ASSERT_EQUAL(nextList.Size(), 2);
        CheckList(nextList);
        UNIT_ASSERT_EQUAL(counter, 2);
    }

    UNIT_ASSERT_EQUAL(counter, 0);
}

void TListTest::TestListWithAutoDeleteClear() {
    using TListType = TIntrusiveListWithAutoDelete<TSelfCountingInt, TSelfCountingIntDelete>;
    int counter{0};
    {
        TListType lst;
        UNIT_ASSERT(lst.Empty());
        lst.PushFront(new TSelfCountingInt(counter, 2));
        UNIT_ASSERT_EQUAL(lst.Size(), 1);
        UNIT_ASSERT_EQUAL(counter, 1);
        lst.PushFront(new TSelfCountingInt(counter, 1));
        UNIT_ASSERT_EQUAL(lst.Size(), 2);
        UNIT_ASSERT_EQUAL(counter, 2);
        CheckList(lst);

        lst.Clear();
        UNIT_ASSERT(lst.Empty());
        UNIT_ASSERT_EQUAL(counter, 0);
        lst.PushFront(new TSelfCountingInt(counter, 1));
        UNIT_ASSERT_EQUAL(lst.Size(), 1);
    }

    UNIT_ASSERT_EQUAL(counter, 0);
}

struct TSecondTag {};

class TDoubleNode
    : public TInt,
      public TIntrusiveListItem<TDoubleNode, TSecondTag> {
public:
    TDoubleNode(int value) noexcept
        : TInt(value)
    {
    }
};

void TListTest::TestSecondTag() {
    TDoubleNode zero(0), one(1);
    TIntrusiveList<TInt> first;
    TIntrusiveList<TDoubleNode, TSecondTag> second;

    first.PushFront(&zero);
    first.PushFront(&one);
    second.PushBack(&zero);
    second.PushBack(&one);

    UNIT_ASSERT_EQUAL(*first.Front(), 1);
    UNIT_ASSERT_EQUAL(*++first.Begin(), 0);
    UNIT_ASSERT_EQUAL(*first.Back(), 0);

    UNIT_ASSERT_EQUAL(*second.Front(), 0);
    UNIT_ASSERT_EQUAL(*++second.Begin(), 1);
    UNIT_ASSERT_EQUAL(*second.Back(), 1);

    second.Remove(&zero);
    UNIT_ASSERT_EQUAL(*second.Front(), 1);
    UNIT_ASSERT_EQUAL(*first.Back(), 0);
}