[ros-diffs] [tfaber] 53046: [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

Author: tfaber
Date: Wed Aug  3 11:21:35 2011
New Revision: 53046

URL: http://svn.reactos.org/svn/reactos?rev=53046&view=rev
Log:
[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

Added:
    branches/GSoC_2011/KMTestSuite/kmtests/rtl/RtlAvlTree.c   (with props)
    branches/GSoC_2011/KMTestSuite/kmtests/rtl/RtlSplayTree.c   (with props)
Modified:
    branches/GSoC_2011/KMTestSuite/kmtests/CMakeLists.txt
    branches/GSoC_2011/KMTestSuite/kmtests/kmtest.rbuild
    branches/GSoC_2011/KMTestSuite/kmtests/kmtest/testlist.c
    branches/GSoC_2011/KMTestSuite/kmtests/kmtest_drv.rbuild
    branches/GSoC_2011/KMTestSuite/kmtests/kmtest_drv/testlist.c

Modified: branches/GSoC_2011/KMTestSuite/kmtests/CMakeLists.txt
URL:
http://svn.reactos.org/svn/reactos/branches/GSoC_2011/KMTestSuite/kmtests/C…
==============================================================================
--- branches/GSoC_2011/KMTestSuite/kmtests/CMakeLists.txt [iso-8859-1] (original)
+++ branches/GSoC_2011/KMTestSuite/kmtests/CMakeLists.txt [iso-8859-1] Wed Aug  3 11:21:35
2011
@@ -32,7 +32,9 @@
     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 @@
     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)

Modified: branches/GSoC_2011/KMTestSuite/kmtests/kmtest.rbuild
URL:
http://svn.reactos.org/svn/reactos/branches/GSoC_2011/KMTestSuite/kmtests/k…
==============================================================================
--- branches/GSoC_2011/KMTestSuite/kmtests/kmtest.rbuild [iso-8859-1] (original)
+++ branches/GSoC_2011/KMTestSuite/kmtests/kmtest.rbuild [iso-8859-1] Wed Aug  3 11:21:35
2011
@@ -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>

Modified: branches/GSoC_2011/KMTestSuite/kmtests/kmtest/testlist.c
URL:
http://svn.reactos.org/svn/reactos/branches/GSoC_2011/KMTestSuite/kmtests/k…
==============================================================================
--- branches/GSoC_2011/KMTestSuite/kmtests/kmtest/testlist.c [iso-8859-1] (original)
+++ branches/GSoC_2011/KMTestSuite/kmtests/kmtest/testlist.c [iso-8859-1] Wed Aug  3
11:21:35 2011
@@ -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 },
 };

Modified: branches/GSoC_2011/KMTestSuite/kmtests/kmtest_drv.rbuild
URL:
http://svn.reactos.org/svn/reactos/branches/GSoC_2011/KMTestSuite/kmtests/k…
==============================================================================
--- branches/GSoC_2011/KMTestSuite/kmtests/kmtest_drv.rbuild [iso-8859-1] (original)
+++ branches/GSoC_2011/KMTestSuite/kmtests/kmtest_drv.rbuild [iso-8859-1] Wed Aug  3
11:21:35 2011
@@ -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">

Modified: branches/GSoC_2011/KMTestSuite/kmtests/kmtest_drv/testlist.c
URL:
http://svn.reactos.org/svn/reactos/branches/GSoC_2011/KMTestSuite/kmtests/k…
==============================================================================
--- branches/GSoC_2011/KMTestSuite/kmtests/kmtest_drv/testlist.c [iso-8859-1] (original)
+++ branches/GSoC_2011/KMTestSuite/kmtests/kmtest_drv/testlist.c [iso-8859-1] Wed Aug  3
11:21:35 2011
@@ -5,7 +5,6 @@
  * PROGRAMMER:      Thomas Faber &lt;thfabba(a)gmx.de&gt;
  */
 
-#include <ntddk.h>
 #include <kmt_test.h>
 
 KMT_TESTFUNC Test_Example;
@@ -27,7 +26,9 @@
 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 @@
     { "KeProcessor",                        Test_KeProcessor },
     { "-KernelType",                        Test_KernelType },
     { "ObCreate",                           Test_ObCreate },
+    { "RtlAvlTreeKM",                       Test_RtlAvlTree },
     { "RtlMemoryKM",                        Test_RtlMemory },
+    { "RtlSplayTreeKM",                     Test_RtlSplayTree },
     { NULL,                                 NULL }
 };

Added: branches/GSoC_2011/KMTestSuite/kmtests/rtl/RtlAvlTree.c
URL:
http://svn.reactos.org/svn/reactos/branches/GSoC_2011/KMTestSuite/kmtests/r…
==============================================================================
--- branches/GSoC_2011/KMTestSuite/kmtests/rtl/RtlAvlTree.c (added)
+++ branches/GSoC_2011/KMTestSuite/kmtests/rtl/RtlAvlTree.c [iso-8859-1] Wed Aug  3
11:21:35 2011
@@ -1,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"

Propchange: branches/GSoC_2011/KMTestSuite/kmtests/rtl/RtlAvlTree.c
------------------------------------------------------------------------------
    svn:eol-style = native

Added: branches/GSoC_2011/KMTestSuite/kmtests/rtl/RtlSplayTree.c
URL:
http://svn.reactos.org/svn/reactos/branches/GSoC_2011/KMTestSuite/kmtests/r…
==============================================================================
--- branches/GSoC_2011/KMTestSuite/kmtests/rtl/RtlSplayTree.c (added)
+++ branches/GSoC_2011/KMTestSuite/kmtests/rtl/RtlSplayTree.c [iso-8859-1] Wed Aug  3
11:21:35 2011
@@ -1,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();
+}

Propchange: branches/GSoC_2011/KMTestSuite/kmtests/rtl/RtlSplayTree.c
------------------------------------------------------------------------------
    svn:eol-style = native