[ros-diffs] [ion] 24541: - Added some generic table routines to rtlfuncs.h so that they can be used in user-mode. - Implemented RtlInsertElementGenericTable and RtlInsertElementGenericTableFull (Splay-Tree versions). Also implemented a helper function RtlpFindGenericTableNodeOrParent when we're not given one and need to locate it manually. - Defined structure for generic table entries so that we can properly return user data and do the right allocations.
ion at svn.reactos.org
ion at svn.reactos.org
Mon Oct 16 05:19:15 CEST 2006
Author: ion
Date: Mon Oct 16 07:19:14 2006
New Revision: 24541
URL: http://svn.reactos.org/svn/reactos?rev=24541&view=rev
Log:
- Added some generic table routines to rtlfuncs.h so that they can be used in user-mode.
- Implemented RtlInsertElementGenericTable and RtlInsertElementGenericTableFull (Splay-Tree versions). Also implemented a helper function RtlpFindGenericTableNodeOrParent when we're not given one and need to locate it manually.
- Defined structure for generic table entries so that we can properly return user data and do the right allocations.
Modified:
trunk/reactos/include/ndk/rtlfuncs.h
trunk/reactos/lib/rtl/generictable.c
Modified: trunk/reactos/include/ndk/rtlfuncs.h
URL: http://svn.reactos.org/svn/reactos/trunk/reactos/include/ndk/rtlfuncs.h?rev=24541&r1=24540&r2=24541&view=diff
==============================================================================
--- trunk/reactos/include/ndk/rtlfuncs.h (original)
+++ trunk/reactos/include/ndk/rtlfuncs.h Mon Oct 16 07:19:14 2006
@@ -212,51 +212,74 @@
#endif
#endif
-//
-// This macro does nothing in kernel mode
+#ifdef NTOS_KERNEL_RUNTIME
+
+//
+// Executing RTL functions at DISPATCH_LEVEL or higher will result in a
+// bugcheck.
+//
+#define RTL_PAGED_CODE PAGED_CODE
+
+#else
+
+//
+// This macro does nothing in user mode
//
#define RTL_PAGED_CODE NOP_FUNCTION
+#endif
+
//
// RTL Splay Tree Functions
//
NTSYSAPI
PRTL_SPLAY_LINKS
NTAPI
-RtlSplay(PRTL_SPLAY_LINKS Links);
+RtlSplay(
+ IN PRTL_SPLAY_LINKS Links
+);
NTSYSAPI
PRTL_SPLAY_LINKS
NTAPI
-RtlDelete(PRTL_SPLAY_LINKS Links);
+RtlDelete(IN PRTL_SPLAY_LINKS Links
+);
NTSYSAPI
VOID
NTAPI
RtlDeleteNoSplay(
- PRTL_SPLAY_LINKS Links,
- PRTL_SPLAY_LINKS *Root
+ IN PRTL_SPLAY_LINKS Links,
+ OUT PRTL_SPLAY_LINKS *Root
);
NTSYSAPI
PRTL_SPLAY_LINKS
NTAPI
-RtlSubtreeSuccessor(PRTL_SPLAY_LINKS Links);
+RtlSubtreeSuccessor(
+ IN PRTL_SPLAY_LINKS Links
+);
NTSYSAPI
PRTL_SPLAY_LINKS
NTAPI
-RtlSubtreePredecessor(PRTL_SPLAY_LINKS Links);
+RtlSubtreePredecessor(
+ IN PRTL_SPLAY_LINKS Links
+);
NTSYSAPI
PRTL_SPLAY_LINKS
NTAPI
-RtlRealSuccessor(PRTL_SPLAY_LINKS Links);
+RtlRealSuccessor(
+ IN PRTL_SPLAY_LINKS Links
+);
NTSYSAPI
PRTL_SPLAY_LINKS
NTAPI
-RtlRealPredecessor(PRTL_SPLAY_LINKS Links);
+RtlRealPredecessor(
+ IN PRTL_SPLAY_LINKS Links
+);
#define RtlIsLeftChild(Links) \
(RtlLeftChild(RtlParent(Links)) == (PRTL_SPLAY_LINKS)(Links))
@@ -304,16 +327,6 @@
_SplayParent->RightChild = _SplayChild; \
_SplayChild->Parent = _SplayParent; \
}
-#endif
-
-#ifdef NTOS_KERNEL_RUNTIME
-
-//
-// Executing RTL functions at DISPATCH_LEVEL or higher will result in a
-// bugcheck.
-//
-#define RTL_PAGED_CODE PAGED_CODE
-
#endif
//
@@ -2492,6 +2505,35 @@
DbgBreakPoint(VOID);
//
+// Generic Table Functions
+//
+PVOID
+NTAPI
+RtlInsertElementGenericTable(
+ IN PRTL_GENERIC_TABLE Table,
+ IN PVOID Buffer,
+ IN ULONG BufferSize,
+ OUT PBOOLEAN NewElement OPTIONAL
+);
+
+PVOID
+NTAPI
+RtlInsertElementGenericTableFull(
+ IN PRTL_GENERIC_TABLE Table,
+ IN PVOID Buffer,
+ IN ULONG BufferSize,
+ OUT PBOOLEAN NewElement OPTIONAL,
+ IN PVOID NodeOrParent,
+ IN TABLE_SEARCH_RESULT SearchResult
+);
+
+BOOLEAN
+NTAPI
+RtlIsGenericTableEmpty(
+ IN PRTL_GENERIC_TABLE Table
+);
+
+//
// Handle Table Functions
//
NTSYSAPI
Modified: trunk/reactos/lib/rtl/generictable.c
URL: http://svn.reactos.org/svn/reactos/trunk/reactos/lib/rtl/generictable.c?rev=24541&r1=24540&r2=24541&view=diff
==============================================================================
--- trunk/reactos/lib/rtl/generictable.c (original)
+++ trunk/reactos/lib/rtl/generictable.c Mon Oct 16 07:19:14 2006
@@ -14,7 +14,82 @@
#define NDEBUG
#include <debug.h>
-/* FUNCTIONS *****************************************************************/
+/* Internal header for table entries */
+typedef struct _TABLE_ENTRY_HEADER
+{
+ RTL_SPLAY_LINKS SplayLinks;
+ LIST_ENTRY ListEntry;
+ LONGLONG UserData;
+} TABLE_ENTRY_HEADER, *PTABLE_ENTRY_HEADER;
+
+/* PRIVATE FUNCTIONS *********************************************************/
+
+TABLE_SEARCH_RESULT
+NTAPI
+RtlpFindGenericTableNodeOrParent(IN PRTL_GENERIC_TABLE Table,
+ IN PVOID Buffer,
+ OUT PRTL_SPLAY_LINKS *NodeOrParent)
+{
+ PRTL_SPLAY_LINKS CurrentNode, ChildNode;
+ RTL_GENERIC_COMPARE_RESULTS Result;
+
+ /* Quick check to see if the table is empty */
+ if (RtlIsGenericTableEmpty(Table)) return TableEmptyTree;
+
+ /* Set the current node */
+ CurrentNode = Table->TableRoot;
+
+ /* Start compare loop */
+ while (TRUE)
+ {
+ /* Do the compare */
+ Result = Table->CompareRoutine(Table,
+ Buffer,
+ &((PTABLE_ENTRY_HEADER)CurrentNode)->
+ UserData);
+ if (Result == GenericLessThan)
+ {
+ /* We're less, check if this is the left child */
+ if ((ChildNode = RtlLeftChild(CurrentNode)))
+ {
+ /* Continue searching from this node */
+ ChildNode = CurrentNode;
+ }
+ else
+ {
+ /* Otherwise, the element isn't in this tree */
+ *NodeOrParent = CurrentNode;
+ return TableInsertAsLeft;
+ }
+ }
+ else if (Result == GenericGreaterThan)
+ {
+ /* We're more, check if this is the right child */
+ if ((ChildNode = RtlRightChild(CurrentNode)))
+ {
+ /* Continue searching from this node */
+ ChildNode = CurrentNode;
+ }
+ else
+ {
+ /* Otherwise, the element isn't in this tree */
+ *NodeOrParent = CurrentNode;
+ return TableInsertAsRight;
+ }
+ }
+ else
+ {
+ /* We should've found the node */
+ ASSERT(Result == GenericEqual);
+
+ /* Return node found */
+ *NodeOrParent = CurrentNode;
+ return TableFoundNode;
+ }
+ }
+}
+
+/* SPLAY FUNCTIONS ***********************************************************/
/*
* @implemented
@@ -49,8 +124,19 @@
IN ULONG BufferSize,
OUT PBOOLEAN NewElement OPTIONAL)
{
- UNIMPLEMENTED;
- return 0;
+ PRTL_SPLAY_LINKS NodeOrParent;
+ TABLE_SEARCH_RESULT Result;
+
+ /* Get the splay links and table search result immediately */
+ Result = RtlpFindGenericTableNodeOrParent(Table, Buffer, &NodeOrParent);
+
+ /* Now call the routine to do the full insert */
+ return RtlInsertElementGenericTableFull(Table,
+ Buffer,
+ BufferSize,
+ NewElement,
+ NodeOrParent,
+ Result);
}
/*
@@ -65,8 +151,70 @@
IN PVOID NodeOrParent,
IN TABLE_SEARCH_RESULT SearchResult)
{
- UNIMPLEMENTED;
- return 0;
+ PRTL_SPLAY_LINKS NewNode;
+
+ /* Check if the entry wasn't already found */
+ if (SearchResult != TableFoundNode)
+ {
+ /* We're doing an allocation, sanity check */
+ ASSERT(Table->NumberGenericTableElements != (MAXULONG - 1));
+
+ /* Allocate a node */
+ NewNode = Table->AllocateRoutine(Table,
+ BufferSize +
+ FIELD_OFFSET(TABLE_ENTRY_HEADER,
+ UserData));
+ if (!NewNode)
+ {
+ /* No memory or other allocation error, fail */
+ if (NewElement) *NewElement = FALSE;
+ return NULL;
+ }
+
+ /* Initialize the new inserted element */
+ RtlInitializeSplayLinks(NewNode);
+ InsertTailList(&Table->InsertOrderList,
+ &((PTABLE_ENTRY_HEADER)NewNode)->ListEntry);
+
+ /* Increase element count */
+ Table->NumberGenericTableElements++;
+
+ /* Check where we should insert the entry */
+ if (SearchResult == TableEmptyTree)
+ {
+ /* This is the new root node */
+ Table->TableRoot = NewNode;
+ }
+ else if (SearchResult == TableInsertAsLeft)
+ {
+ /* Insert it left */
+ RtlInsertAsLeftChild(NodeOrParent, NewNode);
+ }
+ else
+ {
+ /* Right node */
+ RtlInsertAsRightChild(NodeOrParent, NewNode);
+ }
+
+ /* Copy user buffer */
+ RtlCopyMemory(&((PTABLE_ENTRY_HEADER)NewNode)->UserData,
+ Buffer,
+ BufferSize);
+ }
+ else
+ {
+ /* Return the node we already found */
+ NewNode = NodeOrParent;
+ }
+
+ /* Splay the tree */
+ Table->TableRoot = RtlSplay(NewNode);
+
+ /* Return status */
+ if (NewElement) *NewElement = (SearchResult == TableFoundNode);
+
+ /* Return pointer to user data */
+ return &((PTABLE_ENTRY_HEADER)NewNode)->UserData;
}
/*
@@ -289,6 +437,7 @@
RtlEnumerateGenericTableWithoutSplayingAvl(IN PRTL_AVL_TABLE Table,
IN OUT PVOID *RestartKey)
{
+ /* FIXME! */
return RtlEnumerateGenericTableWithoutSplayingAvl(Table, RestartKey);
}
More information about the Ros-diffs
mailing list