1  using Ryujinx.Common.Collections;
  2  using System.Collections;
  3  using System.Collections.Generic;
  4  
  5  namespace Ryujinx.Memory.Range
  6  {
  7      public class MultiRangeList<T> : IEnumerable<T> where T : IMultiRangeItem
  8      {
  9          private readonly IntervalTree<ulong, T> _items;
 10  
 11          public int Count { get; private set; }
 12  
 13          /// <summary>
 14          /// Creates a new range list.
 15          /// </summary>
 16          public MultiRangeList()
 17          {
 18              _items = new IntervalTree<ulong, T>();
 19          }
 20  
 21          /// <summary>
 22          /// Adds a new item to the list.
 23          /// </summary>
 24          /// <param name="item">The item to be added</param>
 25          public void Add(T item)
 26          {
 27              MultiRange range = item.Range;
 28  
 29              for (int i = 0; i < range.Count; i++)
 30              {
 31                  var subrange = range.GetSubRange(i);
 32  
 33                  if (MemoryRange.IsInvalid(ref subrange))
 34                  {
 35                      continue;
 36                  }
 37  
 38                  _items.Add(subrange.Address, subrange.EndAddress, item);
 39              }
 40  
 41              Count++;
 42          }
 43  
 44          /// <summary>
 45          /// Removes an item from the list.
 46          /// </summary>
 47          /// <param name="item">The item to be removed</param>
 48          /// <returns>True if the item was removed, or false if it was not found</returns>
 49          public bool Remove(T item)
 50          {
 51              MultiRange range = item.Range;
 52  
 53              int removed = 0;
 54  
 55              for (int i = 0; i < range.Count; i++)
 56              {
 57                  var subrange = range.GetSubRange(i);
 58  
 59                  if (MemoryRange.IsInvalid(ref subrange))
 60                  {
 61                      continue;
 62                  }
 63  
 64                  removed += _items.Remove(subrange.Address, item);
 65              }
 66  
 67              if (removed > 0)
 68              {
 69                  // All deleted intervals are for the same item - the one we removed.
 70                  Count--;
 71              }
 72  
 73              return removed > 0;
 74          }
 75  
 76          /// <summary>
 77          /// Gets all items on the list overlapping the specified memory range.
 78          /// </summary>
 79          /// <param name="address">Start address of the range</param>
 80          /// <param name="size">Size in bytes of the range</param>
 81          /// <param name="output">Output array where matches will be written. It is automatically resized to fit the results</param>
 82          /// <returns>The number of overlapping items found</returns>
 83          public int FindOverlaps(ulong address, ulong size, ref T[] output)
 84          {
 85              return FindOverlaps(new MultiRange(address, size), ref output);
 86          }
 87  
 88          /// <summary>
 89          /// Gets all items on the list overlapping the specified memory ranges.
 90          /// </summary>
 91          /// <param name="range">Ranges of memory being searched</param>
 92          /// <param name="output">Output array where matches will be written. It is automatically resized to fit the results</param>
 93          /// <returns>The number of overlapping items found</returns>
 94          public int FindOverlaps(MultiRange range, ref T[] output)
 95          {
 96              int overlapCount = 0;
 97  
 98              for (int i = 0; i < range.Count; i++)
 99              {
100                  var subrange = range.GetSubRange(i);
101  
102                  if (MemoryRange.IsInvalid(ref subrange))
103                  {
104                      continue;
105                  }
106  
107                  overlapCount = _items.Get(subrange.Address, subrange.EndAddress, ref output, overlapCount);
108              }
109  
110              // Remove any duplicates, caused by items having multiple sub range nodes in the tree.
111              if (overlapCount > 1)
112              {
113                  int insertPtr = 0;
114                  for (int i = 0; i < overlapCount; i++)
115                  {
116                      T item = output[i];
117                      bool duplicate = false;
118  
119                      for (int j = insertPtr - 1; j >= 0; j--)
120                      {
121                          if (item.Equals(output[j]))
122                          {
123                              duplicate = true;
124                              break;
125                          }
126                      }
127  
128                      if (!duplicate)
129                      {
130                          if (insertPtr != i)
131                          {
132                              output[insertPtr] = item;
133                          }
134  
135                          insertPtr++;
136                      }
137                  }
138  
139                  overlapCount = insertPtr;
140              }
141  
142              return overlapCount;
143          }
144  
145          /// <summary>
146          /// Gets all items on the list starting at the specified memory address.
147          /// </summary>
148          /// <param name="baseAddress">Base address to find</param>
149          /// <param name="output">Output array where matches will be written. It is automatically resized to fit the results</param>
150          /// <returns>The number of matches found</returns>
151          public int FindOverlaps(ulong baseAddress, ref T[] output)
152          {
153              int count = _items.Get(baseAddress, ref output);
154  
155              // Only output items with matching base address
156              int insertPtr = 0;
157              for (int i = 0; i < count; i++)
158              {
159                  if (output[i].BaseAddress == baseAddress)
160                  {
161                      if (i != insertPtr)
162                      {
163                          output[insertPtr] = output[i];
164                      }
165  
166                      insertPtr++;
167                  }
168              }
169  
170              return insertPtr;
171          }
172  
173          private List<T> GetList()
174          {
175              var items = _items.AsList();
176              var result = new List<T>();
177  
178              foreach (RangeNode<ulong, T> item in items)
179              {
180                  if (item.Start == item.Value.BaseAddress)
181                  {
182                      result.Add(item.Value);
183                  }
184              }
185  
186              return result;
187          }
188  
189          public IEnumerator<T> GetEnumerator()
190          {
191              return GetList().GetEnumerator();
192          }
193  
194          IEnumerator IEnumerable.GetEnumerator()
195          {
196              return GetList().GetEnumerator();
197          }
198      }
199  }