326 lines
9.8 KiB
C
326 lines
9.8 KiB
C
|
||
// Define the two pointer triangle splay links and the associated
|
||
// manipuliation macros and routines. Note that the tri_splay_links should
|
||
// be an opaque type. Routine are provided to traverse and manipulate the
|
||
// structure.
|
||
|
||
// The structure of a tri_splay_links record is really
|
||
|
||
// typedef struct _TRI_SPLAY_LINKS {
|
||
// ULONG ParSib; // struct _TRI_SPLAY_LINKS *ParSib;
|
||
// ULONG Child; // struct _TRI_SPLAY_LINKS *Child;
|
||
// } TRI_SPLAY_LINKS;
|
||
|
||
// However to aid in debugging (and without extra cost) we declare the
|
||
// structure to be a union so we can also reference the links as pointers
|
||
// in the debugger.
|
||
|
||
|
||
typedef union _TRI_SPLAY_LINKS {
|
||
struct {
|
||
ULONG ParSib;
|
||
ULONG Child;
|
||
} Refs;
|
||
struct {
|
||
union _TRI_SPLAY_LINKS *ParSibPtr;
|
||
union _TRI_SPLAY_LINKS *ChildPtr;
|
||
} Ptrs;
|
||
} TRI_SPLAY_LINKS;
|
||
typedef TRI_SPLAY_LINKS *PTRI_SPLAY_LINKS;
|
||
|
||
|
||
// The macro procedure InitializeSplayLinks takes as input a pointer to
|
||
// splay link and initializes its substructure. All splay link nodes must
|
||
// be initialized before they are used in the different splay routines and
|
||
// macros.
|
||
|
||
// VOID
|
||
// TriInitializeSplayLinks (
|
||
// IN PTRI_SPLAY_LINKS Links
|
||
// );
|
||
|
||
|
||
#define TriInitializeSplayLinks(Links) { \
|
||
(Links)->Refs.ParSib = MakeIntoParentRef(Links); \
|
||
(Links)->Refs.Child = 0; \
|
||
}
|
||
|
||
|
||
// The macro function Parent takes as input a pointer to a splay link in a
|
||
// tree and returns a pointer to the splay link of the parent of the input
|
||
// node. If the input node is the root of the tree the return value is
|
||
// equal to the input value.
|
||
|
||
// PTRI_SPLAY_LINKS
|
||
// TriParent (
|
||
// IN PTRI_SPLAY_LINKS Links
|
||
// );
|
||
|
||
|
||
#define TriParent(Links) ( \
|
||
(IsParentRef((Links)->Refs.ParSib)) ? \
|
||
MakeIntoPointer((Links)->Refs.ParSib) \
|
||
: \
|
||
MakeIntoPointer(MakeIntoPointer((Links)->Refs.ParSib)->Refs.ParSib) \
|
||
)
|
||
|
||
|
||
// The macro function LeftChild takes as input a pointer to a splay link in
|
||
// a tree and returns a pointer to the splay link of the left child of the
|
||
// input node. If the left child does not exist, the return value is NULL.
|
||
|
||
// PTRI_SPLAY_LINKS
|
||
// TriLeftChild (
|
||
// IN PTRI_SPLAY_LINKS Links
|
||
// );
|
||
|
||
|
||
#define TriLeftChild(Links) ( \
|
||
(IsLeftChildRef((Links)->Refs.Child)) ? \
|
||
MakeIntoPointer((Links)->Refs.Child) \
|
||
: \
|
||
0 \
|
||
)
|
||
|
||
|
||
// The macro function RightChild takes as input a pointer to a splay link
|
||
// in a tree and returns a pointer to the splay link of the right child of
|
||
// the input node. If the right child does not exist, the return value is
|
||
// NULL.
|
||
|
||
// PTRI_SPLAY_LINKS
|
||
// TriRightChild (
|
||
// IN PTRI_SPLAY_LINKS Links
|
||
// );
|
||
|
||
|
||
#define TriRightChild(Links) ( \
|
||
(IsRightChildRef((Links)->Refs.Child)) ? \
|
||
MakeIntoPointer((Links)->Refs.Child) \
|
||
: ( \
|
||
(IsLeftChildRef((Links)->Refs.Child) && \
|
||
IsSiblingRef(MakeIntoPointer((Links)->Refs.Child)->Refs.ParSib)) ? \
|
||
MakeIntoPointer(MakeIntoPointer((Links)->Refs.Child)->Refs.ParSib) \
|
||
: \
|
||
0 \
|
||
) \
|
||
)
|
||
|
||
|
||
// The macro function IsRoot takes as input a pointer to a splay link
|
||
// in a tree and returns TRUE if the input node is the root of the tree,
|
||
// otherwise it returns FALSE.
|
||
|
||
// BOOLEAN
|
||
// TriIsRoot (
|
||
// IN PTRI_SPLAY_LINKS Links
|
||
// );
|
||
|
||
|
||
#define TriIsRoot(Links) ( \
|
||
(IsParentRef((Links)->Refs.ParSib) && MakeIntoPointer((Links)->Refs.ParSib) == (Links)) ? \
|
||
TRUE \
|
||
: \
|
||
FALSE \
|
||
)
|
||
|
||
|
||
// The macro function IsLeftChild takes as input a pointer to a splay link
|
||
// in a tree and returns TRUE if the input node is the left child of its
|
||
// parent, otherwise it returns FALSE. Note that if the input link is the
|
||
// root node this function returns FALSE.
|
||
|
||
// BOOLEAN
|
||
// TriIsLeftChild (
|
||
// IN PTRI_SPLAY_LINKS Links
|
||
// );
|
||
|
||
|
||
#define TriIsLeftChild(Links) ( \
|
||
(TriLeftChild(TriParent(Links)) == (Links)) ? \
|
||
TRUE \
|
||
: \
|
||
FALSE \
|
||
)
|
||
|
||
|
||
// The macro function IsRightChild takes as input a pointer to a splay link
|
||
// in a tree and returns TRUE if the input node is the right child of its
|
||
// parent, otherwise it returns FALSE. Note that if the input link is the
|
||
// root node this function returns FALSE.
|
||
|
||
// BOOLEAN
|
||
// TriIsRightChild (
|
||
// IN PTRI_SPLAY_LINKS Links
|
||
// );
|
||
|
||
|
||
#define TriIsRightChild(Links) ( \
|
||
(TriRightChild(TriParent(Links)) == (Links)) ? \
|
||
TRUE \
|
||
: \
|
||
FALSE \
|
||
)
|
||
|
||
|
||
// The macro procedure InsertAsLeftChild takes as input a pointer to a splay
|
||
// link in a tree and a pointer to a node not in a tree. It inserts the
|
||
// second node as the left child of the first node. The first node must not
|
||
// already have a left child, and the second node must not already have a
|
||
// parent.
|
||
|
||
// VOID
|
||
// TriInsertAsLeftChild (
|
||
// IN PTRI_SPLAY_LINKS ParentLinks,
|
||
// IN PTRI_SPLAY_LINKS ChildLinks
|
||
// );
|
||
|
||
|
||
#define TriInsertAsLeftChild(ParentLinks,ChildLinks) { \
|
||
PTRI_SPLAY_LINKS RightChild; \
|
||
if ((ParentLinks)->Refs.Child == 0) { \
|
||
(ParentLinks)->Refs.Child = MakeIntoLeftChildRef(ChildLinks); \
|
||
(ChildLinks)->Refs.ParSib = MakeIntoParentRef(ParentLinks); \
|
||
} else { \
|
||
RightChild = TriRightChild(ParentLinks); \
|
||
(ParentLinks)->Refs.Child = MakeIntoLeftChildRef(ChildLinks); \
|
||
(ChildLinks)->Refs.ParSib = MakeIntoSiblingRef(RightChild); \
|
||
} \
|
||
}
|
||
|
||
|
||
// The macro procedure InsertAsRightChild takes as input a pointer to a splay
|
||
// link in a tree and a pointer to a node not in a tree. It inserts the
|
||
// second node as the right child of the first node. The first node must not
|
||
// already have a right child, and the second node must not already have a
|
||
// parent.
|
||
|
||
// VOID
|
||
// TriInsertAsRightChild (
|
||
// IN PTRI_SPLAY_LINKS ParentLinks,
|
||
// IN PTRI_SPLAY_LINKS ChildLinks
|
||
// );
|
||
|
||
|
||
#define TriInsertAsRightChild(ParentLinks,ChildLinks) { \
|
||
PTRI_SPLAY_LINKS LeftChild; \
|
||
if ((ParentLinks)->Refs.Child == 0) { \
|
||
(ParentLinks)->Refs.Child = MakeIntoRightChildRef(ChildLinks); \
|
||
(ChildLinks)->Refs.ParSib = MakeIntoParentRef(ParentLinks); \
|
||
} else { \
|
||
LeftChild = TriLeftChild(ParentLinks); \
|
||
LeftChild->Refs.ParSib = MakeIntoSiblingRef(ChildLinks); \
|
||
(ChildLinks)->Refs.ParSib = MakeIntoParentRef(ParentLinks); \
|
||
} \
|
||
}
|
||
|
||
|
||
// The 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.
|
||
|
||
|
||
PTRI_SPLAY_LINKS
|
||
TriSplay (
|
||
IN PTRI_SPLAY_LINKS Links
|
||
);
|
||
|
||
|
||
// The 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 of the tree. If the tree is now empty, the return
|
||
// value is NULL.
|
||
|
||
|
||
PTRI_SPLAY_LINKS
|
||
TriDelete (
|
||
IN PTRI_SPLAY_LINKS Links
|
||
);
|
||
|
||
|
||
// The 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 substree rooted at the input node. If there is not a successor, the
|
||
// return value is NULL.
|
||
|
||
|
||
PTRI_SPLAY_LINKS
|
||
TriSubtreeSuccessor (
|
||
IN PTRI_SPLAY_LINKS Links
|
||
);
|
||
|
||
|
||
// The 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 substree rooted at the input node. If there is not a predecessor,
|
||
// the return value is NULL.
|
||
|
||
|
||
PTRI_SPLAY_LINKS
|
||
TriSubtreePredecessor (
|
||
IN PTRI_SPLAY_LINKS Links
|
||
);
|
||
|
||
|
||
// The RealSuccessor 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 tree. If there is not a successor, the return value is NULL.
|
||
|
||
|
||
PTRI_SPLAY_LINKS
|
||
TriRealSuccessor (
|
||
IN PTRI_SPLAY_LINKS Links
|
||
);
|
||
|
||
|
||
// The 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.
|
||
|
||
|
||
PTRI_SPLAY_LINKS
|
||
TriRealPredecessor (
|
||
IN PTRI_SPLAY_LINKS Links
|
||
);
|
||
|
||
|
||
|
||
// The remainder of this module really belong in triangle.c None of
|
||
// the macros or routines are (logically) exported for use by the programmer
|
||
// however they need to appear in this module to allow the earlier macros
|
||
// to function properly.
|
||
|
||
// In the splay record (declared earlier) the low order bit of the
|
||
// ParSib field indicates whether the link is to a Parent or a Sibling, and
|
||
// the low order bit of the Child field is used to indicate if the link
|
||
// is to a left child or a right child. The values are:
|
||
|
||
// A parent field has the lower bit set to 0
|
||
// A sibling field has the lower bit set to 1
|
||
// A left child field has the lower bit set to 0
|
||
// A right child field has the lower bit set to 1
|
||
|
||
// The comments and code in triangle.c use the term "Ref" to indicate a
|
||
// ParSib field or a Child field with the low order bit to indicate its type.
|
||
// A ref cannot be directly used as a pointer. The following macros help
|
||
// in deciding the type of a ref and making refs from pointers. There is
|
||
// also a macro (MakeIntoPointer) that takes a ref and returns a pointer.
|
||
|
||
|
||
#define IsParentRef(Ulong) (((((ULONG)Ulong) & 1) == 0) && ((Ulong) != 0) ? TRUE : FALSE)
|
||
#define MakeIntoParentRef(Ulong) (((ULONG)Ulong) & 0xfffffffc)
|
||
|
||
#define IsSiblingRef(Ulong) ((((ULONG)Ulong) & 1) == 1 ? TRUE : FALSE)
|
||
#define MakeIntoSiblingRef(Ulong) (((ULONG)Ulong) | 1)
|
||
|
||
#define IsLeftChildRef(Ulong) (((((ULONG)Ulong) & 1) == 0) && ((Ulong) != 0) ? TRUE : FALSE)
|
||
#define MakeIntoLeftChildRef(Ulong) (((ULONG)Ulong) & 0xfffffffc)
|
||
|
||
#define IsRightChildRef(Ulong) ((((ULONG)Ulong) & 1) == 1 ? TRUE : FALSE)
|
||
#define MakeIntoRightChildRef(Ulong) (((ULONG)Ulong) | 1)
|
||
|
||
#define MakeIntoPointer(Ulong) ((PTRI_SPLAY_LINKS)((Ulong) & 0xfffffffc))
|
||
|
||
|