基础

伸展树由一个或者多个entry定义，每一个entry就是一个节点，每个节点由3个指针组成

Parent
LeftChild
RightChild

这几个指针看名字就知道啥意思

每一个节点由一个伸展树头部RTL_SPLAY_LINKS和用户定义的数据组成

typedef struct _RTL_SPLAY_LINKS {
    struct _RTL_SPLAY_LINKS *Parent;
    struct _RTL_SPLAY_LINKS *LeftChild;
    struct _RTL_SPLAY_LINKS *RightChild;
} RTL_SPLAY_LINKS;
typedef RTL_SPLAY_LINKS *PRTL_SPLAY_LINKS;

RtlInitializeSplayLinks宏用于初始化SplayLinks：

SplayLink->Parent = Parent;
SplayLink->LeftChild = SplayLink->RightChild = NULL;

你也可以自定义伸展树的结构，只要里面插入了伸展树头部即可，就像使用ListEntry一样

typedef struct _MYSPLAYNODE {
    //
    // Splay Link to be used to insert this node
    // into my splay tree.
    //
    RTL_SPLAY_LINKS  SplayInfo;
    //
    // Data definition that I am using to build
    // splay node relationships..
    //
    ULONG   Value;
} RTL_SPLAY_LINKS;
typedef RTL_SPLAY_LINKS *PRTL_SPLAY_LINKS;

节点的添加

3步走：

在树中找到合适的可以插入的位置
将新节点插入到找到的节点的LeftChild或者RightChild
"伸展"树，使得新插入的节点成为根节点

伸展树的遍历通过RtlLeftChild或者RtlRightChild函数来完成，使用哪一个函数根据新节点和父节点的关系决定，比如新节点比父节点小，就使用Left，比父节点大就使用Right

使用RtlInsertAsLeftChild或者Right来插入新节点到指定节点的左边或者右边

调用RtlSplay来“伸展”树

伸展树的同步

caller需要负责对伸展树的访问进行同步，根据IRQL的值，不同的同步策略会被使用

对于IRQL>=DISPATCH_DELVE(2)，自旋锁将会被使用，而且节点必须存在于non-paged pool（因为此时page-fault无法工作）

其他情况下就使用dispatcher对象：互斥量、信号量等，同时，节点可以存在于paged-pool中

伸展树的用处

每一个数据结构和其他的相比都有其优缺点，所有的数据结构的评价标准可以抽象为以下三个维度：

内存占用
搜索时间
管理开销（插入、删除等操作）

由于伸展树可以提高最近访问数据的访问速度，经常被用来实现缓存算法

需要注意的是，连续的对伸展树中的所有节点进行访问将会导致很大的开销，因为每一次访问都会引起伸展树的“伸展”操作

替代品：Generic Tables

伸展树用起来多少有点费劲，Windows使用伸展树实现了Generic Tables

Generic Tables的优势：

generic tables会帮你完成所有的伸展树操作，而且还提供了枚举树中所有节点的函数
如果伸展树无法提供你所需的性能，可以很方便的替换为AVL树，在引入ntrtl.h头文件之前，加入#define RTL_USE_AVL_TABLES 0定义即可
windbg提供了一个!gentable扩展

Generic Tables由RTL_GENERIC_TABLE结构体定义：

typedef struct _RTL_GENERIC_TABLE {
    PRTL_SPLAY_LINKS TableRoot;
    LIST_ENTRY InsertOrderList;
    PLIST_ENTRY OrderedPointer;
    ULONG WhichOrderedElement;
    ULONG NumberGenericTableElements;
    PRTL_GENERIC_COMPARE_ROUTINE CompareRoutine;
    PRTL_GENERIC_ALLOCATE_ROUTINE AllocateRoutine;
    PRTL_GENERIC_FREE_ROUTINE FreeRoutine;
    PVOID TableContext;
} RTL_GENERIC_TABLE;
typedef RTL_GENERIC_TABLE *PRTL_GENERIC_TABLE;

和_RTL_AVL_TABLE结构体的定义很像，就是第一个字段不一样

该结构体使用RtlInitializeGenericTable进行初始化

VOID
NTAPI
RtlInitializeGenericTable (
    PRTL_GENERIC_TABLE Table,
    PRTL_GENERIC_COMPARE_ROUTINE CompareRoutine,
    PRTL_GENERIC_ALLOCATE_ROUTINE AllocateRoutine,
    PRTL_GENERIC_FREE_ROUTINE FreeRoutine,
    PVOID TableContext
    );

table就是RTL_GENERIC_TABLE的地址
CompareRoutine就是用于节点之间进行比较的函数，返回RTL_GENERIC_COMPARE_RESULTS表明两个节点之间的关系
AllocateRoutine是用于分配新节点的函数
FreeRoutine用于在节点删除后释放节点内存
TableContext是上下文数据，可以是NULL