--- /dev/null
+/*
+ * PROJECT: Skiplist implementation for the ReactOS Project
+ * LICENSE: GNU LGPL v2.1 or any later version as published by the Free Software Foundation
+ * PURPOSE: All implemented functions operating on the Skiplist
+ * COPYRIGHT: Copyright 2015 Colin Finck <colin@reactos.org>
+ */
+
+#include <intrin.h>
+#include <windef.h>
+#include <winbase.h>
+#include "skiplist.h"
+
+/**
+ * @name _GetRandomLevel
+ *
+ * Returns a random level for the next element to be inserted.
+ * This level is geometrically distributed for p = 0.5, so perfectly suitable for an efficient Skiplist implementation.
+ *
+ * @return
+ * A value between 0 and SKIPLIST_LEVELS - 1.
+ */
+static __inline CHAR
+_GetRandomLevel()
+{
+ // Using a simple fixed seed and the Park-Miller Lehmer Minimal Standard Random Number Generator gives an acceptable distribution for our "random" levels.
+ static DWORD dwRandom = 1;
+
+ DWORD dwLevel = 0;
+ DWORD dwShifted;
+
+ // Generate 32 uniformly distributed pseudo-random bits using the Park-Miller Lehmer Minimal Standard Random Number Generator.
+ dwRandom = (DWORD)(((ULONGLONG)dwRandom * 48271UL) % 2147483647UL);
+
+ // Shift out (32 - SKIPLIST_LEVELS) bits to the right to have no more than SKIPLIST_LEVELS bits set.
+ dwShifted = dwRandom >> (32 - SKIPLIST_LEVELS);
+
+ // BitScanForward doesn't operate on a zero input value.
+ if (dwShifted)
+ {
+ // BitScanForward sets dwLevel to the zero-based position of the first set bit (from LSB to MSB).
+ // This makes dwLevel a geometrically distributed value between 0 and SKIPLIST_LEVELS - 1 for p = 0.5.
+ BitScanForward(&dwLevel, dwShifted);
+ }
+
+ // dwLevel can't have a value higher than 31 this way, so a CHAR is more than enough.
+ return (CHAR)dwLevel;
+}
+
+/**
+ * @name _InsertElementSkiplistWithInformation
+ *
+ * Determines a level for the new element and inserts it at the given position in the Skiplist.
+ * This function is internally used by the Skiplist insertion functions.
+ *
+ * @param Skiplist
+ * Pointer to the SKIPLIST structure to operate on.
+ *
+ * @param Element
+ * The element to insert.
+ *
+ * @param pUpdate
+ * Array containing the last nodes before our new node on each level.
+ *
+ * @param dwDistance
+ * Array containing the distance to the last node before our new node on each level.
+ *
+ * @return
+ * TRUE if the node was successfully inserted, FALSE if no memory could be allocated for it.
+ */
+static BOOL
+_InsertElementSkiplistWithInformation(PSKIPLIST Skiplist, PVOID Element, PSKIPLIST_NODE* pUpdate, DWORD* dwDistance)
+{
+ CHAR chNewLevel;
+ CHAR i;
+ PSKIPLIST_NODE pNode;
+
+ // Get the highest level, on which the node shall be inserted.
+ chNewLevel = _GetRandomLevel();
+
+ // Check if the new level is higher than the maximum level we currently have in the Skiplist.
+ if (chNewLevel > Skiplist->MaximumLevel)
+ {
+ // It is, so we also need to insert the new node right after the Head node on some levels.
+ // These are the levels higher than the current maximum level up to the new level.
+ // We also need to set the distance of these elements to the new node count to account for the calculations below.
+ for (i = Skiplist->MaximumLevel + 1; i <= chNewLevel; i++)
+ {
+ pUpdate[i] = &Skiplist->Head;
+ pUpdate[i]->Distance[i] = Skiplist->NodeCount + 1;
+ }
+
+ // The new level is the new maximum level of the entire Skiplist.
+ Skiplist->MaximumLevel = chNewLevel;
+ }
+
+ // Finally create our new Skiplist node.
+ pNode = Skiplist->AllocateRoutine(sizeof(SKIPLIST_NODE));
+ if (!pNode)
+ return FALSE;
+
+ pNode->Element = Element;
+
+ // For each used level, insert us between the saved node for this level and its current next node.
+ for (i = 0; i <= chNewLevel; i++)
+ {
+ pNode->Next[i] = pUpdate[i]->Next[i];
+ pUpdate[i]->Next[i] = pNode;
+
+ // We know the walked distance in this level: dwDistance[i]
+ // We also know the element index of the new node: dwDistance[0]
+ // 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.
+ pNode->Distance[i] = dwDistance[i] + (pUpdate[i]->Distance[i] - dwDistance[0]);
+
+ // 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.
+ pUpdate[i]->Distance[i] = dwDistance[0] + 1 - dwDistance[i];
+ }
+
+ // For all levels above the new node's level, we need to increment the distance, because we've just added our new node.
+ for (i = chNewLevel + 1; i <= Skiplist->MaximumLevel; i++)
+ ++pUpdate[i]->Distance[i];
+
+ // We've successfully added a node :)
+ ++Skiplist->NodeCount;
+ return TRUE;
+}
+
+/**
+ * @name DeleteElementSkiplist
+ *
+ * Deletes an element from the Skiplist. The efficiency of this operation is O(log N) on average.
+ *
+ * Instead of the result of a LookupElementSkiplist call, it's sufficient to provide a dummy element with just enough information for your CompareRoutine.
+ * A lookup for the element to be deleted needs to be performed in any case.
+ *
+ * @param Skiplist
+ * Pointer to the SKIPLIST structure to operate on.
+ *
+ * @param Element
+ * Information about the element to be deleted.
+ *
+ * @return
+ * Returns the deleted element or NULL if no such element was found.
+ * You can then free memory for the deleted element if necessary.
+ */
+PVOID
+DeleteElementSkiplist(PSKIPLIST Skiplist, PVOID Element)
+{
+ CHAR i;
+ PSKIPLIST_NODE pLastComparedNode = NULL;
+ PSKIPLIST_NODE pNode = &Skiplist->Head;
+ PSKIPLIST_NODE pUpdate[SKIPLIST_LEVELS];
+ PVOID pReturnValue;
+
+ // Find the node on every currently used level, after which the node to be deleted must follow.
+ // This can be done efficiently by starting from the maximum level and going down a level each time a position has been found.
+ for (i = Skiplist->MaximumLevel + 1; --i >= 0;)
+ {
+ while (pNode->Next[i] && pNode->Next[i] != pLastComparedNode && Skiplist->CompareRoutine(pNode->Next[i]->Element, Element) < 0)
+ pNode = pNode->Next[i];
+
+ // Reduce the number of comparisons by not comparing the same node on different levels twice.
+ pLastComparedNode = pNode->Next[i];
+ pUpdate[i] = pNode;
+ }
+
+ // Check if the node we're looking for has been found.
+ pNode = pNode->Next[0];
+ if (!pNode || Skiplist->CompareRoutine(pNode->Element, Element) != 0)
+ {
+ // It hasn't been found, so there's nothing to delete.
+ return NULL;
+ }
+
+ // Beginning at the lowest level, remove the node from each level of the list and merge distances.
+ // We can stop as soon as we found the first level that doesn't contain the node.
+ for (i = 0; i <= Skiplist->MaximumLevel && pUpdate[i]->Next[i] == pNode; i++)
+ {
+ pUpdate[i]->Distance[i] += pNode->Distance[i] - 1;
+ pUpdate[i]->Next[i] = pNode->Next[i];
+ }
+
+ // Now decrement the distance of the corresponding node in levels higher than the deleted node's level to account for the deleted node.
+ while (i <= Skiplist->MaximumLevel)
+ {
+ --pUpdate[i]->Distance[i];
+ i++;
+ }
+
+ // Return the deleted element (so the caller can free it if necessary) and free the memory for the node itself (allocated by us).
+ pReturnValue = pNode->Element;
+ Skiplist->FreeRoutine(pNode);
+
+ // Find all levels which now contain no more nodes and reduce the maximum level of the entire Skiplist accordingly.
+ while (Skiplist->MaximumLevel > 0 && !Skiplist->Head.Next[Skiplist->MaximumLevel])
+ --Skiplist->MaximumLevel;
+
+ // We've successfully deleted the node :)
+ --Skiplist->NodeCount;
+ return pReturnValue;
+}
+
+/**
+ * @name InitializeSkiplist
+ *
+ * Initializes a new Skiplist structure.
+ *
+ * @param Skiplist
+ * Pointer to the SKIPLIST structure to operate on.
+ *
+ * @param AllocateRoutine
+ * Pointer to a SKIPLIST_ALLOCATE_ROUTINE for allocating memory for new Skiplist nodes.
+ *
+ * @param CompareRoutine
+ * Pointer to a SKIPLIST_COMPARE_ROUTINE for comparing two elements of the Skiplist.
+ *
+ * @param FreeRoutine
+ * Pointer to a SKIPLIST_FREE_ROUTINE for freeing memory allocated with AllocateRoutine.
+ */
+void
+InitializeSkiplist(PSKIPLIST Skiplist, PSKIPLIST_ALLOCATE_ROUTINE AllocateRoutine, PSKIPLIST_COMPARE_ROUTINE CompareRoutine, PSKIPLIST_FREE_ROUTINE FreeRoutine)
+{
+ // Store the routines.
+ Skiplist->AllocateRoutine = AllocateRoutine;
+ Skiplist->CompareRoutine = CompareRoutine;
+ Skiplist->FreeRoutine = FreeRoutine;
+
+ // Initialize the members and pointers.
+ // The Distance array is only used when a node is non-NULL, so it doesn't need initialization.
+ Skiplist->MaximumLevel = 0;
+ Skiplist->NodeCount = 0;
+ ZeroMemory(Skiplist->Head.Next, sizeof(Skiplist->Head.Next));
+}
+
+/**
+ * @name InsertElementSkiplist
+ *
+ * Inserts a new element into the Skiplist. The efficiency of this operation is O(log N) on average.
+ * Uses CompareRoutine to find the right position for the insertion.
+ *
+ * @param Skiplist
+ * Pointer to the SKIPLIST structure to operate on.
+ *
+ * @param Element
+ * The element to insert.
+ *
+ * @return
+ * TRUE if the node was successfully inserted, FALSE if it already exists or no memory could be allocated for it.
+ */
+BOOL
+InsertElementSkiplist(PSKIPLIST Skiplist, PVOID Element)
+{
+ CHAR i;
+ DWORD dwDistance[SKIPLIST_LEVELS + 1] = { 0 };
+ PSKIPLIST_NODE pLastComparedNode = NULL;
+ PSKIPLIST_NODE pNode = &Skiplist->Head;
+ PSKIPLIST_NODE pUpdate[SKIPLIST_LEVELS];
+
+ // Find the node on every currently used level, after which the new node needs to be inserted.
+ // This can be done efficiently by starting from the maximum level and going down a level each time a position has been found.
+ for (i = Skiplist->MaximumLevel + 1; --i >= 0;)
+ {
+ // When entering this level, we begin at the distance of the last level we walked through.
+ dwDistance[i] = dwDistance[i + 1];
+
+ while (pNode->Next[i] && pNode->Next[i] != pLastComparedNode && Skiplist->CompareRoutine(pNode->Next[i]->Element, Element) < 0)
+ {
+ // Save our position in every level when walking through the nodes.
+ dwDistance[i] += pNode->Distance[i];
+
+ // Advance to the next node.
+ pNode = pNode->Next[i];
+ }
+
+ // Reduce the number of comparisons by not comparing the same node on different levels twice.
+ pLastComparedNode = pNode->Next[i];
+ pUpdate[i] = pNode;
+ }
+
+ // Check if the node already exists in the Skiplist.
+ pNode = pNode->Next[0];
+ if (pNode && Skiplist->CompareRoutine(pNode->Element, Element) == 0)
+ {
+ // All elements to be inserted mustn't exist in the list, so we see this as a failure.
+ return FALSE;
+ }
+
+ // The rest of the procedure is the same for both insertion functions.
+ return _InsertElementSkiplistWithInformation(Skiplist, Element, pUpdate, dwDistance);
+}
+
+/**
+ * @name InsertTailElementSkiplist
+ *
+ * Inserts a new element at the end of the Skiplist. The efficiency of this operation is O(log N) on average.
+ * In contrast to InsertElementSkiplist, this function is more efficient by not calling CompareRoutine at all and always inserting the element at the end.
+ * You're responsible for calling this function only when you can guarantee that InsertElementSkiplist would also insert the element at the end.
+ *
+ * @param Skiplist
+ * Pointer to the SKIPLIST structure to operate on.
+ *
+ * @param Element
+ * The element to insert.
+ *
+ * @return
+ * TRUE if the node was successfully inserted, FALSE if it already exists or no memory could be allocated for it.
+ */
+BOOL
+InsertTailElementSkiplist(PSKIPLIST Skiplist, PVOID Element)
+{
+ CHAR i;
+ DWORD dwDistance[SKIPLIST_LEVELS + 1] = { 0 };
+ PSKIPLIST_NODE pNode = &Skiplist->Head;
+ PSKIPLIST_NODE pUpdate[SKIPLIST_LEVELS];
+
+ // Find the last node on every currently used level, after which the new node needs to be inserted.
+ // This can be done efficiently by starting from the maximum level and going down a level each time a position has been found.
+ for (i = Skiplist->MaximumLevel + 1; --i >= 0;)
+ {
+ // When entering this level, we begin at the distance of the last level we walked through.
+ dwDistance[i] = dwDistance[i + 1];
+
+ while (pNode->Next[i])
+ {
+ // Save our position in every level when walking through the nodes.
+ dwDistance[i] += pNode->Distance[i];
+
+ // Advance to the next node.
+ pNode = pNode->Next[i];
+ }
+
+ pUpdate[i] = pNode;
+ }
+
+ // The rest of the procedure is the same for both insertion functions.
+ return _InsertElementSkiplistWithInformation(Skiplist, Element, pUpdate, dwDistance);
+}
+
+/**
+ * @name LookupElementSkiplist
+ *
+ * Looks up an element in the Skiplist. The efficiency of this operation is O(log N) on average.
+ *
+ * @param Skiplist
+ * Pointer to the SKIPLIST structure to operate on.
+ *
+ * @param Element
+ * Information about the element to look for.
+ *
+ * @param ElementIndex
+ * Pointer to a DWORD that will contain the zero-based index of the element in the Skiplist.
+ * If you're not interested in the index, you can set this parameter to NULL.
+ *
+ * @return
+ * Returns the found element or NULL if no such element was found.
+ */
+PVOID
+LookupElementSkiplist(PSKIPLIST Skiplist, PVOID Element, PDWORD ElementIndex)
+{
+ CHAR i;
+ DWORD dwIndex = 0;
+ PSKIPLIST_NODE pLastComparedNode = NULL;
+ PSKIPLIST_NODE pNode = &Skiplist->Head;
+
+ // Do the efficient lookup in Skiplists:
+ // * Start from the maximum level.
+ // * Walk through all nodes on this level that come before the node we're looking for.
+ // * When we have reached such a node, go down a level and continue there.
+ // * Repeat these steps till we're in level 0, right in front of the node we're looking for.
+ pNode = &Skiplist->Head;
+
+ for (i = Skiplist->MaximumLevel + 1; --i >= 0;)
+ {
+ while (pNode->Next[i] && pNode->Next[i] != pLastComparedNode && Skiplist->CompareRoutine(pNode->Next[i]->Element, Element) < 0)
+ {
+ dwIndex += pNode->Distance[i];
+ pNode = pNode->Next[i];
+ }
+
+ // Reduce the number of comparisons by not comparing the same node on different levels twice.
+ pLastComparedNode = pNode->Next[i];
+ }
+
+ // We must be right in front of the node we're looking for now, otherwise it doesn't exist in the Skiplist at all.
+ pNode = pNode->Next[0];
+ if (!pNode || Skiplist->CompareRoutine(pNode->Element, Element) != 0)
+ {
+ // It hasn't been found, so there's nothing to return.
+ return NULL;
+ }
+
+ // Return the index of the element if the caller is interested.
+ if (ElementIndex)
+ *ElementIndex = dwIndex;
+
+ // Return the stored element of the found node.
+ return pNode->Element;
+}