These html pages are based on the PhD thesis "Cluster-Based Parallelization of Simulations on Dynamically Adaptive Grids and Dynamic Resource Management" by Martin Schreiber.
There is also more information and a PDF version available.

4.2 Stacks

We assume that the structure of a grid is stored on a stack. Then, we can traverse the grid by successively fetching the top-most element of this stack on each spacetree node.

Formally, a stack Sk is modified via push and pop functions, respectively, pushing data to the top of the stack or removing a data item from the top of the stack.

Given a stack Sk = (s1k,s2k,,s|Sk|k) with its stack elements sik, a push of element α can be formalized via

push : (Sk,α ) ↦→ (sk,sk,...,sk ,α)
                  1 2      |Sk|

and pop by returning a tuple with the stack and the fetched data, yielding

pop : (Sk ) ↦→ ((sk,sk,...,sk   ),sk  ).
               1  2      |Sk|- 1  |Sk|

Regarding the implementation of such a stack access, the push and pop operations are offered with different implementations: Pushing and fetching of single or multiple stack elements. The topmost element is referenced via a pointer. Stack size modifications can, thus, be achieved by increments and decrements on this pointer only. Due to the small number of operations related to stack access, all methods are marked to be inlined by the compiler, thus no function call is involved for the execution of a push or pop operation. The stack is preallocated with the maximum capacity of possible elements being stored on the stack during a traversal (see Section 4.10.6).

The bit stream for a forward spacetree traversal used so far is not directly applicable for a backward traversal. Using our stack structure as the input stream only and following the input/output scheme suggested in [GMPZ06,Nec09,Wei09], this demands for creating a structure stack usable for backward traversals.

For generation of the backward structure stack, we use post-order push operations of the structure markers to a stack. The spacetree traversal is then based on bits fetched from Sforwardstructure and setting up a backward structure stack Sbackwardstructure by pushing the structure bits in postfix order, after the children have been visited. This creates a structure stack with its input usable for traversals in reversed direction.