第 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 章的体系。这种职责切分让它们可以无顾虑地嵌进任何内存策略（堆、池、arena）之上，也意味着销毁路径的纪律完全在调用方——本章坑 1 就是这条纪律的执法现场。

17.2概念

侵入式：节点住在对象里

与传统"容器拥有节点、存元素指针"的链表对比，侵入式把所有权关系倒转了：容器不拥有对象，对象自己带着挂钩。代价是对象结构要为"将来可能挂链"预留字段；收益是挂接零成本、对象同时属于多个分组、摘链不碰对象生命周期。

LRU：MoveFront 就是命中提升

链头 = 最近使用，链尾 = 最久未用。命中时 xrtListMoveFront 把节点 O(1) 移到链头——只调整两个方向的指针，与链长无关。淘汰"最久未用"即取链尾。配上第 20 章的 map 做"键 → 节点"定位，完整的 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示例

完整程序：O(1) LRU 顺序维护

来自仓库范例 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;
}

刚才发生了什么。 ① XRT_LIST_INIT 与 XRT_LIST_NODE_INIT 静态初始化——链表与节点都能零成本起步，无运行时初始化调用。② 三个条目依次 PushFront：后压的在链头，输出 3 2 1。③ 访问条目 1 后 MoveFront：输出变 1 3 2——条目 1 从最旧变最新，操作只改了指针。④ XRT_CONTAINER_OF(pNode, cacheitem, Recent) 由节点地址反查宿主——这是侵入式的配套惯用法，字段偏移在编译期算好。⑤ 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;
}

刚才发生了什么。 ① 两个连接插入得到两个句柄，First = 0x1_00000001（代际 1、下标 1）。② 删除 First 后插入替补——空闲槽 1 被复用，新句柄 0x2_00000001：下标相同、代际已从 1 递增到 2（same-index=yes）。③ 关键断言在最后：旧句柄 First 的 Contains 返回 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 无运行时初始化；同样有配对的运行时版本。
• 代际语义：槽复用代际 +1；句柄校验"下标 + 代际"双匹配；XRT_SLOT_INVALID 为无效哨兵；拆开句柄只取下标等于放弃保护。
• 访问复杂度：链表按下标 O(n)、插删 O(1)；slot_map 按句柄 O(1)；组合架构各取所长。
• 线程：两者都不是线程安全容器——跨线程访问需要外部同步（卷六讲正确的同步原语）。

常见错误

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 ) {
	/* 代际不符：这个句柄已过期，按陈旧引用处理 */
}

编程练习

小结