Concurrent skip list. It is mostly lock-free and fine-grained locking is used for conflict resolution.

The implementation is based on the work described in the paper "A Provably Correct Scalable Concurrent Skip List"

The implementation has an interface that mimics the interface of STL containers like std::set and std::map.

When getting iterators to contained objects mit is guaranteed that the iterator will point to a living object while the accessor that produced it is alive. So to say it differently, you MUST keep the accessor to the list alive while you still have some iterators to items that are contained in the list. That is the only usage in which the list guarantees that the item that is pointed to by the iterator doesn't get deleted (freed) by another thread.

The proposed implementation is in Java so the authors don't worry about garbage collection. This implementation uses the garbage collector that is described previously in this file. The garbage collection is triggered occasionally on each operation that is executed on the list through an accessor.

New link for the paper: http://people.csail.mit.edu/shanir/publications/OPODIS2006-BA.pdf