tagged_ptr.h

Go to the documentation of this file.

 
#ifndef _TAGGED_PTR_CLASS_HEADER_
#define _TAGGED_PTR_CLASS_HEADER_
 
#ifdef WIN32
    #define A_UTILS_HAS_ATOMIC_OPERATORS
    #include <intrin.h>
    #pragma intrinsic (_InterlockedCompareExchange)
    #pragma intrinsic (_InterlockedCompareExchange64)
    #pragma intrinsic (_ReadWriteBarrier)
#else
    #if defined(__i386) || defined(__x86_64)
        #define A_UTILS_HAS_ATOMIC_OPERATORS
    #endif
#endif
 
namespace A_UTILS_NS
{
 
tBool atomic_compare_exchange(tInt32 volatile* pAddress, tInt32 nNewValue, tInt32 nExpectedValue);
 
#ifdef WIN32
    template <class BasicType>
    inline tBool atomic_compare_exchange(volatile BasicType* pAddress, const BasicType& nNewValue, const BasicType& nExpectedValue)
    {
        BasicType nResult = _InterlockedCompareExchange((long*)pAddress, nNewValue, nExpectedValue);
        return (nResult == nExpectedValue);
    }
    template<>
    inline tBool atomic_compare_exchange<tUInt64>(volatile tUInt64* pAddress, const tUInt64& nNewValue, const tUInt64& nExpectedValue)
    {
        tUInt64 nResult = _InterlockedCompareExchange64((tInt64*)pAddress, nNewValue, nExpectedValue);
        return (nResult == nExpectedValue);
    }
#else
    template <class BasicType>
    inline tBool atomic_compare_exchange(volatile BasicType* pAddress, const BasicType& nNewValue, const BasicType& nExpectedValue)
    {
        return __sync_bool_compare_and_swap(pAddress, nExpectedValue, nNewValue);
    }
#endif
 
#ifdef WIN32
    inline tVoid memory_barrier()
    {
        _ReadWriteBarrier();
    }
#else
    inline tVoid memory_barrier()
    {
#if defined(__GNUC__) && ( (__GNUC__ > 4) || ((__GNUC__ >= 4) && \
                                                    (__GNUC_MINOR__ >= 1)))
        __sync_synchronize();
#elif defined(__GNUC__) && defined (__i386__)
        asm volatile("lock; addl $0,0(%%esp)":::"memory");
#else
        #   warning "no memory barrier implemented for this platform"
#endif
    }
#endif
 
 
 
#if (defined(WIN32) && !defined(WIN64)) || \
    defined(A_UTILS_FORCE_TAGGED_POINTER_USE) || \
    ( \
     (defined(__x86_64__) && defined(__GCC_HAVE_SYNC_COMPARE_AND_SWAP_16)) || \
     (!defined(__x86_64__) && \
      ( \
       (defined(__GCC_HAVE_SYNC_COMPARE_AND_SWAP_8) && !defined(A_UTILS_FORCE_NO_TAGGED_POINTER_USE)) || \
       (defined(__GNUC__) && ((__GNUC__ >  4) || ((__GNUC__ == 4) && (__GNUC_MINOR__ > 1))) && !defined(A_UTILS_FORCE_NO_TAGGED_POINTER_USE)) \
      ) \
     ) \
    )
 
#ifdef WIN32
    #define A_UTILS_CAS_ALIGNMENT __declspec(align(8))
#else
    #ifdef __x86_64__
        #define A_UTILS_CAS_ALIGNMENT __attribute__((aligned(16)))
    #else
        #define A_UTILS_CAS_ALIGNMENT __attribute__((aligned(8)))
    #endif
#endif
 
 
#define A_UTILS_TAGGED_POINTER_AVALIABLE
 
template <class T>
class A_UTILS_CAS_ALIGNMENT tagged_ptr
{
    public:
    #ifdef __x86_64__
        typedef int tCompareAndSwapType __attribute__ ((mode (TI)));    
        typedef tUInt64 tTag;                                           
    #else
        typedef tUInt64 tCompareAndSwapType;    
        typedef tUInt32 tTag;                   
    #endif
 
    private:
        T*      m_pPtr;
        tTag    m_nTag;
 
    public:
        tagged_ptr(): m_pPtr(nullptr), m_nTag(0)
        {
        }
 
        tagged_ptr(tagged_ptr const& oPtr)
        {
            Set(oPtr);
        }
 
        explicit tagged_ptr(T* pPtr, tTag nTag = 0): m_pPtr(pPtr), m_nTag(nTag)
        {
        }
 
        void operator=(tagged_ptr const& oPtr)
        {
            Set(oPtr);
        }
 
        void Set(tagged_ptr const& oPtr)
        {
            m_pPtr = oPtr.m_pPtr;
            m_nTag = oPtr.m_nTag;
        }
 
        void Set(T* pPtr, tTag nTag = 0)
        {
            m_pPtr = pPtr;
            m_nTag = nTag;
        }
 
        bool operator== (tagged_ptr const& oPtr) const
        {
            return (m_pPtr == oPtr.m_pPtr) && (m_nTag == oPtr.m_nTag);
        }
 
        bool operator!= (tagged_ptr const& oPtr) const
        {
            return !operator==(oPtr);
        }
 
        T* GetPtr() const
        {
            return m_pPtr;
        }
 
        tTag GetTag() const
        {
            return m_nTag;
        }
 
        tBool CompareAndSwap(tagged_ptr const& oOldVal, T* pNewPtr)
        {
            return CompareAndSwap(oOldVal, pNewPtr, oOldVal.m_nTag + 1);
        }
 
        tBool CompareAndSwap(tagged_ptr const& oOldVal, T* pNewPtr, tTag nTag)
        {
            tagged_ptr oNewVal(pNewPtr, nTag);
            return atomic_compare_exchange<tCompareAndSwapType>((tCompareAndSwapType*) this, *(tCompareAndSwapType*) &oNewVal, *(tCompareAndSwapType*) &oOldVal);
        }
 
        T* operator->() const
        {
            return m_pPtr;
        }
 
        operator bool(void) const
        {
            return m_pPtr != nullptr;
        }
};
 
#elif (defined(__x86_64__) \
        && defined(__GCC_HAVE_SYNC_COMPARE_AND_SWAP_8) \
        && !defined(A_UTILS_FORCE_NO_TAGGED_POINTER_USE) \
        || defined(WIN64) \
        || defined(__ARM_ARCH_8A))
// 64 Bit Linux without 128 Bit compare and swap operation
// we use packed pointers since to OS uses only 48 bit for addresses.
// this should also work for ARMv8-a - http://infocenter.arm.com/help/index.jsp?topic=/com.arm.doc.den0024a/ch12s04.html
 
#ifdef WIN64
    #define A_UTILS_CAS_ALIGNMENT __declspec(align(8))
#else
    #define A_UTILS_CAS_ALIGNMENT __attribute__((aligned(8)))
#endif
 
#define A_UTILS_TAGGED_POINTER_AVALIABLE
 
template <class T>
class A_UTILS_CAS_ALIGNMENT tagged_ptr
{
    public:
        typedef tUInt64 tCompareAndSwapType;    
        typedef tUInt16 tTag;                   
 
    private:
        union tCompressedPtr
        {
            tCompareAndSwapType nValue;
            tTag nTag[4];
        };
 
        static const tInt s_nTagIndex = 3;
        static const tCompareAndSwapType s_nPtrMask = 0xffffffffffff; //(1L<<48L)-1;
 
        // this our actual storage
        tCompressedPtr m_oPtr;
 
    public:
        tagged_ptr()
        {
            m_oPtr.nValue = 0;
        }
 
        tagged_ptr(tagged_ptr const& oPtr)
        {
            Set(oPtr);
        }
 
        explicit tagged_ptr(T* pPtr, tTag nTag = 0)
        {
            Set(pPtr, nTag);
        }
 
        void operator=(tagged_ptr const& oPtr)
        {
            Set(oPtr);
        }
 
        void Set(tagged_ptr const& oPtr)
        {
            m_oPtr = oPtr.m_oPtr;
        }
 
        void Set(T* pPtr, tTag nTag = 0)
        {
            m_oPtr.nValue = tCompareAndSwapType(pPtr);
            m_oPtr.nTag[s_nTagIndex] = nTag;
        }
 
        bool operator== (tagged_ptr const& oPtr) const
        {
            return m_oPtr.nValue == oPtr.m_oPtr.nValue;
        }
 
        bool operator!= (tagged_ptr const& oPtr) const
        {
            return !operator==(oPtr);
        }
 
        T* GetPtr() const
        {
            return (T*)(m_oPtr.nValue & s_nPtrMask);
        }
 
        tTag GetTag() const
        {
            return m_oPtr.nTag[s_nTagIndex];
        }
 
        tBool CompareAndSwap(tagged_ptr const& oOldVal, T* pNewPtr)
        {
            return CompareAndSwap(oOldVal, pNewPtr, oOldVal.GetTag() + 1);
        }
 
        tBool CompareAndSwap(tagged_ptr const& oOldVal, T* pNewPtr, tTag nTag)
        {
            tagged_ptr oNewVal(pNewPtr, nTag);
            return atomic_compare_exchange<tCompareAndSwapType>((tCompareAndSwapType*) this, *(tCompareAndSwapType*) &oNewVal, *(tCompareAndSwapType*) &oOldVal);
        }
 
        T* operator->() const
        {
            return GetPtr();
        }
 
        operator bool(void) const
        {
            return GetPtr() != nullptr;
        }
};
 
#else
    // we're out of luck! We could probably offer a fallback with mutexes.
    #warning "No required compare and swap operation avaliable. cLockFree* classes will use mutexes."
#endif
 
}
 
#endif