1  using Ryujinx.Common.Collections;
 2  using System;
 3  
 4  namespace Ryujinx.Memory.WindowsShared
 5  {
 6      /// <summary>
 7      /// A intrusive Red-Black Tree that also supports getting nodes overlapping a given range.
 8      /// </summary>
 9      /// <typeparam name="T">Type of the value stored on the node</typeparam>
10      class MappingTree<T> : IntrusiveRedBlackTree<RangeNode<T>>
11      {
12          private const int ArrayGrowthSize = 16;
13  
14          public int GetNodes(ulong start, ulong end, ref RangeNode<T>[] overlaps, int overlapCount = 0)
15          {
16              RangeNode<T> node = this.GetNodeByKey(start);
17  
18              for (; node != null; node = node.Successor)
19              {
20                  if (overlaps.Length <= overlapCount)
21                  {
22                      Array.Resize(ref overlaps, overlapCount + ArrayGrowthSize);
23                  }
24  
25                  overlaps[overlapCount++] = node;
26  
27                  if (node.End >= end)
28                  {
29                      break;
30                  }
31              }
32  
33              return overlapCount;
34          }
35      }
36  
37      class RangeNode<T> : IntrusiveRedBlackTreeNode<RangeNode<T>>, IComparable<RangeNode<T>>, IComparable<ulong>
38      {
39          public ulong Start { get; }
40          public ulong End { get; private set; }
41          public T Value { get; }
42  
43          public RangeNode(ulong start, ulong end, T value)
44          {
45              Start = start;
46              End = end;
47              Value = value;
48          }
49  
50          public void Extend(ulong sizeDelta)
51          {
52              End += sizeDelta;
53          }
54  
55          public int CompareTo(RangeNode<T> other)
56          {
57              if (Start < other.Start)
58              {
59                  return -1;
60              }
61              else if (Start <= other.End - 1UL)
62              {
63                  return 0;
64              }
65              else
66              {
67                  return 1;
68              }
69          }
70  
71          public int CompareTo(ulong address)
72          {
73              if (address < Start)
74              {
75                  return 1;
76              }
77              else if (address <= End - 1UL)
78              {
79                  return 0;
80              }
81              else
82              {
83                  return -1;
84              }
85          }
86      }
87  }