blob: 9bcb7873e009b046e070a8b26a6d8ccc851cdee8 (
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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
|
using System.Collections.Generic;
namespace Ryujinx.HLE.Memory
{
class ArenaAllocator
{
private class Region
{
public long Position { get; set; }
public long Size { get; set; }
public Region(long Position, long Size)
{
this.Position = Position;
this.Size = Size;
}
}
private LinkedList<Region> FreeRegions;
public long TotalAvailableSize { get; private set; }
public long TotalUsedSize { get; private set; }
public ArenaAllocator(long ArenaSize)
{
TotalAvailableSize = ArenaSize;
FreeRegions = new LinkedList<Region>();
FreeRegions.AddFirst(new Region(0, ArenaSize));
}
public bool TryAllocate(long Size, out long Position)
{
LinkedListNode<Region> Node = FreeRegions.First;
while (Node != null)
{
Region Rg = Node.Value;
if ((ulong)Rg.Size >= (ulong)Size)
{
Position = Rg.Position;
Rg.Position += Size;
Rg.Size -= Size;
if (Rg.Size == 0)
{
//Region is empty, just remove it.
FreeRegions.Remove(Node);
}
else if (Node.Previous != null)
{
//Re-sort based on size (smaller first).
Node = Node.Previous;
FreeRegions.Remove(Node.Next);
while (Node != null && (ulong)Node.Value.Size > (ulong)Rg.Size)
{
Node = Node.Previous;
}
if (Node != null)
{
FreeRegions.AddAfter(Node, Rg);
}
else
{
FreeRegions.AddFirst(Rg);
}
}
TotalUsedSize += Size;
return true;
}
Node = Node.Next;
}
Position = 0;
return false;
}
public void Free(long Position, long Size)
{
long End = Position + Size;
Region NewRg = new Region(Position, Size);
LinkedListNode<Region> Node = FreeRegions.First;
LinkedListNode<Region> PrevSz = null;
while (Node != null)
{
LinkedListNode<Region> NextNode = Node.Next;
Region Rg = Node.Value;
long RgEnd = Rg.Position + Rg.Size;
if (Rg.Position == End)
{
//Current region position matches the end of the freed region,
//just merge the two and remove the current region from the list.
NewRg.Size += Rg.Size;
FreeRegions.Remove(Node);
}
else if (RgEnd == Position)
{
//End of the current region matches the position of the freed region,
//just merge the two and remove the current region from the list.
NewRg.Position = Rg.Position;
NewRg.Size += Rg.Size;
FreeRegions.Remove(Node);
}
else
{
if (PrevSz == null)
{
PrevSz = Node;
}
else if ((ulong)Rg.Size < (ulong)NewRg.Size &&
(ulong)Rg.Size > (ulong)PrevSz.Value.Size)
{
PrevSz = Node;
}
}
Node = NextNode;
}
if (PrevSz != null && (ulong)PrevSz.Value.Size < (ulong)Size)
{
FreeRegions.AddAfter(PrevSz, NewRg);
}
else
{
FreeRegions.AddFirst(NewRg);
}
TotalUsedSize -= Size;
}
}
}
|
