rostests/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 static LIST_ENTRY Allocations;
  15
  16 static RTL_GENERIC_COMPARE_RESULTS NTAPI
  17 CompareCharTable(PRTL_GENERIC_TABLE Table, PVOID A, PVOID B)
  18 {
  19     RTL_GENERIC_COMPARE_RESULTS Result = (*((PCHAR)A) < *((PCHAR)B)) ? GenericLessThan :
  20         (*((PCHAR)A) > *((PCHAR)B)) ? GenericGreaterThan :
  21         GenericEqual;
  22     return Result;
  23 }
  24
  25 static PVOID NTAPI
  26 AllocRoutine(PRTL_GENERIC_TABLE Table, CLONG ByteSize)
  27 {
  28     PLIST_ENTRY Entry = ExAllocatePool
  29         (NonPagedPool, sizeof(LIST_ENTRY) + ByteSize);
  30     InsertTailList(&Allocations, Entry);
  31     return &Entry[1];
  32 }
  33
  34 static VOID NTAPI
  35 FreeRoutine(PRTL_GENERIC_TABLE Table, PVOID Buffer)
  36 {
  37     PLIST_ENTRY Entry = (PLIST_ENTRY)(((PCHAR)Buffer) - sizeof(LIST_ENTRY));
  38     RemoveEntryList(Entry);
  39     ExFreePool(Entry);
  40 }
  41
  42 static void RtlSplayTreeTest()
  43 {
  44     ULONG i, del;
  45     PCHAR Ch;
  46     CHAR Text[] = "the quick_brown!fOx-jUmp3d/0vER+THe^lazy.D@g";
  47     CHAR NewE[] = "11111111111111111111111111111111110111111111";
  48     RTL_GENERIC_TABLE Table;
  49     RtlInitializeGenericTable
  50         (&Table,
  51          CompareCharTable,
  52          AllocRoutine,
  53          FreeRoutine,
  54          NULL);
  55     for (i = 0; Text[i]; i++) {
  56         BOOLEAN WasNew;
  57         Ch = (PCHAR)RtlInsertElementGenericTable
  58             (&Table,
  59              &Text[i],
  60              sizeof(Text[i]),
  61              &WasNew);
  62         ok(Ch && *Ch == Text[i], "Copy character into node\n");
  63         ok(WasNew == (NewE[i] == '1'),
  64            "Character newness didn't match for char %u: '%c'\n",
  65            i, Text[i]);
  66     }
  67     for (Ch = (PCHAR)RtlEnumerateGenericTable(&Table, TRUE), i = 0;
  68          Ch;
  69          Ch = (PCHAR)RtlEnumerateGenericTable(&Table, FALSE), i++) {
  70         ok(strchr(Text, *Ch) != NULL, "Nonexistent character\n");
  71     }
  72     ok(RtlNumberGenericTableElements(&Table) == strlen(Text) - 1, "Not the right number of elements\n");
  73     ok(RtlLookupElementGenericTable(&Table, "q") != NULL, "Could not lookup q\n");
  74     ok(!RtlLookupElementGenericTable(&Table, "#"), "Found a character that shouldn't appear\n");
  75     ok(strlen(Text) == i + 1, "Didn't enumerate enough characters\n");
  76     del = 0;
  77     for (i = 0; Text[i]; i++) {
  78         if (NewE[i] == '1') {
  79             BOOLEAN WasDeleted;
  80             WasDeleted = RtlDeleteElementGenericTable(&Table, &Text[i]);
  81             del += WasDeleted;
  82         }
  83     }
  84     ok(!RtlNumberGenericTableElements(&Table), "Not zero elements\n");
  85     ok(!RtlGetElementGenericTable(&Table, 0), "Elements left when we removed them all\n");
  86     ok(strlen(Text) == del + 1, "Deleted too many times\n");
  87     ok(IsListEmpty(&Allocations), "Didn't free all memory\n");
  88 }
  89
  90 START_TEST(RtlSplayTree)
  91 {
  92     InitializeListHead(&Allocations);
  93     RtlSplayTreeTest();
  94 }