[KMTESTS]

- add RtlSplayTree test. Patch by arty (hacks by me ;])
- add RtlAvlTree test using the same code
- add kmtest_drivers and kmtest_all build targets

svn path=/branches/GSoC_2011/KMTestSuite/; revision=53046

diff --git a/kmtests/CMakeLists.txt b/kmtests/CMakeLists.txt
index 22d4d21..f024f5d 100644 (file)
--- a/kmtests/CMakeLists.txt
+++ b/kmtests/CMakeLists.txt
@@ -32,7 +32,9 @@ list(APPEND KMTEST_DRV_SOURCE
     ntos_ke/KeProcessor.c
     ntos_ke/KeSpinLock.c
     ntos_ob/ObCreate.c
+    rtl/RtlAvlTree.c
     rtl/RtlMemory.c
+    rtl/RtlSplayTree.c
 
     kmtest_drv/kmtest_drv.rc)
 
@@ -63,13 +65,24 @@ list(APPEND KMTEST_SOURCE
     kmtest/testlist.c
 
     example/Example_user.c
+    rtl/RtlAvlTree.c
     rtl/RtlMemory.c
+    rtl/RtlSplayTree.c
 
     kmtest/kmtest.rc)
 
 add_executable(kmtest ${KMTEST_SOURCE})
 set_module_type(kmtest win32cui)
-add_importlibs(kmtest advapi32 msvcrt kernel32)
+add_importlibs(kmtest advapi32 msvcrt kernel32 ntdll)
 set_property(TARGET kmtest PROPERTY COMPILE_DEFINITIONS KMT_USER_MODE)
 
 add_cd_file(TARGET kmtest DESTINATION reactos/bin FOR all)
+
+#
+# Group targets
+#
+add_custom_target(kmtest_drivers)
+add_dependencies(kmtest_drivers kmtest_drv example_drv)
+
+add_custom_target(kmtest_all)
+add_dependencies(kmtest_all kmtest_drivers kmtest)

diff --git a/kmtests/kmtest.rbuild b/kmtests/kmtest.rbuild
index b7464ea..16fbd77 100644 (file)
--- a/kmtests/kmtest.rbuild
+++ b/kmtests/kmtest.rbuild
@@ -1,6 +1,7 @@
 <module name="kmtest" type="win32cui" installbase="bin" installname="kmtest.exe">
        <include base="kmtest">include</include>
        <library>advapi32</library>
+       <library>ntdll</library>
        <define name="KMT_USER_MODE" />
        <directory name="kmtest">
                <file>kmtest.c</file>
@@ -12,6 +13,8 @@
                <file>Example_user.c</file>
        </directory>
        <directory name="rtl">
+               <file>RtlAvlTree.c</file>
                <file>RtlMemory.c</file>
+               <file>RtlSplayTree.c</file>
        </directory>
 </module>

diff --git a/kmtests/kmtest/testlist.c b/kmtests/kmtest/testlist.c
index 9f315d3..d634ac9 100644 (file)
--- a/kmtests/kmtest/testlist.c
+++ b/kmtests/kmtest/testlist.c
@@ -8,12 +8,16 @@
 #include <kmt_test.h>
 
 KMT_TESTFUNC Test_Example;
+KMT_TESTFUNC Test_RtlAvlTree;
 KMT_TESTFUNC Test_RtlMemory;
+KMT_TESTFUNC Test_RtlSplayTree;
 
 /* tests with a leading '-' will not be listed */
 const KMT_TEST TestList[] =
 {
     { "Example",            Test_Example },
+    { "RtlAvlTree",         Test_RtlAvlTree },
     { "RtlMemory",          Test_RtlMemory },
+    { "RtlSplayTree",       Test_RtlSplayTree },
     { NULL,                 NULL },
 };

diff --git a/kmtests/kmtest_drv.rbuild b/kmtests/kmtest_drv.rbuild
index 15e39da..66def9b 100644 (file)
--- a/kmtests/kmtest_drv.rbuild
+++ b/kmtests/kmtest_drv.rbuild
@@ -42,7 +42,9 @@
                <file>ObCreate.c</file>
        </directory>
        <directory name="rtl">
+               <file>RtlAvlTree.c</file>
                <file>RtlMemory.c</file>
+               <file>RtlSplayTree.c</file>
        </directory>
 </module>
 <module name="kmtest_printf" type="staticlibrary">

diff --git a/kmtests/kmtest_drv/testlist.c b/kmtests/kmtest_drv/testlist.c
index 7310149..330eb05 100644 (file)
--- a/kmtests/kmtest_drv/testlist.c
+++ b/kmtests/kmtest_drv/testlist.c
@@ -5,7 +5,6 @@
  * PROGRAMMER:      Thomas Faber <thfabba@gmx.de>
  */
 
-#include <ntddk.h>
 #include <kmt_test.h>
 
 KMT_TESTFUNC Test_Example;
@@ -27,7 +26,9 @@ KMT_TESTFUNC Test_KeIrql;
 KMT_TESTFUNC Test_KeProcessor;
 KMT_TESTFUNC Test_KernelType;
 KMT_TESTFUNC Test_ObCreate;
+KMT_TESTFUNC Test_RtlAvlTree;
 KMT_TESTFUNC Test_RtlMemory;
+KMT_TESTFUNC Test_RtlSplayTree;
 
 const KMT_TEST TestList[] =
 {
@@ -50,6 +51,8 @@ const KMT_TEST TestList[] =
     { "KeProcessor",                        Test_KeProcessor },
     { "-KernelType",                        Test_KernelType },
     { "ObCreate",                           Test_ObCreate },
+    { "RtlAvlTreeKM",                       Test_RtlAvlTree },
     { "RtlMemoryKM",                        Test_RtlMemory },
+    { "RtlSplayTreeKM",                     Test_RtlSplayTree },
     { NULL,                                 NULL }
 };

diff --git a/kmtests/rtl/RtlAvlTree.c b/kmtests/rtl/RtlAvlTree.c
new file mode 100644 (file)
index 0000000..c8e3057
--- /dev/null
+++ b/kmtests/rtl/RtlAvlTree.c
@@ -0,0 +1,34 @@
+/* HACK: broken ntddk.h */
+#ifdef KMT_KERNEL_MODE
+typedef struct _RTL_SPLAY_LINKS {
+  struct _RTL_SPLAY_LINKS *Parent;
+  struct _RTL_SPLAY_LINKS *LeftChild;
+  struct _RTL_SPLAY_LINKS *RightChild;
+} RTL_SPLAY_LINKS, *PRTL_SPLAY_LINKS;
+#endif
+
+#define RTL_USE_AVL_TABLES
+#define KMT_EMULATE_KERNEL
+#include <kmt_test.h>
+
+#if defined KMT_USER_MODE
+/* HACK: missing in rtltypes.h */
+#undef RTL_GENERIC_TABLE
+#undef PRTL_GENERIC_TABLE
+
+#define RTL_GENERIC_TABLE               RTL_AVL_TABLE
+#define PRTL_GENERIC_TABLE              PRTL_AVL_TABLE
+
+/* HACK: missing in rtlfuncs.h */
+#define RtlInitializeGenericTable       RtlInitializeGenericTableAvl
+#define RtlInsertElementGenericTable    RtlInsertElementGenericTableAvl
+#define RtlDeleteElementGenericTable    RtlDeleteElementGenericTableAvl
+#define RtlLookupElementGenericTable    RtlLookupElementGenericTableAvl
+#define RtlEnumerateGenericTable        RtlEnumerateGenericTableAvl
+#define RtlGetElementGenericTable       RtlGetElementGenericTableAvl
+#define RtlNumberGenericTableElements   RtlNumberGenericTableElementsAvl
+#endif
+
+/* this is a little hacky, but better than duplicating the code (for now) */
+#define Test_RtlSplayTree Test_RtlAvlTree
+#include "RtlSplayTree.c"

diff --git a/kmtests/rtl/RtlSplayTree.c b/kmtests/rtl/RtlSplayTree.c
new file mode 100644 (file)
index 0000000..a967275
--- /dev/null
+++ b/kmtests/rtl/RtlSplayTree.c
@@ -0,0 +1,103 @@
+/*
+ * PROJECT:         ReactOS kernel-mode tests
+ * LICENSE:         LGPLv2+ - See COPYING.LIB in the top level directory
+ * PURPOSE:         Kernel-Mode Test Suite RtlGenericTable
+ * PROGRAMMER:      arty
+ */
+
+#define KMT_EMULATE_KERNEL
+#include <kmt_test.h>
+
+#define NDEBUG
+#include <debug.h>
+
+/* HACK: missing in rtlfuncs.h */
+#if defined KMT_USER_MODE && !defined RTL_USE_AVL_TABLES
+NTSYSAPI VOID NTAPI RtlInitializeGenericTable(OUT PRTL_GENERIC_TABLE Table, IN PRTL_GENERIC_COMPARE_ROUTINE CompareRoutine, IN PRTL_GENERIC_ALLOCATE_ROUTINE AllocateRoutine, IN PRTL_GENERIC_FREE_ROUTINE FreeRoutine, IN PVOID TableContext OPTIONAL);
+NTSYSAPI PVOID NTAPI RtlInsertElementGenericTable(IN PRTL_GENERIC_TABLE Table, IN PVOID Buffer, IN CLONG BufferSize, OUT PBOOLEAN NewElement OPTIONAL);
+NTSYSAPI BOOLEAN NTAPI RtlDeleteElementGenericTable(IN PRTL_GENERIC_TABLE Table, IN PVOID Buffer);
+NTSYSAPI PVOID NTAPI RtlLookupElementGenericTable(IN PRTL_GENERIC_TABLE Table, IN PVOID Buffer);
+NTSYSAPI PVOID NTAPI RtlEnumerateGenericTable(IN PRTL_GENERIC_TABLE Table, IN BOOLEAN Restart);
+NTSYSAPI PVOID NTAPI RtlGetElementGenericTable(IN PRTL_GENERIC_TABLE Table, IN ULONG I);
+NTSYSAPI ULONG NTAPI RtlNumberGenericTableElements(IN PRTL_GENERIC_TABLE Table);
+#endif
+
+static LIST_ENTRY Allocations;
+
+static RTL_GENERIC_COMPARE_RESULTS NTAPI
+CompareCharTable(PRTL_GENERIC_TABLE Table, PVOID A, PVOID B)
+{
+    RTL_GENERIC_COMPARE_RESULTS Result = (*((PCHAR)A) < *((PCHAR)B)) ? GenericLessThan :
+        (*((PCHAR)A) > *((PCHAR)B)) ? GenericGreaterThan :
+        GenericEqual;
+    return Result;
+}
+
+static PVOID NTAPI
+AllocRoutine(PRTL_GENERIC_TABLE Table, CLONG ByteSize)
+{
+    PLIST_ENTRY Entry = ExAllocatePool
+        (NonPagedPool, sizeof(LIST_ENTRY) + ByteSize);
+    InsertTailList(&Allocations, Entry);
+    return &Entry[1];
+}
+
+static VOID NTAPI
+FreeRoutine(PRTL_GENERIC_TABLE Table, PVOID Buffer)
+{
+    PLIST_ENTRY Entry = (PLIST_ENTRY)(((PCHAR)Buffer) - sizeof(LIST_ENTRY));
+    RemoveEntryList(Entry);
+    ExFreePool(Entry);
+}
+
+static void RtlSplayTreeTest()
+{
+    ULONG i, del;
+    PCHAR Ch;
+    CHAR Text[] = "the quick_brown!fOx-jUmp3d/0vER+THe^lazy.D@g";
+    CHAR NewE[] = "11111111111111111111111111111111110111111111";
+    RTL_GENERIC_TABLE Table;
+    RtlInitializeGenericTable
+        (&Table,
+         CompareCharTable,
+         AllocRoutine,
+         FreeRoutine,
+         NULL);
+    for (i = 0; Text[i]; i++) {
+        BOOLEAN WasNew;
+        Ch = (PCHAR)RtlInsertElementGenericTable
+            (&Table,
+             &Text[i],
+             sizeof(Text[i]),
+             &WasNew);
+        ok(Ch && *Ch == Text[i], "Copy character into node\n");
+        ok(WasNew == (NewE[i] == '1'), "Character newness didn't match\n");
+    }
+    for (Ch = (PCHAR)RtlEnumerateGenericTable(&Table, TRUE), i = 0;
+         Ch;
+         Ch = (PCHAR)RtlEnumerateGenericTable(&Table, FALSE), i++) {
+        ok(strchr(Text, *Ch) != NULL, "Nonexistent character\n");
+    }
+    ok(RtlNumberGenericTableElements(&Table) == strlen(Text) - 1, "Not the right number of elements\n");
+    ok(RtlLookupElementGenericTable(&Table, "q") != NULL, "Could not lookup q\n");
+    ok(!RtlLookupElementGenericTable(&Table, "#"), "Found a character that shouldn't appear\n");
+    ok(strlen(Text) == i + 1, "Didn't enumerate enough characters\n");
+    del = 0;
+    for (i = 0; Text[i]; i++) {
+        if (NewE[i] == '1') {
+            BOOLEAN WasDeleted;
+            WasDeleted = RtlDeleteElementGenericTable(&Table, &Text[i]);
+            del += WasDeleted;
+        }
+    }
+    ok(!RtlNumberGenericTableElements(&Table), "Not zero elements\n");
+    ok(!RtlGetElementGenericTable(&Table, 0), "Elements left when we removed them all\n");
+    ok(strlen(Text) == del + 1, "Deleted too many times\n");
+    ok(IsListEmpty(&Allocations), "Didn't free all memory\n");
+}
+
+START_TEST(RtlSplayTree)
+{
+    InitializeListHead(&Allocations);
+    RtlSplayTreeTest();
+}