Something went wrong. Try again.
Reactos
Something went wrong. Try again.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797/* * COPYRIGHT: See COPYING in the top level directory * PROJECT: ReactOS system libraries * PURPOSE: Splay-Tree implementation * FILE: lib/rtl/splaytree.c * PROGRAMMER: Alex Ionescu (alex@relsoft.net) */
/* INCLUDES *****************************************************************/
#include <rtl.h>
#define NDEBUG#include <debug.h>
//#define VERIFY_SWAP_SPLAY_LINKS
/* FUNCTIONS ***************************************************************/
staticVOIDFixupChildLinks(PRTL_SPLAY_LINKS Links, BOOLEAN Root, BOOLEAN LeftChild){ if (RtlLeftChild(Links)) { RtlInsertAsLeftChild(Links, RtlLeftChild(Links)); }
if (RtlRightChild(Links)) { RtlInsertAsRightChild(Links, RtlRightChild(Links)); }
if (!Root) { if (LeftChild) { RtlInsertAsLeftChild(RtlParent(Links), Links); } else { RtlInsertAsRightChild(RtlParent(Links), Links); } }}
/*
Given the tree: D B FA C E G
Swap(Q,S):
Q S Q.P Q.L Q.R S.P S.L S.RA C S.P S.L S.R Q.P Q.L Q.RB A S S.L S.R Q.P Q Q.RB C S S.L S.R Q.P Q.L QD A S.P S.L S.R S Q.L Q.RD B S S.L S.R S Q Q.RD F S S.L S.R S Q.L Q
When Q is the immediate parent of S, Set Q's parent to S, and the proper child ptr of S to QWhen Q is the root, Set S's parent to S
*/
staticVOIDSwapSplayLinks(PRTL_SPLAY_LINKS LinkA, PRTL_SPLAY_LINKS LinkB){ if (RtlParent(LinkA) == LinkB || RtlIsRoot(LinkB)) { PRTL_SPLAY_LINKS Tmp = LinkA; LinkA = LinkB; LinkB = Tmp; }
{ RTL_SPLAY_LINKS Ta = *LinkA, Tb = *LinkB; BOOLEAN RootA = RtlIsRoot(LinkA), LeftA = RtlIsLeftChild(LinkA), LeftB = RtlIsLeftChild(LinkB);
*LinkB = Ta; *LinkA = Tb;
// A was parent of B is a special case: A->Parent is now B if (RtlParent(&Tb) == LinkA) { if (!RootA) { if (LeftA) { RtlInsertAsLeftChild(RtlParent(&Ta), LinkB); } else { RtlInsertAsRightChild(RtlParent(&Ta), LinkB); } }
if (LeftB) { RtlInsertAsLeftChild(LinkB, LinkA); } else { RtlInsertAsRightChild(LinkB, LinkA); } }
FixupChildLinks(LinkA, FALSE, LeftB); FixupChildLinks(LinkB, RootA, LeftA);
// A was root is a special case: B->Parent is now B if (RootA) RtlParent(LinkB) = LinkB;
#ifdef VERIFY_SWAP_SPLAY_LINKS // Verify the distinct cases of node swap if (RootA) { if (RtlParent(&Tb) == LinkA) { // LinkA = D, LinkB = B // D B S S.L S.R S Q Q.R ASSERT(RtlParent(LinkA) == LinkB); ASSERT(RtlLeftChild(LinkA) == RtlLeftChild(&Tb)); ASSERT(RtlRightChild(LinkA) == RtlRightChild(&Tb)); ASSERT(RtlParent(LinkB) == LinkB); ASSERT(RtlLeftChild(LinkB) == (LeftB ? LinkA : RtlLeftChild(&Ta))); ASSERT(RtlRightChild(LinkB) == (LeftB ? RtlRightChild(&Ta) : LinkA)); } else { // LinkA = D, LinkB = A // D A S.P S.L S.R S Q.L Q.R ASSERT(RtlParent(LinkA) == RtlParent(&Tb)); ASSERT(RtlLeftChild(LinkA) == RtlLeftChild(&Tb)); ASSERT(RtlRightChild(LinkA) == RtlRightChild(&Tb)); ASSERT(RtlParent(LinkB) == LinkB); ASSERT(RtlLeftChild(LinkB) == RtlLeftChild(&Ta)); ASSERT(RtlRightChild(LinkB) == RtlRightChild(&Ta)); } } else { if (RtlParent(&Tb) == LinkA) { // LinkA = B, LinkB = A // B A S S.L S.R Q.P Q Q.R ASSERT(RtlParent(LinkA) == LinkB); ASSERT(RtlLeftChild(LinkA) == RtlLeftChild(&Tb)); ASSERT(RtlRightChild(LinkA) == RtlRightChild(&Tb)); ASSERT(RtlParent(LinkB) == RtlParent(&Ta)); ASSERT(RtlLeftChild(LinkB) == (LeftB ? LinkA : RtlLeftChild(&Ta))); ASSERT(RtlRightChild(LinkB) == (LeftB ? RtlRightChild(&Ta) : LinkA)); } else { // LinkA = A, LinkB = C // A C S.P S.L S.R Q.P Q.L Q.R ASSERT(!memcmp(LinkA, &Tb, sizeof(Tb))); ASSERT(!memcmp(LinkB, &Ta, sizeof(Ta))); } }#endif }}
/* * @implemented */PRTL_SPLAY_LINKSNTAPIRtlDelete(PRTL_SPLAY_LINKS Links){ PRTL_SPLAY_LINKS N, P, C, SP; N = Links;
/* Check if we have two children */ if (RtlLeftChild(N) && RtlRightChild(N)) { /* Get the predecessor */ SP = RtlSubtreePredecessor(N);
/* Swap it with N, this will guarantee that N will only have a child */ SwapSplayLinks(SP, N); }
/* Check if we have no children */ if (!RtlLeftChild(N) && !RtlRightChild(N)) { /* If we are also the root, then the tree is gone */ if (RtlIsRoot(N)) return NULL;
/* Get our parent */ P = RtlParent(N);
/* Find out who is referencing us and delete the reference */ if (RtlIsLeftChild(N)) { /* N was a left child, so erase its parent's left child link */ RtlLeftChild(P) = NULL; } else { /* N was a right child, so erase its parent's right child link */ RtlRightChild(P) = NULL; }
/* And finally splay the parent */ return RtlSplay(P); }
/* If we got here, we have a child (not two: we swapped above!) */ if (RtlLeftChild(N)) { /* We have a left child, so get it */ C = RtlLeftChild(N); } else { /* We have a right child, get it instead */ C = RtlRightChild(N); }
/* Check if we are the root entry */ if (RtlIsRoot(N)) { /* Our child is now root, return it */ RtlParent(C) = C; return C; }
/* Get our parent */ P = RtlParent(N);
/* Find out who is referencing us and link to our child instead */ if (RtlIsLeftChild(N)) { /* N was a left child, so set its parent's left child as our child */ RtlLeftChild(P) = C; } else { /* N was a right child, so set its parent's right child as our child */ RtlRightChild(P) = C; }
/* Finally, inherit our parent and splay the parent */ RtlParent(C) = P; return RtlSplay(P);}
/* * @implemented */VOIDNTAPIRtlDeleteNoSplay(PRTL_SPLAY_LINKS Links, PRTL_SPLAY_LINKS *Root){ PRTL_SPLAY_LINKS N, P, C, SP; N = Links;
/* Check if we have two children */ if (RtlLeftChild(N) && RtlRightChild(N)) { /* Get the predecessor */ SP = RtlSubtreePredecessor(N);
/* If we are the root, the new root will be our predecessor after swapping */ if (RtlIsRoot(N)) *Root = SP;
/* Swap the predecessor with N, this will guarantee that N will only have a child */ SwapSplayLinks(SP, N); }
/* Check if we have no children */ if (!RtlLeftChild(N) && !RtlRightChild(N)) { /* If we are also the root, then the tree is gone */ if (RtlIsRoot(N)) { *Root = NULL; return; }
/* Get our parent */ P = RtlParent(N);
/* Find out who is referencing us and delete the reference */ if (RtlIsLeftChild(N)) { /* N was a left child, so erase its parent's left child link */ RtlLeftChild(P) = NULL; } else { /* N was a right child, so erase its parent's right child link */ RtlRightChild(P) = NULL; }
/* We are done */ return; }
/* If we got here, we have a child (not two: we swapped above!) */ if (RtlLeftChild(N)) { /* We have a left child, so get it */ C = RtlLeftChild(N); } else { /* We have a right child, get it instead */ C = RtlRightChild(N); }
/* Check if we are the root entry */ if (RtlIsRoot(N)) { /* Our child is now root, return it */ RtlParent(C) = C; *Root = C; return; }
/* Get our parent */ P = RtlParent(N);
/* Find out who is referencing us and link to our child instead */ if (RtlIsLeftChild(N)) { /* N was a left child, so set its parent's left child as our child */ RtlLeftChild(P) = C; } else { /* N was a right child, so set its parent's right child as our child */ RtlRightChild(P) = C; }
/* Finally, inherit our parent and we are done */ RtlParent(C) = P; return;}
/* * @implemented */PRTL_SPLAY_LINKSNTAPIRtlRealPredecessor(PRTL_SPLAY_LINKS Links){ PRTL_SPLAY_LINKS Child;
/* Get the left child */ Child = RtlLeftChild(Links); if (Child) { /* Get right-most child */ while (RtlRightChild(Child)) Child = RtlRightChild(Child); return Child; }
/* We don't have a left child, keep looping until we find our parent */ Child = Links; while (RtlIsLeftChild(Child)) Child = RtlParent(Child);
/* The parent should be a right child, return the real predecessor */ if (RtlIsRightChild(Child)) return RtlParent(Child);
/* The parent isn't a right child, so no real precessor for us */ return NULL;}
/* * @implemented */PRTL_SPLAY_LINKSNTAPIRtlRealSuccessor(PRTL_SPLAY_LINKS Links){ PRTL_SPLAY_LINKS Child;
/* Get the right child */ Child = RtlRightChild(Links); if (Child) { /* Get left-most child */ while (RtlLeftChild(Child)) Child = RtlLeftChild(Child); return Child; }
/* We don't have a right child, keep looping until we find our parent */ Child = Links; while (RtlIsRightChild(Child)) Child = RtlParent(Child);
/* The parent should be a left child, return the real successor */ if (RtlIsLeftChild(Child)) return RtlParent(Child);
/* The parent isn't a right child, so no real successor for us */ return NULL;}
/* * @implemented */PRTL_SPLAY_LINKSNTAPIRtlSplay(PRTL_SPLAY_LINKS Links){ /* * Implementation Notes (http://en.wikipedia.org/wiki/Splay_tree): * * To do a splay, we carry out a sequence of rotations, * each of which moves the target node N closer to the root. * * Each particular step depends on only two factors: * - Whether N is the left or right child of its parent node, P, * - Whether P is the left or right child of its parent, G (for grandparent node). * * Thus, there are four cases: * - Case 1: N is the left child of P and P is the left child of G. * In this case we perform a double right rotation, so that * P becomes N's right child, and G becomes P's right child. * * - Case 2: N is the right child of P and P is the right child of G. * In this case we perform a double left rotation, so that * P becomes N's left child, and G becomes P's left child. * * - Case 3: N is the left child of P and P is the right child of G. * In this case we perform a rotation so that * G becomes N's left child, and P becomes N's right child. * * - Case 4: N is the right child of P and P is the left child of G. * In this case we perform a rotation so that * P becomes N's left child, and G becomes N's right child. * * Finally, if N doesn't have a grandparent node, we simply perform a * left or right rotation to move it to the root. * * By performing a splay on the node of interest after every operation, * we keep recently accessed nodes near the root and keep the tree * roughly balanced, so that we achieve the desired amortized time bounds. */ PRTL_SPLAY_LINKS N, P, G;
/* N is the item we'll be playing with */ N = Links;
/* Let the algorithm run until N becomes the root entry */ while (!RtlIsRoot(N)) { /* Now get the parent and grand-parent */ P = RtlParent(N); G = RtlParent(P);
/* Case 1 & 3: N is left child of P */ if (RtlIsLeftChild(N)) { /* Case 1: P is the left child of G */ if (RtlIsLeftChild(P)) { /* * N's right-child becomes P's left child and * P's right-child becomes G's left child. */ RtlLeftChild(P) = RtlRightChild(N); RtlLeftChild(G) = RtlRightChild(P);
/* * If they exist, update their parent pointers too, * since they've changed trees. */ if (RtlLeftChild(P)) RtlParent(RtlLeftChild(P)) = P; if (RtlLeftChild(G)) RtlParent(RtlLeftChild(G)) = G;
/* * Now we'll shove N all the way to the top. * Check if G is the root first. */ if (RtlIsRoot(G)) { /* G doesn't have a parent, so N will become the root! */ RtlParent(N) = N; } else { /* G has a parent, so inherit it since we take G's place */ RtlParent(N) = RtlParent(G);
/* * Now find out who was referencing G and have it reference * N instead, since we're taking G's place. */ if (RtlIsLeftChild(G)) { /* * G was a left child, so change its parent's left * child link to point to N now. */ RtlLeftChild(RtlParent(G)) = N; } else { /* * G was a right child, so change its parent's right * child link to point to N now. */ RtlRightChild(RtlParent(G)) = N; } }
/* Now N is on top, so P has become its child. */ RtlRightChild(N) = P; RtlParent(P) = N;
/* N is on top, P is its child, so G is grandchild. */ RtlRightChild(P) = G; RtlParent(G) = P; } /* Case 3: P is the right child of G */ else if (RtlIsRightChild(P)) { /* * N's left-child becomes G's right child and * N's right-child becomes P's left child. */ RtlRightChild(G) = RtlLeftChild(N); RtlLeftChild(P) = RtlRightChild(N);
/* * If they exist, update their parent pointers too, * since they've changed trees. */ if (RtlRightChild(G)) RtlParent(RtlRightChild(G)) = G; if (RtlLeftChild(P)) RtlParent(RtlLeftChild(P)) = P;
/* * Now we'll shove N all the way to the top. * Check if G is the root first. */ if (RtlIsRoot(G)) { /* G doesn't have a parent, so N will become the root! */ RtlParent(N) = N; } else { /* G has a parent, so inherit it since we take G's place */ RtlParent(N) = RtlParent(G);
/* * Now find out who was referencing G and have it reference * N instead, since we're taking G's place. */ if (RtlIsLeftChild(G)) { /* * G was a left child, so change its parent's left * child link to point to N now. */ RtlLeftChild(RtlParent(G)) = N; } else { /* * G was a right child, so change its parent's right * child link to point to N now. */ RtlRightChild(RtlParent(G)) = N; } }
/* Now N is on top, so G has become its left child. */ RtlLeftChild(N) = G; RtlParent(G) = N;
/* N is on top, G is its left child, so P is right child. */ RtlRightChild(N) = P; RtlParent(P) = N; } /* "Finally" case: N doesn't have a grandparent => P is root */ else { /* P's left-child becomes N's right child */ RtlLeftChild(P) = RtlRightChild(N);
/* If it exists, update its parent pointer too */ if (RtlLeftChild(P)) RtlParent(RtlLeftChild(P)) = P;
/* Now make N the root, no need to worry about references */ N->Parent = N;
/* And make P its right child */ N->RightChild = P; P->Parent = N; } } /* Case 2 & 4: N is right child of P */ else { /* Case 2: P is the right child of G */ if (RtlIsRightChild(P)) { /* * P's left-child becomes G's right child and * N's left-child becomes P's right child. */ RtlRightChild(G) = RtlLeftChild(P); RtlRightChild(P) = RtlLeftChild(N);
/* * If they exist, update their parent pointers too, * since they've changed trees. */ if (RtlRightChild(G)) RtlParent(RtlRightChild(G)) = G; if (RtlRightChild(P)) RtlParent(RtlRightChild(P)) = P;
/* * Now we'll shove N all the way to the top. * Check if G is the root first. */ if (RtlIsRoot(G)) { /* G doesn't have a parent, so N will become the root! */ RtlParent(N) = N; } else { /* G has a parent, so inherit it since we take G's place */ RtlParent(N) = RtlParent(G);
/* * Now find out who was referencing G and have it reference * N instead, since we're taking G's place. */ if (RtlIsLeftChild(G)) { /* * G was a left child, so change its parent's left * child link to point to N now. */ RtlLeftChild(RtlParent(G)) = N; } else { /* * G was a right child, so change its parent's right * child link to point to N now. */ RtlRightChild(RtlParent(G)) = N; } }
/* Now N is on top, so P has become its child. */ RtlLeftChild(N) = P; RtlParent(P) = N;
/* N is on top, P is its child, so G is grandchild. */ RtlLeftChild(P) = G; RtlParent(G) = P; } /* Case 4: P is the left child of G */ else if (RtlIsLeftChild(P)) { /* * N's left-child becomes G's right child and * N's right-child becomes P's left child. */ RtlRightChild(P) = RtlLeftChild(N); RtlLeftChild(G) = RtlRightChild(N);
/* * If they exist, update their parent pointers too, * since they've changed trees. */ if (RtlRightChild(P)) RtlParent(RtlRightChild(P)) = P; if (RtlLeftChild(G)) RtlParent(RtlLeftChild(G)) = G;
/* * Now we'll shove N all the way to the top. * Check if G is the root first. */ if (RtlIsRoot(G)) { /* G doesn't have a parent, so N will become the root! */ RtlParent(N) = N; } else { /* G has a parent, so inherit it since we take G's place */ RtlParent(N) = RtlParent(G);
/* * Now find out who was referencing G and have it reference * N instead, since we're taking G's place. */ if (RtlIsLeftChild(G)) { /* * G was a left child, so change its parent's left * child link to point to N now. */ RtlLeftChild(RtlParent(G)) = N; } else { /* * G was a right child, so change its parent's right * child link to point to N now. */ RtlRightChild(RtlParent(G)) = N; } }
/* Now N is on top, so P has become its left child. */ RtlLeftChild(N) = P; RtlParent(G) = N;
/* N is on top, P is its left child, so G is right child. */ RtlRightChild(N) = G; RtlParent(P) = N; } /* "Finally" case: N doesn't have a grandparent => P is root */ else { /* P's right-child becomes N's left child */ RtlRightChild(P) = RtlLeftChild(N);
/* If it exists, update its parent pointer too */ if (RtlRightChild(P)) RtlParent(RtlRightChild(P)) = P;
/* Now make N the root, no need to worry about references */ N->Parent = N;
/* And make P its left child */ N->LeftChild = P; P->Parent = N; } } }
/* Return the root entry */ ASSERT(RtlIsRoot(N)); return N;}
/* * @implemented */PRTL_SPLAY_LINKSNTAPIRtlSubtreePredecessor(IN PRTL_SPLAY_LINKS Links){ PRTL_SPLAY_LINKS Child;
/* Get the left child */ Child = RtlLeftChild(Links); if (!Child) return NULL;
/* Get right-most child */ while (RtlRightChild(Child)) Child = RtlRightChild(Child);
/* Return it */ return Child;}
/* * @implemented */PRTL_SPLAY_LINKSNTAPIRtlSubtreeSuccessor(IN PRTL_SPLAY_LINKS Links){ PRTL_SPLAY_LINKS Child;
/* Get the right child */ Child = RtlRightChild(Links); if (!Child) return NULL;
/* Get left-most child */ while (RtlLeftChild(Child)) Child = RtlLeftChild(Child);
/* Return it */ return Child;}
/* EOF */