BDSkipList

by David W. Jeske

BDSkipList is an open-source public domain, restriction free bi-directional and concurrent SkipList implementation for C#.

Download Source

BDSkipList-20101210.zip

Information

This C# SkipList implementation is similar to a SortedDictionary, except that it offers a bi-directional and efficiently key-qualified scanning interface, IScannable. At a basic level, using this skiplist is similar to using any other simple collection.

   BDSkipList mylist = new BDSkipList();
   mylist["abc"] = 1;
   mylist["def"] = 2;
   mylist["ghi"] = 3;

One can use the default enumeration to walk through all elements in the list.

  foreach (KeyValuePair(string,int) kvp in mylist) {
    System.Console.Writeline(" {0} = {1} ", kvp.Key, kvp.Value);
  }

The IScannable interface provides some more advanced scanning functionality.


public interface IScanner
    {
        // currently scans are always performed (>=,<=) on the lowest/highest 
        // endpoints, because you can use MatchTo() to decide if you want to produce the record
        // TODO: consider if we need to simplify and define (>,<) operations on endpoints
        bool MatchTo(K candidate);
        IComparable genLowestKeyTest(); 
        IComparable genHighestKeyTest();
    }

public interface IScannable
    {
        KeyValuePair FindNext(IComparable keytest,bool equal_ok);
        KeyValuePair FindPrev(IComparable keytest,bool equal_ok);
        IEnumerable> scanForward(IScanner scanner);   
        IEnumerable> scanBackward(IScanner scanner);
    }

In addition to simple single-element FindNext and FindPrev walks, one can also use the scanForward and scanBackward iterators to efficiently scan over a subset of records in either direction. The underlying implementation does an efficient SkipList search for the first element before beginning the iteration, making it efficient to scan subsets even when the collection contains very large numbers of records.


    // scan backwards through keys
    foreach ( KeyValuePair kvp in mylist.scanBackward(ScanRange.All()) ) {
        System.Console.Writeline(" {0} = {1} ", kvp.Key, kvp.Value);
    }

    // scan over a subset of keys
    foreach (KeyValuePair kvp in mylist.scanForward(new ScanRange("d","f")) {
        System.Console.Writeline(" {0} = {1} ", kvp.Key, kvp.Value);
    }

The default ScanRange handler always performs inclusive matches on the endpoint keys. However, by defining your own IScanner implementation you can provide a MatchTo() implementation which makes endpoints exclusive, or implements other filters over the return result set.

Enjoy!