[SKIPLIST]
[reactos.git] / reactos / lib / skiplist / skiplist_test.c
1 /*
2 * PROJECT: Skiplist implementation for the ReactOS Project
3 * LICENSE: GNU LGPL v2.1 or any later version as published by the Free Software Foundation
4 * PURPOSE: A simple program for testing the Skiplist implementation
5 * COPYRIGHT: Copyright 2015 Colin Finck <colin@reactos.org>
6 */
7
8 #include <windows.h>
9 #include <stdio.h>
10 #include "skiplist.h"
11
12 void
13 DumpSkiplist(PSKIPLIST Skiplist)
14 {
15 CHAR i;
16 DWORD j;
17 PSKIPLIST_NODE pNode;
18
19 printf("======= DUMPING SKIPLIST =======\n");
20
21 for (i = Skiplist->MaximumLevel + 1; --i >= 0;)
22 {
23 pNode = &Skiplist->Head;
24 printf("H");
25
26 while (pNode->Next[i])
27 {
28 printf("-");
29
30 // By using the Distance array for painting the lines, we verify both the links and the distances for correctness.
31 for (j = 1; j < pNode->Distance[i]; j++)
32 printf("---");
33
34 printf("%02lu", (DWORD)pNode->Next[i]->Element);
35
36 pNode = pNode->Next[i];
37 }
38
39 printf("\n");
40 }
41
42 printf("================================\n\n");
43 }
44
45 PVOID WINAPI
46 MyAlloc(DWORD Size)
47 {
48 return HeapAlloc(GetProcessHeap(), 0, Size);
49 }
50
51 int WINAPI
52 MyCompare(PVOID A, PVOID B)
53 {
54 return (DWORD)A - (DWORD)B;
55 }
56
57 void WINAPI
58 MyFree(PVOID Ptr)
59 {
60 HeapFree(GetProcessHeap(), 0, Ptr);
61 }
62
63 int
64 main()
65 {
66 DWORD Element;
67 DWORD ElementIndex;
68 DWORD i;
69 SKIPLIST Skiplist;
70
71 system("mode con cols=300");
72 InitializeSkiplist(&Skiplist, MyAlloc, MyCompare, MyFree);
73
74 // Insert some random elements with random numbers.
75 for (i = 0; i < 40; i++)
76 InsertElementSkiplist(&Skiplist, (PVOID)(rand() % 100));
77
78 // Delete all with index 0 to 29.
79 for (i = 0; i < 30; i++)
80 DeleteElementSkiplist(&Skiplist, (PVOID)i);
81
82 // Insert some more random elements.
83 for (i = 0; i < 40; i++)
84 InsertElementSkiplist(&Skiplist, (PVOID)(rand() % 100));
85
86 // Check if an element with number 44 is in the list and output its index.
87 Element = (DWORD)LookupElementSkiplist(&Skiplist, (PVOID)44, &ElementIndex);
88 printf("Element = %lu, ElementIndex = %lu\n\n", Element, ElementIndex);
89
90 DumpSkiplist(&Skiplist);
91
92 return 0;
93 }