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
|
#pragma once
#include <stdexcept>
#include <vector>
#include <stack>
#include <memory>
using namespace std;
template <typename T, typename Index>
class ListAlloc {
static_assert(is_integral_v<Index> && is_unsigned_v<Index>);
public:
const size_t capacity;
ListAlloc(size_t capacity);
~ListAlloc();
template <typename... Args>
Index allocate(Args... args);
void deallocate(Index index);
T* at(Index index);
private:
char *buffer;
stack<Index> freeStack;
size_t cursor = 0;
};
template <typename T, typename Index>
class ListAllocRef {
static_assert(is_integral_v<Index> && is_unsigned_v<Index>);
public:
ListAllocRef() : index(-1) {}
ListAllocRef(Index index) : index(index) {}
~ListAllocRef() {
if (index != (Index)-1) {
assert(false && "Non-empty ListAllocRef upon destruction");
}
}
// No copying
ListAllocRef(const ListAllocRef<T, Index> &other) = delete;
ListAllocRef<T, Index>& operator=(const ListAllocRef<T, Index> &other) = delete;
operator bool() const {
return index != (Index)-1;
}
ListAllocRef<T, Index>& operator=(Index newIndex) {
if (index != (Index)-1) {
throw logic_error("operator= on non-empty ListAllocRef");
}
index = newIndex;
return *this;
}
T* get(ListAlloc<T, Index> &allocator) {
return allocator.at(index);
}
const T* get(ListAlloc<T, Index> &allocator) const {
return allocator.at(index);
}
void deallocate(ListAlloc<T, Index> &allocator) {
if (index != (Index)-1) {
allocator.deallocate(index);
index = -1;
}
}
private:
Index index;
};
template <typename T, typename Index>
ListAlloc<T, Index>::ListAlloc(size_t capacity)
: capacity(capacity)
, buffer(new char[capacity * sizeof(T)]) {
size_t largestIndex = capacity - 1;
if (capacity != 0 && (size_t)(Index)largestIndex != largestIndex) {
throw logic_error("Capacity too large for index type in ListAlloc");
}
fprintf(stderr, "ListAlloc with capacity=%zu, size=%zu\n", capacity, capacity * sizeof(T));
}
template <typename T, typename Index>
ListAlloc<T, Index>::~ListAlloc() {
if (freeStack.size() != cursor) {
assert(false && "Not all entries deallocated in ~ListAlloc");
}
delete[] buffer;
}
template <typename T, typename Index>
template <typename... Args>
Index ListAlloc<T, Index>::allocate(Args... args) {
Index index;
if (!freeStack.empty()) {
index = freeStack.top();
freeStack.pop();
} else if (cursor < capacity) {
index = cursor++;
} else {
throw runtime_error("Out of memory in ListAlloc");
}
new(at(index)) T(args...);
return index;
}
template <typename T, typename Index>
void ListAlloc<T, Index>::deallocate(Index index) {
at(index)->~T();
freeStack.push(index);
}
template <typename T, typename Index>
T* ListAlloc<T, Index>::at(Index index) {
return (T*)&buffer[index * sizeof(T)];
}
|
