diff options
Diffstat (limited to 'src/Ryujinx.Common/Collections/IntrusiveRedBlackTreeImpl.cs')
| -rw-r--r-- | src/Ryujinx.Common/Collections/IntrusiveRedBlackTreeImpl.cs | 354 |
1 files changed, 354 insertions, 0 deletions
diff --git a/src/Ryujinx.Common/Collections/IntrusiveRedBlackTreeImpl.cs b/src/Ryujinx.Common/Collections/IntrusiveRedBlackTreeImpl.cs new file mode 100644 index 00000000..bcb2e2a2 --- /dev/null +++ b/src/Ryujinx.Common/Collections/IntrusiveRedBlackTreeImpl.cs @@ -0,0 +1,354 @@ +using System; + +namespace Ryujinx.Common.Collections +{ + /// <summary> + /// 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. + /// </summary> + /// <typeparam name="T">Derived node type</typeparam> + public class IntrusiveRedBlackTreeImpl<T> where T : IntrusiveRedBlackTreeNode<T> + { + protected const bool Black = true; + protected const bool Red = false; + protected T Root = null; + + internal T RootNode => Root; + + /// <summary> + /// Number of nodes on the tree. + /// </summary> + public int Count { get; protected set; } + + /// <summary> + /// Removes all nodes on the tree. + /// </summary> + public void Clear() + { + Root = null; + Count = 0; + } + + /// <summary> + /// Finds the node whose key is immediately greater than <paramref name="node"/>. + /// </summary> + /// <param name="node">Node to find the successor of</param> + /// <returns>Successor of <paramref name="node"/></returns> + internal static T SuccessorOf(T node) + { + if (node.Right != null) + { + return Minimum(node.Right); + } + T parent = node.Parent; + while (parent != null && node == parent.Right) + { + node = parent; + parent = parent.Parent; + } + return parent; + } + + /// <summary> + /// Finds the node whose key is immediately less than <paramref name="node"/>. + /// </summary> + /// <param name="node">Node to find the predecessor of</param> + /// <returns>Predecessor of <paramref name="node"/></returns> + internal static T PredecessorOf(T node) + { + if (node.Left != null) + { + return Maximum(node.Left); + } + T parent = node.Parent; + while (parent != null && node == parent.Left) + { + node = parent; + parent = parent.Parent; + } + return parent; + } + + /// <summary> + /// Returns the node with the largest key where <paramref name="node"/> is considered the root node. + /// </summary> + /// <param name="node">Root node</param> + /// <returns>Node with the maximum key in the tree of <paramref name="node"/></returns> + protected static T Maximum(T node) + { + T tmp = node; + while (tmp.Right != null) + { + tmp = tmp.Right; + } + + return tmp; + } + + /// <summary> + /// Returns the node with the smallest key where <paramref name="node"/> is considered the root node. + /// </summary> + /// <param name="node">Root node</param> + /// <returns>Node with the minimum key in the tree of <paramref name="node"/></returns> + /// <exception cref="ArgumentNullException"><paramref name="node"/> is null</exception> + protected static T Minimum(T node) + { + ArgumentNullException.ThrowIfNull(node); + + T tmp = node; + while (tmp.Left != null) + { + tmp = tmp.Left; + } + + return tmp; + } + + protected void RestoreBalanceAfterRemoval(T balanceNode) + { + T ptr = balanceNode; + + while (ptr != Root && ColorOf(ptr) == Black) + { + if (ptr == LeftOf(ParentOf(ptr))) + { + T 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 + { + T 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); + } + + protected void RestoreBalanceAfterInsertion(T balanceNode) + { + SetColor(balanceNode, Red); + while (balanceNode != null && balanceNode != Root && ColorOf(ParentOf(balanceNode)) == Red) + { + if (ParentOf(balanceNode) == LeftOf(ParentOf(ParentOf(balanceNode)))) + { + T 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 + { + T 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); + } + + protected virtual void RotateLeft(T node) + { + if (node != null) + { + T right = RightOf(node); + node.Right = LeftOf(right); + if (node.Right != null) + { + node.Right.Parent = node; + } + T 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; + } + } + + protected virtual void RotateRight(T node) + { + if (node != null) + { + T left = LeftOf(node); + node.Left = RightOf(left); + if (node.Left != null) + { + node.Left.Parent = node; + } + T 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; + } + } + + #region Safety-Methods + + // These methods save memory by allowing us to forego sentinel nil nodes, as well as serve as protection against NullReferenceExceptions. + + /// <summary> + /// Returns the color of <paramref name="node"/>, or Black if it is null. + /// </summary> + /// <param name="node">Node</param> + /// <returns>The boolean color of <paramref name="node"/>, or black if null</returns> + protected static bool ColorOf(T node) + { + return node == null || node.Color; + } + + /// <summary> + /// Sets the color of <paramref name="node"/> node to <paramref name="color"/>. + /// <br></br> + /// This method does nothing if <paramref name="node"/> is null. + /// </summary> + /// <param name="node">Node to set the color of</param> + /// <param name="color">Color (Boolean)</param> + protected static void SetColor(T node, bool color) + { + if (node != null) + { + node.Color = color; + } + } + + /// <summary> + /// This method returns the left node of <paramref name="node"/>, or null if <paramref name="node"/> is null. + /// </summary> + /// <param name="node">Node to retrieve the left child from</param> + /// <returns>Left child of <paramref name="node"/></returns> + protected static T LeftOf(T node) + { + return node?.Left; + } + + /// <summary> + /// This method returns the right node of <paramref name="node"/>, or null if <paramref name="node"/> is null. + /// </summary> + /// <param name="node">Node to retrieve the right child from</param> + /// <returns>Right child of <paramref name="node"/></returns> + protected static T RightOf(T node) + { + return node?.Right; + } + + /// <summary> + /// Returns the parent node of <paramref name="node"/>, or null if <paramref name="node"/> is null. + /// </summary> + /// <param name="node">Node to retrieve the parent from</param> + /// <returns>Parent of <paramref name="node"/></returns> + protected static T ParentOf(T node) + { + return node?.Parent; + } + + #endregion + } +} |