cds/details/marked_ptr.h

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