diff options
| -rw-r--r-- | Ryujinx.Graphics.Gpu/Memory/BufferModifiedRangeList.cs | 2 | ||||
| -rw-r--r-- | Ryujinx.Memory/Range/RangeList.cs | 164 | ||||
| -rw-r--r-- | Ryujinx.Memory/WindowsShared/EmulatedSharedMemoryWindows.cs | 13 | ||||
| -rw-r--r-- | Ryujinx.Memory/WindowsShared/PlaceholderList.cs | 12 |
4 files changed, 149 insertions, 42 deletions
diff --git a/Ryujinx.Graphics.Gpu/Memory/BufferModifiedRangeList.cs b/Ryujinx.Graphics.Gpu/Memory/BufferModifiedRangeList.cs index 9e5c5e84..63227431 100644 --- a/Ryujinx.Graphics.Gpu/Memory/BufferModifiedRangeList.cs +++ b/Ryujinx.Graphics.Gpu/Memory/BufferModifiedRangeList.cs @@ -365,7 +365,7 @@ namespace Ryujinx.Graphics.Gpu.Memory { lock (_lock) { - Items.Clear(); + Count = 0; } } } diff --git a/Ryujinx.Memory/Range/RangeList.cs b/Ryujinx.Memory/Range/RangeList.cs index fd260656..d82a05c5 100644 --- a/Ryujinx.Memory/Range/RangeList.cs +++ b/Ryujinx.Memory/Range/RangeList.cs @@ -1,6 +1,7 @@ using System; using System.Collections; using System.Collections.Generic; +using System.Runtime.CompilerServices; namespace Ryujinx.Memory.Range { @@ -10,18 +11,40 @@ namespace Ryujinx.Memory.Range /// <typeparam name="T">Type of the range.</typeparam> public class RangeList<T> : IEnumerable<T> where T : IRange { - private const int ArrayGrowthSize = 32; + private readonly struct RangeItem<TValue> where TValue : IRange + { + public readonly ulong Address; + public readonly ulong EndAddress; + + public readonly TValue Value; + + public RangeItem(TValue value) + { + Value = value; + + Address = value.Address; + EndAddress = value.Address + value.Size; + } + + [MethodImpl(MethodImplOptions.AggressiveInlining)] + public bool OverlapsWith(ulong address, ulong endAddress) + { + return Address < endAddress && address < EndAddress; + } + } - protected readonly List<T> Items; + private const int ArrayGrowthSize = 32; + private const int BackingGrowthSize = 1024; - public int Count => Items.Count; + private RangeItem<T>[] _items; + public int Count { get; protected set; } /// <summary> /// Creates a new range list. /// </summary> public RangeList() { - Items = new List<T>(); + _items = new RangeItem<T>[BackingGrowthSize]; } /// <summary> @@ -37,7 +60,40 @@ namespace Ryujinx.Memory.Range index = ~index; } - Items.Insert(index, item); + Insert(index, new RangeItem<T>(item)); + } + + [MethodImpl(MethodImplOptions.AggressiveInlining)] + private void Insert(int index, RangeItem<T> item) + { + if (Count + 1 > _items.Length) + { + Array.Resize(ref _items, _items.Length + ArrayGrowthSize); + } + + if (index >= Count) + { + if (index == Count) + { + _items[Count++] = item; + } + } + else + { + Array.Copy(_items, index, _items, index + 1, Count - index); + + _items[index] = item; + Count++; + } + } + + [MethodImpl(MethodImplOptions.AggressiveInlining)] + private void RemoveAt(int index) + { + if (index < --Count) + { + Array.Copy(_items, index + 1, _items, index, Count - index); + } } /// <summary> @@ -51,21 +107,21 @@ namespace Ryujinx.Memory.Range if (index >= 0) { - while (index > 0 && Items[index - 1].Address == item.Address) + while (index > 0 && _items[index - 1].Address == item.Address) { index--; } - while (index < Items.Count) + while (index < Count) { - if (Items[index].Equals(item)) + if (_items[index].Value.Equals(item)) { - Items.RemoveAt(index); + RemoveAt(index); return true; } - if (Items[index].Address > item.Address) + if (_items[index].Address > item.Address) { break; } @@ -78,6 +134,40 @@ namespace Ryujinx.Memory.Range } /// <summary> + /// Updates an item's end address. + /// </summary> + /// <param name="item">The item to be updated</param> + public void UpdateEndAddress(T item) + { + int index = BinarySearch(item.Address); + + if (index >= 0) + { + while (index > 0 && _items[index - 1].Address == item.Address) + { + index--; + } + + while (index < Count) + { + if (_items[index].Value.Equals(item)) + { + _items[index] = new RangeItem<T>(item); + + return; + } + + if (_items[index].Address > item.Address) + { + break; + } + + index++; + } + } + } + + /// <summary> /// Gets the first item on the list overlapping in memory with the specified item. /// </summary> /// <remarks> @@ -103,14 +193,14 @@ namespace Ryujinx.Memory.Range /// <returns>The overlapping item, or the default value for the type if none found</returns> public T FindFirstOverlap(ulong address, ulong size) { - int index = BinarySearch(address, size); + int index = BinarySearch(address, address + size); if (index < 0) { return default(T); } - return Items[index]; + return _items[index].Value; } /// <summary> @@ -137,21 +227,23 @@ namespace Ryujinx.Memory.Range ulong endAddress = address + size; - foreach (T item in Items) + for (int i = 0; i < Count; i++) { + ref RangeItem<T> item = ref _items[i]; + if (item.Address >= endAddress) { break; } - if (item.OverlapsWith(address, size)) + if (item.OverlapsWith(address, endAddress)) { if (outputIndex == output.Length) { Array.Resize(ref output, outputIndex + ArrayGrowthSize); } - output[outputIndex++] = item; + output[outputIndex++] = item.Value; } } @@ -192,11 +284,13 @@ namespace Ryujinx.Memory.Range // when none of the items on the list overlaps with each other. int outputIndex = 0; - int index = BinarySearch(address, size); + ulong endAddress = address + size; + + int index = BinarySearch(address, endAddress); if (index >= 0) { - while (index > 0 && Items[index - 1].OverlapsWith(address, size)) + while (index > 0 && _items[index - 1].OverlapsWith(address, endAddress)) { index--; } @@ -208,9 +302,9 @@ namespace Ryujinx.Memory.Range Array.Resize(ref output, outputIndex + ArrayGrowthSize); } - output[outputIndex++] = Items[index++]; + output[outputIndex++] = _items[index++].Value; } - while (index < Items.Count && Items[index].OverlapsWith(address, size)); + while (index < Count && _items[index].OverlapsWith(address, endAddress)); } return outputIndex; @@ -230,14 +324,14 @@ namespace Ryujinx.Memory.Range if (index >= 0) { - while (index > 0 && Items[index - 1].Address == address) + while (index > 0 && _items[index - 1].Address == address) { index--; } - while (index < Items.Count) + while (index < Count) { - T overlap = Items[index++]; + ref RangeItem<T> overlap = ref _items[index++]; if (overlap.Address != address) { @@ -249,7 +343,7 @@ namespace Ryujinx.Memory.Range Array.Resize(ref output, outputIndex + ArrayGrowthSize); } - output[outputIndex++] = overlap; + output[outputIndex++] = overlap.Value; } } @@ -264,7 +358,7 @@ namespace Ryujinx.Memory.Range private int BinarySearch(ulong address) { int left = 0; - int right = Items.Count - 1; + int right = Count - 1; while (left <= right) { @@ -272,7 +366,7 @@ namespace Ryujinx.Memory.Range int middle = left + (range >> 1); - T item = Items[middle]; + ref RangeItem<T> item = ref _items[middle]; if (item.Address == address) { @@ -296,12 +390,12 @@ namespace Ryujinx.Memory.Range /// Performs binary search for items overlapping a given memory range. /// </summary> /// <param name="address">Start address of the range</param> - /// <param name="size">Size in bytes of the range</param> + /// <param name="endAddress">End address of the range</param> /// <returns>List index of the item, or complement index of nearest item with lower value on the list</returns> - private int BinarySearch(ulong address, ulong size) + private int BinarySearch(ulong address, ulong endAddress) { int left = 0; - int right = Items.Count - 1; + int right = Count - 1; while (left <= right) { @@ -309,9 +403,9 @@ namespace Ryujinx.Memory.Range int middle = left + (range >> 1); - T item = Items[middle]; + ref RangeItem<T> item = ref _items[middle]; - if (item.OverlapsWith(address, size)) + if (item.OverlapsWith(address, endAddress)) { return middle; } @@ -331,12 +425,18 @@ namespace Ryujinx.Memory.Range public IEnumerator<T> GetEnumerator() { - return Items.GetEnumerator(); + for (int i = 0; i < Count; i++) + { + yield return _items[i].Value; + } } IEnumerator IEnumerable.GetEnumerator() { - return Items.GetEnumerator(); + for (int i = 0; i < Count; i++) + { + yield return _items[i].Value; + } } } }
\ No newline at end of file diff --git a/Ryujinx.Memory/WindowsShared/EmulatedSharedMemoryWindows.cs b/Ryujinx.Memory/WindowsShared/EmulatedSharedMemoryWindows.cs index 46399504..1417f7d5 100644 --- a/Ryujinx.Memory/WindowsShared/EmulatedSharedMemoryWindows.cs +++ b/Ryujinx.Memory/WindowsShared/EmulatedSharedMemoryWindows.cs @@ -41,10 +41,12 @@ namespace Ryujinx.Memory.WindowsShared return Address < address + size && address < EndAddress; } - public void ExtendTo(ulong endAddress) + public void ExtendTo(ulong endAddress, RangeList<SharedMemoryMapping> list) { EndAddress = endAddress; Size = endAddress - Address; + + list.UpdateEndAddress(this); } public void AddBlocks(IEnumerable<int> blocks) @@ -300,14 +302,14 @@ namespace Ryujinx.Memory.WindowsShared _mappings.Remove(endOverlap); - startOverlap.ExtendTo(endOverlap.EndAddress); + startOverlap.ExtendTo(endOverlap.EndAddress, _mappings); startOverlap.AddBlocks(blocks); startOverlap.AddBlocks(endOverlap.Blocks); } else if (startOverlap != null) { - startOverlap.ExtendTo(endAddress); + startOverlap.ExtendTo(endAddress, _mappings); startOverlap.AddBlocks(blocks); } @@ -317,7 +319,7 @@ namespace Ryujinx.Memory.WindowsShared if (endOverlap != null) { - mapping.ExtendTo(endOverlap.EndAddress); + mapping.ExtendTo(endOverlap.EndAddress, _mappings); mapping.AddBlocks(endOverlap.Blocks); @@ -381,6 +383,7 @@ namespace Ryujinx.Memory.WindowsShared if (mapping.EndAddress > endAddress) { var newMapping = (SharedMemoryMapping)mapping.Split(endAddress); + _mappings.UpdateEndAddress(mapping); _mappings.Add(newMapping); if ((endAddress & MappingMask) != 0) @@ -400,7 +403,9 @@ namespace Ryujinx.Memory.WindowsShared // If the first region starts before the decommit address, split it by modifying its end address. if (mapping.Address < address) { + var oldMapping = mapping; mapping = (SharedMemoryMapping)mapping.Split(address); + _mappings.UpdateEndAddress(oldMapping); if ((address & MappingMask) != 0) { diff --git a/Ryujinx.Memory/WindowsShared/PlaceholderList.cs b/Ryujinx.Memory/WindowsShared/PlaceholderList.cs index be8cef9c..848e410e 100644 --- a/Ryujinx.Memory/WindowsShared/PlaceholderList.cs +++ b/Ryujinx.Memory/WindowsShared/PlaceholderList.cs @@ -32,10 +32,12 @@ namespace Ryujinx.Memory.WindowsShared return Address < address + size && address < EndAddress; } - public void ExtendTo(ulong end) + public void ExtendTo(ulong end, RangeList<PlaceholderBlock> list) { EndAddress = end; Size = end - Address; + + list.UpdateEndAddress(this); } } @@ -126,13 +128,13 @@ namespace Ryujinx.Memory.WindowsShared if (overlapStart && first.IsGranular) { - first.ExtendTo(endId); + first.ExtendTo(endId, _placeholders); } else { if (overlapStart) { - first.ExtendTo(id); + first.ExtendTo(id, _placeholders); } _placeholders.Add(new PlaceholderBlock(id, endId - id, true)); @@ -189,7 +191,7 @@ namespace Ryujinx.Memory.WindowsShared if (block.Address < id && blockEnd > id) { - block.ExtendTo(id); + block.ExtendTo(id, _placeholders); extendBlock = null; } else @@ -223,7 +225,7 @@ namespace Ryujinx.Memory.WindowsShared else { extendFrom = extendBlock.Address; - extendBlock.ExtendTo(block.IsGranular ? extent : block.EndAddress); + extendBlock.ExtendTo(block.IsGranular ? extent : block.EndAddress, _placeholders); } if (block.IsGranular) |