blob: 6e8682c1655c6727c02c777f549c3d2b13591dcf (
plain)
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
|
#ifndef SLANG_VIRTUAL_POOL_ALLOCATOR_H
#define SLANG_VIRTUAL_POOL_ALLOCATOR_H
namespace Slang
{
/// A virtual free-list allocater.
/// This class doesn't actually allocates memory, instead it operates on a
/// virtual integer space. Can be used to implement various types of object pools
/// that needs to support contiguous allocations of more than one elements.
class VirtualObjectPool
{
public:
struct FreeListNode
{
int Offset;
int Length;
FreeListNode* prev;
FreeListNode* next;
};
FreeListNode* freeListHead = nullptr;
public:
void destroy()
{
auto list = freeListHead;
while (list)
{
auto next = list->next;
delete list;
list = next;
}
freeListHead = nullptr;
}
~VirtualObjectPool() { destroy(); }
void initPool(int numElements)
{
freeListHead = new FreeListNode();
freeListHead->prev = freeListHead->next = nullptr;
freeListHead->Offset = 0;
freeListHead->Length = numElements;
}
int alloc(int size)
{
if (!freeListHead)
return -1;
auto freeBlock = freeListHead;
while (freeBlock && freeBlock->Length < size)
freeBlock = freeBlock->next;
if (!freeBlock || freeBlock->Length < size)
return -1;
int result = freeBlock->Offset;
freeBlock->Offset += size;
freeBlock->Length -= size;
if (freeBlock->Length == 0)
{
if (freeBlock->prev)
freeBlock->prev->next = freeBlock->next;
if (freeBlock->next)
freeBlock->next->prev = freeBlock->prev;
if (freeBlock == freeListHead)
freeListHead = freeBlock->next;
delete freeBlock;
}
return result;
}
void free(int offset, int size)
{
if (!freeListHead)
{
freeListHead = new FreeListNode();
freeListHead->next = freeListHead->prev = nullptr;
freeListHead->Length = size;
freeListHead->Offset = offset;
return;
}
auto freeListNode = freeListHead;
FreeListNode* prevFreeNode = nullptr;
while (freeListNode && freeListNode->Offset < offset + size)
{
prevFreeNode = freeListNode;
freeListNode = freeListNode->next;
}
FreeListNode* newNode = new FreeListNode();
newNode->Offset = offset;
newNode->Length = size;
newNode->prev = prevFreeNode;
newNode->next = freeListNode;
if (freeListNode)
freeListNode->prev = newNode;
if (prevFreeNode)
prevFreeNode->next = newNode;
if (freeListNode == freeListHead)
freeListHead = newNode;
if (prevFreeNode && prevFreeNode->Offset + prevFreeNode->Length == newNode->Offset)
{
prevFreeNode->Length += newNode->Length;
prevFreeNode->next = freeListNode;
if (freeListNode)
freeListNode->prev = prevFreeNode;
delete newNode;
newNode = prevFreeNode;
}
if (freeListNode && newNode->Offset + newNode->Length == freeListNode->Offset)
{
newNode->Length += freeListNode->Length;
newNode->next = freeListNode->next;
if (freeListNode->next)
freeListNode->next->prev = newNode;
delete freeListNode;
}
}
};
} // namespace Slang
#endif
|
