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 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 55