第 16 章 栈族：stack / fixed / block 与指针变体

本章导读

栈是计算机科学里最小的容器，XRT 却给了它四个变体——因为"栈"这个需求在不同约束下长得不一样。先把结论放最前：绝大多数场景用动态栈 xstack；确认"深度已知 + 热路径"换固定栈；需要元素地址长期稳定换分块栈；装对象引用用指针变体。本章的任务是让这个选型变成可推导的判断。动态栈 xstack 想压多少压多少；固定栈 xfixedstack 绑定调用方缓冲、全程零分配；分块栈 xblockstack 增长时已有元素地址不变；指针变体装 ptr。本章用两个完整示例讲"零分配"与"稳定地址"这两种工程约束，给出四选一的决策表，并把"递归改显式栈"的机械套路整理成对照表——它是安全解析器的地基动作。递归下降解析器与回溯遍历是贯穿示例的应用场景——它们也是第 31 章解析器与卷三后半的主力数据结构。读本章时不妨带着一个具体问题："如果输入嵌套一万层，我的栈会发生什么？"——每个变体的答案不同，而这正是选型的全部内容。

16.1引入

一个递归下降解析器要在每层递归里保存"当前扫描位置"——这个场景在第 31 章 JSON 解析器里会再次出现，届时你会看到真实的帧结构与这里的模拟版如何对应。用调用栈的局部变量？递归深度由输入决定（第 3 章资源边界里的嵌套深度），栈溢出就是攻击面。用手写循环代替递归？那就要一个显式的帧栈。帧栈的约束怎么选：解析一帧几十字节、最大深度由资源边界限制（比如 128 层）——深度已知、热路径，固定栈绑定一块栈上数组，全程零堆分配。而遍历一棵用户随时增删的树时，遍历途中持有的节点地址不能因为栈扩容而失效？——不，栈扩容失效的是栈自己元素的地址，不是树节点的；但如果栈里存的是"指向栈内工作区的指针"，分块栈的稳定地址就成了硬需求。

两个场景两种答案，这正是栈族存在的意义：约束驱动选型，而不是一个万能栈包打天下。把"递归改显式栈"再展开一步：任何递归算法都可以机械地改写成"循环 + 显式栈"——把"函数调用层"换成"压栈"、把"return"换成"弹栈"。改写后深度上限从系统调用栈（不可控）变成你的栈容量（显式可控），这正是第 3 章资源边界能落地的原因：解析器声明"最大深度 128"，帧栈容量按 128 预备，超深输入在第 128 层被拒绝而不是把进程栈吃穿。

16.2概念

四个变体一张表

一个帧栈的一生

以解析器的帧栈为例，把四个变体放进同一个工作流里看清楚：

零分配契约

固定栈的 Init 把句柄绑定到调用方提供的缓冲（本地数组、静态存储、arena 里的一块都行），之后 Push/Pop 全部在这块内存上进行——永不分配，仓库的 _noalloc 契约测试保证这一点（第 6 章故障注入体系的姐妹篇：一个证明"失败路径正确"，一个证明"零分配路径真实存在"）。满栈 Push 失败、空栈 Pop 失败——两个边界都有明确错误，不越界不崩。

稳定地址：分块栈

动态栈扩容要整体搬迁，元素指针全部失效。什么时候这成为问题？当"栈元素被栈外引用"时——最典型的形态是"栈即工作区"：每层压入的工作帧被更深层的帧回指（树的父指针、解析器的上游上下文），搬迁会让这些回指集体悬空。分块栈把存储拆成块链，增长时挂新块、旧块原地不动，从根上取消搬迁这个动作。分块栈 xblockstack 把存储拆成块链，增长时挂新块、旧块原地不动——从栈里拿到的元素地址在栈的整个生命周期都有效。"栈里还要存指向栈元素的指针"听起来少见，但在"栈即工作区"的模式里（每层递归的工作帧被更深的层引用）是真实需求。代价：遍历跨块、常数略高。

LIFO 语义与错误配对

Pop 空栈返回 false 并在线程错误槽留下记录——示例里循环结束后 xrtClearError 把这条"预期中的失败"清掉。这是第 4 章"成功不清槽"纪律的日常应用：用返回值控制循环，用错误槽做诊断，边界到达后的残留错误主动清掉，不要让它泄漏到下一段逻辑。

16.3示例

完整程序：零分配工作栈

来自仓库范例 examples/containers/fixed_stack/main.c，模拟解析器的帧栈：

 */

#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;
}

刚才发生了什么。 ① pStorage[8] 是栈的物理存储——一块普通本地数组；xrtFixedStackInit 的参数是"句柄、缓冲、容量字节数、元素大小"。② 压三帧后弹出，输出 3/2/1 的 LIFO 顺序——后进先出是栈的全部语义，也是最容易被"顺手"破坏的语义（用栈时想要队列的顺序，说明你该用第 21 章的队列）。③ 弹空时 Pop 返回 false 结束循环，xrtClearError 清掉空栈记录——见上文"错误配对"。④ 容量 8、压 3——如果压第 9 个，Push 失败而不是越界：上限是容量给的防线，配合第 3 章资源边界，"解析深度 ≤ 128"这类规格就有了物理承载。顺带算一笔账：128 帧 × 16 字节 = 2KB——一块栈上数组就装下了全部工作状态，连 arena（第 7 章）都用不上，这就是"零分配"三个字在内存账本上的样子。

完整程序：分块栈的稳定地址

来自 examples/containers/block_stack/main.c，验证增长过程中元素地址不变——这是"永不失效"承诺的机器证言：

 */

#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;
}

刚才发生了什么。 ① 压入 21 个元素（含一个根值 100），存储自动裂成 6 块——增长过程零搬迁。② 程序在压栈途中记下了某元素的地址，全部压完后回读验证内容仍可访问：stable=yes 就是"元素地址永不失效"的实证。③ 对照实验值得亲手做一遍：同样的序列换成动态栈，地址早就换了世界。什么时候这个性质值钱？栈元素被栈外的结构引用时——比如遍历工作帧被父帧引用的树算法。

栈与递归的对照表

把递归函数改写为显式栈时，参数怎么搬有固定套路：函数的"每层局部状态"压成一个帧结构（元素类型）；"递归调用"变成"压栈 + continue"；"返回上层"变成"弹栈"；"入口参数"变成"初始帧"。对照着看：局部变量表 → 帧结构字段，调用栈深度 → 栈的 Count，栈溢出风险 → 容量上限（显式、可配、可拒绝）。这张对照表在第 31 章解析器与卷三 AVL 遍历里都会被直接使用——递归转显式栈不是练习题，是解析器处理不受信任输入的安全底线。

16.4契约

• 配对：Init/Unit 配对；固定栈 Unit 不释放调用方缓冲（它从未拥有过）。
• 零分配：固定栈绑定后 Push/Pop 永不分配；满栈失败、空栈失败，均有明确错误。
• 地址时效：动态栈扩容失效；固定栈绑定期间稳定；分块栈永不失效——选型时先问"栈元素会不会被栈外引用"。
• 错误配对：以返回值控制流程；边界残留错误用完清掉（xrtClearError）。
• 指针变体：指针栈只管指针槽；元素归属与释放完全在调用方。

常见错误

本章的两个坑，一个关于地址时效（与第 14 章数组坑 1 同根同源——连续存储的宿命），一个关于容量与规格的脱节。前者是技术坑，后者是工程坑——工程坑往往更贵。

exampleframe* pTop = (exampleframe*)xrtStackPeek(&tFrames, 0);
xrtStackPush(&tFrames, &tNext);      /* 扩容搬迁 */
pTop->Position = 42;                  /* 悬空 */

xrtStackPush(&tFrames, &tNext);      /* 先压 */
exampleframe* pTop = (exampleframe*)xrtStackPeek(&tFrames, 0);
/* 需要地址长期稳定：换 xblockstack 或 xfixedstack */

exampleframe pStorage[4];            /* 测试用例最深 3 层——上线第一天就爆 */
xrtFixedStackInit(&tFrames, pStorage, sizeof(pStorage), sizeof(exampleframe));

exampleframe pStorage[128];          /* 与资源边界的 iMaxDepth 对齐 */
xrtFixedStackInit(&tFrames, pStorage, sizeof(pStorage), sizeof(exampleframe));
/* 解析前先检查输入深度 ≤ 128（资源边界三闸之一），超限整体拒绝 */

编程练习

小结