huwcampbell.com
Reactos
1/*
2 * PROJECT: Skiplist implementation for the ReactOS Project
3 * LICENSE: GPL-2.0+ (https://spdx.org/licenses/GPL-2.0+)
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
18C_ASSERT(SKIPLIST_LEVELS >= 1);
19C_ASSERT(SKIPLIST_LEVELS <= 31);
20
21// Function pointer definitions
22typedef PVOID (WINAPI *PSKIPLIST_ALLOCATE_ROUTINE)(DWORD);
23typedef int (WINAPI *PSKIPLIST_COMPARE_ROUTINE)(PVOID, PVOID);
24typedef void (WINAPI *PSKIPLIST_FREE_ROUTINE)(PVOID);
25
26// Structure definitions
27typedef struct _SKIPLIST_NODE
28{
29 DWORD Distance[SKIPLIST_LEVELS];
30 struct _SKIPLIST_NODE* Next[SKIPLIST_LEVELS];
31 PVOID Element;
32}
33SKIPLIST_NODE, *PSKIPLIST_NODE;
34
35typedef 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}
44SKIPLIST, *PSKIPLIST;
45
46// Function prototypes
47void InitializeSkiplist(PSKIPLIST Skiplist, PSKIPLIST_ALLOCATE_ROUTINE AllocateRoutine, PSKIPLIST_COMPARE_ROUTINE CompareRoutine, PSKIPLIST_FREE_ROUTINE FreeRoutine);
48BOOL InsertElementSkiplist(PSKIPLIST Skiplist, PVOID Element);
49BOOL InsertTailElementSkiplist(PSKIPLIST Skiplist, PVOID Element);
50PVOID DeleteElementSkiplist(PSKIPLIST Skiplist, PVOID Element);
51PVOID LookupElementSkiplist(PSKIPLIST Skiplist, PVOID Element, PDWORD ElementIndex);
52PSKIPLIST_NODE LookupNodeByIndexSkiplist(PSKIPLIST Skiplist, DWORD ElementIndex);
53
54#endif