898 lines
37 KiB
C
898 lines
37 KiB
C
/*++
|
|
Copyright (c) 1989 Microsoft Corporation
|
|
|
|
Module Name:
|
|
Triangle.c
|
|
|
|
Abstract:
|
|
This module implements the general splay utilities for a two link triangular splay structure.
|
|
|
|
Author:
|
|
Gary Kimura [GaryKi] 28-May-1989
|
|
|
|
Environment:
|
|
Pure utility routine
|
|
--*/
|
|
|
|
#include <nt.h>
|
|
#include "triangle.h"
|
|
|
|
// There are three type of swap macros.
|
|
// The first two (are really the same) are used to swap pointer and ulongs.
|
|
// The last macro is used to swap refs but it does not swap the ref type flags.
|
|
|
|
#define SwapPointers(Ptr1, Ptr2) { \
|
|
PVOID _SWAP_POINTER_TEMP; \
|
|
_SWAP_POINTER_TEMP = (PVOID)(Ptr1); \
|
|
(Ptr1) = (Ptr2); \
|
|
(Ptr2) = _SWAP_POINTER_TEMP; \
|
|
}
|
|
|
|
#define SwapUlongs(Ptr1, Ptr2) { \
|
|
ULONG _SWAP_POINTER_TEMP; \
|
|
_SWAP_POINTER_TEMP = (ULONG)(Ptr1); \
|
|
(Ptr1) = (Ptr2); \
|
|
(Ptr2) = _SWAP_POINTER_TEMP; \
|
|
}
|
|
|
|
#define SwapRefsButKeepFlags(Ref1, Ref2) { \
|
|
ULONG _SWAP_ULONG_TEMP; \
|
|
_SWAP_ULONG_TEMP = (ULONG)(Ref1); \
|
|
(Ref1) = ((Ref2) & 0xfffffffc) | ((Ref1) & 0x00000003); \
|
|
(Ref2) = (_SWAP_ULONG_TEMP & 0xfffffffc) | ((Ref2) & 0x00000003); \
|
|
}
|
|
|
|
// The macro SetRefViaPointer takes a pointer to a ref and checks to see if it is a valid pointer.
|
|
// If it is a valid pointer it copies in the ref a ulong, but does not overwrite the ref flags already in the ref.
|
|
|
|
#define SetRefViaPointer(Ref, Ulong) { \
|
|
if (Ref != NULL) { \
|
|
(*(Ref)) = (((ULONG)(Ulong)) & 0xfffffffc) | ((ULONG)(*(Ref)) & 0x00000003); \
|
|
} \
|
|
}
|
|
|
|
// The following five procedures are local to triangle.c and are used to help manipluate the splay links.
|
|
// The first two procedures take a pointer to a splay link and returns the address of the ref that points back to the input link, via either the parent or child.
|
|
// They return NULL if there is not a back pointer.
|
|
// The result of these two procedures is often used in the code with the SetRefViaPointer macro.
|
|
// The third procedure is used to swap the position to two splay links in the tree (i.e., the links swap position, but everyone else stays stationary).
|
|
// This is a general procedure that can will swap any two nodes, irregardless of their relative positions in the tree.
|
|
// The last two procedures do a single rotation about a tree node.
|
|
// They either rotate left or rotate right and assume that the appropriate child exists (i.e., for rotate left a right child exists and for rotate right a left child exists).
|
|
|
|
PULONG TriAddressOfBackRefViaParent (IN PTRI_SPLAY_LINKS Links);
|
|
PULONG TriAddressOfBackRefViaChild (IN PTRI_SPLAY_LINKS Links);
|
|
VOID TriSwapSplayLinks (IN PTRI_SPLAY_LINKS Link1, IN PTRI_SPLAY_LINKS Link2);
|
|
VOID TriRotateRight (IN PTRI_SPLAY_LINKS Links);
|
|
VOID TriRotateLeft (IN PTRI_SPLAY_LINKS Links);
|
|
|
|
|
|
PTRI_SPLAY_LINKS TriSplay (IN PTRI_SPLAY_LINKS Links)
|
|
/*++
|
|
Routine Description:
|
|
This Splay function takes as input a pointer to a splay link in a tree and splays the tree.
|
|
Its function return value is a pointer to the root of the splayed tree.
|
|
Arguments:
|
|
Links - Supplies the pointer to a splay link in a tree
|
|
Return Values:
|
|
PRTI_SPLAY_LINKS - Returns a pointer to the root of the splayed tree
|
|
--*/
|
|
{
|
|
PTRI_SPLAY_LINKS Parent;
|
|
PTRI_SPLAY_LINKS GrandParent;
|
|
|
|
// While Links is not the root we test and rotate until it is the root.
|
|
while (!TriIsRoot(Links)) {
|
|
// Get Parent and then check if we don't have a grandparent.
|
|
Parent = TriParent(Links);
|
|
if (TriIsRoot(Parent)) {
|
|
// No grandparent so check for single rotation
|
|
if (TriIsLeftChild(Links)) {
|
|
// do the following single rotation
|
|
|
|
// Parent Links
|
|
// / ==> \
|
|
// Links Parent
|
|
TriRotateRight(Parent);
|
|
} else { // TriIsRightChild(Links)
|
|
// do the following single rotation
|
|
|
|
// Parent Links
|
|
// \ ==> /
|
|
// Links Parent
|
|
TriRotateLeft(Parent);
|
|
}
|
|
} else { // !TriIsRoot(Parent)
|
|
// Get grandparent and check for the four double rotation cases
|
|
GrandParent = TriParent(Parent);
|
|
if (TriIsLeftChild(Links)) {
|
|
if (TriIsLeftChild(Parent)) {
|
|
// do the following double rotation
|
|
|
|
// GP L
|
|
// / \
|
|
// P ==> P
|
|
// / \
|
|
// L GP
|
|
|
|
TriRotateRight(GrandParent);
|
|
TriRotateRight(Parent);
|
|
} else { // TriIsRightChild(Parent)
|
|
// do the following double rotation
|
|
|
|
// GP L
|
|
// \ / \
|
|
// P ==> GP P
|
|
// /
|
|
// L
|
|
TriRotateRight(Parent);
|
|
TriRotateLeft(GrandParent);
|
|
}
|
|
} else { // TriIsRightChild(Links);
|
|
if (TriIsLeftChild(Parent)) {
|
|
// do the following double rotation
|
|
|
|
// GP L
|
|
// / / \
|
|
// P ==> P GP
|
|
// \
|
|
// L
|
|
TriRotateLeft(Parent);
|
|
TriRotateRight(GrandParent);
|
|
} else { // TriIsRightChild(Parent)
|
|
// do the following double rotation
|
|
|
|
// GP L
|
|
// \ /
|
|
// P ==> P
|
|
// \ /
|
|
// L GP
|
|
TriRotateLeft(GrandParent);
|
|
TriRotateLeft(Parent);
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
return Links;
|
|
}
|
|
|
|
|
|
PTRI_SPLAY_LINKS TriDelete (IN PTRI_SPLAY_LINKS Links)
|
|
/*++
|
|
Routine Description:
|
|
This Delete function takes as input a pointer to a splay link in a tree and deletes that node from the tree.
|
|
Its function return value is a pointer to the root the tree.
|
|
If the tree is now empty, the return value is NULL.
|
|
Arguments:
|
|
Links - Supplies the pointer to a splay link in a tree
|
|
Return Values:
|
|
PRTI_SPLAY_LINKS - Returns a pointer to the root of the splayed tree
|
|
--*/
|
|
{
|
|
PTRI_SPLAY_LINKS Predecessor;
|
|
PTRI_SPLAY_LINKS Parent;
|
|
PTRI_SPLAY_LINKS Child;
|
|
PULONG ParentChildRef;
|
|
|
|
// First check to see if Links as two children.
|
|
// If it does then swap Links with its subtree predecessor.
|
|
// Now we are guaranteed that Links has at most one child.
|
|
if ((TriLeftChild(Links) != NULL) && (TriRightChild(Links) != NULL)) {
|
|
// get the predecessor, and swap their position in the tree
|
|
Predecessor = TriSubtreePredecessor(Links);
|
|
TriSwapSplayLinks(Predecessor, Links);
|
|
}
|
|
|
|
// If Links has no children then delete links by checking if it is already the root or has a parent.
|
|
// If it is the root then the tree is now empty, otherwise set the appropriate parent's child pointer, and possibly sibling, and splay the parent.
|
|
if ((TriLeftChild(Links) == NULL) && (TriRightChild(Links) == NULL)) {
|
|
// Links has no children, if it is the root then return NULL
|
|
if (TriIsRoot(Links)) {
|
|
return NULL;
|
|
}
|
|
|
|
// Links has no children, check to see if links is an only child
|
|
Parent = TriParent(Links);
|
|
if (MakeIntoPointer(Parent->Refs.Child) == Links && MakeIntoPointer(Links->Refs.ParSib) == Parent) {
|
|
// Links has no children and is an only child. So simply make our parent have no children and splay our parent.
|
|
|
|
// Parent Parent
|
|
// | ==>
|
|
// Links
|
|
|
|
Parent->Refs.Child = 0;
|
|
return TriSplay(Parent);
|
|
} else if (TriIsLeftChild(Links)) {
|
|
// Links has no children and has a right sibling. So make the parent's child Ref be the right sibling, splay the parent.
|
|
|
|
// Parent Parent
|
|
// / \ ==> \
|
|
// Links Sibling Sibling
|
|
|
|
Parent->Refs.Child = MakeIntoRightChildRef(Links->Refs.ParSib);
|
|
return TriSplay(Parent);
|
|
} else { // TriIsRightChild(Links)
|
|
// Links has no children and has a left sibling.
|
|
// So make link's back via its parent into a parent ref of link's parent, and splay the parent.
|
|
|
|
// Parent Parent
|
|
// / \ /
|
|
// Sibling Links ==> Sibling
|
|
|
|
ParentChildRef = TriAddressOfBackRefViaParent(Links);
|
|
*ParentChildRef = MakeIntoParentRef(Parent);
|
|
return TriSplay(Parent);
|
|
}
|
|
}
|
|
|
|
// otherwise Links has one child.
|
|
// If it is the root then make the child the new root, otherwise link together the child and parent, and splay the parent.
|
|
// But first remember who our child is.
|
|
if (TriLeftChild(Links) != NULL) {
|
|
Child = TriLeftChild(Links);
|
|
} else {
|
|
Child = TriRightChild(Links);
|
|
}
|
|
|
|
// If links is the root then we make the child the root and return the child.
|
|
if (TriIsRoot(Links)) {
|
|
Child->Refs.ParSib = MakeIntoParentRef(Child);
|
|
return Child;
|
|
}
|
|
|
|
// Links is not the root, so set links's back ref via its parent to be links's child and the set the child's ParSib to be link's ParSib, and splay the parent.
|
|
// This will handle the case where link is an only or has a sibling on either side.
|
|
Parent = TriParent(Links);
|
|
ParentChildRef = TriAddressOfBackRefViaParent(Links);
|
|
SetRefViaPointer(ParentChildRef, Child);
|
|
Child->Refs.ParSib = Links->Refs.ParSib;
|
|
return TriSplay(Parent);
|
|
}
|
|
|
|
|
|
PTRI_SPLAY_LINKS TriSubtreeSuccessor (IN PTRI_SPLAY_LINKS Links)
|
|
/*++
|
|
Routine Description:
|
|
This SubTreeSuccessor function takes as input a pointer to a splay link in a tree and returns a pointer to the successor of the input node of the subtree rooted at the input node.
|
|
If there is not a successor, the return value is NULL.
|
|
Arguments:
|
|
Links - Supplies the pointer to a splay link in a tree
|
|
Return Values:
|
|
PRTI_SPLAY_LINKS - Returns a pointer to the successor in the subtree
|
|
--*/
|
|
{
|
|
PTRI_SPLAY_LINKS Ptr;
|
|
|
|
// check to see if there is a right subtree to the input link if there is then the subtree successor is the left most node in the right subtree.
|
|
// That is find and return P in the following diagram
|
|
|
|
// Links
|
|
// \
|
|
// .
|
|
// .
|
|
// .
|
|
// /
|
|
// P
|
|
// \
|
|
|
|
if ((Ptr = TriRightChild(Links)) != NULL) {
|
|
while (TriLeftChild(Ptr) != NULL) {
|
|
Ptr = TriLeftChild(Ptr);
|
|
}
|
|
|
|
return Ptr;
|
|
}
|
|
|
|
// Otherwise we do not have a subtree successor so we simply return NULL
|
|
return NULL;
|
|
}
|
|
|
|
|
|
PTRI_SPLAY_LINKS TriSubtreePredecessor (IN PTRI_SPLAY_LINKS Links)
|
|
/*++
|
|
Routine Description:
|
|
This SubTreePredecessor function takes as input a pointer to a splay link in a tree and returns a pointer to the predecessor of the input node of the subtree rooted at the input node.
|
|
If there is not a predecessor, the return value is NULL.
|
|
Arguments:
|
|
Links - Supplies the pointer to a splay link in a tree
|
|
Return Values:
|
|
PRTI_SPLAY_LINKS - Returns a pointer to the predecessor in the subtree
|
|
--*/
|
|
{
|
|
PTRI_SPLAY_LINKS Ptr;
|
|
|
|
// check to see if there is a left subtree to the input link if there is then the subtree predecessor is the right most node in the left subtree.
|
|
// That is find and return P in the following diagram
|
|
|
|
// Links
|
|
// /
|
|
// .
|
|
// .
|
|
// .
|
|
// P
|
|
// /
|
|
|
|
if ((Ptr = TriLeftChild(Links)) != NULL) {
|
|
while (TriRightChild(Ptr) != NULL) {
|
|
Ptr = TriRightChild(Ptr);
|
|
}
|
|
|
|
return Ptr;
|
|
}
|
|
|
|
// Otherwise we do not have a subtree predecessor so we simply return NULL
|
|
return NULL;
|
|
}
|
|
|
|
|
|
PTRI_SPLAY_LINKS TriRealSuccessor (IN PTRI_SPLAY_LINKS Links)
|
|
/*++
|
|
Routine Description:
|
|
This RealSuccess function takes as input a pointer to a splay link in a tree and returns a pointer to the successor of the input node within the entire tire.
|
|
If there is not a successor, the return value is NULL.
|
|
Arguments:
|
|
Links - Supplies the pointer to a splay link in a tree
|
|
Return Values:
|
|
PRTI_SPLAY_LINKS - Returns a pointer to the successor in the entire tree
|
|
--*/
|
|
{
|
|
PTRI_SPLAY_LINKS Ptr;
|
|
|
|
// first check to see if there is a right subtree to the input link if there is then the real successor is the left most node in the right subtree.
|
|
// That is find and return P in the following diagram
|
|
|
|
// Links
|
|
// \
|
|
// .
|
|
// .
|
|
// .
|
|
// /
|
|
// P
|
|
// \
|
|
|
|
if ((Ptr = TriRightChild(Links)) != NULL) {
|
|
while (TriLeftChild(Ptr) != NULL) {
|
|
Ptr = TriLeftChild(Ptr);
|
|
}
|
|
|
|
return Ptr;
|
|
}
|
|
|
|
// we do not have a right child so check to see if have a parent and if so find the first ancestor that we are a left decendent of.
|
|
// That is find and return P in the following diagram
|
|
|
|
// P
|
|
// /
|
|
// .
|
|
// .
|
|
// .
|
|
// Links
|
|
Ptr = Links;
|
|
while (!TriIsLeftChild(Ptr) && !TriIsRoot(Ptr)) { // (TriIsRightChild(Ptr)) {
|
|
Ptr = TriParent(Ptr);
|
|
}
|
|
|
|
if (TriIsLeftChild(Ptr)) {
|
|
return TriParent(Ptr);
|
|
}
|
|
|
|
// Otherwise we do not have a real successor so we simply return NULL
|
|
return NULL;
|
|
}
|
|
|
|
|
|
PTRI_SPLAY_LINKS TriRealPredecessor (IN PTRI_SPLAY_LINKS Links)
|
|
/*++
|
|
Routine Description:
|
|
This RealPredecessor function takes as input a pointer to a splay link in a tree and returns a pointer to the predecessor of the input node within the entire tree.
|
|
If there is not a predecessor, the return value is NULL.
|
|
Arguments:
|
|
Links - Supplies the pointer to a splay link in a tree
|
|
Return Values:
|
|
PRTI_SPLAY_LINKS - Returns a pointer to the predecessor in the entire tree
|
|
--*/
|
|
{
|
|
PTRI_SPLAY_LINKS Ptr;
|
|
|
|
// first check to see if there is a left subtree to the input link if there is then the real predecessor is the right most node in the left subtree.
|
|
// That is find and return P in the following diagram
|
|
|
|
// Links
|
|
// /
|
|
// .
|
|
// .
|
|
// .
|
|
// P
|
|
// /
|
|
|
|
|
|
if ((Ptr = TriLeftChild(Links)) != NULL) {
|
|
while (TriRightChild(Ptr) != NULL) {
|
|
Ptr = TriRightChild(Ptr);
|
|
}
|
|
|
|
return Ptr;
|
|
}
|
|
|
|
// we do not have a left child so check to see if have a parent and if so find the first ancestor that we are a right decendent of.
|
|
// That is find and return P in the following diagram
|
|
|
|
// P
|
|
// \
|
|
// .
|
|
// .
|
|
// .
|
|
// Links
|
|
Ptr = Links;
|
|
while (TriIsLeftChild(Ptr)) {
|
|
Ptr = TriParent(Ptr);
|
|
}
|
|
|
|
if (!TriIsLeftChild(Ptr) && !TriIsRoot(Ptr)) { // (TriIsRightChild(Ptr)) {
|
|
return TriParent(Ptr);
|
|
}
|
|
|
|
// Otherwise we do not have a real predecessor so we simply return NULL
|
|
return NULL;
|
|
}
|
|
|
|
|
|
PULONG TriAddressOfBackRefViaParent (IN PTRI_SPLAY_LINKS Links)
|
|
{
|
|
PTRI_SPLAY_LINKS Ptr;
|
|
|
|
// If Links is the root then we do not have a back pointer via our parent so return NULL
|
|
if (TriIsRoot(Links)) {
|
|
return NULL;
|
|
}
|
|
|
|
// We are not the root so find our parent and if our parent directly points to us we return the address of our parent's reference to us.
|
|
// Otherwise (we must be a right child with a sibling) so return the address of our sibling's ParSib reference to us.
|
|
Ptr = TriParent(Links);
|
|
if (MakeIntoPointer(Ptr->Refs.Child) == Links) {
|
|
return &(Ptr->Refs.Child);
|
|
} else {
|
|
return &(MakeIntoPointer(Ptr->Refs.Child)->Refs.ParSib);
|
|
}
|
|
}
|
|
|
|
|
|
PULONG TriAddressOfBackRefViaChild (IN PTRI_SPLAY_LINKS Links)
|
|
{
|
|
PTRI_SPLAY_LINKS Ptr;
|
|
|
|
// Make Ptr be the same reference as found in our child field.
|
|
Ptr = MakeIntoPointer(Links->Refs.Child);
|
|
|
|
// If our child pointer is null then we don't have a back pointer via our child so return NULL.
|
|
if (Ptr == NULL) {
|
|
return NULL;
|
|
|
|
// if our child directly reference's us (then we only have one child) return the address of the ParSib of our only child.
|
|
} else if (MakeIntoPointer(Ptr->Refs.ParSib) == Links) {
|
|
return &(Ptr->Refs.ParSib);
|
|
|
|
// otherwise we have two children so return the address of the ParSib of the second child.
|
|
} else {
|
|
return &(MakeIntoPointer(Ptr->Refs.ParSib)->Refs.ParSib);
|
|
}
|
|
}
|
|
|
|
|
|
VOID TriSwapSplayLinks (IN PTRI_SPLAY_LINKS Link1, IN PTRI_SPLAY_LINKS Link2)
|
|
{
|
|
PULONG Parent1ChildRef;
|
|
PULONG Parent2ChildRef;
|
|
PULONG Child1ParSibRef;
|
|
PULONG Child2ParSibRef;
|
|
|
|
// We have the following situation
|
|
|
|
|
|
// Parent1 Parent2
|
|
// | |
|
|
// | |
|
|
// Link1 Link2
|
|
// / \ / \
|
|
// / \ / \
|
|
// LC1 RC1 LC2 RC2
|
|
|
|
// where one of the links can possibly be the root and one of the links can possibly be a direct child of the other, or can be connected via their sibling pointers.
|
|
// Without loss of generality we'll make link2 be the possible and root and link1 be the possible child, or link2 have a parsib pointer to link1
|
|
if ((TriIsRoot(Link1)) || (TriParent(Link2) == Link1) || (MakeIntoPointer(Link1->Refs.ParSib) == Link2)) {
|
|
SwapPointers(Link1, Link2);
|
|
}
|
|
|
|
// The cases we need to handle are
|
|
// 1. Link1 is not a child of link2, link2 is not the root, and they are not siblings
|
|
// 2. Link1 is not a child of link2, link2 is not the root, and they are siblings
|
|
// 3. Link1 is not a child of link2, link2 is the root
|
|
// 4. Link1 is an only child of link2, and link2 is not the root
|
|
// 5. Link1 is an only child of link2, and link2 is the root
|
|
// 6. Link1 is a left child of link2 (has a sibling), and link2 is not the root
|
|
// 7. Link1 is a left child of link2 (has a sibling), and link2 is the root
|
|
// 8. Link1 is a right child of link2 (has a sibling), and link2 is not the root
|
|
// 9. Link1 is a right child of link2 (has a sibling), and link2 is the root
|
|
|
|
// Each case will be handled separately
|
|
if (TriParent(Link1) != Link2) {
|
|
if (!TriIsRoot(Link2)) {
|
|
if (MakeIntoPointer(Link2->Refs.ParSib) != Link1) {
|
|
// Case 1 - Link1 is not a child of link2, Link2 is not the root, and they are not siblings
|
|
Parent1ChildRef = TriAddressOfBackRefViaParent(Link1);
|
|
Child1ParSibRef = TriAddressOfBackRefViaChild(Link1);
|
|
Parent2ChildRef = TriAddressOfBackRefViaParent(Link2);
|
|
Child2ParSibRef = TriAddressOfBackRefViaChild(Link2);
|
|
SwapUlongs(Link1->Refs.Child, Link2->Refs.Child);
|
|
SwapUlongs(Link1->Refs.ParSib, Link2->Refs.ParSib);
|
|
SetRefViaPointer(Parent1ChildRef, Link2);
|
|
SetRefViaPointer(Parent2ChildRef, Link1);
|
|
SetRefViaPointer(Child1ParSibRef, Link2);
|
|
SetRefViaPointer(Child2ParSibRef, Link1);
|
|
} else {
|
|
// Case 2 - Link1 is not a child of link2, Link2 is not the root, and they are siblings
|
|
Child1ParSibRef = TriAddressOfBackRefViaChild(Link1);
|
|
Parent2ChildRef = TriAddressOfBackRefViaParent(Link2);
|
|
Child2ParSibRef = TriAddressOfBackRefViaChild(Link2);
|
|
SwapUlongs(Link1->Refs.Child, Link2->Refs.Child);
|
|
SetRefViaPointer(Child1ParSibRef, Link2);
|
|
SetRefViaPointer(Child2ParSibRef, Link1);
|
|
*Parent2ChildRef = MakeIntoLeftChildRef(Link1);
|
|
Link2->Refs.ParSib = Link1->Refs.ParSib;
|
|
Link1->Refs.ParSib = MakeIntoSiblingRef(Link2);
|
|
}
|
|
} else {
|
|
// Case 3 - Link1 is not a child of link2, and Link2 is the root
|
|
Parent1ChildRef = TriAddressOfBackRefViaParent(Link1);
|
|
Child1ParSibRef = TriAddressOfBackRefViaChild(Link1);
|
|
Child2ParSibRef = TriAddressOfBackRefViaChild(Link2);
|
|
SwapUlongs(Link1->Refs.Child, Link2->Refs.Child);
|
|
Link2->Refs.ParSib = Link1->Refs.ParSib;
|
|
Link1->Refs.ParSib = MakeIntoParentRef(Link1);
|
|
SetRefViaPointer(Child1ParSibRef, Link2);
|
|
SetRefViaPointer(Child2ParSibRef, Link1);
|
|
SetRefViaPointer(Parent1ChildRef, Link2);
|
|
}
|
|
} else { // TriParent(Link1) == Link2
|
|
if (MakeIntoPointer(Link2->Refs.Child) == Link1 && MakeIntoPointer(Link1->Refs.ParSib) == Link2) { // Link1 is an only child
|
|
if (!TriIsRoot(Link2)) {
|
|
// Case 4 - Link1 is an only child of link2, and Link2 is not the root
|
|
Child1ParSibRef = TriAddressOfBackRefViaChild(Link1);
|
|
Parent2ChildRef = TriAddressOfBackRefViaParent(Link2);
|
|
SetRefViaPointer(Child1ParSibRef, Link2);
|
|
SetRefViaPointer(Parent2ChildRef, Link1);
|
|
Link1->Refs.ParSib = Link2->Refs.ParSib;
|
|
Link2->Refs.ParSib = MakeIntoParentRef(Link1);
|
|
SwapRefsButKeepFlags(Link1->Refs.Child, Link2->Refs.Child);
|
|
SetRefViaPointer(&Link1->Refs.Child, Link2);
|
|
} else {
|
|
// Case 5 - Link1 is an only child of link2, and Link2 is the root
|
|
Child1ParSibRef = TriAddressOfBackRefViaChild(Link1);
|
|
SetRefViaPointer(Child1ParSibRef, Link2);
|
|
Link1->Refs.ParSib = MakeIntoParentRef(Link1);
|
|
Link2->Refs.ParSib = MakeIntoParentRef(Link1);
|
|
SwapRefsButKeepFlags(Link1->Refs.Child, Link2->Refs.Child);
|
|
SetRefViaPointer(&Link1->Refs.Child, Link2);
|
|
}
|
|
} else if (TriIsLeftChild(Link1)) { // and link1 has a sibling
|
|
if (!TriIsRoot(Link2)) {
|
|
// Case 6 - Link1 is a left child of link2 (has a sibling), and Link2 is not the root
|
|
Child1ParSibRef = TriAddressOfBackRefViaChild(Link1);
|
|
Parent2ChildRef = TriAddressOfBackRefViaParent(Link2);
|
|
Child2ParSibRef = TriAddressOfBackRefViaChild(Link2);
|
|
SetRefViaPointer(Child1ParSibRef, Link2);
|
|
SetRefViaPointer(Parent2ChildRef, Link1);
|
|
SetRefViaPointer(Child2ParSibRef, Link1);
|
|
Link2->Refs.Child = Link1->Refs.Child;
|
|
Link1->Refs.Child = MakeIntoLeftChildRef(Link2);
|
|
SwapUlongs(Link1->Refs.ParSib, Link2->Refs.ParSib);
|
|
} else {
|
|
// Case 7 - Link1 is a left child of link2 (has a sibling), and Link2 is the root
|
|
Child1ParSibRef = TriAddressOfBackRefViaChild(Link1);
|
|
Child2ParSibRef = TriAddressOfBackRefViaChild(Link2);
|
|
SetRefViaPointer(Child1ParSibRef, Link2);
|
|
SetRefViaPointer(Child2ParSibRef, Link1);
|
|
Link2->Refs.Child = Link1->Refs.Child;
|
|
Link1->Refs.Child = MakeIntoLeftChildRef(Link2);
|
|
Link2->Refs.ParSib = Link1->Refs.ParSib;
|
|
Link1->Refs.ParSib = MakeIntoParentRef(Link1);
|
|
}
|
|
} else { // TriIsRightChild(Link1) and Link1 has a sibling
|
|
if (!TriIsRoot(Link2)) {
|
|
// Case 8 - Link1 is a right child of link2 (has a sibling), and Link2 is not the root
|
|
Parent1ChildRef = TriAddressOfBackRefViaParent(Link1);
|
|
Child1ParSibRef = TriAddressOfBackRefViaChild(Link1);
|
|
Parent2ChildRef = TriAddressOfBackRefViaParent(Link2);
|
|
SetRefViaPointer(Parent1ChildRef, Link2);
|
|
SetRefViaPointer(Child1ParSibRef, Link2);
|
|
SetRefViaPointer(Parent2ChildRef, Link1);
|
|
SwapUlongs(Link1->Refs.Child, Link2->Refs.Child);
|
|
Link1->Refs.ParSib = Link2->Refs.ParSib;
|
|
Link2->Refs.ParSib = MakeIntoParentRef(Link1);
|
|
} else {
|
|
// Case 9 - Link1 is a right child of link2 (has a sibling), and Link2 is the root
|
|
Parent1ChildRef = TriAddressOfBackRefViaParent(Link1);
|
|
Child1ParSibRef = TriAddressOfBackRefViaChild(Link1);
|
|
SetRefViaPointer(Parent1ChildRef, Link2);
|
|
SetRefViaPointer(Child1ParSibRef, Link2);
|
|
SwapUlongs(Link1->Refs.Child, Link2->Refs.Child);
|
|
Link1->Refs.ParSib = MakeIntoParentRef(Link1);
|
|
Link1->Refs.ParSib = MakeIntoParentRef(Link1);
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
|
|
VOID TriRotateRight (IN PTRI_SPLAY_LINKS Links)
|
|
{
|
|
BOOLEAN IsRoot;
|
|
PULONG ParentChildRef;
|
|
ULONG SavedParSibRef;
|
|
PTRI_SPLAY_LINKS LeftChild;
|
|
PTRI_SPLAY_LINKS a,b,c;
|
|
|
|
// We perform the following rotation
|
|
|
|
// -Links- -LeftChild-
|
|
// / \ / \
|
|
// LeftChild c ==> a Links
|
|
// / \ / \
|
|
// a b b c
|
|
|
|
// where Links is a possible root and a,b, and c are all optional.
|
|
// We will consider each combination of optional children individually and handle the case of the root when we set T's parsib pointer and the backpointer to T.
|
|
|
|
// First remember if we are the root and if not also remember our back ref via our parent.
|
|
if (TriIsRoot(Links)) {
|
|
IsRoot = TRUE;
|
|
} else {
|
|
IsRoot = FALSE;
|
|
ParentChildRef = TriAddressOfBackRefViaParent(Links);
|
|
SavedParSibRef = Links->Refs.ParSib;
|
|
}
|
|
|
|
// Now we set LeftChild, a, b, and c, and then later check for the different combinations.
|
|
// In the diagrams only those links that need to change are shown in the after part.
|
|
LeftChild = TriLeftChild(Links);
|
|
a = TriLeftChild(LeftChild);
|
|
b = TriRightChild(LeftChild);
|
|
c = TriRightChild(Links);
|
|
if ((a != NULL) && (b != NULL) && (c != NULL)) {
|
|
// Handle the following case
|
|
|
|
// Links LeftChild
|
|
// / \ ==> \
|
|
// LeftChild c a ----- Links
|
|
// / \ /
|
|
// a b b - c
|
|
a->Refs.ParSib = MakeIntoSiblingRef(Links);
|
|
b->Refs.ParSib = MakeIntoSiblingRef(c);
|
|
Links->Refs.Child = MakeIntoLeftChildRef(b);
|
|
Links->Refs.ParSib = MakeIntoParentRef(LeftChild);
|
|
} else if ((a != NULL) && (b != NULL) && (c == NULL)) {
|
|
// Handle the following case
|
|
|
|
// Links LeftChild
|
|
// / ==> \
|
|
// LeftChild a ----- Links
|
|
// / \ /
|
|
// a b b --
|
|
a->Refs.ParSib = MakeIntoSiblingRef(Links);
|
|
b->Refs.ParSib = MakeIntoParentRef(Links);
|
|
Links->Refs.Child = MakeIntoLeftChildRef(b);
|
|
Links->Refs.ParSib = MakeIntoParentRef(LeftChild);
|
|
} else if ((a != NULL) && (b == NULL) && (c != NULL)) {
|
|
// Handle the following case
|
|
|
|
// Links LeftChild
|
|
// / \ ==> \
|
|
// LeftChild c a ----- Links
|
|
// / /
|
|
// a c
|
|
a->Refs.ParSib = MakeIntoSiblingRef(Links);
|
|
Links->Refs.Child = MakeIntoRightChildRef(c);
|
|
Links->Refs.ParSib = MakeIntoParentRef(LeftChild);
|
|
} else if ((a != NULL) && (b == NULL) && (c == NULL)) {
|
|
// Handle the following case
|
|
|
|
// Links LeftChild
|
|
// / ==> \
|
|
// LeftChild a ----- Links
|
|
// / /
|
|
// a
|
|
a->Refs.ParSib = MakeIntoSiblingRef(Links);
|
|
Links->Refs.Child = 0L;
|
|
Links->Refs.ParSib = MakeIntoParentRef(LeftChild);
|
|
} else if ((a == NULL) && (b != NULL) && (c != NULL)) {
|
|
// Handle the following case
|
|
|
|
// Links LeftChild
|
|
// / \ ==> / \
|
|
// LeftChild c Links
|
|
// \ /
|
|
// b b - c
|
|
b->Refs.ParSib = MakeIntoSiblingRef(c);
|
|
Links->Refs.Child = MakeIntoLeftChildRef(b);
|
|
Links->Refs.ParSib = MakeIntoParentRef(LeftChild);
|
|
LeftChild->Refs.Child = MakeIntoRightChildRef(Links);
|
|
} else if ((a == NULL) && (b != NULL) && (c == NULL)) {
|
|
// Handle the following case
|
|
|
|
// Links LeftChild
|
|
// / ==> / \
|
|
// LeftChild Links
|
|
// \ /
|
|
// b b -
|
|
b->Refs.ParSib = MakeIntoParentRef(Links);
|
|
Links->Refs.Child = MakeIntoLeftChildRef(b);
|
|
Links->Refs.ParSib = MakeIntoParentRef(LeftChild);
|
|
LeftChild->Refs.Child = MakeIntoRightChildRef(Links);
|
|
} else if ((a == NULL) && (b == NULL) && (c != NULL)) {
|
|
// Handle the following case
|
|
|
|
// Links LeftChild
|
|
// / \ ==> / \
|
|
// LeftChild c Links
|
|
// /
|
|
// c
|
|
Links->Refs.Child = MakeIntoRightChildRef(c);
|
|
Links->Refs.ParSib = MakeIntoParentRef(LeftChild);
|
|
LeftChild->Refs.Child = MakeIntoRightChildRef(Links);
|
|
} else if ((a == NULL) && (b == NULL) && (c == NULL)) {
|
|
// Handle the following case
|
|
|
|
// Links LeftChild
|
|
// / ==> / \
|
|
// LeftChild Links
|
|
// /
|
|
Links->Refs.Child = 0L;
|
|
Links->Refs.ParSib = MakeIntoParentRef(LeftChild);
|
|
LeftChild->Refs.Child = MakeIntoRightChildRef(Links);
|
|
}
|
|
|
|
if (IsRoot) {
|
|
LeftChild->Refs.ParSib = MakeIntoParentRef(LeftChild);
|
|
} else {
|
|
LeftChild->Refs.ParSib = SavedParSibRef;
|
|
SetRefViaPointer(ParentChildRef, LeftChild);
|
|
}
|
|
}
|
|
|
|
|
|
VOID TriRotateLeft (IN PTRI_SPLAY_LINKS Links)
|
|
{
|
|
BOOLEAN IsRoot;
|
|
PULONG ParentChildRef;
|
|
ULONG SavedParSibRef;
|
|
PTRI_SPLAY_LINKS RightChild;
|
|
PTRI_SPLAY_LINKS a,b,c;
|
|
|
|
// We perform the following rotation
|
|
|
|
// -Links- -RightChild-
|
|
// / \ / \
|
|
// a RightChild ==> Links c
|
|
// / \ / \
|
|
// b c a b
|
|
|
|
// where Links is a possible root and a,b, and c are all optional.
|
|
// We will consider each combination of optional children individually and handle the case of the root when we set T's parsib pointer and the backpointer to T.
|
|
|
|
// First remember if we are the root and if not also remember our back ref via our parent.
|
|
if (TriIsRoot(Links)) {
|
|
IsRoot = TRUE;
|
|
} else {
|
|
IsRoot = FALSE;
|
|
ParentChildRef = TriAddressOfBackRefViaParent(Links);
|
|
SavedParSibRef = Links->Refs.ParSib;
|
|
}
|
|
|
|
// Now we set RightChild, a, b, and c, and then later check for the different combinations.
|
|
// In the diagrams only those links that need to change are shown in the after part.
|
|
RightChild = TriRightChild(Links);
|
|
a = TriLeftChild(Links);
|
|
b = TriLeftChild(RightChild);
|
|
c = TriRightChild(RightChild);
|
|
if ((a != NULL) && (b != NULL) && (c != NULL)) {
|
|
// Handle the following case
|
|
|
|
// Links RightChild
|
|
// / \ /
|
|
// a RightChild ==> Links ----- c
|
|
// / \ \
|
|
// b c a - b
|
|
a->Refs.ParSib = MakeIntoSiblingRef(b);
|
|
b->Refs.ParSib = MakeIntoParentRef(Links);
|
|
Links->Refs.ParSib = MakeIntoSiblingRef(c);
|
|
RightChild->Refs.Child = MakeIntoLeftChildRef(Links);
|
|
} else if ((a != NULL) && (b != NULL) && (c == NULL)) {
|
|
// Handle the following case
|
|
|
|
// Links RightChild
|
|
// / \ /
|
|
// a RightChild ==> Links -----
|
|
// / \
|
|
// b a - b
|
|
a->Refs.ParSib = MakeIntoSiblingRef(b);
|
|
b->Refs.ParSib = MakeIntoParentRef(Links);
|
|
Links->Refs.ParSib = MakeIntoParentRef(RightChild);
|
|
RightChild->Refs.Child = MakeIntoLeftChildRef(Links);
|
|
} else if ((a != NULL) && (b == NULL) && (c != NULL)) {
|
|
// Handle the following case
|
|
|
|
// Links RightChild
|
|
// / \ /
|
|
// a RightChild ==> Links ----- c
|
|
// \
|
|
// c a -
|
|
a->Refs.ParSib = MakeIntoParentRef(Links);
|
|
Links->Refs.ParSib = MakeIntoSiblingRef(c);
|
|
RightChild->Refs.Child = MakeIntoLeftChildRef(Links);
|
|
} else if ((a != NULL) && (b == NULL) && (c == NULL)) {
|
|
// Handle the following case
|
|
|
|
// Links RightChild
|
|
// / \ /
|
|
// a RightChild ==> Links -----
|
|
|
|
// a -
|
|
a->Refs.ParSib = MakeIntoParentRef(Links);
|
|
Links->Refs.ParSib = MakeIntoParentRef(RightChild);
|
|
RightChild->Refs.Child = MakeIntoLeftChildRef(Links);
|
|
} else if ((a == NULL) && (b != NULL) && (c != NULL)) {
|
|
// Handle the following case
|
|
|
|
// Links RightChild
|
|
// \ /
|
|
// RightChild ==> Links ----- c
|
|
// / \ / \
|
|
// b c b
|
|
b->Refs.ParSib = MakeIntoParentRef(Links);
|
|
Links->Refs.Child = MakeIntoRightChildRef(b);
|
|
Links->Refs.ParSib = MakeIntoSiblingRef(c);
|
|
RightChild->Refs.Child = MakeIntoLeftChildRef(Links);
|
|
} else if ((a == NULL) && (b != NULL) && (c == NULL)) {
|
|
// Handle the following case
|
|
|
|
// Links RightChild
|
|
// \ /
|
|
// RightChild ==> Links -----
|
|
// / / \
|
|
// b b
|
|
b->Refs.ParSib = MakeIntoParentRef(Links);
|
|
Links->Refs.Child = MakeIntoRightChildRef(b);
|
|
Links->Refs.ParSib = MakeIntoParentRef(RightChild);
|
|
RightChild->Refs.Child = MakeIntoLeftChildRef(Links);
|
|
} else if ((a == NULL) && (b == NULL) && (c != NULL)) {
|
|
// Handle the following case
|
|
|
|
// Links RightChild
|
|
// \ /
|
|
// RightChild ==> Links ----- c
|
|
// \ /
|
|
// c
|
|
Links->Refs.Child = 0L;
|
|
Links->Refs.ParSib = MakeIntoSiblingRef(c);
|
|
RightChild->Refs.Child = MakeIntoLeftChildRef(Links);
|
|
} else if ((a == NULL) && (b == NULL) && (c == NULL)) {
|
|
// Handle the following case
|
|
|
|
// Links RightChild
|
|
// \ /
|
|
// RightChild ==> Links -----
|
|
// /
|
|
|
|
Links->Refs.Child = 0L;
|
|
Links->Refs.ParSib = MakeIntoParentRef(RightChild);
|
|
RightChild->Refs.Child = MakeIntoLeftChildRef(Links);
|
|
}
|
|
|
|
if (IsRoot) {
|
|
RightChild->Refs.ParSib = MakeIntoParentRef(RightChild);
|
|
} else {
|
|
RightChild->Refs.ParSib = SavedParSibRef;
|
|
SetRefViaPointer(ParentChildRef, RightChild);
|
|
}
|
|
} |