1  using System;
 2  
 3  namespace ARMeilleure.CodeGen.RegisterAllocators
 4  {
 5      unsafe struct UseList
 6      {
 7          private int* _items;
 8          private int _capacity;
 9  
10          public int Count { get; private set; }
11  
12          public readonly int FirstUse => Count > 0 ? _items[Count - 1] : LiveInterval.NotFound;
13          public readonly Span<int> Span => new(_items, Count);
14  
15          public void Add(int position)
16          {
17              if (Count + 1 > _capacity)
18              {
19                  var oldSpan = Span;
20  
21                  _capacity = Math.Max(4, _capacity * 2);
22                  _items = Allocators.Default.Allocate<int>((uint)_capacity);
23  
24                  var newSpan = Span;
25  
26                  oldSpan.CopyTo(newSpan);
27              }
28  
29              // Use positions are usually inserted in descending order, so inserting in descending order is faster,
30              // since the number of half exchanges is reduced.
31              int i = Count - 1;
32  
33              while (i >= 0 && _items[i] < position)
34              {
35                  _items[i + 1] = _items[i--];
36              }
37  
38              _items[i + 1] = position;
39              Count++;
40          }
41  
42          public readonly int NextUse(int position)
43          {
44              int index = NextUseIndex(position);
45  
46              return index != LiveInterval.NotFound ? _items[index] : LiveInterval.NotFound;
47          }
48  
49          public readonly int NextUseIndex(int position)
50          {
51              int i = Count - 1;
52  
53              if (i == -1 || position > _items[0])
54              {
55                  return LiveInterval.NotFound;
56              }
57  
58              while (i >= 0 && _items[i] < position)
59              {
60                  i--;
61              }
62  
63              return i;
64          }
65  
66          public UseList Split(int position)
67          {
68              int index = NextUseIndex(position);
69  
70              // Since the list is in descending order, the new split list takes the front of the list and the current
71              // list takes the back of the list.
72              UseList result = new()
73              {
74                  Count = index + 1,
75              };
76              result._capacity = result.Count;
77              result._items = _items;
78  
79              Count -= result.Count;
80              _capacity = Count;
81              _items += result.Count;
82  
83              return result;
84          }
85      }
86  }