summaryrefslogtreecommitdiffstats
path: root/src/common/intrusive_red_black_tree.h
diff options
context:
space:
mode:
Diffstat (limited to 'src/common/intrusive_red_black_tree.h')
-rw-r--r--src/common/intrusive_red_black_tree.h627
1 files changed, 627 insertions, 0 deletions
diff --git a/src/common/intrusive_red_black_tree.h b/src/common/intrusive_red_black_tree.h
new file mode 100644
index 000000000..929b5497e
--- /dev/null
+++ b/src/common/intrusive_red_black_tree.h
@@ -0,0 +1,627 @@
+// Copyright 2021 yuzu Emulator Project
+// Licensed under GPLv2 or any later version
+// Refer to the license.txt file included.
+
+#pragma once
+
+#include "common/parent_of_member.h"
+#include "common/tree.h"
+
+namespace Common {
+
+namespace impl {
+
+class IntrusiveRedBlackTreeImpl;
+
+}
+
+struct IntrusiveRedBlackTreeNode {
+
+private:
+ RB_ENTRY(IntrusiveRedBlackTreeNode) entry{};
+
+ friend class impl::IntrusiveRedBlackTreeImpl;
+
+ template <class, class, class>
+ friend class IntrusiveRedBlackTree;
+
+public:
+ constexpr IntrusiveRedBlackTreeNode() = default;
+};
+
+template <class T, class Traits, class Comparator>
+class IntrusiveRedBlackTree;
+
+namespace impl {
+
+class IntrusiveRedBlackTreeImpl {
+
+private:
+ template <class, class, class>
+ friend class ::Common::IntrusiveRedBlackTree;
+
+private:
+ RB_HEAD(IntrusiveRedBlackTreeRoot, IntrusiveRedBlackTreeNode);
+ using RootType = IntrusiveRedBlackTreeRoot;
+
+private:
+ IntrusiveRedBlackTreeRoot root;
+
+public:
+ template <bool Const>
+ class Iterator;
+
+ using value_type = IntrusiveRedBlackTreeNode;
+ 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>;
+
+ template <bool Const>
+ class Iterator {
+ public:
+ using iterator_category = std::bidirectional_iterator_tag;
+ using value_type = typename IntrusiveRedBlackTreeImpl::value_type;
+ using difference_type = typename IntrusiveRedBlackTreeImpl::difference_type;
+ using pointer = std::conditional_t<Const, IntrusiveRedBlackTreeImpl::const_pointer,
+ IntrusiveRedBlackTreeImpl::pointer>;
+ using reference = std::conditional_t<Const, IntrusiveRedBlackTreeImpl::const_reference,
+ IntrusiveRedBlackTreeImpl::reference>;
+
+ private:
+ pointer node;
+
+ public:
+ explicit Iterator(pointer n) : node(n) {}
+
+ bool operator==(const Iterator& rhs) const {
+ return this->node == rhs.node;
+ }
+
+ bool operator!=(const Iterator& rhs) const {
+ return !(*this == rhs);
+ }
+
+ pointer operator->() const {
+ return this->node;
+ }
+
+ reference operator*() const {
+ return *this->node;
+ }
+
+ Iterator& operator++() {
+ this->node = GetNext(this->node);
+ return *this;
+ }
+
+ Iterator& operator--() {
+ this->node = GetPrev(this->node);
+ return *this;
+ }
+
+ Iterator operator++(int) {
+ const Iterator it{*this};
+ ++(*this);
+ return it;
+ }
+
+ Iterator operator--(int) {
+ const Iterator it{*this};
+ --(*this);
+ return it;
+ }
+
+ operator Iterator<true>() const {
+ return Iterator<true>(this->node);
+ }
+ };
+
+protected:
+ // Generate static implementations for non-comparison operations for IntrusiveRedBlackTreeRoot.
+ RB_GENERATE_WITHOUT_COMPARE_STATIC(IntrusiveRedBlackTreeRoot, IntrusiveRedBlackTreeNode, entry);
+
+private:
+ // Define accessors using RB_* functions.
+ constexpr void InitializeImpl() {
+ RB_INIT(&this->root);
+ }
+
+ bool EmptyImpl() const {
+ return RB_EMPTY(&this->root);
+ }
+
+ IntrusiveRedBlackTreeNode* GetMinImpl() const {
+ return RB_MIN(IntrusiveRedBlackTreeRoot,
+ const_cast<IntrusiveRedBlackTreeRoot*>(&this->root));
+ }
+
+ IntrusiveRedBlackTreeNode* GetMaxImpl() const {
+ return RB_MAX(IntrusiveRedBlackTreeRoot,
+ const_cast<IntrusiveRedBlackTreeRoot*>(&this->root));
+ }
+
+ IntrusiveRedBlackTreeNode* RemoveImpl(IntrusiveRedBlackTreeNode* node) {
+ return RB_REMOVE(IntrusiveRedBlackTreeRoot, &this->root, node);
+ }
+
+public:
+ static IntrusiveRedBlackTreeNode* GetNext(IntrusiveRedBlackTreeNode* node) {
+ return RB_NEXT(IntrusiveRedBlackTreeRoot, nullptr, node);
+ }
+
+ static IntrusiveRedBlackTreeNode* GetPrev(IntrusiveRedBlackTreeNode* node) {
+ return RB_PREV(IntrusiveRedBlackTreeRoot, nullptr, node);
+ }
+
+ static IntrusiveRedBlackTreeNode const* GetNext(const IntrusiveRedBlackTreeNode* node) {
+ return static_cast<const IntrusiveRedBlackTreeNode*>(
+ GetNext(const_cast<IntrusiveRedBlackTreeNode*>(node)));
+ }
+
+ static IntrusiveRedBlackTreeNode const* GetPrev(const IntrusiveRedBlackTreeNode* node) {
+ return static_cast<const IntrusiveRedBlackTreeNode*>(
+ GetPrev(const_cast<IntrusiveRedBlackTreeNode*>(node)));
+ }
+
+public:
+ constexpr IntrusiveRedBlackTreeImpl() : root() {
+ this->InitializeImpl();
+ }
+
+ // Iterator accessors.
+ iterator begin() {
+ return iterator(this->GetMinImpl());
+ }
+
+ const_iterator begin() const {
+ return const_iterator(this->GetMinImpl());
+ }
+
+ iterator end() {
+ return iterator(static_cast<IntrusiveRedBlackTreeNode*>(nullptr));
+ }
+
+ const_iterator end() const {
+ return const_iterator(static_cast<const IntrusiveRedBlackTreeNode*>(nullptr));
+ }
+
+ const_iterator cbegin() const {
+ return this->begin();
+ }
+
+ const_iterator cend() const {
+ return this->end();
+ }
+
+ iterator iterator_to(reference ref) {
+ return iterator(&ref);
+ }
+
+ const_iterator iterator_to(const_reference ref) const {
+ return const_iterator(&ref);
+ }
+
+ // Content management.
+ bool empty() const {
+ return this->EmptyImpl();
+ }
+
+ reference back() {
+ return *this->GetMaxImpl();
+ }
+
+ const_reference back() const {
+ return *this->GetMaxImpl();
+ }
+
+ reference front() {
+ return *this->GetMinImpl();
+ }
+
+ const_reference front() const {
+ return *this->GetMinImpl();
+ }
+
+ iterator erase(iterator it) {
+ auto cur = std::addressof(*it);
+ auto next = GetNext(cur);
+ this->RemoveImpl(cur);
+ return iterator(next);
+ }
+};
+
+} // namespace impl
+
+template <typename T>
+concept HasLightCompareType = requires {
+ { std::is_same<typename T::LightCompareType, void>::value }
+ ->std::convertible_to<bool>;
+};
+
+namespace impl {
+
+template <typename T, typename Default>
+consteval auto* GetLightCompareType() {
+ if constexpr (HasLightCompareType<T>) {
+ return static_cast<typename T::LightCompareType*>(nullptr);
+ } else {
+ return static_cast<Default*>(nullptr);
+ }
+}
+
+} // namespace impl
+
+template <typename T, typename Default>
+using LightCompareType = std::remove_pointer_t<decltype(impl::GetLightCompareType<T, Default>())>;
+
+template <class T, class Traits, class Comparator>
+class IntrusiveRedBlackTree {
+
+public:
+ using ImplType = impl::IntrusiveRedBlackTreeImpl;
+
+private:
+ ImplType impl{};
+
+public:
+ struct IntrusiveRedBlackTreeRootWithCompare : ImplType::IntrusiveRedBlackTreeRoot {};
+
+ template <bool Const>
+ class Iterator;
+
+ using value_type = T;
+ using size_type = size_t;
+ using difference_type = ptrdiff_t;
+ using pointer = T*;
+ using const_pointer = const T*;
+ using reference = T&;
+ using const_reference = const T&;
+ using iterator = Iterator<false>;
+ using const_iterator = Iterator<true>;
+
+ using light_value_type = LightCompareType<Comparator, value_type>;
+ using const_light_pointer = const light_value_type*;
+ using const_light_reference = const light_value_type&;
+
+ template <bool Const>
+ class Iterator {
+ public:
+ friend class IntrusiveRedBlackTree<T, Traits, Comparator>;
+
+ using ImplIterator =
+ std::conditional_t<Const, ImplType::const_iterator, ImplType::iterator>;
+
+ using iterator_category = std::bidirectional_iterator_tag;
+ using value_type = typename IntrusiveRedBlackTree::value_type;
+ using difference_type = typename IntrusiveRedBlackTree::difference_type;
+ using pointer = std::conditional_t<Const, IntrusiveRedBlackTree::const_pointer,
+ IntrusiveRedBlackTree::pointer>;
+ using reference = std::conditional_t<Const, IntrusiveRedBlackTree::const_reference,
+ IntrusiveRedBlackTree::reference>;
+
+ private:
+ ImplIterator iterator;
+
+ private:
+ explicit Iterator(ImplIterator it) : iterator(it) {}
+
+ explicit Iterator(typename std::conditional<Const, ImplType::const_iterator,
+ ImplType::iterator>::type::pointer ptr)
+ : iterator(ptr) {}
+
+ ImplIterator GetImplIterator() const {
+ return this->iterator;
+ }
+
+ public:
+ bool operator==(const Iterator& rhs) const {
+ return this->iterator == rhs.iterator;
+ }
+
+ bool operator!=(const Iterator& rhs) const {
+ return !(*this == rhs);
+ }
+
+ pointer operator->() const {
+ return Traits::GetParent(std::addressof(*this->iterator));
+ }
+
+ reference operator*() const {
+ return *Traits::GetParent(std::addressof(*this->iterator));
+ }
+
+ Iterator& operator++() {
+ ++this->iterator;
+ return *this;
+ }
+
+ Iterator& operator--() {
+ --this->iterator;
+ return *this;
+ }
+
+ Iterator operator++(int) {
+ const Iterator it{*this};
+ ++this->iterator;
+ return it;
+ }
+
+ Iterator operator--(int) {
+ const Iterator it{*this};
+ --this->iterator;
+ return it;
+ }
+
+ operator Iterator<true>() const {
+ return Iterator<true>(this->iterator);
+ }
+ };
+
+private:
+ // Generate static implementations for comparison operations for IntrusiveRedBlackTreeRoot.
+ RB_GENERATE_WITH_COMPARE_STATIC(IntrusiveRedBlackTreeRootWithCompare, IntrusiveRedBlackTreeNode,
+ entry, CompareImpl, LightCompareImpl);
+
+private:
+ static int CompareImpl(const IntrusiveRedBlackTreeNode* lhs,
+ const IntrusiveRedBlackTreeNode* rhs) {
+ return Comparator::Compare(*Traits::GetParent(lhs), *Traits::GetParent(rhs));
+ }
+
+ static int LightCompareImpl(const void* elm, const IntrusiveRedBlackTreeNode* rhs) {
+ return Comparator::Compare(*static_cast<const_light_pointer>(elm), *Traits::GetParent(rhs));
+ }
+
+ // Define accessors using RB_* functions.
+ IntrusiveRedBlackTreeNode* InsertImpl(IntrusiveRedBlackTreeNode* node) {
+ return RB_INSERT(IntrusiveRedBlackTreeRootWithCompare,
+ static_cast<IntrusiveRedBlackTreeRootWithCompare*>(&this->impl.root),
+ node);
+ }
+
+ IntrusiveRedBlackTreeNode* FindImpl(const IntrusiveRedBlackTreeNode* node) const {
+ return RB_FIND(
+ IntrusiveRedBlackTreeRootWithCompare,
+ const_cast<IntrusiveRedBlackTreeRootWithCompare*>(
+ static_cast<const IntrusiveRedBlackTreeRootWithCompare*>(&this->impl.root)),
+ const_cast<IntrusiveRedBlackTreeNode*>(node));
+ }
+
+ IntrusiveRedBlackTreeNode* NFindImpl(const IntrusiveRedBlackTreeNode* node) const {
+ return RB_NFIND(
+ IntrusiveRedBlackTreeRootWithCompare,
+ const_cast<IntrusiveRedBlackTreeRootWithCompare*>(
+ static_cast<const IntrusiveRedBlackTreeRootWithCompare*>(&this->impl.root)),
+ const_cast<IntrusiveRedBlackTreeNode*>(node));
+ }
+
+ IntrusiveRedBlackTreeNode* FindLightImpl(const_light_pointer lelm) const {
+ return RB_FIND_LIGHT(
+ IntrusiveRedBlackTreeRootWithCompare,
+ const_cast<IntrusiveRedBlackTreeRootWithCompare*>(
+ static_cast<const IntrusiveRedBlackTreeRootWithCompare*>(&this->impl.root)),
+ static_cast<const void*>(lelm));
+ }
+
+ IntrusiveRedBlackTreeNode* NFindLightImpl(const_light_pointer lelm) const {
+ return RB_NFIND_LIGHT(
+ IntrusiveRedBlackTreeRootWithCompare,
+ const_cast<IntrusiveRedBlackTreeRootWithCompare*>(
+ static_cast<const IntrusiveRedBlackTreeRootWithCompare*>(&this->impl.root)),
+ static_cast<const void*>(lelm));
+ }
+
+public:
+ constexpr IntrusiveRedBlackTree() = default;
+
+ // Iterator accessors.
+ iterator begin() {
+ return iterator(this->impl.begin());
+ }
+
+ const_iterator begin() const {
+ return const_iterator(this->impl.begin());
+ }
+
+ iterator end() {
+ return iterator(this->impl.end());
+ }
+
+ const_iterator end() const {
+ return const_iterator(this->impl.end());
+ }
+
+ const_iterator cbegin() const {
+ return this->begin();
+ }
+
+ const_iterator cend() const {
+ return this->end();
+ }
+
+ iterator iterator_to(reference ref) {
+ return iterator(this->impl.iterator_to(*Traits::GetNode(std::addressof(ref))));
+ }
+
+ const_iterator iterator_to(const_reference ref) const {
+ return const_iterator(this->impl.iterator_to(*Traits::GetNode(std::addressof(ref))));
+ }
+
+ // Content management.
+ bool empty() const {
+ return this->impl.empty();
+ }
+
+ reference back() {
+ return *Traits::GetParent(std::addressof(this->impl.back()));
+ }
+
+ const_reference back() const {
+ return *Traits::GetParent(std::addressof(this->impl.back()));
+ }
+
+ reference front() {
+ return *Traits::GetParent(std::addressof(this->impl.front()));
+ }
+
+ const_reference front() const {
+ return *Traits::GetParent(std::addressof(this->impl.front()));
+ }
+
+ iterator erase(iterator it) {
+ return iterator(this->impl.erase(it.GetImplIterator()));
+ }
+
+ iterator insert(reference ref) {
+ ImplType::pointer node = Traits::GetNode(std::addressof(ref));
+ this->InsertImpl(node);
+ return iterator(node);
+ }
+
+ iterator find(const_reference ref) const {
+ return iterator(this->FindImpl(Traits::GetNode(std::addressof(ref))));
+ }
+
+ iterator nfind(const_reference ref) const {
+ return iterator(this->NFindImpl(Traits::GetNode(std::addressof(ref))));
+ }
+
+ iterator find_light(const_light_reference ref) const {
+ return iterator(this->FindLightImpl(std::addressof(ref)));
+ }
+
+ iterator nfind_light(const_light_reference ref) const {
+ return iterator(this->NFindLightImpl(std::addressof(ref)));
+ }
+};
+
+template <auto T, class Derived = impl::GetParentType<T>>
+class IntrusiveRedBlackTreeMemberTraits;
+
+template <class Parent, IntrusiveRedBlackTreeNode Parent::*Member, class Derived>
+class IntrusiveRedBlackTreeMemberTraits<Member, Derived> {
+public:
+ template <class Comparator>
+ using TreeType = IntrusiveRedBlackTree<Derived, IntrusiveRedBlackTreeMemberTraits, Comparator>;
+ using TreeTypeImpl = impl::IntrusiveRedBlackTreeImpl;
+
+private:
+ template <class, class, class>
+ friend class IntrusiveRedBlackTree;
+
+ friend class impl::IntrusiveRedBlackTreeImpl;
+
+ static constexpr IntrusiveRedBlackTreeNode* GetNode(Derived* parent) {
+ return std::addressof(parent->*Member);
+ }
+
+ static constexpr IntrusiveRedBlackTreeNode const* GetNode(Derived const* parent) {
+ return std::addressof(parent->*Member);
+ }
+
+ static constexpr Derived* GetParent(IntrusiveRedBlackTreeNode* node) {
+ return GetParentPointer<Member, Derived>(node);
+ }
+
+ static constexpr Derived const* GetParent(const IntrusiveRedBlackTreeNode* node) {
+ return GetParentPointer<Member, Derived>(node);
+ }
+
+private:
+ static constexpr TYPED_STORAGE(Derived) DerivedStorage = {};
+ static_assert(GetParent(GetNode(GetPointer(DerivedStorage))) == GetPointer(DerivedStorage));
+};
+
+template <auto T, class Derived = impl::GetParentType<T>>
+class IntrusiveRedBlackTreeMemberTraitsDeferredAssert;
+
+template <class Parent, IntrusiveRedBlackTreeNode Parent::*Member, class Derived>
+class IntrusiveRedBlackTreeMemberTraitsDeferredAssert<Member, Derived> {
+public:
+ template <class Comparator>
+ using TreeType =
+ IntrusiveRedBlackTree<Derived, IntrusiveRedBlackTreeMemberTraitsDeferredAssert, Comparator>;
+ using TreeTypeImpl = impl::IntrusiveRedBlackTreeImpl;
+
+ static constexpr bool IsValid() {
+ TYPED_STORAGE(Derived) DerivedStorage = {};
+ return GetParent(GetNode(GetPointer(DerivedStorage))) == GetPointer(DerivedStorage);
+ }
+
+private:
+ template <class, class, class>
+ friend class IntrusiveRedBlackTree;
+
+ friend class impl::IntrusiveRedBlackTreeImpl;
+
+ static constexpr IntrusiveRedBlackTreeNode* GetNode(Derived* parent) {
+ return std::addressof(parent->*Member);
+ }
+
+ static constexpr IntrusiveRedBlackTreeNode const* GetNode(Derived const* parent) {
+ return std::addressof(parent->*Member);
+ }
+
+ static constexpr Derived* GetParent(IntrusiveRedBlackTreeNode* node) {
+ return GetParentPointer<Member, Derived>(node);
+ }
+
+ static constexpr Derived const* GetParent(const IntrusiveRedBlackTreeNode* node) {
+ return GetParentPointer<Member, Derived>(node);
+ }
+};
+
+template <class Derived>
+class IntrusiveRedBlackTreeBaseNode : public IntrusiveRedBlackTreeNode {
+public:
+ constexpr Derived* GetPrev() {
+ return static_cast<Derived*>(impl::IntrusiveRedBlackTreeImpl::GetPrev(this));
+ }
+ constexpr const Derived* GetPrev() const {
+ return static_cast<const Derived*>(impl::IntrusiveRedBlackTreeImpl::GetPrev(this));
+ }
+
+ constexpr Derived* GetNext() {
+ return static_cast<Derived*>(impl::IntrusiveRedBlackTreeImpl::GetNext(this));
+ }
+ constexpr const Derived* GetNext() const {
+ return static_cast<const Derived*>(impl::IntrusiveRedBlackTreeImpl::GetNext(this));
+ }
+};
+
+template <class Derived>
+class IntrusiveRedBlackTreeBaseTraits {
+public:
+ template <class Comparator>
+ using TreeType = IntrusiveRedBlackTree<Derived, IntrusiveRedBlackTreeBaseTraits, Comparator>;
+ using TreeTypeImpl = impl::IntrusiveRedBlackTreeImpl;
+
+private:
+ template <class, class, class>
+ friend class IntrusiveRedBlackTree;
+
+ friend class impl::IntrusiveRedBlackTreeImpl;
+
+ static constexpr IntrusiveRedBlackTreeNode* GetNode(Derived* parent) {
+ return static_cast<IntrusiveRedBlackTreeNode*>(parent);
+ }
+
+ static constexpr IntrusiveRedBlackTreeNode const* GetNode(Derived const* parent) {
+ return static_cast<const IntrusiveRedBlackTreeNode*>(parent);
+ }
+
+ static constexpr Derived* GetParent(IntrusiveRedBlackTreeNode* node) {
+ return static_cast<Derived*>(node);
+ }
+
+ static constexpr Derived const* GetParent(const IntrusiveRedBlackTreeNode* node) {
+ return static_cast<const Derived*>(node);
+ }
+};
+
+} // namespace Common