[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);
 }