aboutsummaryrefslogtreecommitdiff
path: root/Ryujinx.Memory/Range
diff options
context:
space:
mode:
authorTSR Berry <20988865+TSRBerry@users.noreply.github.com>2023-04-08 01:22:00 +0200
committerMary <thog@protonmail.com>2023-04-27 23:51:14 +0200
commitcee712105850ac3385cd0091a923438167433f9f (patch)
tree4a5274b21d8b7f938c0d0ce18736d3f2993b11b1 /Ryujinx.Memory/Range
parentcd124bda587ef09668a971fa1cac1c3f0cfc9f21 (diff)
Move solution and projects to src
Diffstat (limited to 'Ryujinx.Memory/Range')
-rw-r--r--Ryujinx.Memory/Range/HostMemoryRange.cs71
-rw-r--r--Ryujinx.Memory/Range/IMultiRangeItem.cs9
-rw-r--r--Ryujinx.Memory/Range/INonOverlappingRange.cs16
-rw-r--r--Ryujinx.Memory/Range/IRange.cs31
-rw-r--r--Ryujinx.Memory/Range/MemoryRange.cs61
-rw-r--r--Ryujinx.Memory/Range/MultiRange.cs323
-rw-r--r--Ryujinx.Memory/Range/MultiRangeList.cs210
-rw-r--r--Ryujinx.Memory/Range/NonOverlappingRangeList.cs106
-rw-r--r--Ryujinx.Memory/Range/RangeList.cs483
9 files changed, 0 insertions, 1310 deletions
diff --git a/Ryujinx.Memory/Range/HostMemoryRange.cs b/Ryujinx.Memory/Range/HostMemoryRange.cs
deleted file mode 100644
index 79c649d8..00000000
--- a/Ryujinx.Memory/Range/HostMemoryRange.cs
+++ /dev/null
@@ -1,71 +0,0 @@
-using System;
-
-namespace Ryujinx.Memory.Range
-{
- /// <summary>
- /// Range of memory composed of an address and size.
- /// </summary>
- public struct HostMemoryRange : IEquatable<HostMemoryRange>
- {
- /// <summary>
- /// An empty memory range, with a null address and zero size.
- /// </summary>
- public static HostMemoryRange Empty => new HostMemoryRange(0, 0);
-
- /// <summary>
- /// Start address of the range.
- /// </summary>
- public nuint Address { get; }
-
- /// <summary>
- /// Size of the range in bytes.
- /// </summary>
- public ulong Size { get; }
-
- /// <summary>
- /// Address where the range ends (exclusive).
- /// </summary>
- public nuint EndAddress => Address + (nuint)Size;
-
- /// <summary>
- /// Creates a new memory range with the specified address and size.
- /// </summary>
- /// <param name="address">Start address</param>
- /// <param name="size">Size in bytes</param>
- public HostMemoryRange(nuint address, ulong size)
- {
- Address = address;
- Size = size;
- }
-
- /// <summary>
- /// Checks if the range overlaps with another.
- /// </summary>
- /// <param name="other">The other range to check for overlap</param>
- /// <returns>True if the ranges overlap, false otherwise</returns>
- 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/Ryujinx.Memory/Range/IMultiRangeItem.cs b/Ryujinx.Memory/Range/IMultiRangeItem.cs
deleted file mode 100644
index e95a69fc..00000000
--- a/Ryujinx.Memory/Range/IMultiRangeItem.cs
+++ /dev/null
@@ -1,9 +0,0 @@
-namespace Ryujinx.Memory.Range
-{
- public interface IMultiRangeItem
- {
- MultiRange Range { get; }
-
- ulong BaseAddress => Range.GetSubRange(0).Address;
- }
-}
diff --git a/Ryujinx.Memory/Range/INonOverlappingRange.cs b/Ryujinx.Memory/Range/INonOverlappingRange.cs
deleted file mode 100644
index 1886eb1d..00000000
--- a/Ryujinx.Memory/Range/INonOverlappingRange.cs
+++ /dev/null
@@ -1,16 +0,0 @@
-namespace Ryujinx.Memory.Range
-{
- /// <summary>
- /// Range of memory that can be split in two.
- /// </summary>
- interface INonOverlappingRange : IRange
- {
- /// <summary>
- /// 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.
- /// </summary>
- /// <param name="splitAddress">Address to split the region around</param>
- /// <returns>The second part of the split region, with start address at the given split.</returns>
- public INonOverlappingRange Split(ulong splitAddress);
- }
-}
diff --git a/Ryujinx.Memory/Range/IRange.cs b/Ryujinx.Memory/Range/IRange.cs
deleted file mode 100644
index 1685396d..00000000
--- a/Ryujinx.Memory/Range/IRange.cs
+++ /dev/null
@@ -1,31 +0,0 @@
-namespace Ryujinx.Memory.Range
-{
- /// <summary>
- /// Range of memory.
- /// </summary>
- public interface IRange
- {
- /// <summary>
- /// Base address.
- /// </summary>
- ulong Address { get; }
-
- /// <summary>
- /// Size of the range.
- /// </summary>
- ulong Size { get; }
-
- /// <summary>
- /// End address.
- /// </summary>
- ulong EndAddress { get; }
-
- /// <summary>
- /// Check if this range overlaps with another.
- /// </summary>
- /// <param name="address">Base address</param>
- /// <param name="size">Size of the range</param>
- /// <returns>True if overlapping, false otherwise</returns>
- bool OverlapsWith(ulong address, ulong size);
- }
-} \ No newline at end of file
diff --git a/Ryujinx.Memory/Range/MemoryRange.cs b/Ryujinx.Memory/Range/MemoryRange.cs
deleted file mode 100644
index 7465fbcb..00000000
--- a/Ryujinx.Memory/Range/MemoryRange.cs
+++ /dev/null
@@ -1,61 +0,0 @@
-namespace Ryujinx.Memory.Range
-{
- /// <summary>
- /// Range of memory composed of an address and size.
- /// </summary>
- public readonly record struct MemoryRange
- {
- /// <summary>
- /// An empty memory range, with a null address and zero size.
- /// </summary>
- public static MemoryRange Empty => new MemoryRange(0UL, 0);
-
- /// <summary>
- /// Start address of the range.
- /// </summary>
- public ulong Address { get; }
-
- /// <summary>
- /// Size of the range in bytes.
- /// </summary>
- public ulong Size { get; }
-
- /// <summary>
- /// Address where the range ends (exclusive).
- /// </summary>
- public ulong EndAddress => Address + Size;
-
- /// <summary>
- /// Creates a new memory range with the specified address and size.
- /// </summary>
- /// <param name="address">Start address</param>
- /// <param name="size">Size in bytes</param>
- public MemoryRange(ulong address, ulong size)
- {
- Address = address;
- Size = size;
- }
-
- /// <summary>
- /// Checks if the range overlaps with another.
- /// </summary>
- /// <param name="other">The other range to check for overlap</param>
- /// <returns>True if the ranges overlap, false otherwise</returns>
- 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/Ryujinx.Memory/Range/MultiRange.cs b/Ryujinx.Memory/Range/MultiRange.cs
deleted file mode 100644
index 9dbd76ec..00000000
--- a/Ryujinx.Memory/Range/MultiRange.cs
+++ /dev/null
@@ -1,323 +0,0 @@
-using System;
-using System.Collections.Generic;
-
-namespace Ryujinx.Memory.Range
-{
- /// <summary>
- /// Sequence of physical memory regions that a single non-contiguous virtual memory region maps to.
- /// </summary>
- public readonly struct MultiRange : IEquatable<MultiRange>
- {
- private const ulong InvalidAddress = ulong.MaxValue;
-
- private readonly MemoryRange _singleRange;
- private readonly MemoryRange[] _ranges;
-
- private bool HasSingleRange => _ranges == null;
-
- /// <summary>
- /// Total of physical sub-ranges on the virtual memory region.
- /// </summary>
- public int Count => HasSingleRange ? 1 : _ranges.Length;
-
- /// <summary>
- /// Creates a new multi-range with a single physical region.
- /// </summary>
- /// <param name="address">Start address of the region</param>
- /// <param name="size">Size of the region in bytes</param>
- public MultiRange(ulong address, ulong size)
- {
- _singleRange = new MemoryRange(address, size);
- _ranges = null;
- }
-
- /// <summary>
- /// Creates a new multi-range with multiple physical regions.
- /// </summary>
- /// <param name="ranges">Array of physical regions</param>
- /// <exception cref="ArgumentNullException"><paramref name="ranges"/> is null</exception>
- public MultiRange(MemoryRange[] ranges)
- {
- _singleRange = MemoryRange.Empty;
- _ranges = ranges ?? throw new ArgumentNullException(nameof(ranges));
- }
-
- /// <summary>
- /// Gets a slice of the multi-range.
- /// </summary>
- /// <param name="offset">Offset of the slice into the multi-range in bytes</param>
- /// <param name="size">Size of the slice in bytes</param>
- /// <returns>A new multi-range representing the given slice of this one</returns>
- 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<MemoryRange>();
-
- 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());
- }
- }
-
- /// <summary>
- /// Gets the physical region at the specified index.
- /// </summary>
- /// <param name="index">Index of the physical region</param>
- /// <returns>Region at the index specified</returns>
- /// <exception cref="ArgumentOutOfRangeException"><paramref name="index"/> is invalid</exception>
- 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];
- }
- }
-
- /// <summary>
- /// Gets the physical region at the specified index, without explicit bounds checking.
- /// </summary>
- /// <param name="index">Index of the physical region</param>
- /// <returns>Region at the index specified</returns>
- private MemoryRange GetSubRangeUnchecked(int index)
- {
- return HasSingleRange ? _singleRange : _ranges[index];
- }
-
- /// <summary>
- /// Check if two multi-ranges overlap with each other.
- /// </summary>
- /// <param name="other">Other multi-range to check for overlap</param>
- /// <returns>True if any sub-range overlaps, false otherwise</returns>
- 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;
- }
-
- /// <summary>
- /// Checks if a given multi-range is fully contained inside another.
- /// </summary>
- /// <param name="other">Multi-range to be checked</param>
- /// <returns>True if all the sub-ranges on <paramref name="other"/> are contained inside the multi-range, with the same order, false otherwise</returns>
- public bool Contains(MultiRange other)
- {
- return FindOffset(other) >= 0;
- }
-
- /// <summary>
- /// 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.
- /// </summary>
- /// <param name="other">Multi-range that should be fully contained inside this one</param>
- /// <returns>Offset in bytes if fully contained, otherwise -1</returns>
- 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;
- }
-
- /// <summary>
- /// Gets the total size of all sub-ranges in bytes.
- /// </summary>
- /// <returns>Total size in bytes</returns>
- 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/Ryujinx.Memory/Range/MultiRangeList.cs b/Ryujinx.Memory/Range/MultiRangeList.cs
deleted file mode 100644
index 5131889f..00000000
--- a/Ryujinx.Memory/Range/MultiRangeList.cs
+++ /dev/null
@@ -1,210 +0,0 @@
-using Ryujinx.Common.Collections;
-using System.Collections;
-using System.Collections.Generic;
-
-namespace Ryujinx.Memory.Range
-{
- public class MultiRangeList<T> : IEnumerable<T> where T : IMultiRangeItem
- {
- private readonly IntervalTree<ulong, T> _items;
-
- public int Count { get; private set; }
-
- /// <summary>
- /// Creates a new range list.
- /// </summary>
- public MultiRangeList()
- {
- _items = new IntervalTree<ulong, T>();
- }
-
- /// <summary>
- /// Adds a new item to the list.
- /// </summary>
- /// <param name="item">The item to be added</param>
- 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++;
- }
-
- /// <summary>
- /// Removes an item from the list.
- /// </summary>
- /// <param name="item">The item to be removed</param>
- /// <returns>True if the item was removed, or false if it was not found</returns>
- 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;
- }
-
- /// <summary>
- /// Gets all items on the list overlapping the specified memory range.
- /// </summary>
- /// <param name="address">Start address of the range</param>
- /// <param name="size">Size in bytes of the range</param>
- /// <param name="output">Output array where matches will be written. It is automatically resized to fit the results</param>
- /// <returns>The number of overlapping items found</returns>
- public int FindOverlaps(ulong address, ulong size, ref T[] output)
- {
- return FindOverlaps(new MultiRange(address, size), ref output);
- }
-
- /// <summary>
- /// Gets all items on the list overlapping the specified memory ranges.
- /// </summary>
- /// <param name="range">Ranges of memory being searched</param>
- /// <param name="output">Output array where matches will be written. It is automatically resized to fit the results</param>
- /// <returns>The number of overlapping items found</returns>
- 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;
- }
-
- /// <summary>
- /// Checks if a given sub-range of memory is invalid.
- /// Those are used to represent unmapped memory regions (holes in the region mapping).
- /// </summary>
- /// <param name="subRange">Memory range to checl</param>
- /// <returns>True if the memory range is considered invalid, false otherwise</returns>
- private static bool IsInvalid(ref MemoryRange subRange)
- {
- return subRange.Address == ulong.MaxValue;
- }
-
- /// <summary>
- /// Gets all items on the list starting at the specified memory address.
- /// </summary>
- /// <param name="baseAddress">Base address to find</param>
- /// <param name="output">Output array where matches will be written. It is automatically resized to fit the results</param>
- /// <returns>The number of matches found</returns>
- 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<T> GetList()
- {
- var items = _items.AsList();
- var result = new List<T>();
-
- foreach (RangeNode<ulong, T> item in items)
- {
- if (item.Start == item.Value.BaseAddress)
- {
- result.Add(item.Value);
- }
- }
-
- return result;
- }
-
- public IEnumerator<T> GetEnumerator()
- {
- return GetList().GetEnumerator();
- }
-
- IEnumerator IEnumerable.GetEnumerator()
- {
- return GetList().GetEnumerator();
- }
- }
-}
diff --git a/Ryujinx.Memory/Range/NonOverlappingRangeList.cs b/Ryujinx.Memory/Range/NonOverlappingRangeList.cs
deleted file mode 100644
index 60b2b378..00000000
--- a/Ryujinx.Memory/Range/NonOverlappingRangeList.cs
+++ /dev/null
@@ -1,106 +0,0 @@
-using System;
-using System.Collections.Generic;
-
-namespace Ryujinx.Memory.Range
-{
- /// <summary>
- /// A range list that assumes ranges are non-overlapping, with list items that can be split in two to avoid overlaps.
- /// </summary>
- /// <typeparam name="T">Type of the range.</typeparam>
- class NonOverlappingRangeList<T> : RangeList<T> where T : INonOverlappingRange
- {
- /// <summary>
- /// 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.
- /// </summary>
- /// <param name="list">List to add found regions to</param>
- /// <param name="address">Start address of the search region</param>
- /// <param name="size">Size of the search region</param>
- /// <param name="factory">Factory for creating new ranges</param>
- public void GetOrAddRegions(List<T> list, ulong address, ulong size, Func<ulong, ulong, T> 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);
- }
- }
- }
-
- /// <summary>
- /// 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.
- /// </summary>
- /// <param name="region">The region to split</param>
- /// <param name="splitAddress">The address to split with</param>
- /// <returns>The new region (high part)</returns>
- private T Split(T region, ulong splitAddress)
- {
- T newRegion = (T)region.Split(splitAddress);
- Update(region);
- Add(newRegion);
- return newRegion;
- }
- }
-}
diff --git a/Ryujinx.Memory/Range/RangeList.cs b/Ryujinx.Memory/Range/RangeList.cs
deleted file mode 100644
index 46919597..00000000
--- a/Ryujinx.Memory/Range/RangeList.cs
+++ /dev/null
@@ -1,483 +0,0 @@
-using System;
-using System.Collections;
-using System.Collections.Generic;
-using System.Runtime.CompilerServices;
-
-namespace Ryujinx.Memory.Range
-{
- /// <summary>
- /// Sorted list of ranges that supports binary search.
- /// </summary>
- /// <typeparam name="T">Type of the range.</typeparam>
- public class RangeList<T> : IEnumerable<T> where T : IRange
- {
- 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;
- }
- }
-
- private const int BackingInitialSize = 1024;
- private const int ArrayGrowthSize = 32;
-
- private RangeItem<T>[] _items;
- private readonly int _backingGrowthSize;
-
- public int Count { get; protected set; }
-
- /// <summary>
- /// Creates a new range list.
- /// </summary>
- /// <param name="backingInitialSize">The initial size of the backing array</param>
- public RangeList(int backingInitialSize = BackingInitialSize)
- {
- _backingGrowthSize = backingInitialSize;
- _items = new RangeItem<T>[backingInitialSize];
- }
-
- /// <summary>
- /// Adds a new item to the list.
- /// </summary>
- /// <param name="item">The item to be added</param>
- public void Add(T item)
- {
- int index = BinarySearch(item.Address);
-
- if (index < 0)
- {
- index = ~index;
- }
-
- Insert(index, new RangeItem<T>(item));
- }
-
- /// <summary>
- /// Updates an item's end address on the list. Address must be the same.
- /// </summary>
- /// <param name="item">The item to be updated</param>
- /// <returns>True if the item was located and updated, false otherwise</returns>
- 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<T>(item);
-
- return true;
- }
-
- if (_items[index].Address > item.Address)
- {
- break;
- }
-
- index++;
- }
- }
-
- return false;
- }
-
- [MethodImpl(MethodImplOptions.AggressiveInlining)]
- private void Insert(int index, RangeItem<T> 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);
- }
- }
-
- /// <summary>
- /// Removes an item from the list.
- /// </summary>
- /// <param name="item">The item to be removed</param>
- /// <returns>True if the item was removed, or false if it was not found</returns>
- 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;
- }
-
- /// <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>
- /// Despite the name, this has no ordering guarantees of the returned item.
- /// It only ensures that the item returned overlaps the specified item.
- /// </remarks>
- /// <param name="item">Item to check for overlaps</param>
- /// <returns>The overlapping item, or the default value for the type if none found</returns>
- public T FindFirstOverlap(T item)
- {
- return FindFirstOverlap(item.Address, item.Size);
- }
-
- /// <summary>
- /// Gets the first item on the list overlapping the specified memory range.
- /// </summary>
- /// <remarks>
- /// Despite the name, this has no ordering guarantees of the returned item.
- /// It only ensures that the item returned overlaps the specified memory range.
- /// </remarks>
- /// <param name="address">Start address of the range</param>
- /// <param name="size">Size in bytes of the range</param>
- /// <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, address + size);
-
- if (index < 0)
- {
- return default(T);
- }
-
- return _items[index].Value;
- }
-
- /// <summary>
- /// Gets all items overlapping with the specified item in memory.
- /// </summary>
- /// <param name="item">Item to check for overlaps</param>
- /// <param name="output">Output array where matches will be written. It is automatically resized to fit the results</param>
- /// <returns>The number of overlapping items found</returns>
- public int FindOverlaps(T item, ref T[] output)
- {
- return FindOverlaps(item.Address, item.Size, ref output);
- }
-
- /// <summary>
- /// Gets all items on the list overlapping the specified memory range.
- /// </summary>
- /// <param name="address">Start address of the range</param>
- /// <param name="size">Size in bytes of the range</param>
- /// <param name="output">Output array where matches will be written. It is automatically resized to fit the results</param>
- /// <returns>The number of overlapping items found</returns>
- 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<T> 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;
- }
-
- /// <summary>
- /// Gets all items overlapping with the specified item in memory.
- /// </summary>
- /// <remarks>
- /// 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.
- /// </remarks>
- /// <param name="item">Item to check for overlaps</param>
- /// <param name="output">Output array where matches will be written. It is automatically resized to fit the results</param>
- /// <returns>The number of overlapping items found</returns>
- public int FindOverlapsNonOverlapping(T item, ref T[] output)
- {
- return FindOverlapsNonOverlapping(item.Address, item.Size, ref output);
- }
-
- /// <summary>
- /// Gets all items on the list overlapping the specified memory range.
- /// </summary>
- /// <remarks>
- /// 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.
- /// </remarks>
- /// <param name="address">Start address of the range</param>
- /// <param name="size">Size in bytes of the range</param>
- /// <param name="output">Output array where matches will be written. It is automatically resized to fit the results</param>
- /// <returns>The number of overlapping items found</returns>
- 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;
- }
-
- /// <summary>
- /// Gets all items on the list with the specified memory address.
- /// </summary>
- /// <param name="address">Address to find</param>
- /// <param name="output">Output array where matches will be written. It is automatically resized to fit the results</param>
- /// <returns>The number of matches found</returns>
- 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<T> 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;
- }
-
- /// <summary>
- /// Performs binary search on the internal list of items.
- /// </summary>
- /// <param name="address">Address to find</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)
- {
- int left = 0;
- int right = Count - 1;
-
- while (left <= right)
- {
- int range = right - left;
-
- int middle = left + (range >> 1);
-
- ref RangeItem<T> item = ref _items[middle];
-
- if (item.Address == address)
- {
- return middle;
- }
-
- if (address < item.Address)
- {
- right = middle - 1;
- }
- else
- {
- left = middle + 1;
- }
- }
-
- return ~left;
- }
-
- /// <summary>
- /// Performs binary search for items overlapping a given memory range.
- /// </summary>
- /// <param name="address">Start address 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 endAddress)
- {
- int left = 0;
- int right = Count - 1;
-
- while (left <= right)
- {
- int range = right - left;
-
- int middle = left + (range >> 1);
-
- ref RangeItem<T> 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<T> 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