reactos/sdk/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     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, (PVOID)(rand() % 100));
  78
  79     // Delete all with index 0 to 29.
  80     for (i = 0; i < 30; i++)
  81         DeleteElementSkiplist(&Skiplist, (PVOID)i);
  82
  83     // Insert some more random elements.
  84     for (i = 0; i < 40; i++)
  85         InsertElementSkiplist(&Skiplist, (PVOID)(rand() % 100));
  86
  87     // Output the third element (with zero-based index 2).
  88     pNode = LookupNodeByIndexSkiplist(&Skiplist, 2);
  89     printf("Element = %lu for index 2\n", (DWORD)pNode->Element);
  90
  91     // Check if an element with number 44 is in the list and output its index.
  92     Element = (DWORD)LookupElementSkiplist(&Skiplist, (PVOID)44, &ElementIndex);
  93     printf("Element = %lu, ElementIndex = %lu\n\n", Element, ElementIndex);
  94
  95     DumpSkiplist(&Skiplist);
  96
  97     return 0;
  98 }