Глава 16 Семейство стеков: stack / fixed / block и указательные варианты

Ориентация главы

Стек — мельчайший контейнер информатики, но XRT даёт ему четыре варианта — потому что потребность «стек» в разных ограничениях выглядит по-разному. Вывод вперёд: в подавляющем большинстве сцен берите динамический стек xstack; подтверждены «глубина известна + горячий путь» — фиксированный стек; нужна долгосрочная стабильность адресов элементов — блочный; храните ссылки на объекты — указательная разновидность. Задача главы — сделать этот выбор выводимым. Динамический стек xstack давит сколько угодно; фиксированный стек xfixedstack привязывается к буферу вызывающего с нулевым выделением на всём пути; блочный стек xblockstack при росте не меняет адреса уже размещённых элементов; указательная разновидность хранит ptr. Двумя полными программами глава разбирает два инженерных ограничения — «нулевое выделение» и «стабильный адрес», даёт таблицу выбора из четырёх и сводит механический приём «рекурсия → явный стек» в таблицу соответствий — это базовое движение безопасного парсера. Рекурсивно-нисходящие парсеры и обходы с возвратом — сквозной прикладной сценарий главы — они же главная структура данных главы 31 и второй половины тома 3. Читая, держите в голове конкретный вопрос: «что случится с моим стеком, если ввод вложится на десять тысяч уровней?» — у каждого варианта свой ответ, и в этом весь выбор.

16.1引入

Рекурсивно-нисходящему парсеру нужно сохранять на каждом уровне рекурсии «текущую позицию сканирования» — этот сценарий снова возникнет в парсере JSON главы 31, где вы увидите, как реальные кадры соответствуют здешней имитации. Локальная переменная на стеке вызовов? Глубина рекурсии определяется вводом (глубина вложенности из границ ресурсов главы 3), переполнение стека — поверхность атаки. Заменить рекурсию рукописным циклом? Тогда нужен явный стек кадров. Как выбрать его ограничения: кадр разбора в десятки байтов, максимальная глубина ограничена границей ресурсов (скажем 128) — глубина известна, путь горячий: фиксированный стек на стековом массиве, нулевое кучное выделение на всём пути. А при обходе дерева, которое пользователь в любой момент меняет, не должны ли адреса узлов, удерживаемые в пути, инвалидироваться ростом стека? Нет — рост инвалидирует адреса собственных элементов стека, не узлов дерева; но если в стеке лежат «указатели на рабочие зоны внутри стека», стабильные адреса блочного стека становятся жёсткой потребностью.

Две сцены — два ответа: в этом смысл существования семейства — ограничение ведёт выбор, а не один универсальный стек на все случаи. Развернём «рекурсию в явный стек» ещё на шаг: любой рекурсивный алгоритм механически переписывается в «цикл + явный стек» — «уровень вызова функции» становится «push», «return» становится «pop». После переписывания потолок глубины переходит из системного стека вызовов (неуправляем) в ёмкость вашего стека (явно управляемая) — именно поэтому границы ресурсов главы 3 вообще осуществимы: парсер заявляет «максимальная глубина 128», ёмкость стека кадров готовится по 128, и сверхглубокий ввод получает отмену на 128-м уровне (отвергается), а не прорезает стек процесса.

16.2概念

Четыре варианта в одной таблице

Жизнь одного стека кадров

На примере стека кадров парсера все четыре варианта в одном рабочем потоке:

Контракт нулевого выделения

Init фиксированного стека привязывает дескриптор к буферу вызывающего (локальный массив, статическая память, кусок арены — что угодно), после чего 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;
}

Что только что произошло. (1) pStorage[8] — физическое хранилище стека, обычный локальный массив; параметры xrtFixedStackInit — «дескриптор, буфер, ёмкость в байтах, размер элемента». (2) После трёх кадров и выборки вывод идёт в порядке LIFO 3/2/1 — «последним пришёл, первым ушёл» — вся семантика стека и самая «запросто» ломаемая (если при работе со стеком вам нужен порядок очереди — вам нужна очередь главы 21). (3) При пустом стеке Pop возвращает false и завершает цикл, xrtClearError стирает запись о пустоте — см. «парирование ошибок» выше. (4) Ёмкость 8, положили 3 — девятый Push не удастся, а не выйдет за границу: потолок — линия обороны, данная ёмкостью; в связке с границами ресурсов главы 3 спецификации вида «глубина разбора ≤ 128» получают физического носителя. Заодно счёт: 128 кадров × 16 байт = 2 КБ — один стековый массив вмещает всё рабочее состояние, даже арена (глава 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;
}

Что только что произошло. (1) Вложено 21 элемент (включая корневое значение 100), хранилище само раскололось на 6 блоков — рост без переезда. (2) Програмна записала по пути адрес некоторого элемента, а после полной укладки перечитала и проверила доступность содержимого: stable=yes — эмпирическое доказательство «адреса элементов не инвалидируются никогда». (3) Контрольный опыт стоит проделать руками: та же последовательность на динамическом стеке — адрес давно сменил мир. Когда это свойство дорого? Когда элементы стека цитируются структурами вне стека — например, древесные алгоритмы, где рабочий кадр ссылается на родительский.

Таблица соответствий стека и рекурсии

При переписывании рекурсивной функции в явный стек перенос аргументов имеет фиксированный приём: «локальное состояние каждого уровня» функции ужимается в структуру кадра (тип элемента); «рекурсивный вызов» становится «push + continue»; «возврат на уровень выше» становится «pop»; «входные параметры» становятся «начальным кадром». Сопоставьте: таблица локальных переменных → поля кадра, глубина стека вызовов → Count стека, риск переполнения стека → потолок ёмкости (явный, настраиваемый, отказывающий). Эта таблица будет прямо использована в парсере главы 31 и в обходах AVL тома 3 — рекурсия в явный стек не упражнение, а линия безопасности парсера перед недоверенным вводом.

16.4契约

• Парность: Init/Unit в паре; Unit фиксированного стека не освобождает буфер вызывающего (он ему никогда не принадлежал).
• Нулевое выделение: после привязки фиксированный стек никогда не выделяет на Push/Pop; полный стек и пустой стек — обе границы с явными ошибками.
• Время жизни адресов: рост динамического инвалидирует; фиксированный стабилен на период привязки; блочный — никогда не инвалидирует; выбирая, сперва спросите «будут ли элементы стека цитироваться извне».
• Парирование ошибок: потоком правит возвращаемое значение; остаточную ошибку границы стираем по использовании (xrtClearError).
• Указательная разновидность: указательный стек ведает только слотами указателей; владение и освобождение элементов — целиком на вызывающем.

Типичные ошибки

Две ловушки главы: одна про время жизни адресов (одного корня с ловушкой 1 массивов главы 14 — судьба непрерывного хранения), другая про разрыв между ёмкостью и спецификацией. Первая — техническая, вторая — инженерная; инженерные ловушки обычно дороже.

exampleframe* pTop = (exampleframe*)xrtStackPeek(&tFrames, 0);
xrtStackPush(&tFrames, &tNext);      /* расширение с переездом */
pTop->Position = 42;                  /* висяк */

xrtStackPush(&tFrames, &tNext);      /* сперва push */
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 (один из трёх шлюзов границ), сверх - отвергнуть целиком */

Практические задания

Итоги