Blender  V3.3
Classes | Namespaces | Typedefs
BLI_stack.hh File Reference
#include "BLI_allocator.hh"
#include "BLI_memory_utils.hh"
#include "BLI_span.hh"

Go to the source code of this file.

Classes

struct  blender::StackChunk< T >
 
class  blender::Stack< T, InlineBufferCapacity, Allocator >
 

Namespaces

 blender
 

Typedefs

template<typename T , int64_t InlineBufferCapacity = default_inline_buffer_capacity(sizeof(T))>
using blender::RawStack = Stack< T, InlineBufferCapacity, RawAllocator >
 

Detailed Description

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.

Definition in file BLI_stack.hh.