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 C_ASSERT(SKIPLIST_LEVELS >= 1);
  19 C_ASSERT(SKIPLIST_LEVELS <= 32);
  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