test: triangle.h Source File

Main Page | Class Hierarchy | Class List | File List | Class Members | File Members

# triangle.h

Go to the documentation of this file.

    00001 //
    00002 //  Define the two pointer triangle splay links and the associated
    00003 //  manipuliation macros and routines.  Note that the tri_splay_links should
    00004 //  be an opaque type.  Routine are provided to traverse and manipulate the
    00005 //  structure.
    00006 //
    00007 //  The structure of a tri_splay_links record is really
    00008 //
    00009 //      typedef struct _TRI_SPLAY_LINKS {
    00010 //          ULONG ParSib; // struct _TRI_SPLAY_LINKS *ParSib;
    00011 //          ULONG Child;  // struct _TRI_SPLAY_LINKS *Child;
    00012 //      } TRI_SPLAY_LINKS;
    00013 //
    00014 //  However to aid in debugging (and without extra cost) we declare the
    00015 //  structure to be a union so we can also reference the links as pointers
    00016 //  in the debugger.
    00017 //
    00018
    00019 typedef union _TRI_SPLAY_LINKS {
    00020     struct {
    00021         ULONG ParSib;
    00022         ULONG Child;
    00023     } Refs;
    00024     struct {
    00025         union _TRI_SPLAY_LINKS *ParSibPtr;
    00026         union _TRI_SPLAY_LINKS *ChildPtr;
    00027     } Ptrs;
    00028 } TRI_SPLAY_LINKS;
    00029 typedef TRI_SPLAY_LINKS *PTRI_SPLAY_LINKS;
    00030
    00031 //
    00032 //  The macro procedure InitializeSplayLinks takes as input a pointer to
    00033 //  splay link and initializes its substructure.  All splay link nodes must
    00034 //  be initialized before they are used in the different splay routines and
    00035 //  macros.
    00036 //
    00037 // VOID
    00038 // TriInitializeSplayLinks (
    00039 //     IN PTRI_SPLAY_LINKS Links
    00040 //     );
    00041 //
    00042
    00043 #define TriInitializeSplayLinks(Links) { \
    00044     (Links)->Refs.ParSib = MakeIntoParentRef(Links); \
    00045     (Links)->Refs.Child = 0; \
    00046     }
    00047
    00048 //
    00049 //  The macro function Parent takes as input a pointer to a splay link in a
    00050 //  tree and returns a pointer to the splay link of the parent of the input
    00051 //  node.  If the input node is the root of the tree the return value is
    00052 //  equal to the input value.
    00053 //
    00054 // PTRI_SPLAY_LINKS
    00055 // TriParent (
    00056 //     IN PTRI_SPLAY_LINKS Links
    00057 //     );
    00058 //
    00059
    00060 #define TriParent(Links) ( \
    00061     (IsParentRef((Links)->Refs.ParSib)) ? \
    00062         MakeIntoPointer((Links)->Refs.ParSib) \
    00063     : \
    00064         MakeIntoPointer(MakeIntoPointer((Links)->Refs.ParSib)->Refs.ParSib) \
    00065     )
    00066
    00067 //
    00068 //  The macro function LeftChild takes as input a pointer to a splay link in
    00069 //  a tree and returns a pointer to the splay link of the left child of the
    00070 //  input node.  If the left child does not exist, the return value is NULL.
    00071 //
    00072 // PTRI_SPLAY_LINKS
    00073 // TriLeftChild (
    00074 //     IN PTRI_SPLAY_LINKS Links
    00075 //     );
    00076 //
    00077
    00078 #define TriLeftChild(Links) ( \
    00079     (IsLeftChildRef((Links)->Refs.Child)) ? \
    00080         MakeIntoPointer((Links)->Refs.Child) \
    00081     : \
    00082         0 \
    00083     )
    00084
    00085 //
    00086 //  The macro function RightChild takes as input a pointer to a splay link
    00087 //  in a tree and returns a pointer to the splay link of the right child of
    00088 //  the input node.  If the right child does not exist, the return value is
    00089 //  NULL.
    00090 //
    00091 // PTRI_SPLAY_LINKS
    00092 // TriRightChild (
    00093 //     IN PTRI_SPLAY_LINKS Links
    00094 //     );
    00095 //
    00096
    00097 #define TriRightChild(Links) ( \
    00098     (IsRightChildRef((Links)->Refs.Child)) ? \
    00099         MakeIntoPointer((Links)->Refs.Child) \
    00100     : ( \
    00101         (IsLeftChildRef((Links)->Refs.Child) && \
    00102          IsSiblingRef(MakeIntoPointer((Links)->Refs.Child)->Refs.ParSib)) ? \
    00103             MakeIntoPointer(MakeIntoPointer((Links)->Refs.Child)->Refs.ParSib) \
    00104         : \
    00105             0 \
    00106         ) \
    00107     )
    00108
    00109 //
    00110 //  The macro function IsRoot takes as input a pointer to a splay link
    00111 //  in a tree and returns TRUE if the input node is the root of the tree,
    00112 //  otherwise it returns FALSE.
    00113 //
    00114 // BOOLEAN
    00115 // TriIsRoot (
    00116 //     IN PTRI_SPLAY_LINKS Links
    00117 //     );
    00118 //
    00119
    00120 #define TriIsRoot(Links) ( \
    00121     (IsParentRef((Links)->Refs.ParSib) && MakeIntoPointer((Links)->Refs.ParSib) == (Links)) ? \
    00122         TRUE \
    00123     : \
    00124         FALSE \
    00125     )
    00126
    00127 //
    00128 //  The macro function IsLeftChild takes as input a pointer to a splay link
    00129 //  in a tree and returns TRUE if the input node is the left child of its
    00130 //  parent, otherwise it returns FALSE.  Note that if the input link is the
    00131 //  root node this function returns FALSE.
    00132 //
    00133 // BOOLEAN
    00134 // TriIsLeftChild (
    00135 //     IN PTRI_SPLAY_LINKS Links
    00136 //     );
    00137 //
    00138
    00139 #define TriIsLeftChild(Links) ( \
    00140     (TriLeftChild(TriParent(Links)) == (Links)) ? \
    00141         TRUE \
    00142     : \
    00143         FALSE \
    00144     )
    00145
    00146 //
    00147 //  The macro function IsRightChild takes as input a pointer to a splay link
    00148 //  in a tree and returns TRUE if the input node is the right child of its
    00149 //  parent, otherwise it returns FALSE.  Note that if the input link is the
    00150 //  root node this function returns FALSE.
    00151 //
    00152 // BOOLEAN
    00153 // TriIsRightChild (
    00154 //     IN PTRI_SPLAY_LINKS Links
    00155 //     );
    00156 //
    00157
    00158 #define TriIsRightChild(Links) ( \
    00159     (TriRightChild(TriParent(Links)) == (Links)) ? \
    00160         TRUE \
    00161     : \
    00162         FALSE \
    00163     )
    00164
    00165 //
    00166 //  The macro procedure InsertAsLeftChild takes as input a pointer to a splay
    00167 //  link in a tree and a pointer to a node not in a tree.  It inserts the
    00168 //  second node as the left child of the first node.  The first node must not
    00169 //  already have a left child, and the second node must not already have a
    00170 //  parent.
    00171 //
    00172 // VOID
    00173 // TriInsertAsLeftChild (
    00174 //     IN PTRI_SPLAY_LINKS ParentLinks,
    00175 //     IN PTRI_SPLAY_LINKS ChildLinks
    00176 //     );
    00177 //
    00178
    00179 #define TriInsertAsLeftChild(ParentLinks,ChildLinks) { \
    00180     PTRI_SPLAY_LINKS RightChild; \
    00181     if ((ParentLinks)->Refs.Child == 0) { \
    00182         (ParentLinks)->Refs.Child = MakeIntoLeftChildRef(ChildLinks); \
    00183         (ChildLinks)->Refs.ParSib = MakeIntoParentRef(ParentLinks); \
    00184     } else { \
    00185         RightChild = TriRightChild(ParentLinks); \
    00186         (ParentLinks)->Refs.Child = MakeIntoLeftChildRef(ChildLinks); \
    00187         (ChildLinks)->Refs.ParSib = MakeIntoSiblingRef(RightChild); \
    00188     } \
    00189 }
    00190
    00191 //
    00192 //  The macro procedure InsertAsRightChild takes as input a pointer to a splay
    00193 //  link in a tree and a pointer to a node not in a tree.  It inserts the
    00194 //  second node as the right child of the first node.  The first node must not
    00195 //  already have a right child, and the second node must not already have a
    00196 //  parent.
    00197 //
    00198 // VOID
    00199 // TriInsertAsRightChild (
    00200 //     IN PTRI_SPLAY_LINKS ParentLinks,
    00201 //     IN PTRI_SPLAY_LINKS ChildLinks
    00202 //     );
    00203 //
    00204
    00205 #define TriInsertAsRightChild(ParentLinks,ChildLinks) { \
    00206     PTRI_SPLAY_LINKS LeftChild; \
    00207     if ((ParentLinks)->Refs.Child == 0) { \
    00208         (ParentLinks)->Refs.Child = MakeIntoRightChildRef(ChildLinks); \
    00209         (ChildLinks)->Refs.ParSib = MakeIntoParentRef(ParentLinks); \
    00210     } else { \
    00211         LeftChild = TriLeftChild(ParentLinks); \
    00212         LeftChild->Refs.ParSib = MakeIntoSiblingRef(ChildLinks); \
    00213         (ChildLinks)->Refs.ParSib = MakeIntoParentRef(ParentLinks); \
    00214     } \
    00215 }
    00216
    00217 //
    00218 //  The Splay function takes as input a pointer to a splay link in a tree
    00219 //  and splays the tree.  Its function return value is a pointer to the
    00220 //  root of the splayed tree.
    00221 //
    00222
    00223 PTRI_SPLAY_LINKS
    00224 TriSplay (
    00225     IN PTRI_SPLAY_LINKS Links
    00226     );
    00227
    00228 //
    00229 //  The Delete function takes as input a pointer to a splay link in a tree
    00230 //  and deletes that node from the tree.  Its function return value is a
    00231 //  pointer to the root of the tree.  If the tree is now empty, the return
    00232 //  value is NULL.
    00233 //
    00234
    00235 PTRI_SPLAY_LINKS
    00236 TriDelete (
    00237     IN PTRI_SPLAY_LINKS Links
    00238     );
    00239
    00240 //
    00241 //  The SubtreeSuccessor function takes as input a pointer to a splay link
    00242 //  in a tree and returns a pointer to the successor of the input node of
    00243 //  the substree rooted at the input node.  If there is not a successor, the
    00244 //  return value is NULL.
    00245 //
    00246
    00247 PTRI_SPLAY_LINKS
    00248 TriSubtreeSuccessor (
    00249     IN PTRI_SPLAY_LINKS Links
    00250     );
    00251
    00252 //
    00253 //  The SubtreePredecessor function takes as input a pointer to a splay link
    00254 //  in a tree and returns a pointer to the predecessor of the input node of
    00255 //  the substree rooted at the input node.  If there is not a predecessor,
    00256 //  the return value is NULL.
    00257 //
    00258
    00259 PTRI_SPLAY_LINKS
    00260 TriSubtreePredecessor (
    00261     IN PTRI_SPLAY_LINKS Links
    00262     );
    00263
    00264 //
    00265 //  The RealSuccessor function takes as input a pointer to a splay link
    00266 //  in a tree and returns a pointer to the successor of the input node within
    00267 //  the entire tree.  If there is not a successor, the return value is NULL.
    00268 //
    00269
    00270 PTRI_SPLAY_LINKS
    00271 TriRealSuccessor (
    00272     IN PTRI_SPLAY_LINKS Links
    00273     );
    00274
    00275 //
    00276 //  The RealPredecessor function takes as input a pointer to a splay link
    00277 //  in a tree and returns a pointer to the predecessor of the input node
    00278 //  within the entire tree.  If there is not a predecessor, the return value
    00279 //  is NULL.
    00280 //
    00281
    00282 PTRI_SPLAY_LINKS
    00283 TriRealPredecessor (
    00284     IN PTRI_SPLAY_LINKS Links
    00285     );
    00286
    00287
    00288 //
    00289 //  The remainder of this module really belong in triangle.c  None of
    00290 //  the macros or routines are (logically) exported for use by the programmer
    00291 //  however they need to appear in this module to allow the earlier macros
    00292 //  to function properly.
    00293 //
    00294 //  In the splay record (declared earlier) the low order bit of the
    00295 //  ParSib field indicates whether the link is to a Parent or a Sibling, and
    00296 //  the low order bit of the Child field is used to indicate if the link
    00297 //  is to a left child or a right child.  The values are:
    00298 //
    00299 //      A parent field has the lower bit set to 0
    00300 //      A sibling field has the lower bit set to 1
    00301 //      A left child field has the lower bit set to 0
    00302 //      A right child field has the lower bit set to 1
    00303 //
    00304 //  The comments and code in triangle.c use the term "Ref" to indicate a
    00305 //  ParSib field or a Child field with the low order bit to indicate its type.
    00306 //  A ref cannot be directly used as a pointer.  The following macros help
    00307 //  in deciding the type of a ref and making refs from pointers.  There is
    00308 //  also a macro (MakeIntoPointer) that takes a ref and returns a pointer.
    00309 //
    00310
    00311 #define IsParentRef(Ulong)           (((((ULONG)Ulong) & 1) == 0) && ((Ulong) != 0) ? TRUE : FALSE)
    00312 #define MakeIntoParentRef(Ulong)     (((ULONG)Ulong) & 0xfffffffc)
    00313
    00314 #define IsSiblingRef(Ulong)          ((((ULONG)Ulong) & 1) == 1 ? TRUE : FALSE)
    00315 #define MakeIntoSiblingRef(Ulong)    (((ULONG)Ulong) | 1)
    00316
    00317 #define IsLeftChildRef(Ulong)        (((((ULONG)Ulong) & 1) == 0) && ((Ulong) != 0) ? TRUE : FALSE)
    00318 #define MakeIntoLeftChildRef(Ulong)  (((ULONG)Ulong) & 0xfffffffc)
    00319
    00320 #define IsRightChildRef(Ulong)       ((((ULONG)Ulong) & 1) == 1 ? TRUE : FALSE)
    00321 #define MakeIntoRightChildRef(Ulong) (((ULONG)Ulong) | 1)
    00322
    00323 #define MakeIntoPointer(Ulong)       ((PTRI_SPLAY_LINKS)((Ulong) & 0xfffffffc))
    00324
    00325