[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.
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=... ============================================================================== --- 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=... ============================================================================== --- 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); }
-
ion＠svn.reactos.org