From 6922862db8677fb8067a3e35d2433b1f12f8329c Mon Sep 17 00:00:00 2001
From: gdkchan <gab.dark.100@gmail.com>
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.HLE/HOS/Kernel/Memory/KMemoryBlock.cs | 73 +++++++++++++++++++--------
 1 file changed, 53 insertions(+), 20 deletions(-)

(limited to 'Ryujinx.HLE/HOS/Kernel/Memory/KMemoryBlock.cs')

diff --git a/Ryujinx.HLE/HOS/Kernel/Memory/KMemoryBlock.cs b/Ryujinx.HLE/HOS/Kernel/Memory/KMemoryBlock.cs
index b612022c..e082105b 100644
--- a/Ryujinx.HLE/HOS/Kernel/Memory/KMemoryBlock.cs
+++ b/Ryujinx.HLE/HOS/Kernel/Memory/KMemoryBlock.cs
@@ -1,42 +1,43 @@
+using Ryujinx.Common.Collections;
 using System;
 
 namespace Ryujinx.HLE.HOS.Kernel.Memory
 {
-    class KMemoryBlock
+    class KMemoryBlock : IntrusiveRedBlackTreeNode<KMemoryBlock>, IComparable<KMemoryBlock>, IComparable<ulong>
     {
         public ulong BaseAddress { get; private set; }
-        public ulong PagesCount  { get; private set; }
+        public ulong PagesCount { get; private set; }
 
-        public MemoryState      State            { get; private set; }
-        public KMemoryPermission Permission       { get; private set; }
-        public MemoryAttribute  Attribute        { get; private set; }
+        public MemoryState State { get; private set; }
+        public KMemoryPermission Permission { get; private set; }
+        public MemoryAttribute Attribute { get; private set; }
         public KMemoryPermission SourcePermission { get; private set; }
 
-        public int IpcRefCount    { get; private set; }
+        public int IpcRefCount { get; private set; }
         public int DeviceRefCount { get; private set; }
 
         public KMemoryBlock(
-            ulong            baseAddress,
-            ulong            pagesCount,
-            MemoryState      state,
+            ulong baseAddress,
+            ulong pagesCount,
+            MemoryState state,
             KMemoryPermission permission,
-            MemoryAttribute  attribute,
-            int              ipcRefCount    = 0,
-            int              deviceRefCount = 0)
+            MemoryAttribute attribute,
+            int ipcRefCount = 0,
+            int deviceRefCount = 0)
         {
-            BaseAddress    = baseAddress;
-            PagesCount     = pagesCount;
-            State          = state;
-            Attribute      = attribute;
-            Permission     = permission;
-            IpcRefCount    = ipcRefCount;
+            BaseAddress = baseAddress;
+            PagesCount = pagesCount;
+            State = state;
+            Attribute = attribute;
+            Permission = permission;
+            IpcRefCount = ipcRefCount;
             DeviceRefCount = deviceRefCount;
         }
 
         public void SetState(KMemoryPermission permission, MemoryState state, MemoryAttribute attribute)
         {
             Permission = permission;
-            State      = state;
+            State = state;
             Attribute &= MemoryAttribute.IpcAndDeviceMapped;
             Attribute |= attribute;
         }
@@ -55,7 +56,7 @@ namespace Ryujinx.HLE.HOS.Kernel.Memory
                 SourcePermission = Permission;
 
                 Permission &= ~KMemoryPermission.ReadAndWrite;
-                Permission |=  KMemoryPermission.ReadAndWrite & newPermission;
+                Permission |= KMemoryPermission.ReadAndWrite & newPermission;
             }
 
             Attribute |= MemoryAttribute.IpcMapped;
@@ -119,5 +120,37 @@ namespace Ryujinx.HLE.HOS.Kernel.Memory
                 IpcRefCount,
                 DeviceRefCount);
         }
+
+        public int CompareTo(KMemoryBlock other)
+        {
+            if (BaseAddress < other.BaseAddress)
+            {
+                return -1;
+            }
+            else if (BaseAddress <= other.BaseAddress + other.PagesCount * KPageTableBase.PageSize - 1UL)
+            {
+                return 0;
+            }
+            else
+            {
+                return 1;
+            }
+        }
+
+        public int CompareTo(ulong address)
+        {
+            if (address < BaseAddress)
+            {
+                return 1;
+            }
+            else if (address <= BaseAddress + PagesCount * KPageTableBase.PageSize - 1UL)
+            {
+                return 0;
+            }
+            else
+            {
+                return -1;
+            }
+        }
     }
 }
\ No newline at end of file
-- 
cgit v1.2.3