cds/details/marked_ptr.h

   1 //$$CDS-header$$
   2
   3 #ifndef __CDS_DETAILS_MARKED_PTR_H
   4 #define __CDS_DETAILS_MARKED_PTR_H
   5
   6 #include <cds/cxx11_atomic.h>
   7
   8 namespace cds {
   9     namespace details {
  10
  11         /// Marked pointer
  12         /**
  13             On the modern architectures, the default data alignment is 4 (for 32bit) or 8 byte for 64bit.
  14             Therefore, the least 2 or 3 bits of the pointer is always zero and can
  15             be used as a bitfield to store logical flags. This trick is widely used in
  16             lock-free programming to operate with the pointer and its flags atomically.
  17
  18             Template parameters:
  19             - T - type of pointer
  20             - Bitmask - bitmask of least unused bits
  21         */
  22         template <typename T, int Bitmask>
  23         class marked_ptr
  24         {
  25             T *     m_ptr   ;   ///< pointer and its mark bits
  26
  27         public:
  28             typedef T       value_type      ;       ///< type of value the class points to
  29             typedef T *     pointer_type    ;       ///< type of pointer
  30             static CDS_CONSTEXPR_CONST uintptr_t bitmask = Bitmask  ;   ///< bitfield bitmask
  31             static CDS_CONSTEXPR_CONST uintptr_t pointer_bitmask = ~bitmask ; ///< pointer bitmask
  32
  33         public:
  34             /// Constructs null marked pointer. The flag is cleared.
  35             CDS_CONSTEXPR marked_ptr() CDS_NOEXCEPT
  36                 : m_ptr( null_ptr<pointer_type>() )
  37             {}
  38
  39             /// Constructs marked pointer with \p ptr value. The least bit(s) of \p ptr is the flag.
  40             CDS_CONSTEXPR explicit marked_ptr( value_type * ptr ) CDS_NOEXCEPT
  41                 : m_ptr( ptr )
  42             {}
  43
  44             /// Constructs marked pointer with \p ptr value and \p nMask flag.
  45             /**
  46                 The \p nMask argument defines the OR-bits
  47             */
  48             marked_ptr( value_type * ptr, int nMask ) CDS_NOEXCEPT
  49                 : m_ptr( ptr )
  50             {
  51                 assert( bits() == 0 );
  52                 *this |= nMask;
  53             }
  54
  55 #   ifdef CDS_CXX11_EXPLICITLY_DEFAULTED_FUNCTION_SUPPORT
  56             /// Copy constructor
  57             marked_ptr( marked_ptr const& src ) CDS_NOEXCEPT_DEFAULTED = default;
  58             /// Copy-assignment operator
  59             marked_ptr& operator =( marked_ptr const& p ) CDS_NOEXCEPT_DEFAULTED = default;
  60 #       if defined(CDS_MOVE_SEMANTICS_SUPPORT) && !defined(CDS_DISABLE_DEFAULT_MOVE_CTOR)
  61             //@cond
  62             marked_ptr( marked_ptr&& src ) CDS_NOEXCEPT_DEFAULTED = default;
  63             marked_ptr& operator =( marked_ptr&& p ) CDS_NOEXCEPT_DEFAULTED = default;
  64             //@endcond
  65 #       endif
  66 #   else
  67             /// Copy constructor
  68             marked_ptr( marked_ptr const& src ) CDS_NOEXCEPT
  69                 : m_ptr( src.m_ptr )
  70             {}
  71
  72             /// Copy-assignment operator
  73             marked_ptr& operator =( marked_ptr const& p ) CDS_NOEXCEPT
  74             {
  75                 m_ptr = p.m_ptr;
  76                 return *this;
  77             }
  78 #   endif
  79
  80             //TODO: make move ctor
  81
  82         private:
  83             //@cond
  84             static uintptr_t   to_int( value_type * p ) CDS_NOEXCEPT
  85             {
  86                 return reinterpret_cast<uintptr_t>( p );
  87             }
  88
  89             static value_type * to_ptr( uintptr_t n ) CDS_NOEXCEPT
  90             {
  91                 return reinterpret_cast< value_type *>( n );
  92             }
  93
  94             uintptr_t   to_int() const CDS_NOEXCEPT
  95             {
  96                 return to_int( m_ptr );
  97             }
  98             //@endcond
  99
 100         public:
 101             /// Returns the pointer without mark bits (real pointer) const version
 102             value_type *        ptr() const CDS_NOEXCEPT
 103             {
 104                 return to_ptr( to_int() & ~bitmask );
 105             }
 106
 107             /// Returns the pointer and bits together
 108             value_type *        all() const CDS_NOEXCEPT
 109             {
 110                 return m_ptr;
 111             }
 112
 113             /// Returns the least bits of pointer according to \p Bitmask template argument of the class
 114             uintptr_t bits() const CDS_NOEXCEPT
 115             {
 116                 return to_int() & bitmask;
 117             }
 118
 119             /// Analogue for \ref ptr
 120             value_type * operator ->() const CDS_NOEXCEPT
 121             {
 122                 return ptr();
 123             }
 124
 125             /// Assignment operator sets markup bits to zero
 126             marked_ptr operator =( T * p ) CDS_NOEXCEPT
 127             {
 128                 m_ptr = p;
 129                 return *this;
 130             }
 131
 132             /// Set LSB bits as <tt>bits() | nBits</tt>
 133             marked_ptr& operator |=( int nBits ) CDS_NOEXCEPT
 134             {
 135                 assert( (nBits & pointer_bitmask) == 0 );
 136                 m_ptr = to_ptr( to_int() | nBits );
 137                 return *this;
 138             }
 139
 140             /// Set LSB bits as <tt>bits() & nBits</tt>
 141             marked_ptr& operator &=( int nBits ) CDS_NOEXCEPT
 142             {
 143                 assert( (nBits & pointer_bitmask) == 0 );
 144                 m_ptr = to_ptr( to_int() & (pointer_bitmask | nBits) );
 145                 return *this;
 146             }
 147
 148             /// Set LSB bits as <tt>bits() ^ nBits</tt>
 149             marked_ptr& operator ^=( int nBits ) CDS_NOEXCEPT
 150             {
 151                 assert( (nBits & pointer_bitmask) == 0 );
 152                 m_ptr = to_ptr( to_int() ^ nBits );
 153                 return *this;
 154             }
 155
 156             /// Returns <tt>p |= nBits</tt>
 157             friend marked_ptr operator |( marked_ptr p, int nBits) CDS_NOEXCEPT
 158             {
 159                 p |= nBits;
 160                 return p;
 161             }
 162
 163             /// Returns <tt>p |= nBits</tt>
 164             friend marked_ptr operator |( int nBits, marked_ptr p ) CDS_NOEXCEPT
 165             {
 166                 p |= nBits;
 167                 return p;
 168             }
 169
 170             /// Returns <tt>p &= nBits</tt>
 171             friend marked_ptr operator &( marked_ptr p, int nBits) CDS_NOEXCEPT
 172             {
 173                 p &= nBits;
 174                 return p;
 175             }
 176
 177             /// Returns <tt>p &= nBits</tt>
 178             friend marked_ptr operator &( int nBits, marked_ptr p ) CDS_NOEXCEPT
 179             {
 180                 p &= nBits;
 181                 return p;
 182             }
 183
 184             /// Returns <tt>p ^= nBits</tt>
 185             friend marked_ptr operator ^( marked_ptr p, int nBits) CDS_NOEXCEPT
 186             {
 187                 p ^= nBits;
 188                 return p;
 189             }
 190             /// Returns <tt>p ^= nBits</tt>
 191             friend marked_ptr operator ^( int nBits, marked_ptr p ) CDS_NOEXCEPT
 192             {
 193                 p ^= nBits;
 194                 return p;
 195             }
 196
 197             /// Inverts LSBs of pointer \p p
 198             friend marked_ptr operator ~( marked_ptr p ) CDS_NOEXCEPT
 199             {
 200                 return p ^ marked_ptr::bitmask;
 201             }
 202
 203
 204             /// Comparing two marked pointer including its mark bits
 205             friend bool operator ==( marked_ptr p1, marked_ptr p2 ) CDS_NOEXCEPT
 206             {
 207                 return p1.all() == p2.all();
 208             }
 209
 210             /// Comparing marked pointer and raw pointer, mark bits of \p p1 is ignored
 211             friend bool operator ==( marked_ptr p1, value_type const * p2 ) CDS_NOEXCEPT
 212             {
 213                 return p1.ptr() == p2;
 214             }
 215
 216             /// Comparing marked pointer and raw pointer, mark bits of \p p2 is ignored
 217             friend bool operator ==( value_type const * p1, marked_ptr p2 ) CDS_NOEXCEPT
 218             {
 219                 return p1 == p2.ptr();
 220             }
 221
 222             /// Comparing two marked pointer including its mark bits
 223             friend bool operator !=( marked_ptr p1, marked_ptr p2 ) CDS_NOEXCEPT
 224             {
 225                 return p1.all() != p2.all();
 226             }
 227
 228             /// Comparing marked pointer and raw pointer, mark bits of \p p1 is ignored
 229             friend bool operator !=( marked_ptr p1, value_type const * p2 ) CDS_NOEXCEPT
 230             {
 231                 return p1.ptr() != p2;
 232             }
 233
 234             /// Comparing marked pointer and raw pointer, mark bits of \p p2 is ignored
 235             friend bool operator !=( value_type const * p1, marked_ptr p2 ) CDS_NOEXCEPT
 236             {
 237                 return p1 != p2.ptr();
 238             }
 239
 240             //@cond
 241             /// atomic< marked_ptr< T, Bitmask > > support
 242             T *& impl_ref() CDS_NOEXCEPT
 243             {
 244                 return m_ptr;
 245             }
 246             //@endcond
 247         };
 248     }   // namespace details
 249
 250 }   // namespace cds
 251
 252 //@cond
 253 CDS_CXX11_ATOMIC_BEGIN_NAMESPACE
 254
 255     template <typename T, int Bitmask >
 256     class atomic< cds::details::marked_ptr<T, Bitmask> >
 257     {
 258     private:
 259         typedef cds::details::marked_ptr<T, Bitmask> marked_ptr;
 260         typedef CDS_ATOMIC::atomic<T *>  atomic_impl;
 261
 262         atomic_impl m_atomic;
 263     public:
 264         bool is_lock_free() const volatile CDS_NOEXCEPT
 265         {
 266             return m_atomic.is_lock_free();
 267         }
 268         bool is_lock_free() const CDS_NOEXCEPT
 269         {
 270             return m_atomic.is_lock_free();
 271         }
 272
 273         void store(marked_ptr val, memory_order order = memory_order_seq_cst) volatile CDS_NOEXCEPT
 274         {
 275             m_atomic.store( val.all(), order );
 276         }
 277         void store(marked_ptr val, memory_order order = memory_order_seq_cst) CDS_NOEXCEPT
 278         {
 279             m_atomic.store( val.all(), order );
 280         }
 281
 282         marked_ptr load(memory_order order = memory_order_seq_cst) const volatile CDS_NOEXCEPT
 283         {
 284             return marked_ptr( m_atomic.load( order ));
 285         }
 286         marked_ptr load(memory_order order = memory_order_seq_cst) const CDS_NOEXCEPT
 287         {
 288             return marked_ptr( m_atomic.load( order ));
 289         }
 290
 291         operator marked_ptr() const volatile CDS_NOEXCEPT
 292         {
 293             return load();
 294         }
 295         operator marked_ptr() const CDS_NOEXCEPT
 296         {
 297             return load();
 298         }
 299
 300         marked_ptr exchange(marked_ptr val, memory_order order = memory_order_seq_cst) volatile CDS_NOEXCEPT
 301         {
 302             return marked_ptr( m_atomic.exchange( val.all(), order ));
 303         }
 304         marked_ptr exchange(marked_ptr val, memory_order order = memory_order_seq_cst) CDS_NOEXCEPT
 305         {
 306             return marked_ptr( m_atomic.exchange( val.all(), order ));
 307         }
 308
 309         bool compare_exchange_weak(marked_ptr& expected, marked_ptr desired, memory_order success_order, memory_order failure_order) volatile CDS_NOEXCEPT
 310         {
 311             return m_atomic.compare_exchange_weak( expected.impl_ref(), desired.all(), success_order, failure_order );
 312         }
 313         bool compare_exchange_weak(marked_ptr& expected, marked_ptr desired, memory_order success_order, memory_order failure_order) CDS_NOEXCEPT
 314         {
 315             return m_atomic.compare_exchange_weak( expected.impl_ref(), desired.all(), success_order, failure_order );
 316         }
 317         bool compare_exchange_strong(marked_ptr& expected, marked_ptr desired, memory_order success_order, memory_order failure_order) volatile CDS_NOEXCEPT
 318         {
 319             return m_atomic.compare_exchange_strong( expected.impl_ref(), desired.all(), success_order, failure_order );
 320         }
 321         bool compare_exchange_strong(marked_ptr& expected, marked_ptr desired, memory_order success_order, memory_order failure_order) CDS_NOEXCEPT
 322         {
 323             return m_atomic.compare_exchange_strong( expected.impl_ref(), desired.all(), success_order, failure_order );
 324         }
 325         bool compare_exchange_weak(marked_ptr& expected, marked_ptr desired, memory_order success_order = memory_order_seq_cst) volatile CDS_NOEXCEPT
 326         {
 327             return m_atomic.compare_exchange_weak( expected.impl_ref(), desired.all(), success_order );
 328         }
 329         bool compare_exchange_weak(marked_ptr& expected, marked_ptr desired, memory_order success_order = memory_order_seq_cst) CDS_NOEXCEPT
 330         {
 331             return m_atomic.compare_exchange_weak( expected.impl_ref(), desired.all(), success_order );
 332         }
 333         bool compare_exchange_strong(marked_ptr& expected, marked_ptr desired, memory_order success_order = memory_order_seq_cst) volatile CDS_NOEXCEPT
 334         {
 335             return m_atomic.compare_exchange_strong( expected.impl_ref(), desired.all(), success_order );
 336         }
 337         bool compare_exchange_strong(marked_ptr& expected, marked_ptr desired, memory_order success_order = memory_order_seq_cst) CDS_NOEXCEPT
 338         {
 339             return m_atomic.compare_exchange_strong( expected.impl_ref(), desired.all(), success_order );
 340         }
 341
 342         CDS_CONSTEXPR atomic() CDS_NOEXCEPT
 343             : m_atomic( cds::null_ptr<T *>() )
 344         {}
 345
 346         CDS_CONSTEXPR explicit atomic(marked_ptr val) CDS_NOEXCEPT
 347             : m_atomic( val.all() )
 348         {}
 349         CDS_CONSTEXPR explicit atomic(T * p) CDS_NOEXCEPT
 350             : m_atomic( p )
 351         {}
 352
 353 #   ifdef CDS_CXX11_DELETE_DEFINITION_SUPPORT
 354         atomic(const atomic&) = delete;
 355         atomic& operator=(const atomic&) = delete;
 356         atomic& operator=(const atomic&) volatile = delete;
 357 #   endif
 358
 359         marked_ptr operator=(marked_ptr val) volatile CDS_NOEXCEPT
 360         {
 361             store( val );
 362             return val;
 363         }
 364         marked_ptr operator=(marked_ptr val) CDS_NOEXCEPT
 365         {
 366             store( val );
 367             return val;
 368         }
 369     };
 370
 371 CDS_CXX11_ATOMIC_END_NAMESPACE
 372 //@endcond
 373
 374 #endif  // #ifndef __CDS_DETAILS_MARKED_PTR_H