blob: 91600f981ba284aa034c44cbf06a9e8b232584d3 (
plain) (
blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
|
using System;
namespace Ryujinx.Horizon.Sdk.Ngc.Detail
{
readonly struct MatchRange
{
public readonly int StartOffset;
public readonly int EndOffset;
public MatchRange(int startOffset, int endOffset)
{
StartOffset = startOffset;
EndOffset = endOffset;
}
}
struct MatchRangeList
{
private int _capacity;
private int _count;
private MatchRange[] _ranges;
public readonly int Count => _count;
public readonly MatchRange this[int index] => _ranges[index];
public MatchRangeList()
{
_capacity = 0;
_count = 0;
_ranges = Array.Empty<MatchRange>();
}
public void Add(int startOffset, int endOffset)
{
if (_count == _capacity)
{
int newCapacity = _count * 2;
if (newCapacity == 0)
{
newCapacity = 1;
}
Array.Resize(ref _ranges, newCapacity);
_capacity = newCapacity;
}
_ranges[_count++] = new(startOffset, endOffset);
}
public readonly MatchRangeList Deduplicate()
{
MatchRangeList output = new();
if (_count != 0)
{
int prevStartOffset = _ranges[0].StartOffset;
int prevEndOffset = _ranges[0].EndOffset;
for (int index = 1; index < _count; index++)
{
int currStartOffset = _ranges[index].StartOffset;
int currEndOffset = _ranges[index].EndOffset;
if (prevStartOffset == currStartOffset)
{
if (prevEndOffset <= currEndOffset)
{
prevEndOffset = currEndOffset;
}
}
else if (prevEndOffset <= currStartOffset)
{
output.Add(prevStartOffset, prevEndOffset);
prevStartOffset = currStartOffset;
prevEndOffset = currEndOffset;
}
}
output.Add(prevStartOffset, prevEndOffset);
}
return output;
}
public readonly int Find(int startOffset, int endOffset)
{
int baseIndex = 0;
int range = _count;
while (range != 0)
{
MatchRange currRange = _ranges[baseIndex + (range / 2)];
if (currRange.StartOffset < startOffset || (currRange.StartOffset == startOffset && currRange.EndOffset < endOffset))
{
int nextHalf = (range / 2) + 1;
baseIndex += nextHalf;
range -= nextHalf;
}
else
{
range /= 2;
}
}
return baseIndex;
}
}
}
|