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/WindowsShared/MappingTree.cs | 87 +++++++++++++++++++++++++
 1 file changed, 87 insertions(+)
 create mode 100644 src/Ryujinx.Memory/WindowsShared/MappingTree.cs

(limited to 'src/Ryujinx.Memory/WindowsShared/MappingTree.cs')

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
-- 
cgit v1.2.3