Subj : Re: atomic operations api added to AppCore...
To   : comp.programming.threads
From : SenderX
Date : Wed Feb 23 2005 08:36 pm

> Basically, you need *a* memory management system for this, but you could 
> do it with a 32-bit CAS and hazard pointers without too much trouble: the 
> hazard pointers would be necessary only to make sure you don't re-use a 
> node while you shouldn't.
> The way I'm implementing it now limits the deque to 32768 (2^15) nodes, 
> which should be enough for most purposes: I allocate pointers for the 
> nodes when the deque is first allocated in a simple, fixed-size array and 
> keep the status (l,r,s) in a 32-bit structure containing a 15-bit index 
> for both the left and right node (hence the limit of 32768 nodes) - the 
> index points in the array allocated in the beginning - and the status on 
> two bits.
> The nodes are allocated as needed and placed in the array using a first 
> CAS(NULL, &new_node, nodes[n]). For freeing a node, I do an atomic_swap to 
> get the node and set nodes[n] to NULL, then use SMR to free the node.

That will do it. I was wondering about something... How do you avoid aba in 
your smr_hptr_free_list_deq/smr_hptr_free_list_enq functions?


-- 
http://appcore.home.comcast.net/
(portable lock-free data-structures)

.