intrusive.hpp

Go to the documentation of this file.

 
#pragma once
 
#include "condy/detail/utils.hpp"
#include <cassert>
#include <utility>
 
namespace condy {
namespace detail {
 
template <typename M, typename T>
constexpr ptrdiff_t offset_of(M T::*member) noexcept {
    constexpr T *dummy = nullptr;
    return reinterpret_cast<ptrdiff_t>(&(dummy->*member));
}
 
template <typename M, typename T>
T *container_of(M T::*member, M *ptr) noexcept {
    auto offset = offset_of(member);
    // NOLINTNEXTLINE(performance-no-int-to-ptr)
    return reinterpret_cast<T *>(reinterpret_cast<uintptr_t>(ptr) - offset);
}
 
struct SingleLinkEntry {
    SingleLinkEntry *next = nullptr;
};
 
struct DoubleLinkEntry {
    DoubleLinkEntry *next = nullptr;
    DoubleLinkEntry *prev = nullptr;
};
 
class SingleLinkListImpl {
public:
    SingleLinkListImpl() = default;
    SingleLinkListImpl(SingleLinkListImpl &&other) noexcept
        : head_(std::exchange(other.head_, nullptr)),
          tail_(std::exchange(other.tail_, nullptr)) {}
    SingleLinkListImpl &operator=(SingleLinkListImpl &&other) noexcept {
        if (this != &other) {
            assert(empty());
            head_ = std::exchange(other.head_, nullptr);
            tail_ = std::exchange(other.tail_, nullptr);
        }
        return *this;
    }
 
    CONDY_DELETE_COPY(SingleLinkListImpl);
 
    void push_back(SingleLinkEntry *entry) noexcept {
        assert(entry != nullptr);
        assert(entry->next == nullptr);
        if (!head_) {
            head_ = entry;
            tail_ = entry;
        } else {
            tail_->next = entry;
            tail_ = entry;
        }
    }
 
    void push_back(SingleLinkListImpl &other) noexcept {
        if (other.empty()) {
            return;
        }
        if (empty()) {
            head_ = other.head_;
            tail_ = other.tail_;
        } else {
            tail_->next = other.head_;
            tail_ = other.tail_;
        }
        other.head_ = nullptr;
        other.tail_ = nullptr;
    }
 
    bool empty() const noexcept { return head_ == nullptr; }
 
    SingleLinkEntry *pop_front() noexcept {
        if (empty()) {
            return nullptr;
        }
        SingleLinkEntry *entry = head_;
        head_ = head_->next;
        if (!head_) {
            tail_ = nullptr;
        }
        entry->next = nullptr;
        return entry;
    }
 
private:
    SingleLinkEntry *head_ = nullptr;
    SingleLinkEntry *tail_ = nullptr;
};
 
class DoubleLinkListImpl {
public:
    DoubleLinkListImpl() = default;
    DoubleLinkListImpl(DoubleLinkListImpl &&other) noexcept
        : head_(std::exchange(other.head_, nullptr)),
          tail_(std::exchange(other.tail_, nullptr)) {}
    DoubleLinkListImpl &operator=(DoubleLinkListImpl &&other) noexcept {
        if (this != &other) {
            assert(empty());
            head_ = std::exchange(other.head_, nullptr);
            tail_ = std::exchange(other.tail_, nullptr);
        }
        return *this;
    }
 
    CONDY_DELETE_COPY(DoubleLinkListImpl);
 
    void push_back(DoubleLinkEntry *entry) noexcept {
        assert(entry != nullptr);
        assert(entry->next == nullptr && entry->prev == nullptr);
        entry->next = nullptr;
        entry->prev = tail_;
        if (!head_) {
            head_ = entry;
            tail_ = entry;
        } else {
            tail_->next = entry;
            tail_ = entry;
        }
    }
 
    bool empty() const noexcept { return head_ == nullptr; }
 
    DoubleLinkEntry *pop_front() noexcept {
        if (empty()) {
            return nullptr;
        }
        DoubleLinkEntry *entry = head_;
        head_ = head_->next;
        if (head_) {
            head_->prev = nullptr;
        } else {
            tail_ = nullptr;
        }
        entry->next = nullptr;
        entry->prev = nullptr;
        return entry;
    }
 
    bool remove(DoubleLinkEntry *entry) noexcept {
        assert(entry != nullptr);
        if (entry->prev == nullptr && entry->next == nullptr &&
            head_ != entry) {
            return false;
        }
        if (entry->prev) {
            entry->prev->next = entry->next;
        } else {
            assert(head_ == entry);
            head_ = entry->next;
        }
        if (entry->next) {
            entry->next->prev = entry->prev;
        } else {
            assert(tail_ == entry);
            tail_ = entry->prev;
        }
        entry->next = nullptr;
        entry->prev = nullptr;
        return true;
    }
 
private:
    DoubleLinkEntry *head_ = nullptr;
    DoubleLinkEntry *tail_ = nullptr;
};
 
template <typename T, SingleLinkEntry T::*Member> class IntrusiveSingleList {
public:
    void push_back(T *item) noexcept { impl_.push_back(&(item->*Member)); }
 
    void push_back(IntrusiveSingleList other) noexcept {
        impl_.push_back(other.impl_);
    }
 
    bool empty() const noexcept { return impl_.empty(); }
 
    T *pop_front() noexcept {
        SingleLinkEntry *entry = impl_.pop_front();
        return entry ? container_of(Member, entry) : nullptr;
    }
 
private:
    SingleLinkListImpl impl_;
};
 
template <typename T, DoubleLinkEntry T::*Member> class IntrusiveDoubleList {
public:
    void push_back(T *item) noexcept { impl_.push_back(&(item->*Member)); }
 
    bool empty() const noexcept { return impl_.empty(); }
 
    T *pop_front() noexcept {
        DoubleLinkEntry *entry = impl_.pop_front();
        return entry ? container_of(Member, entry) : nullptr;
    }
 
    bool remove(T *item) noexcept { return impl_.remove(&(item->*Member)); }
 
private:
    DoubleLinkListImpl impl_;
};
 
} // namespace detail
} // namespace condy