Blender  V3.3
BLI_stack.hh
Go to the documentation of this file.
1 /* SPDX-License-Identifier: GPL-2.0-or-later */
2 
3 #pragma once
4 
28 #include "BLI_allocator.hh"
29 #include "BLI_memory_utils.hh"
30 #include "BLI_span.hh"
31 
32 namespace blender {
33 
38 template<typename T> struct StackChunk {
44  T *begin;
47 
48  int64_t capacity() const
49  {
50  return capacity_end - begin;
51  }
52 };
53 
54 template<
56  typename T,
62  int64_t InlineBufferCapacity = default_inline_buffer_capacity(sizeof(T)),
67  typename Allocator = GuardedAllocator>
68 class Stack {
69  public:
70  using value_type = T;
71  using pointer = T *;
72  using const_pointer = const T *;
73  using reference = T &;
74  using const_reference = const T &;
75  using size_type = int64_t;
76 
77  private:
78  using Chunk = StackChunk<T>;
79 
88  T *top_;
89 
91  Chunk *top_chunk_;
92 
96  int64_t size_;
97 
100 
105  Chunk inline_chunk_;
106 
108  BLI_NO_UNIQUE_ADDRESS Allocator allocator_;
109 
110  public:
114  Stack(Allocator allocator = {}) noexcept : allocator_(allocator)
115  {
116  inline_chunk_.below = nullptr;
117  inline_chunk_.above = nullptr;
118  inline_chunk_.begin = inline_buffer_;
119  inline_chunk_.capacity_end = inline_buffer_ + InlineBufferCapacity;
120 
121  top_ = inline_buffer_;
122  top_chunk_ = &inline_chunk_;
123  size_ = 0;
124  }
125 
126  Stack(NoExceptConstructor, Allocator allocator = {}) noexcept : Stack(allocator)
127  {
128  }
129 
134  Stack(Span<T> values, Allocator allocator = {}) : Stack(NoExceptConstructor(), allocator)
135  {
136  this->push_multiple(values);
137  }
138 
148  Stack(const std::initializer_list<T> &values, Allocator allocator = {})
149  : Stack(Span<T>(values), allocator)
150  {
151  }
152 
153  Stack(const Stack &other) : Stack(NoExceptConstructor(), other.allocator_)
154  {
155  for (const Chunk *chunk = &other.inline_chunk_; chunk; chunk = chunk->above) {
156  const T *begin = chunk->begin;
157  const T *end = (chunk == other.top_chunk_) ? other.top_ : chunk->capacity_end;
158  this->push_multiple(Span<T>(begin, end - begin));
159  }
160  }
161 
162  Stack(Stack &&other) noexcept(std::is_nothrow_move_constructible_v<T>)
163  : Stack(NoExceptConstructor(), other.allocator_)
164  {
165  uninitialized_relocate_n<T>(
166  other.inline_buffer_, std::min(other.size_, InlineBufferCapacity), inline_buffer_);
167 
168  inline_chunk_.above = other.inline_chunk_.above;
169  size_ = other.size_;
170 
171  if (inline_chunk_.above != nullptr) {
172  inline_chunk_.above->below = &inline_chunk_;
173  }
174 
175  if (size_ <= InlineBufferCapacity) {
176  top_chunk_ = &inline_chunk_;
177  top_ = inline_buffer_ + size_;
178  }
179  else {
180  top_chunk_ = other.top_chunk_;
181  top_ = other.top_;
182  }
183 
184  other.size_ = 0;
185  other.inline_chunk_.above = nullptr;
186  other.top_chunk_ = &other.inline_chunk_;
187  other.top_ = other.top_chunk_->begin;
188  }
189 
191  {
192  this->destruct_all_elements();
193  Chunk *above_chunk;
194  for (Chunk *chunk = inline_chunk_.above; chunk; chunk = above_chunk) {
195  above_chunk = chunk->above;
196  allocator_.deallocate(chunk);
197  }
198  }
199 
200  Stack &operator=(const Stack &other)
201  {
202  return copy_assign_container(*this, other);
203  }
204 
206  {
207  return move_assign_container(*this, std::move(other));
208  }
209 
213  void push(const T &value)
214  {
215  this->push_as(value);
216  }
217  void push(T &&value)
218  {
219  this->push_as(std::move(value));
220  }
221  /* This is similar to `std::stack::emplace`. */
222  template<typename... ForwardT> void push_as(ForwardT &&...value)
223  {
224  if (top_ == top_chunk_->capacity_end) {
225  this->activate_next_chunk(1);
226  }
227  try {
228  new (top_) T(std::forward<ForwardT>(value)...);
229  top_++;
230  size_++;
231  }
232  catch (...) {
233  this->move_top_pointer_back_to_below_chunk();
234  throw;
235  }
236  }
237 
242  T pop()
243  {
244  BLI_assert(size_ > 0);
245  T value = std::move(*(top_ - 1));
246  top_--;
247  top_->~T();
248  size_--;
249 
250  if (top_ == top_chunk_->begin) {
251  if (top_chunk_->below != nullptr) {
252  top_chunk_ = top_chunk_->below;
253  top_ = top_chunk_->capacity_end;
254  }
255  }
256  return value;
257  }
258 
263  T &peek()
264  {
265  BLI_assert(size_ > 0);
266  BLI_assert(top_ > top_chunk_->begin);
267  return *(top_ - 1);
268  }
269  const T &peek() const
270  {
271  BLI_assert(size_ > 0);
272  BLI_assert(top_ > top_chunk_->begin);
273  return *(top_ - 1);
274  }
275 
281  void push_multiple(Span<T> values)
282  {
283  Span<T> remaining_values = values;
284  while (!remaining_values.is_empty()) {
285  if (top_ == top_chunk_->capacity_end) {
286  this->activate_next_chunk(remaining_values.size());
287  }
288 
289  const int64_t remaining_capacity = top_chunk_->capacity_end - top_;
290  const int64_t amount = std::min(remaining_values.size(), remaining_capacity);
291  try {
292  uninitialized_copy_n(remaining_values.data(), amount, top_);
293  }
294  catch (...) {
295  this->move_top_pointer_back_to_below_chunk();
296  throw;
297  }
298  top_ += amount;
299  size_ += amount;
300 
301  remaining_values = remaining_values.drop_front(amount);
302  }
303  }
304 
308  bool is_empty() const
309  {
310  return size_ == 0;
311  }
312 
316  int64_t size() const
317  {
318  return size_;
319  }
320 
325  void clear()
326  {
327  this->destruct_all_elements();
328  top_chunk_ = &inline_chunk_;
329  top_ = top_chunk_->begin;
330  }
331 
332  /* This should only be called by unit tests. */
334  {
335  if (size_ == 0) {
336  return top_ == inline_chunk_.begin;
337  }
338  return top_ > top_chunk_->begin;
339  }
340 
341  private:
349  void activate_next_chunk(const int64_t size_hint)
350  {
351  BLI_assert(top_ == top_chunk_->capacity_end);
352  if (top_chunk_->above == nullptr) {
353  const int64_t new_capacity = std::max(size_hint, top_chunk_->capacity() * 2 + 10);
354 
355  /* Do a single memory allocation for the Chunk and the array it references. */
356  void *buffer = allocator_.allocate(
357  sizeof(Chunk) + sizeof(T) * new_capacity + alignof(T), alignof(Chunk), AT);
358  void *chunk_buffer = buffer;
359  void *data_buffer = reinterpret_cast<void *>(
360  (reinterpret_cast<uintptr_t>(buffer) + sizeof(Chunk) + alignof(T) - 1) &
361  ~(alignof(T) - 1));
362 
363  Chunk *new_chunk = new (chunk_buffer) Chunk();
364  new_chunk->begin = static_cast<T *>(data_buffer);
365  new_chunk->capacity_end = new_chunk->begin + new_capacity;
366  new_chunk->above = nullptr;
367  new_chunk->below = top_chunk_;
368  top_chunk_->above = new_chunk;
369  }
370  top_chunk_ = top_chunk_->above;
371  top_ = top_chunk_->begin;
372  }
373 
374  void move_top_pointer_back_to_below_chunk()
375  {
376  /* This makes sure that the invariant stays intact after a failed push. */
377  if (size_ == 0) {
378  top_ = inline_chunk_.begin;
379  }
380  else if (top_ == top_chunk_->begin) {
381  top_chunk_ = top_chunk_->below;
382  top_ = top_chunk_->capacity_end;
383  }
384  }
385 
386  void destruct_all_elements()
387  {
388  for (T *value = top_chunk_->begin; value != top_; value++) {
389  value->~T();
390  }
391  for (Chunk *chunk = top_chunk_->below; chunk; chunk = chunk->below) {
392  for (T *value = chunk->begin; value != chunk->capacity_end; value++) {
393  value->~T();
394  }
395  }
396  }
397 };
398 
403 template<typename T, int64_t InlineBufferCapacity = default_inline_buffer_capacity(sizeof(T))>
405 
406 } /* namespace blender */
#define BLI_assert(a)
Definition: BLI_assert.h:46
#define AT
#define BLI_NO_UNIQUE_ADDRESS
constexpr Span drop_front(int64_t n) const
Definition: BLI_span.hh:159
constexpr const T * data() const
Definition: BLI_span.hh:203
constexpr int64_t size() const
Definition: BLI_span.hh:240
constexpr bool is_empty() const
Definition: BLI_span.hh:248
bool is_invariant_maintained() const
Definition: BLI_stack.hh:333
Stack(Allocator allocator={}) noexcept
Definition: BLI_stack.hh:114
Stack(NoExceptConstructor, Allocator allocator={}) noexcept
Definition: BLI_stack.hh:126
Stack(Span< T > values, Allocator allocator={})
Definition: BLI_stack.hh:134
void push_as(ForwardT &&...value)
Definition: BLI_stack.hh:222
Stack & operator=(const Stack &other)
Definition: BLI_stack.hh:200
Stack & operator=(Stack &&other)
Definition: BLI_stack.hh:205
bool is_empty() const
Definition: BLI_stack.hh:308
const T & const_reference
Definition: BLI_stack.hh:74
Stack(Stack &&other) noexcept(std::is_nothrow_move_constructible_v< T >)
Definition: BLI_stack.hh:162
Stack(const std::initializer_list< T > &values, Allocator allocator={})
Definition: BLI_stack.hh:148
void push(T &&value)
Definition: BLI_stack.hh:217
void push(const T &value)
Definition: BLI_stack.hh:213
const T * const_pointer
Definition: BLI_stack.hh:72
void push_multiple(Span< T > values)
Definition: BLI_stack.hh:281
const T & peek() const
Definition: BLI_stack.hh:269
int64_t size_type
Definition: BLI_stack.hh:75
int64_t size() const
Definition: BLI_stack.hh:316
Stack(const Stack &other)
Definition: BLI_stack.hh:153
ccl_global float * buffer
#define T
Container & move_assign_container(Container &dst, Container &&src) noexcept(std::is_nothrow_move_constructible_v< Container >)
Container & copy_assign_container(Container &dst, const Container &src)
constexpr int64_t default_inline_buffer_capacity(size_t element_size)
void uninitialized_copy_n(const T *src, int64_t n, T *dst)
#define min(a, b)
Definition: sort.c:35
_W64 unsigned int uintptr_t
Definition: stdint.h:119
__int64 int64_t
Definition: stdint.h:89
StackChunk * above
Definition: BLI_stack.hh:42
StackChunk * below
Definition: BLI_stack.hh:40
int64_t capacity() const
Definition: BLI_stack.hh:48
float max