118 Stack(Allocator allocator = {})
noexcept : allocator_(allocator)
120 inline_chunk_.
below =
nullptr;
121 inline_chunk_.
above =
nullptr;
122 inline_chunk_.
begin = inline_buffer_;
123 inline_chunk_.
capacity_end = inline_buffer_ + InlineBufferCapacity;
125 top_ = inline_buffer_;
126 top_chunk_ = &inline_chunk_;
150 Stack(
const std::initializer_list<T> &values, Allocator allocator = {})
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));
164 Stack(
Stack &&other)
noexcept(std::is_nothrow_move_constructible_v<T>)
168 other.inline_buffer_, std::min(other.size_, InlineBufferCapacity), inline_buffer_);
170 inline_chunk_.above = other.inline_chunk_.above;
173 if (inline_chunk_.above !=
nullptr) {
174 inline_chunk_.above->below = &inline_chunk_;
177 if (size_ <= InlineBufferCapacity) {
178 top_chunk_ = &inline_chunk_;
179 top_ = inline_buffer_ + size_;
182 top_chunk_ = other.top_chunk_;
187 other.inline_chunk_.above =
nullptr;
188 other.top_chunk_ = &other.inline_chunk_;
189 other.top_ = other.top_chunk_->begin;
194 this->destruct_all_elements();
196 for (Chunk *chunk = inline_chunk_.above; chunk; chunk = above_chunk) {
197 above_chunk = chunk->
above;
198 allocator_.deallocate(chunk);
221 this->
push_as(std::move(value));
224 template<
typename... ForwardT>
void push_as(ForwardT &&...value)
226 if (top_ == top_chunk_->capacity_end) {
227 this->activate_next_chunk(1);
230 new (top_)
T(std::forward<ForwardT>(value)...);
235 this->move_top_pointer_back_to_below_chunk();
247 T value = std::move(*(top_ - 1));
252 if (top_ == top_chunk_->begin) {
253 if (top_chunk_->below !=
nullptr) {
254 top_chunk_ = top_chunk_->below;
255 top_ = top_chunk_->capacity_end;
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());
291 const int64_t remaining_capacity = top_chunk_->capacity_end - top_;
292 const int64_t amount = std::min(remaining_values.
size(), remaining_capacity);
297 this->move_top_pointer_back_to_below_chunk();
303 remaining_values = remaining_values.
drop_front(amount);
329 this->destruct_all_elements();
330 top_chunk_ = &inline_chunk_;
331 top_ = top_chunk_->begin;
339 std::destroy_at(
this);
347 return top_ == inline_chunk_.begin;
349 return top_ > top_chunk_->begin;
360 void activate_next_chunk(
const int64_t size_hint)
363 if (top_chunk_->
above ==
nullptr) {
364 const int64_t new_capacity = std::max(size_hint, top_chunk_->
capacity() * 2 + 10);
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) &
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;
381 top_chunk_ = top_chunk_->
above;
382 top_ = top_chunk_->
begin;
385 void move_top_pointer_back_to_below_chunk()
389 top_ = inline_chunk_.begin;
391 else if (top_ == top_chunk_->begin) {
392 top_chunk_ = top_chunk_->below;
393 top_ = top_chunk_->capacity_end;
397 void destruct_all_elements()
399 for (
T *value = top_chunk_->begin; value != top_; value++) {
402 for (Chunk *chunk = top_chunk_->below; chunk; chunk = chunk->below) {
403 for (
T *value = chunk->begin; value != chunk->capacity_end; value++) {
414template<
typename T,
int64_t InlineBufferCapacity = default_inline_buffer_capacity(sizeof(T))>
#define BLI_NO_UNIQUE_ADDRESS
constexpr Span drop_front(int64_t n) const
constexpr const T * data() const
constexpr int64_t size() const
constexpr bool is_empty() const
bool is_invariant_maintained() const
Stack(Allocator allocator={}) noexcept
Stack(NoExceptConstructor, RawAllocator allocator={}) noexcept
Stack(Span< T > values, RawAllocator allocator={})
void push_as(ForwardT &&...value)
Stack & operator=(Stack &&other)
const T & const_reference
Stack(Stack &&other) noexcept(std::is_nothrow_move_constructible_v< T >)
Stack(const std::initializer_list< T > &values, RawAllocator allocator={})
void push(const T &value)
void push_multiple(Span< T > values)
Stack & operator=(const Stack &other)
Stack(const Stack &other)
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
Stack< T, InlineBufferCapacity, RawAllocator > RawStack
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
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)