[cfinck] 68262: [SKIPLIST] - Add a LookupNodeByIndexSkiplist function and a small test for it in skiplist_test. - Remove a redundant double-set in LookupElementSkiplist. Yes, we now have one lookup...

Author: cfinck
Date: Thu Jun 25 13:12:01 2015
New Revision: 68262

URL: http://svn.reactos.org/svn/reactos?rev=68262&view=rev
Log:
[SKIPLIST]
- Add a LookupNodeByIndexSkiplist function and a small test for it in skiplist_test.
- Remove a redundant double-set in LookupElementSkiplist.

Yes, we now have one lookup function that accepts search criteria and returns an element and another one that accepts an index and returns a SKIPLIST_NODE.
It's simply because I have exactly these two cases :)
You're free to implement the two missing functions or refactor this code another way.

Modified:
    branches/colins-printing-for-freedom/reactos/lib/skiplist/skiplist.c
    branches/colins-printing-for-freedom/reactos/lib/skiplist/skiplist.h
    branches/colins-printing-for-freedom/reactos/lib/skiplist/skiplist_test.c

Modified: branches/colins-printing-for-freedom/reactos/lib/skiplist/skiplist.c
URL: http://svn.reactos.org/svn/reactos/branches/colins-printing-for-freedom/reac...
==============================================================================
--- branches/colins-printing-for-freedom/reactos/lib/skiplist/skiplist.c	[iso-8859-1] (original)
+++ branches/colins-printing-for-freedom/reactos/lib/skiplist/skiplist.c	[iso-8859-1] Thu Jun 25 13:12:01 2015
@@ -366,8 +366,6 @@
     //    * 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)
@@ -395,3 +393,48 @@
     // Return the stored element of the found node.
     return pNode->Element;
 }
+
+/**
+ * @name LookupNodeByIndexSkiplist
+ *
+ * Looks up a node in the Skiplist at the given position. The efficiency of this operation is O(log N) on average.
+ *
+ * @param Skiplist
+ * Pointer to the SKIPLIST structure to operate on.
+ *
+ * @param ElementIndex
+ * Zero-based position of the node in the Skiplist.
+ *
+ * @return
+ * Returns the found node or NULL if the position is invalid.
+ */
+PSKIPLIST_NODE
+LookupNodeByIndexSkiplist(PSKIPLIST Skiplist, DWORD ElementIndex)
+{
+    CHAR i;
+    DWORD dwIndex = 0;
+    PSKIPLIST_NODE pNode = &Skiplist->Head;
+
+    // The only way the node can't be found is when the index is out of range.
+    if (ElementIndex >= Skiplist->NodeCount)
+        return NULL;
+
+    // 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.
+    for (i = Skiplist->MaximumLevel + 1; --i >= 0;)
+    {
+        // We compare with <= instead of < here, because the added distances make up a 1-based index while ElementIndex is zero-based,
+        // so we have to jump one node further.
+        while (pNode->Next[i] && dwIndex + pNode->Distance[i] <= ElementIndex)
+        {
+            dwIndex += pNode->Distance[i];
+            pNode = pNode->Next[i];
+        }
+    }
+
+    // We are right in front of the node we're looking for now.
+    return pNode->Next[0];
+}

Modified: branches/colins-printing-for-freedom/reactos/lib/skiplist/skiplist.h
URL: http://svn.reactos.org/svn/reactos/branches/colins-printing-for-freedom/reac...
==============================================================================
--- branches/colins-printing-for-freedom/reactos/lib/skiplist/skiplist.h	[iso-8859-1] (original)
+++ branches/colins-printing-for-freedom/reactos/lib/skiplist/skiplist.h	[iso-8859-1] Thu Jun 25 13:12:01 2015
@@ -49,5 +49,6 @@
 BOOL InsertTailElementSkiplist(PSKIPLIST Skiplist, PVOID Element);
 PVOID DeleteElementSkiplist(PSKIPLIST Skiplist, PVOID Element);
 PVOID LookupElementSkiplist(PSKIPLIST Skiplist, PVOID Element, PDWORD ElementIndex);
+PSKIPLIST_NODE LookupNodeByIndexSkiplist(PSKIPLIST Skiplist, DWORD ElementIndex);

#endif

Modified: branches/colins-printing-for-freedom/reactos/lib/skiplist/skiplist_test.c
URL: http://svn.reactos.org/svn/reactos/branches/colins-printing-for-freedom/reac...
==============================================================================
--- branches/colins-printing-for-freedom/reactos/lib/skiplist/skiplist_test.c	[iso-8859-1] (original)
+++ branches/colins-printing-for-freedom/reactos/lib/skiplist/skiplist_test.c	[iso-8859-1] Thu Jun 25 13:12:01 2015
@@ -67,6 +67,7 @@
     DWORD ElementIndex;
     DWORD i;
     SKIPLIST Skiplist;
+    PSKIPLIST_NODE pNode;

system("mode con cols=300");
     InitializeSkiplist(&Skiplist, MyAlloc, MyCompare, MyFree);
@@ -83,6 +84,10 @@
     for (i = 0; i < 40; i++)
         InsertElementSkiplist(&Skiplist, (PVOID)(rand() % 100));

+    // Output the third element (with zero-based index 2).
+    pNode = LookupNodeByIndexSkiplist(&Skiplist, 2);
+    printf("Element = %lu for index 2\n", (DWORD)pNode->Element);
+
     // 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);