ReactOS  0.4.12-dev-432-g3463b2d
skiplist_test.c
Go to the documentation of this file.
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
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 
47 {
48  return HeapAlloc(GetProcessHeap(), 0, Size);
49 }
50 
51 int WINAPI
53 {
54  return (DWORD_PTR)A - (DWORD_PTR)B;
55 }
56 
57 void WINAPI
59 {
61 }
62 
63 int
65 {
66  PVOID Element;
67  DWORD ElementIndex;
68  DWORD i;
69  SKIPLIST Skiplist;
70  PSKIPLIST_NODE pNode;
71 
72  system("mode con cols=300");
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 }
#define DWORD_PTR
Definition: treelist.c:76
SKIPLIST_NODE Head
Definition: skiplist.h:37
int WINAPI MyCompare(PVOID A, PVOID B)
Definition: skiplist_test.c:52
char CHAR
Definition: xmlstorage.h:175
_Must_inspect_result_ _In_ PFSRTL_PER_STREAM_CONTEXT Ptr
Definition: fsrtlfuncs.h:898
CHAR MaximumLevel
Definition: skiplist.h:38
PSKIPLIST_NODE LookupNodeByIndexSkiplist(PSKIPLIST Skiplist, DWORD ElementIndex)
Definition: skiplist.c:412
void InitializeSkiplist(PSKIPLIST Skiplist, PSKIPLIST_ALLOCATE_ROUTINE AllocateRoutine, PSKIPLIST_COMPARE_ROUTINE CompareRoutine, PSKIPLIST_FREE_ROUTINE FreeRoutine)
Definition: skiplist.c:220
GLsizei GLenum const GLvoid GLsizei GLenum GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLint GLint GLint GLshort GLshort GLshort GLubyte GLubyte GLubyte GLuint GLuint GLuint GLushort GLushort GLushort GLbyte GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLfloat GLint GLint GLint GLint GLshort GLshort GLshort GLshort GLubyte GLubyte GLubyte GLubyte GLuint GLuint GLuint GLuint GLushort GLushort GLushort GLushort GLboolean const GLdouble const GLfloat const GLint const GLshort const GLbyte const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLdouble const GLfloat const GLfloat const GLint const GLint const GLshort const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort GLenum GLenum GLenum GLfloat GLenum GLint GLenum GLenum GLenum GLfloat GLenum GLenum GLint GLenum GLfloat GLenum GLint GLint GLushort GLenum GLenum GLfloat GLenum GLenum GLint GLfloat const GLubyte GLenum GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLint GLint GLsizei GLsizei GLint GLenum GLenum const GLvoid GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLenum const GLdouble GLenum GLenum const GLfloat GLenum GLenum const GLint GLsizei GLuint GLfloat GLuint GLbitfield GLfloat GLint GLuint GLboolean GLenum GLfloat GLenum GLbitfield GLenum GLfloat GLfloat GLint GLint const GLfloat GLenum GLfloat GLfloat GLint GLint GLfloat GLfloat GLint GLint const GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat const GLdouble const GLfloat const GLdouble const GLfloat GLint i
Definition: glfuncs.h:248
_Check_return_ int __cdecl rand(void)
Definition: rand.c:10
BOOL InsertElementSkiplist(PSKIPLIST Skiplist, PVOID Element)
Definition: skiplist.c:250
int __cdecl system(_In_opt_z_ const char *_Command)
void DumpSkiplist(PSKIPLIST Skiplist)
Definition: skiplist_test.c:13
GLsizei GLenum const GLvoid GLsizei GLenum GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLint GLint GLint GLshort GLshort GLshort GLubyte GLubyte GLubyte GLuint GLuint GLuint GLushort GLushort GLushort GLbyte GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLfloat GLint GLint GLint GLint GLshort GLshort GLshort GLshort GLubyte GLubyte GLubyte GLubyte GLuint GLuint GLuint GLuint GLushort GLushort GLushort GLushort GLboolean const GLdouble const GLfloat const GLint const GLshort const GLbyte const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLdouble const GLfloat const GLfloat const GLint const GLint const GLshort const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort GLenum GLenum GLenum GLfloat GLenum GLint GLenum GLenum GLenum GLfloat GLenum GLenum GLint GLenum GLfloat GLenum GLint GLint GLushort GLenum GLenum GLfloat GLenum GLenum GLint GLfloat const GLubyte GLenum GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLint GLint GLsizei GLsizei GLint GLenum GLenum const GLvoid GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLenum const GLdouble GLenum GLenum const GLfloat GLenum GLenum const GLint GLsizei GLuint GLfloat GLuint GLbitfield GLfloat GLint GLuint GLboolean GLenum GLfloat GLenum GLbitfield GLenum GLfloat GLfloat GLint GLint const GLfloat GLenum GLfloat GLfloat GLint GLint GLfloat GLfloat GLint GLint const GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat const GLdouble const GLfloat const GLdouble const GLfloat GLint GLint GLint j
Definition: glfuncs.h:250
#define UlongToPtr(ul)
Definition: basetsd.h:98
#define GetProcessHeap()
Definition: compat.h:395
PVOID WINAPI HeapAlloc(HANDLE, DWORD, SIZE_T)
int main()
Definition: skiplist_test.c:64
struct _SKIPLIST_NODE * Next[SKIPLIST_LEVELS]
Definition: skiplist.h:30
unsigned long DWORD
Definition: ntddk_ex.h:95
DWORD Distance[SKIPLIST_LEVELS]
Definition: skiplist.h:29
Definition: ttei1.cpp:12
IN PVOID IN PVOID IN USHORT IN USHORT Size
Definition: pci.h:359
uint32_t DWORD_PTR
Definition: typedefs.h:63
void WINAPI MyFree(PVOID Ptr)
Definition: skiplist_test.c:58
#define WINAPI
Definition: msvc.h:20
PVOID LookupElementSkiplist(PSKIPLIST Skiplist, PVOID Element, PDWORD ElementIndex)
Definition: skiplist.c:357
#define B(row, col)
PVOID Element
Definition: skiplist.h:31
PVOID DeleteElementSkiplist(PSKIPLIST Skiplist, PVOID Element)
Definition: skiplist.c:146
#define HeapFree(x, y, z)
Definition: compat.h:394
#define printf
Definition: config.h:203
PVOID WINAPI MyAlloc(DWORD Size)
Definition: skiplist_test.c:46