// SPDX-FileCopyrightText: Copyright 2023 yuzu Emulator Project
// SPDX-License-Identifier: GPL-2.0-or-later
#pragma once
#include "common/common_funcs.h"
#include "common/parent_of_member.h"
namespace Common {
// Forward declare implementation class for Node.
namespace impl {
class IntrusiveListImpl;
}
class IntrusiveListNode {
YUZU_NON_COPYABLE(IntrusiveListNode);
private:
friend class impl::IntrusiveListImpl;
IntrusiveListNode* m_prev;
IntrusiveListNode* m_next;
public:
constexpr IntrusiveListNode() : m_prev(this), m_next(this) {}
constexpr bool IsLinked() const {
return m_next != this;
}
private:
constexpr void LinkPrev(IntrusiveListNode* node) {
// We can't link an already linked node.
ASSERT(!node->IsLinked());
this->SplicePrev(node, node);
}
constexpr void SplicePrev(IntrusiveListNode* first, IntrusiveListNode* last) {
// Splice a range into the list.
auto last_prev = last->m_prev;
first->m_prev = m_prev;
last_prev->m_next = this;
m_prev->m_next = first;
m_prev = last_prev;
}
constexpr void LinkNext(IntrusiveListNode* node) {
// We can't link an already linked node.
ASSERT(!node->IsLinked());
return this->SpliceNext(node, node);
}
constexpr void SpliceNext(IntrusiveListNode* first, IntrusiveListNode* last) {
// Splice a range into the list.
auto last_prev = last->m_prev;
first->m_prev = this;
last_prev->m_next = m_next;
m_next->m_prev = last_prev;
m_next = first;
}
constexpr void Unlink() {
this->Unlink(m_next);
}
constexpr void Unlink(IntrusiveListNode* last) {
// Unlink a node from a next node.
auto last_prev = last->m_prev;
m_prev->m_next = last;
last->m_prev = m_prev;
last_prev->m_next = this;
m_prev = last_prev;
}
constexpr IntrusiveListNode* GetPrev() {
return m_prev;
}
constexpr const IntrusiveListNode* GetPrev() const {
return m_prev;
}
constexpr IntrusiveListNode* GetNext() {
return m_next;
}
constexpr const IntrusiveListNode* GetNext() const {
return m_next;
}
};
// DEPRECATED: static_assert(std::is_literal_type<IntrusiveListNode>::value);
namespace impl {
class IntrusiveListImpl {
YUZU_NON_COPYABLE(IntrusiveListImpl);
private:
IntrusiveListNode m_root_node;
public:
template <bool Const>
class Iterator;
using value_type = IntrusiveListNode;
using size_type = size_t;
using difference_type = ptrdiff_t;
using pointer = value_type*;
using const_pointer = const value_type*;
using reference = value_type&;
using const_reference = const value_type&;
using iterator = Iterator<false>;
using const_iterator = Iterator<true>;
using reverse_iterator = std::reverse_iterator<iterator>;
using const_reverse_iterator = std::reverse_iterator<const_iterator>;
template <bool Const>
class Iterator {
public:
using iterator_category = std::bidirectional_iterator_tag;
using value_type = typename IntrusiveListImpl::value_type;
using difference_type = typename IntrusiveListImpl::difference_type;
using pointer =
std::conditional_t<Const, IntrusiveListImpl::const_pointer, IntrusiveListImpl::pointer>;
using reference = std::conditional_t<Const, IntrusiveListImpl::const_reference,
IntrusiveListImpl::reference>;
private:
pointer m_node;
public:
constexpr explicit Iterator(pointer n) : m_node(n) {}
constexpr bool operator==(const Iterator& rhs) const {
return m_node == rhs.m_node;
}
constexpr pointer operator->() const {
return m_node;
}
constexpr reference operator*() const {
return *m_node;
}
constexpr Iterator& operator++() {
m_node = m_node->m_next;
return *this;
}
constexpr Iterator& operator--() {
m_node = m_node->m_prev;
return *this;
}
constexpr Iterator operator++(int) {
const Iterator it{*this};
++(*this);
return it;
}
constexpr Iterator operator--(int) {
const Iterator it{*this};
--(*this);
return it;
}
constexpr operator Iterator<true>() const {
return Iterator<true>(m_node);
}
constexpr Iterator<false> GetNonConstIterator() const {
return Iterator<false>(const_cast<IntrusiveListImpl::pointer>(m_node));
}
};
public:
constexpr IntrusiveListImpl() : m_root_node() {}
// Iterator accessors.
constexpr iterator begin() {
return iterator(m_root_node.GetNext());
}
constexpr const_iterator begin() const {
return const_iterator(m_root_node.GetNext());
}
constexpr iterator end() {
return iterator(std::addressof(m_root_node));
}
constexpr const_iterator end() const {
return const_iterator(std::addressof(m_root_node));
}
constexpr iterator iterator_to(reference v) {
// Only allow iterator_to for values in lists.
ASSERT(v.IsLinked());
return iterator(std::addressof(v));
}
constexpr const_iterator iterator_to(const_reference v) const {
// Only allow iterator_to for values in lists.
ASSERT(v.IsLinked());
return const_iterator(std::addressof(v));
}
// Content management.
constexpr bool empty() const {
return !m_root_node.IsLinked();
}
constexpr size_type size() const {
return static_cast<size_type>(std::distance(this->begin(), this->end()));
}
constexpr reference back() {
return *m_root_node.GetPrev();
}
constexpr const_reference back() const {
return *m_root_node.GetPrev();
}
constexpr reference front() {
return *m_root_node.GetNext();
}
constexpr const_reference front() const {
return *m_root_node.GetNext();
}
constexpr void push_back(reference node) {
m_root_node.LinkPrev(std::addressof(node));
}
constexpr void push_front(reference node) {
m_root_node.LinkNext(std::addressof(node));
}
constexpr void pop_back() {
m_root_node.GetPrev()->Unlink();
}
constexpr void pop_front() {
m_root_node.GetNext()->Unlink();
}
constexpr iterator insert(const_iterator pos, reference node) {
pos.GetNonConstIterator()->LinkPrev(std::addressof(node));
return iterator(std::addressof(node));
}
constexpr void splice(const_iterator pos, IntrusiveListImpl& o) {
splice_impl(pos, o.begin(), o.end());
}
constexpr void splice(const_iterator pos, IntrusiveListImpl& o, const_iterator first) {
const_iterator last(first);
std::advance(last, 1);
splice_impl(pos, first, last);
}
constexpr void splice(const_iterator pos, IntrusiveListImpl& o, const_iterator first,
const_iterator last) {
splice_impl(pos, first, last);
}
constexpr iterator erase(const_iterator pos) {
if (pos == this->end()) {
return this->end();
}
iterator it(pos.GetNonConstIterator());
(it++)->Unlink();
return it;
}
constexpr void clear() {
while (!this->empty()) {
this->pop_front();
}
}
private:
constexpr void splice_impl(const_iterator _pos, const_iterator _first, const_iterator _last) {
if (_first == _last) {
return;
}
iterator pos(_pos.GetNonConstIterator());
iterator first(_first.GetNonConstIterator());
iterator last(_last.GetNonConstIterator());
first->Unlink(std::addressof(*last));
pos->SplicePrev(std::addressof(*first), std::addressof(*first));
}
};
} // namespace impl
template <class T, class Traits>
class IntrusiveList {
YUZU_NON_COPYABLE(IntrusiveList);
private:
impl::IntrusiveListImpl m_impl;
public:
template <bool Const>
class Iterator;
using value_type = T;
using size_type = size_t;
using difference_type = ptrdiff_t;
using pointer = value_type*;
using const_pointer = const value_type*;
using reference = value_type&;
using const_reference = const value_type&;
using iterator = Iterator<false>;
using const_iterator = Iterator<true>;
using reverse_iterator = std::reverse_iterator<iterator>;
using const_reverse_iterator = std::reverse_iterator<const_iterator>;
template <bool Const>
class Iterator {
public:
friend class Common::IntrusiveList<T, Traits>;
using ImplIterator =
std::conditional_t<Const, Common::impl::IntrusiveListImpl::const_iterator,
Common::impl::IntrusiveListImpl::iterator>;
using iterator_category = std::bidirectional_iterator_tag;
using value_type = typename IntrusiveList::value_type;
using difference_type = typename IntrusiveList::difference_type;
using pointer =
std::conditional_t<Const, IntrusiveList::const_pointer, IntrusiveList::pointer>;
using reference =
std::conditional_t<Const, IntrusiveList::const_reference, IntrusiveList::reference>;
private:
ImplIterator m_iterator;
private:
constexpr explicit Iterator(ImplIterator it) : m_iterator(it) {}
constexpr ImplIterator GetImplIterator() const {
return m_iterator;
}
public:
constexpr bool operator==(const Iterator& rhs) const {
return m_iterator == rhs.m_iterator;
}
constexpr pointer operator->() const {
return std::addressof(Traits::GetParent(*m_iterator));
}
constexpr reference operator*() const {
return Traits::GetParent(*m_iterator);
}
constexpr Iterator& operator++() {
++m_iterator;
return *this;
}
constexpr Iterator& operator--() {
--m_iterator;
return *this;
}
constexpr Iterator operator++(int) {
const Iterator it{*this};
++m_iterator;
return it;
}
constexpr Iterator operator--(int) {
const Iterator it{*this};
--m_iterator;
return it;
}
constexpr operator Iterator<true>() const {
return Iterator<true>(m_iterator);
}
};
private:
static constexpr IntrusiveListNode& GetNode(reference ref) {
return Traits::GetNode(ref);
}
static constexpr IntrusiveListNode const& GetNode(const_reference ref) {
return Traits::GetNode(ref);
}
static constexpr reference GetParent(IntrusiveListNode& node) {
return Traits::GetParent(node);
}
static constexpr const_reference GetParent(IntrusiveListNode const& node) {
return Traits::GetParent(node);
}
public:
constexpr IntrusiveList() : m_impl() {}
// Iterator accessors.
constexpr iterator begin() {
return iterator(m_impl.begin());
}
constexpr const_iterator begin() const {
return const_iterator(m_impl.begin());
}
constexpr iterator end() {
return iterator(m_impl.end());
}
constexpr const_iterator end() const {
return const_iterator(m_impl.end());
}
constexpr const_iterator cbegin() const {
return this->begin();
}
constexpr const_iterator cend() const {
return this->end();
}
constexpr reverse_iterator rbegin() {
return reverse_iterator(this->end());
}
constexpr const_reverse_iterator rbegin() const {
return const_reverse_iterator(this->end());
}
constexpr reverse_iterator rend() {
return reverse_iterator(this->begin());
}
constexpr const_reverse_iterator rend() const {
return const_reverse_iterator(this->begin());
}
constexpr const_reverse_iterator crbegin() const {
return this->rbegin();
}
constexpr const_reverse_iterator crend() const {
return this->rend();
}
constexpr iterator iterator_to(reference v) {
return iterator(m_impl.iterator_to(GetNode(v)));
}
constexpr const_iterator iterator_to(const_reference v) const {
return const_iterator(m_impl.iterator_to(GetNode(v)));
}
// Content management.
constexpr bool empty() const {
return m_impl.empty();
}
constexpr size_type size() const {
return m_impl.size();
}
constexpr reference back() {
return GetParent(m_impl.back());
}
constexpr const_reference back() const {
return GetParent(m_impl.back());
}
constexpr reference front() {
return GetParent(m_impl.front());
}
constexpr const_reference front() const {
return GetParent(m_impl.front());
}
constexpr void push_back(reference ref) {
m_impl.push_back(GetNode(ref));
}
constexpr void push_front(reference ref) {
m_impl.push_front(GetNode(ref));
}
constexpr void pop_back() {
m_impl.pop_back();
}
constexpr void pop_front() {
m_impl.pop_front();
}
constexpr iterator insert(const_iterator pos, reference ref) {
return iterator(m_impl.insert(pos.GetImplIterator(), GetNode(ref)));
}
constexpr void splice(const_iterator pos, IntrusiveList& o) {
m_impl.splice(pos.GetImplIterator(), o.m_impl);
}
constexpr void splice(const_iterator pos, IntrusiveList& o, const_iterator first) {
m_impl.splice(pos.GetImplIterator(), o.m_impl, first.GetImplIterator());
}
constexpr void splice(const_iterator pos, IntrusiveList& o, const_iterator first,
const_iterator last) {
m_impl.splice(pos.GetImplIterator(), o.m_impl, first.GetImplIterator(),
last.GetImplIterator());
}
constexpr iterator erase(const_iterator pos) {
return iterator(m_impl.erase(pos.GetImplIterator()));
}
constexpr void clear() {
m_impl.clear();
}
};
template <auto T, class Derived = Common::impl::GetParentType<T>>
class IntrusiveListMemberTraits;
template <class Parent, IntrusiveListNode Parent::*Member, class Derived>
class IntrusiveListMemberTraits<Member, Derived> {
public:
using ListType = IntrusiveList<Derived, IntrusiveListMemberTraits>;
private:
friend class IntrusiveList<Derived, IntrusiveListMemberTraits>;
static constexpr IntrusiveListNode& GetNode(Derived& parent) {
return parent.*Member;
}
static constexpr IntrusiveListNode const& GetNode(Derived const& parent) {
return parent.*Member;
}
static Derived& GetParent(IntrusiveListNode& node) {
return Common::GetParentReference<Member, Derived>(std::addressof(node));
}
static Derived const& GetParent(IntrusiveListNode const& node) {
return Common::GetParentReference<Member, Derived>(std::addressof(node));
}
};
template <auto T, class Derived = Common::impl::GetParentType<T>>
class IntrusiveListMemberTraitsByNonConstexprOffsetOf;
template <class Parent, IntrusiveListNode Parent::*Member, class Derived>
class IntrusiveListMemberTraitsByNonConstexprOffsetOf<Member, Derived> {
public:
using ListType = IntrusiveList<Derived, IntrusiveListMemberTraitsByNonConstexprOffsetOf>;
private:
friend class IntrusiveList<Derived, IntrusiveListMemberTraitsByNonConstexprOffsetOf>;
static constexpr IntrusiveListNode& GetNode(Derived& parent) {
return parent.*Member;
}
static constexpr IntrusiveListNode const& GetNode(Derived const& parent) {
return parent.*Member;
}
static Derived& GetParent(IntrusiveListNode& node) {
return *reinterpret_cast<Derived*>(reinterpret_cast<char*>(std::addressof(node)) -
GetOffset());
}
static Derived const& GetParent(IntrusiveListNode const& node) {
return *reinterpret_cast<const Derived*>(
reinterpret_cast<const char*>(std::addressof(node)) - GetOffset());
}
static uintptr_t GetOffset() {
return reinterpret_cast<uintptr_t>(std::addressof(reinterpret_cast<Derived*>(0)->*Member));
}
};
template <class Derived>
class IntrusiveListBaseNode : public IntrusiveListNode {};
template <class Derived>
class IntrusiveListBaseTraits {
public:
using ListType = IntrusiveList<Derived, IntrusiveListBaseTraits>;
private:
friend class IntrusiveList<Derived, IntrusiveListBaseTraits>;
static constexpr IntrusiveListNode& GetNode(Derived& parent) {
return static_cast<IntrusiveListNode&>(
static_cast<IntrusiveListBaseNode<Derived>&>(parent));
}
static constexpr IntrusiveListNode const& GetNode(Derived const& parent) {
return static_cast<const IntrusiveListNode&>(
static_cast<const IntrusiveListBaseNode<Derived>&>(parent));
}
static constexpr Derived& GetParent(IntrusiveListNode& node) {
return static_cast<Derived&>(static_cast<IntrusiveListBaseNode<Derived>&>(node));
}
static constexpr Derived const& GetParent(IntrusiveListNode const& node) {
return static_cast<const Derived&>(
static_cast<const IntrusiveListBaseNode<Derived>&>(node));
}
};
} // namespace Common
