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

Mike Skells mike.skells@ebizz-consulting.com
Fri, 18 Jun 2004 16:09:58 +0100


I would be interested in using them
Comments inline

> -----Original Message-----
> From: concurrency-interest-admin@cs.oswego.edu 
> [mailto:concurrency-interest-admin@cs.oswego.edu] On Behalf 
> Of Bill Pugh
> Sent: Friday 18 June 2004 14:48
> To: concurrency-interest@altair.cs.oswego.edu
> Subject: [concurrency-interest] Skip Lists, Concurrent Skip 
> Lists and Concurrent Sorted Maps
> 
> 
> 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.

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
List.get(int)
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
the skipping?


> 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 
Map,
SortedMap
SortedList (a List that is always sorted according to a comparator, or
naturally)
SortedSet (as above but a set)
SortedListSet (both a List and Set), useful wher dual semantics is
required

For the Map I wold like to see an interface that allows user to 
getEntry(Object key)
And a way to put a value that will not overwrite i.e. put if not there
already
(but then I woul like to see these on the general map and they are not
specific 
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
> support?
> 
> 	Bill
> 
> _______________________________________________
> Concurrency-interest mailing list
> Concurrency-interest@altair.cs.oswego.edu
> http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
>