[concurrency-interest] Skip Lists, Concurrent Skip Lists and Concurrent Sorted Maps
Fri, 18 Jun 2004 16:09:58 +0100
I would be interested in using them
> -----Original Message-----
> From: firstname.lastname@example.org
> [mailto:email@example.com] On Behalf
> Of Bill Pugh
> Sent: Friday 18 June 2004 14:48
> To: firstname.lastname@example.org
> Subject: [concurrency-interest] Skip Lists, Concurrent Skip
> Lists and Concurrent Sorted Maps
> 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.
Are these intended to be in the JDK or seperate
> 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.
I think that there are 2 separate implementation, for 2 separate needs.
Both have their uses. I think that both are needed
> 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
I don't understand this. From my understanding a rank query is
which is inefficent for a skip list, as it has to scan every node like a
linked list doesn't it,
As the skiplist doesn't know its position due to the random nature of
> queries can't be
> done efficiently in a concurrent skip list, but could be done in a
> regular skip list.
Fot be the concepts to implement interface are
SortedList (a List that is always sorted according to a comparator, or
SortedSet (as above but a set)
SortedListSet (both a List and Set), useful wher dual semantics is
For the Map I wold like to see an interface that allows user to
And a way to put a value that will not overwrite i.e. put if not there
(but then I woul like to see these on the general map and they are not
to the subject of this email) ;-)
IT might be useful to spec up the api that you are proposing and javadoc
it to allow for an easy review
> So, requests or thoughts on the methods and interfaces we should
> Concurrency-interest mailing list