[SKIPLIST]
[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 31 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 31.
16 #endif
17
18 C_ASSERT(SKIPLIST_LEVELS >= 1);
19 C_ASSERT(SKIPLIST_LEVELS <= 31);
20
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);
25
26 // Structure definitions
27 typedef struct _SKIPLIST_NODE
28 {
29 DWORD Distance[SKIPLIST_LEVELS];
30 struct _SKIPLIST_NODE* Next[SKIPLIST_LEVELS];
31 PVOID Element;
32 }
33 SKIPLIST_NODE, *PSKIPLIST_NODE;
34
35 typedef struct _SKIPLIST
36 {
37 SKIPLIST_NODE Head;
38 CHAR MaximumLevel;
39 DWORD NodeCount;
40 PSKIPLIST_ALLOCATE_ROUTINE AllocateRoutine;
41 PSKIPLIST_COMPARE_ROUTINE CompareRoutine;
42 PSKIPLIST_FREE_ROUTINE FreeRoutine;
43 }
44 SKIPLIST, *PSKIPLIST;
45
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);
53
54 #endif