ReactOS 0.4.15-dev-5666-gc548b97
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
12void
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
51int WINAPI
53{
54 return (DWORD_PTR)A - (DWORD_PTR)B;
55}
56
57void WINAPI
59{
61}
62
63int
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++)
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}
Definition: ehthrow.cxx:93
Definition: ehthrow.cxx:54
#define GetProcessHeap()
Definition: compat.h:736
#define HeapAlloc
Definition: compat.h:733
#define HeapFree(x, y, z)
Definition: compat.h:735
#define UlongToPtr(u)
Definition: config.h:106
unsigned long DWORD
Definition: ntddk_ex.h:95
#define printf
Definition: freeldr.h:94
_Must_inspect_result_ _In_ PFSRTL_PER_STREAM_CONTEXT Ptr
Definition: fsrtlfuncs.h:898
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
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
_Check_return_ int __cdecl rand(void)
Definition: rand.c:10
int __cdecl system(_In_opt_z_ const char *_Command)
PVOID LookupElementSkiplist(PSKIPLIST Skiplist, PVOID Element, PDWORD ElementIndex)
Definition: skiplist.c:357
PSKIPLIST_NODE LookupNodeByIndexSkiplist(PSKIPLIST Skiplist, DWORD ElementIndex)
Definition: skiplist.c:412
BOOL InsertElementSkiplist(PSKIPLIST Skiplist, PVOID Element)
Definition: skiplist.c:250
PVOID DeleteElementSkiplist(PSKIPLIST Skiplist, PVOID Element)
Definition: skiplist.c:146
void InitializeSkiplist(PSKIPLIST Skiplist, PSKIPLIST_ALLOCATE_ROUTINE AllocateRoutine, PSKIPLIST_COMPARE_ROUTINE CompareRoutine, PSKIPLIST_FREE_ROUTINE FreeRoutine)
Definition: skiplist.c:220
void DumpSkiplist(PSKIPLIST Skiplist)
Definition: skiplist_test.c:13
PVOID WINAPI MyAlloc(DWORD Size)
Definition: skiplist_test.c:46
int WINAPI MyCompare(PVOID A, PVOID B)
Definition: skiplist_test.c:52
void WINAPI MyFree(PVOID Ptr)
Definition: skiplist_test.c:58
int main()
Definition: skiplist_test.c:64
DWORD Distance[SKIPLIST_LEVELS]
Definition: skiplist.h:29
struct _SKIPLIST_NODE * Next[SKIPLIST_LEVELS]
Definition: skiplist.h:30
PVOID Element
Definition: skiplist.h:31
CHAR MaximumLevel
Definition: skiplist.h:38
SKIPLIST_NODE Head
Definition: skiplist.h:37
#define DWORD_PTR
Definition: treelist.c:76
uint32_t DWORD_PTR
Definition: typedefs.h:65
_Must_inspect_result_ _In_ WDFDEVICE _In_ PWDF_DEVICE_PROPERTY_DATA _In_ DEVPROPTYPE _In_ ULONG Size
Definition: wdfdevice.h:4533
#define WINAPI
Definition: msvc.h:6
char CHAR
Definition: xmlstorage.h:175