1 /* 2 * PROJECT: Skiplist implementation for the ReactOS Project 3 * LICENSE: GPL-2.0+ (https://spdx.org/licenses/GPL-2.0+) 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("%02Iu", (DWORD_PTR)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_PTR)A - (DWORD_PTR)B; 55 } 56 57 void WINAPI 58 MyFree(PVOID Ptr) 59 { 60 HeapFree(GetProcessHeap(), 0, Ptr); 61 } 62 63 int 64 main() 65 { 66 PVOID Element; 67 DWORD ElementIndex; 68 DWORD i; 69 SKIPLIST Skiplist; 70 PSKIPLIST_NODE pNode; 71 72 system("mode con cols=300"); 73 InitializeSkiplist(&Skiplist, MyAlloc, MyCompare, MyFree); 74 75 // Insert some random elements with random numbers. 76 for (i = 0; i < 40; i++) 77 InsertElementSkiplist(&Skiplist, UlongToPtr(rand() % 100)); 78 79 // Delete all with index 0 to 29. 80 for (i = 0; i < 30; i++) 81 DeleteElementSkiplist(&Skiplist, UlongToPtr(i)); 82 83 // Insert some more random elements. 84 for (i = 0; i < 40; i++) 85 InsertElementSkiplist(&Skiplist, UlongToPtr(rand() % 100)); 86 87 // Output the third element (with zero-based index 2). 88 pNode = LookupNodeByIndexSkiplist(&Skiplist, 2); 89 printf("Element = %Iu for index 2\n", (DWORD_PTR)pNode->Element); 90 91 // Check if an element with number 44 is in the list and output its index. 92 Element = LookupElementSkiplist(&Skiplist, UlongToPtr(44), &ElementIndex); 93 printf("Element = %p, ElementIndex = %lu\n\n", Element, ElementIndex); 94 95 DumpSkiplist(&Skiplist); 96 97 return 0; 98 } 99