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( nullptr )
  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             /// Copy constructor
  56             marked_ptr( marked_ptr const& src ) CDS_NOEXCEPT_DEFAULTED = default;
  57             /// Copy-assignment operator
  58             marked_ptr& operator =( marked_ptr const& p ) CDS_NOEXCEPT_DEFAULTED = default;
  59 #       if defined(CDS_MOVE_SEMANTICS_SUPPORT) && !defined(CDS_DISABLE_DEFAULT_MOVE_CTOR)
  60             //@cond
  61             marked_ptr( marked_ptr&& src ) CDS_NOEXCEPT_DEFAULTED = default;
  62             marked_ptr& operator =( marked_ptr&& p ) CDS_NOEXCEPT_DEFAULTED = default;
  63             //@endcond
  64 #       endif
  65
  66             //TODO: make move ctor
  67
  68         private:
  69             //@cond
  70             static uintptr_t   to_int( value_type * p ) CDS_NOEXCEPT
  71             {
  72                 return reinterpret_cast<uintptr_t>( p );
  73             }
  74
  75             static value_type * to_ptr( uintptr_t n ) CDS_NOEXCEPT
  76             {
  77                 return reinterpret_cast< value_type *>( n );
  78             }
  79
  80             uintptr_t   to_int() const CDS_NOEXCEPT
  81             {
  82                 return to_int( m_ptr );
  83             }
  84             //@endcond
  85
  86         public:
  87             /// Returns the pointer without mark bits (real pointer) const version
  88             value_type *        ptr() const CDS_NOEXCEPT
  89             {
  90                 return to_ptr( to_int() & ~bitmask );
  91             }
  92
  93             /// Returns the pointer and bits together
  94             value_type *        all() const CDS_NOEXCEPT
  95             {
  96                 return m_ptr;
  97             }
  98
  99             /// Returns the least bits of pointer according to \p Bitmask template argument of the class
 100             uintptr_t bits() const CDS_NOEXCEPT
 101             {
 102                 return to_int() & bitmask;
 103             }
 104
 105             /// Analogue for \ref ptr
 106             value_type * operator ->() const CDS_NOEXCEPT
 107             {
 108                 return ptr();
 109             }
 110
 111             /// Assignment operator sets markup bits to zero
 112             marked_ptr operator =( T * p ) CDS_NOEXCEPT
 113             {
 114                 m_ptr = p;
 115                 return *this;
 116             }
 117
 118             /// Set LSB bits as <tt>bits() | nBits</tt>
 119             marked_ptr& operator |=( int nBits ) CDS_NOEXCEPT
 120             {
 121                 assert( (nBits & pointer_bitmask) == 0 );
 122                 m_ptr = to_ptr( to_int() | nBits );
 123                 return *this;
 124             }
 125
 126             /// Set LSB bits as <tt>bits() & nBits</tt>
 127             marked_ptr& operator &=( int nBits ) CDS_NOEXCEPT
 128             {
 129                 assert( (nBits & pointer_bitmask) == 0 );
 130                 m_ptr = to_ptr( to_int() & (pointer_bitmask | nBits) );
 131                 return *this;
 132             }
 133
 134             /// Set LSB bits as <tt>bits() ^ nBits</tt>
 135             marked_ptr& operator ^=( int nBits ) CDS_NOEXCEPT
 136             {
 137                 assert( (nBits & pointer_bitmask) == 0 );
 138                 m_ptr = to_ptr( to_int() ^ nBits );
 139                 return *this;
 140             }
 141
 142             /// Returns <tt>p |= nBits</tt>
 143             friend marked_ptr operator |( marked_ptr p, int nBits) CDS_NOEXCEPT
 144             {
 145                 p |= nBits;
 146                 return p;
 147             }
 148
 149             /// Returns <tt>p |= nBits</tt>
 150             friend marked_ptr operator |( int nBits, marked_ptr p ) CDS_NOEXCEPT
 151             {
 152                 p |= nBits;
 153                 return p;
 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             /// Returns <tt>p ^= nBits</tt>
 177             friend marked_ptr operator ^( int nBits, marked_ptr p ) CDS_NOEXCEPT
 178             {
 179                 p ^= nBits;
 180                 return p;
 181             }
 182
 183             /// Inverts LSBs of pointer \p p
 184             friend marked_ptr operator ~( marked_ptr p ) CDS_NOEXCEPT
 185             {
 186                 return p ^ marked_ptr::bitmask;
 187             }
 188
 189
 190             /// Comparing two marked pointer including its mark bits
 191             friend bool operator ==( marked_ptr p1, marked_ptr p2 ) CDS_NOEXCEPT
 192             {
 193                 return p1.all() == p2.all();
 194             }
 195
 196             /// Comparing marked pointer and raw pointer, mark bits of \p p1 is ignored
 197             friend bool operator ==( marked_ptr p1, value_type const * p2 ) CDS_NOEXCEPT
 198             {
 199                 return p1.ptr() == p2;
 200             }
 201
 202             /// Comparing marked pointer and raw pointer, mark bits of \p p2 is ignored
 203             friend bool operator ==( value_type const * p1, marked_ptr p2 ) CDS_NOEXCEPT
 204             {
 205                 return p1 == p2.ptr();
 206             }
 207
 208             /// Comparing two marked pointer including its mark bits
 209             friend bool operator !=( marked_ptr p1, marked_ptr p2 ) CDS_NOEXCEPT
 210             {
 211                 return p1.all() != p2.all();
 212             }
 213
 214             /// Comparing marked pointer and raw pointer, mark bits of \p p1 is ignored
 215             friend bool operator !=( marked_ptr p1, value_type const * p2 ) CDS_NOEXCEPT
 216             {
 217                 return p1.ptr() != p2;
 218             }
 219
 220             /// Comparing marked pointer and raw pointer, mark bits of \p p2 is ignored
 221             friend bool operator !=( value_type const * p1, marked_ptr p2 ) CDS_NOEXCEPT
 222             {
 223                 return p1 != p2.ptr();
 224             }
 225
 226             //@cond
 227             /// atomic< marked_ptr< T, Bitmask > > support
 228             T *& impl_ref() CDS_NOEXCEPT
 229             {
 230                 return m_ptr;
 231             }
 232             //@endcond
 233         };
 234     }   // namespace details
 235
 236 }   // namespace cds
 237
 238 //@cond
 239 CDS_CXX11_ATOMIC_BEGIN_NAMESPACE
 240
 241     template <typename T, int Bitmask >
 242     class atomic< cds::details::marked_ptr<T, Bitmask> >
 243     {
 244     private:
 245         typedef cds::details::marked_ptr<T, Bitmask> marked_ptr;
 246         typedef atomics::atomic<T *>  atomic_impl;
 247
 248         atomic_impl m_atomic;
 249     public:
 250         bool is_lock_free() const volatile CDS_NOEXCEPT
 251         {
 252             return m_atomic.is_lock_free();
 253         }
 254         bool is_lock_free() const CDS_NOEXCEPT
 255         {
 256             return m_atomic.is_lock_free();
 257         }
 258
 259         void store(marked_ptr val, memory_order order = memory_order_seq_cst) volatile CDS_NOEXCEPT
 260         {
 261             m_atomic.store( val.all(), order );
 262         }
 263         void store(marked_ptr val, memory_order order = memory_order_seq_cst) CDS_NOEXCEPT
 264         {
 265             m_atomic.store( val.all(), order );
 266         }
 267
 268         marked_ptr load(memory_order order = memory_order_seq_cst) const volatile CDS_NOEXCEPT
 269         {
 270             return marked_ptr( m_atomic.load( order ));
 271         }
 272         marked_ptr load(memory_order order = memory_order_seq_cst) const CDS_NOEXCEPT
 273         {
 274             return marked_ptr( m_atomic.load( order ));
 275         }
 276
 277         operator marked_ptr() const volatile CDS_NOEXCEPT
 278         {
 279             return load();
 280         }
 281         operator marked_ptr() const CDS_NOEXCEPT
 282         {
 283             return load();
 284         }
 285
 286         marked_ptr exchange(marked_ptr val, memory_order order = memory_order_seq_cst) volatile CDS_NOEXCEPT
 287         {
 288             return marked_ptr( m_atomic.exchange( val.all(), order ));
 289         }
 290         marked_ptr exchange(marked_ptr val, memory_order order = memory_order_seq_cst) CDS_NOEXCEPT
 291         {
 292             return marked_ptr( m_atomic.exchange( val.all(), order ));
 293         }
 294
 295         bool compare_exchange_weak(marked_ptr& expected, marked_ptr desired, memory_order success_order, memory_order failure_order) volatile CDS_NOEXCEPT
 296         {
 297             return m_atomic.compare_exchange_weak( expected.impl_ref(), desired.all(), success_order, failure_order );
 298         }
 299         bool compare_exchange_weak(marked_ptr& expected, marked_ptr desired, memory_order success_order, memory_order failure_order) CDS_NOEXCEPT
 300         {
 301             return m_atomic.compare_exchange_weak( expected.impl_ref(), desired.all(), success_order, failure_order );
 302         }
 303         bool compare_exchange_strong(marked_ptr& expected, marked_ptr desired, memory_order success_order, memory_order failure_order) volatile CDS_NOEXCEPT
 304         {
 305             return m_atomic.compare_exchange_strong( expected.impl_ref(), desired.all(), success_order, failure_order );
 306         }
 307         bool compare_exchange_strong(marked_ptr& expected, marked_ptr desired, memory_order success_order, memory_order failure_order) CDS_NOEXCEPT
 308         {
 309             return m_atomic.compare_exchange_strong( expected.impl_ref(), desired.all(), success_order, failure_order );
 310         }
 311         bool compare_exchange_weak(marked_ptr& expected, marked_ptr desired, memory_order success_order = memory_order_seq_cst) volatile CDS_NOEXCEPT
 312         {
 313             return m_atomic.compare_exchange_weak( expected.impl_ref(), desired.all(), success_order );
 314         }
 315         bool compare_exchange_weak(marked_ptr& expected, marked_ptr desired, memory_order success_order = memory_order_seq_cst) CDS_NOEXCEPT
 316         {
 317             return m_atomic.compare_exchange_weak( expected.impl_ref(), desired.all(), success_order );
 318         }
 319         bool compare_exchange_strong(marked_ptr& expected, marked_ptr desired, memory_order success_order = memory_order_seq_cst) volatile CDS_NOEXCEPT
 320         {
 321             return m_atomic.compare_exchange_strong( expected.impl_ref(), desired.all(), success_order );
 322         }
 323         bool compare_exchange_strong(marked_ptr& expected, marked_ptr desired, memory_order success_order = memory_order_seq_cst) CDS_NOEXCEPT
 324         {
 325             return m_atomic.compare_exchange_strong( expected.impl_ref(), desired.all(), success_order );
 326         }
 327
 328         CDS_CONSTEXPR atomic() CDS_NOEXCEPT
 329             : m_atomic( nullptr )
 330         {}
 331
 332         CDS_CONSTEXPR explicit atomic(marked_ptr val) CDS_NOEXCEPT
 333             : m_atomic( val.all() )
 334         {}
 335         CDS_CONSTEXPR explicit atomic(T * p) CDS_NOEXCEPT
 336             : m_atomic( p )
 337         {}
 338
 339 #   ifdef CDS_CXX11_DELETE_DEFINITION_SUPPORT
 340         atomic(const atomic&) = delete;
 341         atomic& operator=(const atomic&) = delete;
 342         atomic& operator=(const atomic&) volatile = delete;
 343 #   endif
 344
 345         marked_ptr operator=(marked_ptr val) volatile CDS_NOEXCEPT
 346         {
 347             store( val );
 348             return val;
 349         }
 350         marked_ptr operator=(marked_ptr val) CDS_NOEXCEPT
 351         {
 352             store( val );
 353             return val;
 354         }
 355     };
 356
 357 CDS_CXX11_ATOMIC_END_NAMESPACE
 358 //@endcond
 359
 360 #endif  // #ifndef __CDS_DETAILS_MARKED_PTR_H