1 files changed, 57 insertions, 48 deletions
diff --git a/Ryujinx.Memory/WindowsShared/PlaceholderManager.cs b/Ryujinx.Memory/WindowsShared/PlaceholderManager.cs
index 0937d462..6db8d7df 100644
--- a/Ryujinx.Memory/WindowsShared/PlaceholderManager.cs
+++ b/Ryujinx.Memory/WindowsShared/PlaceholderManager.cs
@@ -13,10 +13,10 @@ namespace Ryujinx.Memory.WindowsShared
     [SupportedOSPlatform("windows")]
     class PlaceholderManager
     {
-        private const ulong MinimumPageSize = 0x1000;
+        private const int InitialOverlapsSize = 10;
 
-        private readonly IntervalTree<ulong, ulong> _mappings;
-        private readonly IntervalTree<ulong, MemoryPermission> _protections;
+        private readonly MappingTree<ulong> _mappings;
+        private readonly MappingTree<MemoryPermission> _protections;
         private readonly IntPtr _partialUnmapStatePtr;
         private readonly Thread _partialUnmapTrimThread;
 
@@ -25,8 +25,8 @@ namespace Ryujinx.Memory.WindowsShared
         /// </summary>
         public PlaceholderManager()
         {
-            _mappings = new IntervalTree<ulong, ulong>();
-            _protections = new IntervalTree<ulong, MemoryPermission>();
+            _mappings = new MappingTree<ulong>();
+            _protections = new MappingTree<MemoryPermission>();
 
             _partialUnmapStatePtr = PartialUnmapState.GlobalState;
 
@@ -67,7 +67,7 @@ namespace Ryujinx.Memory.WindowsShared
         {
             lock (_mappings)
             {
-                _mappings.Add(address, address + size, ulong.MaxValue);
+                _mappings.Add(new RangeNode<ulong>(address, address + size, ulong.MaxValue));
             }
         }
 
@@ -81,12 +81,12 @@ namespace Ryujinx.Memory.WindowsShared
         {
             ulong endAddress = address + size;
 
-            var overlaps = Array.Empty<IntervalTreeNode<ulong, ulong>>();
+            var overlaps = new RangeNode<ulong>[InitialOverlapsSize];
             int count;
 
             lock (_mappings)
             {
-                count = _mappings.Get(address, endAddress, ref overlaps);
+                count = _mappings.GetNodes(address, endAddress, ref overlaps);
 
                 for (int index = 0; index < count; index++)
                 {
@@ -178,11 +178,11 @@ namespace Ryujinx.Memory.WindowsShared
         {
             ulong endAddress = address + size;
 
-            var overlaps = Array.Empty<IntervalTreeNode<ulong, ulong>>();
+            var overlaps = new RangeNode<ulong>[InitialOverlapsSize];
 
             lock (_mappings)
             {
-                int count = _mappings.Get(address, endAddress, ref overlaps);
+                int count = _mappings.GetNodes(address, endAddress, ref overlaps);
 
                 Debug.Assert(count == 1);
                 Debug.Assert(!IsMapped(overlaps[0].Value));
@@ -206,8 +206,8 @@ namespace Ryujinx.Memory.WindowsShared
                         (IntPtr)size,
                         AllocationType.Release | AllocationType.PreservePlaceholder));
 
-                    _mappings.Add(overlapStart, address, overlapValue);
-                    _mappings.Add(endAddress, overlapEnd, AddBackingOffset(overlapValue, endAddress - overlapStart));
+                    _mappings.Add(new RangeNode<ulong>(overlapStart, address, overlapValue));
+                    _mappings.Add(new RangeNode<ulong>(endAddress, overlapEnd, AddBackingOffset(overlapValue, endAddress - overlapStart)));
                 }
                 else if (overlapStartsBefore)
                 {
@@ -218,7 +218,7 @@ namespace Ryujinx.Memory.WindowsShared
                         (IntPtr)overlappedSize,
                         AllocationType.Release | AllocationType.PreservePlaceholder));
 
-                    _mappings.Add(overlapStart, address, overlapValue);
+                    _mappings.Add(new RangeNode<ulong>(overlapStart, address, overlapValue));
                 }
                 else if (overlapEndsAfter)
                 {
@@ -229,10 +229,10 @@ namespace Ryujinx.Memory.WindowsShared
                         (IntPtr)overlappedSize,
                         AllocationType.Release | AllocationType.PreservePlaceholder));
 
-                    _mappings.Add(endAddress, overlapEnd, AddBackingOffset(overlapValue, overlappedSize));
+                    _mappings.Add(new RangeNode<ulong>(endAddress, overlapEnd, AddBackingOffset(overlapValue, overlappedSize)));
                 }
 
-                _mappings.Add(address, endAddress, backingOffset);
+                _mappings.Add(new RangeNode<ulong>(address, endAddress, backingOffset));
             }
         }
 
@@ -280,12 +280,12 @@ namespace Ryujinx.Memory.WindowsShared
             ulong unmapSize = (ulong)size;
             ulong endAddress = startAddress + unmapSize;
 
-            var overlaps = Array.Empty<IntervalTreeNode<ulong, ulong>>();
+            var overlaps = new RangeNode<ulong>[InitialOverlapsSize];
             int count;
 
             lock (_mappings)
             {
-                count = _mappings.Get(startAddress, endAddress, ref overlaps);
+                count = _mappings.GetNodes(startAddress, endAddress, ref overlaps);
             }
 
             for (int index = 0; index < count; index++)
@@ -302,7 +302,7 @@ namespace Ryujinx.Memory.WindowsShared
                     lock (_mappings)
                     {
                         _mappings.Remove(overlap);
-                        _mappings.Add(overlapStart, overlapEnd, ulong.MaxValue);
+                        _mappings.Add(new RangeNode<ulong>(overlapStart, overlapEnd, ulong.MaxValue));
                     }
 
                     bool overlapStartsBefore = overlapStart < startAddress;
@@ -374,44 +374,53 @@ namespace Ryujinx.Memory.WindowsShared
             ulong endAddress = address + size;
             ulong blockAddress = (ulong)owner.Pointer;
             ulong blockEnd = blockAddress + owner.Size;
-            var overlaps = Array.Empty<IntervalTreeNode<ulong, ulong>>();
+            var overlaps = new RangeNode<ulong>[InitialOverlapsSize];
             int unmappedCount = 0;
 
             lock (_mappings)
             {
-                int count = _mappings.Get(
-                    Math.Max(address - MinimumPageSize, blockAddress),
-                    Math.Min(endAddress + MinimumPageSize, blockEnd), ref overlaps);
+                int count = _mappings.GetNodes(address, endAddress, ref overlaps);
 
-                if (count < 2)
+                if (count == 0)
                 {
-                    // Nothing to coalesce if we only have 1 or no overlaps.
+                    // Nothing to coalesce if we no overlaps.
                     return;
                 }
 
+                RangeNode<ulong> predecessor = overlaps[0].Predecessor;
+                RangeNode<ulong> successor = overlaps[count - 1].Successor;
+
                 for (int index = 0; index < count; index++)
                 {
                     var overlap = overlaps[index];
 
                     if (!IsMapped(overlap.Value))
                     {
-                        if (address > overlap.Start)
-                        {
-                            address = overlap.Start;
-                        }
-
-                        if (endAddress < overlap.End)
-                        {
-                            endAddress = overlap.End;
-                        }
+                        address = Math.Min(address, overlap.Start);
+                        endAddress = Math.Max(endAddress, overlap.End);
 
                         _mappings.Remove(overlap);
-
                         unmappedCount++;
                     }
                 }
 
-                _mappings.Add(address, endAddress, ulong.MaxValue);
+                if (predecessor != null && !IsMapped(predecessor.Value) && predecessor.Start >= blockAddress)
+                {
+                    address = Math.Min(address, predecessor.Start);
+
+                    _mappings.Remove(predecessor);
+                    unmappedCount++;
+                }
+
+                if (successor != null && !IsMapped(successor.Value) && successor.End <= blockEnd)
+                {
+                    endAddress = Math.Max(endAddress, successor.End);
+
+                    _mappings.Remove(successor);
+                    unmappedCount++;
+                }
+
+                _mappings.Add(new RangeNode<ulong>(address, endAddress, ulong.MaxValue));
             }
 
             if (unmappedCount > 1)
@@ -462,12 +471,12 @@ namespace Ryujinx.Memory.WindowsShared
             ulong reprotectSize = (ulong)size;
             ulong endAddress = reprotectAddress + reprotectSize;
 
-            var overlaps = Array.Empty<IntervalTreeNode<ulong, ulong>>();
+            var overlaps = new RangeNode<ulong>[InitialOverlapsSize];
             int count;
 
             lock (_mappings)
             {
-                count = _mappings.Get(reprotectAddress, endAddress, ref overlaps);
+                count = _mappings.GetNodes(reprotectAddress, endAddress, ref overlaps);
             }
 
             bool success = true;
@@ -567,12 +576,12 @@ namespace Ryujinx.Memory.WindowsShared
         private void AddProtection(ulong address, ulong size, MemoryPermission permission)
         {
             ulong endAddress = address + size;
-            var overlaps = Array.Empty<IntervalTreeNode<ulong, MemoryPermission>>();
+            var overlaps = new RangeNode<MemoryPermission>[InitialOverlapsSize];
             int count;
 
             lock (_protections)
             {
-                count = _protections.Get(address, endAddress, ref overlaps);
+                count = _protections.GetNodes(address, endAddress, ref overlaps);
 
                 if (count == 1 &&
                     overlaps[0].Start <= address &&
@@ -610,17 +619,17 @@ namespace Ryujinx.Memory.WindowsShared
                     {
                         if (startAddress > protAddress)
                         {
-                            _protections.Add(protAddress, startAddress, protPermission);
+                            _protections.Add(new RangeNode<MemoryPermission>(protAddress, startAddress, protPermission));
                         }
 
                         if (endAddress < protEndAddress)
                         {
-                            _protections.Add(endAddress, protEndAddress, protPermission);
+                            _protections.Add(new RangeNode<MemoryPermission>(endAddress, protEndAddress, protPermission));
                         }
                     }
                 }
 
-                _protections.Add(startAddress, endAddress, permission);
+                _protections.Add(new RangeNode<MemoryPermission>(startAddress, endAddress, permission));
             }
         }
 
@@ -632,12 +641,12 @@ namespace Ryujinx.Memory.WindowsShared
         private void RemoveProtection(ulong address, ulong size)
         {
             ulong endAddress = address + size;
-            var overlaps = Array.Empty<IntervalTreeNode<ulong, MemoryPermission>>();
+            var overlaps = new RangeNode<MemoryPermission>[InitialOverlapsSize];
             int count;
 
             lock (_protections)
             {
-                count = _protections.Get(address, endAddress, ref overlaps);
+                count = _protections.GetNodes(address, endAddress, ref overlaps);
 
                 for (int index = 0; index < count; index++)
                 {
@@ -651,12 +660,12 @@ namespace Ryujinx.Memory.WindowsShared
 
                     if (address > protAddress)
                     {
-                        _protections.Add(protAddress, address, protPermission);
+                        _protections.Add(new RangeNode<MemoryPermission>(protAddress, address, protPermission));
                     }
 
                     if (endAddress < protEndAddress)
                     {
-                        _protections.Add(endAddress, protEndAddress, protPermission);
+                        _protections.Add(new RangeNode<MemoryPermission>(endAddress, protEndAddress, protPermission));
                     }
                 }
             }
@@ -670,12 +679,12 @@ namespace Ryujinx.Memory.WindowsShared
         private void RestoreRangeProtection(ulong address, ulong size)
         {
             ulong endAddress = address + size;
-            var overlaps = Array.Empty<IntervalTreeNode<ulong, MemoryPermission>>();
+            var overlaps = new RangeNode<MemoryPermission>[InitialOverlapsSize];
             int count;
 
             lock (_protections)
             {
-                count = _protections.Get(address, endAddress, ref overlaps);
+                count = _protections.GetNodes(address, endAddress, ref overlaps);
             }
 
             ulong startAddress = address;