Subj : Re: Lock-free binary trees
To   : comp.programming.threads
From : Joe Seigh
Date : Sun Sep 18 2005 05:09 pm

gottlobfrege@gmail.com wrote:
> Joe Seigh wrote:
> 
>>I've been playing around with a reader lock-free
>>binary tree implementation in Java.  Looks like
>>it does what I think it should be doing.  It
>>would probably be neat to graphically display
>>the tree in real time and step it through the
>>various operations.  That would be cool.
>>
>>
> 
> 
> I'm not sure _exactly_ what you mean by reader lock free (ie writers
> wait until no readers?), but on a similar vein, it dawned on me the
> other day that a lock-free skiplist might be doable, and might be a
> useful replacement for maps.  So, all excited that this might be a new
> idea, I quickly got shot down by Google - it looks like lock free skip
> lists have just been tackled in the last couple of years...
> 

No locks required for readers, just writers.  Skip lists are essentially
linked lists and doing lock-free linked lists has been around for ages
and is fairly well understood.

-- 
Joe Seigh

When you get lemons, you make lemonade.
When you get hardware, you make software.

.