Глава 17 Двусвязные списки и slot_map

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

Глава ставит рядом два «контринтуитивных, но предельно ходовых» контейнера и завершает кратким наброском их комбинации. После неё ваш ящик инструментов «позиции и идентификаторы» полон: индексы массива, узлы списка, дескрипторы с поколением — каждый на своём месте. Интрузивный двусвязный список xlist встраивает узел внутрь объекта-носителя — подвешивание без выделений, один объект на нескольких цепях, снятие с цепи не уничтожает объект; поддержание порядка LRU за O(1) — его учебниковое применение. slot_map xslotmap решает классическую ловушку «дескриптор-индекс»: после переиспользования слота старый дескриптор ошибочно попадает в новый объект — счётчик поколений автоматически инвалидирует устаревший дескриптор. Оба контейнера отвечают на один вопрос: когда «позицию» объекта меняет система, как внешней ссылке остаться правильной — ответ списка «узел — часть объекта», ответ slot_map «дескриптор несёт номер версии».

17.1引入

Два места крушения. Первое: кэш LRU собран как «массив + пересортировка на каждое попадание» — кэш подрос, и сортировка стала узким местом пропускной способности; переход на список вскрыл, что каждое перемещение узла выделяет новый и освобождает старый — аллокатор стал занятее сортировки. Интрузивный список решает одним движением: узел — поле объекта, перемещение лишь перецепляет два указателя, O(1) и ноль выделений. Второе: таблица соединений раздаёт индексы массива бизнес-слой как дескрипторы; соединение 1 закрылось, новое соединение заняло слот 1, бизнес-слой работает со старым дескриптором и попадает в чужое соединение — перекрёст данных и превышение прав растут именно отсюда. Дескрипторы с поколением slot_map автоматически инвалидируют старый дескриптор после переиспользования слота; ошибочное попадание отвергается на уровне контейнера.

Техническая суть обоих мест одна: идентификатор обязан нести достаточно информации для борьбы с «переиспользованием позиции». Список уходит от позиции «встроенной идентичностью», slot_map версионирует позицию «индекс + поколение».

Стоит проговорить: ни один из контейнеров не управляет памятью объектов за вас — интрузивный список ничего не выделяет и не освобождает, slot_map хранит лишь ptr. Они поставщики «структуры и порядка», а не «владения»; владение всегда принадлежит режиму главы 5. Это разделение обязанностей позволяет без опаски ставить их поверх любой стратегии памяти (куча, пул, арена) — и означает, что дисциплина пути уничтожения целиком на вызывающем; ловушка 1 главы — место исполнения этой дисциплины.

17.2概念

Интрузивность: узел живёт в объекте

В отличие от традиционного списка, где «контейнер владеет узлами и хранит указатели на элементы», интрузивный стиль переворачивает отношение владения: контейнер не владеет объектами; объекты несут собственные крючки. Цена — структуре надо зарезервировать поле «на случай, если когда-нибудь повисну на цепи»; выигрыш — бесплатное подвешивание, принадлежность одного объекта нескольким группам сразу и снятие, не затрагивающее жизненный цикл объекта.

LRU: MoveFront и есть повышение при попадании

Голова — самый свежий, хвост — самый давний. При попадании xrtListMoveFront переносит узел в голову за O(1) — меняются только два двунаправленных указателя, независимо от длины цепи. Вытеснение «самого давнего» — взятие хвоста. В паре с map главы 20, ведающим «ключ → узел», полный LRU — эти два контейнера плюс один MoveFront.

Дескрипторы с поколением: индекс + версия

Сперва растолкуем «зачем версия»: 32-битный индекс сам по себе — совершенный идентификатор позиции — одношаговая локация, доступ O(1); его единственный изъян — он не несёт истории: после переиспользования слота старый и новый индексы неразличимы. Добавка 32-битного поколения закрывает пазл: позиция отвечает «где», поколение — «который по счёту». Дескриптор xslotmap (xslot) — упаковка в 64 бита: поколение << 32 | индекс. Каждое переиспользование слота инкрементирует поколение. Contains проверяет индекс и поколение вместе — старый дескриптор (поколение отстаёт) признаётся недействительным, даже если его индекс указывает на слот, где сейчас живёт новый объект. Remove валидирует так же; несовпадение поколения отказывает удалению. Это стандартный фундамент «таблиц соединений, пулов ресурсов, управления сущностями ECS»: внешний мир держит дескрипторы, контейнер гарантирует семантическую точность дескриптора.

Когда списком не пользуются

O(1) вставки-удаления списка имеет предпосылку: вы уже держите тот узел. Поиск по индексу или по значению — всё ещё O(n) — сам акт «найти элемент в списке» съедает преимущество O(1) целиком. Три контрправила: нужна случайная адресация → массив (глава 14); нужен поиск по ключу → map (глава 18); нужен упорядоченный обход → сортированный массив или AVL (глава 20). Незаменимые сценарии списка сужаются до: поддержания порядка (LRU, очереди планирования, свободные списки) и «объект известен — нужно лишь сменить групповую принадлежность». Правило-пароль: сначала спросите «как я получаю узел», потом «часты ли вставки-удаления» — где у первого нет ответа O(1), список вам не поможет.

Обход и портрет сложности

Обход списка идёт от головы к хвосту узел за узлом (First/Next); вставка и удаление O(1); но нет случайного доступа по индексу — поиск узла по индексу O(n). slot_map наоборот: дескриптор и есть индекс, доступ O(1), но обход должен перепрыгивать пустые слоты. Сила одного — слабость другого, и совместное применение (slot_map хранит объекты + список держит порядок) — классическая архитектура менеджера ресурсов; таблица соединений главы 67 — та же комбинация в масштабе: локация по дескриптору O(1), поддержание порядка событий O(1), ясная принадлежность жизненного цикла.

17.3示例

Первая полная программа: поддержание порядка LRU за O(1)

Из репозиторного образца examples/containers/list/main.c:

 */

#include <stdio.h>

#include <xrt.h>



/* 缓存条目：Recent 内嵌节点让它可以直接挂进 LRU 链。 */
typedef struct cacheitem {
	int Key;
	int Value;
	xlistnode Recent;
} cacheitem;



/* 打印从最近到最久未使用的缓存条目。 */
static void printCache(const xlist* pCache)
{
	for ( xlistnode* pNode = xrtListFirst(pCache);
		  pNode != NULL;
		  pNode = xrtListNext(pNode) ) {
		/* 由节点地址减去字段偏移，反查宿主 cacheitem 地址。 */
		cacheitem* pItem = XRT_CONTAINER_OF(pNode, cacheitem, Recent);

		printf("%d=%d ", pItem->Key, pItem->Value);
	}
	printf("\n");
}



int main(void)
{
	xlist Cache = XRT_LIST_INIT;    /* 空链表，无分配 */
	cacheitem Items[] = {
		{ 1, 100, XRT_LIST_NODE_INIT },
		{ 2, 200, XRT_LIST_NODE_INIT },
		{ 3, 300, XRT_LIST_NODE_INIT }
	};

	/* 依次压到链头：最终顺序 3(最新) 2 1(最旧)。 */
	for ( size_t i = 0; i < 3u; i++ ) {
		if ( !xrtListPushFront(&Cache, &Items[i].Recent) ) {
			return 1;
		}
	}
	printCache(&Cache);

	


	 */
	if ( !xrtListMoveFront(&Cache, &Items[0].Recent) ) {
		return 2;
	}
	printCache(&Cache);

	/* 摘除全部节点；Items 是栈数组，无需也不应释放。 */
	if ( !xrtListClear(&Cache) ) {
		return 3;
	}
	return 0;
}

Что только что произошло. (1) Статическая инициализация XRT_LIST_INIT и XRT_LIST_NODE_INIT — список и узел стартуют с нулевой стоимостью, без вызовов инициализации времени исполнения. (2) Три записи последовательно PushFront: последний лежит в голове, вывод 3 2 1. (3) После обращения к записи 1 — MoveFront: вывод становится 1 3 2 — запись 1 перешла из старейших в новейшие, операция тронула только указатели. (4) XRT_CONTAINER_OF(pNode, cacheitem, Recent) — обратный поиск носителя из адреса узла; сопутствующая идиома интрузивности, смещение поля вычислено на этапе компиляции. (5) Clear снимает все узлы; Items — стековый массив, освобождать не нужно и не следует — снятие с цепи не уничтожает объекты.

Вторая полная программа: поколения против ложных попаданий

Из examples/containers/slot_map/main.c:

 */

#include <stdio.h>
#include <xrt.h>



/* 连接对象仅用于演示稳定代际句柄。 */
typedef struct connection {
	int ID;
} connection;



int main(void)
{
	xslotmap tConnections;
	connection tFirst = { 100 };
	connection tSecond = { 200 };
	connection tReplacement = { 300 };
	xslot First;
	xslot Second;
	xslot Replacement;

	if ( !xrtSlotMapInit(&tConnections) ) {
		return 1;
	}

	/* 插入两个连接：得到两个不同下标的句柄。 */
	First = xrtSlotMapInsert(&tConnections, &tFirst);
	Second = xrtSlotMapInsert(&tConnections, &tSecond);
	if ( (First == XRT_SLOT_INVALID) || (Second == XRT_SLOT_INVALID) ) {
		xrtSlotMapUnit(&tConnections);
		return 2;
	}

	/* 删除第一个连接：末参可回调被摘除的指针，这里传 NULL 不需要。 */
	if ( !xrtSlotMapRemove(&tConnections, First, NULL) ) {
		xrtSlotMapUnit(&tConnections);
		return 3;
	}

	




	 */
	Replacement = xrtSlotMapInsert(&tConnections, &tReplacement);
	if ( Replacement == XRT_SLOT_INVALID ) {
		xrtSlotMapUnit(&tConnections);
		return 4;
	}

	




	 */
	printf(
		"old=%llu replacement=%llu same-index=%s stale-valid=%s\n",
		(unsigned long long)First,
		(unsigned long long)Replacement,
		xrtSlotIndex(First) == xrtSlotIndex(Replacement) ? "yes" : "no",
		xrtSlotMapContains(&tConnections, First) ? "yes" : "no"
	);
	xrtSlotMapUnit(&tConnections);
	return 0;
}

Что только что произошло. (1) Два вставленных соединения дают два дескриптора, First = 0x1_00000001 (поколение 1, индекс 1). (2) После удаления First и вставки замены свободный слот 1 переиспользуется, новый дескриптор 0x2_00000001: индекс тот же, поколение уже выросло с 1 до 2 (same-index=yes). (3) Ключевое утверждение в конце: Contains старого дескриптора First возвращает no — он ни при каких условиях не укажет на замену. Сравните десятичные значения двух дескрипторов в выводе (4294967297 и 8589934593): разница — ровно 2 в 32-й степени, поколение перенесло разряд. Перепишите программу с «голыми индексами» и перезапустите — stale-valid станет yes: собственными глазами увидеть место крушения запоминается лучше, чем десять раз прочесть документацию. Перепись меняет лишь дескриптор на голый индекс и Contains на проверку границ — меньше десяти строк, и безопасный контейнер деградировал в место аварии; этот контрольный опыт — лучший материал для разбора на ревью «почему дескриптор нельзя разбирать».

Набросок комбинированной архитектуры

Индивидуальные слабости двух контейнеров (список не находит, slot_map без порядка) взаимно гасятся в комбинации — стоит приколотить типовую форму наброском: соединение прибыло → вставка в slot_map даёт дескриптор, одновременно узел PushFront в цепь активных; событие сработало → дескриптор локализует объект за O(1), после обработки MoveFront поднимает время; соединение закрылось → сперва снятие с цепи, затем Remove, дескриптор инвалидируется вместе с ним (поколение уже записано); внешняя сторона работает со старым дескриптором → контейнер отказывает, перекрёст невозможен. Четыре шага покрывают будни менеджера ресурсов; таблица соединений главы 67 масштабирует это в конкурентный движок, но скелет — строки в точности эти, ни больше ни меньше.

17.4契约

• Интрузивное владение: список никогда не владеет объектами; Clear/снятие не освобождает носителей; перед уничтожением объект обязан быть снят с цепи.
• Статическая инициализация: XRT_LIST_INIT / XRT_LIST_NODE_INIT без инициализации времени исполнения; есть и парные версии времени исполнения.
• Семантика поколений: переиспользование слота инкрементирует поколение; валидация дескриптора требует двойного совпадения «индекс + поколение»; XRT_SLOT_INVALID — недействительный сигнальное значение; разобрать дескриптор, оставив только индекс, — значит отказаться от защиты.
• Сложность доступа: список по индексу O(n), вставка/удаление O(1); slot_map по дескриптору O(1); комбинированная архитектура берёт лучшее от каждого.
• Потоки: ни тот ни другой не потокобезопасные контейнеры — межпотоковый доступ требует внешней синхронизации (правильные примитивы — том 6).

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

cacheitem* pItem = find_expired(&Cache);
xrtFree(pItem);                      /* узел всё ещё на Cache - цепь повисла */

cacheitem* pItem = find_expired(&Cache);
xrtListRemove(&Cache, &pItem->Recent);   /* сперва снять с цепи */
xrtFree(pItem);                           /* потом уничтожить */

size_t iIndex = First & 0xFFFFFFFFu;         /* оставить только 32-битный индекс */
connection* pConn = (connection*)xrtSlotMapGet(&tMap, iIndex);  /* индекс в роли дескриптора */

connection* pConn = (connection*)xrtSlotMapGet(&tMap, First);   /* дескриптор передаётся как есть */
if ( pConn == NULL ) {
	/* поколение не совпало: дескриптор устарел - трактуем как устаревшую ссылку */
}

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

Итоги