test: splay.c File Reference

( \ RtlIsLeftChild(Links) ? \ &(((Links)->Parent)->LeftChild) \ : \ &(((Links)->Parent)->RightChild) \ )

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

00391 : 00392 00393 The Delete function takes as input a pointer to a splay link in a tree 00394 and deletes that node from the tree. Its function return value is a 00395 pointer to the root of the tree. If the tree is now empty, the return 00396 value is NULL. 00397 00398 Arguments: 00399 00400 Links - Supplies a pointer to a splay link in a tree. 00401 00402 Return Value: 00403 00404 PRTL_SPLAY_LINKS - returns a pointer to the root of the tree. 00405 00406 --*/ 00407 00408 { 00409 PRTL_SPLAY_LINKS Predecessor; 00410 PRTL_SPLAY_LINKS Parent; 00411 PRTL_SPLAY_LINKS Child; 00412 00413 PRTL_SPLAY_LINKS *ParentChildPtr; 00414 00415 // 00416 // First check to see if Links as two children. If it does then swap 00417 // Links with its subtree predecessor. Now we are guaranteed that Links 00418 // has at most one child. 00419 // 00420 00421 if ((RtlLeftChild(Links) != NULL) && (RtlRightChild(Links) != NULL)) { 00422 00423 // 00424 // get the predecessor, and swap their position in the tree 00425 // 00426 00427 Predecessor = RtlSubtreePredecessor(Links); 00428 SwapSplayLinks(Predecessor, Links); 00429 00430 } 00431 00432 // 00433 // If Links has no children then delete links by checking if it is 00434 // already the root or has a parent. If it is the root then the 00435 // tree is now empty, otherwise it set the appropriate parent's child 00436 // pointer (i.e., the one to links) to NULL, and splay the parent. 00437 // 00438 00439 if ((RtlLeftChild(Links) == NULL) && (RtlRightChild(Links) == NULL)) { 00440 00441 // 00442 // Links has no children, if it is the root then return NULL 00443 // 00444 00445 if (RtlIsRoot(Links)) { 00446 00447 return NULL; 00448 } 00449 00450 // 00451 // Links as not children and is not the root, so to the parent's 00452 // child pointer to NULL and splay the parent. 00453 // 00454 00455 Parent = RtlParent(Links); 00456 00457 ParentChildPtr = ParentsChildPointerAddress(Links); 00458 *ParentChildPtr = NULL; 00459 00460 return RtlSplay(Parent); 00461 00462 } 00463 00464 // 00465 // otherwise Links has one child. If it is the root then make the child 00466 // the new root, otherwise link together the child and parent, and splay 00467 // the parent. But first remember who our child is. 00468 // 00469 00470 if (RtlLeftChild(Links) != NULL) { 00471 Child = RtlLeftChild(Links); 00472 } else { 00473 Child = RtlRightChild(Links); 00474 } 00475 00476 // 00477 // If links is the root then we make the child the root and return the 00478 // child. 00479 // 00480 00481 if (RtlIsRoot(Links)) { 00482 Child->Parent = Child; 00483 return Child; 00484 } 00485 00486 // 00487 // Links is not the root, so set link's parent child pointer to be 00488 // the child and the set child's parent to be link's parent, and splay 00489 // the parent. 00490 // 00491 00492 ParentChildPtr = ParentsChildPointerAddress(Links); 00493 *ParentChildPtr = Child; 00494 Child->Parent = Links->Parent; 00495 00496 return RtlSplay(RtlParent(Child)); 00497 00498 }

00509 : 00510 00511 The Delete function takes as input a pointer to a splay link in a tree, 00512 a pointer to the callers pointer to the tree and deletes that node from 00513 the tree. The caller's pointer is updated upon return. If the tree is 00514 now empty, the value is NULL. 00515 00516 Unfortunately, the original RtlDelete() always splays and this is not 00517 always a desireable side-effect. 00518 00519 Arguments: 00520 00521 Links - Supplies a pointer to a splay link in a tree. 00522 00523 Root - Pointer to the callers pointer to the root 00524 00525 Return Value: 00526 00527 None 00528 00529 --*/ 00530 00531 { 00532 PRTL_SPLAY_LINKS Predecessor; 00533 PRTL_SPLAY_LINKS Parent; 00534 PRTL_SPLAY_LINKS Child; 00535 00536 PRTL_SPLAY_LINKS *ParentChildPtr; 00537 00538 // 00539 // First check to see if Links as two children. If it does then swap 00540 // Links with its subtree predecessor. Now we are guaranteed that Links 00541 // has at most one child. 00542 // 00543 00544 if ((RtlLeftChild(Links) != NULL) && (RtlRightChild(Links) != NULL)) { 00545 00546 // 00547 // get the predecessor, and swap their position in the tree 00548 // 00549 00550 Predecessor = RtlSubtreePredecessor(Links); 00551 00552 if (RtlIsRoot(Links)) { 00553 00554 // 00555 // If we're switching with the root of the tree, fix the 00556 // caller's root pointer 00557 // 00558 00559 *Root = Predecessor; 00560 } 00561 00562 SwapSplayLinks(Predecessor, Links); 00563 00564 } 00565 00566 // 00567 // If Links has no children then delete links by checking if it is 00568 // already the root or has a parent. If it is the root then the 00569 // tree is now empty, otherwise it set the appropriate parent's child 00570 // pointer (i.e., the one to links) to NULL. 00571 // 00572 00573 if ((RtlLeftChild(Links) == NULL) && (RtlRightChild(Links) == NULL)) { 00574 00575 // 00576 // Links has no children, if it is the root then set root to NULL 00577 // 00578 00579 if (RtlIsRoot(Links)) { 00580 00581 *Root = NULL; 00582 00583 return; 00584 } 00585 00586 // 00587 // Links as not children and is not the root, so to the parent's 00588 // child pointer to NULL. 00589 // 00590 00591 ParentChildPtr = ParentsChildPointerAddress(Links); 00592 *ParentChildPtr = NULL; 00593 00594 return; 00595 } 00596 00597 // 00598 // otherwise Links has one child. If it is the root then make the child 00599 // the new root, otherwise link together the child and parent. But first 00600 // remember who our child is. 00601 // 00602 00603 if (RtlLeftChild(Links) != NULL) { 00604 Child = RtlLeftChild(Links); 00605 } else { 00606 Child = RtlRightChild(Links); 00607 } 00608 00609 // 00610 // If links is the root then we make the child the root and return the 00611 // child. 00612 // 00613 00614 if (RtlIsRoot(Links)) { 00615 Child->Parent = Child; 00616 00617 *Root = Child; 00618 00619 return; 00620 } 00621 00622 // 00623 // Links is not the root, so set link's parent child pointer to be 00624 // the child and the set child's parent to be link's parent. 00625 // 00626 00627 ParentChildPtr = ParentsChildPointerAddress(Links); 00628 *ParentChildPtr = Child; 00629 Child->Parent = Links->Parent; 00630 00631 return; 00632 }

00848 : 00849 00850 The RealPredecessor function takes as input a pointer to a splay link 00851 in a tree and returns a pointer to the predecessor of the input node 00852 within the entire tree. If there is not a predecessor, the return value 00853 is NULL. 00854 00855 Arguments: 00856 00857 Links - Supplies a pointer to a splay link in a tree. 00858 00859 Return Value: 00860 00861 PRTL_SPLAY_LINKS - returns a pointer to the predecessor in the entire tree 00862 00863 --*/ 00864 00865 { 00866 PRTL_SPLAY_LINKS Ptr; 00867 00868 /* 00869 first check to see if there is a left subtree to the input link 00870 if there is then the real predecessor is the right most node in 00871 the left subtree. That is find and return P in the following diagram 00872 00873 Links 00874 / 00875 . 00876 . 00877 . 00878 P 00879 / 00880 */ 00881 00882 if ((Ptr = RtlLeftChild(Links)) != NULL) { 00883 00884 while (RtlRightChild(Ptr) != NULL) { 00885 Ptr = RtlRightChild(Ptr); 00886 } 00887 00888 return Ptr; 00889 00890 } 00891 00892 /* 00893 we do not have a left child so check to see if have a parent and if 00894 so find the first ancestor that we are a right decendent of. That 00895 is find and return P in the following diagram 00896 00897 P 00898 \ 00899 . 00900 . 00901 . 00902 Links 00903 */ 00904 00905 Ptr = Links; 00906 while (RtlIsLeftChild(Ptr)) { 00907 Ptr = RtlParent(Ptr); 00908 } 00909 00910 if (RtlIsRightChild(Ptr)) { 00911 return RtlParent(Ptr); 00912 } 00913 00914 // 00915 // otherwise we are do not have a real predecessor so we simply return 00916 // NULL 00917 // 00918 00919 return NULL; 00920 00921 }

00765 : 00766 00767 The RealSuccessor function takes as input a pointer to a splay link 00768 in a tree and returns a pointer to the successor of the input node within 00769 the entire tree. If there is not a successor, the return value is NULL. 00770 00771 Arguments: 00772 00773 Links - Supplies a pointer to a splay link in a tree. 00774 00775 Return Value: 00776 00777 PRTL_SPLAY_LINKS - returns a pointer to the successor in the entire tree 00778 00779 --*/ 00780 00781 { 00782 PRTL_SPLAY_LINKS Ptr; 00783 00784 /* 00785 first check to see if there is a right subtree to the input link 00786 if there is then the real successor is the left most node in 00787 the right subtree. That is find and return P in the following diagram 00788 00789 Links 00790 \ 00791 . 00792 . 00793 . 00794 / 00795 P 00796 \ 00797 */ 00798 00799 if ((Ptr = RtlRightChild(Links)) != NULL) { 00800 00801 while (RtlLeftChild(Ptr) != NULL) { 00802 Ptr = RtlLeftChild(Ptr); 00803 } 00804 00805 return Ptr; 00806 00807 } 00808 00809 /* 00810 we do not have a right child so check to see if have a parent and if 00811 so find the first ancestor that we are a left decendent of. That 00812 is find and return P in the following diagram 00813 00814 P 00815 / 00816 . 00817 . 00818 . 00819 Links 00820 */ 00821 00822 Ptr = Links; 00823 while (RtlIsRightChild(Ptr)) { 00824 Ptr = RtlParent(Ptr); 00825 } 00826 00827 if (RtlIsLeftChild(Ptr)) { 00828 return RtlParent(Ptr); 00829 } 00830 00831 // 00832 // otherwise we are do not have a real successor so we simply return 00833 // NULL 00834 // 00835 00836 return NULL; 00837 00838 }

00057 : 00058 00059 The Splay function takes as input a pointer to a splay link in a tree 00060 and splays the tree. Its function return value is a pointer to the 00061 root of the splayed tree. 00062 00063 Arguments: 00064 00065 Links - Supplies a pointer to a splay link in a tree. 00066 00067 Return Value: 00068 00069 PRTL_SPLAY_LINKS - returns a pointer to the root of the splayed tree. 00070 00071 --*/ 00072 00073 { 00074 PRTL_SPLAY_LINKS L; 00075 PRTL_SPLAY_LINKS P; 00076 PRTL_SPLAY_LINKS G; 00077 00078 // 00079 // while links is not the root we need to keep rotating it toward 00080 // the root 00081 // 00082 00083 L = Links; 00084 00085 while (!RtlIsRoot(L)) { 00086 00087 P = RtlParent(L); 00088 G = RtlParent(P); 00089 00090 if (RtlIsLeftChild(L)) { 00091 00092 if (RtlIsRoot(P)) { 00093 00094 /* 00095 we have the following case 00096 00097 P L 00098 / \ / \ 00099 L c ==> a P 00100 / \ / \ 00101 a b b c 00102 */ 00103 00104 // 00105 // Connect P & b 00106 // 00107 00108 P->LeftChild = L->RightChild; 00109 if (P->LeftChild != NULL) {P->LeftChild->Parent = P;} 00110 00111 // 00112 // Connect L & P 00113 // 00114 00115 L->RightChild = P; 00116 P->Parent = L; 00117 00118 // 00119 // Make L the root 00120 // 00121 00122 L->Parent = L; 00123 00124 } else if (RtlIsLeftChild(P)) { 00125 00126 /* 00127 we have the following case 00128 00129 | | 00130 G L 00131 / \ / \ 00132 P d ==> a P 00133 / \ / \ 00134 L c b G 00135 / \ / \ 00136 a b c d 00137 */ 00138 00139 // 00140 // Connect P & b 00141 // 00142 00143 P->LeftChild = L->RightChild; 00144 if (P->LeftChild != NULL) {P->LeftChild->Parent = P;} 00145 00146 // 00147 // Connect G & c 00148 // 00149 00150 G->LeftChild = P->RightChild; 00151 if (G->LeftChild != NULL) {G->LeftChild->Parent = G;} 00152 00153 // 00154 // Connect L & Great GrandParent 00155 // 00156 00157 if (RtlIsRoot(G)) { 00158 L->Parent = L; 00159 } else { 00160 L->Parent = G->Parent; 00161 *(ParentsChildPointerAddress(G)) = L; 00162 } 00163 00164 // 00165 // Connect L & P 00166 // 00167 00168 L->RightChild = P; 00169 P->Parent = L; 00170 00171 // 00172 // Connect P & G 00173 // 00174 00175 P->RightChild = G; 00176 G->Parent = P; 00177 00178 } else { // RtlIsRightChild(Parent) 00179 00180 /* 00181 we have the following case 00182 00183 | | 00184 G L 00185 / \ / \ 00186 a P G P 00187 / \ / \ / \ 00188 L d ==> a b c d 00189 / \ 00190 b c 00191 */ 00192 00193 // 00194 // Connect G & b 00195 // 00196 00197 G->RightChild = L->LeftChild; 00198 if (G->RightChild != NULL) {G->RightChild->Parent = G;} 00199 00200 // 00201 // Connect P & c 00202 // 00203 00204 P->LeftChild = L->RightChild; 00205 if (P->LeftChild != NULL) {P->LeftChild->Parent = P;} 00206 00207 // 00208 // Connect L & Great GrandParent 00209 // 00210 00211 if (RtlIsRoot(G)) { 00212 L->Parent = L; 00213 } else { 00214 L->Parent = G->Parent; 00215 *(ParentsChildPointerAddress(G)) = L; 00216 } 00217 00218 // 00219 // Connect L & G 00220 // 00221 00222 L->LeftChild = G; 00223 G->Parent = L; 00224 00225 // 00226 // Connect L & P 00227 // 00228 00229 L->RightChild = P; 00230 P->Parent = L; 00231 00232 } 00233 00234 } else { // RtlIsRightChild(L) 00235 00236 if (RtlIsRoot(P)) { 00237 00238 /* 00239 we have the following case 00240 00241 P L 00242 / \ / \ 00243 a L P c 00244 / \ / \ 00245 b c ==> a b 00246 */ 00247 00248 // 00249 // Connect P & b 00250 // 00251 00252 P->RightChild = L->LeftChild; 00253 if (P->RightChild != NULL) {P->RightChild->Parent = P;} 00254 00255 // 00256 // Connect P & L 00257 // 00258 00259 L->LeftChild = P; 00260 P->Parent = L; 00261 00262 // 00263 // Make L the root 00264 // 00265 00266 L->Parent = L; 00267 00268 } else if (RtlIsRightChild(P)) { 00269 00270 /* 00271 we have the following case 00272 00273 | | 00274 G L 00275 / \ / \ 00276 a P P d 00277 / \ / \ 00278 b L G c 00279 / \ / \ 00280 c d ==> a b 00281 */ 00282 00283 // 00284 // Connect G & b 00285 // 00286 00287 G->RightChild = P->LeftChild; 00288 if (G->RightChild != NULL) {G->RightChild->Parent = G;} 00289 00290 // 00291 // Connect P & c 00292 // 00293 00294 P->RightChild = L->LeftChild; 00295 if (P->RightChild != NULL) {P->RightChild->Parent = P;} 00296 00297 // 00298 // Connect L & Great GrandParent 00299 // 00300 00301 if (RtlIsRoot(G)) { 00302 L->Parent = L; 00303 } else { 00304 L->Parent = G->Parent; 00305 *(ParentsChildPointerAddress(G)) = L; 00306 } 00307 00308 // 00309 // Connect L & P 00310 // 00311 00312 L->LeftChild = P; 00313 P->Parent = L; 00314 00315 // 00316 // Connect P & G 00317 // 00318 00319 P->LeftChild = G; 00320 G->Parent = P; 00321 00322 } else { // RtlIsLeftChild(P) 00323 00324 /* 00325 we have the following case 00326 00327 | | 00328 G L 00329 / \ / \ 00330 P d P G 00331 / \ / \ / \ 00332 a L ==> a b c d 00333 / \ 00334 b c 00335 */ 00336 00337 // 00338 // Connect P & b 00339 // 00340 00341 P->RightChild = L->LeftChild; 00342 if (P->RightChild != NULL) {P->RightChild->Parent = P;} 00343 00344 // 00345 // Connect G & c 00346 // 00347 00348 G->LeftChild = L->RightChild; 00349 if (G->LeftChild != NULL) {G->LeftChild->Parent = G;} 00350 00351 // 00352 // Connect L & Great GrandParent 00353 // 00354 00355 if (RtlIsRoot(G)) { 00356 L->Parent = L; 00357 } else { 00358 L->Parent = G->Parent; 00359 *(ParentsChildPointerAddress(G)) = L; 00360 } 00361 00362 // 00363 // Connect L & P 00364 // 00365 00366 L->LeftChild = P; 00367 P->Parent = L; 00368 00369 // 00370 // Connect L & G 00371 // 00372 00373 L->RightChild = G; 00374 G->Parent = L; 00375 00376 } 00377 } 00378 } 00379 00380 return L; 00381 }

00704 : 00705 00706 The SubtreePredecessor function takes as input a pointer to a splay link 00707 in a tree and returns a pointer to the predecessor of the input node of 00708 the substree rooted at the input node. If there is not a predecessor, 00709 the return value is NULL. 00710 00711 Arguments: 00712 00713 Links - Supplies a pointer to a splay link in a tree. 00714 00715 Return Value: 00716 00717 PRTL_SPLAY_LINKS - returns a pointer to the predecessor in the subtree 00718 00719 --*/ 00720 00721 { 00722 PRTL_SPLAY_LINKS Ptr; 00723 00724 // 00725 // check to see if there is a left subtree to the input link 00726 // if there is then the subtree predecessor is the right most node in 00727 // the left subtree. That is find and return P in the following diagram 00728 // 00729 // Links 00730 // / 00731 // . 00732 // . 00733 // . 00734 // P 00735 // / 00736 // 00737 00738 if ((Ptr = RtlLeftChild(Links)) != NULL) { 00739 00740 while (RtlRightChild(Ptr) != NULL) { 00741 Ptr = RtlRightChild(Ptr); 00742 } 00743 00744 return Ptr; 00745 00746 } 00747 00748 // 00749 // otherwise we are do not have a subtree predecessor so we simply return 00750 // NULL 00751 // 00752 00753 return NULL; 00754 00755 }

00642 : 00643 00644 The SubtreeSuccessor function takes as input a pointer to a splay link 00645 in a tree and returns a pointer to the successor of the input node of 00646 the substree rooted at the input node. If there is not a successor, the 00647 return value is NULL. 00648 00649 Arguments: 00650 00651 Links - Supplies a pointer to a splay link in a tree. 00652 00653 Return Value: 00654 00655 PRTL_SPLAY_LINKS - returns a pointer to the successor in the subtree 00656 00657 --*/ 00658 00659 { 00660 PRTL_SPLAY_LINKS Ptr; 00661 00662 /* 00663 check to see if there is a right subtree to the input link 00664 if there is then the subtree successor is the left most node in 00665 the right subtree. That is find and return P in the following diagram 00666 00667 Links 00668 \ 00669 . 00670 . 00671 . 00672 / 00673 P 00674 \ 00675 */ 00676 00677 if ((Ptr = RtlRightChild(Links)) != NULL) { 00678 00679 while (RtlLeftChild(Ptr) != NULL) { 00680 Ptr = RtlLeftChild(Ptr); 00681 } 00682 00683 return Ptr; 00684 00685 } 00686 00687 // 00688 // otherwise we are do not have a subtree successor so we simply return 00689 // NULL 00690 // 00691 00692 return NULL; 00693 00694 }

00930 { 00931 PRTL_SPLAY_LINKS *Parent1ChildPtr; 00932 PRTL_SPLAY_LINKS *Parent2ChildPtr; 00933 00934 /* 00935 We have the following situation 00936 00937 00938 Parent1 Parent2 00939 | | 00940 | | 00941 Link1 Link2 00942 / \ / \ 00943 / \ / \ 00944 LC1 RC1 LC2 RC2 00945 00946 where one of the links can possibly be the root and one of the links 00947 can possibly be a direct child of the other. Without loss of 00948 generality we'll make link2 be the possible and root and link1 be 00949 the possible child. 00950 */ 00951 00952 if ((RtlIsRoot(Link1)) || (RtlParent(Link2) == Link1)) { 00953 SwapPointers(Link1, Link2); 00954 } 00955 00956 // 00957 // The four cases we need to handle are 00958 // 00959 // 1. Link1 is not a child of link2 and link2 is not the root 00960 // 2. Link1 is not a child of link2 and link2 is the root 00961 // 3. Link1 is a child of link2 and link2 is not the root 00962 // 4. Link1 is a child of link2 and link2 is the root 00963 // 00964 // 00965 // Each case will be handled separately 00966 // 00967 00968 if (RtlParent(Link1) != Link2) { 00969 00970 if (!RtlIsRoot(Link2)) { 00971 00972 // 00973 // Case 1 the initial steps are: 00974 // 00975 // 1. get both parent child pointers 00976 // 2. swap the parent child pointers 00977 // 3. swap the parent pointers 00978 // 00979 00980 Parent1ChildPtr = ParentsChildPointerAddress(Link1); 00981 Parent2ChildPtr = ParentsChildPointerAddress(Link2); 00982 00983 SwapPointers(*Parent1ChildPtr, *Parent2ChildPtr); 00984 00985 SwapPointers(Link1->Parent, Link2->Parent); 00986 00987 } else { 00988 00989 // 00990 // Case 2 the initial steps are: 00991 // 00992 // 1. Set link1's parent child pointer to link2 00993 // 2. Set parent pointer of link2 to link1's parent 00994 // 3. Set parent pointer of link1 to be itself 00995 // 00996 00997 Parent1ChildPtr = ParentsChildPointerAddress(Link1); 00998 *Parent1ChildPtr = Link2; 00999 01000 Link2->Parent = Link1->Parent; 01001 01002 Link1->Parent = Link1; 01003 01004 } 01005 01006 // 01007 // Case 1 and 2 common steps are: 01008 // 01009 // 1. swap the child pointers 01010 // 01011 01012 SwapPointers(Link1->LeftChild, Link2->LeftChild); 01013 SwapPointers(Link1->RightChild, Link2->RightChild); 01014 01015 } else { // RtlParent(Link1) == Link2 01016 01017 if (!RtlIsRoot(Link2)) { 01018 01019 // 01020 // Case 3 the initial steps are: 01021 // 01022 // 1. Set Link2's parent child pointer to link1 01023 // 2. Set Link1's parent pointer to parent of link2 01024 // 01025 01026 Parent2ChildPtr = ParentsChildPointerAddress(Link2); 01027 *Parent2ChildPtr = Link1; 01028 01029 Link1->Parent = Link2->Parent; 01030 01031 } else { 01032 01033 // 01034 // Case 4 the initial steps are: 01035 // 01036 // 1. Set Link1's parent pointer to be link1 01037 // 01038 01039 Link1->Parent = Link1; 01040 01041 } 01042 01043 // 01044 // Case 3 and 4 common steps are: 01045 // 01046 // 1. Swap the child pointers 01047 // 2. if link1 was a left child (i.e., RtlLeftChild(Link1) == Link1) 01048 // then set left child of link1 to link2 01049 // else set right child of link1 to link2 01050 // 01051 01052 SwapPointers(Link1->LeftChild, Link2->LeftChild); 01053 SwapPointers(Link1->RightChild, Link2->RightChild); 01054 01055 if (Link1->LeftChild == Link1) { 01056 Link1->LeftChild = Link2; 01057 } else { 01058 Link1->RightChild = Link2; 01059 } 01060 01061 } 01062 01063 // 01064 // Case 1, 2, 3, 4 common (and final) steps are: 01065 // 01066 // 1. Fix the parent pointers of the left and right children 01067 // 01068 01069 if (Link1->LeftChild != NULL) {Link1->LeftChild->Parent = Link1;} 01070 if (Link1->RightChild != NULL) {Link1->RightChild->Parent = Link1;} 01071 if (Link2->LeftChild != NULL) {Link2->LeftChild->Parent = Link2;} 01072 if (Link2->RightChild != NULL) {Link2->RightChild->Parent = Link2;} 01073 01074 }


Defines
#define	SwapPointers(Ptr1, Ptr2)
#define	ParentsChildPointerAddress(Links)
Functions
VOID	SwapSplayLinks (IN PRTL_SPLAY_LINKS Link1, IN PRTL_SPLAY_LINKS Link2)
PRTL_SPLAY_LINKS	RtlSplay (IN PRTL_SPLAY_LINKS Links)
PRTL_SPLAY_LINKS	RtlDelete (IN PRTL_SPLAY_LINKS Links)
VOID	RtlDeleteNoSplay (IN PRTL_SPLAY_LINKS Links, IN OUT PRTL_SPLAY_LINKS *Root)
PRTL_SPLAY_LINKS	RtlSubtreeSuccessor (IN PRTL_SPLAY_LINKS Links)
PRTL_SPLAY_LINKS	RtlSubtreePredecessor (IN PRTL_SPLAY_LINKS Links)
PRTL_SPLAY_LINKS	RtlRealSuccessor (IN PRTL_SPLAY_LINKS Links)
PRTL_SPLAY_LINKS	RtlRealPredecessor (IN PRTL_SPLAY_LINKS Links)

splay.c File Reference

Defines

Functions

Define Documentation

Function Documentation