kmtests/rtl/RtlSplayTree.c

   1 /*
   2  * PROJECT:         ReactOS kernel-mode tests
   3  * LICENSE:         LGPLv2+ - See COPYING.LIB in the top level directory
   4  * PURPOSE:         Kernel-Mode Test Suite RtlGenericTable
   5  * PROGRAMMER:      arty
   6  */
   7
   8 #define KMT_EMULATE_KERNEL
   9 #include <kmt_test.h>
  10
  11 #define NDEBUG
  12 #include <debug.h>
  13
  14 /* HACK: missing in rtlfuncs.h */
  15 #if defined KMT_USER_MODE && !defined RTL_USE_AVL_TABLES
  16 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);
  17 NTSYSAPI PVOID NTAPI RtlInsertElementGenericTable(IN PRTL_GENERIC_TABLE Table, IN PVOID Buffer, IN CLONG BufferSize, OUT PBOOLEAN NewElement OPTIONAL);
  18 NTSYSAPI BOOLEAN NTAPI RtlDeleteElementGenericTable(IN PRTL_GENERIC_TABLE Table, IN PVOID Buffer);
  19 NTSYSAPI PVOID NTAPI RtlLookupElementGenericTable(IN PRTL_GENERIC_TABLE Table, IN PVOID Buffer);
  20 NTSYSAPI PVOID NTAPI RtlEnumerateGenericTable(IN PRTL_GENERIC_TABLE Table, IN BOOLEAN Restart);
  21 NTSYSAPI PVOID NTAPI RtlGetElementGenericTable(IN PRTL_GENERIC_TABLE Table, IN ULONG I);
  22 NTSYSAPI ULONG NTAPI RtlNumberGenericTableElements(IN PRTL_GENERIC_TABLE Table);
  23 #endif
  24
  25 static LIST_ENTRY Allocations;
  26
  27 static RTL_GENERIC_COMPARE_RESULTS NTAPI
  28 CompareCharTable(PRTL_GENERIC_TABLE Table, PVOID A, PVOID B)
  29 {
  30     RTL_GENERIC_COMPARE_RESULTS Result = (*((PCHAR)A) < *((PCHAR)B)) ? GenericLessThan :
  31         (*((PCHAR)A) > *((PCHAR)B)) ? GenericGreaterThan :
  32         GenericEqual;
  33     return Result;
  34 }
  35
  36 static PVOID NTAPI
  37 AllocRoutine(PRTL_GENERIC_TABLE Table, CLONG ByteSize)
  38 {
  39     PLIST_ENTRY Entry = ExAllocatePool
  40         (NonPagedPool, sizeof(LIST_ENTRY) + ByteSize);
  41     InsertTailList(&Allocations, Entry);
  42     return &Entry[1];
  43 }
  44
  45 static VOID NTAPI
  46 FreeRoutine(PRTL_GENERIC_TABLE Table, PVOID Buffer)
  47 {
  48     PLIST_ENTRY Entry = (PLIST_ENTRY)(((PCHAR)Buffer) - sizeof(LIST_ENTRY));
  49     RemoveEntryList(Entry);
  50     ExFreePool(Entry);
  51 }
  52
  53 static void RtlSplayTreeTest()
  54 {
  55     ULONG i, del;
  56     PCHAR Ch;
  57     CHAR Text[] = "the quick_brown!fOx-jUmp3d/0vER+THe^lazy.D@g";
  58     CHAR NewE[] = "11111111111111111111111111111111110111111111";
  59     RTL_GENERIC_TABLE Table;
  60     RtlInitializeGenericTable
  61         (&Table,
  62          CompareCharTable,
  63          AllocRoutine,
  64          FreeRoutine,
  65          NULL);
  66     for (i = 0; Text[i]; i++) {
  67         BOOLEAN WasNew;
  68         Ch = (PCHAR)RtlInsertElementGenericTable
  69             (&Table,
  70              &Text[i],
  71              sizeof(Text[i]),
  72              &WasNew);
  73         ok(Ch && *Ch == Text[i], "Copy character into node\n");
  74         ok(WasNew == (NewE[i] == '1'), "Character newness didn't match\n");
  75     }
  76     for (Ch = (PCHAR)RtlEnumerateGenericTable(&Table, TRUE), i = 0;
  77          Ch;
  78          Ch = (PCHAR)RtlEnumerateGenericTable(&Table, FALSE), i++) {
  79         ok(strchr(Text, *Ch) != NULL, "Nonexistent character\n");
  80     }
  81     ok(RtlNumberGenericTableElements(&Table) == strlen(Text) - 1, "Not the right number of elements\n");
  82     ok(RtlLookupElementGenericTable(&Table, "q") != NULL, "Could not lookup q\n");
  83     ok(!RtlLookupElementGenericTable(&Table, "#"), "Found a character that shouldn't appear\n");
  84     ok(strlen(Text) == i + 1, "Didn't enumerate enough characters\n");
  85     del = 0;
  86     for (i = 0; Text[i]; i++) {
  87         if (NewE[i] == '1') {
  88             BOOLEAN WasDeleted;
  89             WasDeleted = RtlDeleteElementGenericTable(&Table, &Text[i]);
  90             del += WasDeleted;
  91         }
  92     }
  93     ok(!RtlNumberGenericTableElements(&Table), "Not zero elements\n");
  94     ok(!RtlGetElementGenericTable(&Table, 0), "Elements left when we removed them all\n");
  95     ok(strlen(Text) == del + 1, "Deleted too many times\n");
  96     ok(IsListEmpty(&Allocations), "Didn't free all memory\n");
  97 }
  98
  99 START_TEST(RtlSplayTree)
 100 {
 101     InitializeListHead(&Allocations);
 102     RtlSplayTreeTest();
 103 }