diff options
| author | TSR Berry <20988865+TSRBerry@users.noreply.github.com> | 2023-04-08 01:22:00 +0200 |
|---|---|---|
| committer | Mary <thog@protonmail.com> | 2023-04-27 23:51:14 +0200 |
| commit | cee712105850ac3385cd0091a923438167433f9f (patch) | |
| tree | 4a5274b21d8b7f938c0d0ce18736d3f2993b11b1 /src/Ryujinx.Memory/WindowsShared/MappingTree.cs | |
| parent | cd124bda587ef09668a971fa1cac1c3f0cfc9f21 (diff) | |
Move solution and projects to src
Diffstat (limited to 'src/Ryujinx.Memory/WindowsShared/MappingTree.cs')
| -rw-r--r-- | src/Ryujinx.Memory/WindowsShared/MappingTree.cs | 87 |
1 files changed, 87 insertions, 0 deletions
diff --git a/src/Ryujinx.Memory/WindowsShared/MappingTree.cs b/src/Ryujinx.Memory/WindowsShared/MappingTree.cs new file mode 100644 index 00000000..97758c2b --- /dev/null +++ b/src/Ryujinx.Memory/WindowsShared/MappingTree.cs @@ -0,0 +1,87 @@ +using Ryujinx.Common.Collections; +using System; + +namespace Ryujinx.Memory.WindowsShared +{ + /// <summary> + /// A intrusive Red-Black Tree that also supports getting nodes overlapping a given range. + /// </summary> + /// <typeparam name="T">Type of the value stored on the node</typeparam> + class MappingTree<T> : IntrusiveRedBlackTree<RangeNode<T>> + { + private const int ArrayGrowthSize = 16; + + public int GetNodes(ulong start, ulong end, ref RangeNode<T>[] overlaps, int overlapCount = 0) + { + RangeNode<T> node = this.GetNodeByKey(start); + + for (; node != null; node = node.Successor) + { + if (overlaps.Length <= overlapCount) + { + Array.Resize(ref overlaps, overlapCount + ArrayGrowthSize); + } + + overlaps[overlapCount++] = node; + + if (node.End >= end) + { + break; + } + } + + return overlapCount; + } + } + + class RangeNode<T> : IntrusiveRedBlackTreeNode<RangeNode<T>>, IComparable<RangeNode<T>>, IComparable<ulong> + { + public ulong Start { get; } + public ulong End { get; private set; } + public T Value { get; } + + public RangeNode(ulong start, ulong end, T value) + { + Start = start; + End = end; + Value = value; + } + + public void Extend(ulong sizeDelta) + { + End += sizeDelta; + } + + public int CompareTo(RangeNode<T> other) + { + if (Start < other.Start) + { + return -1; + } + else if (Start <= other.End - 1UL) + { + return 0; + } + else + { + return 1; + } + } + + public int CompareTo(ulong address) + { + if (address < Start) + { + return 1; + } + else if (address <= End - 1UL) + { + return 0; + } + else + { + return -1; + } + } + } +}
\ No newline at end of file |