内核中的数据结构：SplayTree
内核中的数据结构：
Splay Tree
Splay Tree(伸展树)是Binary Search Tree(二叉搜索树)， Daniel Sleator和Robert E.Tarjan发明。但此操作可能会花费O(n)时间，但m次操作的最坏情况为O(m*log2(n))。
Splay Tree是在节点访问后，此节点将成为该树的根。如此节点位置深，则根到该节点路径上会有很多较深节点。旋转后，这些节点的深度会减少。
查找频率高的item经常在靠近树根的位置。每次查找后，对树进行重构，把item挪倒离树根近地方。Splay tree是自调整形式的二叉查找树，会沿着某个节点到树根间的路径，通过一系列旋转把此节点搬移到树根。
RtlSplay 主要例程，完成节点到Splay树根的操作。
RtlDelete 删除节点，重新平衡。
RtlIsRoot 节点是否是Splay树根。
RtlRealPredecessor 返回节点的pre节点。
RtlInsertAsLeftChild
PRTL_SPLAY_LINKS
RtlSplay( IN PRTL_SPLAY_LINKS Links )
{
PRTL_SPLAY_LINKS L;
PRTL_SPLAY_LINKS P;
PRTL_SPLAY_LINKS G;
// while links is not the root we need to keep rotating it toward
// the root
L = Links;
while (!RtlIsRoot(L)) {
P = RtlParent(L);
G = RtlParent(P);
if (RtlIsLeftChild(L)) {
if (RtlIsRoot(P)) {
/*
we have the following case
P L
/ \ / \
L c ==> a P
/ \ / \
a b b c
*/
// Connect P & b
//
P->LeftChild = L->RightChild;
if (P->LeftChild != NULL) {P->LeftChild->Parent = P;}
// Connect L & P
L->RightChild = P;
P->Parent = L;
// Make L the root
L->Parent = L;
} else if (RtlIsLeftChild(P)) {
/* we have the following case
| |
G L
/ \ / \
P d ==> a P
/ \ / \
L c b G
/ \ / \
a b c d
*/
// Connect P & b
P->LeftChild = L->RightChild;
if (P->LeftChild != NULL) {P->LeftChild->Parent = P;}
// Connect G & c
G->LeftChild = P->RightChild;
if (G->LeftChild != NULL) {G->LeftChild->Parent = G;}
// Connect L & Great GrandParent
if (RtlIsRoot(G)) {
L->Parent = L;
} else {
L->Parent = G->Parent;
*(ParentsChildPointerAddress(G)) = L;
}
// Connect L & P
L->RightChild = P;
P->Parent = L;
//
// Connect P & G
//
P->RightChild = G;
G->Parent = P;
} else { // RtlIsRightChild(Parent)
/*
we have the following case
| |
G L
/ \ / \
a P G P
/ \ / \ / \
L d ==> a b c d
/ \
b c
*/
//
// Connect G & b
//
G->RightChild = L->LeftChild;
if (G->RightChild != NULL) {G->RightChild->Parent = G;}
//
// Connect P & c
//
P->LeftChild = L->RightChild;
if (P->LeftChild != NULL) {P->LeftChild->Parent = P;}
//
// Connect L & Great GrandParent
//
if (RtlIsRoot(G)) {
L->Parent = L;
} else {
L->Parent = G->Parent;
*(ParentsChildPointerAddress(G)) = L;
}
//
// Connect L & G
//
L->LeftChild = G;
G->Parent = L;
//
// Connect L & P
//
L->RightChild = P;
P->Parent = L;
}
} else { // RtlIsRightChild(L)
if (RtlIsRoot(P)) {
/*
we have the following case
P L
/ \ / \
a L P c
/ \ / \
b c ==> a b
*/
//
// Connect P & b
//
P->RightChild = L->LeftChild;
if (P->RightChild != NULL) {P->RightChild->Parent = P;}
//
// Connect P & L
//
L->LeftChild = P;
P->Parent = L;
//
// Make L the root
//
L->Parent = L;
} else if (RtlIsRightChild(P)) {
/*
we have the following case
| |
G L
/ \ / \
a P P d
/ \ / \
b L G c
/ \ / \
c d ==> a b
*/
//
// Connect G & b
//
G->RightChild = P->LeftChild;
if (G->RightChild != NULL) {G->RightChild->Parent = G;}
//
// Connect P & c
//
P->RightChild = L->LeftChild;
if (P->RightChild != NULL) {P->RightChild->Parent = P;}
//
// Connect L & Great GrandParent
//
if (RtlIsRoot(G)) {
L->Parent = L;
} else {
L->Parent = G->Parent;
*(ParentsChildPointerAddress(G)) = L;
}
//
// Connect L & P
//
L->LeftChild = P;
P->Parent = L;
//
// Connect P & G
//
P->LeftChild = G;
G->Parent = P;
} else { // RtlIsLeftChild(P)
/*
we have the following case
| |
G L
/ \ / \
P d P G
/ \ / \ / \
a L ==> a b c d
/ \
b c
*/
//
// Connect P & b
//
P->RightChild = L->LeftChild;
if (P->RightChild != NULL) {P->RightChild->Parent = P;}
//
// Connect G & c
//
G->LeftChild = L->RightChild;
if (G->LeftChild != NULL) {G->LeftChild->Parent = G;}
//
// Connect L & Great GrandParent
//
if (RtlIsRoot(G)) {
L->Parent = L;
} else {
L->Parent = G->Parent;
*(ParentsChildPointerAddress(G)) = L;
}
//
// Connect L & P
//
L->LeftChild = P;
P->Parent = L;
//
// Connect L & G
//
L->RightChild = G;
G->Parent = L;
}
}
}
return L;
}
