1  using System;
  2  using System.Collections.Generic;
  3  
  4  namespace Ryujinx.Graphics.Vulkan
  5  {
  6      /// <summary>
  7      /// A structure tracking pending upload ranges for buffers.
  8      /// Where a range is present, pending data exists that can either be used to build mirrors
  9      /// or upload directly to the buffer.
 10      /// </summary>
 11      struct BufferMirrorRangeList
 12      {
 13          internal readonly struct Range
 14          {
 15              public int Offset { get; }
 16              public int Size { get; }
 17  
 18              public int End => Offset + Size;
 19  
 20              public Range(int offset, int size)
 21              {
 22                  Offset = offset;
 23                  Size = size;
 24              }
 25  
 26              public bool OverlapsWith(int offset, int size)
 27              {
 28                  return Offset < offset + size && offset < Offset + Size;
 29              }
 30          }
 31  
 32          private List<Range> _ranges;
 33  
 34          public readonly IEnumerable<Range> All()
 35          {
 36              return _ranges;
 37          }
 38  
 39          public readonly bool Remove(int offset, int size)
 40          {
 41              var list = _ranges;
 42              bool removedAny = false;
 43              if (list != null)
 44              {
 45                  int overlapIndex = BinarySearch(list, offset, size);
 46  
 47                  if (overlapIndex >= 0)
 48                  {
 49                      // Overlaps with a range. Search back to find the first one it doesn't overlap with.
 50  
 51                      while (overlapIndex > 0 && list[overlapIndex - 1].OverlapsWith(offset, size))
 52                      {
 53                          overlapIndex--;
 54                      }
 55  
 56                      int endOffset = offset + size;
 57                      int startIndex = overlapIndex;
 58  
 59                      var currentOverlap = list[overlapIndex];
 60  
 61                      // Orphan the start of the overlap.
 62                      if (currentOverlap.Offset < offset)
 63                      {
 64                          list[overlapIndex] = new Range(currentOverlap.Offset, offset - currentOverlap.Offset);
 65                          currentOverlap = new Range(offset, currentOverlap.End - offset);
 66                          list.Insert(++overlapIndex, currentOverlap);
 67                          startIndex++;
 68  
 69                          removedAny = true;
 70                      }
 71  
 72                      // Remove any middle overlaps.
 73                      while (currentOverlap.Offset < endOffset)
 74                      {
 75                          if (currentOverlap.End > endOffset)
 76                          {
 77                              // Update the end overlap instead of removing it, if it spans beyond the removed range.
 78                              list[overlapIndex] = new Range(endOffset, currentOverlap.End - endOffset);
 79  
 80                              removedAny = true;
 81                              break;
 82                          }
 83  
 84                          if (++overlapIndex >= list.Count)
 85                          {
 86                              break;
 87                          }
 88  
 89                          currentOverlap = list[overlapIndex];
 90                      }
 91  
 92                      int count = overlapIndex - startIndex;
 93  
 94                      list.RemoveRange(startIndex, count);
 95  
 96                      removedAny |= count > 0;
 97                  }
 98              }
 99  
100              return removedAny;
101          }
102  
103          public void Add(int offset, int size)
104          {
105              var list = _ranges;
106              if (list != null)
107              {
108                  int overlapIndex = BinarySearch(list, offset, size);
109                  if (overlapIndex >= 0)
110                  {
111                      while (overlapIndex > 0 && list[overlapIndex - 1].OverlapsWith(offset, size))
112                      {
113                          overlapIndex--;
114                      }
115  
116                      int endOffset = offset + size;
117                      int startIndex = overlapIndex;
118  
119                      while (overlapIndex < list.Count && list[overlapIndex].OverlapsWith(offset, size))
120                      {
121                          var currentOverlap = list[overlapIndex];
122                          var currentOverlapEndOffset = currentOverlap.Offset + currentOverlap.Size;
123  
124                          if (offset > currentOverlap.Offset)
125                          {
126                              offset = currentOverlap.Offset;
127                          }
128  
129                          if (endOffset < currentOverlapEndOffset)
130                          {
131                              endOffset = currentOverlapEndOffset;
132                          }
133  
134                          overlapIndex++;
135                          size = endOffset - offset;
136                      }
137  
138                      int count = overlapIndex - startIndex;
139  
140                      list.RemoveRange(startIndex, count);
141  
142                      overlapIndex = startIndex;
143                  }
144                  else
145                  {
146                      overlapIndex = ~overlapIndex;
147                  }
148  
149                  list.Insert(overlapIndex, new Range(offset, size));
150              }
151              else
152              {
153                  _ranges = new List<Range>
154                  {
155                      new Range(offset, size)
156                  };
157              }
158          }
159  
160          public readonly bool OverlapsWith(int offset, int size)
161          {
162              var list = _ranges;
163              if (list == null)
164              {
165                  return false;
166              }
167  
168              return BinarySearch(list, offset, size) >= 0;
169          }
170  
171          public readonly List<Range> FindOverlaps(int offset, int size)
172          {
173              var list = _ranges;
174              if (list == null)
175              {
176                  return null;
177              }
178  
179              List<Range> result = null;
180  
181              int index = BinarySearch(list, offset, size);
182  
183              if (index >= 0)
184              {
185                  while (index > 0 && list[index - 1].OverlapsWith(offset, size))
186                  {
187                      index--;
188                  }
189  
190                  do
191                  {
192                      (result ??= new List<Range>()).Add(list[index++]);
193                  }
194                  while (index < list.Count && list[index].OverlapsWith(offset, size));
195              }
196  
197              return result;
198          }
199  
200          private static int BinarySearch(List<Range> list, int offset, int size)
201          {
202              int left = 0;
203              int right = list.Count - 1;
204  
205              while (left <= right)
206              {
207                  int range = right - left;
208  
209                  int middle = left + (range >> 1);
210  
211                  var item = list[middle];
212  
213                  if (item.OverlapsWith(offset, size))
214                  {
215                      return middle;
216                  }
217  
218                  if (offset < item.Offset)
219                  {
220                      right = middle - 1;
221                  }
222                  else
223                  {
224                      left = middle + 1;
225                  }
226              }
227  
228              return ~left;
229          }
230  
231          public readonly void FillData(Span<byte> baseData, Span<byte> modData, int offset, Span<byte> result)
232          {
233              int size = baseData.Length;
234              int endOffset = offset + size;
235  
236              var list = _ranges;
237              if (list == null)
238              {
239                  baseData.CopyTo(result);
240              }
241  
242              int srcOffset = offset;
243              int dstOffset = 0;
244              bool activeRange = false;
245  
246              for (int i = 0; i < list.Count; i++)
247              {
248                  var range = list[i];
249  
250                  int rangeEnd = range.Offset + range.Size;
251  
252                  if (activeRange)
253                  {
254                      if (range.Offset >= endOffset)
255                      {
256                          break;
257                      }
258                  }
259                  else
260                  {
261                      if (rangeEnd <= offset)
262                      {
263                          continue;
264                      }
265  
266                      activeRange = true;
267                  }
268  
269                  int baseSize = range.Offset - srcOffset;
270  
271                  if (baseSize > 0)
272                  {
273                      baseData.Slice(dstOffset, baseSize).CopyTo(result.Slice(dstOffset, baseSize));
274                      srcOffset += baseSize;
275                      dstOffset += baseSize;
276                  }
277  
278                  int modSize = Math.Min(rangeEnd - srcOffset, endOffset - srcOffset);
279                  if (modSize != 0)
280                  {
281                      modData.Slice(dstOffset, modSize).CopyTo(result.Slice(dstOffset, modSize));
282                      srcOffset += modSize;
283                      dstOffset += modSize;
284                  }
285              }
286  
287              int baseSizeEnd = endOffset - srcOffset;
288  
289              if (baseSizeEnd > 0)
290              {
291                  baseData.Slice(dstOffset, baseSizeEnd).CopyTo(result.Slice(dstOffset, baseSizeEnd));
292              }
293          }
294  
295          public readonly int Count()
296          {
297              return _ranges?.Count ?? 0;
298          }
299  
300          public void Clear()
301          {
302              _ranges = null;
303          }
304      }
305  }