Chapter 16 The Stack Family: stack / fixed / block and the Pointer Variant

Chapter Orientation

The stack is computer science's smallest container, yet XRT gives it four variants — because the "stack" need looks different under different constraints. Conclusion first: the dynamic stack xstack for the vast majority of scenarios; switch to the fixed stack when "depth known + hot path"; the block stack when element addresses must stay stable long-term; the pointer variant for holding object references. This chapter's task is making that selection a derivable judgment. The dynamic stack xstack pushes as much as you like; the fixed stack xfixedstack binds to a caller buffer with zero allocation throughout; the block stack xblockstack keeps existing element addresses unchanged while growing; the pointer variant holds ptr. Two complete examples explain the two engineering constraints "zero allocation" and "stable address", a decision table settles the four-way choice, and the mechanical recipe of "recursion into an explicit stack" is tabulated — it is the foundation move of safe parsers. Recursive-descent parsing and backtracking traversal run through the examples as the application scenario — they are also the main data structures of Chapter 31's parser and the latter half of Volume 3. Read this chapter carrying one concrete question: "if the input nests ten thousand deep, what happens to my stack?" — every variant answers differently, and that is the whole of selection.

16.1引入

A recursive-descent parser must save the "current scan position" at every recursion level — this scenario reappears in Chapter 31's JSON parser, where you will see how the real frame structure corresponds to the simulation here. Local variables on the call stack? Recursion depth is decided by the input (the nesting depth of Chapter 3's resource limits), and stack overflow is then an attack surface. A hand-written loop instead of recursion? Then you need an explicit frame stack. How to choose the frame stack's constraints: a parser frame is a few dozen bytes, the maximum depth bounded by resource limits (say 128) — depth known, hot path: the fixed stack bound to a stack array, zero heap allocation throughout. And when traversing a tree the user mutates at will, must the node addresses held mid-traversal not go stale on stack growth? — no: stack growth invalidates the addresses of the stack's own elements, not the tree nodes'; but if the stack holds "pointers into an in-stack work area", the block stack's stable addresses become a hard requirement.

Two scenarios, two answers — exactly why the family exists: constraints drive selection, not one universal stack conquering all. Unfolding "recursion into an explicit stack" one step further: any recursive algorithm can be mechanically rewritten as "loop + explicit stack" — the "function-call level" becomes "push", "return" becomes "pop". After the rewrite, the depth cap moves from the system call stack (uncontrolled) to your stack capacity (explicit and controllable) — precisely why Chapter 3's resource limits can land: the parser declares "max depth 128", the frame stack is provisioned for 128, and over-deep input is refused at level 128 instead of eating through the process stack.

16.2概念

The four variants in one table

The life of a frame stack

Using a parser's frame stack, put the four variants into the same workflow:

The zero-allocation contract

The fixed stack's Init binds the handle to a caller-provided buffer (a local array, static storage, or an arena block all work), after which Push/Pop operate entirely on that memory — never allocating; the repository's _noalloc contract tests guarantee it (a sibling of Chapter 6's fault injection: one proves "failure paths correct", the other "the zero-allocation path truly exists"). Full-stack Push fails and empty-stack Pop fails — both boundaries carry clear errors, no overrun, no crash.

Stable addresses: the block stack

The dynamic stack relocates wholesale on growth, invalidating all element pointers. When does that become a problem? When "stack elements are referenced from outside the stack" — the most typical form being "the stack is the work area": each pushed work frame is back-referenced by deeper frames (a tree's parent pointers, a parser's upstream context), and relocation dangles all those back-references at once. The block stack splits storage into a block chain; growth hangs a new block while old blocks stay put, cancellation of relocation at the root. The block stack xblockstack splits storage into a block chain — growth hangs a new block and old blocks stay put — element addresses taken from the stack remain valid for the stack's whole lifetime. "The stack also holds pointers to stack elements" sounds rare, but in the "stack as work area" pattern (each recursion level's work frame referenced by deeper levels) it is a real requirement. The price: traversal crosses blocks, constants slightly higher.

LIFO semantics and error hygiene

Popping an empty stack returns false and leaves a record in the thread error slot — the example's xrtClearError after the loop clears this "expected failure". It is Chapter 4's "success doesn't clear the slot" discipline in daily use: control the loop with return values, diagnose with the error slot, and actively clear the residual error once the boundary is reached — never let it leak into the next stretch of logic.

16.3示例

Complete program: a zero-allocation work stack

From the repository example examples/containers/fixed_stack/main.c, simulating a parser's frame stack:

 */

#include <stdio.h>

#include <xrt.h>



/* 模拟解析器的调用帧：函数编号 + 扫描位置。 */
typedef struct exampleframe {
	int Function;
	int Position;
} exampleframe;



int main(void)
{
	xfixedstack tFrames;
	exampleframe pStorage[8];      /* 栈的物理存储：本地数组 */
	exampleframe pInput[] = {
		{ 1, 10 },
		{ 2, 20 },
		{ 3, 30 }
	};
	exampleframe tFrame;

	


	 */
	if ( !xrtFixedStackInit(&tFrames, pStorage, sizeof(pStorage), sizeof(exampleframe)) ) {
		return 1;
	}

	/* 依次压入 3 帧（容量 8，远未触顶）。 */
	for ( size_t i = 0; i < 3; i++ ) {
		if ( !xrtFixedStackPush(&tFrames, &pInput[i]) ) {
			return 2;
		}
	}

	/* LIFO 弹出；栈空时结束并清掉"空栈"错误记录。 */
	while ( xrtFixedStackPop(&tFrames, &tFrame) ) {
		printf("function=%d position=%d\n", tFrame.Function, tFrame.Position);
	}
	xrtClearError();
	xrtFixedStackUnit(&tFrames);
	return 0;
}

What just happened. (1) pStorage[8] is the stack's physical storage — an ordinary local array; xrtFixedStackInit's parameters are "handle, buffer, capacity in bytes, element size". (2) After pushing three frames and popping them, the output is the 3/2/1 LIFO order — last-in-first-out is the stack's entire semantics and the easiest to "casually" break (if you want queue order while using a stack, you want Chapter 21's queue). (3) When emptied, Pop returns false ending the loop, and xrtClearError clears the empty-stack record — see "error hygiene" above. (4) Capacity 8, three pushed — pushing a ninth would fail rather than overrun: the cap is the capacity's defense line; with Chapter 3's resource limits, specs like "parse depth ≤ 128" gain a physical carrier. Quick accounting: 128 frames × 16 bytes = 2 KB — one stack array holds the whole working state, without even an arena (Chapter 7); that is what "zero allocation" looks like on the memory ledger.

Complete program: the block stack's stable addresses

From examples/containers/block_stack/main.c, verifying that element addresses don't change during growth — the machine's testimony for the "never invalid" promise:

 */

#include <stdio.h>

#include <xrt.h>



int main(void)
{
	xblockstack tFrames;
	int* pRoot;

	


	 */
	if ( !xrtBlockStackInitLayout(&tFrames, sizeof(int), sizeof(int), 4) ) {
		return 1;
	}

	



	 */
	pRoot = (int*)xrtBlockStackAdd(&tFrames);
	if ( pRoot == NULL ) {
		xrtBlockStackUnit(&tFrames);
		return 2;
	}
	*pRoot = 100;

	/* 连续压 20 个元素，触发多次跨块增长（4 块 → 6 块）。 */
	for ( int i = 1; i <= 20; i++ ) {
		if ( !xrtBlockStackPush(&tFrames, &i) ) {
			xrtBlockStackUnit(&tFrames);
			return 3;
		}
	}

	




	 */
	printf(
		"count=%zu blocks=%zu root=%d stable=%s\n",
		tFrames.Count,
		tFrames.Blocks.Count,
		*pRoot,
		xrtBlockStackGet(&tFrames, 0) == pRoot ? "yes" : "no"
	);

	xrtBlockStackUnit(&tFrames);
	return 0;
}

What just happened. (1) Twenty-one elements pushed (including a root value of 100), storage automatically splitting into 6 blocks — zero relocation across growth. (2) The program noted an element's address mid-push and read it back after all pushes to verify the content remains reachable: stable=yes is the empirical proof of "element addresses never invalid". (3) The control experiment deserves a hands-on run: the same sequence on the dynamic stack and the addresses changed worlds long ago. When is this property worth money? When stack elements are referenced from structures outside — say tree algorithms whose traversal work frames are referenced by parent frames.

The stack-versus-recursion correspondence table

Rewriting a recursive function into an explicit stack has a fixed recipe: the function's "per-level local state" becomes a pushed frame structure (the element type); "the recursive call" becomes "push + continue"; "return to the parent" becomes "pop"; "the entry parameters" become "the initial frame". Side by side: local variable table → frame structure fields, call-stack depth → the stack's Count, stack-overflow risk → the capacity cap (explicit, configurable, refusable). This table is used directly in Chapter 31's parser and Volume 3's AVL traversals — recursion into an explicit stack is not an exercise but the safety baseline for parsers handling untrusted input.

16.4契约

• Lifecycle pairing: Init/Unit paired; the fixed stack's Unit does not free the caller buffer (it never owned it).
• Zero allocation: once bound, the fixed stack's Push/Pop never allocate; full-stack and empty-stack failures both carry clear errors.
• Address validity: the dynamic stack invalidates on growth; the fixed is stable while bound; the block never invalidates — at selection time first ask "will stack elements be referenced from outside".
• Error hygiene: control flow by return values; clear residual boundary errors when done (xrtClearError).
• Pointer variant: the pointer stack manages only pointer slots; element ownership and freeing lie entirely with the caller.

Common Mistakes

This chapter's two pitfalls: one about address validity (same root as Chapter 14's array Pitfall 1 — the fate of contiguous storage), one about capacity detached from spec. The former is a technical pit; the latter an engineering pit — engineering pits are usually more expensive.

exampleframe* pTop = (exampleframe*)xrtStackPeek(&tFrames, 0);
xrtStackPush(&tFrames, &tNext);      /* growth relocates */
pTop->Position = 42;                  /* dangles */

xrtStackPush(&tFrames, &tNext);      /* push first */
exampleframe* pTop = (exampleframe*)xrtStackPeek(&tFrames, 0);
/* need long-term stable addresses: switch to xblockstack or xfixedstack */

exampleframe pStorage[4];            /* test cases nest 3 deep — explodes on day one */
xrtFixedStackInit(&tFrames, pStorage, sizeof(pStorage), sizeof(exampleframe));

exampleframe pStorage[128];          /* aligned with the resource limit's iMaxDepth */
xrtFixedStackInit(&tFrames, pStorage, sizeof(pStorage), sizeof(exampleframe));
/* before parsing, check input depth <= 128 (one of the three resource gates); over-limit refuses whole */

Programming Exercises

Summary