[SKIPLIST]
[reactos.git] / reactos / lib / skiplist / skiplist.c
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: 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
13 /**
14 * @name _GetRandomLevel
15 *
16 * Returns a random level for the next element to be inserted.
17 * This level is geometrically distributed for p = 0.5, so perfectly suitable for an efficient Skiplist implementation.
18 *
19 * @return
20 * A value between 0 and SKIPLIST_LEVELS - 1.
21 */
22 static __inline CHAR
23 _GetRandomLevel()
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
49 /**
50 * @name _InsertElementSkiplistWithInformation
51 *
52 * Determines a level for the new element and inserts it at the given position in the Skiplist.
53 * This function is internally used by the Skiplist insertion functions.
54 *
55 * @param Skiplist
56 * Pointer to the SKIPLIST structure to operate on.
57 *
58 * @param Element
59 * The element to insert.
60 *
61 * @param pUpdate
62 * Array containing the last nodes before our new node on each level.
63 *
64 * @param dwDistance
65 * Array containing the distance to the last node before our new node on each level.
66 *
67 * @return
68 * TRUE if the node was successfully inserted, FALSE if no memory could be allocated for it.
69 */
70 static BOOL
71 _InsertElementSkiplistWithInformation(PSKIPLIST Skiplist, PVOID Element, PSKIPLIST_NODE* pUpdate, DWORD* dwDistance)
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
127 /**
128 * @name DeleteElementSkiplist
129 *
130 * Deletes an element from the Skiplist. The efficiency of this operation is O(log N) on average.
131 *
132 * Instead of the result of a LookupElementSkiplist call, it's sufficient to provide a dummy element with just enough information for your CompareRoutine.
133 * A lookup for the element to be deleted needs to be performed in any case.
134 *
135 * @param Skiplist
136 * Pointer to the SKIPLIST structure to operate on.
137 *
138 * @param Element
139 * Information about the element to be deleted.
140 *
141 * @return
142 * Returns the deleted element or NULL if no such element was found.
143 * You can then free memory for the deleted element if necessary.
144 */
145 PVOID
146 DeleteElementSkiplist(PSKIPLIST Skiplist, PVOID Element)
147 {
148 CHAR i;
149 PSKIPLIST_NODE pLastComparedNode = NULL;
150 PSKIPLIST_NODE pNode = &Skiplist->Head;
151 PSKIPLIST_NODE pUpdate[SKIPLIST_LEVELS];
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
202 /**
203 * @name InitializeSkiplist
204 *
205 * Initializes a new Skiplist structure.
206 *
207 * @param Skiplist
208 * Pointer to the SKIPLIST structure to operate on.
209 *
210 * @param AllocateRoutine
211 * Pointer to a SKIPLIST_ALLOCATE_ROUTINE for allocating memory for new Skiplist nodes.
212 *
213 * @param CompareRoutine
214 * Pointer to a SKIPLIST_COMPARE_ROUTINE for comparing two elements of the Skiplist.
215 *
216 * @param FreeRoutine
217 * Pointer to a SKIPLIST_FREE_ROUTINE for freeing memory allocated with AllocateRoutine.
218 */
219 void
220 InitializeSkiplist(PSKIPLIST Skiplist, PSKIPLIST_ALLOCATE_ROUTINE AllocateRoutine, PSKIPLIST_COMPARE_ROUTINE CompareRoutine, PSKIPLIST_FREE_ROUTINE FreeRoutine)
221 {
222 // Store the routines.
223 Skiplist->AllocateRoutine = AllocateRoutine;
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
234 /**
235 * @name InsertElementSkiplist
236 *
237 * Inserts a new element into the Skiplist. The efficiency of this operation is O(log N) on average.
238 * Uses CompareRoutine to find the right position for the insertion.
239 *
240 * @param Skiplist
241 * Pointer to the SKIPLIST structure to operate on.
242 *
243 * @param Element
244 * The element to insert.
245 *
246 * @return
247 * TRUE if the node was successfully inserted, FALSE if it already exists or no memory could be allocated for it.
248 */
249 BOOL
250 InsertElementSkiplist(PSKIPLIST Skiplist, PVOID Element)
251 {
252 CHAR i;
253 DWORD dwDistance[SKIPLIST_LEVELS + 1] = { 0 };
254 PSKIPLIST_NODE pLastComparedNode = NULL;
255 PSKIPLIST_NODE pNode = &Skiplist->Head;
256 PSKIPLIST_NODE pUpdate[SKIPLIST_LEVELS];
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
291 /**
292 * @name InsertTailElementSkiplist
293 *
294 * Inserts a new element at the end of the Skiplist. The efficiency of this operation is O(log N) on average.
295 * In contrast to InsertElementSkiplist, this function is more efficient by not calling CompareRoutine at all and always inserting the element at the end.
296 * You're responsible for calling this function only when you can guarantee that InsertElementSkiplist would also insert the element at the end.
297 *
298 * @param Skiplist
299 * Pointer to the SKIPLIST structure to operate on.
300 *
301 * @param Element
302 * The element to insert.
303 *
304 * @return
305 * TRUE if the node was successfully inserted, FALSE if it already exists or no memory could be allocated for it.
306 */
307 BOOL
308 InsertTailElementSkiplist(PSKIPLIST Skiplist, PVOID Element)
309 {
310 CHAR i;
311 DWORD dwDistance[SKIPLIST_LEVELS + 1] = { 0 };
312 PSKIPLIST_NODE pNode = &Skiplist->Head;
313 PSKIPLIST_NODE pUpdate[SKIPLIST_LEVELS];
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
338 /**
339 * @name LookupElementSkiplist
340 *
341 * Looks up an element in the Skiplist. The efficiency of this operation is O(log N) on average.
342 *
343 * @param Skiplist
344 * Pointer to the SKIPLIST structure to operate on.
345 *
346 * @param Element
347 * Information about the element to look for.
348 *
349 * @param ElementIndex
350 * Pointer to a DWORD that will contain the zero-based index of the element in the Skiplist.
351 * If you're not interested in the index, you can set this parameter to NULL.
352 *
353 * @return
354 * Returns the found element or NULL if no such element was found.
355 */
356 PVOID
357 LookupElementSkiplist(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
397 /**
398 * @name LookupNodeByIndexSkiplist
399 *
400 * Looks up a node in the Skiplist at the given position. The efficiency of this operation is O(log N) on average.
401 *
402 * @param Skiplist
403 * Pointer to the SKIPLIST structure to operate on.
404 *
405 * @param ElementIndex
406 * Zero-based position of the node in the Skiplist.
407 *
408 * @return
409 * Returns the found node or NULL if the position is invalid.
410 */
411 PSKIPLIST_NODE
412 LookupNodeByIndexSkiplist(PSKIPLIST Skiplist, DWORD ElementIndex)
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 }