[concurrency-interest] Skip Lists, Concurrent Skip Lists and Concurrent Sorted Maps
Fri, 18 Jun 2004 09:48:20 -0400
Doug and I have been working on building implementations of
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
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
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
but are private).
We might also release a nonconcurrent SkipList. For example, that would
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