[cfinck] 68191: [SKIPLIST] Add my implementation of an efficient Skiplist. A Skiplist can do insertion, deletion and lookups in O(log N) on average just like balanced trees. It features simpler alg...

Author: cfinck
Date: Fri Jun 19 10:27:46 2015
New Revision: 68191
URL: http://svn.reactos.org/svn/reactos?rev=68191&view=rev
Log:
[SKIPLIST]
Add my implementation of an efficient Skiplist. A Skiplist can do insertion, deletion and
lookups in O(log N) on average just like balanced trees.
It features simpler algorithms though due to purely relying on probabilistic balancing at
insertion and not on rebalancing with every modification.
This simple structure allowed me to implement some additions on top of the standard
algorithms:
* Storing distances between elements on each level to efficiently return the index of the
element in the Skiplist when doing a lookup.
* InsertTailElementSkiplist to explicitly insert an element at the end of the Skiplist.
  This needs no comparisons and is useful when you can be sure that the new element would
be inserted at the end (e.g. for a new print job in the queue with default priority).
More features are easily possible, but for now I limited features on those needed for my
Local Spooler work.
Some references on Skiplists:
* ftp://ftp.cs.umd.edu/pub/skipLists/skiplists.pdf
* http://drum.lib.umd.edu/bitstream/1903/544/2/CS-TR-2286.1.pdf
Added:
    branches/colins-printing-for-freedom/reactos/lib/skiplist/   (with props)
    branches/colins-printing-for-freedom/reactos/lib/skiplist/CMakeLists.txt   (with
props)
    branches/colins-printing-for-freedom/reactos/lib/skiplist/skiplist.c   (with props)
    branches/colins-printing-for-freedom/reactos/lib/skiplist/skiplist.h   (with props)
    branches/colins-printing-for-freedom/reactos/lib/skiplist/skiplist_test.c   (with
props)
Modified:
    branches/colins-printing-for-freedom/reactos/lib/CMakeLists.txt
Modified: branches/colins-printing-for-freedom/reactos/lib/CMakeLists.txt
URL:
http://svn.reactos.org/svn/reactos/branches/colins-printing-for-freedom/rea…
==============================================================================
--- branches/colins-printing-for-freedom/reactos/lib/CMakeLists.txt     [iso-8859-1]
(original)
+++ branches/colins-printing-for-freedom/reactos/lib/CMakeLists.txt     [iso-8859-1] Fri
Jun 19 10:27:46 2015
@@ -27,6 +27,7 @@
 add_subdirectory(rtl)
 add_subdirectory(sdk)
+add_subdirectory(skiplist)
 add_subdirectory(smlib)
 add_subdirectory(tdilib)
Propchange: branches/colins-printing-for-freedom/reactos/lib/skiplist/
------------------------------------------------------------------------------
--- bugtraq:logregex    (added)
+++ bugtraq:logregex    Fri Jun 19 10:27:46 2015
@@ -0,0 +1 @@
+((CORE|ROSTESTS|ROSAPPS)-\d+)(,? ?((CORE|ROSTESTS|ROSAPPS)-\d+))*(,? ?(and |or
)?((CORE|ROSTESTS|ROSAPPS)-\d+))?
Propchange: branches/colins-printing-for-freedom/reactos/lib/skiplist/
------------------------------------------------------------------------------
    bugtraq:message = See issue %BUGID% for more details.
Propchange: branches/colins-printing-for-freedom/reactos/lib/skiplist/
------------------------------------------------------------------------------
    bugtraq:url = https://jira.reactos.org/browse/%BUGID%
Propchange: branches/colins-printing-for-freedom/reactos/lib/skiplist/
------------------------------------------------------------------------------
    tsvn:logminsize = 10
Added: branches/colins-printing-for-freedom/reactos/lib/skiplist/CMakeLists.txt
URL:
http://svn.reactos.org/svn/reactos/branches/colins-printing-for-freedom/rea…
==============================================================================
--- branches/colins-printing-for-freedom/reactos/lib/skiplist/CMakeLists.txt    (added)
+++ branches/colins-printing-for-freedom/reactos/lib/skiplist/CMakeLists.txt
[iso-8859-1] Fri Jun 19 10:27:46 2015
@@ -0,0 +1,10 @@
+
+# The library
+add_definitions(-DSKIPLIST_LEVELS=16)
+add_library(skiplist16 skiplist.c)
+
+# The Test program
+add_executable(skiplist_test skiplist_test.c)
+target_link_libraries(skiplist_test skiplist16)
+set_module_type(skiplist_test win32cui)
+add_importlibs(skiplist_test msvcrt kernel32 ntdll)
Propchange: branches/colins-printing-for-freedom/reactos/lib/skiplist/CMakeLists.txt
------------------------------------------------------------------------------
    svn:eol-style = native
Added: branches/colins-printing-for-freedom/reactos/lib/skiplist/skiplist.c
URL:
http://svn.reactos.org/svn/reactos/branches/colins-printing-for-freedom/rea…
==============================================================================
--- branches/colins-printing-for-freedom/reactos/lib/skiplist/skiplist.c        (added)
+++ branches/colins-printing-for-freedom/reactos/lib/skiplist/skiplist.c
[iso-8859-1] Fri Jun 19 10:27:46 2015
@@ -0,0 +1,397 @@
+/*
+ * 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(a)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;
+}
Propchange: branches/colins-printing-for-freedom/reactos/lib/skiplist/skiplist.c
------------------------------------------------------------------------------
    svn:eol-style = native
Added: branches/colins-printing-for-freedom/reactos/lib/skiplist/skiplist.h
URL:
http://svn.reactos.org/svn/reactos/branches/colins-printing-for-freedom/rea…
==============================================================================
--- branches/colins-printing-for-freedom/reactos/lib/skiplist/skiplist.h        (added)
+++ branches/colins-printing-for-freedom/reactos/lib/skiplist/skiplist.h
[iso-8859-1] Fri Jun 19 10:27:46 2015
@@ -0,0 +1,50 @@
+/*
+ * PROJECT:     Skiplist implementation for the ReactOS Project
+ * LICENSE:     GNU LGPL v2.1 or any later version as published by the Free Software
Foundation
+ * PURPOSE:     Interfaces for the Skiplist
+ * COPYRIGHT:   Copyright 2015 Colin Finck &lt;colin(a)reactos.org&gt;
+ */
+
+#ifndef _REACTOS_SKIPLIST_H
+#define _REACTOS_SKIPLIST_H
+
+// Define SKIPLIST_LEVELS to a value between 1 and 32 before including this header.
+// This specifies the maximum number of levels you want your Skiplist to have.
+// A value of X is recommended for handling up to 2^X elements.
+#ifndef SKIPLIST_LEVELS
+#error Please define SKIPLIST_LEVELS to a value between 1 and 32.
+#endif
+
+// Function pointer definitions
+typedef PVOID (WINAPI *PSKIPLIST_ALLOCATE_ROUTINE)(DWORD);
+typedef int (WINAPI *PSKIPLIST_COMPARE_ROUTINE)(PVOID, PVOID);
+typedef void (WINAPI *PSKIPLIST_FREE_ROUTINE)(PVOID);
+
+// Structure definitions
+typedef struct _SKIPLIST_NODE
+{
+    DWORD Distance[SKIPLIST_LEVELS];
+    struct _SKIPLIST_NODE* Next[SKIPLIST_LEVELS];
+    PVOID Element;
+}
+SKIPLIST_NODE, *PSKIPLIST_NODE;
+
+typedef struct _SKIPLIST
+{
+    SKIPLIST_NODE Head;
+    CHAR MaximumLevel;
+    DWORD NodeCount;
+    PSKIPLIST_ALLOCATE_ROUTINE AllocateRoutine;
+    PSKIPLIST_COMPARE_ROUTINE CompareRoutine;
+    PSKIPLIST_FREE_ROUTINE FreeRoutine;
+}
+SKIPLIST, *PSKIPLIST;
+
+// Function prototypes
+void InitializeSkiplist(PSKIPLIST Skiplist, PSKIPLIST_ALLOCATE_ROUTINE AllocateRoutine,
PSKIPLIST_COMPARE_ROUTINE CompareRoutine, PSKIPLIST_FREE_ROUTINE FreeRoutine);
+BOOL InsertElementSkiplist(PSKIPLIST Skiplist, PVOID Element);
+BOOL InsertTailElementSkiplist(PSKIPLIST Skiplist, PVOID Element);
+PVOID DeleteElementSkiplist(PSKIPLIST Skiplist, PVOID Element);
+PVOID LookupElementSkiplist(PSKIPLIST Skiplist, PVOID Element, PDWORD ElementIndex);
+
+#endif
Propchange: branches/colins-printing-for-freedom/reactos/lib/skiplist/skiplist.h
------------------------------------------------------------------------------
    svn:eol-style = native
Added: branches/colins-printing-for-freedom/reactos/lib/skiplist/skiplist_test.c
URL:
http://svn.reactos.org/svn/reactos/branches/colins-printing-for-freedom/rea…
==============================================================================
--- branches/colins-printing-for-freedom/reactos/lib/skiplist/skiplist_test.c   (added)
+++ branches/colins-printing-for-freedom/reactos/lib/skiplist/skiplist_test.c
[iso-8859-1] Fri Jun 19 10:27:46 2015
@@ -0,0 +1,93 @@
+/*
+ * PROJECT:     Skiplist implementation for the ReactOS Project
+ * LICENSE:     GNU LGPL v2.1 or any later version as published by the Free Software
Foundation
+ * PURPOSE:     A simple program for testing the Skiplist implementation
+ * COPYRIGHT:   Copyright 2015 Colin Finck &lt;colin(a)reactos.org&gt;
+ */
+
+#include <windows.h>
+#include <stdio.h>
+#include "skiplist.h"
+
+void
+DumpSkiplist(PSKIPLIST Skiplist)
+{
+    CHAR i;
+    DWORD j;
+    PSKIPLIST_NODE pNode;
+
+    printf("======= DUMPING SKIPLIST =======\n");
+
+    for (i = Skiplist->MaximumLevel + 1; --i >= 0;)
+    {
+        pNode = &Skiplist->Head;
+        printf("H");
+
+        while (pNode->Next[i])
+        {
+            printf("-");
+
+            // By using the Distance array for painting the lines, we verify both the
links and the distances for correctness.
+            for (j = 1; j < pNode->Distance[i]; j++)
+                printf("---");
+
+            printf("%02lu", (DWORD)pNode->Next[i]->Element);
+
+            pNode = pNode->Next[i];
+        }
+
+        printf("\n");
+    }
+
+    printf("================================\n\n");
+}
+
+PVOID WINAPI
+MyAlloc(DWORD Size)
+{
+    return HeapAlloc(GetProcessHeap(), 0, Size);
+}
+
+int WINAPI
+MyCompare(PVOID A, PVOID B)
+{
+    return (DWORD)A - (DWORD)B;
+}
+
+void WINAPI
+MyFree(PVOID Ptr)
+{
+    HeapFree(GetProcessHeap(), 0, Ptr);
+}
+
+int
+main()
+{
+    DWORD Element;
+    DWORD ElementIndex;
+    DWORD i;
+    SKIPLIST Skiplist;
+
+    system("mode con cols=300");
+    InitializeSkiplist(&Skiplist, MyAlloc, MyCompare, MyFree);
+
+    // Insert some random elements with random numbers.
+    for (i = 0; i < 40; i++)
+        InsertElementSkiplist(&Skiplist, (PVOID)(rand() % 100));
+
+    // Delete all with index 0 to 29.
+    for (i = 0; i < 30; i++)
+        DeleteElementSkiplist(&Skiplist, (PVOID)i);
+
+    // Insert some more random elements.
+    for (i = 0; i < 40; i++)
+        InsertElementSkiplist(&Skiplist, (PVOID)(rand() % 100));
+
+    // Check if an element with number 44 is in the list and output its index.
+    Element = (DWORD)LookupElementSkiplist(&Skiplist, (PVOID)44, &ElementIndex);
+    printf("Element = %lu, ElementIndex = %lu\n\n", Element, ElementIndex);
+
+    DumpSkiplist(&Skiplist);
+
+    return 0;
+}
Propchange: branches/colins-printing-for-freedom/reactos/lib/skiplist/skiplist_test.c
------------------------------------------------------------------------------
    svn:eol-style = native