[concurrency-interest] Skip Lists, Concurrent Skip Lists and Concurrent Sorted Maps

Bill Pugh pugh@cs.umd.edu
Fri, 18 Jun 2004 09:48:20 -0400


Doug and I have been working on building implementations of 
ConcurrentSortedMap,
to parallel ConcurrentHashMap.

We've done both linked list implementations (suitable only for small 
lists) and some
skip list implementations.

We've still got lots of tuning and coding to do, but I thought now 
might be
a good time to ask what other features people would want in such a 
class. We might
be able to fix some shortcomings of SortedTreeMap.

For example, should it also implement PriorityQueue? One issue their is 
that Map uses
Key,Value pairs, while PriorityQueue uses a single value elements. 
Should it be
a PriorityQueue of Entrys, or we just define the SortedSet version of 
SkipLists to
implement PriorityQueue, and don't do anything with the Map version.

It would also be nice to expose methods that, given a key k,
return the entry with the smallest key > k, and another method that 
returns the entry
with the largest key < k. (Methods like this exist in the current 
TreeMap implementation,
but are private).

We might also release a nonconcurrent SkipList. For example, that would 
allow you
to perform rank queries (get me the entry at position 42).  Rank 
queries can't be
done efficiently in a concurrent skip list, but could be done in a 
regular skip list.

So, requests or thoughts on the methods and interfaces we should
support?

	Bill