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>
14 * @name _GetRandomLevel
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.
20 * A value between 0 and SKIPLIST_LEVELS - 1.
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;
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);
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
);
37 // BitScanForward doesn't operate on a zero input value.
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
);
45 // dwLevel can't have a value higher than 30 this way, so a CHAR is more than enough.
50 * @name _InsertElementSkiplistWithInformation
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.
56 * Pointer to the SKIPLIST structure to operate on.
59 * The element to insert.
62 * Array containing the last nodes before our new node on each level.
65 * Array containing the distance to the last node before our new node on each level.
68 * TRUE if the node was successfully inserted, FALSE if no memory could be allocated for it.
71 _InsertElementSkiplistWithInformation(PSKIPLIST Skiplist
, PVOID Element
, PSKIPLIST_NODE
* pUpdate
, DWORD
* dwDistance
)
77 // Get the highest level, on which the node shall be inserted.
78 chNewLevel
= _GetRandomLevel();
80 // Check if the new level is higher than the maximum level we currently have in the Skiplist.
81 if (chNewLevel
> Skiplist
->MaximumLevel
)
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
++)
88 pUpdate
[i
] = &Skiplist
->Head
;
89 pUpdate
[i
]->Distance
[i
] = Skiplist
->NodeCount
+ 1;
92 // The new level is the new maximum level of the entire Skiplist.
93 Skiplist
->MaximumLevel
= chNewLevel
;
96 // Finally create our new Skiplist node.
97 pNode
= Skiplist
->AllocateRoutine(sizeof(SKIPLIST_NODE
));
101 pNode
->Element
= Element
;
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
++)
106 pNode
->Next
[i
] = pUpdate
[i
]->Next
[i
];
107 pUpdate
[i
]->Next
[i
] = pNode
;
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]);
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
];
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
];
122 // We've successfully added a node :)
123 ++Skiplist
->NodeCount
;
128 * @name DeleteElementSkiplist
130 * Deletes an element from the Skiplist. The efficiency of this operation is O(log N) on average.
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.
136 * Pointer to the SKIPLIST structure to operate on.
139 * Information about the element to be deleted.
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.
146 DeleteElementSkiplist(PSKIPLIST Skiplist
, PVOID Element
)
149 PSKIPLIST_NODE pLastComparedNode
= NULL
;
150 PSKIPLIST_NODE pNode
= &Skiplist
->Head
;
151 PSKIPLIST_NODE pUpdate
[SKIPLIST_LEVELS
];
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;)
158 while (pNode
->Next
[i
] && pNode
->Next
[i
] != pLastComparedNode
&& Skiplist
->CompareRoutine(pNode
->Next
[i
]->Element
, Element
) < 0)
159 pNode
= pNode
->Next
[i
];
161 // Reduce the number of comparisons by not comparing the same node on different levels twice.
162 pLastComparedNode
= pNode
->Next
[i
];
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)
170 // It hasn't been found, so there's nothing to delete.
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
++)
178 pUpdate
[i
]->Distance
[i
] += pNode
->Distance
[i
] - 1;
179 pUpdate
[i
]->Next
[i
] = pNode
->Next
[i
];
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
)
185 --pUpdate
[i
]->Distance
[i
];
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
);
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
;
197 // We've successfully deleted the node :)
198 --Skiplist
->NodeCount
;
203 * @name InitializeSkiplist
205 * Initializes a new Skiplist structure.
208 * Pointer to the SKIPLIST structure to operate on.
210 * @param AllocateRoutine
211 * Pointer to a SKIPLIST_ALLOCATE_ROUTINE for allocating memory for new Skiplist nodes.
213 * @param CompareRoutine
214 * Pointer to a SKIPLIST_COMPARE_ROUTINE for comparing two elements of the Skiplist.
217 * Pointer to a SKIPLIST_FREE_ROUTINE for freeing memory allocated with AllocateRoutine.
220 InitializeSkiplist(PSKIPLIST Skiplist
, PSKIPLIST_ALLOCATE_ROUTINE AllocateRoutine
, PSKIPLIST_COMPARE_ROUTINE CompareRoutine
, PSKIPLIST_FREE_ROUTINE FreeRoutine
)
222 // Store the routines.
223 Skiplist
->AllocateRoutine
= AllocateRoutine
;
224 Skiplist
->CompareRoutine
= CompareRoutine
;
225 Skiplist
->FreeRoutine
= FreeRoutine
;
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
));
235 * @name InsertElementSkiplist
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.
241 * Pointer to the SKIPLIST structure to operate on.
244 * The element to insert.
247 * TRUE if the node was successfully inserted, FALSE if it already exists or no memory could be allocated for it.
250 InsertElementSkiplist(PSKIPLIST Skiplist
, PVOID Element
)
253 DWORD dwDistance
[SKIPLIST_LEVELS
+ 1] = { 0 };
254 PSKIPLIST_NODE pLastComparedNode
= NULL
;
255 PSKIPLIST_NODE pNode
= &Skiplist
->Head
;
256 PSKIPLIST_NODE pUpdate
[SKIPLIST_LEVELS
];
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;)
262 // When entering this level, we begin at the distance of the last level we walked through.
263 dwDistance
[i
] = dwDistance
[i
+ 1];
265 while (pNode
->Next
[i
] && pNode
->Next
[i
] != pLastComparedNode
&& Skiplist
->CompareRoutine(pNode
->Next
[i
]->Element
, Element
) < 0)
267 // Save our position in every level when walking through the nodes.
268 dwDistance
[i
] += pNode
->Distance
[i
];
270 // Advance to the next node.
271 pNode
= pNode
->Next
[i
];
274 // Reduce the number of comparisons by not comparing the same node on different levels twice.
275 pLastComparedNode
= pNode
->Next
[i
];
279 // Check if the node already exists in the Skiplist.
280 pNode
= pNode
->Next
[0];
281 if (pNode
&& Skiplist
->CompareRoutine(pNode
->Element
, Element
) == 0)
283 // All elements to be inserted mustn't exist in the list, so we see this as a failure.
287 // The rest of the procedure is the same for both insertion functions.
288 return _InsertElementSkiplistWithInformation(Skiplist
, Element
, pUpdate
, dwDistance
);
292 * @name InsertTailElementSkiplist
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.
299 * Pointer to the SKIPLIST structure to operate on.
302 * The element to insert.
305 * TRUE if the node was successfully inserted, FALSE if it already exists or no memory could be allocated for it.
308 InsertTailElementSkiplist(PSKIPLIST Skiplist
, PVOID Element
)
311 DWORD dwDistance
[SKIPLIST_LEVELS
+ 1] = { 0 };
312 PSKIPLIST_NODE pNode
= &Skiplist
->Head
;
313 PSKIPLIST_NODE pUpdate
[SKIPLIST_LEVELS
];
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;)
319 // When entering this level, we begin at the distance of the last level we walked through.
320 dwDistance
[i
] = dwDistance
[i
+ 1];
322 while (pNode
->Next
[i
])
324 // Save our position in every level when walking through the nodes.
325 dwDistance
[i
] += pNode
->Distance
[i
];
327 // Advance to the next node.
328 pNode
= pNode
->Next
[i
];
334 // The rest of the procedure is the same for both insertion functions.
335 return _InsertElementSkiplistWithInformation(Skiplist
, Element
, pUpdate
, dwDistance
);
339 * @name LookupElementSkiplist
341 * Looks up an element in the Skiplist. The efficiency of this operation is O(log N) on average.
344 * Pointer to the SKIPLIST structure to operate on.
347 * Information about the element to look for.
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.
354 * Returns the found element or NULL if no such element was found.
357 LookupElementSkiplist(PSKIPLIST Skiplist
, PVOID Element
, PDWORD ElementIndex
)
361 PSKIPLIST_NODE pLastComparedNode
= NULL
;
362 PSKIPLIST_NODE pNode
= &Skiplist
->Head
;
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;)
371 while (pNode
->Next
[i
] && pNode
->Next
[i
] != pLastComparedNode
&& Skiplist
->CompareRoutine(pNode
->Next
[i
]->Element
, Element
) < 0)
373 dwIndex
+= pNode
->Distance
[i
];
374 pNode
= pNode
->Next
[i
];
377 // Reduce the number of comparisons by not comparing the same node on different levels twice.
378 pLastComparedNode
= pNode
->Next
[i
];
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)
385 // It hasn't been found, so there's nothing to return.
389 // Return the index of the element if the caller is interested.
391 *ElementIndex
= dwIndex
;
393 // Return the stored element of the found node.
394 return pNode
->Element
;
398 * @name LookupNodeByIndexSkiplist
400 * Looks up a node in the Skiplist at the given position. The efficiency of this operation is O(log N) on average.
403 * Pointer to the SKIPLIST structure to operate on.
405 * @param ElementIndex
406 * Zero-based position of the node in the Skiplist.
409 * Returns the found node or NULL if the position is invalid.
412 LookupNodeByIndexSkiplist(PSKIPLIST Skiplist
, DWORD ElementIndex
)
416 PSKIPLIST_NODE pNode
= &Skiplist
->Head
;
418 // The only way the node can't be found is when the index is out of range.
419 if (ElementIndex
>= Skiplist
->NodeCount
)
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;)
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
)
433 dwIndex
+= pNode
->Distance
[i
];
434 pNode
= pNode
->Next
[i
];
438 // We are right in front of the node we're looking for now.
439 return pNode
->Next
[0];