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: Interfaces for the Skiplist
5 * COPYRIGHT: Copyright 2015 Colin Finck <colin@reactos.org>
8 #ifndef _REACTOS_SKIPLIST_H
9 #define _REACTOS_SKIPLIST_H
11 // Define SKIPLIST_LEVELS to a value between 1 and 32 before including this header.
12 // This specifies the maximum number of levels you want your Skiplist to have.
13 // A value of X is recommended for handling up to 2^X elements.
14 #ifndef SKIPLIST_LEVELS
15 #error Please define SKIPLIST_LEVELS to a value between 1 and 32.
18 C_ASSERT(SKIPLIST_LEVELS
>= 1);
19 C_ASSERT(SKIPLIST_LEVELS
<= 32);
21 // Function pointer definitions
22 typedef PVOID (WINAPI
*PSKIPLIST_ALLOCATE_ROUTINE
)(DWORD
);
23 typedef int (WINAPI
*PSKIPLIST_COMPARE_ROUTINE
)(PVOID
, PVOID
);
24 typedef void (WINAPI
*PSKIPLIST_FREE_ROUTINE
)(PVOID
);
26 // Structure definitions
27 typedef struct _SKIPLIST_NODE
29 DWORD Distance
[SKIPLIST_LEVELS
];
30 struct _SKIPLIST_NODE
* Next
[SKIPLIST_LEVELS
];
33 SKIPLIST_NODE
, *PSKIPLIST_NODE
;
35 typedef struct _SKIPLIST
40 PSKIPLIST_ALLOCATE_ROUTINE AllocateRoutine
;
41 PSKIPLIST_COMPARE_ROUTINE CompareRoutine
;
42 PSKIPLIST_FREE_ROUTINE FreeRoutine
;
46 // Function prototypes
47 void InitializeSkiplist(PSKIPLIST Skiplist
, PSKIPLIST_ALLOCATE_ROUTINE AllocateRoutine
, PSKIPLIST_COMPARE_ROUTINE CompareRoutine
, PSKIPLIST_FREE_ROUTINE FreeRoutine
);
48 BOOL
InsertElementSkiplist(PSKIPLIST Skiplist
, PVOID Element
);
49 BOOL
InsertTailElementSkiplist(PSKIPLIST Skiplist
, PVOID Element
);
50 PVOID
DeleteElementSkiplist(PSKIPLIST Skiplist
, PVOID Element
);
51 PVOID
LookupElementSkiplist(PSKIPLIST Skiplist
, PVOID Element
, PDWORD ElementIndex
);
52 PSKIPLIST_NODE
LookupNodeByIndexSkiplist(PSKIPLIST Skiplist
, DWORD ElementIndex
);