Ros-diffs November 2005

ros-diffs@reactos.org

27 participants
875 discussions

[ion] 19082: - Implement most of RtlDelete.
by ion＠svn.reactos.com 09 Nov '05

09 Nov '05

- Implement most of RtlDelete. Modified: trunk/reactos/lib/rtl/splaytree.c _____ Modified: trunk/reactos/lib/rtl/splaytree.c --- trunk/reactos/lib/rtl/splaytree.c 2005-11-09 01:39:39 UTC (rev 19081) +++ trunk/reactos/lib/rtl/splaytree.c 2005-11-09 02:16:03 UTC (rev 19082) @@ -16,16 +16,86 @@ /* FUNCTIONS ***************************************************************/ /* -* @unimplemented -*/ + * @implemented + */ PRTL_SPLAY_LINKS NTAPI -RtlDelete ( - PRTL_SPLAY_LINKS Links - ) +RtlDelete(PRTL_SPLAY_LINKS Links) { - UNIMPLEMENTED; - return 0; + 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 have only a child */ + //SwapSplayLinks(SP, N); + DPRINT1("UNIMPLEMENTED!\n"); + } + + /* Check if we have no children */ + if (!(RtlLeftChild(N)) && !(RtlRightChild(N))) + { + /* If we are also the root, then the tree is gone */ + 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(RtlParent(N)) = NULL; + } + else + { + /* N was a right child, so erase its parent's right child link */ + RtlRightChild(RtlParent(N)) = 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 him instead */ + C = RtlRightChild(N); + } + + /* Check if we are the root entry */ + if (RtlIsRoot(N)) + { + /* Our child is now root, return him */ + C->Parent = C; + return C; + } + + /* 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(RtlParent(N)) = C; + } + else + { + /* N was a right child, so set its parent's right child as our child */ + RtlRightChild(RtlParent(N)) = C; + } + + /* Finally, inherit our parent and splay the parent */ + C->Parent = N->Parent; + return RtlSplay(RtlParent(C)); } /*

1 0

[ion] 19081: - Implement RtlRealPrecessdor and RtlRealSuccessor
by ion＠svn.reactos.com 09 Nov '05

09 Nov '05

- Implement RtlRealPrecessdor and RtlRealSuccessor Modified: trunk/reactos/lib/rtl/splaytree.c _____ Modified: trunk/reactos/lib/rtl/splaytree.c --- trunk/reactos/lib/rtl/splaytree.c 2005-11-09 01:05:00 UTC (rev 19080) +++ trunk/reactos/lib/rtl/splaytree.c 2005-11-09 01:39:39 UTC (rev 19081) @@ -41,31 +41,62 @@ UNIMPLEMENTED; } - /* -* @unimplemented +* @implemented */ PRTL_SPLAY_LINKS NTAPI -RtlRealPredecessor ( - PRTL_SPLAY_LINKS Links - ) +RtlRealPredecessor(PRTL_SPLAY_LINKS Links) { - UNIMPLEMENTED; - return 0; + 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; } /* -* @unimplemented +* @implemented */ PRTL_SPLAY_LINKS NTAPI -RtlRealSuccessor ( - PRTL_SPLAY_LINKS Links - ) +RtlRealSuccessor(PRTL_SPLAY_LINKS Links) { - UNIMPLEMENTED; - return 0; + 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; } /*

1 0

[ion] 19080: - Fix RtlSubtreePredecessor/Successor, someone had implemented them backwards.
by ion＠svn.reactos.com 09 Nov '05

09 Nov '05

- Fix RtlSubtreePredecessor/Successor, someone had implemented them backwards. Modified: trunk/reactos/lib/rtl/splaytree.c _____ Modified: trunk/reactos/lib/rtl/splaytree.c --- trunk/reactos/lib/rtl/splaytree.c 2005-11-09 00:56:41 UTC (rev 19079) +++ trunk/reactos/lib/rtl/splaytree.c 2005-11-09 01:05:00 UTC (rev 19080) @@ -411,49 +411,44 @@ return N; } - /* * @implemented */ -PRTL_SPLAY_LINKS NTAPI -RtlSubtreePredecessor (IN PRTL_SPLAY_LINKS Links) +PRTL_SPLAY_LINKS +NTAPI +RtlSubtreePredecessor(IN PRTL_SPLAY_LINKS Links) { - PRTL_SPLAY_LINKS Child; + PRTL_SPLAY_LINKS Child; - Child = Links->RightChild; - if (Child == NULL) - return NULL; + /* Get the left child */ + Child = RtlLeftChild(Links); + if (!Child) return NULL; - if (Child->LeftChild == NULL) - return Child; + /* Get right-most child */ + while (RtlRightChild(Child)) Child = RtlRightChild(Child); - /* Get left-most child */ - while (Child->LeftChild != NULL) - Child = Child->LeftChild; - - return Child; + /* Return it */ + return Child; } /* * @implemented */ -PRTL_SPLAY_LINKS NTAPI -RtlSubtreeSuccessor (IN PRTL_SPLAY_LINKS Links) +PRTL_SPLAY_LINKS +NTAPI +RtlSubtreeSuccessor(IN PRTL_SPLAY_LINKS Links) { - PRTL_SPLAY_LINKS Child; + PRTL_SPLAY_LINKS Child; - Child = Links->LeftChild; - if (Child == NULL) - return NULL; + /* Get the right child */ + Child = RtlRightChild(Links); + if (!Child) return NULL; - if (Child->RightChild == NULL) - return Child; + /* Get left-most child */ + while (RtlLeftChild(Child)) Child = RtlLeftChild(Child); - /* Get right-most child */ - while (Child->RightChild != NULL) - Child = Child->RightChild; - - return Child; + /* Return it */ + return Child; } /* EOF */

1 0

[weiden] 19079: fixed data size calculation in RtlSelfRelativeToAbsoluteSD2
by weiden＠svn.reactos.com 09 Nov '05

09 Nov '05

fixed data size calculation in RtlSelfRelativeToAbsoluteSD2 Modified: trunk/reactos/lib/rtl/sd.c _____ Modified: trunk/reactos/lib/rtl/sd.c --- trunk/reactos/lib/rtl/sd.c 2005-11-09 00:44:37 UTC (rev 19078) +++ trunk/reactos/lib/rtl/sd.c 2005-11-09 00:56:41 UTC (rev 19079) @@ -815,7 +815,7 @@ ASSERT((ULONG_PTR)DataEnd >= (ULONG_PTR)DataStart); - DataSize = (ULONG)((ULONG_PTR)DataEnd >= (ULONG_PTR)DataStart); + DataSize = (ULONG)((ULONG_PTR)DataEnd - (ULONG_PTR)DataStart); if (*BufferSize < sizeof(SECURITY_DESCRIPTOR) + DataSize) {

1 0

[ion] 19078: - Fix CreateNamedPipeW to convert some NT flags properly, timeouts, etc, and document/prettify the function.
by ion＠svn.reactos.com 09 Nov '05

09 Nov '05

- Fix CreateNamedPipeW to convert some NT flags properly, timeouts, etc, and document/prettify the function. - NT 5.2 NPFS now works great, the kernel32_wintest pipe runs without crashing, and reports "411 tests passed, 30 failures". Modified: trunk/reactos/include/ndk/iotypes.h Modified: trunk/reactos/lib/kernel32/file/npipe.c _____ Modified: trunk/reactos/include/ndk/iotypes.h --- trunk/reactos/include/ndk/iotypes.h 2005-11-08 23:51:46 UTC (rev 19077) +++ trunk/reactos/include/ndk/iotypes.h 2005-11-09 00:44:37 UTC (rev 19078) @@ -38,6 +38,7 @@ /* Pipe Flags */ #define FILE_PIPE_BYTE_STREAM_TYPE 0x00000000 +#define FILE_PIPE_MESSAGE_TYPE 0x00000001 #define FILE_PIPE_BYTE_STREAM_MODE 0x00000000 #define FILE_PIPE_MESSAGE_MODE 0x00000001 #define FILE_PIPE_QUEUE_OPERATION 0x00000000 _____ Modified: trunk/reactos/lib/kernel32/file/npipe.c --- trunk/reactos/lib/kernel32/file/npipe.c 2005-11-08 23:51:46 UTC (rev 19077) +++ trunk/reactos/lib/kernel32/file/npipe.c 2005-11-09 00:44:37 UTC (rev 19078) @@ -13,6 +13,7 @@ #include <k32.h> #define NDEBUG +//#define USING_PROPER_NPFS_WAIT_SEMANTICS #include "../include/debug.h" /* FUNCTIONS ****************************************************************/ @@ -51,130 +52,178 @@ return(NamedPipeHandle); } - /* * @implemented */ -HANDLE STDCALL +HANDLE +STDCALL CreateNamedPipeW(LPCWSTR lpName, - DWORD dwOpenMode, - DWORD dwPipeMode, - DWORD nMaxInstances, - DWORD nOutBufferSize, - DWORD nInBufferSize, - DWORD nDefaultTimeOut, - LPSECURITY_ATTRIBUTES lpSecurityAttributes) + DWORD dwOpenMode, + DWORD dwPipeMode, + DWORD nMaxInstances, + DWORD nOutBufferSize, + DWORD nInBufferSize, + DWORD nDefaultTimeOut, + LPSECURITY_ATTRIBUTES lpSecurityAttributes) { - UNICODE_STRING NamedPipeName; - BOOL Result; - NTSTATUS Status; - OBJECT_ATTRIBUTES ObjectAttributes; - HANDLE PipeHandle; - ACCESS_MASK DesiredAccess; - ULONG CreateOptions; - ULONG WriteModeMessage; - ULONG ReadModeMessage; - ULONG NonBlocking; - IO_STATUS_BLOCK Iosb; - ULONG ShareAccess, Attributes; - LARGE_INTEGER DefaultTimeOut; - PSECURITY_DESCRIPTOR SecurityDescriptor = NULL; + UNICODE_STRING NamedPipeName; + BOOL Result; + NTSTATUS Status; + OBJECT_ATTRIBUTES ObjectAttributes; + HANDLE PipeHandle; + ACCESS_MASK DesiredAccess; + ULONG CreateOptions = 0; + ULONG WriteModeMessage; + ULONG ReadModeMessage; + ULONG NonBlocking; + IO_STATUS_BLOCK Iosb; + ULONG ShareAccess = 0, Attributes; + LARGE_INTEGER DefaultTimeOut; + PSECURITY_DESCRIPTOR SecurityDescriptor = NULL; - if (nMaxInstances == 0 || nMaxInstances > PIPE_UNLIMITED_INSTANCES) - { - SetLastError(ERROR_INVALID_PARAMETER); - return INVALID_HANDLE_VALUE; - } + /* Check for valid instances */ + if (nMaxInstances == 0 || nMaxInstances > PIPE_UNLIMITED_INSTANCES) + { + /* Fail */ + SetLastError(ERROR_INVALID_PARAMETER); + return INVALID_HANDLE_VALUE; + } - Result = RtlDosPathNameToNtPathName_U((LPWSTR)lpName, - &NamedPipeName, - NULL, - NULL); - if (!Result) - { - SetLastError(ERROR_PATH_NOT_FOUND); - return(INVALID_HANDLE_VALUE); - } + /* Convert to NT syntax */ + if (nMaxInstances == PIPE_UNLIMITED_INSTANCES) nMaxInstances = -1; - DPRINT("Pipe name: %wZ\n", &NamedPipeName); - DPRINT("Pipe name: %S\n", NamedPipeName.Buffer); + /* Convert the name */ + Result = RtlDosPathNameToNtPathName_U((LPWSTR)lpName, + &NamedPipeName, + NULL, + NULL); + if (!Result) + { + /* Conversion failed */ + SetLastError(ERROR_PATH_NOT_FOUND); + return(INVALID_HANDLE_VALUE); + } - Attributes = OBJ_CASE_INSENSITIVE; - if(lpSecurityAttributes) - { - SecurityDescriptor = lpSecurityAttributes->lpSecurityDescriptor; - if(lpSecurityAttributes->bInheritHandle) - Attributes |= OBJ_INHERIT; - } + DPRINT1("Pipe name: %wZ\n", &NamedPipeName); + DPRINT1("Pipe name: %S\n", NamedPipeName.Buffer); - InitializeObjectAttributes(&ObjectAttributes, - &NamedPipeName, - Attributes, - NULL, - SecurityDescriptor); + /* Always case insensitive, check if we got extra attributes */ + Attributes = OBJ_CASE_INSENSITIVE; + if(lpSecurityAttributes) + { + /* We did; get the security descriptor */ + SecurityDescriptor = lpSecurityAttributes->lpSecurityDescriptor; - DesiredAccess = SYNCHRONIZE | (dwOpenMode & (WRITE_DAC | WRITE_OWNER | ACCESS_SYSTEM_SECURITY)); - ShareAccess = 0; - CreateOptions = 0; + /* And check if this is pipe's handle will beinheritable */ + if(lpSecurityAttributes->bInheritHandle) Attributes |= OBJ_INHERIT; + } - if (dwOpenMode & FILE_FLAG_WRITE_THROUGH) - CreateOptions = CreateOptions | FILE_WRITE_THROUGH; + /* Now we can initialize the object attributes */ + InitializeObjectAttributes(&ObjectAttributes, + &NamedPipeName, + Attributes, + NULL, + SecurityDescriptor); - if (!(dwOpenMode & FILE_FLAG_OVERLAPPED)) - CreateOptions = CreateOptions | FILE_SYNCHRONOUS_IO_NONALERT; + /* Setup the default Desired Access */ + DesiredAccess = SYNCHRONIZE | (dwOpenMode & (WRITE_DAC | + WRITE_OWNER | + ACCESS_SYSTEM_SECURITY)); - if (dwOpenMode & PIPE_ACCESS_OUTBOUND) - { - ShareAccess |= FILE_SHARE_READ; - DesiredAccess |= GENERIC_WRITE; - } - if (dwOpenMode & PIPE_ACCESS_INBOUND) - { - ShareAccess |= FILE_SHARE_WRITE; - DesiredAccess |= GENERIC_READ; - } - if (dwPipeMode & PIPE_TYPE_MESSAGE) - WriteModeMessage = FILE_PIPE_MESSAGE_MODE; - else - WriteModeMessage = FILE_PIPE_BYTE_STREAM_MODE; + /* Convert to NT Create Flags */ + if (dwOpenMode & FILE_FLAG_WRITE_THROUGH) + { + CreateOptions |= FILE_WRITE_THROUGH; + } + if (!(dwOpenMode & FILE_FLAG_OVERLAPPED)) + { + CreateOptions |= FILE_SYNCHRONOUS_IO_NONALERT; + } - if (dwPipeMode & PIPE_READMODE_MESSAGE) - ReadModeMessage = FILE_PIPE_MESSAGE_MODE; - else - ReadModeMessage = FILE_PIPE_BYTE_STREAM_MODE; + /* Handle all open modes */ + if (dwOpenMode & PIPE_ACCESS_OUTBOUND) + { + ShareAccess |= FILE_SHARE_READ; + DesiredAccess |= GENERIC_WRITE; + } + if (dwOpenMode & PIPE_ACCESS_INBOUND) + { + ShareAccess |= FILE_SHARE_WRITE; + DesiredAccess |= GENERIC_READ; + } - if (dwPipeMode & PIPE_NOWAIT) - NonBlocking = FILE_PIPE_COMPLETE_OPERATION; - else - NonBlocking = FILE_PIPE_QUEUE_OPERATION; + /* Handle the type flags */ + if (dwPipeMode & PIPE_TYPE_MESSAGE) + { + WriteModeMessage = FILE_PIPE_MESSAGE_TYPE; + } + else + { + WriteModeMessage = FILE_PIPE_BYTE_STREAM_TYPE; + } - DefaultTimeOut.QuadPart = nDefaultTimeOut * -10000LL; + /* Handle the mode flags */ + if (dwPipeMode & PIPE_READMODE_MESSAGE) + { + ReadModeMessage = FILE_PIPE_MESSAGE_MODE; + } + else + { + ReadModeMessage = FILE_PIPE_BYTE_STREAM_MODE; + } - Status = NtCreateNamedPipeFile(&PipeHandle, - DesiredAccess, - &ObjectAttributes, - &Iosb, - ShareAccess, - FILE_OPEN_IF, - CreateOptions, - WriteModeMessage, - ReadModeMessage, - NonBlocking, - nMaxInstances, - nInBufferSize, - nOutBufferSize, - &DefaultTimeOut); + /* Handle the blocking mode */ + if (dwPipeMode & PIPE_NOWAIT) + { + NonBlocking = FILE_PIPE_COMPLETE_OPERATION; + } + else + { + NonBlocking = FILE_PIPE_QUEUE_OPERATION; + } - RtlFreeUnicodeString(&NamedPipeName); + /* Check if we have a timeout */ + if (nDefaultTimeOut) + { + /* Convert the time to NT format */ + DefaultTimeOut.QuadPart = UInt32x32To64(nDefaultTimeOut, -10000); + } + else + { + /* Use default timeout of 50 ms */ + DefaultTimeOut.QuadPart = -500000; + } - if (!NT_SUCCESS(Status)) - { - DPRINT("NtCreateNamedPipe failed (Status %x)!\n", Status); - SetLastErrorByStatus (Status); - return INVALID_HANDLE_VALUE; - } + /* Now create the pipe */ + Status = NtCreateNamedPipeFile(&PipeHandle, + DesiredAccess, + &ObjectAttributes, + &Iosb, + ShareAccess, + FILE_OPEN_IF, + CreateOptions, + WriteModeMessage, + ReadModeMessage, + NonBlocking, + nMaxInstances, + nInBufferSize, + nOutBufferSize, + &DefaultTimeOut); - return PipeHandle; + /* Free the name */ + RtlFreeUnicodeString(&NamedPipeName); + + /* Check status */ + if (!NT_SUCCESS(Status)) + { + /* Failed to create it */ + DPRINT1("NtCreateNamedPipe failed (Status %x)!\n", Status); + SetLastErrorByStatus (Status); + return INVALID_HANDLE_VALUE; + } + + /* Return the handle */ + return PipeHandle; }

1 0

[ion] 19077: - Finish implementing RtlSplayTree
by ion＠svn.reactos.com 08 Nov '05

08 Nov '05

- Finish implementing RtlSplayTree Modified: trunk/reactos/lib/rtl/splaytree.c _____ Modified: trunk/reactos/lib/rtl/splaytree.c --- trunk/reactos/lib/rtl/splaytree.c 2005-11-08 23:47:25 UTC (rev 19076) +++ trunk/reactos/lib/rtl/splaytree.c 2005-11-08 23:51:46 UTC (rev 19077) @@ -69,7 +69,7 @@ } /* -* @unimplemented +* @implemented */ PRTL_SPLAY_LINKS NTAPI @@ -249,7 +249,18 @@ /* "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 */ @@ -380,7 +391,18 @@ /* "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; } } }

1 0

[ion] 19076: - Implement cases 2 & 4 of RtlSplayTree
by ion＠svn.reactos.com 08 Nov '05

08 Nov '05

- Implement cases 2 & 4 of RtlSplayTree Modified: trunk/reactos/lib/rtl/splaytree.c _____ Modified: trunk/reactos/lib/rtl/splaytree.c --- trunk/reactos/lib/rtl/splaytree.c 2005-11-08 23:42:40 UTC (rev 19075) +++ trunk/reactos/lib/rtl/splaytree.c 2005-11-08 23:47:25 UTC (rev 19076) @@ -258,12 +258,124 @@ /* 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. + */ + RtlLeftChild(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. + */ + RtlLeftChild(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

1 0

[ion] 19075: - Fix bug in case 2/4 denomination.
by ion＠svn.reactos.com 08 Nov '05

08 Nov '05

- Fix bug in case 2/4 denomination. Modified: trunk/reactos/lib/rtl/splaytree.c _____ Modified: trunk/reactos/lib/rtl/splaytree.c --- trunk/reactos/lib/rtl/splaytree.c 2005-11-08 23:40:37 UTC (rev 19074) +++ trunk/reactos/lib/rtl/splaytree.c 2005-11-08 23:42:40 UTC (rev 19075) @@ -255,13 +255,13 @@ /* Case 2 & 4: N is right child of P */ else { - /* Case 2: P is the left child of G */ - if (RtlIsLeftChild(P)) + /* Case 2: P is the right child of G */ + if (RtlIsRightChild(P)) { } - /* Case 4: P is the right child of G */ - else if (RtlIsRightChild(P)) + /* Case 4: P is the left child of G */ + else if (RtlIsLeftChild(P)) { }

1 0

[ion] 19074: - Implement Case 3 of RtlSplay
by ion＠svn.reactos.com 08 Nov '05

08 Nov '05

- Implement Case 3 of RtlSplay Modified: trunk/reactos/lib/rtl/splaytree.c _____ Modified: trunk/reactos/lib/rtl/splaytree.c --- trunk/reactos/lib/rtl/splaytree.c 2005-11-08 23:33:07 UTC (rev 19073) +++ trunk/reactos/lib/rtl/splaytree.c 2005-11-08 23:40:37 UTC (rev 19074) @@ -136,7 +136,7 @@ /* * If they exist, update their parent pointers too, - * since they've changed trees + * since they've changed trees. */ if (RtlLeftChild(P)) RtlParent(RtlLeftChild(P)) = P; if (RtlLeftChild(G)) RtlParent(RtlLeftChild(G)) = G; @@ -177,18 +177,74 @@ } } - /* Now N is on top, so P has become its child */ + /* 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 */ + /* 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. + */ + RtlLeftChild(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

1 0

[ion] 19073: - Implement Case 1 of RtlSplay
by ion＠svn.reactos.com 08 Nov '05

08 Nov '05

- Implement Case 1 of RtlSplay Modified: trunk/reactos/lib/rtl/splaytree.c _____ Modified: trunk/reactos/lib/rtl/splaytree.c --- trunk/reactos/lib/rtl/splaytree.c 2005-11-08 22:54:39 UTC (rev 19072) +++ trunk/reactos/lib/rtl/splaytree.c 2005-11-08 23:33:07 UTC (rev 19073) @@ -127,7 +127,63 @@ /* 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. + */ + RtlLeftChild(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))

1 0

← Newer
1
...
69
70
71
72
73
74
75
...
88
Older →

Jump to page:

2025

2024

2023

2022

2021

2020

2019

2018

2017

2016

2015

2014

2013

2012

2011

2010

2009

2008

2007

2006

2005

2004

Ros-diffs November 2005