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

Tim Peierls tim@peierls.net
Fri, 18 Jun 2004 14:42:45 -0400

Bill Pugh wrote:
> So, requests or thoughts on the methods and interfaces we should support?

PriorityQueue and PriorityBlockingQueue both lack a decreaseKey
operation, which among other things has the practical effect of forcing
implementors of Dijkstra shortest path searches to use remove-and-
reinsert as a poor man's decreaseKey.

To support a real decreaseKey, you would need to have an insert method
that returned a search finger, which I gather from the SkipList Cookbook
is quite feasible with skip lists. It's too late for j.u.PQ and
j.u.c.PBQ, but maybe it isn't too late for ConcurrentSkipList? This would
also be an excellent reason to provide a nonconcurrent skip list, at
least in my book.