skiplist

A generic C skiplist, with some extensions.

Skiplists are probabilistic alternatives to binary search trees. Nodes are in multiple lists up to a given level, forming a series of parallel linked lists, where each level up consists of 25% of the nodes of the previous level (on average). Searches run from the highest level skipping over large numbers of elements and moving down the levels to find an item in logarithmic randomized time.

This skiplist can efficiently move to the next and previous nodes, and select the n-th ranked element in O(log n) time. It has average storage costs of 3.33*sizeof(void *) and 0.33*sizeof(int), close to the limits of other compact trees like Jason Evan's rb.h. However, since nodes are allocated dynamically, actual memory use will be somewhat higher.

Also included are two simple testing tools; sl, for testing skiplist, and kl, for testing the bundled kazlib hash. They should all build on most OS's with bmake; tested on FreeBSD.

Listing of /files/c/skiplist/
FilenameFilesizeLast Modified
testskiplist.c5.67k2009-03-21 12:03
Makefile0.73k2009-03-21 12:03
Makefile.kl0.09k2009-03-21 12:03
Makefile.sl0.17k2009-03-21 12:03
dict.c34.67k2009-03-21 12:03
dict.h4.55k2009-03-21 12:03
kaztest.c1.68k2009-03-21 12:03
skiplist.c11.1k2009-03-21 12:03
skiplist.h3.19k2009-03-21 12:03