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);
+    }
+
+}