w_markable_pointer.h

Go to the documentation of this file.

/*
 * (c) Copyright 2014, Hewlett-Packard Development Company, LP
 */
#ifndef __W_MARKABLE_POINTER_H
#define __W_MARKABLE_POINTER_H

#include "w_defines.h"
#include <cstdint>
#include <cassert>
#include <iostream>
#include "AtomicCounter.hpp"

typedef uint16_t aba_stamp;

template<class T>
class MarkablePointer {
public:
    static const uint64_t MARK_BIT = 0x0000000000000001LL;

    static const uint64_t POINTER_MASK = 0x0000FFFFFFFFFFFELL;

    static const uint64_t STAMP_SHIFT = 48;

    static const uint64_t STAMP_MASK = 0xFFFF000000000000LL;

    MarkablePointer() : _pointer(0) {}

    MarkablePointer(T* pointer, bool mark, aba_stamp stamp = 0)
            : _pointer(combine(pointer, mark, stamp)) {}

    MarkablePointer(const MarkablePointer<T>& other) {
        operator=(other);
    }

    MarkablePointer& operator=(const MarkablePointer<T>& other) {
        // ACCESS_ONCE semantics to make it at least regular.
        _pointer = static_cast<const volatile uintptr_t&>(other._pointer);
        return *this;
    }

    bool operator==(const MarkablePointer& other) const {
        return _pointer == other._pointer;
    }

    bool operator!=(const MarkablePointer& other) const {
        return _pointer != other._pointer;
    }

    void set_mark(bool on) {
        _pointer = (_pointer & ~MARK_BIT) | (on ? MARK_BIT : 0);
    }

    bool is_marked() const {
        return (_pointer & MARK_BIT) != 0;
    }

    aba_stamp get_aba_stamp() const {
        return (_pointer & STAMP_MASK) >> STAMP_SHIFT;
    }

    void set_aba_stamp(aba_stamp stamp) {
        uint64_t stamp_shifted = static_cast<uint64_t>(stamp) << STAMP_SHIFT;
        _pointer = (_pointer & (~STAMP_MASK)) | stamp_shifted;
    }

    void increase_aba_stamp() {
        _pointer += (1LL << STAMP_SHIFT);
    }

    T* get_pointer() const {
        return cast_to_ptr(_pointer & POINTER_MASK);
    }

    T* operator->() const {
        return get_pointer();
    }

    bool is_null() const {
        return (_pointer & POINTER_MASK) == 0;
    }

    uint64_t as_int() const {
        return _pointer;
    }

    bool atomic_cas(T* expected_pointer, T* new_pointer,
                    bool expected_mark, bool new_mark,
                    aba_stamp expected_stamp, aba_stamp new_stamp);

    bool atomic_cas(const MarkablePointer& expected,
                    const MarkablePointer& desired);

    MarkablePointer atomic_swap(const MarkablePointer& new_ptr);

    static uintptr_t combine(T* ptr, bool mark, aba_stamp stamp) {
        assert((cast_to_int(ptr) & (~POINTER_MASK)) == 0);
        uint64_t stamp_shifted = static_cast<uint64_t>(stamp) << STAMP_SHIFT;
        return cast_to_int(ptr) | (mark ? MARK_BIT : 0) | stamp_shifted;
    }

    static uintptr_t cast_to_int(T* ptr) {
        return reinterpret_cast<uintptr_t>(reinterpret_cast<void*>(ptr));
    }

    static T* cast_to_ptr(uintptr_t ptr) {
        return reinterpret_cast<T*>(reinterpret_cast<void*>(ptr));
    }

protected:
    uintptr_t _pointer;
};

template<class NEXT>
struct MarkablePointerChain {
    MarkablePointerChain() : next() {}

    MarkablePointerChain(const MarkablePointerChain& other)
            : next(other.next) {}

    MarkablePointerChain& operator=(const MarkablePointerChain& other) {
        next = other.next;
        return *this;
    }

    MarkablePointer<NEXT> next;
};

template<class T>
inline bool MarkablePointer<T>::atomic_cas(T* expected_pointer, T* desired_pointer,
                                           bool expected_mark, bool desired_mark, aba_stamp expected_stamp,
                                           aba_stamp new_stamp) {
    uintptr_t expected = combine(expected_pointer, expected_mark, expected_stamp);
    uintptr_t desired = combine(desired_pointer, desired_mark, new_stamp);
    return lintel::unsafe::atomic_compare_exchange_strong<uintptr_t>(
            &_pointer, &expected, desired);
}

template<class T>
inline bool MarkablePointer<T>::atomic_cas(const MarkablePointer& expected,
                                           const MarkablePointer& desired) {
    uintptr_t expected_tmp = expected._pointer;
    return lintel::unsafe::atomic_compare_exchange_strong<uintptr_t>(
            &_pointer, &expected_tmp, desired._pointer);
}

template<class T>
inline MarkablePointer<T> MarkablePointer<T>::atomic_swap(const MarkablePointer<T>& new_ptr) {
    uintptr_t old = lintel::unsafe::atomic_exchange<uintptr_t>(&_pointer, new_ptr._pointer);
    MarkablePointer<T> ret;
    ret._pointer = old;
    return ret;
}

template<class T>
inline std::ostream& operator<<(std::ostream& o, const MarkablePointer<T>& x) {
    o << "Markable pointer ";
    if (x.is_null()) {
        o << "<NULL>";
    } else {
        o << x.as_int() << " <marked=" << x.is_marked() << ", stamp=" << x.get_aba_stamp()
          << ", ptr=" << *(x.get_pointer()) << ">";
    }
    return o;
}

#endif // __W_MARKABLE_POINTER_H