Intrusive List

intrusive_list.hpp

#pragma once

#include <cassert>
#include <iterator>
#include <type_traits>

/**
 * @brief Intrusive list implementation.
 *
 * An intrusive container can hold an unlimited number of instances that are
 * derived from base_hook without a memory allocation.
 *
 * @tparam T List element type, must derive from base_hook.
 */
template <typename T>
class intrusive_list
{
  public:
    template <typename U>
    class iterator_impl;

    using iterator        = iterator_impl<T>;
    using const_iterator  = iterator_impl<const T>;
    using reference       = T&;
    using const_reference = const T&;
    using size_type       = std::size_t;

    class base_hook
    {
        friend intrusive_list<T>;
        friend iterator;
        friend const_iterator;

      public:
        base_hook()  = default;
        ~base_hook() = default;

        base_hook(const base_hook&) = delete;
        base_hook(base_hook&&)      = delete;

        void operator=(const base_hook&) = delete;
        void operator=(base_hook&&) = delete;

      private:
        T* prev_{nullptr};
        T* next_{nullptr};
    };

    template <typename U>
    class iterator_impl
    {
        friend class intrusive_list<T>;

      public:
        // iterator traits
        using difference_type   = std::ptrdiff_t;
        using value_type        = std::remove_const_t<U>;
        using pointer           = value_type*;
        using reference         = value_type&;
        using iterator_category = std::forward_iterator_tag;

        iterator_impl(pointer ptr = nullptr) : ptr_(ptr)
        {
        }

        iterator_impl(const iterator_impl<value_type>& rhs) : ptr_(rhs.operator->())
        {
        }

        iterator_impl& operator=(const iterator_impl<value_type>& rhs)
        {
            ptr_ = rhs.operator->();
            return *this;
        }

        iterator_impl& operator++()
        {
            ptr_ = ptr_->next_;
            return *this;
        }

        iterator_impl operator++(int)
        {
            iterator_impl retval = *this;
            ++(*this);
            return retval;
        }

        bool operator==(iterator_impl other) const
        {
            return ptr_ == other.ptr_;
        }

        bool operator!=(iterator_impl other) const
        {
            return !(*this == other);
        }

        U& operator*() const
        {
            return *ptr_;
        }

        U* operator->() const
        {
            return ptr_;
        }

      private:
        pointer ptr_{nullptr};
    };

    intrusive_list()
    {
    }

    intrusive_list(intrusive_list&& rhs) : first_(rhs.first_), last_(rhs.last_)
    {
        rhs.first_ = rhs.last_ = nullptr;
    }

    intrusive_list& operator=(intrusive_list&& rhs)
    {
        first_ = rhs.first_;
        last_  = rhs.last_;

        rhs.first_ = rhs.last_ = nullptr;
        return *this;
    }

    void push_back(reference value)
    {
        assert(!(bool(first_) xor bool(last_)));
        assert(!value.prev_ && !value.next_);

        value.prev_ = last_;
        value.next_ = nullptr;

        if (!first_) {
            first_ = &value;
            last_  = &value;
        } else {
            last_->next_ = &value;
            last_        = &value;
        }
    }

    void push_front(reference value)
    {
        assert(!(bool(first_) xor bool(last_)));
        assert(!value.prev_ && !value.next_);

        value.prev_ = nullptr;
        value.next_ = first_;

        if (!first_) {
            first_ = &value;
            last_  = &value;
        } else {
            first_->prev_ = &value;
            first_        = &value;
        }
    }

    void pop_back()
    {
        assert(!(bool(first_) xor bool(last_)));

        if (!last_) {
            return;
        } else if (first_ == last_) {
            first_ = last_ = nullptr;
        } else {
            auto value   = last_;
            last_        = last_->prev_;
            last_->next_ = nullptr;
            value->prev_ = nullptr;
        }
    }

    void pop_front()
    {
        assert(!(bool(first_) xor bool(last_)));

        if (!first_) {
            return;
        } else if (first_ == last_) {
            first_ = last_ = nullptr;
        } else {
            auto value    = first_;
            first_        = first_->next_;
            first_->prev_ = nullptr;
            value->next_  = nullptr;
        }
    }

    iterator begin()
    {
        return first_;
    }

    const_iterator cbegin() const
    {
        return first_;
    }

    iterator end()
    {
        return nullptr;
    }

    const_iterator cend() const
    {
        return nullptr;
    }

    size_type size() const
    {
        return std::distance(cbegin(), cend());
    }

    bool empty() const
    {
        return first_ == nullptr;
    }

    /**
     * @brief Inserts the @p value before the position pointed by @p p.
     *
     * Does not affect the validity of iterators and references.
     *
     * @pre @p value must be an lvalue and @p p must be a valid iterator of
     * @c *this.
     *
     * @param p Insertion position.
     * @param value Element to be inserted.
     * @return An iterator to the inserted element.
     */
    iterator insert(const_iterator p, reference value)
    {
        assert(!(bool(first_) xor bool(last_)));
        assert(!value.prev_ && !value.next_);

        if (!first_ || p == end()) {
            push_back(value);
        } else if (p == begin()) {
            push_front(value);
        } else {
            value.next_ = p.ptr_;
            value.prev_ = p.ptr_->prev_;

            p.ptr_->prev_->next_ = &value;
            p.ptr_->prev_        = &value;
        }

        return &value;
    }

    /**
     * @brief Removes the given element from list.
     *
     * The relative order of elements that are not removed is unchanged,
     * and iterators to elements that are not removed remain valid.
     *
     * Removing an element that is not part of the list results in undefined
     * behavior.
     *
     * @pre @p value is an element of list.
     * @post @p value is not part of the list.
     *
     * @param value The element to be removed.
     */
    void remove(reference value)
    {
        assert(!(bool(first_) xor bool(last_)));
        assert(!empty());

        if (first_ == &value) {
            pop_front();
        } else if (last_ == &value) {
            pop_back();
        } else {
            value.prev_->next_ = value.next_;
            value.next_->prev_ = value.prev_;
            value.prev_ = value.next_ = nullptr;
        }
    }

  private:
    T* first_{nullptr};
    T* last_{nullptr};
};

test_intrusive_list.cpp

#define BOOST_TEST_DYN_LINK
#define BOOST_TEST_MAIN
#define BOOST_TEST_MODULE "intrusive_list"

#include <boost/test/unit_test.hpp>

#include <intrusive_list.hpp>

#include <algorithm>

struct element : public intrusive_list<element>::base_hook
{
    element(int _i = 0) : i(_i)
    {
    }

    bool operator==(const element& rhs) const
    {
        return i == rhs.i;
    }

    int i;
};

BOOST_AUTO_TEST_SUITE(intrusive_list_test)

namespace {

struct fixture
{
    intrusive_list<element> list;
};

} // namespace

BOOST_FIXTURE_TEST_CASE(initial_empty, fixture)
{
    BOOST_REQUIRE_EQUAL(list.empty(), true);
    BOOST_REQUIRE_EQUAL(list.size(), 0);
}

BOOST_FIXTURE_TEST_CASE(push_back, fixture)
{
    element e1{1}, e2{2};
    list.push_back(e1);
    BOOST_REQUIRE_EQUAL(list.empty(), false);
    BOOST_REQUIRE_EQUAL(list.size(), 1);

    list.push_back(e2);
    BOOST_REQUIRE_EQUAL(list.size(), 2);
    BOOST_REQUIRE(std::equal(list.cbegin(), list.cend(), std::vector<int>{1, 2}.cbegin()));
}

BOOST_FIXTURE_TEST_CASE(move_assign_op, fixture)
{
    element e1{1};
    list.push_back(e1);
    BOOST_REQUIRE_EQUAL(list.size(), 1);

    intrusive_list<element> list2;
    BOOST_REQUIRE_EQUAL(list2.empty(), true);

    list2 = std::move(list);

    BOOST_REQUIRE_EQUAL(list.empty(), true);
    BOOST_REQUIRE_EQUAL(list2.size(), 1);
}

BOOST_FIXTURE_TEST_CASE(pop_back_empty, fixture)
{
    list.pop_back();
    BOOST_REQUIRE_EQUAL(list.empty(), true);
}

BOOST_FIXTURE_TEST_CASE(pop_back_single, fixture)
{
    element e1;
    list.push_back(e1);
    list.pop_back();
    BOOST_REQUIRE_EQUAL(list.empty(), true);
}

BOOST_FIXTURE_TEST_CASE(pop_back_multiple, fixture)
{
    element e1, e2;
    list.push_back(e1);
    list.push_back(e2);
    list.pop_back();
    BOOST_REQUIRE_EQUAL(list.size(), 1);
}

BOOST_FIXTURE_TEST_CASE(pop_front_empty, fixture)
{
    list.pop_front();
    BOOST_REQUIRE_EQUAL(list.empty(), true);
}

BOOST_FIXTURE_TEST_CASE(pop_front_single, fixture)
{
    element e1;
    list.push_front(e1);
    list.pop_front();
    BOOST_REQUIRE_EQUAL(list.empty(), true);
}

BOOST_FIXTURE_TEST_CASE(pop_front_multiple, fixture)
{
    element e1, e2;
    list.push_front(e1);
    list.push_front(e2);
    list.pop_front();
    BOOST_REQUIRE_EQUAL(list.size(), 1);
}

BOOST_FIXTURE_TEST_CASE(initial_insert, fixture)
{
    element e1;
    auto    it = list.insert(list.begin(), e1);
    BOOST_REQUIRE(it.operator->() == &e1);
    BOOST_REQUIRE_EQUAL(list.size(), 1);
}

BOOST_FIXTURE_TEST_CASE(tail_insert, fixture)
{
    element e1{1}, e2{2};
    list.push_back(e1);
    auto it = list.insert(list.end(), e2);
    BOOST_REQUIRE_EQUAL(list.size(), 2);
    BOOST_REQUIRE(std::equal(list.cbegin(), list.cend(), std::vector<int>{1, 2}.cbegin()));
}

BOOST_FIXTURE_TEST_CASE(head_insert, fixture)
{
    element e1{1}, e2{2};
    list.push_back(e2);
    auto it = list.insert(list.begin(), e1);
    BOOST_REQUIRE_EQUAL(list.size(), 2);
    BOOST_REQUIRE(std::equal(list.cbegin(), list.cend(), std::vector<int>{1, 2}.cbegin()));
}

BOOST_FIXTURE_TEST_CASE(center_insert, fixture)
{
    element e1{1}, e2{2}, e3{3};
    list.push_back(e1);
    list.push_back(e3);

    auto it = list.insert(++list.begin(), e2);
    BOOST_REQUIRE_EQUAL(list.size(), 3);
    BOOST_REQUIRE(std::equal(list.cbegin(), list.cend(), std::vector<int>{1, 2, 3}.cbegin()));
}

BOOST_FIXTURE_TEST_CASE(tail_remove, fixture)
{
    element e1, e2;
    list.push_back(e1);
    list.push_back(e2);

    list.remove(e2);
    BOOST_REQUIRE_EQUAL(list.size(), 1);
    BOOST_REQUIRE(list.begin().operator->() == &e1);
}

BOOST_FIXTURE_TEST_CASE(head_remove, fixture)
{
    element e1, e2;
    list.push_back(e1);
    list.push_back(e2);

    list.remove(e1);
    BOOST_REQUIRE_EQUAL(list.size(), 1);
    BOOST_REQUIRE(list.begin().operator->() == &e2);
}

BOOST_FIXTURE_TEST_CASE(center_remove, fixture)
{
    element e1{1}, e2{2}, e3{3};
    list.push_back(e1);
    list.push_back(e2);
    list.push_back(e3);

    list.remove(e2);
    BOOST_REQUIRE_EQUAL(list.size(), 2);
    BOOST_REQUIRE(std::equal(list.cbegin(), list.cend(), std::vector<int>{1, 3}.cbegin()));
}

BOOST_FIXTURE_TEST_CASE(iterate_empty, fixture)
{
    for (auto& _ : list) {
        BOOST_REQUIRE(false);
    }
}

BOOST_FIXTURE_TEST_CASE(iterate_single, fixture)
{
    element e1;
    list.push_back(e1);
    BOOST_REQUIRE_EQUAL(std::distance(list.begin(), list.end()), 1);
}

BOOST_FIXTURE_TEST_CASE(iterate_multiple, fixture)
{
    element e1, e2, e3;
    list.push_back(e1);
    list.push_back(e2);
    list.push_back(e3);
    BOOST_REQUIRE_EQUAL(std::distance(list.begin(), list.end()), 3);
}

BOOST_FIXTURE_TEST_CASE(find, fixture)
{
    element e1{1}, e2{2}, e3{3};
    list.push_back(e1);
    list.push_back(e2);
    list.push_back(e3);

    auto it = std::find_if(list.cbegin(), list.cend(), [](const auto& e) { return e.i == 2; });
    BOOST_REQUIRE_EQUAL(it->i, 2);
}

BOOST_AUTO_TEST_SUITE_END()