1  using System;
  2  using System.Collections.Generic;
  3  
  4  namespace Ryujinx.Memory.Range
  5  {
  6      /// <summary>
  7      /// A range list that assumes ranges are non-overlapping, with list items that can be split in two to avoid overlaps.
  8      /// </summary>
  9      /// <typeparam name="T">Type of the range.</typeparam>
 10      class NonOverlappingRangeList<T> : RangeList<T> where T : INonOverlappingRange
 11      {
 12          /// <summary>
 13          /// Finds a list of regions that cover the desired (address, size) range.
 14          /// If this range starts or ends in the middle of an existing region, it is split and only the relevant part is added.
 15          /// If there is no matching region, or there is a gap, then new regions are created with the factory.
 16          /// Regions are added to the list in address ascending order.
 17          /// </summary>
 18          /// <param name="list">List to add found regions to</param>
 19          /// <param name="address">Start address of the search region</param>
 20          /// <param name="size">Size of the search region</param>
 21          /// <param name="factory">Factory for creating new ranges</param>
 22          public void GetOrAddRegions(List<T> list, ulong address, ulong size, Func<ulong, ulong, T> factory)
 23          {
 24              // (regarding the specific case this generalized function is used for)
 25              // A new region may be split into multiple parts if multiple virtual regions have mapped to it.
 26              // For instance, while a virtual mapping could cover 0-2 in physical space, the space 0-1 may have already been reserved...
 27              // So we need to return both the split 0-1 and 1-2 ranges.
 28  
 29              var results = new T[1];
 30              int count = FindOverlapsNonOverlapping(address, size, ref results);
 31  
 32              if (count == 0)
 33              {
 34                  // The region is fully unmapped. Create and add it to the range list.
 35                  T region = factory(address, size);
 36                  list.Add(region);
 37                  Add(region);
 38              }
 39              else
 40              {
 41                  ulong lastAddress = address;
 42                  ulong endAddress = address + size;
 43  
 44                  for (int i = 0; i < count; i++)
 45                  {
 46                      T region = results[i];
 47                      if (count == 1 && region.Address == address && region.Size == size)
 48                      {
 49                          // Exact match, no splitting required.
 50                          list.Add(region);
 51                          return;
 52                      }
 53  
 54                      if (lastAddress < region.Address)
 55                      {
 56                          // There is a gap between this region and the last. We need to fill it.
 57                          T fillRegion = factory(lastAddress, region.Address - lastAddress);
 58                          list.Add(fillRegion);
 59                          Add(fillRegion);
 60                      }
 61  
 62                      if (region.Address < address)
 63                      {
 64                          // Split the region around our base address and take the high half.
 65  
 66                          region = Split(region, address);
 67                      }
 68  
 69                      if (region.EndAddress > address + size)
 70                      {
 71                          // Split the region around our end address and take the low half.
 72  
 73                          Split(region, address + size);
 74                      }
 75  
 76                      list.Add(region);
 77                      lastAddress = region.EndAddress;
 78                  }
 79  
 80                  if (lastAddress < endAddress)
 81                  {
 82                      // There is a gap between this region and the end. We need to fill it.
 83                      T fillRegion = factory(lastAddress, endAddress - lastAddress);
 84                      list.Add(fillRegion);
 85                      Add(fillRegion);
 86                  }
 87              }
 88          }
 89  
 90          /// <summary>
 91          /// Splits a region around a target point and updates the region list. 
 92          /// The original region's size is modified, but its address stays the same.
 93          /// A new region starting from the split address is added to the region list and returned.
 94          /// </summary>
 95          /// <param name="region">The region to split</param>
 96          /// <param name="splitAddress">The address to split with</param>
 97          /// <returns>The new region (high part)</returns>
 98          private T Split(T region, ulong splitAddress)
 99          {
100              T newRegion = (T)region.Split(splitAddress);
101              Update(region);
102              Add(newRegion);
103              return newRegion;
104          }
105      }
106  }