- Implement RtlSplay skeleton cases.
Modified: trunk/reactos/include/ndk/rtlfuncs.h
Modified: trunk/reactos/lib/rtl/splaytree.c
_____
Modified: trunk/reactos/include/ndk/rtlfuncs.h
--- trunk/reactos/include/ndk/rtlfuncs.h 2005-11-08 22:45:45 UTC
(rev 19071)
+++ trunk/reactos/include/ndk/rtlfuncs.h 2005-11-08 22:54:39 UTC
(rev 19072)
@@ -24,6 +24,9 @@
#define RtlIsLeftChild(Links) \
(RtlLeftChild(RtlParent(Links)) == (PRTL_SPLAY_LINKS)(Links))
+#define RtlIsRightChild(Links) \
+ (RtlRightChild(RtlParent(Links)) == (PRTL_SPLAY_LINKS)(Links))
+
#define RtlRightChild(Links) \
((PRTL_SPLAY_LINKS)(Links))->RightChild
_____
Modified: trunk/reactos/lib/rtl/splaytree.c
--- trunk/reactos/lib/rtl/splaytree.c 2005-11-08 22:45:45 UTC (rev
19071)
+++ trunk/reactos/lib/rtl/splaytree.c 2005-11-08 22:54:39 UTC (rev
19072)
@@ -109,8 +109,60 @@
* we keep recently accessed nodes near the root and keep the tree
* roughly balanced, so that we achieve the desired amortized time
bounds.
*/
- UNIMPLEMENTED;
- return 0;
+ 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))
+ {
+
+ }
+ /* Case 3: P is the right child of G */
+ else if (RtlIsRightChild(P))
+ {
+
+ }
+ /* "Finally" case: N doesn't have a grandparent => P is
root */
+ else
+ {
+
+ }
+ }
+ /* Case 2 & 4: N is right child of P */
+ else
+ {
+ /* Case 2: P is the left child of G */
+ if (RtlIsLeftChild(P))
+ {
+
+ }
+ /* Case 4: P is the right child of G */
+ else if (RtlIsRightChild(P))
+ {
+
+ }
+ /* "Finally" case: N doesn't have a grandparent => P is
root */
+ else
+ {
+
+ }
+ }
+ }
+
+ /* Return the root entry */
+ return N;
}
- Add implementation notes for RtlSplayTree
Modified: trunk/reactos/lib/rtl/splaytree.c
_____
Modified: trunk/reactos/lib/rtl/splaytree.c
--- trunk/reactos/lib/rtl/splaytree.c 2005-11-08 22:25:29 UTC (rev
19070)
+++ trunk/reactos/lib/rtl/splaytree.c 2005-11-08 22:45:45 UTC (rev
19071)
@@ -73,10 +73,42 @@
*/
PRTL_SPLAY_LINKS
NTAPI
-RtlSplay (
- PRTL_SPLAY_LINKS Links
- )
+RtlSplay(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.
+ */
UNIMPLEMENTED;
return 0;
}
Allocate mem for the structure, not only for a pointer.
Modified: trunk/reactos/drivers/storage/pciidex/pdo.c
_____
Modified: trunk/reactos/drivers/storage/pciidex/pdo.c
--- trunk/reactos/drivers/storage/pciidex/pdo.c 2005-11-08 21:07:11 UTC
(rev 19067)
+++ trunk/reactos/drivers/storage/pciidex/pdo.c 2005-11-08 21:49:27 UTC
(rev 19068)
@@ -180,7 +180,7 @@
/* FIXME: what to do with BusMasterPortBase? */
- ListSize = sizeof(PIO_RESOURCE_REQUIREMENTS_LIST)
+ ListSize = sizeof(IO_RESOURCE_REQUIREMENTS_LIST)
+ 2 * sizeof(IO_RESOURCE_DESCRIPTOR);
RequirementsList = ExAllocatePool(PagedPool, ListSize);
if (!RequirementsList)
- Implement proper version of WaitNamedPipeW to be used when NPFS will
be modified to work as documented. Define
USING_PROPER_NPFS_WAIT_SEMANTICS if you want to use Windows NPFS
Modified: trunk/reactos/lib/kernel32/file/npipe.c
_____
Modified: trunk/reactos/lib/kernel32/file/npipe.c
--- trunk/reactos/lib/kernel32/file/npipe.c 2005-11-08 20:57:31 UTC
(rev 19066)
+++ trunk/reactos/lib/kernel32/file/npipe.c 2005-11-08 21:07:11 UTC
(rev 19067)
@@ -199,7 +199,195 @@
return(r);
}
+/*
+ * When NPFS will work properly, use this code instead. It is
compatible with
+ * Microsoft's NPFS.SYS. The main difference is that:
+ * - This code actually respects the timeout instead of ignoring
it!
+ * - This code validates and creates the proper names for both UNC
and local pipes
+ * - On NT, you open the *root* pipe directory (either
\DosDevices\Pipe or
+ * \DosDevices\Unc\Server\Pipe) and then send the pipe to wait
on in the
+ * FILE_PIPE_WAIT_FOR_BUFFER structure.
+ */
+#ifdef USING_PROPER_NPFS_WAIT_SEMANTICS
+/*
+ * @implemented
+ */
+BOOL
+WINAPI
+WaitNamedPipeW(LPCWSTR lpNamedPipeName,
+ DWORD nTimeOut)
+{
+ UNICODE_STRING NamedPipeName, NewName, DevicePath, PipePrefix;
+ ULONG NameLength;
+ ULONG i;
+ PWCHAR p;
+ ULONG Type;
+ OBJECT_ATTRIBUTES ObjectAttributes;
+ NTSTATUS Status;
+ HANDLE FileHandle;
+ IO_STATUS_BLOCK IoStatusBlock;
+ ULONG WaitPipeInfoSize;
+ PFILE_PIPE_WAIT_FOR_BUFFER WaitPipeInfo;
+ /* Start by making a unicode string of the name */
+ DPRINT("Sent path: %S\n", lpNamedPipeName);
+ RtlCreateUnicodeString(&NamedPipeName, lpNamedPipeName);
+ NameLength = NamedPipeName.Length / sizeof(WCHAR);
+
+ /* All slashes must become backslashes */
+ for (i = 0; i < NameLength; i++)
+ {
+ /* Check and convert */
+ if (NamedPipeName.Buffer[i] == L'/') NamedPipeName.Buffer[i] =
L'\\';
+ }
+
+ /* Find the path type of the name we were given */
+ NewName = NamedPipeName;
+ Type = RtlDetermineDosPathNameType_U(lpNamedPipeName);
+
+ /* Check if this was a device path, ie : "\\.\pipe\name" */
+ if (Type == DEVICE_PATH)
+ {
+ /* Make sure it's a valid prefix */
+ RtlInitUnicodeString(&PipePrefix, L"\\\\.\\pipe\\");
+ RtlPrefixString((PANSI_STRING)&PipePrefix,
(PANSI_STRING)&NewName, TRUE);
+
+ /* Move past it */
+ NewName.Buffer += 9;
+ NewName.Length -= 9 * sizeof(WCHAR);
+
+ /* Initialize the Dos Devices name */
+ DPRINT("NewName: %wZ\n", &NewName);
+ RtlInitUnicodeString(&DevicePath, L"\\DosDevices\\pipe\\");
+ }
+ else if (Type == UNC_PATH)
+ {
+ /* The path is \\server\\pipe\name; find the pipename itself */
+ p = &NewName.Buffer[2];
+
+ /* First loop to get past the server name */
+ do
+ {
+ /* Check if this is a backslash */
+ if (*p == L'\\') break;
+
+ /* Check next */
+ p++;
+ } while (*p);
+
+ /* Now make sure the full name contains "pipe\" */
+ if ((*p) && !(_wcsnicmp(p + 1, L"pipe\\", sizeof("pipe\\"))))
+ {
+ /* Get to the pipe name itself now */
+ p += sizeof("pipe\\") - 1;
+ }
+ else
+ {
+ /* The name is invalid */
+ DPRINT1("Invalid name!\n");
+ SetLastErrorByStatus(STATUS_OBJECT_PATH_SYNTAX_BAD);
+ return FALSE;
+ }
+
+ /* FIXME: Open \DosDevices\Unc\Server\Pipe\Name */
+ }
+ else
+ {
+ DPRINT1("Invalid path type\n");
+ SetLastErrorByStatus(STATUS_OBJECT_PATH_SYNTAX_BAD);
+ return FALSE;
+ }
+
+ /* Initialize the object attributes */
+ DPRINT("Opening: %wZ\n", &DevicePath);
+ InitializeObjectAttributes(&ObjectAttributes,
+ &DevicePath,
+ OBJ_CASE_INSENSITIVE,
+ NULL,
+ NULL);
+
+ /* Open the path */
+ Status = NtOpenFile(&FileHandle,
+ FILE_READ_ATTRIBUTES | SYNCHRONIZE,
+ &ObjectAttributes,
+ &IoStatusBlock,
+ FILE_SHARE_READ | FILE_SHARE_WRITE,
+ FILE_SYNCHRONOUS_IO_NONALERT);
+ if (!NT_SUCCESS(Status))
+ {
+ /* Fail; couldn't open */
+ DPRINT1("Status: %lx\n", Status);
+ SetLastErrorByStatus(Status);
+ RtlFreeUnicodeString(&NamedPipeName);
+ return(FALSE);
+ }
+
+ /* Now calculate the total length of the structure and allocate it
*/
+ WaitPipeInfoSize = FIELD_OFFSET(FILE_PIPE_WAIT_FOR_BUFFER, Name[0])
+
+ NewName.Length;
+ WaitPipeInfo = RtlAllocateHeap(RtlGetProcessHeap(), 0,
WaitPipeInfoSize);
+
+ /* Check what timeout we got */
+ if (nTimeOut == NMPWAIT_USE_DEFAULT_WAIT)
+ {
+ /* Don't use a timeout */
+ WaitPipeInfo->TimeoutSpecified = FALSE;
+ }
+ else
+ {
+ /* Check if we should wait forever */
+ if (nTimeOut == NMPWAIT_WAIT_FOREVER)
+ {
+ /* Set the max */
+ WaitPipeInfo->Timeout.LowPart = 0;
+ WaitPipeInfo->Timeout.HighPart = 0x80000000;
+ }
+ else
+ {
+ /* Convert to NT format */
+ WaitPipeInfo->Timeout.QuadPart = UInt32x32To64(-10000,
nTimeOut);
+ }
+
+ /* In both cases, we do have a timeout */
+ WaitPipeInfo->TimeoutSpecified = FALSE;
+ }
+
+ /* Set the length and copy the name */
+ WaitPipeInfo->NameLength = NewName.Length;
+ RtlCopyMemory(WaitPipeInfo->Name, NewName.Buffer, NewName.Length);
+
+ /* Get rid of the full name */
+ RtlFreeUnicodeString(&NamedPipeName);
+
+ /* Let NPFS know of our request */
+ Status = NtFsControlFile(FileHandle,
+ NULL,
+ NULL,
+ NULL,
+ &IoStatusBlock,
+ FSCTL_PIPE_WAIT,
+ WaitPipeInfo,
+ WaitPipeInfoSize,
+ NULL,
+ 0);
+
+ /* Free our pipe info data and close the handle */
+ RtlFreeHeap(RtlGetProcessHeap(), 0, WaitPipeInfo);
+ NtClose(FileHandle);
+
+ /* Check the status */
+ if (!NT_SUCCESS(Status))
+ {
+ /* Failure to wait on the pipe */
+ DPRINT1("Status: %lx\n", Status);
+ SetLastErrorByStatus (Status);
+ return FALSE;
+ }
+
+ /* Success */
+ return TRUE;
+}
+#else
/*
* @implemented
*/
@@ -262,8 +450,8 @@
return(TRUE);
}
+#endif
-
/*
* @implemented
*/
@@ -335,7 +523,6 @@
return TRUE;
}
-
/*
* @implemented
*/
Change KEBUGCHECK -> KEBUGCHECKEX
Modified: trunk/reactos/ntoskrnl/ex/work.c
_____
Modified: trunk/reactos/ntoskrnl/ex/work.c
--- trunk/reactos/ntoskrnl/ex/work.c 2005-11-08 19:43:54 UTC (rev
19062)
+++ trunk/reactos/ntoskrnl/ex/work.c 2005-11-08 20:07:41 UTC (rev
19063)
@@ -78,15 +78,21 @@
/* Make sure it returned at right IRQL */
if (KeGetCurrentIrql() != PASSIVE_LEVEL) {
- /* FIXME: Make this an Ex */
- KEBUGCHECK(WORKER_THREAD_RETURNED_AT_BAD_IRQL);
+ KEBUGCHECKEX(WORKER_THREAD_RETURNED_AT_BAD_IRQL,
+ (ULONG_PTR)WorkItem->WorkerRoutine,
+ KeGetCurrentIrql(),
+ (ULONG_PTR)WorkItem->Parameter,
+ (ULONG_PTR)WorkItem);
}
/* Make sure it returned with Impersionation Disabled */
if (PsGetCurrentThread()->ActiveImpersonationInfo) {
- /* FIXME: Make this an Ex */
- KEBUGCHECK(IMPERSONATING_WORKER_THREAD);
+ KEBUGCHECKEX(IMPERSONATING_WORKER_THREAD,
+ (ULONG_PTR)WorkItem->WorkerRoutine,
+ (ULONG_PTR)WorkItem->Parameter,
+ (ULONG_PTR)WorkItem,
+ 0);
}
}
}