Use a more efficient range list on the buffer manager

1 files changed, 88 insertions, 52 deletions

diff --git a/Ryujinx.Graphics.Gpu/Memory/RangeList.cs b/Ryujinx.Graphics.Gpu/Memory/RangeList.cs
index 6114f15d..072fdfe8 100644
--- a/Ryujinx.Graphics.Gpu/Memory/RangeList.cs
+++ b/Ryujinx.Graphics.Gpu/Memory/RangeList.cs
@@ -6,6 +6,8 @@ namespace Ryujinx.Graphics.Gpu.Memory
     {
         private List<T> _items;
 
+        public int Count => _items.Count;
+
         public RangeList()
         {
             _items = new List<T>();
@@ -13,49 +15,57 @@ namespace Ryujinx.Graphics.Gpu.Memory
 
         public void Add(T item)
         {
-            lock (_items)
-            {
-                int index = BinarySearch(item.Address);
-
-                if (index < 0)
-                {
-                    index = ~index;
-                }
+            int index = BinarySearch(item.Address);
 
-                _items.Insert(index, item);
+            if (index < 0)
+            {
+                index = ~index;
             }
+
+            _items.Insert(index, item);
         }
 
         public bool Remove(T item)
         {
-            lock (_items)
+            int index = BinarySearch(item.Address);
+
+            if (index >= 0)
             {
-                int index = BinarySearch(item.Address);
+                while (index > 0 && _items[index - 1].Address == item.Address)
+                {
+                    index--;
+                }
 
-                if (index >= 0)
+                while (index < _items.Count)
                 {
-                    while (index > 0 && _items[index - 1].Address == item.Address)
+                    if (_items[index].Equals(item))
                     {
-                        index--;
+                        _items.RemoveAt(index);
+
+                        return true;
                     }
 
-                    while (index < _items.Count)
+                    if (_items[index].Address > item.Address)
                     {
-                        if (_items[index].Equals(item))
-                        {
-                            _items.RemoveAt(index);
+                        break;
+                    }
 
-                            return true;
-                        }
+                    index++;
+                }
+            }
 
-                        if (_items[index].Address > item.Address)
-                        {
-                            break;
-                        }
+            return false;
+        }
 
-                        index++;
-                    }
-                }
+        public bool CanExitEarly(ulong address, ulong size)
+        {
+            int index = BinarySearch(address, size);
+
+            if (index >= 0)
+            {
+                T item = _items[index];
+
+                return address >= item.Address && address + size <= item.Address + item.Size;
             }
 
             return false;
@@ -68,17 +78,14 @@ namespace Ryujinx.Graphics.Gpu.Memory
 
         public T FindFirstOverlap(ulong address, ulong size)
         {
-            lock (_items)
-            {
-                int index = BinarySearch(address, size);
+            int index = BinarySearch(address, size);
 
-                if (index < 0)
-                {
-                    return default(T);
-                }
-
-                return _items[index];
+            if (index < 0)
+            {
+                return default(T);
             }
+
+            return _items[index];
         }
 
         public T[] FindOverlaps(T item)
@@ -111,32 +118,61 @@ namespace Ryujinx.Graphics.Gpu.Memory
             return overlapsList.ToArray();
         }
 
-        public T[] FindOverlaps(ulong address)
+        public T[] FindOverlapsNonOverlapping(T item)
+        {
+            return FindOverlapsNonOverlapping(item.Address, item.Size);
+        }
+
+        public T[] FindOverlapsNonOverlapping(ulong address, ulong size)
         {
+            // This is a bit faster than FindOverlaps, but only works
+            // when none of the items on the list overlaps with each other.
             List<T> overlapsList = new List<T>();
 
-            lock (_items)
+            ulong endAddress = address + size;
+
+            int index = BinarySearch(address, size);
+
+            if (index >= 0)
             {
-                int index = BinarySearch(address);
+                while (index > 0 && _items[index - 1].OverlapsWith(address, size))
+                {
+                    index--;
+                }
 
-                if (index >= 0)
+                do
                 {
-                    while (index > 0 && _items[index - 1].Address == address)
-                    {
-                        index--;
-                    }
+                    overlapsList.Add(_items[index++]);
+                }
+                while (index < _items.Count && _items[index].OverlapsWith(address, size));
+            }
 
-                    while (index < _items.Count)
-                    {
-                        T overlap = _items[index++];
+            return overlapsList.ToArray();
+        }
+
+        public T[] FindOverlaps(ulong address)
+        {
+            List<T> overlapsList = new List<T>();
 
-                        if (overlap.Address != address)
-                        {
-                            break;
-                        }
+            int index = BinarySearch(address);
 
-                        overlapsList.Add(overlap);
+            if (index >= 0)
+            {
+                while (index > 0 && _items[index - 1].Address == address)
+                {
+                    index--;
+                }
+
+                while (index < _items.Count)
+                {
+                    T overlap = _items[index++];
+
+                    if (overlap.Address != address)
+                    {
+                        break;
                     }
+
+                    overlapsList.Add(overlap);
                 }
             }