It is possible to create dynamic lock-free lists that allow for concurrent pushes, pops, and iterations using a "special" reference counted garbage-collector. You implement this using the wonderful cmpxchg8b instruction... ( why didn't intel do a cmpxchg16b for 64-bit? )
The garbage-collector is referenced and collects garbage nodes on the fly, in a 100% lock-free manor. It is used to protect CAS sections. Any nodes that any CAS-section pops, would get tossed in the current garbage collector...
This garbage-collector uses application threads when they reach the zero-reference count on the current garbage-collector. This make this algo as efficient as atomic_ptr.
Look here for some caveats on this:
caveatsHere is my lock-free stack and garbage-collector algo code:
stack.hHere is a pthread test program:
main.cppthread.cppthread.hlfsema.cpplfsema.hmutex.hatomic.hWhat do you guys think of my algo?
;)