test: triangle.c File Reference

{ \ if (Ref != NULL) { \ (*(Ref)) = (((ULONG)(Ulong)) & 0xfffffffc) | ((ULONG)(*(Ref)) & 0x00000003); \ } \ }

{ \ PVOID _SWAP_POINTER_TEMP; \ _SWAP_POINTER_TEMP = (PVOID)(Ptr1); \ (Ptr1) = (Ptr2); \ (Ptr2) = _SWAP_POINTER_TEMP; \ }

{ \ ULONG _SWAP_ULONG_TEMP; \ _SWAP_ULONG_TEMP = (ULONG)(Ref1); \ (Ref1) = ((Ref2) & 0xfffffffc) | ((Ref1) & 0x00000003); \ (Ref2) = (_SWAP_ULONG_TEMP & 0xfffffffc) | ((Ref2) & 0x00000003); \ }

{ \ ULONG _SWAP_POINTER_TEMP; \ _SWAP_POINTER_TEMP = (ULONG)(Ptr1); \ (Ptr1) = (Ptr2); \ (Ptr2) = _SWAP_POINTER_TEMP; \ }

00757 { 00758 PTRI_SPLAY_LINKS Ptr; 00759 00760 // 00761 // Make Ptr be the same reference as found in our child field. 00762 // 00763 00764 Ptr = MakeIntoPointer(Links->Refs.Child); 00765 00766 // 00767 // If our child pointer is null then we don't have a back pointer 00768 // via our child so return NULL. 00769 // 00770 00771 if (Ptr == NULL) { 00772 return NULL; 00773 00774 // 00775 // if our child directly reference's us (then we only have one child) 00776 // return the address of the ParSib of our only child. 00777 // 00778 00779 } else if (MakeIntoPointer(Ptr->Refs.ParSib) == Links) { 00780 return &(Ptr->Refs.ParSib); 00781 00782 // 00783 // otherwise we have two children so return the address of the ParSib 00784 // of the second child. 00785 // 00786 00787 } else { 00788 return &(MakeIntoPointer(Ptr->Refs.ParSib)->Refs.ParSib); 00789 00790 } 00791 00792 }

00721 { 00722 PTRI_SPLAY_LINKS Ptr; 00723 00724 // 00725 // If Links is the root then we do not have a back pointer via our parent 00726 // so return NULL 00727 // 00728 00729 if (TriIsRoot(Links)) { 00730 00731 return NULL; 00732 00733 } 00734 00735 // 00736 // We are not the root so find our parent and if our parent directly points 00737 // to us we return the address of our parent's reference to us. Otherwise 00738 // (we must be a right child with a sibling) so return the address of 00739 // our sibling's ParSib reference to us. 00740 // 00741 00742 Ptr = TriParent(Links); 00743 if (MakeIntoPointer(Ptr->Refs.Child) == Links) { 00744 return &(Ptr->Refs.Child); 00745 } else { 00746 return &(MakeIntoPointer(Ptr->Refs.Child)->Refs.ParSib); 00747 } 00748 00749 }

00279 : 00280 00281 This Delete function takes as input a pointer to a splay link in a tree 00282 and deletes that node from the tree. Its function return value is a 00283 pointer to the root the tree. If the tree is now empty, the return 00284 value is NULL. 00285 00286 Arguments: 00287 00288 Links - Supplies the pointer to a splay link in a tree 00289 00290 Return Values: 00291 00292 PRTI_SPLAY_LINKS - Returns a pointer to the root of the splayed tree 00293 00294 --*/ 00295 00296 { 00297 PTRI_SPLAY_LINKS Predecessor; 00298 PTRI_SPLAY_LINKS Parent; 00299 PTRI_SPLAY_LINKS Child; 00300 00301 PULONG ParentChildRef; 00302 00303 // 00304 // First check to see if Links as two children. If it does then swap 00305 // Links with its subtree predecessor. Now we are guaranteed that Links 00306 // has at most one child. 00307 // 00308 00309 if ((TriLeftChild(Links) != NULL) && (TriRightChild(Links) != NULL)) { 00310 00311 // 00312 // get the predecessor, and swap their position in the tree 00313 // 00314 00315 Predecessor = TriSubtreePredecessor(Links); 00316 TriSwapSplayLinks(Predecessor, Links); 00317 00318 } 00319 00320 // 00321 // If Links has no children then delete links by checking if it is 00322 // already the root or has a parent. If it is the root then the 00323 // tree is now empty, otherwise set the appropriate parent's child 00324 // pointer, and possibly sibling, and splay the parent. 00325 // 00326 00327 if ((TriLeftChild(Links) == NULL) && (TriRightChild(Links) == NULL)) { 00328 00329 // 00330 // Links has no children, if it is the root then return NULL 00331 // 00332 00333 if (TriIsRoot(Links)) { 00334 00335 return NULL; 00336 00337 } 00338 00339 // 00340 // Links has no children, check to see if links is an only child 00341 // 00342 00343 Parent = TriParent(Links); 00344 if (MakeIntoPointer(Parent->Refs.Child) == Links && 00345 MakeIntoPointer(Links->Refs.ParSib) == Parent) { 00346 00347 // 00348 // Links has no children and is an only child. So simply make 00349 // our parent have no children and splay our parent. 00350 // 00351 // Parent Parent 00352 // | ==> 00353 // Links 00354 // 00355 00356 Parent->Refs.Child = 0; 00357 return TriSplay(Parent); 00358 00359 } else if (TriIsLeftChild(Links)) { 00360 00361 // 00362 // Links has no children and has a right sibling. So make the 00363 // parent's child Ref be the right sibling, splay the parent. 00364 // 00365 // Parent Parent 00366 // / \ ==> \ 00367 // Links Sibling Sibling 00368 // 00369 00370 Parent->Refs.Child = MakeIntoRightChildRef(Links->Refs.ParSib); 00371 return TriSplay(Parent); 00372 00373 } else { // TriIsRightChild(Links) 00374 00375 // 00376 // Links has no children and has a left sibling. So make link's 00377 // back via its parent into a parent ref of link's parent, and 00378 // splay the parent. 00379 // 00380 // Parent Parent 00381 // / \ / 00382 // Sibling Links ==> Sibling 00383 // 00384 00385 ParentChildRef = TriAddressOfBackRefViaParent(Links); 00386 *ParentChildRef = MakeIntoParentRef(Parent); 00387 return TriSplay(Parent); 00388 00389 } 00390 00391 } 00392 00393 // 00394 // otherwise Links has one child. If it is the root then make the child 00395 // the new root, otherwise link together the child and parent, and splay 00396 // the parent. But first remember who our child is. 00397 // 00398 00399 if (TriLeftChild(Links) != NULL) { 00400 Child = TriLeftChild(Links); 00401 } else { 00402 Child = TriRightChild(Links); 00403 } 00404 00405 // 00406 // If links is the root then we make the child the root and return the 00407 // child. 00408 // 00409 00410 if (TriIsRoot(Links)) { 00411 Child->Refs.ParSib = MakeIntoParentRef(Child); 00412 return Child; 00413 } 00414 00415 // 00416 // Links is not the root, so set links's back ref via its parent to be 00417 // links's child and the set the child's ParSib to be link's ParSib, and 00418 // splay the parent. This will handle the case where link is an only 00419 // or has a sibling on either side. 00420 // 00421 00422 Parent = TriParent(Links); 00423 ParentChildRef = TriAddressOfBackRefViaParent(Links); 00424 SetRefViaPointer(ParentChildRef, Child); 00425 Child->Refs.ParSib = Links->Refs.ParSib; 00426 00427 return TriSplay(Parent); 00428 00429 }

00642 : 00643 00644 This RealPredecessor function takes as input a pointer to a splay link in 00645 a tree and returns a pointer to the predecessor of the input node within 00646 the entire tree. If there is not a predecessor, the return value is NULL. 00647 00648 Arguments: 00649 00650 Links - Supplies the pointer to a splay link in a tree 00651 00652 Return Values: 00653 00654 PRTI_SPLAY_LINKS - Returns a pointer to the predecessor in the entire tree 00655 00656 --*/ 00657 00658 { 00659 PTRI_SPLAY_LINKS Ptr; 00660 00661 // 00662 // first check to see if there is a left subtree to the input link 00663 // if there is then the real predecessor is the right most node in 00664 // the left subtree. That is find and return P in the following diagram 00665 // 00666 // Links 00667 // / 00668 // . 00669 // . 00670 // . 00671 // P 00672 // / 00673 // 00674 00675 if ((Ptr = TriLeftChild(Links)) != NULL) { 00676 00677 while (TriRightChild(Ptr) != NULL) { 00678 Ptr = TriRightChild(Ptr); 00679 } 00680 00681 return Ptr; 00682 00683 } 00684 00685 // 00686 // we do not have a left child so check to see if have a parent and if 00687 // so find the first ancestor that we are a right decendent of. That 00688 // is find and return P in the following diagram 00689 // 00690 // P 00691 // \ 00692 // . 00693 // . 00694 // . 00695 // Links 00696 // 00697 00698 Ptr = Links; 00699 while (TriIsLeftChild(Ptr)) { 00700 Ptr = TriParent(Ptr); 00701 } 00702 00703 if (!TriIsLeftChild(Ptr) && !TriIsRoot(Ptr)) { // (TriIsRightChild(Ptr)) { 00704 return TriParent(Ptr); 00705 } 00706 00707 // 00708 // Otherwise we do not have a real predecessor so we simply return NULL 00709 // 00710 00711 return NULL; 00712 00713 }

00560 : 00561 00562 This RealSuccess function takes as input a pointer to a splay link in a 00563 tree and returns a pointer to the successor of the input node within the 00564 entire tire. If there is not a successor, the return value is NULL. 00565 00566 Arguments: 00567 00568 Links - Supplies the pointer to a splay link in a tree 00569 00570 Return Values: 00571 00572 PRTI_SPLAY_LINKS - Returns a pointer to the successor in the entire tree 00573 00574 --*/ 00575 00576 { 00577 PTRI_SPLAY_LINKS Ptr; 00578 00579 // 00580 // first check to see if there is a right subtree to the input link 00581 // if there is then the real successor is the left most node in 00582 // the right subtree. That is find and return P in the following diagram 00583 // 00584 // Links 00585 // \ 00586 // . 00587 // . 00588 // . 00589 // / 00590 // P 00591 // \ 00592 // 00593 00594 if ((Ptr = TriRightChild(Links)) != NULL) { 00595 00596 while (TriLeftChild(Ptr) != NULL) { 00597 Ptr = TriLeftChild(Ptr); 00598 } 00599 00600 return Ptr; 00601 00602 } 00603 00604 // 00605 // we do not have a right child so check to see if have a parent and if 00606 // so find the first ancestor that we are a left decendent of. That 00607 // is find and return P in the following diagram 00608 // 00609 // P 00610 // / 00611 // . 00612 // . 00613 // . 00614 // Links 00615 // 00616 00617 Ptr = Links; 00618 while (!TriIsLeftChild(Ptr) && !TriIsRoot(Ptr)) { // (TriIsRightChild(Ptr)) { 00619 Ptr = TriParent(Ptr); 00620 } 00621 00622 if (TriIsLeftChild(Ptr)) { 00623 return TriParent(Ptr); 00624 } 00625 00626 // 00627 // Otherwise we do not have a real successor so we simply return NULL 00628 // 00629 00630 return NULL; 00631 00632 }

01233 { 01234 BOOLEAN IsRoot; 01235 PULONG ParentChildRef; 01236 ULONG SavedParSibRef; 01237 PTRI_SPLAY_LINKS RightChild; 01238 PTRI_SPLAY_LINKS a,b,c; 01239 01240 // 01241 // We perform the following rotation 01242 // 01243 // -Links- -RightChild- 01244 // / \ / \ 01245 // a RightChild ==> Links c 01246 // / \ / \ 01247 // b c a b 01248 // 01249 // where Links is a possible root and a,b, and c are all optional. 01250 // We will consider each combination of optional children individually 01251 // and handle the case of the root when we set T's parsib pointer and 01252 // the backpointer to T. 01253 // 01254 01255 // 01256 // First remember if we are the root and if not also remember our 01257 // back ref via our parent. 01258 // 01259 01260 if (TriIsRoot(Links)) { 01261 IsRoot = TRUE; 01262 } else { 01263 IsRoot = FALSE; 01264 ParentChildRef = TriAddressOfBackRefViaParent(Links); 01265 SavedParSibRef = Links->Refs.ParSib; 01266 } 01267 01268 // 01269 // Now we set RightChild, a, b, and c, and then later check for the 01270 // different combinations. In the diagrams only those links that 01271 // need to change are shown in the after part. 01272 // 01273 01274 RightChild = TriRightChild(Links); 01275 a = TriLeftChild(Links); 01276 b = TriLeftChild(RightChild); 01277 c = TriRightChild(RightChild); 01278 01279 if ((a != NULL) && (b != NULL) && (c != NULL)) { 01280 01281 // 01282 // Handle the following case 01283 // 01284 // Links RightChild 01285 // / \ / 01286 // a RightChild ==> Links ----- c 01287 // / \ \ 01288 // b c a - b 01289 // 01290 01291 a->Refs.ParSib = MakeIntoSiblingRef(b); 01292 b->Refs.ParSib = MakeIntoParentRef(Links); 01293 Links->Refs.ParSib = MakeIntoSiblingRef(c); 01294 RightChild->Refs.Child = MakeIntoLeftChildRef(Links); 01295 01296 } else if ((a != NULL) && (b != NULL) && (c == NULL)) { 01297 01298 // 01299 // Handle the following case 01300 // 01301 // Links RightChild 01302 // / \ / 01303 // a RightChild ==> Links ----- 01304 // / \ 01305 // b a - b 01306 // 01307 01308 a->Refs.ParSib = MakeIntoSiblingRef(b); 01309 b->Refs.ParSib = MakeIntoParentRef(Links); 01310 Links->Refs.ParSib = MakeIntoParentRef(RightChild); 01311 RightChild->Refs.Child = MakeIntoLeftChildRef(Links); 01312 01313 } else if ((a != NULL) && (b == NULL) && (c != NULL)) { 01314 01315 // 01316 // Handle the following case 01317 // 01318 // Links RightChild 01319 // / \ / 01320 // a RightChild ==> Links ----- c 01321 // \ 01322 // c a - 01323 // 01324 01325 a->Refs.ParSib = MakeIntoParentRef(Links); 01326 Links->Refs.ParSib = MakeIntoSiblingRef(c); 01327 RightChild->Refs.Child = MakeIntoLeftChildRef(Links); 01328 01329 } else if ((a != NULL) && (b == NULL) && (c == NULL)) { 01330 01331 // 01332 // Handle the following case 01333 // 01334 // Links RightChild 01335 // / \ / 01336 // a RightChild ==> Links ----- 01337 // 01338 // a - 01339 // 01340 01341 a->Refs.ParSib = MakeIntoParentRef(Links); 01342 Links->Refs.ParSib = MakeIntoParentRef(RightChild); 01343 RightChild->Refs.Child = MakeIntoLeftChildRef(Links); 01344 01345 } else if ((a == NULL) && (b != NULL) && (c != NULL)) { 01346 01347 // 01348 // Handle the following case 01349 // 01350 // Links RightChild 01351 // \ / 01352 // RightChild ==> Links ----- c 01353 // / \ / \ 01354 // b c b 01355 // 01356 01357 b->Refs.ParSib = MakeIntoParentRef(Links); 01358 Links->Refs.Child = MakeIntoRightChildRef(b); 01359 Links->Refs.ParSib = MakeIntoSiblingRef(c); 01360 RightChild->Refs.Child = MakeIntoLeftChildRef(Links); 01361 01362 } else if ((a == NULL) && (b != NULL) && (c == NULL)) { 01363 01364 // 01365 // Handle the following case 01366 // 01367 // Links RightChild 01368 // \ / 01369 // RightChild ==> Links ----- 01370 // / / \ 01371 // b b 01372 // 01373 01374 b->Refs.ParSib = MakeIntoParentRef(Links); 01375 Links->Refs.Child = MakeIntoRightChildRef(b); 01376 Links->Refs.ParSib = MakeIntoParentRef(RightChild); 01377 RightChild->Refs.Child = MakeIntoLeftChildRef(Links); 01378 01379 } else if ((a == NULL) && (b == NULL) && (c != NULL)) { 01380 01381 // 01382 // Handle the following case 01383 // 01384 // Links RightChild 01385 // \ / 01386 // RightChild ==> Links ----- c 01387 // \ / 01388 // c 01389 // 01390 01391 Links->Refs.Child = 0L; 01392 Links->Refs.ParSib = MakeIntoSiblingRef(c); 01393 RightChild->Refs.Child = MakeIntoLeftChildRef(Links); 01394 01395 } else if ((a == NULL) && (b == NULL) && (c == NULL)) { 01396 01397 // 01398 // Handle the following case 01399 // 01400 // Links RightChild 01401 // \ / 01402 // RightChild ==> Links ----- 01403 // / 01404 // 01405 // 01406 01407 Links->Refs.Child = 0L; 01408 Links->Refs.ParSib = MakeIntoParentRef(RightChild); 01409 RightChild->Refs.Child = MakeIntoLeftChildRef(Links); 01410 01411 } 01412 01413 if (IsRoot) { 01414 RightChild->Refs.ParSib = MakeIntoParentRef(RightChild); 01415 } else { 01416 RightChild->Refs.ParSib = SavedParSibRef; 01417 SetRefViaPointer(ParentChildRef, RightChild); 01418 } 01419 01420 }

01039 { 01040 BOOLEAN IsRoot; 01041 PULONG ParentChildRef; 01042 ULONG SavedParSibRef; 01043 PTRI_SPLAY_LINKS LeftChild; 01044 PTRI_SPLAY_LINKS a,b,c; 01045 01046 // 01047 // We perform the following rotation 01048 // 01049 // -Links- -LeftChild- 01050 // / \ / \ 01051 // LeftChild c ==> a Links 01052 // / \ / \ 01053 // a b b c 01054 // 01055 // where Links is a possible root and a,b, and c are all optional. 01056 // We will consider each combination of optional children individually 01057 // and handle the case of the root when we set T's parsib pointer and 01058 // the backpointer to T. 01059 // 01060 01061 // 01062 // First remember if we are the root and if not also remember our 01063 // back ref via our parent. 01064 // 01065 01066 if (TriIsRoot(Links)) { 01067 IsRoot = TRUE; 01068 } else { 01069 IsRoot = FALSE; 01070 ParentChildRef = TriAddressOfBackRefViaParent(Links); 01071 SavedParSibRef = Links->Refs.ParSib; 01072 } 01073 01074 // 01075 // Now we set LeftChild, a, b, and c, and then later check for the 01076 // different combinations. In the diagrams only those links that 01077 // need to change are shown in the after part. 01078 // 01079 01080 LeftChild = TriLeftChild(Links); 01081 a = TriLeftChild(LeftChild); 01082 b = TriRightChild(LeftChild); 01083 c = TriRightChild(Links); 01084 01085 if ((a != NULL) && (b != NULL) && (c != NULL)) { 01086 01087 // 01088 // Handle the following case 01089 // 01090 // Links LeftChild 01091 // / \ ==> \ 01092 // LeftChild c a ----- Links 01093 // / \ / 01094 // a b b - c 01095 // 01096 01097 a->Refs.ParSib = MakeIntoSiblingRef(Links); 01098 b->Refs.ParSib = MakeIntoSiblingRef(c); 01099 Links->Refs.Child = MakeIntoLeftChildRef(b); 01100 Links->Refs.ParSib = MakeIntoParentRef(LeftChild); 01101 01102 } else if ((a != NULL) && (b != NULL) && (c == NULL)) { 01103 01104 // 01105 // Handle the following case 01106 // 01107 // Links LeftChild 01108 // / ==> \ 01109 // LeftChild a ----- Links 01110 // / \ / 01111 // a b b -- 01112 // 01113 01114 a->Refs.ParSib = MakeIntoSiblingRef(Links); 01115 b->Refs.ParSib = MakeIntoParentRef(Links); 01116 Links->Refs.Child = MakeIntoLeftChildRef(b); 01117 Links->Refs.ParSib = MakeIntoParentRef(LeftChild); 01118 01119 } else if ((a != NULL) && (b == NULL) && (c != NULL)) { 01120 01121 // 01122 // Handle the following case 01123 // 01124 // Links LeftChild 01125 // / \ ==> \ 01126 // LeftChild c a ----- Links 01127 // / / 01128 // a c 01129 // 01130 01131 a->Refs.ParSib = MakeIntoSiblingRef(Links); 01132 Links->Refs.Child = MakeIntoRightChildRef(c); 01133 Links->Refs.ParSib = MakeIntoParentRef(LeftChild); 01134 01135 } else if ((a != NULL) && (b == NULL) && (c == NULL)) { 01136 01137 // 01138 // Handle the following case 01139 // 01140 // Links LeftChild 01141 // / ==> \ 01142 // LeftChild a ----- Links 01143 // / / 01144 // a 01145 // 01146 01147 a->Refs.ParSib = MakeIntoSiblingRef(Links); 01148 Links->Refs.Child = 0L; 01149 Links->Refs.ParSib = MakeIntoParentRef(LeftChild); 01150 01151 } else if ((a == NULL) && (b != NULL) && (c != NULL)) { 01152 01153 // 01154 // Handle the following case 01155 // 01156 // Links LeftChild 01157 // / \ ==> / \ 01158 // LeftChild c Links 01159 // \ / 01160 // b b - c 01161 // 01162 01163 b->Refs.ParSib = MakeIntoSiblingRef(c); 01164 Links->Refs.Child = MakeIntoLeftChildRef(b); 01165 Links->Refs.ParSib = MakeIntoParentRef(LeftChild); 01166 LeftChild->Refs.Child = MakeIntoRightChildRef(Links); 01167 01168 } else if ((a == NULL) && (b != NULL) && (c == NULL)) { 01169 01170 // 01171 // Handle the following case 01172 // 01173 // Links LeftChild 01174 // / ==> / \ 01175 // LeftChild Links 01176 // \ / 01177 // b b - 01178 // 01179 01180 b->Refs.ParSib = MakeIntoParentRef(Links); 01181 Links->Refs.Child = MakeIntoLeftChildRef(b); 01182 Links->Refs.ParSib = MakeIntoParentRef(LeftChild); 01183 LeftChild->Refs.Child = MakeIntoRightChildRef(Links); 01184 01185 } else if ((a == NULL) && (b == NULL) && (c != NULL)) { 01186 01187 // 01188 // Handle the following case 01189 // 01190 // Links LeftChild 01191 // / \ ==> / \ 01192 // LeftChild c Links 01193 // / 01194 // c 01195 // 01196 01197 Links->Refs.Child = MakeIntoRightChildRef(c); 01198 Links->Refs.ParSib = MakeIntoParentRef(LeftChild); 01199 LeftChild->Refs.Child = MakeIntoRightChildRef(Links); 01200 01201 } else if ((a == NULL) && (b == NULL) && (c == NULL)) { 01202 01203 // 01204 // Handle the following case 01205 // 01206 // Links LeftChild 01207 // / ==> / \ 01208 // LeftChild Links 01209 // / 01210 // 01211 01212 Links->Refs.Child = 0L; 01213 Links->Refs.ParSib = MakeIntoParentRef(LeftChild); 01214 LeftChild->Refs.Child = MakeIntoRightChildRef(Links); 01215 01216 } 01217 01218 if (IsRoot) { 01219 LeftChild->Refs.ParSib = MakeIntoParentRef(LeftChild); 01220 } else { 01221 LeftChild->Refs.ParSib = SavedParSibRef; 01222 SetRefViaPointer(ParentChildRef, LeftChild); 01223 } 01224 01225 }

00119 : 00120 00121 This Splay function takes as input a pointer to a splay link in a tree 00122 and splays the tree. Its function return value is a pointer to the 00123 root of the splayed tree. 00124 00125 Arguments: 00126 00127 Links - Supplies the pointer to a splay link in a tree 00128 00129 Return Values: 00130 00131 PRTI_SPLAY_LINKS - Returns a pointer to the root of the splayed tree 00132 00133 --*/ 00134 00135 { 00136 PTRI_SPLAY_LINKS Parent; 00137 PTRI_SPLAY_LINKS GrandParent; 00138 00139 // 00140 // While Links is not the root we test and rotate until it is the root. 00141 // 00142 00143 while (!TriIsRoot(Links)) { 00144 00145 // 00146 // Get Parent and then check if we don't have a grandparent. 00147 // 00148 00149 Parent = TriParent(Links); 00150 00151 if (TriIsRoot(Parent)) { 00152 00153 // 00154 // No grandparent so check for single rotation 00155 // 00156 00157 if (TriIsLeftChild(Links)) { 00158 00159 // 00160 // do the following single rotation 00161 // 00162 // Parent Links 00163 // / ==> \ 00164 // Links Parent 00165 // 00166 00167 TriRotateRight(Parent); 00168 00169 } else { // TriIsRightChild(Links) 00170 00171 // 00172 // do the following single rotation 00173 // 00174 // 00175 // Parent Links 00176 // \ ==> / 00177 // Links Parent 00178 // 00179 00180 TriRotateLeft(Parent); 00181 00182 } 00183 00184 } else { // !TriIsRoot(Parent) 00185 00186 // 00187 // Get grandparent and check for the four double rotation 00188 // cases 00189 // 00190 00191 GrandParent = TriParent(Parent); 00192 00193 if (TriIsLeftChild(Links)) { 00194 00195 if (TriIsLeftChild(Parent)) { 00196 00197 // 00198 // do the following double rotation 00199 // 00200 // GP L 00201 // / \ 00202 // P ==> P 00203 // / \ 00204 // L GP 00205 // 00206 00207 TriRotateRight(GrandParent); 00208 TriRotateRight(Parent); 00209 00210 } else { // TriIsRightChild(Parent) 00211 00212 // 00213 // do the following double rotation 00214 // 00215 // GP L 00216 // \ / \ 00217 // P ==> GP P 00218 // / 00219 // L 00220 // 00221 00222 TriRotateRight(Parent); 00223 TriRotateLeft(GrandParent); 00224 00225 } 00226 00227 } else { // TriIsRightChild(Links); 00228 00229 if (TriIsLeftChild(Parent)) { 00230 00231 // 00232 // do the following double rotation 00233 // 00234 // GP L 00235 // / / \ 00236 // P ==> P GP 00237 // \ 00238 // L 00239 // 00240 00241 TriRotateLeft(Parent); 00242 TriRotateRight(GrandParent); 00243 00244 } else { // TriIsRightChild(Parent) 00245 00246 // 00247 // do the following double rotation 00248 // 00249 // GP L 00250 // \ / 00251 // P ==> P 00252 // \ / 00253 // L GP 00254 // 00255 00256 TriRotateLeft(GrandParent); 00257 TriRotateLeft(Parent); 00258 00259 } 00260 00261 } 00262 00263 } 00264 00265 } 00266 00267 return Links; 00268 00269 }

00500 : 00501 00502 This SubTreePredecessor function takes as input a pointer to a splay link 00503 in a tree and returns a pointer to the predecessor of the input node of 00504 the subtree rooted at the input node. If there is not a predecessor, 00505 the return value is NULL. 00506 00507 Arguments: 00508 00509 Links - Supplies the pointer to a splay link in a tree 00510 00511 Return Values: 00512 00513 PRTI_SPLAY_LINKS - Returns a pointer to the predecessor in the subtree 00514 00515 --*/ 00516 00517 { 00518 PTRI_SPLAY_LINKS Ptr; 00519 00520 // 00521 // check to see if there is a left subtree to the input link 00522 // if there is then the subtree predecessor is the right most node in 00523 // the left subtree. That is find and return P in the following diagram 00524 // 00525 // Links 00526 // / 00527 // . 00528 // . 00529 // . 00530 // P 00531 // / 00532 // 00533 00534 if ((Ptr = TriLeftChild(Links)) != NULL) { 00535 00536 while (TriRightChild(Ptr) != NULL) { 00537 Ptr = TriRightChild(Ptr); 00538 } 00539 00540 return Ptr; 00541 00542 } 00543 00544 // 00545 // Otherwise we do not have a subtree predecessor so we simply return NULL 00546 // 00547 00548 return NULL; 00549 00550 }

00439 : 00440 00441 This SubTreeSuccessor function takes as input a pointer to a splay link 00442 in a tree and returns a pointer to the successor of the input node of 00443 the subtree rooted at the input node. If there is not a successor, the 00444 return value is NULL. 00445 00446 Arguments: 00447 00448 Links - Supplies the pointer to a splay link in a tree 00449 00450 Return Values: 00451 00452 PRTI_SPLAY_LINKS - Returns a pointer to the successor in the subtree 00453 00454 --*/ 00455 00456 { 00457 PTRI_SPLAY_LINKS Ptr; 00458 00459 // 00460 // check to see if there is a right subtree to the input link 00461 // if there is then the subtree successor is the left most node in 00462 // the right subtree. That is find and return P in the following diagram 00463 // 00464 // Links 00465 // \ 00466 // . 00467 // . 00468 // . 00469 // / 00470 // P 00471 // \ 00472 // 00473 00474 if ((Ptr = TriRightChild(Links)) != NULL) { 00475 00476 while (TriLeftChild(Ptr) != NULL) { 00477 Ptr = TriLeftChild(Ptr); 00478 } 00479 00480 return Ptr; 00481 00482 } 00483 00484 // 00485 // Otherwise we do not have a subtree successor so we simply return NULL 00486 // 00487 00488 return NULL; 00489 00490 }

00801 { 00802 PULONG Parent1ChildRef; 00803 PULONG Parent2ChildRef; 00804 00805 PULONG Child1ParSibRef; 00806 PULONG Child2ParSibRef; 00807 00808 // 00809 // We have the following situation 00810 // 00811 // 00812 // Parent1 Parent2 00813 // | | 00814 // | | 00815 // Link1 Link2 00816 // / \ / \ 00817 // / \ / \ 00818 // LC1 RC1 LC2 RC2 00819 // 00820 // where one of the links can possibly be the root and one of the links 00821 // can possibly be a direct child of the other, or can be connected 00822 // via their sibling pointers. Without loss of generality we'll make 00823 // link2 be the possible and root and link1 be the possible child, or 00824 // link2 have a parsib pointer to link1 00825 // 00826 00827 if ((TriIsRoot(Link1)) || 00828 (TriParent(Link2) == Link1) || 00829 (MakeIntoPointer(Link1->Refs.ParSib) == Link2)) { 00830 00831 SwapPointers(Link1, Link2); 00832 00833 } 00834 00835 // 00836 // The cases we need to handle are 00837 // 00838 // 1. Link1 is not a child of link2, link2 is not the root, and they are not siblings 00839 // 2. Link1 is not a child of link2, link2 is not the root, and they are siblings 00840 // 00841 // 3. Link1 is not a child of link2, link2 is the root 00842 // 00843 // 4. Link1 is an only child of link2, and link2 is not the root 00844 // 5. Link1 is an only child of link2, and link2 is the root 00845 // 00846 // 6. Link1 is a left child of link2 (has a sibling), and link2 is not the root 00847 // 7. Link1 is a left child of link2 (has a sibling), and link2 is the root 00848 // 00849 // 8. Link1 is a right child of link2 (has a sibling), and link2 is not the root 00850 // 9. Link1 is a right child of link2 (has a sibling), and link2 is the root 00851 // 00852 // Each case will be handled separately 00853 // 00854 00855 if (TriParent(Link1) != Link2) { 00856 00857 if (!TriIsRoot(Link2)) { 00858 00859 if (MakeIntoPointer(Link2->Refs.ParSib) != Link1) { 00860 00861 // 00862 // Case 1 - Link1 is not a child of link2, 00863 // Link2 is not the root, and 00864 // they are not siblings 00865 // 00866 00867 Parent1ChildRef = TriAddressOfBackRefViaParent(Link1); 00868 Child1ParSibRef = TriAddressOfBackRefViaChild(Link1); 00869 Parent2ChildRef = TriAddressOfBackRefViaParent(Link2); 00870 Child2ParSibRef = TriAddressOfBackRefViaChild(Link2); 00871 SwapUlongs(Link1->Refs.Child, Link2->Refs.Child); 00872 SwapUlongs(Link1->Refs.ParSib, Link2->Refs.ParSib); 00873 SetRefViaPointer(Parent1ChildRef, Link2); 00874 SetRefViaPointer(Parent2ChildRef, Link1); 00875 SetRefViaPointer(Child1ParSibRef, Link2); 00876 SetRefViaPointer(Child2ParSibRef, Link1); 00877 00878 } else { 00879 00880 // 00881 // Case 2 - Link1 is not a child of link2, 00882 // Link2 is not the root, and 00883 // they are siblings 00884 // 00885 00886 Child1ParSibRef = TriAddressOfBackRefViaChild(Link1); 00887 Parent2ChildRef = TriAddressOfBackRefViaParent(Link2); 00888 Child2ParSibRef = TriAddressOfBackRefViaChild(Link2); 00889 SwapUlongs(Link1->Refs.Child, Link2->Refs.Child); 00890 SetRefViaPointer(Child1ParSibRef, Link2); 00891 SetRefViaPointer(Child2ParSibRef, Link1); 00892 *Parent2ChildRef = MakeIntoLeftChildRef(Link1); 00893 Link2->Refs.ParSib = Link1->Refs.ParSib; 00894 Link1->Refs.ParSib = MakeIntoSiblingRef(Link2); 00895 00896 } 00897 00898 } else { 00899 00900 // 00901 // Case 3 - Link1 is not a child of link2, and 00902 // Link2 is the root 00903 // 00904 00905 Parent1ChildRef = TriAddressOfBackRefViaParent(Link1); 00906 Child1ParSibRef = TriAddressOfBackRefViaChild(Link1); 00907 Child2ParSibRef = TriAddressOfBackRefViaChild(Link2); 00908 SwapUlongs(Link1->Refs.Child, Link2->Refs.Child); 00909 Link2->Refs.ParSib = Link1->Refs.ParSib; 00910 Link1->Refs.ParSib = MakeIntoParentRef(Link1); 00911 SetRefViaPointer(Child1ParSibRef, Link2); 00912 SetRefViaPointer(Child2ParSibRef, Link1); 00913 SetRefViaPointer(Parent1ChildRef, Link2); 00914 00915 } 00916 00917 } else { // TriParent(Link1) == Link2 00918 00919 if (MakeIntoPointer(Link2->Refs.Child) == Link1 && 00920 MakeIntoPointer(Link1->Refs.ParSib) == Link2) { // Link1 is an only child 00921 00922 if (!TriIsRoot(Link2)) { 00923 00924 // 00925 // Case 4 - Link1 is an only child of link2, and 00926 // Link2 is not the root 00927 // 00928 00929 Child1ParSibRef = TriAddressOfBackRefViaChild(Link1); 00930 Parent2ChildRef = TriAddressOfBackRefViaParent(Link2); 00931 SetRefViaPointer(Child1ParSibRef, Link2); 00932 SetRefViaPointer(Parent2ChildRef, Link1); 00933 Link1->Refs.ParSib = Link2->Refs.ParSib; 00934 Link2->Refs.ParSib = MakeIntoParentRef(Link1); 00935 SwapRefsButKeepFlags(Link1->Refs.Child, Link2->Refs.Child); 00936 SetRefViaPointer(&Link1->Refs.Child, Link2); 00937 00938 } else { 00939 00940 // 00941 // Case 5 - Link1 is an only child of link2, and 00942 // Link2 is the root 00943 // 00944 00945 Child1ParSibRef = TriAddressOfBackRefViaChild(Link1); 00946 SetRefViaPointer(Child1ParSibRef, Link2); 00947 Link1->Refs.ParSib = MakeIntoParentRef(Link1); 00948 Link2->Refs.ParSib = MakeIntoParentRef(Link1); 00949 SwapRefsButKeepFlags(Link1->Refs.Child, Link2->Refs.Child); 00950 SetRefViaPointer(&Link1->Refs.Child, Link2); 00951 00952 } 00953 00954 } else if (TriIsLeftChild(Link1)) { // and link1 has a sibling 00955 00956 if (!TriIsRoot(Link2)) { 00957 00958 // 00959 // Case 6 - Link1 is a left child of link2 (has a sibling), and 00960 // Link2 is not the root 00961 // 00962 00963 Child1ParSibRef = TriAddressOfBackRefViaChild(Link1); 00964 Parent2ChildRef = TriAddressOfBackRefViaParent(Link2); 00965 Child2ParSibRef = TriAddressOfBackRefViaChild(Link2); 00966 SetRefViaPointer(Child1ParSibRef, Link2); 00967 SetRefViaPointer(Parent2ChildRef, Link1); 00968 SetRefViaPointer(Child2ParSibRef, Link1); 00969 Link2->Refs.Child = Link1->Refs.Child; 00970 Link1->Refs.Child = MakeIntoLeftChildRef(Link2); 00971 SwapUlongs(Link1->Refs.ParSib, Link2->Refs.ParSib); 00972 00973 } else { 00974 00975 // 00976 // Case 7 - Link1 is a left child of link2 (has a sibling), and 00977 // Link2 is the root 00978 // 00979 00980 Child1ParSibRef = TriAddressOfBackRefViaChild(Link1); 00981 Child2ParSibRef = TriAddressOfBackRefViaChild(Link2); 00982 SetRefViaPointer(Child1ParSibRef, Link2); 00983 SetRefViaPointer(Child2ParSibRef, Link1); 00984 Link2->Refs.Child = Link1->Refs.Child; 00985 Link1->Refs.Child = MakeIntoLeftChildRef(Link2); 00986 Link2->Refs.ParSib = Link1->Refs.ParSib; 00987 Link1->Refs.ParSib = MakeIntoParentRef(Link1); 00988 00989 } 00990 00991 } else { // TriIsRightChild(Link1) and Link1 has a sibling 00992 00993 if (!TriIsRoot(Link2)) { 00994 00995 // 00996 // Case 8 - Link1 is a right child of link2 (has a sibling), and 00997 // Link2 is not the root 00998 // 00999 01000 Parent1ChildRef = TriAddressOfBackRefViaParent(Link1); 01001 Child1ParSibRef = TriAddressOfBackRefViaChild(Link1); 01002 Parent2ChildRef = TriAddressOfBackRefViaParent(Link2); 01003 SetRefViaPointer(Parent1ChildRef, Link2); 01004 SetRefViaPointer(Child1ParSibRef, Link2); 01005 SetRefViaPointer(Parent2ChildRef, Link1); 01006 SwapUlongs(Link1->Refs.Child, Link2->Refs.Child); 01007 Link1->Refs.ParSib = Link2->Refs.ParSib; 01008 Link2->Refs.ParSib = MakeIntoParentRef(Link1); 01009 01010 } else { 01011 01012 // 01013 // Case 9 - Link1 is a right child of link2 (has a sibling), and 01014 // Link2 is the root 01015 // 01016 01017 Parent1ChildRef = TriAddressOfBackRefViaParent(Link1); 01018 Child1ParSibRef = TriAddressOfBackRefViaChild(Link1); 01019 SetRefViaPointer(Parent1ChildRef, Link2); 01020 SetRefViaPointer(Child1ParSibRef, Link2); 01021 SwapUlongs(Link1->Refs.Child, Link2->Refs.Child); 01022 Link1->Refs.ParSib = MakeIntoParentRef(Link1); 01023 Link1->Refs.ParSib = MakeIntoParentRef(Link1); 01024 01025 } 01026 01027 } 01028 01029 } 01030 01031 }


Defines
#define	SwapPointers(Ptr1, Ptr2)
#define	SwapUlongs(Ptr1, Ptr2)
#define	SwapRefsButKeepFlags(Ref1, Ref2)
#define	SetRefViaPointer(Ref, Ulong)
Functions
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)
PTRI_SPLAY_LINKS	TriDelete (IN PTRI_SPLAY_LINKS Links)
PTRI_SPLAY_LINKS	TriSubtreeSuccessor (IN PTRI_SPLAY_LINKS Links)
PTRI_SPLAY_LINKS	TriSubtreePredecessor (IN PTRI_SPLAY_LINKS Links)
PTRI_SPLAY_LINKS	TriRealSuccessor (IN PTRI_SPLAY_LINKS Links)
PTRI_SPLAY_LINKS	TriRealPredecessor (IN PTRI_SPLAY_LINKS Links)

triangle.c File Reference

Defines

Functions

Define Documentation

Function Documentation