Blender V5.3
BLI_stack.hh
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2023 Blender Authors
2 *
3 * SPDX-License-Identifier: GPL-2.0-or-later */
4
5#pragma once
6
29
30#include "BLI_allocator.hh"
31#include "BLI_memory_utils.hh"
32#include "BLI_span.hh"
33
34namespace blender {
35
36namespace detail {
41template<typename T> struct StackChunk {
50
52 {
53 return capacity_end - begin;
54 }
55};
56} // namespace detail
57
58template<
60 typename T,
66 int64_t InlineBufferCapacity = default_inline_buffer_capacity(sizeof(T)),
71 typename Allocator = GuardedAllocator>
72class Stack {
73 public:
74 using value_type = T;
75 using pointer = T *;
76 using const_pointer = const T *;
77 using reference = T &;
78 using const_reference = const T &;
80
81 private:
83
92 T *top_;
93
95 Chunk *top_chunk_;
96
100 int64_t size_;
101
104
109 Chunk inline_chunk_;
110
112 BLI_NO_UNIQUE_ADDRESS Allocator allocator_;
113
114 public:
118 Stack(Allocator allocator = {}) noexcept : allocator_(allocator)
119 {
120 inline_chunk_.below = nullptr;
121 inline_chunk_.above = nullptr;
122 inline_chunk_.begin = inline_buffer_;
123 inline_chunk_.capacity_end = inline_buffer_ + InlineBufferCapacity;
124
125 top_ = inline_buffer_;
126 top_chunk_ = &inline_chunk_;
127 size_ = 0;
128 }
129
130 Stack(NoExceptConstructor, Allocator allocator = {}) noexcept : Stack(allocator) {}
131
136 Stack(Span<T> values, Allocator allocator = {}) : Stack(NoExceptConstructor(), allocator)
137 {
138 this->push_multiple(values);
139 }
140
150 Stack(const std::initializer_list<T> &values, Allocator allocator = {})
151 : Stack(Span<T>(values), allocator)
152 {
153 }
154
155 Stack(const Stack &other) : Stack(NoExceptConstructor(), other.allocator_)
156 {
157 for (const Chunk *chunk = &other.inline_chunk_; chunk; chunk = chunk->above) {
158 const T *begin = chunk->begin;
159 const T *end = (chunk == other.top_chunk_) ? other.top_ : chunk->capacity_end;
160 this->push_multiple(Span<T>(begin, end - begin));
161 }
162 }
163
164 Stack(Stack &&other) noexcept(std::is_nothrow_move_constructible_v<T>)
165 : Stack(NoExceptConstructor(), other.allocator_)
166 {
168 other.inline_buffer_, std::min(other.size_, InlineBufferCapacity), inline_buffer_);
169
170 inline_chunk_.above = other.inline_chunk_.above;
171 size_ = other.size_;
172
173 if (inline_chunk_.above != nullptr) {
174 inline_chunk_.above->below = &inline_chunk_;
175 }
176
177 if (size_ <= InlineBufferCapacity) {
178 top_chunk_ = &inline_chunk_;
179 top_ = inline_buffer_ + size_;
180 }
181 else {
182 top_chunk_ = other.top_chunk_;
183 top_ = other.top_;
184 }
185
186 other.size_ = 0;
187 other.inline_chunk_.above = nullptr;
188 other.top_chunk_ = &other.inline_chunk_;
189 other.top_ = other.top_chunk_->begin;
190 }
191
193 {
194 this->destruct_all_elements();
195 Chunk *above_chunk;
196 for (Chunk *chunk = inline_chunk_.above; chunk; chunk = above_chunk) {
197 above_chunk = chunk->above;
198 allocator_.deallocate(chunk);
199 }
200 }
201
202 Stack &operator=(const Stack &other)
203 {
204 return copy_assign_container(*this, other);
205 }
206
208 {
209 return move_assign_container(*this, std::move(other));
210 }
211
215 void push(const T &value)
216 {
217 this->push_as(value);
218 }
219 void push(T &&value)
220 {
221 this->push_as(std::move(value));
222 }
223 /* This is similar to `std::stack::emplace`. */
224 template<typename... ForwardT> void push_as(ForwardT &&...value)
225 {
226 if (top_ == top_chunk_->capacity_end) {
227 this->activate_next_chunk(1);
228 }
229 try {
230 new (top_) T(std::forward<ForwardT>(value)...);
231 top_++;
232 size_++;
233 }
234 catch (...) {
235 this->move_top_pointer_back_to_below_chunk();
236 throw;
237 }
238 }
239
245 {
246 BLI_assert(size_ > 0);
247 T value = std::move(*(top_ - 1));
248 top_--;
249 top_->~T();
250 size_--;
251
252 if (top_ == top_chunk_->begin) {
253 if (top_chunk_->below != nullptr) {
254 top_chunk_ = top_chunk_->below;
255 top_ = top_chunk_->capacity_end;
256 }
257 }
258 return value;
259 }
260
266 {
267 BLI_assert(size_ > 0);
268 BLI_assert(top_ > top_chunk_->begin);
269 return *(top_ - 1);
270 }
271 const T &peek() const
272 {
273 BLI_assert(size_ > 0);
274 BLI_assert(top_ > top_chunk_->begin);
275 return *(top_ - 1);
276 }
277
284 {
285 Span<T> remaining_values = values;
286 while (!remaining_values.is_empty()) {
287 if (top_ == top_chunk_->capacity_end) {
288 this->activate_next_chunk(remaining_values.size());
289 }
290
291 const int64_t remaining_capacity = top_chunk_->capacity_end - top_;
292 const int64_t amount = std::min(remaining_values.size(), remaining_capacity);
293 try {
294 uninitialized_copy_n(remaining_values.data(), amount, top_);
295 }
296 catch (...) {
297 this->move_top_pointer_back_to_below_chunk();
298 throw;
299 }
300 top_ += amount;
301 size_ += amount;
302
303 remaining_values = remaining_values.drop_front(amount);
304 }
305 }
306
310 bool is_empty() const
311 {
312 return size_ == 0;
313 }
314
318 int64_t size() const
319 {
320 return size_;
321 }
322
327 void clear()
328 {
329 this->destruct_all_elements();
330 top_chunk_ = &inline_chunk_;
331 top_ = top_chunk_->begin;
332 }
333
338 {
339 std::destroy_at(this);
340 new (this) Stack(NoExceptConstructor{});
341 }
342
343 /* This should only be called by unit tests. */
345 {
346 if (size_ == 0) {
347 return top_ == inline_chunk_.begin;
348 }
349 return top_ > top_chunk_->begin;
350 }
351
352 private:
360 void activate_next_chunk(const int64_t size_hint)
361 {
362 BLI_assert(top_ == top_chunk_->capacity_end);
363 if (top_chunk_->above == nullptr) {
364 const int64_t new_capacity = std::max(size_hint, top_chunk_->capacity() * 2 + 10);
365
366 /* Do a single memory allocation for the Chunk and the array it references. */
367 void *buffer = allocator_.allocate(
368 sizeof(Chunk) + sizeof(T) * new_capacity + alignof(T), alignof(Chunk), AT);
369 void *chunk_buffer = buffer;
370 void *data_buffer = reinterpret_cast<void *>(
371 (reinterpret_cast<uintptr_t>(buffer) + sizeof(Chunk) + alignof(T) - 1) &
372 ~(alignof(T) - 1));
373
374 Chunk *new_chunk = new (chunk_buffer) Chunk();
375 new_chunk->begin = static_cast<T *>(data_buffer);
376 new_chunk->capacity_end = new_chunk->begin + new_capacity;
377 new_chunk->above = nullptr;
378 new_chunk->below = top_chunk_;
379 top_chunk_->above = new_chunk;
380 }
381 top_chunk_ = top_chunk_->above;
382 top_ = top_chunk_->begin;
383 }
384
385 void move_top_pointer_back_to_below_chunk()
386 {
387 /* This makes sure that the invariant stays intact after a failed push. */
388 if (size_ == 0) {
389 top_ = inline_chunk_.begin;
390 }
391 else if (top_ == top_chunk_->begin) {
392 top_chunk_ = top_chunk_->below;
393 top_ = top_chunk_->capacity_end;
394 }
395 }
396
397 void destruct_all_elements()
398 {
399 for (T *value = top_chunk_->begin; value != top_; value++) {
400 value->~T();
401 }
402 for (Chunk *chunk = top_chunk_->below; chunk; chunk = chunk->below) {
403 for (T *value = chunk->begin; value != chunk->capacity_end; value++) {
404 value->~T();
405 }
406 }
407 }
408};
409
414template<typename T, int64_t InlineBufferCapacity = default_inline_buffer_capacity(sizeof(T))>
416
417} // namespace blender
#define AT
#define BLI_NO_UNIQUE_ADDRESS
long long int int64_t
constexpr Span drop_front(int64_t n) const
Definition BLI_span.hh:175
constexpr const T * data() const
Definition BLI_span.hh:219
constexpr int64_t size() const
Definition BLI_span.hh:256
constexpr bool is_empty() const
Definition BLI_span.hh:264
Stack(Allocator allocator={}) noexcept
Definition BLI_stack.hh:118
Stack(NoExceptConstructor, RawAllocator allocator={}) noexcept
Definition BLI_stack.hh:130
Stack(Span< T > values, RawAllocator allocator={})
Definition BLI_stack.hh:136
const T & const_reference
Definition BLI_stack.hh:78
Stack(Stack &&other) noexcept(std::is_nothrow_move_constructible_v< T >)
Definition BLI_stack.hh:164
Stack(const std::initializer_list< T > &values, RawAllocator allocator={})
Definition BLI_stack.hh:150
const T * const_pointer
Definition BLI_stack.hh:76
void push_multiple(Span< T > values)
Definition BLI_stack.hh:283
int64_t size_type
Definition BLI_stack.hh:79
#define T
BMesh Iterators.
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
__int64 int64_t
Definition BKE_text.h:90
Stack< T, InlineBufferCapacity, RawAllocator > RawStack
Definition BLI_stack.hh:415
Container & copy_assign_container(Container &dst, const Container &src)
Container & move_assign_container(Container &dst, Container &&src) noexcept(std::is_nothrow_move_constructible_v< Container >)
_W64 unsigned int uintptr_t
Definition BKE_text.h:120
constexpr int64_t default_inline_buffer_capacity(size_t element_size)
void uninitialized_relocate_n(T *src, int64_t n, T *dst)
void uninitialized_copy_n(const T *src, int64_t n, T *dst)
int64_t capacity() const
Definition BLI_stack.hh:51