What is the C++ 11 atomic library equivalent of Java's AtomicMarkableReference<T>

Question

Need this call to implement a lock-free linked list. An AtomicMarkableReference is an object from the java.util.concurrent.atomic package that encapsulates both a reference to an object of type T and a Boolean mark. These fields can be updated atomically,either together or individually.

Thank You.

Answer 1

Assuming object's alignement be more than 1, you may use the last bit of the pointer as a boolean mark:

template<class T>
class MarkableReference
{
private:
    uintptr_t val;
    static const uintptr_t mask = 1;
public:
    MarkableReference(T* ref = NULL, bool mark = false)
    {
        val = ((uintptr_t)ref & ~mask) | (mark ? 1 : 0);
    }
    T* getRef(void)
    {
        return (T*)(val & ~mask);
    }
    bool getMark(void)
    {
        return (val & mask);
    }
};

For perform atomic operations, you need to create atomic variable from this class. E.g., if type of object, pointed by a reference, should be int, you may create this variable:

atomic<MarkableReference<int>> mRef;

For variable mRef you may apply any operation, which is applied for normal atomic. For example, Compare-and-Set (CAS):

int a;
int b;
...
// Atomically change pair (&a, true) to (&b, false).
MarkableReference<int> old = mRef.load();
if(old == MarkableReference(&a, true))
{
    if(mRef.compare_exchange_strong(old, MarkableReference(&b, false)))
    {
        // Successful CAS
    }
}
// 'old' contains other value. (Unsuccessfull CAS)