[KMTESTS]
[reactos.git] / 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 }