1313768f4a926b1f32c30812cbe0b56afb1a9cf7
[reactos.git] / reactos / lib / skiplist / skiplist.h
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: Interfaces for the Skiplist
5 * COPYRIGHT: Copyright 2015 Colin Finck <colin@reactos.org>
6 */
7
8 #ifndef _REACTOS_SKIPLIST_H
9 #define _REACTOS_SKIPLIST_H
10
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.
16 #endif
17
18 // Function pointer definitions
19 typedef PVOID (WINAPI *PSKIPLIST_ALLOCATE_ROUTINE)(DWORD);
20 typedef int (WINAPI *PSKIPLIST_COMPARE_ROUTINE)(PVOID, PVOID);
21 typedef void (WINAPI *PSKIPLIST_FREE_ROUTINE)(PVOID);
22
23 // Structure definitions
24 typedef struct _SKIPLIST_NODE
25 {
26 DWORD Distance[SKIPLIST_LEVELS];
27 struct _SKIPLIST_NODE* Next[SKIPLIST_LEVELS];
28 PVOID Element;
29 }
30 SKIPLIST_NODE, *PSKIPLIST_NODE;
31
32 typedef struct _SKIPLIST
33 {
34 SKIPLIST_NODE Head;
35 CHAR MaximumLevel;
36 DWORD NodeCount;
37 PSKIPLIST_ALLOCATE_ROUTINE AllocateRoutine;
38 PSKIPLIST_COMPARE_ROUTINE CompareRoutine;
39 PSKIPLIST_FREE_ROUTINE FreeRoutine;
40 }
41 SKIPLIST, *PSKIPLIST;
42
43 // Function prototypes
44 void InitializeSkiplist(PSKIPLIST Skiplist, PSKIPLIST_ALLOCATE_ROUTINE AllocateRoutine, PSKIPLIST_COMPARE_ROUTINE CompareRoutine, PSKIPLIST_FREE_ROUTINE FreeRoutine);
45 BOOL InsertElementSkiplist(PSKIPLIST Skiplist, PVOID Element);
46 BOOL InsertTailElementSkiplist(PSKIPLIST Skiplist, PVOID Element);
47 PVOID DeleteElementSkiplist(PSKIPLIST Skiplist, PVOID Element);
48 PVOID LookupElementSkiplist(PSKIPLIST Skiplist, PVOID Element, PDWORD ElementIndex);
49
50 #endif