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 --- Ryujinx.Memory/WindowsShared/IntervalTree.cs | 319 ++------------------------- 1 file changed, 16 insertions(+), 303 deletions(-) (limited to 'Ryujinx.Memory/WindowsShared/IntervalTree.cs') diff --git a/Ryujinx.Memory/WindowsShared/IntervalTree.cs b/Ryujinx.Memory/WindowsShared/IntervalTree.cs index eac5c545..fe12e8b8 100644 --- a/Ryujinx.Memory/WindowsShared/IntervalTree.cs +++ b/Ryujinx.Memory/WindowsShared/IntervalTree.cs @@ -1,3 +1,4 @@ +using Ryujinx.Common.Collections; using System; using System.Collections.Generic; @@ -8,19 +9,10 @@ namespace Ryujinx.Memory.WindowsShared /// /// Key /// Value - class IntervalTree where K : IComparable + class IntervalTree : IntrusiveRedBlackTreeImpl> where K : IComparable { private const int ArrayGrowthSize = 32; - private const bool Black = true; - private const bool Red = false; - private IntervalTreeNode _root = null; - private int _count = 0; - - public int Count => _count; - - public IntervalTree() { } - #region Public Methods /// @@ -53,7 +45,7 @@ namespace Ryujinx.Memory.WindowsShared /// Number of intervals found public int Get(K start, K end, ref IntervalTreeNode[] overlaps, int overlapCount = 0) { - GetNodes(_root, start, end, ref overlaps, ref overlapCount); + GetNodes(Root, start, end, ref overlaps, ref overlapCount); return overlapCount; } @@ -99,7 +91,7 @@ namespace Ryujinx.Memory.WindowsShared Delete(nodeToDelete); - _count--; + Count--; return 1; } @@ -112,7 +104,7 @@ namespace Ryujinx.Memory.WindowsShared { List list = new List(); - AddToList(_root, list); + AddToList(Root, list); return list; } @@ -153,7 +145,7 @@ namespace Ryujinx.Memory.WindowsShared throw new ArgumentNullException(nameof(key)); } - IntervalTreeNode node = _root; + IntervalTreeNode node = Root; while (node != null) { int cmp = key.CompareTo(node.Start); @@ -271,7 +263,7 @@ namespace Ryujinx.Memory.WindowsShared private bool BSTInsert(K start, K end, V value, Func updateFactoryCallback, out IntervalTreeNode outNode) { IntervalTreeNode parent = null; - IntervalTreeNode node = _root; + IntervalTreeNode node = Root; while (node != null) { @@ -319,7 +311,7 @@ namespace Ryujinx.Memory.WindowsShared IntervalTreeNode newNode = new IntervalTreeNode(start, end, value, parent); if (newNode.Parent == null) { - _root = newNode; + Root = newNode; } else if (start.CompareTo(parent.Start) < 0) { @@ -331,7 +323,7 @@ namespace Ryujinx.Memory.WindowsShared } PropagateIncrease(newNode); - _count++; + Count++; RestoreBalanceAfterInsertion(newNode); outNode = newNode; return true; @@ -351,7 +343,7 @@ namespace Ryujinx.Memory.WindowsShared } else { - replacementNode = PredecessorOf(nodeToDelete); + replacementNode = nodeToDelete.Predecessor; } IntervalTreeNode tmp = LeftOf(replacementNode) ?? RightOf(replacementNode); @@ -363,7 +355,7 @@ namespace Ryujinx.Memory.WindowsShared if (ParentOf(replacementNode) == null) { - _root = tmp; + Root = tmp; } else if (replacementNode == LeftOf(ParentOf(replacementNode))) { @@ -390,232 +382,25 @@ namespace Ryujinx.Memory.WindowsShared } } - /// - /// Returns the node with the largest key where is considered the root node. - /// - /// Root Node - /// Node with the maximum key in the tree of - private static IntervalTreeNode Maximum(IntervalTreeNode node) - { - IntervalTreeNode tmp = node; - while (tmp.Right != null) - { - tmp = tmp.Right; - } - - return tmp; - } - - /// - /// Finds the node whose key is immediately less than . - /// - /// Node to find the predecessor of - /// Predecessor of - private static IntervalTreeNode PredecessorOf(IntervalTreeNode node) - { - if (node.Left != null) - { - return Maximum(node.Left); - } - IntervalTreeNode parent = node.Parent; - while (parent != null && node == parent.Left) - { - node = parent; - parent = parent.Parent; - } - return parent; - } - #endregion #region Private Methods (RBL) - private void RestoreBalanceAfterRemoval(IntervalTreeNode balanceNode) - { - IntervalTreeNode ptr = balanceNode; - - while (ptr != _root && ColorOf(ptr) == Black) - { - if (ptr == LeftOf(ParentOf(ptr))) - { - IntervalTreeNode sibling = RightOf(ParentOf(ptr)); - - if (ColorOf(sibling) == Red) - { - SetColor(sibling, Black); - SetColor(ParentOf(ptr), Red); - RotateLeft(ParentOf(ptr)); - sibling = RightOf(ParentOf(ptr)); - } - if (ColorOf(LeftOf(sibling)) == Black && ColorOf(RightOf(sibling)) == Black) - { - SetColor(sibling, Red); - ptr = ParentOf(ptr); - } - else - { - if (ColorOf(RightOf(sibling)) == Black) - { - SetColor(LeftOf(sibling), Black); - SetColor(sibling, Red); - RotateRight(sibling); - sibling = RightOf(ParentOf(ptr)); - } - SetColor(sibling, ColorOf(ParentOf(ptr))); - SetColor(ParentOf(ptr), Black); - SetColor(RightOf(sibling), Black); - RotateLeft(ParentOf(ptr)); - ptr = _root; - } - } - else - { - IntervalTreeNode sibling = LeftOf(ParentOf(ptr)); - - if (ColorOf(sibling) == Red) - { - SetColor(sibling, Black); - SetColor(ParentOf(ptr), Red); - RotateRight(ParentOf(ptr)); - sibling = LeftOf(ParentOf(ptr)); - } - if (ColorOf(RightOf(sibling)) == Black && ColorOf(LeftOf(sibling)) == Black) - { - SetColor(sibling, Red); - ptr = ParentOf(ptr); - } - else - { - if (ColorOf(LeftOf(sibling)) == Black) - { - SetColor(RightOf(sibling), Black); - SetColor(sibling, Red); - RotateLeft(sibling); - sibling = LeftOf(ParentOf(ptr)); - } - SetColor(sibling, ColorOf(ParentOf(ptr))); - SetColor(ParentOf(ptr), Black); - SetColor(LeftOf(sibling), Black); - RotateRight(ParentOf(ptr)); - ptr = _root; - } - } - } - SetColor(ptr, Black); - } - - private void RestoreBalanceAfterInsertion(IntervalTreeNode balanceNode) - { - SetColor(balanceNode, Red); - while (balanceNode != null && balanceNode != _root && ColorOf(ParentOf(balanceNode)) == Red) - { - if (ParentOf(balanceNode) == LeftOf(ParentOf(ParentOf(balanceNode)))) - { - IntervalTreeNode sibling = RightOf(ParentOf(ParentOf(balanceNode))); - - if (ColorOf(sibling) == Red) - { - SetColor(ParentOf(balanceNode), Black); - SetColor(sibling, Black); - SetColor(ParentOf(ParentOf(balanceNode)), Red); - balanceNode = ParentOf(ParentOf(balanceNode)); - } - else - { - if (balanceNode == RightOf(ParentOf(balanceNode))) - { - balanceNode = ParentOf(balanceNode); - RotateLeft(balanceNode); - } - SetColor(ParentOf(balanceNode), Black); - SetColor(ParentOf(ParentOf(balanceNode)), Red); - RotateRight(ParentOf(ParentOf(balanceNode))); - } - } - else - { - IntervalTreeNode sibling = LeftOf(ParentOf(ParentOf(balanceNode))); - - if (ColorOf(sibling) == Red) - { - SetColor(ParentOf(balanceNode), Black); - SetColor(sibling, Black); - SetColor(ParentOf(ParentOf(balanceNode)), Red); - balanceNode = ParentOf(ParentOf(balanceNode)); - } - else - { - if (balanceNode == LeftOf(ParentOf(balanceNode))) - { - balanceNode = ParentOf(balanceNode); - RotateRight(balanceNode); - } - SetColor(ParentOf(balanceNode), Black); - SetColor(ParentOf(ParentOf(balanceNode)), Red); - RotateLeft(ParentOf(ParentOf(balanceNode))); - } - } - } - SetColor(_root, Black); - } - - private void RotateLeft(IntervalTreeNode node) + protected override void RotateLeft(IntervalTreeNode node) { if (node != null) { - IntervalTreeNode right = RightOf(node); - node.Right = LeftOf(right); - if (node.Right != null) - { - node.Right.Parent = node; - } - IntervalTreeNode nodeParent = ParentOf(node); - right.Parent = nodeParent; - if (nodeParent == null) - { - _root = right; - } - else if (node == LeftOf(nodeParent)) - { - nodeParent.Left = right; - } - else - { - nodeParent.Right = right; - } - right.Left = node; - node.Parent = right; + base.RotateLeft(node); PropagateFull(node); } } - private void RotateRight(IntervalTreeNode node) + protected override void RotateRight(IntervalTreeNode node) { if (node != null) { - IntervalTreeNode left = LeftOf(node); - node.Left = RightOf(left); - if (node.Left != null) - { - node.Left.Parent = node; - } - IntervalTreeNode nodeParent = ParentOf(node); - left.Parent = nodeParent; - if (nodeParent == null) - { - _root = left; - } - else if (node == RightOf(nodeParent)) - { - nodeParent.Right = left; - } - else - { - nodeParent.Left = left; - } - left.Right = node; - node.Parent = left; + base.RotateRight(node); PropagateFull(node); } @@ -623,77 +408,10 @@ namespace Ryujinx.Memory.WindowsShared #endregion - #region Safety-Methods - - // These methods save memory by allowing us to forego sentinel nil nodes, as well as serve as protection against NullReferenceExceptions. - - /// - /// Returns the color of , or Black if it is null. - /// - /// Node - /// The boolean color of , or black if null - private static bool ColorOf(IntervalTreeNode node) - { - return node == null || node.Color; - } - - /// - /// Sets the color of node to . - ///

- /// This method does nothing if is null. - /// - /// Node to set the color of - /// Color (Boolean) - private static void SetColor(IntervalTreeNode node, bool color) - { - if (node != null) - { - node.Color = color; - } - } - - /// - /// This method returns the left node of , or null if is null. - /// - /// Node to retrieve the left child from - /// Left child of - private static IntervalTreeNode LeftOf(IntervalTreeNode node) - { - return node?.Left; - } - - /// - /// This method returns the right node of , or null if is null. - /// - /// Node to retrieve the right child from - /// Right child of - private static IntervalTreeNode RightOf(IntervalTreeNode node) - { - return node?.Right; - } - - /// - /// Returns the parent node of , or null if is null. - /// - /// Node to retrieve the parent from - /// Parent of - private static IntervalTreeNode ParentOf(IntervalTreeNode node) - { - return node?.Parent; - } - - #endregion - public bool ContainsKey(K key) { return GetNode(key) != null; } - - public void Clear() - { - _root = null; - _count = 0; - } } /// @@ -701,13 +419,8 @@ namespace Ryujinx.Memory.WindowsShared /// /// Key type of the node /// Value type of the node - class IntervalTreeNode + class IntervalTreeNode : IntrusiveRedBlackTreeNode> { - public bool Color = true; - public IntervalTreeNode Left = null; - public IntervalTreeNode Right = null; - public IntervalTreeNode Parent = null; - /// /// The start of the range. /// -- cgit v1.2.3