summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--src/common/intrusive_list.h631
1 files changed, 631 insertions, 0 deletions
diff --git a/src/common/intrusive_list.h b/src/common/intrusive_list.h
new file mode 100644
index 000000000..d330dc1c2
--- /dev/null
+++ b/src/common/intrusive_list.h
@@ -0,0 +1,631 @@
+// 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