[SKIPLIST]
authorColin Finck <colin@reactos.org>
Fri, 19 Jun 2015 10:27:46 +0000 (10:27 +0000)
committerColin Finck <colin@reactos.org>
Fri, 19 Jun 2015 10:27:46 +0000 (10:27 +0000)
commit86ad9580b11f56a23a551c445a896d1d54f0e9d9
tree1b3a4f14aed71ab828cd735bf132af7d28b43e27
parent888171ae186578dbe4b481308be4808c8e122520
[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

svn path=/branches/colins-printing-for-freedom/; revision=68191
reactos/lib/CMakeLists.txt
reactos/lib/skiplist/CMakeLists.txt [new file with mode: 0644]
reactos/lib/skiplist/skiplist.c [new file with mode: 0644]
reactos/lib/skiplist/skiplist.h [new file with mode: 0644]
reactos/lib/skiplist/skiplist_test.c [new file with mode: 0644]