From cee712105850ac3385cd0091a923438167433f9f Mon Sep 17 00:00:00 2001
From: TSR Berry <20988865+TSRBerry@users.noreply.github.com>
Date: Sat, 8 Apr 2023 01:22:00 +0200
Subject: Move solution and projects to src
---
src/Ryujinx.Memory/Range/HostMemoryRange.cs | 71 +++
src/Ryujinx.Memory/Range/IMultiRangeItem.cs | 9 +
src/Ryujinx.Memory/Range/INonOverlappingRange.cs | 16 +
src/Ryujinx.Memory/Range/IRange.cs | 31 ++
src/Ryujinx.Memory/Range/MemoryRange.cs | 61 +++
src/Ryujinx.Memory/Range/MultiRange.cs | 323 ++++++++++++++
src/Ryujinx.Memory/Range/MultiRangeList.cs | 210 +++++++++
.../Range/NonOverlappingRangeList.cs | 106 +++++
src/Ryujinx.Memory/Range/RangeList.cs | 483 +++++++++++++++++++++
9 files changed, 1310 insertions(+)
create mode 100644 src/Ryujinx.Memory/Range/HostMemoryRange.cs
create mode 100644 src/Ryujinx.Memory/Range/IMultiRangeItem.cs
create mode 100644 src/Ryujinx.Memory/Range/INonOverlappingRange.cs
create mode 100644 src/Ryujinx.Memory/Range/IRange.cs
create mode 100644 src/Ryujinx.Memory/Range/MemoryRange.cs
create mode 100644 src/Ryujinx.Memory/Range/MultiRange.cs
create mode 100644 src/Ryujinx.Memory/Range/MultiRangeList.cs
create mode 100644 src/Ryujinx.Memory/Range/NonOverlappingRangeList.cs
create mode 100644 src/Ryujinx.Memory/Range/RangeList.cs
(limited to 'src/Ryujinx.Memory/Range')
diff --git a/src/Ryujinx.Memory/Range/HostMemoryRange.cs b/src/Ryujinx.Memory/Range/HostMemoryRange.cs
new file mode 100644
index 00000000..79c649d8
--- /dev/null
+++ b/src/Ryujinx.Memory/Range/HostMemoryRange.cs
@@ -0,0 +1,71 @@
+using System;
+
+namespace Ryujinx.Memory.Range
+{
+ ///
+ /// Range of memory composed of an address and size.
+ ///
+ public struct HostMemoryRange : IEquatable
+ {
+ ///
+ /// An empty memory range, with a null address and zero size.
+ ///
+ public static HostMemoryRange Empty => new HostMemoryRange(0, 0);
+
+ ///
+ /// Start address of the range.
+ ///
+ public nuint Address { get; }
+
+ ///
+ /// Size of the range in bytes.
+ ///
+ public ulong Size { get; }
+
+ ///
+ /// Address where the range ends (exclusive).
+ ///
+ public nuint EndAddress => Address + (nuint)Size;
+
+ ///
+ /// Creates a new memory range with the specified address and size.
+ ///
+ /// Start address
+ /// Size in bytes
+ public HostMemoryRange(nuint address, ulong size)
+ {
+ Address = address;
+ Size = size;
+ }
+
+ ///
+ /// Checks if the range overlaps with another.
+ ///
+ /// The other range to check for overlap
+ /// True if the ranges overlap, false otherwise
+ public bool OverlapsWith(HostMemoryRange other)
+ {
+ nuint thisAddress = Address;
+ nuint thisEndAddress = EndAddress;
+ nuint otherAddress = other.Address;
+ nuint otherEndAddress = other.EndAddress;
+
+ return thisAddress < otherEndAddress && otherAddress < thisEndAddress;
+ }
+
+ public override bool Equals(object obj)
+ {
+ return obj is HostMemoryRange other && Equals(other);
+ }
+
+ public bool Equals(HostMemoryRange other)
+ {
+ return Address == other.Address && Size == other.Size;
+ }
+
+ public override int GetHashCode()
+ {
+ return HashCode.Combine(Address, Size);
+ }
+ }
+}
diff --git a/src/Ryujinx.Memory/Range/IMultiRangeItem.cs b/src/Ryujinx.Memory/Range/IMultiRangeItem.cs
new file mode 100644
index 00000000..e95a69fc
--- /dev/null
+++ b/src/Ryujinx.Memory/Range/IMultiRangeItem.cs
@@ -0,0 +1,9 @@
+namespace Ryujinx.Memory.Range
+{
+ public interface IMultiRangeItem
+ {
+ MultiRange Range { get; }
+
+ ulong BaseAddress => Range.GetSubRange(0).Address;
+ }
+}
diff --git a/src/Ryujinx.Memory/Range/INonOverlappingRange.cs b/src/Ryujinx.Memory/Range/INonOverlappingRange.cs
new file mode 100644
index 00000000..1886eb1d
--- /dev/null
+++ b/src/Ryujinx.Memory/Range/INonOverlappingRange.cs
@@ -0,0 +1,16 @@
+namespace Ryujinx.Memory.Range
+{
+ ///
+ /// Range of memory that can be split in two.
+ ///
+ interface INonOverlappingRange : IRange
+ {
+ ///
+ /// Split this region into two, around the specified address.
+ /// This region is updated to end at the split address, and a new region is created to represent past that point.
+ ///
+ /// Address to split the region around
+ /// The second part of the split region, with start address at the given split.
+ public INonOverlappingRange Split(ulong splitAddress);
+ }
+}
diff --git a/src/Ryujinx.Memory/Range/IRange.cs b/src/Ryujinx.Memory/Range/IRange.cs
new file mode 100644
index 00000000..1685396d
--- /dev/null
+++ b/src/Ryujinx.Memory/Range/IRange.cs
@@ -0,0 +1,31 @@
+namespace Ryujinx.Memory.Range
+{
+ ///
+ /// Range of memory.
+ ///
+ public interface IRange
+ {
+ ///
+ /// Base address.
+ ///
+ ulong Address { get; }
+
+ ///
+ /// Size of the range.
+ ///
+ ulong Size { get; }
+
+ ///
+ /// End address.
+ ///
+ ulong EndAddress { get; }
+
+ ///
+ /// Check if this range overlaps with another.
+ ///
+ /// Base address
+ /// Size of the range
+ /// True if overlapping, false otherwise
+ bool OverlapsWith(ulong address, ulong size);
+ }
+}
\ No newline at end of file
diff --git a/src/Ryujinx.Memory/Range/MemoryRange.cs b/src/Ryujinx.Memory/Range/MemoryRange.cs
new file mode 100644
index 00000000..7465fbcb
--- /dev/null
+++ b/src/Ryujinx.Memory/Range/MemoryRange.cs
@@ -0,0 +1,61 @@
+namespace Ryujinx.Memory.Range
+{
+ ///
+ /// Range of memory composed of an address and size.
+ ///
+ public readonly record struct MemoryRange
+ {
+ ///
+ /// An empty memory range, with a null address and zero size.
+ ///
+ public static MemoryRange Empty => new MemoryRange(0UL, 0);
+
+ ///
+ /// Start address of the range.
+ ///
+ public ulong Address { get; }
+
+ ///
+ /// Size of the range in bytes.
+ ///
+ public ulong Size { get; }
+
+ ///
+ /// Address where the range ends (exclusive).
+ ///
+ public ulong EndAddress => Address + Size;
+
+ ///
+ /// Creates a new memory range with the specified address and size.
+ ///
+ /// Start address
+ /// Size in bytes
+ public MemoryRange(ulong address, ulong size)
+ {
+ Address = address;
+ Size = size;
+ }
+
+ ///
+ /// Checks if the range overlaps with another.
+ ///
+ /// The other range to check for overlap
+ /// True if the ranges overlap, false otherwise
+ public bool OverlapsWith(MemoryRange other)
+ {
+ ulong thisAddress = Address;
+ ulong thisEndAddress = EndAddress;
+ ulong otherAddress = other.Address;
+ ulong otherEndAddress = other.EndAddress;
+
+ // If any of the ranges if invalid (address + size overflows),
+ // then they are never considered to overlap.
+ if (thisEndAddress < thisAddress || otherEndAddress < otherAddress)
+ {
+ return false;
+ }
+
+ return thisAddress < otherEndAddress && otherAddress < thisEndAddress;
+ }
+ }
+}
diff --git a/src/Ryujinx.Memory/Range/MultiRange.cs b/src/Ryujinx.Memory/Range/MultiRange.cs
new file mode 100644
index 00000000..9dbd76ec
--- /dev/null
+++ b/src/Ryujinx.Memory/Range/MultiRange.cs
@@ -0,0 +1,323 @@
+using System;
+using System.Collections.Generic;
+
+namespace Ryujinx.Memory.Range
+{
+ ///
+ /// Sequence of physical memory regions that a single non-contiguous virtual memory region maps to.
+ ///
+ public readonly struct MultiRange : IEquatable
+ {
+ private const ulong InvalidAddress = ulong.MaxValue;
+
+ private readonly MemoryRange _singleRange;
+ private readonly MemoryRange[] _ranges;
+
+ private bool HasSingleRange => _ranges == null;
+
+ ///
+ /// Total of physical sub-ranges on the virtual memory region.
+ ///
+ public int Count => HasSingleRange ? 1 : _ranges.Length;
+
+ ///
+ /// Creates a new multi-range with a single physical region.
+ ///
+ /// Start address of the region
+ /// Size of the region in bytes
+ public MultiRange(ulong address, ulong size)
+ {
+ _singleRange = new MemoryRange(address, size);
+ _ranges = null;
+ }
+
+ ///
+ /// Creates a new multi-range with multiple physical regions.
+ ///
+ /// Array of physical regions
+ /// is null
+ public MultiRange(MemoryRange[] ranges)
+ {
+ _singleRange = MemoryRange.Empty;
+ _ranges = ranges ?? throw new ArgumentNullException(nameof(ranges));
+ }
+
+ ///
+ /// Gets a slice of the multi-range.
+ ///
+ /// Offset of the slice into the multi-range in bytes
+ /// Size of the slice in bytes
+ /// A new multi-range representing the given slice of this one
+ public MultiRange Slice(ulong offset, ulong size)
+ {
+ if (HasSingleRange)
+ {
+ if (_singleRange.Size - offset < size)
+ {
+ throw new ArgumentOutOfRangeException(nameof(size));
+ }
+
+ return new MultiRange(_singleRange.Address + offset, size);
+ }
+ else
+ {
+ var ranges = new List();
+
+ foreach (MemoryRange range in _ranges)
+ {
+ if ((long)offset <= 0)
+ {
+ ranges.Add(new MemoryRange(range.Address, Math.Min(size, range.Size)));
+ size -= range.Size;
+ }
+ else if (offset < range.Size)
+ {
+ ulong sliceSize = Math.Min(size, range.Size - offset);
+
+ if (range.Address == InvalidAddress)
+ {
+ ranges.Add(new MemoryRange(range.Address, sliceSize));
+ }
+ else
+ {
+ ranges.Add(new MemoryRange(range.Address + offset, sliceSize));
+ }
+
+ size -= sliceSize;
+ }
+
+ if ((long)size <= 0)
+ {
+ break;
+ }
+
+ offset -= range.Size;
+ }
+
+ return new MultiRange(ranges.ToArray());
+ }
+ }
+
+ ///
+ /// Gets the physical region at the specified index.
+ ///
+ /// Index of the physical region
+ /// Region at the index specified
+ /// is invalid
+ public MemoryRange GetSubRange(int index)
+ {
+ if (HasSingleRange)
+ {
+ if (index != 0)
+ {
+ throw new ArgumentOutOfRangeException(nameof(index));
+ }
+
+ return _singleRange;
+ }
+ else
+ {
+ if ((uint)index >= _ranges.Length)
+ {
+ throw new ArgumentOutOfRangeException(nameof(index));
+ }
+
+ return _ranges[index];
+ }
+ }
+
+ ///
+ /// Gets the physical region at the specified index, without explicit bounds checking.
+ ///
+ /// Index of the physical region
+ /// Region at the index specified
+ private MemoryRange GetSubRangeUnchecked(int index)
+ {
+ return HasSingleRange ? _singleRange : _ranges[index];
+ }
+
+ ///
+ /// Check if two multi-ranges overlap with each other.
+ ///
+ /// Other multi-range to check for overlap
+ /// True if any sub-range overlaps, false otherwise
+ public bool OverlapsWith(MultiRange other)
+ {
+ if (HasSingleRange && other.HasSingleRange)
+ {
+ return _singleRange.OverlapsWith(other._singleRange);
+ }
+ else
+ {
+ for (int i = 0; i < Count; i++)
+ {
+ MemoryRange currentRange = GetSubRangeUnchecked(i);
+
+ for (int j = 0; j < other.Count; j++)
+ {
+ if (currentRange.OverlapsWith(other.GetSubRangeUnchecked(j)))
+ {
+ return true;
+ }
+ }
+ }
+ }
+
+ return false;
+ }
+
+ ///
+ /// Checks if a given multi-range is fully contained inside another.
+ ///
+ /// Multi-range to be checked
+ /// True if all the sub-ranges on are contained inside the multi-range, with the same order, false otherwise
+ public bool Contains(MultiRange other)
+ {
+ return FindOffset(other) >= 0;
+ }
+
+ ///
+ /// Calculates the offset of a given multi-range inside another, when the multi-range is fully contained
+ /// inside the other multi-range, otherwise returns -1.
+ ///
+ /// Multi-range that should be fully contained inside this one
+ /// Offset in bytes if fully contained, otherwise -1
+ public int FindOffset(MultiRange other)
+ {
+ int thisCount = Count;
+ int otherCount = other.Count;
+
+ if (thisCount == 1 && otherCount == 1)
+ {
+ MemoryRange otherFirstRange = other.GetSubRangeUnchecked(0);
+ MemoryRange currentFirstRange = GetSubRangeUnchecked(0);
+
+ if (otherFirstRange.Address >= currentFirstRange.Address &&
+ otherFirstRange.EndAddress <= currentFirstRange.EndAddress)
+ {
+ return (int)(otherFirstRange.Address - currentFirstRange.Address);
+ }
+ }
+ else if (thisCount >= otherCount)
+ {
+ ulong baseOffset = 0;
+
+ MemoryRange otherFirstRange = other.GetSubRangeUnchecked(0);
+ MemoryRange otherLastRange = other.GetSubRangeUnchecked(otherCount - 1);
+
+ for (int i = 0; i < (thisCount - otherCount) + 1; baseOffset += GetSubRangeUnchecked(i).Size, i++)
+ {
+ MemoryRange currentFirstRange = GetSubRangeUnchecked(i);
+ MemoryRange currentLastRange = GetSubRangeUnchecked(i + otherCount - 1);
+
+ if (otherCount > 1)
+ {
+ if (otherFirstRange.Address < currentFirstRange.Address ||
+ otherFirstRange.EndAddress != currentFirstRange.EndAddress)
+ {
+ continue;
+ }
+
+ if (otherLastRange.Address != currentLastRange.Address ||
+ otherLastRange.EndAddress > currentLastRange.EndAddress)
+ {
+ continue;
+ }
+
+ bool fullMatch = true;
+
+ for (int j = 1; j < otherCount - 1; j++)
+ {
+ if (!GetSubRangeUnchecked(i + j).Equals(other.GetSubRangeUnchecked(j)))
+ {
+ fullMatch = false;
+ break;
+ }
+ }
+
+ if (!fullMatch)
+ {
+ continue;
+ }
+ }
+ else if (currentFirstRange.Address > otherFirstRange.Address ||
+ currentFirstRange.EndAddress < otherFirstRange.EndAddress)
+ {
+ continue;
+ }
+
+ return (int)(baseOffset + (otherFirstRange.Address - currentFirstRange.Address));
+ }
+ }
+
+ return -1;
+ }
+
+ ///
+ /// Gets the total size of all sub-ranges in bytes.
+ ///
+ /// Total size in bytes
+ public ulong GetSize()
+ {
+ if (HasSingleRange)
+ {
+ return _singleRange.Size;
+ }
+
+ ulong sum = 0;
+
+ foreach (MemoryRange range in _ranges)
+ {
+ sum += range.Size;
+ }
+
+ return sum;
+ }
+
+ public override bool Equals(object obj)
+ {
+ return obj is MultiRange other && Equals(other);
+ }
+
+ public bool Equals(MultiRange other)
+ {
+ if (HasSingleRange && other.HasSingleRange)
+ {
+ return _singleRange.Equals(other._singleRange);
+ }
+
+ int thisCount = Count;
+ if (thisCount != other.Count)
+ {
+ return false;
+ }
+
+ for (int i = 0; i < thisCount; i++)
+ {
+ if (!GetSubRangeUnchecked(i).Equals(other.GetSubRangeUnchecked(i)))
+ {
+ return false;
+ }
+ }
+
+ return true;
+ }
+
+ public override int GetHashCode()
+ {
+ if (HasSingleRange)
+ {
+ return _singleRange.GetHashCode();
+ }
+
+ HashCode hash = new HashCode();
+
+ foreach (MemoryRange range in _ranges)
+ {
+ hash.Add(range);
+ }
+
+ return hash.ToHashCode();
+ }
+ }
+}
diff --git a/src/Ryujinx.Memory/Range/MultiRangeList.cs b/src/Ryujinx.Memory/Range/MultiRangeList.cs
new file mode 100644
index 00000000..5131889f
--- /dev/null
+++ b/src/Ryujinx.Memory/Range/MultiRangeList.cs
@@ -0,0 +1,210 @@
+using Ryujinx.Common.Collections;
+using System.Collections;
+using System.Collections.Generic;
+
+namespace Ryujinx.Memory.Range
+{
+ public class MultiRangeList : IEnumerable where T : IMultiRangeItem
+ {
+ private readonly IntervalTree _items;
+
+ public int Count { get; private set; }
+
+ ///
+ /// Creates a new range list.
+ ///
+ public MultiRangeList()
+ {
+ _items = new IntervalTree();
+ }
+
+ ///
+ /// Adds a new item to the list.
+ ///
+ /// The item to be added
+ public void Add(T item)
+ {
+ MultiRange range = item.Range;
+
+ for (int i = 0; i < range.Count; i++)
+ {
+ var subrange = range.GetSubRange(i);
+
+ if (IsInvalid(ref subrange))
+ {
+ continue;
+ }
+
+ _items.Add(subrange.Address, subrange.EndAddress, item);
+ }
+
+ Count++;
+ }
+
+ ///
+ /// Removes an item from the list.
+ ///
+ /// The item to be removed
+ /// True if the item was removed, or false if it was not found
+ public bool Remove(T item)
+ {
+ MultiRange range = item.Range;
+
+ int removed = 0;
+
+ for (int i = 0; i < range.Count; i++)
+ {
+ var subrange = range.GetSubRange(i);
+
+ if (IsInvalid(ref subrange))
+ {
+ continue;
+ }
+
+ removed += _items.Remove(subrange.Address, item);
+ }
+
+ if (removed > 0)
+ {
+ // All deleted intervals are for the same item - the one we removed.
+ Count--;
+ }
+
+ return removed > 0;
+ }
+
+ ///
+ /// Gets all items on the list overlapping the specified memory range.
+ ///
+ /// Start address of the range
+ /// Size in bytes of the range
+ /// Output array where matches will be written. It is automatically resized to fit the results
+ /// The number of overlapping items found
+ public int FindOverlaps(ulong address, ulong size, ref T[] output)
+ {
+ return FindOverlaps(new MultiRange(address, size), ref output);
+ }
+
+ ///
+ /// Gets all items on the list overlapping the specified memory ranges.
+ ///
+ /// Ranges of memory being searched
+ /// Output array where matches will be written. It is automatically resized to fit the results
+ /// The number of overlapping items found
+ public int FindOverlaps(MultiRange range, ref T[] output)
+ {
+ int overlapCount = 0;
+
+ for (int i = 0; i < range.Count; i++)
+ {
+ var subrange = range.GetSubRange(i);
+
+ if (IsInvalid(ref subrange))
+ {
+ continue;
+ }
+
+ overlapCount = _items.Get(subrange.Address, subrange.EndAddress, ref output, overlapCount);
+ }
+
+ // Remove any duplicates, caused by items having multiple sub range nodes in the tree.
+ if (overlapCount > 1)
+ {
+ int insertPtr = 0;
+ for (int i = 0; i < overlapCount; i++)
+ {
+ T item = output[i];
+ bool duplicate = false;
+
+ for (int j = insertPtr - 1; j >= 0; j--)
+ {
+ if (item.Equals(output[j]))
+ {
+ duplicate = true;
+ break;
+ }
+ }
+
+ if (!duplicate)
+ {
+ if (insertPtr != i)
+ {
+ output[insertPtr] = item;
+ }
+
+ insertPtr++;
+ }
+ }
+
+ overlapCount = insertPtr;
+ }
+
+ return overlapCount;
+ }
+
+ ///
+ /// Checks if a given sub-range of memory is invalid.
+ /// Those are used to represent unmapped memory regions (holes in the region mapping).
+ ///
+ /// Memory range to checl
+ /// True if the memory range is considered invalid, false otherwise
+ private static bool IsInvalid(ref MemoryRange subRange)
+ {
+ return subRange.Address == ulong.MaxValue;
+ }
+
+ ///
+ /// Gets all items on the list starting at the specified memory address.
+ ///
+ /// Base address to find
+ /// Output array where matches will be written. It is automatically resized to fit the results
+ /// The number of matches found
+ public int FindOverlaps(ulong baseAddress, ref T[] output)
+ {
+ int count = _items.Get(baseAddress, ref output);
+
+ // Only output items with matching base address
+ int insertPtr = 0;
+ for (int i = 0; i < count; i++)
+ {
+ if (output[i].BaseAddress == baseAddress)
+ {
+ if (i != insertPtr)
+ {
+ output[insertPtr] = output[i];
+ }
+
+ insertPtr++;
+ }
+ }
+
+ return insertPtr;
+ }
+
+ private List GetList()
+ {
+ var items = _items.AsList();
+ var result = new List();
+
+ foreach (RangeNode item in items)
+ {
+ if (item.Start == item.Value.BaseAddress)
+ {
+ result.Add(item.Value);
+ }
+ }
+
+ return result;
+ }
+
+ public IEnumerator GetEnumerator()
+ {
+ return GetList().GetEnumerator();
+ }
+
+ IEnumerator IEnumerable.GetEnumerator()
+ {
+ return GetList().GetEnumerator();
+ }
+ }
+}
diff --git a/src/Ryujinx.Memory/Range/NonOverlappingRangeList.cs b/src/Ryujinx.Memory/Range/NonOverlappingRangeList.cs
new file mode 100644
index 00000000..60b2b378
--- /dev/null
+++ b/src/Ryujinx.Memory/Range/NonOverlappingRangeList.cs
@@ -0,0 +1,106 @@
+using System;
+using System.Collections.Generic;
+
+namespace Ryujinx.Memory.Range
+{
+ ///
+ /// A range list that assumes ranges are non-overlapping, with list items that can be split in two to avoid overlaps.
+ ///
+ /// Type of the range.
+ class NonOverlappingRangeList : RangeList where T : INonOverlappingRange
+ {
+ ///
+ /// Finds a list of regions that cover the desired (address, size) range.
+ /// If this range starts or ends in the middle of an existing region, it is split and only the relevant part is added.
+ /// If there is no matching region, or there is a gap, then new regions are created with the factory.
+ /// Regions are added to the list in address ascending order.
+ ///
+ /// List to add found regions to
+ /// Start address of the search region
+ /// Size of the search region
+ /// Factory for creating new ranges
+ public void GetOrAddRegions(List list, ulong address, ulong size, Func factory)
+ {
+ // (regarding the specific case this generalized function is used for)
+ // A new region may be split into multiple parts if multiple virtual regions have mapped to it.
+ // For instance, while a virtual mapping could cover 0-2 in physical space, the space 0-1 may have already been reserved...
+ // So we need to return both the split 0-1 and 1-2 ranges.
+
+ var results = new T[1];
+ int count = FindOverlapsNonOverlapping(address, size, ref results);
+
+ if (count == 0)
+ {
+ // The region is fully unmapped. Create and add it to the range list.
+ T region = factory(address, size);
+ list.Add(region);
+ Add(region);
+ }
+ else
+ {
+ ulong lastAddress = address;
+ ulong endAddress = address + size;
+
+ for (int i = 0; i < count; i++)
+ {
+ T region = results[i];
+ if (count == 1 && region.Address == address && region.Size == size)
+ {
+ // Exact match, no splitting required.
+ list.Add(region);
+ return;
+ }
+
+ if (lastAddress < region.Address)
+ {
+ // There is a gap between this region and the last. We need to fill it.
+ T fillRegion = factory(lastAddress, region.Address - lastAddress);
+ list.Add(fillRegion);
+ Add(fillRegion);
+ }
+
+ if (region.Address < address)
+ {
+ // Split the region around our base address and take the high half.
+
+ region = Split(region, address);
+ }
+
+ if (region.EndAddress > address + size)
+ {
+ // Split the region around our end address and take the low half.
+
+ Split(region, address + size);
+ }
+
+ list.Add(region);
+ lastAddress = region.EndAddress;
+ }
+
+ if (lastAddress < endAddress)
+ {
+ // There is a gap between this region and the end. We need to fill it.
+ T fillRegion = factory(lastAddress, endAddress - lastAddress);
+ list.Add(fillRegion);
+ Add(fillRegion);
+ }
+ }
+ }
+
+ ///
+ /// Splits a region around a target point and updates the region list.
+ /// The original region's size is modified, but its address stays the same.
+ /// A new region starting from the split address is added to the region list and returned.
+ ///
+ /// The region to split
+ /// The address to split with
+ /// The new region (high part)
+ private T Split(T region, ulong splitAddress)
+ {
+ T newRegion = (T)region.Split(splitAddress);
+ Update(region);
+ Add(newRegion);
+ return newRegion;
+ }
+ }
+}
diff --git a/src/Ryujinx.Memory/Range/RangeList.cs b/src/Ryujinx.Memory/Range/RangeList.cs
new file mode 100644
index 00000000..46919597
--- /dev/null
+++ b/src/Ryujinx.Memory/Range/RangeList.cs
@@ -0,0 +1,483 @@
+using System;
+using System.Collections;
+using System.Collections.Generic;
+using System.Runtime.CompilerServices;
+
+namespace Ryujinx.Memory.Range
+{
+ ///
+ /// Sorted list of ranges that supports binary search.
+ ///
+ /// Type of the range.
+ public class RangeList : IEnumerable where T : IRange
+ {
+ private readonly struct RangeItem 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;
+ }
+ }
+
+ private const int BackingInitialSize = 1024;
+ private const int ArrayGrowthSize = 32;
+
+ private RangeItem[] _items;
+ private readonly int _backingGrowthSize;
+
+ public int Count { get; protected set; }
+
+ ///
+ /// Creates a new range list.
+ ///
+ /// The initial size of the backing array
+ public RangeList(int backingInitialSize = BackingInitialSize)
+ {
+ _backingGrowthSize = backingInitialSize;
+ _items = new RangeItem[backingInitialSize];
+ }
+
+ ///
+ /// Adds a new item to the list.
+ ///
+ /// The item to be added
+ public void Add(T item)
+ {
+ int index = BinarySearch(item.Address);
+
+ if (index < 0)
+ {
+ index = ~index;
+ }
+
+ Insert(index, new RangeItem(item));
+ }
+
+ ///
+ /// Updates an item's end address on the list. Address must be the same.
+ ///
+ /// The item to be updated
+ /// True if the item was located and updated, false otherwise
+ public bool Update(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(item);
+
+ return true;
+ }
+
+ if (_items[index].Address > item.Address)
+ {
+ break;
+ }
+
+ index++;
+ }
+ }
+
+ return false;
+ }
+
+ [MethodImpl(MethodImplOptions.AggressiveInlining)]
+ private void Insert(int index, RangeItem item)
+ {
+ if (Count + 1 > _items.Length)
+ {
+ Array.Resize(ref _items, _items.Length + _backingGrowthSize);
+ }
+
+ 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);
+ }
+ }
+
+ ///
+ /// Removes an item from the list.
+ ///
+ /// The item to be removed
+ /// True if the item was removed, or false if it was not found
+ public bool Remove(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))
+ {
+ RemoveAt(index);
+
+ return true;
+ }
+
+ if (_items[index].Address > item.Address)
+ {
+ break;
+ }
+
+ index++;
+ }
+ }
+
+ return false;
+ }
+
+ ///
+ /// Updates an item's end address.
+ ///
+ /// The item to be updated
+ 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(item);
+
+ return;
+ }
+
+ if (_items[index].Address > item.Address)
+ {
+ break;
+ }
+
+ index++;
+ }
+ }
+ }
+
+ ///
+ /// Gets the first item on the list overlapping in memory with the specified item.
+ ///
+ ///
+ /// Despite the name, this has no ordering guarantees of the returned item.
+ /// It only ensures that the item returned overlaps the specified item.
+ ///
+ /// Item to check for overlaps
+ /// The overlapping item, or the default value for the type if none found
+ public T FindFirstOverlap(T item)
+ {
+ return FindFirstOverlap(item.Address, item.Size);
+ }
+
+ ///
+ /// Gets the first item on the list overlapping the specified memory range.
+ ///
+ ///
+ /// Despite the name, this has no ordering guarantees of the returned item.
+ /// It only ensures that the item returned overlaps the specified memory range.
+ ///
+ /// Start address of the range
+ /// Size in bytes of the range
+ /// The overlapping item, or the default value for the type if none found
+ public T FindFirstOverlap(ulong address, ulong size)
+ {
+ int index = BinarySearch(address, address + size);
+
+ if (index < 0)
+ {
+ return default(T);
+ }
+
+ return _items[index].Value;
+ }
+
+ ///
+ /// Gets all items overlapping with the specified item in memory.
+ ///
+ /// Item to check for overlaps
+ /// Output array where matches will be written. It is automatically resized to fit the results
+ /// The number of overlapping items found
+ public int FindOverlaps(T item, ref T[] output)
+ {
+ return FindOverlaps(item.Address, item.Size, ref output);
+ }
+
+ ///
+ /// Gets all items on the list overlapping the specified memory range.
+ ///
+ /// Start address of the range
+ /// Size in bytes of the range
+ /// Output array where matches will be written. It is automatically resized to fit the results
+ /// The number of overlapping items found
+ public int FindOverlaps(ulong address, ulong size, ref T[] output)
+ {
+ int outputIndex = 0;
+
+ ulong endAddress = address + size;
+
+ for (int i = 0; i < Count; i++)
+ {
+ ref RangeItem item = ref _items[i];
+
+ if (item.Address >= endAddress)
+ {
+ break;
+ }
+
+ if (item.OverlapsWith(address, endAddress))
+ {
+ if (outputIndex == output.Length)
+ {
+ Array.Resize(ref output, outputIndex + ArrayGrowthSize);
+ }
+
+ output[outputIndex++] = item.Value;
+ }
+ }
+
+ return outputIndex;
+ }
+
+ ///
+ /// Gets all items overlapping with the specified item in memory.
+ ///
+ ///
+ /// This method only returns correct results if none of the items on the list overlaps with
+ /// each other. If that is not the case, this method should not be used.
+ /// This method is faster than the regular method to find all overlaps.
+ ///
+ /// Item to check for overlaps
+ /// Output array where matches will be written. It is automatically resized to fit the results
+ /// The number of overlapping items found
+ public int FindOverlapsNonOverlapping(T item, ref T[] output)
+ {
+ return FindOverlapsNonOverlapping(item.Address, item.Size, ref output);
+ }
+
+ ///
+ /// Gets all items on the list overlapping the specified memory range.
+ ///
+ ///
+ /// This method only returns correct results if none of the items on the list overlaps with
+ /// each other. If that is not the case, this method should not be used.
+ /// This method is faster than the regular method to find all overlaps.
+ ///
+ /// Start address of the range
+ /// Size in bytes of the range
+ /// Output array where matches will be written. It is automatically resized to fit the results
+ /// The number of overlapping items found
+ public int FindOverlapsNonOverlapping(ulong address, ulong size, ref T[] output)
+ {
+ // This is a bit faster than FindOverlaps, but only works
+ // when none of the items on the list overlaps with each other.
+ int outputIndex = 0;
+
+ ulong endAddress = address + size;
+
+ int index = BinarySearch(address, endAddress);
+
+ if (index >= 0)
+ {
+ while (index > 0 && _items[index - 1].OverlapsWith(address, endAddress))
+ {
+ index--;
+ }
+
+ do
+ {
+ if (outputIndex == output.Length)
+ {
+ Array.Resize(ref output, outputIndex + ArrayGrowthSize);
+ }
+
+ output[outputIndex++] = _items[index++].Value;
+ }
+ while (index < Count && _items[index].OverlapsWith(address, endAddress));
+ }
+
+ return outputIndex;
+ }
+
+ ///
+ /// Gets all items on the list with the specified memory address.
+ ///
+ /// Address to find
+ /// Output array where matches will be written. It is automatically resized to fit the results
+ /// The number of matches found
+ public int FindOverlaps(ulong address, ref T[] output)
+ {
+ int index = BinarySearch(address);
+
+ int outputIndex = 0;
+
+ if (index >= 0)
+ {
+ while (index > 0 && _items[index - 1].Address == address)
+ {
+ index--;
+ }
+
+ while (index < Count)
+ {
+ ref RangeItem overlap = ref _items[index++];
+
+ if (overlap.Address != address)
+ {
+ break;
+ }
+
+ if (outputIndex == output.Length)
+ {
+ Array.Resize(ref output, outputIndex + ArrayGrowthSize);
+ }
+
+ output[outputIndex++] = overlap.Value;
+ }
+ }
+
+ return outputIndex;
+ }
+
+ ///
+ /// Performs binary search on the internal list of items.
+ ///
+ /// Address to find
+ /// List index of the item, or complement index of nearest item with lower value on the list
+ private int BinarySearch(ulong address)
+ {
+ int left = 0;
+ int right = Count - 1;
+
+ while (left <= right)
+ {
+ int range = right - left;
+
+ int middle = left + (range >> 1);
+
+ ref RangeItem item = ref _items[middle];
+
+ if (item.Address == address)
+ {
+ return middle;
+ }
+
+ if (address < item.Address)
+ {
+ right = middle - 1;
+ }
+ else
+ {
+ left = middle + 1;
+ }
+ }
+
+ return ~left;
+ }
+
+ ///
+ /// Performs binary search for items overlapping a given memory range.
+ ///
+ /// Start address of the range
+ /// End address of the range
+ /// List index of the item, or complement index of nearest item with lower value on the list
+ private int BinarySearch(ulong address, ulong endAddress)
+ {
+ int left = 0;
+ int right = Count - 1;
+
+ while (left <= right)
+ {
+ int range = right - left;
+
+ int middle = left + (range >> 1);
+
+ ref RangeItem item = ref _items[middle];
+
+ if (item.OverlapsWith(address, endAddress))
+ {
+ return middle;
+ }
+
+ if (address < item.Address)
+ {
+ right = middle - 1;
+ }
+ else
+ {
+ left = middle + 1;
+ }
+ }
+
+ return ~left;
+ }
+
+ public IEnumerator GetEnumerator()
+ {
+ for (int i = 0; i < Count; i++)
+ {
+ yield return _items[i].Value;
+ }
+ }
+
+ IEnumerator IEnumerable.GetEnumerator()
+ {
+ for (int i = 0; i < Count; i++)
+ {
+ yield return _items[i].Value;
+ }
+ }
+ }
+}
\ No newline at end of file
--
cgit v1.2.3