ReactOS 0.4.16-dev-109-gf4cb10f
skiplist.c
Go to the documentation of this file.
1/*
2 * PROJECT: Skiplist implementation for the ReactOS Project
3 * LICENSE: GPL-2.0+ (https://spdx.org/licenses/GPL-2.0+)
4 * PURPOSE: All implemented functions operating on the Skiplist
5 * COPYRIGHT: Copyright 2015 Colin Finck (colin@reactos.org)
6 */
7
8#include <intrin.h>
9#include <windef.h>
10#include <winbase.h>
11#include "skiplist.h"
12
22static __inline CHAR
24{
25 // Using a simple fixed seed and the Park-Miller Lehmer Minimal Standard Random Number Generator gives an acceptable distribution for our "random" levels.
26 static DWORD dwRandom = 1;
27
28 DWORD dwLevel = 0;
29 DWORD dwShifted;
30
31 // Generate 31 uniformly distributed pseudo-random bits using the Park-Miller Lehmer Minimal Standard Random Number Generator.
32 dwRandom = (DWORD)(((ULONGLONG)dwRandom * 48271UL) % 2147483647UL);
33
34 // Shift out (31 - SKIPLIST_LEVELS) bits to the right to have no more than SKIPLIST_LEVELS bits set.
35 dwShifted = dwRandom >> (31 - SKIPLIST_LEVELS);
36
37 // BitScanForward doesn't operate on a zero input value.
38 if (dwShifted)
39 {
40 // BitScanForward sets dwLevel to the zero-based position of the first set bit (from LSB to MSB).
41 // This makes dwLevel a geometrically distributed value between 0 and SKIPLIST_LEVELS - 1 for p = 0.5.
42 BitScanForward(&dwLevel, dwShifted);
43 }
44
45 // dwLevel can't have a value higher than 30 this way, so a CHAR is more than enough.
46 return (CHAR)dwLevel;
47}
48
70static BOOL
72{
73 CHAR chNewLevel;
74 CHAR i;
75 PSKIPLIST_NODE pNode;
76
77 // Get the highest level, on which the node shall be inserted.
78 chNewLevel = _GetRandomLevel();
79
80 // Check if the new level is higher than the maximum level we currently have in the Skiplist.
81 if (chNewLevel > Skiplist->MaximumLevel)
82 {
83 // It is, so we also need to insert the new node right after the Head node on some levels.
84 // These are the levels higher than the current maximum level up to the new level.
85 // We also need to set the distance of these elements to the new node count to account for the calculations below.
86 for (i = Skiplist->MaximumLevel + 1; i <= chNewLevel; i++)
87 {
88 pUpdate[i] = &Skiplist->Head;
89 pUpdate[i]->Distance[i] = Skiplist->NodeCount + 1;
90 }
91
92 // The new level is the new maximum level of the entire Skiplist.
93 Skiplist->MaximumLevel = chNewLevel;
94 }
95
96 // Finally create our new Skiplist node.
97 pNode = Skiplist->AllocateRoutine(sizeof(SKIPLIST_NODE));
98 if (!pNode)
99 return FALSE;
100
101 pNode->Element = Element;
102
103 // For each used level, insert us between the saved node for this level and its current next node.
104 for (i = 0; i <= chNewLevel; i++)
105 {
106 pNode->Next[i] = pUpdate[i]->Next[i];
107 pUpdate[i]->Next[i] = pNode;
108
109 // We know the walked distance in this level: dwDistance[i]
110 // We also know the element index of the new node: dwDistance[0]
111 // The new node's distance is now the walked distance in this level plus the difference between the saved node's distance and the element index.
112 pNode->Distance[i] = dwDistance[i] + (pUpdate[i]->Distance[i] - dwDistance[0]);
113
114 // The saved node's distance is now the element index plus one (to account for the added node) minus the walked distance in this level.
115 pUpdate[i]->Distance[i] = dwDistance[0] + 1 - dwDistance[i];
116 }
117
118 // For all levels above the new node's level, we need to increment the distance, because we've just added our new node.
119 for (i = chNewLevel + 1; i <= Skiplist->MaximumLevel; i++)
120 ++pUpdate[i]->Distance[i];
121
122 // We've successfully added a node :)
123 ++Skiplist->NodeCount;
124 return TRUE;
125}
126
145PVOID
147{
148 CHAR i;
149 PSKIPLIST_NODE pLastComparedNode = NULL;
150 PSKIPLIST_NODE pNode = &Skiplist->Head;
152 PVOID pReturnValue;
153
154 // Find the node on every currently used level, after which the node to be deleted must follow.
155 // This can be done efficiently by starting from the maximum level and going down a level each time a position has been found.
156 for (i = Skiplist->MaximumLevel + 1; --i >= 0;)
157 {
158 while (pNode->Next[i] && pNode->Next[i] != pLastComparedNode && Skiplist->CompareRoutine(pNode->Next[i]->Element, Element) < 0)
159 pNode = pNode->Next[i];
160
161 // Reduce the number of comparisons by not comparing the same node on different levels twice.
162 pLastComparedNode = pNode->Next[i];
163 pUpdate[i] = pNode;
164 }
165
166 // Check if the node we're looking for has been found.
167 pNode = pNode->Next[0];
168 if (!pNode || Skiplist->CompareRoutine(pNode->Element, Element) != 0)
169 {
170 // It hasn't been found, so there's nothing to delete.
171 return NULL;
172 }
173
174 // Beginning at the lowest level, remove the node from each level of the list and merge distances.
175 // We can stop as soon as we found the first level that doesn't contain the node.
176 for (i = 0; i <= Skiplist->MaximumLevel && pUpdate[i]->Next[i] == pNode; i++)
177 {
178 pUpdate[i]->Distance[i] += pNode->Distance[i] - 1;
179 pUpdate[i]->Next[i] = pNode->Next[i];
180 }
181
182 // Now decrement the distance of the corresponding node in levels higher than the deleted node's level to account for the deleted node.
183 while (i <= Skiplist->MaximumLevel)
184 {
185 --pUpdate[i]->Distance[i];
186 i++;
187 }
188
189 // Return the deleted element (so the caller can free it if necessary) and free the memory for the node itself (allocated by us).
190 pReturnValue = pNode->Element;
191 Skiplist->FreeRoutine(pNode);
192
193 // Find all levels which now contain no more nodes and reduce the maximum level of the entire Skiplist accordingly.
194 while (Skiplist->MaximumLevel > 0 && !Skiplist->Head.Next[Skiplist->MaximumLevel])
195 --Skiplist->MaximumLevel;
196
197 // We've successfully deleted the node :)
198 --Skiplist->NodeCount;
199 return pReturnValue;
200}
201
219void
221{
222 // Store the routines.
224 Skiplist->CompareRoutine = CompareRoutine;
225 Skiplist->FreeRoutine = FreeRoutine;
226
227 // Initialize the members and pointers.
228 // The Distance array is only used when a node is non-NULL, so it doesn't need initialization.
229 Skiplist->MaximumLevel = 0;
230 Skiplist->NodeCount = 0;
231 ZeroMemory(Skiplist->Head.Next, sizeof(Skiplist->Head.Next));
232}
233
249BOOL
251{
252 CHAR i;
253 DWORD dwDistance[SKIPLIST_LEVELS + 1] = { 0 };
254 PSKIPLIST_NODE pLastComparedNode = NULL;
255 PSKIPLIST_NODE pNode = &Skiplist->Head;
257
258 // Find the node on every currently used level, after which the new node needs to be inserted.
259 // This can be done efficiently by starting from the maximum level and going down a level each time a position has been found.
260 for (i = Skiplist->MaximumLevel + 1; --i >= 0;)
261 {
262 // When entering this level, we begin at the distance of the last level we walked through.
263 dwDistance[i] = dwDistance[i + 1];
264
265 while (pNode->Next[i] && pNode->Next[i] != pLastComparedNode && Skiplist->CompareRoutine(pNode->Next[i]->Element, Element) < 0)
266 {
267 // Save our position in every level when walking through the nodes.
268 dwDistance[i] += pNode->Distance[i];
269
270 // Advance to the next node.
271 pNode = pNode->Next[i];
272 }
273
274 // Reduce the number of comparisons by not comparing the same node on different levels twice.
275 pLastComparedNode = pNode->Next[i];
276 pUpdate[i] = pNode;
277 }
278
279 // Check if the node already exists in the Skiplist.
280 pNode = pNode->Next[0];
281 if (pNode && Skiplist->CompareRoutine(pNode->Element, Element) == 0)
282 {
283 // All elements to be inserted mustn't exist in the list, so we see this as a failure.
284 return FALSE;
285 }
286
287 // The rest of the procedure is the same for both insertion functions.
288 return _InsertElementSkiplistWithInformation(Skiplist, Element, pUpdate, dwDistance);
289}
290
307BOOL
309{
310 CHAR i;
311 DWORD dwDistance[SKIPLIST_LEVELS + 1] = { 0 };
312 PSKIPLIST_NODE pNode = &Skiplist->Head;
314
315 // Find the last node on every currently used level, after which the new node needs to be inserted.
316 // This can be done efficiently by starting from the maximum level and going down a level each time a position has been found.
317 for (i = Skiplist->MaximumLevel + 1; --i >= 0;)
318 {
319 // When entering this level, we begin at the distance of the last level we walked through.
320 dwDistance[i] = dwDistance[i + 1];
321
322 while (pNode->Next[i])
323 {
324 // Save our position in every level when walking through the nodes.
325 dwDistance[i] += pNode->Distance[i];
326
327 // Advance to the next node.
328 pNode = pNode->Next[i];
329 }
330
331 pUpdate[i] = pNode;
332 }
333
334 // The rest of the procedure is the same for both insertion functions.
335 return _InsertElementSkiplistWithInformation(Skiplist, Element, pUpdate, dwDistance);
336}
337
356PVOID
357LookupElementSkiplist(PSKIPLIST Skiplist, PVOID Element, PDWORD ElementIndex)
358{
359 CHAR i;
360 DWORD dwIndex = 0;
361 PSKIPLIST_NODE pLastComparedNode = NULL;
362 PSKIPLIST_NODE pNode = &Skiplist->Head;
363
364 // Do the efficient lookup in Skiplists:
365 // * Start from the maximum level.
366 // * Walk through all nodes on this level that come before the node we're looking for.
367 // * When we have reached such a node, go down a level and continue there.
368 // * Repeat these steps till we're in level 0, right in front of the node we're looking for.
369 for (i = Skiplist->MaximumLevel + 1; --i >= 0;)
370 {
371 while (pNode->Next[i] && pNode->Next[i] != pLastComparedNode && Skiplist->CompareRoutine(pNode->Next[i]->Element, Element) < 0)
372 {
373 dwIndex += pNode->Distance[i];
374 pNode = pNode->Next[i];
375 }
376
377 // Reduce the number of comparisons by not comparing the same node on different levels twice.
378 pLastComparedNode = pNode->Next[i];
379 }
380
381 // We must be right in front of the node we're looking for now, otherwise it doesn't exist in the Skiplist at all.
382 pNode = pNode->Next[0];
383 if (!pNode || Skiplist->CompareRoutine(pNode->Element, Element) != 0)
384 {
385 // It hasn't been found, so there's nothing to return.
386 return NULL;
387 }
388
389 // Return the index of the element if the caller is interested.
390 if (ElementIndex)
391 *ElementIndex = dwIndex;
392
393 // Return the stored element of the found node.
394 return pNode->Element;
395}
396
413{
414 CHAR i;
415 DWORD dwIndex = 0;
416 PSKIPLIST_NODE pNode = &Skiplist->Head;
417
418 // The only way the node can't be found is when the index is out of range.
419 if (ElementIndex >= Skiplist->NodeCount)
420 return NULL;
421
422 // Do the efficient lookup in Skiplists:
423 // * Start from the maximum level.
424 // * Walk through all nodes on this level that come before the node we're looking for.
425 // * When we have reached such a node, go down a level and continue there.
426 // * Repeat these steps till we're in level 0, right in front of the node we're looking for.
427 for (i = Skiplist->MaximumLevel + 1; --i >= 0;)
428 {
429 // We compare with <= instead of < here, because the added distances make up a 1-based index while ElementIndex is zero-based,
430 // so we have to jump one node further.
431 while (pNode->Next[i] && dwIndex + pNode->Distance[i] <= ElementIndex)
432 {
433 dwIndex += pNode->Distance[i];
434 pNode = pNode->Next[i];
435 }
436 }
437
438 // We are right in front of the node we're looking for now.
439 return pNode->Next[0];
440}
#define NULL
Definition: types.h:112
#define TRUE
Definition: types.h:120
#define FALSE
Definition: types.h:117
unsigned int BOOL
Definition: ntddk_ex.h:94
unsigned long DWORD
Definition: ntddk_ex.h:95
GLsizei GLenum const GLvoid GLsizei GLenum GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLint GLint GLint GLshort GLshort GLshort GLubyte GLubyte GLubyte GLuint GLuint GLuint GLushort GLushort GLushort GLbyte GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLfloat GLint GLint GLint GLint GLshort GLshort GLshort GLshort GLubyte GLubyte GLubyte GLubyte GLuint GLuint GLuint GLuint GLushort GLushort GLushort GLushort GLboolean const GLdouble const GLfloat const GLint const GLshort const GLbyte const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLdouble const GLfloat const GLfloat const GLint const GLint const GLshort const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort GLenum GLenum GLenum GLfloat GLenum GLint GLenum GLenum GLenum GLfloat GLenum GLenum GLint GLenum GLfloat GLenum GLint GLint GLushort GLenum GLenum GLfloat GLenum GLenum GLint GLfloat const GLubyte GLenum GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLint GLint GLsizei GLsizei GLint GLenum GLenum const GLvoid GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLenum const GLdouble GLenum GLenum const GLfloat GLenum GLenum const GLint GLsizei GLuint GLfloat GLuint GLbitfield GLfloat GLint GLuint GLboolean GLenum GLfloat GLenum GLbitfield GLenum GLfloat GLfloat GLint GLint const GLfloat GLenum GLfloat GLfloat GLint GLint GLfloat GLfloat GLint GLint const GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat const GLdouble const GLfloat const GLdouble const GLfloat GLint i
Definition: glfuncs.h:248
#define BitScanForward
Definition: interlocked.h:5
#define DWORD
Definition: nt_native.h:44
DWORD * PDWORD
Definition: pedump.c:68
static __inline CHAR _GetRandomLevel()
Definition: skiplist.c:23
BOOL InsertTailElementSkiplist(PSKIPLIST Skiplist, PVOID Element)
Definition: skiplist.c:308
PVOID LookupElementSkiplist(PSKIPLIST Skiplist, PVOID Element, PDWORD ElementIndex)
Definition: skiplist.c:357
static BOOL _InsertElementSkiplistWithInformation(PSKIPLIST Skiplist, PVOID Element, PSKIPLIST_NODE *pUpdate, DWORD *dwDistance)
Definition: skiplist.c:71
PSKIPLIST_NODE LookupNodeByIndexSkiplist(PSKIPLIST Skiplist, DWORD ElementIndex)
Definition: skiplist.c:412
BOOL InsertElementSkiplist(PSKIPLIST Skiplist, PVOID Element)
Definition: skiplist.c:250
PVOID DeleteElementSkiplist(PSKIPLIST Skiplist, PVOID Element)
Definition: skiplist.c:146
void InitializeSkiplist(PSKIPLIST Skiplist, PSKIPLIST_ALLOCATE_ROUTINE AllocateRoutine, PSKIPLIST_COMPARE_ROUTINE CompareRoutine, PSKIPLIST_FREE_ROUTINE FreeRoutine)
Definition: skiplist.c:220
PVOID(WINAPI * PSKIPLIST_ALLOCATE_ROUTINE)(DWORD)
Definition: skiplist.h:22
int(WINAPI * PSKIPLIST_COMPARE_ROUTINE)(PVOID, PVOID)
Definition: skiplist.h:23
void(WINAPI * PSKIPLIST_FREE_ROUTINE)(PVOID)
Definition: skiplist.h:24
DWORD Distance[SKIPLIST_LEVELS]
Definition: skiplist.h:29
struct _SKIPLIST_NODE * Next[SKIPLIST_LEVELS]
Definition: skiplist.h:30
PVOID Element
Definition: skiplist.h:31
CHAR MaximumLevel
Definition: skiplist.h:38
PSKIPLIST_COMPARE_ROUTINE CompareRoutine
Definition: skiplist.h:41
SKIPLIST_NODE Head
Definition: skiplist.h:37
PSKIPLIST_FREE_ROUTINE FreeRoutine
Definition: skiplist.h:42
DWORD NodeCount
Definition: skiplist.h:39
PSKIPLIST_ALLOCATE_ROUTINE AllocateRoutine
Definition: skiplist.h:40
uint64_t ULONGLONG
Definition: typedefs.h:67
#define SKIPLIST_LEVELS
Definition: precomp.h:30
#define ZeroMemory
Definition: winbase.h:1712
_In_ PRTL_GENERIC_COMPARE_ROUTINE _In_ PRTL_GENERIC_ALLOCATE_ROUTINE _In_ PRTL_GENERIC_FREE_ROUTINE FreeRoutine
Definition: rtlfuncs.h:1104
_In_ PRTL_GENERIC_COMPARE_ROUTINE _In_ PRTL_GENERIC_ALLOCATE_ROUTINE AllocateRoutine
Definition: rtlfuncs.h:1103
_In_ PRTL_GENERIC_COMPARE_ROUTINE CompareRoutine
Definition: rtlfuncs.h:1102
char CHAR
Definition: xmlstorage.h:175