template<class NEXT>
struct MarkablePointerChain< NEXT >
Atomic Markable Pointer Chain for lock-free list/queue/etc.
- Template Parameters
-
What it is for
Container class like list/queue often needs an object to hold both a value and a pointer to next such object. For example, Chap 9.8 and Chap 10.6 of [HERLIHY] use "Node" class for that purpose. This is required because we need to atomically switch some value and a pointer together in those lock-free algorithm. Otherwise we are risking SEGFAULT when the pointed object gets revoked by other threads.
One way to achieve it is to define a Node class in the container (as in [HERLIHY]), but that means lock-free methods have to allocate and deallocate objects, which is usually expensive and might not be lock-free!
The solution is to have "next" MarkablePointer in the containee class itself. This class is a template for such use and you can either just derive from this class. Yes, it's 8 more bytes, but sometimes we need to pay the price.
- See also
- http://blog.memsql.com/common-pitfalls-in-writing-lock-free-algorithms/
-
MarkablePointer
Dependency
This tiny class is completely header-only. To use, just include w_markable_pointer.h.
