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/rea…
==============================================================================
--- 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/rea…
==============================================================================
--- 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/rea…
==============================================================================
--- 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);