JINHU
Splay Tree 代码详细分析
整体架构概述
Splay Tree（伸展树）是一种自调整二叉搜索树，通过 Splay 操作将最近访问的节点移动到根部，利用访问局部性原理提高性能。
核心架构图
┌─────────────────────────────────────────────────────────┐
│ IMG_SPLAY_TREE 节点 │
├─────────────────────────────────────────────────────────┤
│ - uiFlags: 键值 (用于排序和查找) │
│ - psLeft: 左子树指针 │
│ - psRight: 右子树指针 │
│ - buckets[]: 存储桶数组 (FREE_TABLE_LIMIT个) │
│ - bHasEltsMapping: 位图 (快速定位非空桶) │
└─────────────────────────────────────────────────────────┘
典型树结构:
┌─────────┐
│ flags=5 │ <- 根节点
│ buckets │
└────┬────┘
│
┌────────────┴────────────┐
│ │
┌────▼────┐ ┌────▼────┐
│flags=3 │ │flags=8 │
│buckets │ │buckets │
└────┬────┘ └────┬────┘
│ │
┌────┴───┐ ┌────┴───┐
│ │ │ │
┌──▼──┐ ┌──▼──┐ ┌──▼──┐ ┌──▼──┐
│f=1 │ │f=4 │ │f=7 │ │f=9 │
└─────┘ └─────┘ └─────┘ └─────┘
特点:
- 每个节点包含一个 flags 值
- 每个节点包含多个 buckets (用于 RA)
- 满足二叉搜索树性质: 左 < 根 < 右
核心数据结构
IMG_SPLAY_TREE 结构
// 在 uniq_key_splay_tree.h 中定义
typedef struct _IMG_SPLAY_TREE {
IMG_PSPLAY_FLAGS_T uiFlags; // 键值
struct _IMG_SPLAY_TREE *psLeft; // 左子树
struct _IMG_SPLAY_TREE *psRight; // 右子树
// RA 特定字段
struct _BT_ *buckets[FREE_TABLE_LIMIT]; // 桶数组
#if defined(PVR_CTZLL)
IMG_ELTS_MAPPINGS bHasEltsMapping; // 位图：标记哪些桶非空
#endif
} IMG_SPLAY_TREE, *IMG_PSPLAY_TREE;
字段详解:
节点内存布局 (64位系统):
┌────────────────────────────────────────────────────┐
│ uiFlags (8 bytes) │
├────────────────────────────────────────────────────┤
│ psLeft (8 bytes) │
├────────────────────────────────────────────────────┤
│ psRight (8 bytes) │
├────────────────────────────────────────────────────┤
│ buckets[0] (8 bytes) │
│ buckets[1] (8 bytes) │
│ ... │
│ buckets[FREE_TABLE_LIMIT-1] (8 bytes) │
├────────────────────────────────────────────────────┤
│ bHasEltsMapping (8 bytes, 如果定义 PVR_CTZLL) │
└────────────────────────────────────────────────────┘
假设 FREE_TABLE_LIMIT = 64:
总大小 = 8 + 8 + 8 + 64*8 + 8 = 544 bytes
每个节点存储:
1. 一个 flags 值 (用于树的排序)
2. 64 个桶指针 (每个桶是一个 BT 链表)
3. 一个 64 位位图 (标记哪些桶有元素)
与 RA 的集成关系
RA_ARENA 结构:
┌────────────────────────────────────────┐
│ per_flags_buckets: IMG_PSPLAY_TREE* │ <- 指向 Splay Tree 根
└────────────────┬───────────────────────┘
│
▼
Splay Tree (按 flags 组织)
│
┌──────────┼──────────┐
│ │ │
flags=0 flags=1 flags=2
┌─────┐ ┌─────┐ ┌─────┐
│ │ │ │ │ │
└──┬──┘ └──┬──┘ └──┬──┘
│ │ │
buckets[0..63] buckets[0..63] buckets[0..63]
│ │ │
│ │ │
▼ ▼ ▼
BT链表 BT链表 BT链表
说明:
1. Splay Tree 的每个节点代表一种 flags 组合
2. 每个节点内部有 64 个桶 (按大小分类)
3. 每个桶是一个 BT 链表 (具体的空闲段)
Splay 操作详解
Splay 操作原理
核心思想: 将访问的节点通过旋转操作移动到根节点。
为什么要 Splay?
┌────────────────────────────────────────┐
│ 1. 访问局部性原理 │
│ - 最近访问的数据可能很快再次访问 │
│ - 将其放在根部，下次访问 O(1) │
│ │
│ 2. 自平衡 │
│ - 无需显式平衡操作 (vs 红黑树) │
│ - 均摊复杂度 O(log n) │
│ │
│ 3. 简单实现 │
│ - 只需要旋转操作 │
│ - 无需颜色标记或平衡因子 │
└────────────────────────────────────────┘
PVRSRVSplay 函数详解
IMG_INTERNAL
IMG_PSPLAY_TREE PVRSRVSplay(IMG_PSPLAY_FLAGS_T uiFlags, IMG_PSPLAY_TREE psTree)
{
IMG_SPLAY_TREE sTmp1; // 临时节点
IMG_PSPLAY_TREE psLeft; // 左树的根
IMG_PSPLAY_TREE psRight; // 右树的根
IMG_PSPLAY_TREE psTmp2;
if (psTree == NULL)
{
return NULL;
}
// 初始化临时节点
sTmp1.psLeft = NULL;
sTmp1.psRight = NULL;
psLeft = &sTmp1;
psRight = &sTmp1;
for (;;)
{
if (uiFlags < psTree->uiFlags)
{
// 目标在左子树
if (psTree->psLeft == NULL)
{
break;
}
if (uiFlags < psTree->psLeft->uiFlags)
{
// Zig-Zig 情况: 右旋转
psTmp2 = psTree->psLeft;
psTree->psLeft = psTmp2->psRight;
psTmp2->psRight = psTree;
psTree = psTmp2;
if (psTree->psLeft == NULL)
{
break;
}
}
// Link Right: 将当前节点链接到右树
psRight->psLeft = psTree;
psRight = psTree;
psTree = psTree->psLeft;
}
else if (uiFlags > psTree->uiFlags)
{
// 目标在右子树 (对称操作)
if (psTree->psRight == NULL)
{
break;
}
if (uiFlags > psTree->psRight->uiFlags)
{
// Zag-Zag 情况: 左旋转
psTmp2 = psTree->psRight;
psTree->psRight = psTmp2->psLeft;
psTmp2->psLeft = psTree;
psTree = psTmp2;
if (psTree->psRight == NULL)
{
break;
}
}
// Link Left: 将当前节点链接到左树
psLeft->psRight = psTree;
psLeft = psTree;
psTree = psTree->psRight;
}
else
{
// 找到目标节点
break;
}
}
// 重新组装树
psLeft->psRight = psTree->psLeft;
psRight->psLeft = psTree->psRight;
psTree->psLeft = sTmp1.psRight;
psTree->psRight = sTmp1.psLeft;
return psTree;
}
Splay 操作图解
场景1: Zig-Zig (目标在左-左)
初始树:
┌───┐
│ 7 │
└─┬─┘
│
┌───▼──┐
│ │
┌─▼─┐ │
│ 5 │ │
└─┬─┘ │
│ │
┌───▼──┐ │
│ │ │
┌─▼─┐ │ │
│ 3 │ │ │
└───┘ │ │
│ │
┌─▼─┐ │
│ 4 │ │
└───┘ │
┌─▼─┐
│ 6 │
└───┘
Splay(3) 第一步: Zig-Zig 右旋转
旋转 5 和 7:
┌───┐
│ 5 │
└─┬─┘
│
┌───┴───┐
│ │
┌─▼─┐ ┌─▼─┐
│ 3 │ │ 7 │
└───┘ └─┬─┘
│
┌───┴───┐
│ │
┌─▼─┐ ┌─▼─┐
│ 6 │ │...│
└───┘ └───┘
第二步: 再次右旋转
┌───┐
│ 3 │ <- 目标到根
└─┬─┘
│
└───┐
│
┌─▼─┐
│ 5 │
└─┬─┘
│
└───┐
│
┌─▼─┐
│ 7 │
└───┘
场景2: Zig-Zag (目标在左-右)
初始树:
┌───┐
│ 7 │
└─┬─┘
│
┌───▼──┐
│ │
┌─▼─┐ │
│ 3 │ │
└─┬─┘ │
│ │
└───┐ │
│ │
┌─▼─┐│
│ 5 ││
└─┬─┘│
│ │
┌───┴──┴───┐
│ │
┌─▼─┐ ┌─▼─┐
│ 4 │ │ 6 │
└───┘ └───┘
Splay(5) 过程:
步骤1: Link Right (7)
步骤2: Link Left (3)
┌───┐
│ 5 │ <- 目标到根
└─┬─┘
│
┌───┴───┐
│ │
┌─▼─┐ ┌─▼─┐
│ 3 │ │ 7 │
└─┬─┘ └─┬─┘
│ │
┌─▼─┐ ┌─▼─┐
│ 4 │ │ 6 │
└───┘ └───┘
Top-Down Splay 算法详解
算法状态维护:
在 Splay 过程中维护三棵树:
1. Left Tree (L): 收集比目标大的节点
2. Middle Tree (M): 当前正在处理的子树
3. Right Tree (R): 收集比目标小的节点
初始状态:
L = 空
M = 原树
R = 空
处理过程示意:
┌────────────────────────────────────────┐
│ L M R │
│ ┌─┐ ┌─┐ ┌─┐ │
│ │ │ │7│ │ │ │
│ └─┘ └┬┘ └─┘ │
│ │ │
│ ┌─┴─┐ │
│ │ │ │
│ ┌─▼┐ │ │
│ │5 │ │ │
│ └┬─┘ │ │
│ │ │ │
│ ┌─┴┐ │ │
│ │3 │ │ │
│ └──┘ │ │
└────────────────────────────────────────┘
Splay(3) 过程:
步骤1: 3 < 7, Link Right
┌────────────────────────────────────────┐
│ L M R │
│ ┌─┐ ┌─┐ ┌─┐ │
│ │ │ │5│ │7│ │
│ └─┘ └┬┘ └┬┘ │
│ │ └─ (链接到R) │
│ ┌─┴─┐ │
│ │ │ │
│ ┌─▼┐ │ │
│ │3 │ │ │
│ └──┘ │ │
└────────────────────────────────────────┘
步骤2: 3 < 5, Link Right
┌────────────────────────────────────────┐
│ L M R │
│ ┌─┐ ┌─┐ ┌─┐ │
│ │ │ │3│ │5│ │
│ └─┘ └─┘ └┬┘ │
│ │ │
│ ┌─▼┐ │
│ │7 │ │
│ └──┘ │
└────────────────────────────────────────┘
步骤3: 重新组装
┌───┐
│ 3 │ <- 根
└─┬─┘
│
└───┐
│
┌─▼─┐
│ 5 │
└─┬─┘
│
└───┐
│
┌─▼─┐
│ 7 │
└───┘
重新组装代码:
psLeft->psRight = psTree->psLeft; // L 的右子树 = M 的左子树
psRight->psLeft = psTree->psRight; // R 的左子树 = M 的右子树
psTree->psLeft = sTmp1.psRight; // M 的左子树 = L
psTree->psRight = sTmp1.psLeft; // M 的右子树 = R
插入操作详解
PVRSRVInsert 函数
IMG_INTERNAL
IMG_PSPLAY_TREE PVRSRVInsert(IMG_PSPLAY_FLAGS_T uiFlags, IMG_PSPLAY_TREE psTree)
{
IMG_PSPLAY_TREE psNew;
// 步骤1: 如果树非空，先 Splay
if (psTree != NULL)
{
psTree = PVRSRVSplay(uiFlags, psTree);
// 如果键已存在，直接返回
if (psTree->uiFlags == uiFlags)
{
return psTree;
}
}
// 步骤2: 分配新节点
psNew = (IMG_PSPLAY_TREE) OSAllocMem(sizeof(IMG_SPLAY_TREE));
if (psNew == NULL)
{
PVR_DPF((PVR_DBG_ERROR,
"Error: failed to allocate memory for splay tree node."));
return NULL;
}
// 步骤3: 初始化新节点
psNew->uiFlags = uiFlags;
OSCachedMemSet(&(psNew->buckets[0]), 0, sizeof(psNew->buckets));
#if defined(PVR_CTZLL)
// 初始化位图：所有桶都为空
psNew->bHasEltsMapping = ~(((IMG_ELTS_MAPPINGS) 1 <<
(sizeof(psNew->buckets) / sizeof(psNew->buckets[0]))) - 1);
#endif
// 步骤4: 插入新节点
if (psTree == NULL)
{
// 空树，新节点成为根
psNew->psLeft = NULL;
psNew->psRight = NULL;
return psNew;
}
if (uiFlags < psTree->uiFlags)
{
// 新节点插入到根的左边
psNew->psLeft = psTree->psLeft;
psNew->psRight = psTree;
psTree->psLeft = NULL;
}
else
{
// 新节点插入到根的右边
psNew->psRight = psTree->psRight;
psNew->psLeft = psTree;
psTree->psRight = NULL;
}
return psNew;
}
插入过程图解
场景: 插入 flags=4
初始树:
┌───┐
│ 6 │
└─┬─┘
│
┌───┴───┐
│ │
┌─▼─┐ ┌─▼─┐
│ 2 │ │ 8 │
└─┬─┘ └───┘
│
└───┐
│
┌─▼─┐
│ 5 │
└───┘
步骤1: Splay(4) - 虽然 4 不存在，但会 Splay 到最接近的位置
执行 Splay(4):
- 4 < 6, 向左
- 4 > 2, 向右
- 到达 5 (最接近的节点)
Splay 后:
┌───┐
│ 5 │ <- 最接近 4 的节点
└─┬─┘
│
┌───┴───┐
│ │
┌─▼─┐ ┌─▼─┐
│ 2 │ │ 6 │
└───┘ └─┬─┘
│
└───┐
│
┌─▼─┐
│ 8 │
└───┘
步骤2: 插入新节点 4
因为 4 < 5:
psNew->psLeft = psTree->psLeft; // = 2
psNew->psRight = psTree; // = 5
psTree->psLeft = NULL;
最终树:
┌───┐
│ 4 │ <- 新节点成为根
└─┬─┘
│
┌───┴───┐
│ │
┌─▼─┐ ┌─▼─┐
│ 2 │ │ 5 │
└───┘ └─┬─┘
│
└───┐
│
┌─▼─┐
│ 6 │
└─┬─┘
│
└───┐
│
┌─▼─┐
│ 8 │
└───┘
特点:
- 新插入的节点总是成为根
- O(log n) 均摊时间复杂度
- 利用 Splay 操作自动平衡
位图初始化详解
#if defined(PVR_CTZLL)
psNew->bHasEltsMapping = ~(((IMG_ELTS_MAPPINGS) 1 <<
(sizeof(psNew->buckets) / sizeof(psNew->buckets[0]))) - 1);
#endif
计算过程:
假设:
- sizeof(psNew->buckets) = 64 * 8 = 512 bytes
- sizeof(psNew->buckets[0]) = 8 bytes
- 桶数量 = 512 / 8 = 64
计算:
步骤1: (IMG_ELTS_MAPPINGS) 1 << 64
= 0x0000000000000001 << 64
= 0x0000000000000000 (溢出归零, 但实际是 2^64)
步骤2: 2^64 - 1
= 0xFFFFFFFFFFFFFFFF (所有64位都是1)
步骤3: ~0xFFFFFFFFFFFFFFFF
= 0x0000000000000000
结果: bHasEltsMapping = 0 (所有桶都标记为空)
位图含义:
bit 0 = 0: bucket[0] 空
bit 1 = 0: bucket[1] 空
...
bit 63 = 0: bucket[63] 空
当插入第一个元素到 bucket[5]:
bHasEltsMapping |= (1 << 5)
= 0x0000000000000020
现在:
bit 5 = 1: bucket[5] 非空
其他 bits = 0: 其他桶都空
删除操作详解
VRSRVDelete 函数
IMG_INTERNAL
IMG_PSPLAY_TREE PVRSRVDelete(IMG_PSPLAY_FLAGS_T uiFlags, IMG_PSPLAY_TREE psTree)
{
IMG_PSPLAY_TREE psTmp;
if (psTree == NULL)
{
return NULL;
}
// 步骤1: Splay 目标节点到根
psTree = PVRSRVSplay(uiFlags, psTree);
// 步骤2: 检查是否找到
if (uiFlags == psTree->uiFlags)
{
// 找到了，删除根节点
if (psTree->psLeft == NULL)
{
// 没有左子树，右子树成为新根
psTmp = psTree->psRight;
}
else
{
// 有左子树，需要合并左右子树
// 在左子树中 Splay 目标值 (会 Splay 出最大节点)
psTmp = PVRSRVSplay(uiFlags, psTree->psLeft);
// 将右子树接到左子树的最大节点
psTmp->psRight = psTree->psRight;
}
// 释放原根节点
OSFreeMem(psTree);
return psTmp;
}
// 步骤3: 未找到，返回 Splay 后的树
return psTree;
}
删除过程图解
场景1: 删除节点没有左子树
初始树:
┌───┐
│ 8 │
└─┬─┘
│
┌───┴───┐
│ │
┌─▼─┐ ┌─▼─┐
│ 4 │ │ 10│
└─┬─┘ └───┘
│
┌───┴───┐
│ │
┌─▼─┐ ┌─▼─┐
│ 2 │ │ 6 │
└───┘ └───┘
Delete(6):
步骤1: Splay(6)
┌───┐
│ 6 │ <- 目标到根
└─┬─┘
│
┌───┴───┐
│ │
┌─▼─┐ ┌─▼─┐
│ 4 │ │ 8 │
└─┬─┘ └─┬─┘
│ │
┌─▼─┐ ┌─▼─┐
│ 2 │ │ 10│
└───┘ └───┘
步骤2: 删除根节点 6
psTree->psLeft == NULL? NO, 有左子树
执行:
psTmp = PVRSRVSplay(6, psTree->psLeft);
// 在左子树中 Splay, 会将左子树最大节点 (4) 提升到根
┌───┐
│ 4 │ <- 左子树最大节点
└─┬─┘
│
┌───┴───┐
│ │
┌─▼─┐ NULL
│ 2 │
└───┘
psTmp->psRight = psTree->psRight;
最终树:
┌───┐
│ 4 │
└─┬─┘
│
┌───┴───┐
│ │
┌─▼─┐ ┌─▼─┐
│ 2 │ │ 8 │
└───┘ └─┬─┘
│
└───┐
│
┌─▼─┐
│ 10│
└───┘
场景2: 删除节点没有右子树
初始树:
┌───┐
│ 8 │
└─┬─┘
│
┌───┴───┐
│ │
┌─▼─┐ NULL
│ 4 │
└─┬─┘
│
┌───┴───┐
│ │
┌─▼─┐ ┌─▼─┐
│ 2 │ │ 6 │
└───┘ └───┘
Delete(8):
步骤1: Splay(8) - 已经在根
步骤2: 删除根节点 8
psTree->psLeft == NULL? NO
psTmp = PVRSRVSplay(8, psTree->psLeft);
┌───┐
│ 6 │ <- 左子树最大节点
└─┬─┘
│
┌───┴───┐
│ │
┌─▼─┐ NULL
│ 4 │
└─┬─┘
│
┌─▼─┐
│ 2 │
└───┘
psTmp->psRight = NULL (原本就没有右子树)
最终树:
┌───┐
│ 6 │
└─┬─┘
│
┌───┴───┐
│ │
┌─▼─┐ NULL
│ 4 │
└─┬─┘
│
┌─▼─┐
│ 2 │
└───┘
查找操作详解
PVRSRVFindNode 函数
IMG_INTERNAL
IMG_PSPLAY_TREE PVRSRVFindNode(IMG_PSPLAY_FLAGS_T uiFlags, IMG_PSPLAY_TREE psTree)
{
if (psTree == NULL)
{
return NULL;
}
while (psTree)
{
if (uiFlags == psTree->uiFlags)
{
return psTree; // 找到，直接返回
}
if (uiFlags < psTree->uiFlags)
{
psTree = psTree->psLeft; // 向左搜索
continue;
}
if (uiFlags > psTree->uiFlags)
{
psTree = psTree->psRight; // 向右搜索
continue;
}
}
return NULL; // 未找到
}
与 PVRSRVSplay 的区别:
┌────────────────────────────────────────────────────────┐
│ PVRSRVSplay vs PVRSRVFindNode │
├────────────────────────────────────────────────────────┤
│ │
│ PVRSRVSplay: │
│ - 修改树结构 (旋转操作) │
│ - 将目标移到根 │
│ - 时间: O(log n) 均摊 │
│ - 用途: Insert/Delete 前的预处理 │
│ │
│ PVRSRVFindNode: │
│ - 不修改树结构 │
│ - 标准二叉搜索树查找 │
│ - 时间: O(h), h 是树高度 │
│ - 用途: 只读查找，不希望改变树结构 │
│ │
└────────────────────────────────────────────────────────┘
查找过程图解
树结构:
┌───┐
│ 7 │
└─┬─┘
│
┌───────┴───────┐
│ │
┌─▼─┐ ┌─▼─┐
│ 3 │ │ 10│
└─┬─┘ └─┬─┘
│ │
┌───┴───┐ ┌───┴───┐
│ │ │ │
┌─▼─┐ ┌─▼─┐ ┌─▼─┐ ┌─▼─┐
│ 1 │ │ 5 │ │ 8 │ │ 12│
└───┘ └───┘ └───┘ └───┘
查找 flags=5:
┌──────────────────────────────────────┐
│ 步骤1: psTree = root (7) │
│ 5 < 7, 向左 │
├──────────────────────────────────────┤
│ 步骤2: psTree = 3 │
│ 5 > 3, 向右 │
├──────────────────────────────────────┤
│ 步骤3: psTree = 5 │
│ 5 == 5, 找到! 返回节点 │
└──────────────────────────────────────┘
查找 flags=9 (不存在):
┌──────────────────────────────────────┐
│ 步骤1: psTree = root (7) │
│ 9 > 7, 向右 │
├──────────────────────────────────────┤
│ 步骤2: psTree = 10 │
│ 9 < 10, 向左 │
├──────────────────────────────────────┤
│ 步骤3: psTree = 8 │
│ 9 > 8, 向右 │
├──────────────────────────────────────┤
│ 步骤4: psTree = NULL │
│ 未找到, 返回 NULL │
└──────────────────────────────────────┘
在 RA 中的实际应用
完整的查找流程
// 在 ra.c 中的使用
// 场景: 分配时查找对应 flags 的 buckets
static IMG_BOOL
_AttemptAllocAligned(RA_ARENA *pArena,
RA_LENGTH_T uSize,
RA_FLAGS_T uFlags,
RA_LENGTH_T uAlignment,
RA_BASE_T *base,
RA_PERISPAN_HANDLE *phPriv)
{
IMG_UINT32 index_low;
IMG_UINT32 index_high;
IMG_UINT32 i;
struct _BT_ *pBT = NULL;
// 步骤1: Splay 查找对应 flags 的节点
pArena->per_flags_buckets = PVRSRVSplay(uFlags, pArena->per_flags_buckets);
// 步骤2: 检查是否找到
if ((pArena->per_flags_buckets == NULL) ||
(pArena->per_flags_buckets->uiFlags != uFlags))
{
// 没有这个 flags 的 bucket
return IMG_FALSE;
}
// 步骤3: 在该节点的 buckets 中查找合适的 BT
index_low = pvr_log2(uSize);
// ... 计算 index_high ...
// 步骤4: 搜索 buckets
for (i = index_low; i < FREE_TABLE_LIMIT; i++) {
pBT = find_chunk_in_bucket(pArena->per_flags_buckets->buckets[i],
uSize, uAlignment, ~0);
if (pBT) break;
}
// ... 分配逻辑 ...
}
Splay 带来的性能优势
场景: RA 中频繁使用相同的 flags
假设有 10 种不同的 flags: 0, 1, 2, ..., 9
使用频率:
- flags=5: 60% (最常用)
- flags=3: 20%
- flags=7: 10%
- 其他: 10%
不使用 Splay (普通 BST):
┌────────────────────────────────────────┐
│ 树结构固定 │
│ 查找 flags=5 可能需要多次比较 │
│ 平均查找: O(log n) = O(log 10) ≈ 3.3 │
└────────────────────────────────────────┘
使用 Splay:
┌────────────────────────────────────────┐
│ 第一次查找 flags=5: O(log n) │
│ Splay 后, flags=5 在根 │
│ │
│ 后续查找 flags=5: O(1) │
│ (因为 60% 的访问都是 flags=5) │
│ │
│ 偶尔查找 flags=3: O(log n) │
│ 然后 flags=3 被 Splay 到根 │
│ │
│ 实际平均查找: │
│ 0.6 * O(1) + 0.2 * O(log n) + ... │
│ ≈ 0.6 + 0.66 + ... ≈ 1.5 │
│ │
│ 性能提升: 3.3 / 1.5 ≈ 2.2x │
└────────────────────────────────────────┘
实际使用流程图
RA_Alloc 中的 Splay Tree 使用:
┌────────────────────────────────────────┐
│ 1. 用户请求分配 │
│ - size = 64KB │
│ - flags = 0x123 │
└────────────┬───────────────────────────┘
│
▼
┌────────────────────────────────────────┐
│ 2. Splay 操作 │
│ pArena->per_flags_buckets = │
│ PVRSRVSplay(0x123, per_flags_buckets)│
└────────────┬───────────────────────────┘
│
▼
┌────────┴────────┐
│ │
YES NO
│ │
▼ ▼
┌─────────┐ ┌─────────────┐
│ 找到节点│ │ 节点不存在 │
│flags=0x123│ │ 返回失败 │
└────┬────┘ └─────────────┘
│
▼
┌────────────────────────────────────────┐
│ 3. 节点在根，访问 buckets │
│ node->buckets[index] 是 BT 链表 │
└────────────┬───────────────────────────┘
│
▼
┌────────────────────────────────────────┐
│ 4. 遍历 BT 链表查找合适的块 │
│ for (pBT = buckets[i]; pBT; ...) │
└────────────┬───────────────────────────┘
│
▼
┌────────┴────────┐
│ │
YES NO
│ │
▼ ▼
┌─────────┐ ┌─────────────┐
│ 分配成功│ │ 尝试导入资源│
└─────────┘ └─────────────┘
性能分析
时间复杂度
操作 最坏情况 均摊情况 说明
────────────────────────────────────────────────
Splay O(n) O(log n) 自平衡特性
Insert O(n) O(log n) 先 Splay 再插入
Delete O(n) O(log n) 先 Splay 再删除
FindNode O(n) O(h) 不改变结构, h=树高
关键点:
1. 均摊分析 (Amortized Analysis)
- 虽然单次操作可能 O(n)
- 但 m 次操作总时间 O(m log n)
- 均摊每次 O(log n)
2. 访问局部性优化
- 频繁访问的节点保持在根附近
- 实际性能优于 O(log n)
3. 最坏情况
- 退化为链表: O(n)
- 但通过 Splay 自动恢复平衡
空间复杂度
每个节点的空间:
基本字段:
- uiFlags: 8 bytes
- psLeft: 8 bytes
- psRight: 8 bytes
- buckets[64]: 64 * 8 = 512 bytes
- bHasEltsMapping: 8 bytes
─────────────────────────────
总计: 544 bytes
n 个节点的树:
总空间 = n * 544 bytes
示例:
10 个不同 flags -> 10 * 544 = 5440 bytes ≈ 5.3 KB
100 个不同 flags -> 100 * 544 = 54400 bytes ≈ 53 KB
优势:
- 节点数量 = 不同 flags 的数量
- 通常远小于总的 BT 数量
- 层次结构减少查找时间
与其他数据结构对比
Splay Tree vs 红黑树 vs AVL树 vs 哈希表:
┌────────────────────────────────────────────────────┐
│ Splay Tree (本实现) │
├────────────────────────────────────────────────────┤
│ 查找: O(log n) 均摊, 常访问节点 O(1) │
│ 插入: O(log n) 均摊 │
│ 删除: O(log n) 均摊 │
│ 有序: 是 │
│ 平衡: 自适应 (无显式平衡) │
│ 缓存友好: 好 (最近访问在根附近) │
│ 实现: 简单 │
│ 最坏情况: O(n) (但均摊 O(log n)) │
└────────────────────────────────────────────────────┘
┌────────────────────────────────────────────────────┐
│ 红黑树 │
├────────────────────────────────────────────────────┤
│ 查找: O(log n) 严格 │
│ 插入: O(log n) 严格 │
│ 删除: O(log n) 严格 │
│ 有序: 是 │
│ 平衡: 严格保证 │
│ 缓存友好: 中等 │
│ 实现: 复杂 (颜色规则) │
│ 最坏情况: O(log n) 保证 │
└────────────────────────────────────────────────────┘
┌────────────────────────────────────────────────────┐
│ AVL树 │
├────────────────────────────────────────────────────┤
│ 查找: O(log n) 严格 │
│ 插入: O(log n) 严格 │
│ 删除: O(log n) 严格 │
│ 有序: 是 │
│ 平衡: 更严格 (高度差 ≤ 1) │
│ 缓存友好: 好 (树更平衡) │
│ 实现: 复杂 (旋转规则) │
│ 最坏情况: O(log n) 保证 │
│ 查找最快, 但插入/删除需要更多旋转 │
└────────────────────────────────────────────────────┘
┌────────────────────────────────────────────────────┐
│ 哈希表 │
├────────────────────────────────────────────────────┤
│ 查找: O(1) 平均 │
│ 插入: O(1) 平均 │
│ 删除: O(1) 平均 │
│ 有序: 否 │
│ 平衡: N/A │
│ 缓存友好: 差 (随机访问) │
│ 实现: 中等 │
│ 最坏情况: O(n) (所有键冲突) │
│ 不支持有序遍历或范围查询 │
└────────────────────────────────────────────────────┘
选择建议:
─────────────────────────────────────────
场景1: 需要严格 O(log n) 保证
推荐: 红黑树 或 AVL树
场景2: 频繁查找相同的键 + 需要有序
推荐: Splay Tree ✓ (本实现)
场景3: 只需快速查找, 不需要有序
推荐: 哈希表
场景4: 频繁范围查询
推荐: B树 或 B+树
Splay Tree 的优势与劣势
优势
1. 访问局部性优化
┌────────────────────────────────────────┐
│ 场景: 80% 的访问集中在 20% 的节点 │
│ │
│ Splay 效果: │
│ - 热点数据自动上浮到根附近 │
│ - 实际访问时间远低于 O(log n) │
│ - 无需程序员手动优化 │
└────────────────────────────────────────┘
2. 实现简单
┌────────────────────────────────────────┐
│ vs 红黑树: │
│ - 无需颜色标记 │
│ - 无需复杂的平衡规则 │
│ - 只需要旋转操作 │
│ │
│ vs AVL树: │
│ - 无需平衡因子 │
│ - 无需多种旋转模式 │
└────────────────────────────────────────┘
3. 自适应性
┌────────────────────────────────────────┐
│ - 根据访问模式自动调整结构 │
│ - 适应数据分布变化 │
│ - 无需预知访问模式 │
└────────────────────────────────────────┘
4. 缓存友好
┌────────────────────────────────────────┐
│ - 热点数据在根附近 │
│ - 减少缓存失效 │
│ - 提高实际性能 │
└────────────────────────────────────────┘
劣势
1. 最坏情况不保证
┌────────────────────────────────────────┐
│ - 单次操作可能 O(n) │
│ - 不适合实时系统 │
│ - 对延迟敏感的应用需谨慎 │
└────────────────────────────────────────┘
2. 改变树结构
┌────────────────────────────────────────┐
│ - 每次访问都可能旋转 │
│ - 并发访问需要写锁 │
│ - 只读操作也需要修改结构 │
│ │
│ 解决: PVRSRVFindNode 提供只读查找 │
└────────────────────────────────────────┘
3. 性能不稳定
┌────────────────────────────────────────┐
│ - 依赖访问模式 │
│ - 随机访问时性能退化 │
│ - 难以预测具体性能 │
└────────────────────────────────────────┘
RA 中 Splay Tree 的作用总结
层次结构
RA 的三层查找结构:
Level 1: Splay Tree (按 flags 分类)
├─ 节点数 = 不同 flags 的数量
├─ 通常很小 (< 100)
└─ O(log n) 均摊, 热点 O(1)
Level 2: Bucket Array (按大小分类)
├─ 每个节点 64 个 buckets
├─ 索引 = log2(size)
└─ O(1) 直接索引
Level 3: BT Linked List (具体空闲段)
├─ 每个 bucket 一个链表
├─ 链表长度依赖负载
└─ O(k), k = 链表长度
总查找时间:
O(log n) + O(1) + O(k)
≈ O(log n + k)
其中 n << 总BT数, k 通常很小
为什么不用哈希表?
Splay Tree vs 哈希表 (针对 flags 分类):
┌────────────────────────────────────────┐
│ Splay Tree 优势: │
├────────────────────────────────────────┤
│ 1. 有序遍历 │
│ - 可以按 flags 顺序遍历 │
│ - 方便调试和统计 │
│ │
│ 2. 无哈希冲突 │
│ - 保证 O(log n) │
│ - 无需处理冲突 │
│ │
│ 3. 空间效率 │
│ - 节点数 = flags 种类 │
│ - 无需预分配大表 │
│ │
│ 4. 范围操作 │
│ - 可以查找相近的 flags │
│ - 支持区间查询 │
└────────────────────────────────────────┘
┌────────────────────────────────────────┐
│ 哈希表 劣势 (针对这个场景): │
├────────────────────────────────────────┤
│ 1. 无序 │
│ - 无法按 flags 顺序遍历 │
│ │
│ 2. 空间浪费 │
│ - 需要预分配较大的表 │
│ - 负载因子 < 1 时浪费空间 │
│ │
│ 3. Resize 开销 │
│ - flags 数量增长时需要 rehash │
│ - 峰值延迟高 │
└────────────────────────────────────────┘
结论:
对于 flags 分类这个特定场景，
Splay Tree 是更好的选择
实际性能表现
典型 RA 使用场景分析:
假设:
- 10 种不同 flags
- 其中 flags=0 占 70% 的访问
- flags=1 占 20% 的访问
- 其他 8 种各占 1.25% 的访问
Splay Tree 行为:
┌────────────────────────────────────────┐
│ 初始状态: 树相对平衡 │
│ │
│ 运行一段时间后: │
│ - flags=0 经常被 Splay 到根 │
│ - 70% 的访问: O(1) │
│ │
│ - flags=1 在 flags=0 附近 │
│ - 20% 的访问: O(2) ≈ O(1) │
│ │
│ - 其他 flags 较深 │
│ - 10% 的访问: O(log 10) ≈ O(3) │
│ │
│ 加权平均: │
│ 0.7*1 + 0.2*2 + 0.1*3 = 1.4 │
│ │
│ vs 普通 BST: log2(10) ≈ 3.3 │
│ 性能提升: 2.4x │
└────────────────────────────────────────┘
位图优化 (bHasEltsMapping)
位图作用
#if defined(PVR_CTZLL)
IMG_ELTS_MAPPINGS bHasEltsMapping;
#endif
用途: 快速定位非空 bucket
问题: 查找非空 bucket
┌────────────────────────────────────────┐
│ 朴素方法: │
│ for (i = 0; i < 64; i++) { │
│ if (buckets[i] != NULL) { │
│ // 找到 │
│ } │
│ } │
│ 时间: O(64) = O(n) │
└────────────────────────────────────────┘
┌────────────────────────────────────────┐
│ 位图优化: │
│ i = CTZ(bHasEltsMapping); │
│ // 直接定位第一个 1 bit │
│ 时间: O(1) │
└────────────────────────────────────────┘
示例:
buckets 状态:
[0]: NULL
[1]: NULL
[2]: ●●● (有元素)
[3]: NULL
[4]: NULL
[5]: ● (有元素)
...
[63]: NULL
bHasEltsMapping:
0000...0010 0100
│ │
│ └─ bit 2 = 1 (bucket[2] 非空)
└───── bit 5 = 1 (bucket[5] 非空)
查找第一个非空 bucket:
i = CTZ(bHasEltsMapping) = 2
直接访问 buckets[2]
位图操作
// 在 ra.c 中的使用
// 插入元素到 bucket
_FreeListInsert(RA_ARENA *pArena, BT *pBT)
{
IMG_UINT32 uIndex = pvr_log2(pBT->uSize);
// ... 插入 BT 到 buckets[uIndex] ...
#if defined(PVR_CTZLL)
// 标记该 bucket 非空
pArena->per_flags_buckets->bHasEltsMapping |=
((IMG_ELTS_MAPPINGS) 1 << uIndex);
#endif
}
// 从 bucket 移除元素
_FreeListRemove(RA_ARENA *pArena, BT *pBT)
{
IMG_UINT32 uIndex = pvr_log2(pBT->uSize);
// ... 从 buckets[uIndex] 移除 BT ...
#if defined(PVR_CTZLL)
if (pArena->per_flags_buckets->buckets[uIndex] == NULL)
{
// bucket 变空，清除位
pArena->per_flags_buckets->bHasEltsMapping &=
~((IMG_ELTS_MAPPINGS) 1 << uIndex);
}
#endif
}
// 快速查找非空 bucket
_AttemptAllocAligned(...)
{
#if defined(PVR_CTZLL)
// 快速跳过空 buckets
i = PVR_CTZLL(
(~(((IMG_ELTS_MAPPINGS)1 << (index_high + 1)) - 1))
& pArena->per_flags_buckets->bHasEltsMapping
);
#else
// 线性搜索
for (i = index_high + 1;
i < FREE_TABLE_LIMIT && buckets[i] == NULL;
i++);
#endif
}
位图操作示意
操作序列:
初始状态: bHasEltsMapping = 0x0000000000000000
所有 buckets 都空
1. 插入 16KB 块 (bucket[4])
bHasEltsMapping |= (1 << 4)
= 0x0000000000000010
2. 插入 128KB 块 (bucket[7])
bHasEltsMapping |= (1 << 7)
= 0x0000000000000090
3. 插入 32KB 块 (bucket[5])
bHasEltsMapping |= (1 << 5)
= 0x00000000000000B0
当前状态:
Bit: 7 6 5 4 3 2 1 0
1 0 1 1 0 0 0 0 = 0xB0
│ │ │
│ │ └─ bucket[4] 非空 (16KB)
│ └─── bucket[5] 非空 (32KB)
└─────── bucket[7] 非空 (128KB)
4. 查找 >= 64KB 的块
需要查找 bucket[6] 及以上
掩码: ~((1 << 7) - 1) = ~0x7F = 0xFF...80
(清除 bit 0-6, 保留 bit 7+)
结果: 0xB0 & 0xFF...80 = 0x80
CTZ(0x80) = 7
找到 bucket[7]
5. 从 bucket[4] 移除最后一个元素
if (buckets[4] == NULL)
bHasEltsMapping &= ~(1 << 4)
= 0x00000000000000A0
新状态:
Bit: 7 6 5 4 3 2 1 0
1 0 1 0 0 0 0 0 = 0xA0
│ │
│ └─── bucket[5] 非空
└─────── bucket[7] 非空
完整流程总结
RA 中的完整查找流程
用户请求分配: size=80KB, flags=0x123, alignment=4KB
┌─────────────────────────────────────────────────────┐
│ 步骤1: Splay 操作 (查找 flags=0x123) │
├─────────────────────────────────────────────────────┤
│ pArena->per_flags_buckets = │
│ PVRSRVSplay(0x123, pArena->per_flags_buckets) │
│ │
│ 树结构变化: │
│ Before: After: │
│ ┌──────┐ ┌──────┐ │
│ │0x100 │ │0x123 │ <- 目标到根 │
│ └──┬───┘ └──┬───┘ │
│ │ │ │
│ ┌───┴───┐ ┌───┴────┐ │
│ │ │ │ │ │
│ 0x123 0x200 0x100 0x200 │
└─────────────────────────────────────────────────────┘
┌─────────────────────────────────────────────────────┐
│ 步骤2: 检查是否找到 │
├─────────────────────────────────────────────────────┤
│ if (per_flags_buckets->uiFlags != 0x123) │
│ return IMG_FALSE; // 没有这个 flags │
│ │
│ 找到了, 继续... │
└─────────────────────────────────────────────────────┘
┌─────────────────────────────────────────────────────┐
│ 步骤3: 计算 bucket 索引范围 │
├─────────────────────────────────────────────────────┤
│ size = 80KB │
│ index_low = log2(80KB) = log2(20*4KB) = 4.32 │
│ = 4 (向下取整) │
│ │
│ alignment = 4KB, 可能需要额外空间 │
│ index_high = log2(80KB + 4KB - 1) = 5 │
│ │
│ 搜索范围: bucket[5] 及以上 │
└─────────────────────────────────────────────────────┘
┌─────────────────────────────────────────────────────┐
│ 步骤4: 使用位图快速定位非空 bucket │
├─────────────────────────────────────────────────────┤
│ #if defined(PVR_CTZLL) │
│ mask = ~((1 << 6) - 1) // 清除 bit 0-5 │
│ = 0xFFFFFFFFFFFFFFC0 │
│ │
│ available = bHasEltsMapping & mask │
│ = 0x0000000000000290 & 0xFF...C0 │
│ = 0x0000000000000280 │
│ │
│ i = CTZ(0x280) = 7 │
│ 直接跳到 bucket[7] │
│ #else │
│ // 线性搜索 │
│ for (i=6; i<64 && buckets[i]==NULL; i++); │
│ #endif │
└─────────────────────────────────────────────────────┘
┌─────────────────────────────────────────────────────┐
│ 步骤5: 在 bucket[7] 中查找合适的 BT │
├─────────────────────────────────────────────────────┤
│ bucket[7] 存储 128~255KB 的 BT 链表 │
│ │
│ pBT = find_chunk_in_bucket(buckets[7], │
│ 80KB, 4KB, ~0); │
│ │
│ 遍历链表: │
│ BT1: 150KB, base=0x10000 (4KB对齐) ✓ │
│ 150KB >= 80KB, 可用! │
└─────────────────────────────────────────────────────┘
┌─────────────────────────────────────────────────────┐
│ 步骤6: 分割和分配 │
├─────────────────────────────────────────────────────┤
│ _AllocAlignSplit(pArena, BT1, 80KB, 4KB, ...) │
│ │
│ 1. 从 bucket[7] 移除 BT1 │
│ 2. 分割: 80KB (分配) + 70KB (返回 free) │
│ 3. 70KB 插入 bucket[6] (64~127KB) │
│ 4. 80KB 标记为 live, 加入哈希表 │
│ 5. 更新位图 (如果 bucket 状态改变) │
└─────────────────────────────────────────────────────┘
性能分析:
- Splay: O(log m), m = flags 种类, 通常 < 100
- 位图定位: O(1)
- BT 查找: O(k), k = 链表长度, 通常 < 10
- 总计: O(log m + k) ≈ O(log 100 + 10) ≈ O(17)
如果 flags=0x123 是热点:
- 下次 Splay(0x123): O(1) (已在根)
- 总计: O(1 + k) ≈ O(11)
Splay Tree 在系统中的角色
完整的数据结构层次:
┌───────────────────────────────────────────────────────┐
│ RA_ARENA │
│ │
│ per_flags_buckets ──> Splay Tree Root │
└─────────────────┬─────────────────────────────────────┘
│
▼
┌─────────────────────┐
│ Splay Tree Node │ flags=0x123
│ uiFlags: 0x123 │
│ buckets[64] │
│ bHasEltsMapping │
└──────────┬──────────┘
│
┌──────────┴──────────┐
│ │
┌────▼────┐ ┌────▼────┐
│Node │ │Node │
│flags=0x │ │flags=0x2│
│100 │ │00 │
└─────────┘ └─────────┘
每个 Splay Tree 节点:
┌───────────────────────────────────────────────────────┐
│ buckets[0] -> NULL │
│ buckets[1] -> NULL │
│ buckets[2] -> BT(4~7KB) -> BT(6KB) -> NULL │
│ buckets[3] -> BT(8~15KB) -> NULL │
│ buckets[4] -> BT(16~31KB) -> BT(20KB) -> BT(28KB) │
│ ... │
│ buckets[63] -> NULL │
└───────────────────────────────────────────────────────┘
每个 BT 链表:
┌─────────┐ ┌─────────┐ ┌─────────┐
│BT │ ->│BT │-> │BT │ -> NULL
│base=... │ │base=... │ │base=... │
│size=... │ │size=... │ │size=... │
│type=free│ │type=free│ │type=free│
└─────────┘ └─────────┘ └─────────┘
性能优化总结
Splay Tree 带来的优化:
1. 时间优化
┌────────────────────────────────────────────┐
│ 无 Splay Tree (线性查找 flags): │
│ - 遍历所有 flags: O(m) │
│ - m 个 flags, 平均 m/2 次比较 │
│ │
│ 有 Splay Tree: │
│ - 查找 flags: O(log m) 均摊 │
│ - 热点 flags: O(1) │
│ │
│ 提升: 当 m=100, 从 O(50) -> O(1~7) │
│ 约 7~50倍 性能提升 │
└────────────────────────────────────────────┘
2. 空间优化
┌────────────────────────────────────────────┐
│ 数组方案 (所有可能的 flags): │
│ - 需要预分配: 2^32 个指针 │
│ - 空间: 2^32 * 8 = 32GB (!!) │
│ │
│ 哈希表方案: │
│ - 需要预分配: 足够大的表 │
│ - 空间: ~4 * m * 8 bytes │
│ - 对于 m=100: 3.2KB │
│ │
│ Splay Tree 方案: │
│ - 按需分配: 只分配实际使用的 │
│ - 空间: m * 544 bytes │
│ - 对于 m=100: 53KB │
│ │
│ 权衡: 比哈希表多用空间 (存储树结构) │
│ 但支持有序操作和范围查询 │
└────────────────────────────────────────────┘
3. 自适应优化
┌────────────────────────────────────────────┐
│ 访问模式: 80-20 原则 │
│ - 80% 访问集中在 20% 的 flags │
│ │
│ Splay 效果: │
│ - 热点自动上浮 │
│ - 冷数据自然下沉 │
│ - 无需人工干预 │
│ │
│ 实测效果 (假设): │
│ - 热点访问: O(1~2) │
│ - 普通访问: O(log m) │
│ - 加权平均: O(2~3) │
│ │
│ vs 平衡树: 始终 O(log m) ≈ O(7) │
│ 提升: 2~3倍 │
└────────────────────────────────────────────┘
Splay Tree 关键代码片段分析
旋转操作详解
// Zig-Zig 情况 (右旋转)
if (uiFlags < psTree->psLeft->uiFlags)
{
/* if we get to this point, we need to rotate right the tree */
psTmp2 = psTree->psLeft;
psTree->psLeft = psTmp2->psRight;
psTmp2->psRight = psTree;
psTree = psTmp2;
if (psTree->psLeft == NULL)
{
break;
}
}
图解:
旋转前:
psTree
│
┌─▼─┐
│ Y │
└─┬─┘
│
┌────┴────┐
│ │
┌─▼─┐ ┌─▼─┐
│ X │ │ C │
└─┬─┘ └───┘
│
┌───┴───┐
│ │
A B
代码执行:
psTmp2 = psTree->psLeft; // psTmp2 = X
psTree->psLeft = psTmp2->psRight; // Y->left = B
psTmp2->psRight = psTree; // X->right = Y
psTree = psTmp2; // psTree = X
旋转后:
psTree
│
┌─▼─┐
│ X │
└─┬─┘
│
┌────┴────┐
│ │
┌─▼─┐ ┌─▼─┐
│ A │ │ Y │
└───┘ └─┬─┘
│
┌────┴────┐
│ │
┌─▼─┐ ┌─▼─┐
│ B │ │ C │
└───┘ └───┘
性质保持:
- A < X < B < Y < C (BST性质)
- X 向上移动 (更接近根)
重新组装操作
/* at this point re-assemble the tree */
psLeft->psRight = psTree->psLeft;
psRight->psLeft = psTree->psRight;
psTree->psLeft = sTmp1.psRight;
psTree->psRight = sTmp1.psLeft;
return psTree;
图解:
Splay 过程中的三棵树:
在循环中:
┌─────────┐ ┌─────────┐ ┌─────────┐
│Left Tree│ │Middle │ │Right │
│(较大值) │ │(当前) │ │(较小值) │
└─────────┘ └─────────┘ └─────────┘
L M R
L 结构 (反向):
sTmp1.psRight -> ... (收集的较大节点)
R 结构 (反向):
sTmp1.psLeft -> ... (收集的较小节点)
重新组装:
步骤1: psLeft->psRight = psTree->psLeft
将 M 的左子树接到 L 的右端
步骤2: psRight->psLeft = psTree->psRight
将 M 的右子树接到 R 的左端
步骤3: psTree->psLeft = sTmp1.psRight
L 成为 M 的左子树
步骤4: psTree->psRight = sTmp1.psLeft
R 成为 M 的右子树
最终树:
M (目标节点在根)
/ \
L R
(较小) (较大)
插入时的树分裂
if (uiFlags < psTree->uiFlags)
{
psNew->psLeft = psTree->psLeft;
psNew->psRight = psTree;
psTree->psLeft = NULL;
}
else
{
psNew->psRight = psTree->psRight;
psNew->psLeft = psTree;
psTree->psRight = NULL;
}
图解:
Splay 后树的状态:
psTree (最接近目标的节点)
/ \
小的 大的
情况1: 新键 < psTree->uiFlags
Before Splay:
psTree
/ \
A B
插入 psNew:
psNew->psLeft = psTree->psLeft; // psNew->left = A
psNew->psRight = psTree; // psNew->right = psTree
psTree->psLeft = NULL; // psTree->left = NULL
After:
psNew
/ \
A psTree
\
B
所有节点关系:
A < psNew < psTree < B ✓
情况2: 新键 > psTree->uiFlags
Before Splay:
psTree
/ \
A B
插入 psNew:
psNew->psRight = psTree->psRight; // psNew->right = B
psNew->psLeft = psTree; // psNew->left = psTree
psTree->psRight = NULL; // psTree->right = NULL
After:
psNew
/ \
psTree B
/
A
所有节点关系:
A < psTree < psNew < B ✓
测试场景与边界情况
空树操作
// 空树插入
IMG_PSPLAY_TREE tree = NULL;
tree = PVRSRVInsert(5, tree);
结果:
┌─────┐
│ 5 │ (单节点树)
└─────┘
// 空树 Splay
tree = PVRSRVSplay(5, NULL);
结果: NULL (返回 NULL)
// 空树删除
tree = PVRSRVDelete(5, NULL);
结果: NULL (返回 NULL)
// 空树查找
node = PVRSRVFindNode(5, NULL);
结果: NULL (返回 NULL)
单节点操作
树: [5]
// Splay 存在的键
tree = PVRSRVSplay(5, tree);
结果: [5] (不变)
// Splay 不存在的键
tree = PVRSRVSplay(3, tree);
结果: [5] (不变, 但尝试查找)
// 插入已存在的键
tree = PVRSRVInsert(5, tree);
结果: [5] (不变, Splay 后发现已存在)
// 插入新键
tree = PVRSRVInsert(3, tree);
结果:
┌─────┐
│ 3 │
└──┬──┘
└───┐
┌─▼─┐
│ 5 │
└───┘
// 删除唯一节点
tree = PVRSRVDelete(5, tree);
结果: NULL (空树)
退化情况
场景: 按升序插入 1, 2, 3, 4, 5
插入 1:
┌───┐
│ 1 │
└───┘
插入 2:
┌───┐
│ 2 │ (新节点成为根)
└─┬─┘
│
┌───▼──┐
│ │
1 NULL
插入 3:
┌───┐
│ 3 │ (新节点成为根)
└─┬─┘
│
┌───▼──┐
│ │
2 NULL
│
┌─▼─┐
│ 1 │
└───┘
最终树 (插入 1-5):
┌───┐
│ 5 │
└─┬─┘
│
┌───▼──┐
│ │
4 NULL
│
┌───▼──┐
│ │
3 NULL
│
┌─▼─┐
│ 2 │
└─┬─┘
│
┌─▼─┐
│ 1 │
└───┘
特点:
- 退化为链表
- 高度 = n
- 单次操作 O(n)
但是:
访问任意节点后会自动平衡
例如 Splay(1):
┌───┐
│ 1 │
└─┬─┘
│
└───┐
┌─▼─┐
│ 2 │
└─┬─┘
│
└───┐
┌─▼─┐
│ 3 │
└─┬─┘
│
└───┐
┌─▼─┐
│ 4 │
└─┬─┘
│
┌─▼─┐
│ 5 │
└───┘
再次 Splay(5):
树变回接近平衡的状态
实现技巧与注意事项
Top-Down vs Bottom-Up
本实现使用 Top-Down Splay:
Top-Down 优势:
┌────────────────────────────────────────┐
│ 1. 单次遍历 │
│ - 从根到目标只需一次 │
│ - 无需回溯 │
│ │
│ 2. 空间效率 │
│ - 不需要父指针 │
│ - 不需要栈 │
│ │
│ 3. 代码简洁 │
│ - 迭代实现 │
│ - 易于理解 │
└────────────────────────────────────────┘
Bottom-Up 对比:
┌────────────────────────────────────────┐
│ 1. 两次遍历 │
│ - 向下查找 │
│ - 向上旋转 │
│ │
│ 2. 需要额外信息 │
│ - 父指针 或 栈 │
│ │
│ 3. 代码复杂 │
│ - 递归 或 栈管理 │
└────────────────────────────────────────┘
内存管理
// 分配节点
psNew = (IMG_PSPLAY_TREE) OSAllocMem(sizeof(IMG_SPLAY_TREE));
if (psNew == NULL)
{
PVR_DPF((PVR_DBG_ERROR,
"Error: failed to allocate memory for splay tree node."));
return NULL;
}
// 初始化
psNew->uiFlags = uiFlags;
OSCachedMemSet(&(psNew->buckets[0]), 0, sizeof(psNew->buckets));
// 释放节点
OSFreeMem(psTree);
注意事项:
1. 分配失败处理
┌────────────────────────────────────────┐
│ - 返回 NULL, 保持原树不变 │
│ - 不会导致数据结构损坏 │
│ - 上层需要检查返回值 │
└────────────────────────────────────────┘
2. 初始化
┌────────────────────────────────────────┐
│ - buckets 清零 (所有指针 NULL) │
│ - bHasEltsMapping 初始化 │
│ - 左右指针由插入逻辑设置 │
└────────────────────────────────────────┘
3. 释放时机
┌────────────────────────────────────────┐
│ Delete 操作: │
│ - 先 Splay 到根 │
│ - 合并子树 │
│ - 释放根节点 │
│ │
│ 注意: 不要释放仍在树中的节点! │
└────────────────────────────────────────┘
并发访问考虑
Splay Tree 的并发问题:
问题:
┌────────────────────────────────────────┐
│ Splay 操作修改树结构 │
│ - 即使只是查找也会旋转 │
│ - 读操作变成写操作 │
│ - 需要写锁保护 │
└────────────────────────────────────────┘
在 RA 中的解决方案:
┌────────────────────────────────────────┐
│ 1. Arena 级别的锁 │
│ - 所有操作都持有 Arena 锁 │
│ - 自然保证了串行化 │
│ │
│ 2. PVRSRVFindNode 不修改树 │
│ - 只读查找时使用 │
│ - 但性能不如 Splay │
│ │
│ 3. 接受 Splay 的语义 │
│ - "查找"本身就是优化操作 │
│ - 未来访问会更快 │
└────────────────────────────────────────┘
如果需要并发:
┌────────────────────────────────────────┐
│ 方案1: 读写锁 │
│ - 读操作: 使用 FindNode (共享锁) │
│ - 写操作: 使用 Splay (独占锁) │
│ │
│ 方案2: 线程本地树 │
│ - 每个线程自己的 Splay Tree │
│ - 无竞争 │
│ │
│ 方案3: 改用其他数据结构 │
│ - 并发友好的跳表 │
│ - 无锁哈希表 │
└────────────────────────────────────────┘
总结
Splay Tree 核心特性总结
┌─────────────────────────────────────────────────────┐
│ Splay Tree 特性汇总 │
├─────────────────────────────────────────────────────┤
│ │
│ 1. 自调整 (Self-Adjusting) │
│ └─ 通过 Splay 操作自动优化结构 │
│ │
│ 2. 访问局部性 (Locality) │
│ └─ 热点数据自动上浮到根附近 │
│ │
│ 3. 均摊 O(log n) (Amortized) │
│ └─ 单次可能 O(n), 但长期平均 O(log n) │
│ │
│ 4. 简单实现 (Simplicity) │
│ └─ 只需旋转, 无需平衡因子或颜色 │
│ │
│ 5. 统一操作 (Unified) │
│ └─ Insert/Delete/Find 都基于 Splay │
│ │
│ 6. 自适应 (Adaptive) │
│ └─ 根据访问模式动态调整 │
│ │
└─────────────────────────────────────────────────────┘
在 RA 中的价值
RA 使用 Splay Tree 的理由:
1. 场景匹配
┌────────────────────────────────────────┐
│ RA 的 flags 访问特征: │
│ - flags 种类有限 (通常 < 100) │
│ - 存在热点 flags (20-80 原则) │
│ - 需要快速查找 │
│ │
│ Splay Tree 正好适合: │
│ - 小规模数据集 │
│ - 有访问局部性 │
│ - 自动优化热点 │
└────────────────────────────────────────┘
2. 性能收益
┌────────────────────────────────────────┐
│ vs 线性查找: │
│ - 提升: 10~50倍 (取决于 flags 数量) │
│ │
│ vs 普通 BST: │
│ - 提升: 2~3倍 (利用访问局部性) │
│ │
│ vs 哈希表: │
│ - 支持有序操作 │
│ - 空间效率更高 (按需分配) │
└────────────────────────────────────────┘
3. 维护简单
┌────────────────────────────────────────┐
│ - 无需手动平衡 │
│ - 插入/删除逻辑简单 │
│ - 调试容易 (BST 性质易验证) │
└────────────────────────────────────────┘
Splay Tree 与其他组件的配合
完整的 RA 查找链:
┌──────────────────────────────────────────────┐
│ Level 2: Bucket Array (大小分类) │
│ - 桶数: 64 (FREE_TABLE_LIMIT) │
│ - 复杂度: O(1) 直接索引 │
│ - 优化: bHasEltsMapping 位图加速 │
│ - 作用: 按大小快速缩小搜索范围 │
└────────────────┬─────────────────────────────┘
│
▼
┌──────────────────────────────────────────────┐
│ Level 3: BT Linked List (具体空闲段) │
│ - 链表长度: 依赖负载, 通常 < 10 │
│ - 复杂度: O(k), k = 链表长度 │
│ - 策略: 按大小排序 (OPTIMAL 策略) │
│ - 作用: 找到满足对齐和大小要求的具体块 │
└──────────────────────────────────────────────┘
总查找时间:
O(log m) + O(1) + O(k)
= O(log m + k)
其中:
- m: flags 种类 (< 100)
- k: 链表长度 (< 10)
实际性能:
- 最好: O(1 + 1 + 1) = O(1) (热点 flags, 第一个 BT 满足)
- 平均: O(3 + 1 + 3) = O(7) (log 100 ≈ 3, 平均链长 3)
- 最坏: O(7 + 1 + 10) = O(18) (冷 flags, 遍历整个链表)
vs 线性搜索所有 BT:
- O(n), n = 所有 BT 数量 (可能 > 1000)
- 提升: 50~100倍
设计权衡分析
Splay Tree 的设计权衡:
┌────────────────────────────────────────────────┐
│ 优势 (Pros) │
├────────────────────────────────────────────────┤
│ ✓ 自适应性 │
│ - 自动优化访问模式 │
│ - 热点数据快速访问 │
│ │
│ ✓ 实现简单 │
│ - 代码简洁 │
│ - 易于理解和维护 │
│ │
│ ✓ 空间效率 │
│ - 无需额外的平衡信息 │
│ - 按需分配节点 │
│ │
│ ✓ 缓存友好 │
│ - 热点数据在根附近 │
│ - 减少内存访问 │
│ │
│ ✓ 支持有序操作 │
│ - 中序遍历得到有序序列 │
│ - 支持范围查询 │
└────────────────────────────────────────────────┘
┌────────────────────────────────────────────────┐
│ 劣势 (Cons) │
├────────────────────────────────────────────────┤
│ ✗ 最坏情况不保证 │
│ - 单次操作可能 O(n) │
│ - 不适合硬实时系统 │
│ │
│ ✗ 修改树结构 │
│ - 查找也会旋转 │
│ - 并发访问需要写锁 │
│ │
│ ✗ 依赖访问模式 │
│ - 随机访问时性能退化 │
│ - 最坏情况接近链表 │
│ │
│ ✗ 难以预测性能 │
│ - 性能波动 │
│ - 基准测试困难 │
└────────────────────────────────────────────────┘
在 RA 中的权衡结论:
┌────────────────────────────────────────────────┐
│ ✓ flags 数量有限 (< 100) │
│ └─ Splay 劣势影响小 │
│ │
│ ✓ 存在明显的访问热点 │
│ └─ Splay 优势充分发挥 │
│ │
│ ✓ 不是实时系统 │
│ └─ 可以接受偶尔的延迟峰值 │
│ │
│ ✓ 需要有序操作 │
│ └─ 支持调试和统计 │
│ │
│ 结论: Splay Tree 是最优选择 ✓ │
└────────────────────────────────────────────────┘
完整示例：从插入到查找
完整操作序列示例:
初始: 空 Splay Tree
操作1: Insert(flags=0x100)
┌─────────┐
│ 0x100 │
└─────────┘
操作2: Insert(flags=0x200)
┌─────────┐
│ 0x200 │ (新节点成为根)
└────┬────┘
│
┌────┴────┐
│ │
0x100 NULL
操作3: Insert(flags=0x050)
┌─────────┐
│ 0x050 │ (新节点成为根)
└────┬────┘
│
┌────┴────┐
│ │
NULL ┌───▼────┐
│ 0x200 │
└───┬────┘
│
┌────┴────┐
│ │
0x100 NULL
操作4: 分配 flags=0x100, size=64KB
步骤4.1: Splay(0x100)
┌─────────┐
│ 0x100 │ (0x100 到根)
└────┬────┘
│
┌────────┴────────┐
│ │
┌────▼────┐ ┌────▼────┐
│ 0x050 │ │ 0x200 │
└─────────┘ └─────────┘
步骤4.2: 访问 node(0x100)->buckets
index = log2(64KB) = log2(16*4KB) = 4
bucket = node->buckets[4]
步骤4.3: 在 bucket[4] 的 BT 链表中查找
pBT = find_chunk_in_bucket(bucket[4], 64KB, ...)
操作5: 再次分配 flags=0x100, size=32KB
步骤5.1: Splay(0x100)
- 0x100 已经在根，Splay 操作 O(1) 返回
┌─────────┐
│ 0x100 │ (仍在根)
└────┬────┘
│
┌────────┴────────┐
│ │
┌────▼────┐ ┌────▼────┐
│ 0x050 │ │ 0x200 │
└─────────┘ └─────────┘
步骤5.2: 直接访问 node(0x100)->buckets[3]
- 无需遍历树 ✓
- 性能提升显著 ✓
操作6: 分配 flags=0x200, size=128KB
步骤6.1: Splay(0x200)
┌─────────┐
│ 0x200 │ (0x200 到根)
└────┬────┘
│
┌────────┴────────┐
│ │
┌────▼────┐ ┌────▼────┐
│ 0x100 │ │ NULL │
└────┬────┘
│
┌────┴────┐
│ │
0x050 NULL
步骤6.2: 访问 node(0x200)->buckets[7]
观察:
- flags=0x100 使用频率高 -> 经常在根附近
- flags=0x200 使用频率中 -> 根据使用上浮
- flags=0x050 使用频率低 -> 在树的深处
- 自动形成"热-温-冷"的层次结构
性能基准对比
假设场景:
- 10 种不同 flags
- 1000 次操作
- 访问分布: 80% 集中在 2 个热点 flags
┌──────────────────────────────────────────────────────┐
│ 数据结构性能对比 │
├──────────────────────────────────────────────────────┤
│ │
│ 1. 线性搜索链表 │
│ - 平均: 遍历 5 个节点 │
│ - 1000 次 * 5 = 5000 次比较 │
│ - 基准: 1.0x │
│ │
│ 2. 无序数组 + 线性搜索 │
│ - 平均: 遍历 5 个元素 │
│ - 1000 次 * 5 = 5000 次比较 │
│ - 相对: 1.0x │
│ │
│ 3. 哈希表 │
│ - 平均: O(1) │
│ - 1000 次 * 1 = 1000 次查找 │
│ - 相对: 5.0x 提升 │
│ - 但: 无序，额外空间，resize 开销 │
│ │
│ 4. 红黑树 │
│ - 平均: log2(10) ≈ 3.3 │
│ - 1000 次 * 3.3 = 3300 次比较 │
│ - 相对: 1.5x 提升 │
│ - 优点: 严格 O(log n) 保证 │
│ │
│ 5. AVL 树 │
│ - 平均: log2(10) ≈ 3.3 (更平衡) │
│ - 1000 次 * 3.2 = 3200 次比较 │
│ - 相对: 1.56x 提升 │
│ - 查找最快，但插入/删除旋转多 │
│ │
│ 6. Splay Tree (80% 热点) │
│ - 热点 (800次): 平均 1.5 次比较 │
│ - 冷点 (200次): 平均 4 次比较 │
│ - 加权: 800*1.5 + 200*4 = 2000 次比较 │
│ - 相对: 2.5x 提升 │
│ - 优势: 自适应热点，有序 │
│ │
└──────────────────────────────────────────────────────┘
结论:
- 纯查找速度: 哈希表 > Splay Tree > AVL ≈ 红黑树 > 线性
- 有序支持: Splay/AVL/红黑 > 线性 > 哈希表 (不支持)
- 空间效率: Splay/红黑/AVL > 线性 > 哈希表
- 实现复杂度: Splay > 红黑 > AVL > 哈希表 > 线性
- 自适应性: Splay (优秀) > 其他 (无)
综合评分 (针对 RA 场景):
1. Splay Tree: ★★★★★ (最佳选择)
2. 红黑树: ★★★★☆
3. 哈希表: ★★★☆☆
4. AVL 树: ★★★☆☆
5. 线性搜索: ★☆☆☆☆
实际应用建议
何时使用 Splay Tree:
✓ 推荐场景:
┌────────────────────────────────────────┐
│ 1. 访问具有局部性 │
│ - 80-20 原则明显 │
│ - 热点数据反复访问 │
│ │
│ 2. 数据集规模适中 │
│ - 节点数 < 10000 │
│ - 过大会导致旋转开销高 │
│ │
│ 3. 需要有序操作 │
│ - 范围查询 │
│ - 顺序遍历 │
│ │
│ 4. 非实时系统 │
│ - 可以接受偶尔的延迟峰值 │
│ - 关注平均性能 │
│ │
│ 5. 实现简单优先 │
│ - 代码维护成本低 │
│ - 调试容易 │
└────────────────────────────────────────┘
✗ 不推荐场景:
┌────────────────────────────────────────┐
│ 1. 需要严格实时保证 │
│ - 不能接受 O(n) 最坏情况 │
│ - 使用红黑树或 AVL 树 │
│ │
│ 2. 访问完全随机 │
│ - 无访问局部性 │
│ - 使用哈希表或红黑树 │
│ │
│ 3. 高并发读写 │
│ - 读操作也修改结构 │
│ - 使用跳表或并发哈希表 │
│ │
│ 4. 只需快速查找 │
│ - 不需要有序 │
│ - 使用哈希表更简单 │
└────────────────────────────────────────┘
代码质量与优化建议
当前实现的优点
✓ 优秀的设计:
┌────────────────────────────────────────┐
│ 1. Top-Down 实现 │
│ - 单次遍历 │
│ - 无需父指针 │
│ - 空间效率高 │
│ │
│ 2. 代码简洁 │
│ - 逻辑清晰 │
│ - 易于理解 │
│ - 注释充分 │
│ │
│ 3. 健壮性 │
│ - 空指针检查 │
│ - 内存分配失败处理 │
│ - 保持树的不变性 │
│ │
│ 4. 集成良好 │
│ - 与 RA 紧密配合 │
│ - 支持 RA 的 bucket 结构 │
│ - 位图优化 │
└────────────────────────────────────────┘
可能的优化方向
潜在优化:
1. 惰性 Splay (Lazy Splay)
┌────────────────────────────────────────┐
│ 当前: 每次访问都 Splay │
│ │
│ 优化: 批量操作后统一 Splay │
│ - 减少旋转次数 │
│ - 提高批量操作性能 │
│ - 但增加实现复杂度 │
└────────────────────────────────────────┘
2. 半-Splay (Semi-Splaying)
┌────────────────────────────────────────┐
│ 当前: Splay 到根 │
│ │
│ 优化: 只 Splay 部分路径 │
│ - 减少旋转开销 │
│ - 仍保持大部分优势 │
│ - 权衡: 性能 vs 简洁性 │
└────────────────────────────────────────┘
3. 缓存根节点
┌────────────────────────────────────────┐
│ 当前: 每次从根开始 │
│ │
│ 优化: 记录最近访问的节点 │
│ - 热点直接命中 │
│ - 进一步提升热点访问 │
│ - 增加: 额外的缓存字段 │
└────────────────────────────────────────┘
4. 统计信息
┌────────────────────────────────────────┐
│ 当前: 无统计 │
│ │
│ 优化: 记录访问频率、树高度等 │
│ - 便于性能分析 │
│ - 辅助调优决策 │
│ - 增加: 统计字段和维护成本 │
└────────────────────────────────────────┘
建议: 保持当前实现
理由:
- 简洁性 > 微小性能提升
- RA 场景下已足够高效
- 优化收益不明显
- 增加复杂度不值得
测试建议
推荐的测试场景:
1. 基本功能测试
┌────────────────────────────────────────┐
│ - 空树操作 │
│ - 单节点操作 │
│ - 多节点插入/删除/查找 │
│ - 已存在键的插入 │
│ - 不存在键的删除 │
└────────────────────────────────────────┘
2. 性能测试
┌────────────────────────────────────────┐
│ - 顺序插入 (最坏情况) │
│ - 随机插入 │
│ - 重复访问热点 │
│ - 冷热混合访问 │
│ - 大量插入后批量删除 │
└────────────────────────────────────────┘
3. 压力测试
┌────────────────────────────────────────┐
│ - 大规模插入 (10000+ 节点) │
│ - 内存分配失败模拟 │
│ - 边界条件 (最大/最小 flags) │
└────────────────────────────────────────┘
4. 正确性验证
┌────────────────────────────────────────┐
│ - BST 性质检查 (中序遍历有序) │
│ - 内存泄漏检查 │
│ - 并发访问 (如果支持) │
└────────────────────────────────────────┘
最终总结
Splay Tree 是 RA 系统中 按 flags 分类 的核心数据结构，通过自适应的树结构调整，充分利用访问局部性原理，在简单实现和高效性能之间取得了优秀的平衡。
关键要点回顾：
- 核心机制: Top-Down Splay 操作将访问节点移到根
- 性能特征: O(log n) 均摊，热点数据 O(1)
- 主要优势: 自适应、简单实现、缓存友好
- 主要劣势: 最坏情况不保证、修改树结构
- 应用价值: 在 RA 的三层查找结构中承担第一层，将 O(m) 线性查找优化为 O(log m)，配合访问热点优化实际达到 O(1~3)
这个 Splay Tree 实现是一个教科书级别的例子，展示了如何将经典算法应用到实际系统中，并通过与 RA 的紧密集成（buckets 数组、位图优化）发挥最大价值。
