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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
|
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Diagnostics.CodeAnalysis;
namespace Ryujinx.Cpu.LightningJit.Cache
{
class CacheMemoryAllocator
{
private readonly struct MemoryBlock : IComparable<MemoryBlock>
{
public int Offset { get; }
public int Size { get; }
public MemoryBlock(int offset, int size)
{
Offset = offset;
Size = size;
}
public int CompareTo([AllowNull] MemoryBlock other)
{
return Offset.CompareTo(other.Offset);
}
}
private readonly List<MemoryBlock> _blocks = new();
public CacheMemoryAllocator(int capacity)
{
_blocks.Add(new MemoryBlock(0, capacity));
}
public int Allocate(int size)
{
for (int i = 0; i < _blocks.Count; i++)
{
MemoryBlock block = _blocks[i];
if (block.Size > size)
{
_blocks[i] = new(block.Offset + size, block.Size - size);
return block.Offset;
}
else if (block.Size == size)
{
_blocks.RemoveAt(i);
return block.Offset;
}
}
// We don't have enough free memory to perform the allocation.
return -1;
}
public void ForceAllocation(int offset, int size)
{
int index = _blocks.BinarySearch(new(offset, size));
if (index < 0)
{
index = ~index;
}
int endOffset = offset + size;
MemoryBlock block = _blocks[index];
Debug.Assert(block.Offset <= offset && block.Offset + block.Size >= endOffset);
if (offset > block.Offset && endOffset < block.Offset + block.Size)
{
_blocks[index] = new(block.Offset, offset - block.Offset);
_blocks.Insert(index + 1, new(endOffset, (block.Offset + block.Size) - endOffset));
}
else if (offset > block.Offset)
{
_blocks[index] = new(block.Offset, offset - block.Offset);
}
else if (endOffset < block.Offset + block.Size)
{
_blocks[index] = new(endOffset, (block.Offset + block.Size) - endOffset);
}
else
{
_blocks.RemoveAt(index);
}
}
public void Free(int offset, int size)
{
Insert(new MemoryBlock(offset, size));
}
private void Insert(MemoryBlock block)
{
int index = _blocks.BinarySearch(block);
if (index < 0)
{
index = ~index;
}
if (index < _blocks.Count)
{
MemoryBlock next = _blocks[index];
int endOffs = block.Offset + block.Size;
if (next.Offset == endOffs)
{
block = new MemoryBlock(block.Offset, block.Size + next.Size);
_blocks.RemoveAt(index);
}
}
if (index > 0)
{
MemoryBlock prev = _blocks[index - 1];
if (prev.Offset + prev.Size == block.Offset)
{
block = new MemoryBlock(block.Offset - prev.Size, block.Size + prev.Size);
_blocks.RemoveAt(--index);
}
}
_blocks.Insert(index, block);
}
public void Clear()
{
_blocks.Clear();
}
}
}
|
