File Coverage

t/intrusive_chain.cc

Criterion	Covered	Total	%
statement	209	209	100.0
branch	2063	4904	42.0
condition			n/a
subroutine			n/a
pod			n/a
total	2272	5113	44.4

#include "test.h"
#include
#include
#include

using namespace panda;
using std::shared_ptr;
using test::Tracer;

struct MyPtr : IntrusiveChainNode {};

struct MyIPtr : Refcnt, IntrusiveChainNode> {};

struct MySPtr : IntrusiveChainNode> {};

struct MyCustom : IntrusiveChainNode {
    MyCustom () : p(), n() {}

    MyCustom* p;
    MyCustom* n;
};

MyCustom* intrusive_chain_next (MyCustom* n) { return n->n; }
MyCustom* intrusive_chain_prev (MyCustom* n) { return n->p; }

void intrusive_chain_next (MyCustom* n, MyCustom* v) { n->n = v; }
void intrusive_chain_prev (MyCustom* n, MyCustom* v) { n->p = v; }

template
struct Test {
    using IC = IntrusiveChain;
    using CIt = typename IC::const_iterator;

    static void check_content (CIt begin, CIt end) {
        CHECK(begin == end);
    }

    template
    static void check_content (CIt begin, CIt end, const T& v, Args&&... rest) {
        REQUIRE(begin != end);
        CHECK(*begin == v);
        ++begin;
        check_content(begin, end, rest...);
    }

    template
    static void check_content (const IC& list, Args&&... rest) {
        CHECK(list.size() == sizeof...(Args));
        check_content(list.begin(), list.end(), rest...);
    }

    //checks that elements has been properly removed from chain: next/prev properties must be reset
    static void check_removed (const T& v) {
        CHECK(!intrusive_chain_next(v));
        CHECK(!intrusive_chain_prev(v));
    }

    static void test (function ctor) {
        T v[10];
        for (int i = 0; i < 10; ++i) v[i] = ctor();

        SECTION("ctor: empty") {
            IC list;
            check_content(list);
            CHECK(list.empty());
        }

        SECTION("push_back") {
            IC list;
            list.push_back(v[0]);
            check_content(list, v[0]);
            list.push_back(v[1]);
            check_content(list, v[0], v[1]);
        }

        SECTION("push_front") {
            IC list;
            list.push_front(v[0]);
            check_content(list, v[0]);
            list.push_front(v[1]);
            check_content(list, v[1], v[0]);
        }

        SECTION("ctor: initializer list") {
            IC list({v[0], v[1], v[2]});
            check_content(list, v[0], v[1], v[2]);
        }

        SECTION("pop_back") {
            IC list({v[0], v[1], v[2]});
            CHECK(list.pop_back());
            check_content(list, v[0], v[1]);
            check_removed(v[2]);
            CHECK(list.pop_back());
            check_content(list, v[0]);
            check_removed(v[1]);
            CHECK(!list.pop_back());
            check_content(list);
            check_removed(v[0]);
        }

        SECTION("pop_front") {
            IC list({v[0], v[1], v[2]});
            CHECK(list.pop_front());
            check_content(list, v[1], v[2]);
            check_removed(v[0]);
            CHECK(list.pop_front());
            check_content(list, v[2]);
            check_removed(v[1]);
            CHECK(!list.pop_front());
            check_content(list);
            check_removed(v[2]);
        }

        SECTION("insert") {
            IC list;
            auto it = list.insert(list.begin(), v[0]);
            check_content(list, v[0]);
            CHECK(*it == v[0]);

            it = list.insert(list.begin(), v[1]);
            check_content(list, v[1], v[0]);
            CHECK(*it == v[1]);

            it = list.insert(list.end(), v[2]);
            check_content(list, v[1], v[0], v[2]);
            CHECK(*it == v[2]);

            --it;
            it = list.insert(it, v[3]);
            check_content(list, v[1], v[3], v[0], v[2]);
            CHECK(*it == v[3]);

            list.insert(T(), v[4]);
            check_content(list, v[1], v[3], v[0], v[2], v[4]);

            list.insert(v[1], v[5]);
            check_content(list, v[5], v[1], v[3], v[0], v[2], v[4]);

            list.insert(v[3], v[6]);
            check_content(list, v[5], v[1], v[6], v[3], v[0], v[2], v[4]);
        }

        SECTION("erase") {
            IC list({v[0], v[1], v[2], v[3]});

            SECTION("at end") {
                auto it = list.erase(list.end());
                check_content(list, v[0], v[1], v[2], v[3]);
                CHECK(it == list.end());
                list.erase(T());
                check_content(list, v[0], v[1], v[2], v[3]);
            }

            SECTION("from head") {
                auto it = list.erase(list.begin());
                check_content(list, v[1], v[2], v[3]);
                CHECK(*it == v[1]);
                check_removed(v[0]);

                it = list.erase(list.begin());
                check_content(list, v[2], v[3]);
                CHECK(*it == v[2]);
                check_removed(v[1]);

                list.erase(v[2]);
                check_content(list, v[3]);
                check_removed(v[2]);

                list.erase(v[3]);
                check_content(list);
                check_removed(v[3]);
            }

            SECTION("from tail") {
                auto pos = list.end(); --pos;
                auto it = list.erase(pos);
                check_content(list, v[0], v[1], v[2]);
                CHECK(it == list.end());
                check_removed(v[3]);

                pos = list.end(); --pos;
                it = list.erase(pos);
                check_content(list, v[0], v[1]);
                CHECK(it == list.end());
                check_removed(v[2]);

                list.erase(v[1]);
                check_content(list, v[0]);
                check_removed(v[1]);

                list.erase(v[0]);
                check_content(list);
                check_removed(v[0]);
            }

            SECTION("from the middle") {
                auto pos = list.begin(); ++pos; ++pos;
                auto it = list.erase(pos);
                check_content(list, v[0], v[1], v[3]);
                CHECK(*it == v[3]);
                check_removed(v[2]);

                pos = list.begin(); ++pos;
                it = list.erase(pos);
                check_content(list, v[0], v[3]);
                CHECK(*it == v[3]);
                check_removed(v[1]);

                list.push_back(v[4]);
                list.push_back(v[5]);

                list.erase(v[3]);
                check_content(list, v[0], v[4], v[5]);
                check_removed(v[3]);

                list.erase(v[4]);
                check_content(list, v[0], v[5]);
                check_removed(v[4]);
            }
            SECTION("element not in the list") {
                auto it = list.erase(v[4]);
                check_content(list, v[0], v[1], v[2], v[3]);
                CHECK(it == list.end());
            }
        }

        SECTION("clear") {
            IC list({v[0], v[1], v[2]});
            list.clear();
            check_content(list);
            CHECK(list.empty());
            check_removed(v[0]);
            check_removed(v[1]);
            check_removed(v[2]);
        }

        SECTION("front/back") {
            IC list;
            CHECK(list.front() == T());
            CHECK(list.back() == T());
            CHECK(list.size() == 0);

            list.push_back(v[0]);
            CHECK(list.front() == v[0]);
            CHECK(list.back() == v[0]);
            CHECK(list.size() == 1);

            list.push_back(v[1]);
            CHECK(list.front() == v[0]);
            CHECK(list.back() == v[1]);
            CHECK(list.size() == 2);

            list.push_back(v[2]);
            CHECK(list.front() == v[0]);
            CHECK(list.back() == v[2]);
            CHECK(list.size() == 3);
        }

    }
};

TEST_CASE("pointer type", "[intrusive_chain]") {
    std::vector objs;
    Test::test([&]() -> MyPtr* {
        MyPtr* obj = new MyPtr();
        objs.push_back(obj);
        return obj;
    });
    for (auto o : objs) {
        delete o;
    }
}

TEST_CASE("iptr type", "[intrusive_chain]") {
    Test>::test([&]() -> iptr {
        return new MyIPtr();
    });
}

TEST_CASE("shared_ptr type", "[intrusive_chain]") {
    Test>::test([&]() -> shared_ptr {
        return shared_ptr(new MySPtr());
    });
}

TEST_CASE("custom type", "[intrusive_chain]") {
    std::vector objs;
    Test::test([&]() -> MyCustom* {
        MyCustom* obj = new MyCustom();
        objs.push_back(obj);
        return obj;
    });
    for (auto o : objs) {
        delete o;
    }
}