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
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
|
/*
* This program is free software; you can redistribute it and/or
* modify it under the terms of the GNU General Public License
* as published by the Free Software Foundation; either version 2
* of the License, or (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software Foundation,
* Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
*/
#ifndef __BLI_STACK_HH__
#define __BLI_STACK_HH__
/** \file
* \ingroup bli
*
* A `blender::Stack<T>` is a dynamically growing FILO (first-in, last-out) data structure. It is
* designed to be a more convenient and efficient replacement for `std::stack`.
*
* The improved efficiency is mainly achieved by supporting small buffer optimization. As long as
* the number of elements added to the stack stays below InlineBufferCapacity, no heap allocation
* is done. Consequently, values stored in the stack have to be movable and they might be moved,
* when the stack is moved.
*
* A Vector can be used to emulate a stack. However, this stack implementation is more efficient
* when all you have to do is to push and pop elements. That is because a vector guarantees that
* all elements are in a contiguous array. Therefore, it has to copy all elements to a new buffer
* when it grows. This stack implementation does not have to copy all previously pushed elements
* when it grows.
*
* blender::Stack is implemented using a double linked list of chunks. Each chunk contains an array
* of elements. The chunk size increases exponentially with every new chunk that is required. The
* lowest chunk, i.e. the one that is used for the first few pushed elements, is embedded into the
* stack.
*/
#include "BLI_allocator.hh"
#include "BLI_array_ref.hh"
#include "BLI_memory_utils.hh"
namespace blender {
/**
* A StackChunk references a contiguous memory buffer. Multiple StackChunk instances are linked in
* a double linked list.
*/
template<typename T> struct StackChunk {
/** The below chunk contains the elements that have been pushed on the stack before. */
StackChunk *below;
/** The above chunk contains the elements that have been pushed on the stack afterwards. */
StackChunk *above;
/** Pointer to the first element of the referenced buffer. */
T *begin;
/** Pointer to one element past the end of the referenced buffer. */
T *capacity_end;
uint capacity() const
{
return capacity_end - begin;
}
};
template<
/** Type of the elements that are stored in the stack. */
typename T,
/**
* The number of values that can be stored in this stack, without doing a heap allocation.
* Sometimes it can make sense to increase this value a lot. The memory in the inline buffer is
* not initialized when it is not needed.
*
* When T is large, the small buffer optimization is disabled by default to avoid large
* unexpected allocations on the stack. It can still be enabled explicitely though.
*/
uint InlineBufferCapacity = (sizeof(T) < 100) ? 4 : 0,
/**
* The allocator used by this stack. Should rarely be changed, except when you don't want that
* MEM_* is used internally.
*/
typename Allocator = GuardedAllocator>
class Stack {
private:
using Chunk = StackChunk<T>;
/**
* Points to one element after top-most value in the stack.
*
* Invariant:
* If m_size == 0
* then: m_top == m_inline_chunk.begin
* else: &peek() == m_top - 1;
*/
T *m_top;
/** Points to the chunk that references the memory pointed to by m_top. */
Chunk *m_top_chunk;
/**
* Number of elements in the entire stack. The sum of initialized element counts in the chunks.
*/
uint m_size;
/** The buffer used to implement small object optimization. */
AlignedBuffer<sizeof(T) * InlineBufferCapacity, alignof(T)> m_inline_buffer;
/**
* A chunk referencing the inline buffer. This is always the bottom-most chunk.
* So m_inline_chunk.below == nullptr.
*/
Chunk m_inline_chunk;
/** Used for allocations when the inline buffer is not large enough. */
Allocator m_allocator;
public:
/**
* Initialize an empty stack. No heap allocation is done.
*/
Stack(Allocator allocator = {}) : m_allocator(allocator)
{
T *inline_buffer = this->inline_buffer();
m_inline_chunk.below = nullptr;
m_inline_chunk.above = nullptr;
m_inline_chunk.begin = inline_buffer;
m_inline_chunk.capacity_end = inline_buffer + InlineBufferCapacity;
m_top = inline_buffer;
m_top_chunk = &m_inline_chunk;
m_size = 0;
}
/**
* Create a new stack that contains the given elements. The values are pushed to the stack in
* the order they are in the array.
*/
Stack(ArrayRef<T> values) : Stack()
{
this->push_multiple(values);
}
/**
* Create a new stack that contains the given elements. The values are pushed to the stack in the
* order they are in the array.
*
* Example:
* Stack<int> stack = {4, 5, 6};
* assert(stack.pop() == 6);
* assert(stack.pop() == 5);
*/
Stack(const std::initializer_list<T> &values) : Stack(ArrayRef<T>(values))
{
}
Stack(const Stack &other) : Stack(other.m_allocator)
{
for (const Chunk *chunk = &other.m_inline_chunk; chunk; chunk = chunk->above) {
const T *begin = chunk->begin;
const T *end = (chunk == other.m_top_chunk) ? other.m_top : chunk->capacity_end;
this->push_multiple(ArrayRef<T>(begin, end - begin));
}
}
Stack(Stack &&other) noexcept : Stack(other.m_allocator)
{
uninitialized_relocate_n(other.inline_buffer(),
std::min(other.m_size, InlineBufferCapacity),
this->inline_buffer());
m_inline_chunk.above = other.m_inline_chunk.above;
m_size = other.m_size;
if (m_size <= InlineBufferCapacity) {
m_top_chunk = &m_inline_chunk;
m_top = this->inline_buffer() + m_size;
}
else {
m_top_chunk = other.m_top_chunk;
m_top = other.m_top;
}
other.m_size = 0;
other.m_inline_chunk.above = nullptr;
other.m_top_chunk = &other.m_inline_chunk;
other.m_top = other.m_top_chunk->begin;
}
~Stack()
{
this->destruct_all_elements();
Chunk *above_chunk;
for (Chunk *chunk = m_inline_chunk.above; chunk; chunk = above_chunk) {
above_chunk = chunk->above;
m_allocator.deallocate(chunk);
}
}
Stack &operator=(const Stack &stack)
{
if (this == &stack) {
return *this;
}
this->~Stack();
new (this) Stack(stack);
return *this;
}
Stack &operator=(Stack &&stack)
{
if (this == &stack) {
return *this;
}
this->~Stack();
new (this) Stack(std::move(stack));
return *this;
}
/**
* Add a new element to the top of the stack.
*/
void push(const T &value)
{
if (m_top == m_top_chunk->capacity_end) {
this->activate_next_chunk(1);
}
new (m_top) T(value);
m_top++;
m_size++;
}
void push(T &&value)
{
if (m_top == m_top_chunk->capacity_end) {
this->activate_next_chunk(1);
}
new (m_top) T(std::move(value));
m_top++;
m_size++;
}
/**
* Remove and return the top-most element from the stack. This invokes undefined behavior when
* the stack is empty.
*/
T pop()
{
BLI_assert(m_size > 0);
m_top--;
T value = std::move(*m_top);
m_top->~T();
m_size--;
if (m_top == m_top_chunk->begin) {
if (m_top_chunk->below != nullptr) {
m_top_chunk = m_top_chunk->below;
m_top = m_top_chunk->capacity_end;
}
}
return value;
}
/**
* Get a reference to the top-most element without removing it from the stack. This invokes
* undefined behavior when the stack is empty.
*/
T &peek()
{
BLI_assert(m_size > 0);
BLI_assert(m_top > m_top_chunk->begin);
return *(m_top - 1);
}
const T &peek() const
{
BLI_assert(m_size > 0);
BLI_assert(m_top > m_top_chunk->begin);
return *(m_top - 1);
}
/**
* Add multiple elements to the stack. The values are pushed in the order they are in the array.
* This method is more efficient than pushing multiple elements individually and might cause less
* heap allocations.
*/
void push_multiple(ArrayRef<T> values)
{
ArrayRef<T> remaining_values = values;
while (!remaining_values.is_empty()) {
if (m_top == m_top_chunk->capacity_end) {
this->activate_next_chunk(remaining_values.size());
}
uint remaining_capacity = m_top_chunk->capacity_end - m_top;
uint amount = std::min(remaining_values.size(), remaining_capacity);
uninitialized_copy_n(remaining_values.data(), amount, m_top);
m_top += amount;
remaining_values = remaining_values.drop_front(amount);
}
m_size += values.size();
}
/**
* Returns true when the size is zero.
*/
bool is_empty() const
{
return m_size == 0;
}
/**
* Returns the number of elements in the stack.
*/
uint size() const
{
return m_size;
}
/**
* Removes all elements from the stack. The memory is not freed, so it is more efficient to reuse
* the stack than to create a new one.
*/
void clear()
{
this->destruct_all_elements();
m_top_chunk = &m_inline_chunk;
m_top = m_top_chunk->begin;
}
private:
T *inline_buffer() const
{
return (T *)m_inline_buffer.ptr();
}
/**
* Changes m_top_chunk to point to a new chunk that is above the current one. The new chunk might
* be smaller than the given size_hint. This happens when a chunk that has been allocated before
* is reused. The size of the new chunk will be at least one.
*
* This invokes undefined behavior when the currently active chunk is not full.
*/
void activate_next_chunk(uint size_hint)
{
BLI_assert(m_top == m_top_chunk->capacity_end);
if (m_top_chunk->above == nullptr) {
uint new_capacity = std::max(size_hint, m_top_chunk->capacity() * 2 + 10);
/* Do a single memory allocation for the Chunk and the array it references. */
void *buffer = m_allocator.allocate(
sizeof(Chunk) + sizeof(T) * new_capacity + alignof(T), alignof(Chunk), AT);
void *chunk_buffer = buffer;
void *data_buffer = (void *)(((uintptr_t)buffer + sizeof(Chunk) + alignof(T) - 1) &
~(alignof(T) - 1));
Chunk *new_chunk = new (chunk_buffer) Chunk();
new_chunk->begin = (T *)data_buffer;
new_chunk->capacity_end = new_chunk->begin + new_capacity;
new_chunk->above = nullptr;
new_chunk->below = m_top_chunk;
m_top_chunk->above = new_chunk;
}
m_top_chunk = m_top_chunk->above;
m_top = m_top_chunk->begin;
}
void destruct_all_elements()
{
for (T *value = m_top_chunk->begin; value != m_top; value++) {
value->~T();
}
for (Chunk *chunk = m_top_chunk->below; chunk; chunk = chunk->below) {
for (T *value = chunk->begin; value != chunk->capacity_end; value++) {
value->~T();
}
}
}
};
} /* namespace blender */
#endif /* __BLI_STACK_HH__ */
|