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 --- Ryujinx.Memory/Range/HostMemoryRange.cs | 71 ---- Ryujinx.Memory/Range/IMultiRangeItem.cs | 9 - Ryujinx.Memory/Range/INonOverlappingRange.cs | 16 - Ryujinx.Memory/Range/IRange.cs | 31 -- Ryujinx.Memory/Range/MemoryRange.cs | 61 --- Ryujinx.Memory/Range/MultiRange.cs | 323 ---------------- Ryujinx.Memory/Range/MultiRangeList.cs | 210 ----------- Ryujinx.Memory/Range/NonOverlappingRangeList.cs | 106 ------ Ryujinx.Memory/Range/RangeList.cs | 483 ------------------------ 9 files changed, 1310 deletions(-) delete mode 100644 Ryujinx.Memory/Range/HostMemoryRange.cs delete mode 100644 Ryujinx.Memory/Range/IMultiRangeItem.cs delete mode 100644 Ryujinx.Memory/Range/INonOverlappingRange.cs delete mode 100644 Ryujinx.Memory/Range/IRange.cs delete mode 100644 Ryujinx.Memory/Range/MemoryRange.cs delete mode 100644 Ryujinx.Memory/Range/MultiRange.cs delete mode 100644 Ryujinx.Memory/Range/MultiRangeList.cs delete mode 100644 Ryujinx.Memory/Range/NonOverlappingRangeList.cs delete mode 100644 Ryujinx.Memory/Range/RangeList.cs (limited to 'Ryujinx.Memory/Range') 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 -{ - /// - /// 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/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 -{ - /// - /// 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/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 -{ - /// - /// 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/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 -{ - /// - /// 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/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 -{ - /// - /// 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/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 : 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/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 -{ - /// - /// 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/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 -{ - /// - /// 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