diff options
author | Adam <you@example.com> | 2020-05-17 05:51:50 +0200 |
---|---|---|
committer | Adam <you@example.com> | 2020-05-17 05:51:50 +0200 |
commit | e611b132f9b8abe35b362e5870b74bce94a1e58e (patch) | |
tree | a5781d2ec0e085eeca33cf350cf878f2efea6fe5 /private/ntos/rtl/triangle.c | |
download | NT4.0-e611b132f9b8abe35b362e5870b74bce94a1e58e.tar NT4.0-e611b132f9b8abe35b362e5870b74bce94a1e58e.tar.gz NT4.0-e611b132f9b8abe35b362e5870b74bce94a1e58e.tar.bz2 NT4.0-e611b132f9b8abe35b362e5870b74bce94a1e58e.tar.lz NT4.0-e611b132f9b8abe35b362e5870b74bce94a1e58e.tar.xz NT4.0-e611b132f9b8abe35b362e5870b74bce94a1e58e.tar.zst NT4.0-e611b132f9b8abe35b362e5870b74bce94a1e58e.zip |
Diffstat (limited to 'private/ntos/rtl/triangle.c')
-rw-r--r-- | private/ntos/rtl/triangle.c | 1420 |
1 files changed, 1420 insertions, 0 deletions
diff --git a/private/ntos/rtl/triangle.c b/private/ntos/rtl/triangle.c new file mode 100644 index 000000000..185d26d5e --- /dev/null +++ b/private/ntos/rtl/triangle.c @@ -0,0 +1,1420 @@ +/*++ + +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 + +Revision History: + +--*/ + +#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); + } + +} |