From 6922862db8677fb8067a3e35d2433b1f12f8329c Mon Sep 17 00:00:00 2001 From: gdkchan Date: Fri, 26 Aug 2022 15:21:48 -0300 Subject: Optimize kernel memory block lookup and consolidate RBTree implementations (#3410) * Implement intrusive red-black tree, use it for HLE kernel block manager * Implement TreeDictionary using IntrusiveRedBlackTree * Implement IntervalTree using IntrusiveRedBlackTree * Implement IntervalTree (on Ryujinx.Memory) using IntrusiveRedBlackTree * Make PredecessorOf and SuccessorOf internal, expose Predecessor and Successor properties on the node itself * Allocation free tree node lookup --- .../Collections/IntrusiveRedBlackTree.cs | 293 +++++++++++++++++++++ 1 file changed, 293 insertions(+) create mode 100644 Ryujinx.Common/Collections/IntrusiveRedBlackTree.cs (limited to 'Ryujinx.Common/Collections/IntrusiveRedBlackTree.cs') diff --git a/Ryujinx.Common/Collections/IntrusiveRedBlackTree.cs b/Ryujinx.Common/Collections/IntrusiveRedBlackTree.cs new file mode 100644 index 00000000..970cab87 --- /dev/null +++ b/Ryujinx.Common/Collections/IntrusiveRedBlackTree.cs @@ -0,0 +1,293 @@ +using System; + +namespace Ryujinx.Common.Collections +{ + /// + /// Tree that provides the ability for O(logN) lookups for keys that exist in the tree, and O(logN) lookups for keys immediately greater than or less than a specified key. + /// + /// Derived node type + public class IntrusiveRedBlackTree : IntrusiveRedBlackTreeImpl where T : IntrusiveRedBlackTreeNode, IComparable + { + #region Public Methods + + /// + /// Adds a new node into the tree. + /// + /// Node to be added + /// is null + public void Add(T node) + { + if (node == null) + { + throw new ArgumentNullException(nameof(node)); + } + + Insert(node); + } + + /// + /// Removes a node from the tree. + /// + /// Note to be removed + /// is null + public void Remove(T node) + { + if (node == null) + { + throw new ArgumentNullException(nameof(node)); + } + if (Delete(node) != null) + { + Count--; + } + } + + /// + /// Retrieve the node that is considered equal to the specified node by the comparator. + /// + /// Node to compare with + /// Node that is equal to + /// is null + public T GetNode(T searchNode) + { + if (searchNode == null) + { + throw new ArgumentNullException(nameof(searchNode)); + } + + T node = Root; + while (node != null) + { + int cmp = searchNode.CompareTo(node); + if (cmp < 0) + { + node = node.Left; + } + else if (cmp > 0) + { + node = node.Right; + } + else + { + return node; + } + } + return null; + } + + #endregion + + #region Private Methods (BST) + + /// + /// Inserts a new node into the tree. + /// + /// Node to be inserted + private void Insert(T node) + { + T newNode = BSTInsert(node); + RestoreBalanceAfterInsertion(newNode); + } + + /// + /// Insertion Mechanism for a Binary Search Tree (BST). + ///

+ /// Iterates the tree starting from the root and inserts a new node + /// where all children in the left subtree are less than , + /// and all children in the right subtree are greater than . + /// + /// Node to be inserted + /// The inserted Node + private T BSTInsert(T newNode) + { + T parent = null; + T node = Root; + + while (node != null) + { + parent = node; + int cmp = newNode.CompareTo(node); + if (cmp < 0) + { + node = node.Left; + } + else if (cmp > 0) + { + node = node.Right; + } + else + { + return node; + } + } + newNode.Parent = parent; + if (parent == null) + { + Root = newNode; + } + else if (newNode.CompareTo(parent) < 0) + { + parent.Left = newNode; + } + else + { + parent.Right = newNode; + } + Count++; + return newNode; + } + + /// + /// Removes from the tree, if it exists. + /// + /// Node to be removed + /// The deleted Node + private T Delete(T nodeToDelete) + { + if (nodeToDelete == null) + { + return null; + } + + T old = nodeToDelete; + T child; + T parent; + bool color; + + if (LeftOf(nodeToDelete) == null) + { + child = RightOf(nodeToDelete); + } + else if (RightOf(nodeToDelete) == null) + { + child = LeftOf(nodeToDelete); + } + else + { + T element = Minimum(RightOf(nodeToDelete)); + + child = RightOf(element); + parent = ParentOf(element); + color = ColorOf(element); + + if (child != null) + { + child.Parent = parent; + } + + if (parent == null) + { + Root = child; + } + else if (element == LeftOf(parent)) + { + parent.Left = child; + } + else + { + parent.Right = child; + } + + if (ParentOf(element) == old) + { + parent = element; + } + + element.Color = old.Color; + element.Left = old.Left; + element.Right = old.Right; + element.Parent = old.Parent; + + if (ParentOf(old) == null) + { + Root = element; + } + else if (old == LeftOf(ParentOf(old))) + { + ParentOf(old).Left = element; + } + else + { + ParentOf(old).Right = element; + } + + LeftOf(old).Parent = element; + + if (RightOf(old) != null) + { + RightOf(old).Parent = element; + } + + if (child != null && color == Black) + { + RestoreBalanceAfterRemoval(child); + } + + return old; + } + + parent = ParentOf(nodeToDelete); + color = ColorOf(nodeToDelete); + + if (child != null) + { + child.Parent = parent; + } + + if (parent == null) + { + Root = child; + } + else if (nodeToDelete == LeftOf(parent)) + { + parent.Left = child; + } + else + { + parent.Right = child; + } + + if (child != null && color == Black) + { + RestoreBalanceAfterRemoval(child); + } + + return old; + } + + #endregion + } + + public static class IntrusiveRedBlackTreeExtensions + { + /// + /// Retrieve the node that is considered equal to the key by the comparator. + /// + /// Tree to search at + /// Key of the node to be found + /// Node that is equal to + public static N GetNodeByKey(this IntrusiveRedBlackTree tree, K key) + where N : IntrusiveRedBlackTreeNode, IComparable, IComparable + where K : struct + { + N node = tree.RootNode; + while (node != null) + { + int cmp = node.CompareTo(key); + if (cmp < 0) + { + node = node.Right; + } + else if (cmp > 0) + { + node = node.Left; + } + else + { + return node; + } + } + return null; + } + } +} -- cgit v1.2.3