Use a more efficient range list on the buffer manager

4 files changed, 301 insertions, 55 deletions

diff --git a/Ryujinx.Graphics.Gpu/Image/TextureManager.cs b/Ryujinx.Graphics.Gpu/Image/TextureManager.cs
index 2db1b4f2..d4c161bd 100644
--- a/Ryujinx.Graphics.Gpu/Image/TextureManager.cs
+++ b/Ryujinx.Graphics.Gpu/Image/TextureManager.cs
@@ -22,7 +22,7 @@ namespace Ryujinx.Graphics.Gpu.Image
         private ITexture[] _rtHostColors;
         private ITexture   _rtHostDs;
 
-        private RangeList<Texture> _textures;
+        private ConcurrentRangeList<Texture> _textures;
 
         private AutoDeleteCache _cache;
 
@@ -37,7 +37,7 @@ namespace Ryujinx.Graphics.Gpu.Image
 
             _rtHostColors = new ITexture[Constants.TotalRenderTargets];
 
-            _textures = new RangeList<Texture>();
+            _textures = new ConcurrentRangeList<Texture>();
 
             _cache = new AutoDeleteCache();
         }
diff --git a/Ryujinx.Graphics.Gpu/Memory/BufferManager.cs b/Ryujinx.Graphics.Gpu/Memory/BufferManager.cs
index c4240061..1431bf41 100644
--- a/Ryujinx.Graphics.Gpu/Memory/BufferManager.cs
+++ b/Ryujinx.Graphics.Gpu/Memory/BufferManager.cs
@@ -198,7 +198,7 @@ namespace Ryujinx.Graphics.Gpu.Memory
 
         private void CreateBuffer(ulong address, ulong size)
         {
-            Buffer[] overlaps = _buffers.FindOverlaps(address, size);
+            Buffer[] overlaps = _buffers.FindOverlapsNonOverlapping(address, size);
 
             if (overlaps.Length != 0)
             {
diff --git a/Ryujinx.Graphics.Gpu/Memory/ConcurrentRangeList.cs b/Ryujinx.Graphics.Gpu/Memory/ConcurrentRangeList.cs
new file mode 100644
index 00000000..7bcb011c
--- /dev/null
+++ b/Ryujinx.Graphics.Gpu/Memory/ConcurrentRangeList.cs
@@ -0,0 +1,210 @@
+using System.Collections.Generic;
+
+namespace Ryujinx.Graphics.Gpu.Memory
+{
+    class ConcurrentRangeList<T> where T : IRange<T>
+    {
+        private List<T> _items;
+
+        public int Count => _items.Count;
+
+        public ConcurrentRangeList()
+        {
+            _items = new List<T>();
+        }
+
+        public void Add(T item)
+        {
+            lock (_items)
+            {
+                int index = BinarySearch(item.Address);
+
+                if (index < 0)
+                {
+                    index = ~index;
+                }
+
+                _items.Insert(index, item);
+            }
+        }
+
+        public bool Remove(T item)
+        {
+            lock (_items)
+            {
+                int index = BinarySearch(item.Address);
+
+                if (index >= 0)
+                {
+                    while (index > 0 && _items[index - 1].Address == item.Address)
+                    {
+                        index--;
+                    }
+
+                    while (index < _items.Count)
+                    {
+                        if (_items[index].Equals(item))
+                        {
+                            _items.RemoveAt(index);
+
+                            return true;
+                        }
+
+                        if (_items[index].Address > item.Address)
+                        {
+                            break;
+                        }
+
+                        index++;
+                    }
+                }
+            }
+
+            return false;
+        }
+
+        public T FindFirstOverlap(T item)
+        {
+            return FindFirstOverlap(item.Address, item.Size);
+        }
+
+        public T FindFirstOverlap(ulong address, ulong size)
+        {
+            lock (_items)
+            {
+                int index = BinarySearch(address, size);
+
+                if (index < 0)
+                {
+                    return default(T);
+                }
+
+                return _items[index];
+            }
+        }
+
+        public T[] FindOverlaps(T item)
+        {
+            return FindOverlaps(item.Address, item.Size);
+        }
+
+        public T[] FindOverlaps(ulong address, ulong size)
+        {
+            List<T> overlapsList = new List<T>();
+
+            ulong endAddress = address + size;
+
+            lock (_items)
+            {
+                foreach (T item in _items)
+                {
+                    if (item.Address >= endAddress)
+                    {
+                        break;
+                    }
+
+                    if (item.OverlapsWith(address, size))
+                    {
+                        overlapsList.Add(item);
+                    }
+                }
+            }
+
+            return overlapsList.ToArray();
+        }
+
+        public T[] FindOverlaps(ulong address)
+        {
+            List<T> overlapsList = new List<T>();
+
+            lock (_items)
+            {
+                int index = BinarySearch(address);
+
+                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);
+                    }
+                }
+            }
+
+            return overlapsList.ToArray();
+        }
+
+        private int BinarySearch(ulong address)
+        {
+            int left  = 0;
+            int right = _items.Count - 1;
+
+            while (left <= right)
+            {
+                int range = right - left;
+
+                int middle = left + (range >> 1);
+
+                T item = _items[middle];
+
+                if (item.Address == address)
+                {
+                    return middle;
+                }
+
+                if (address < item.Address)
+                {
+                    right = middle - 1;
+                }
+                else
+                {
+                    left = middle + 1;
+                }
+            }
+
+            return ~left;
+        }
+
+        private int BinarySearch(ulong address, ulong size)
+        {
+            int left  = 0;
+            int right = _items.Count - 1;
+
+            while (left <= right)
+            {
+                int range = right - left;
+
+                int middle = left + (range >> 1);
+
+                T item = _items[middle];
+
+                if (item.OverlapsWith(address, size))
+                {
+                    return middle;
+                }
+
+                if (address < item.Address)
+                {
+                    right = middle - 1;
+                }
+                else
+                {
+                    left = middle + 1;
+                }
+            }
+
+            return ~left;
+        }
+    }
+}
\ No newline at end of file
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);
                 }
             }