cds/details/marked_ptr.h

   1 /*
   2     This file is a part of libcds - Concurrent Data Structures library
   3
   4     (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017
   5
   6     Source code repo: http://github.com/khizmax/libcds/
   7     Download: http://sourceforge.net/projects/libcds/files/
   8
   9     Redistribution and use in source and binary forms, with or without
  10     modification, are permitted provided that the following conditions are met:
  11
  12     * Redistributions of source code must retain the above copyright notice, this
  13       list of conditions and the following disclaimer.
  14
  15     * Redistributions in binary form must reproduce the above copyright notice,
  16       this list of conditions and the following disclaimer in the documentation
  17       and/or other materials provided with the distribution.
  18
  19     THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  20     AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  21     IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  22     DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
  23     FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  24     DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
  25     SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  26     CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  27     OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  28     OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  29 */
  30
  31 #ifndef CDSLIB_DETAILS_MARKED_PTR_H
  32 #define CDSLIB_DETAILS_MARKED_PTR_H
  33
  34 #include <cds/algo/atomic.h>
  35
  36 namespace cds {
  37     namespace details {
  38
  39         /// Marked pointer
  40         /**
  41             On the modern architectures, the default data alignment is 4 (for 32bit) or 8 byte for 64bit.
  42             Therefore, the least 2 or 3 bits of the pointer is always zero and can
  43             be used as a bitfield to store logical flags. This trick is widely used in
  44             lock-free programming to operate with the pointer and its flags atomically.
  45
  46             Template parameters:
  47             - T - type of pointer
  48             - Bitmask - bitmask of least unused bits
  49         */
  50         template <typename T, int Bitmask>
  51         class marked_ptr
  52         {
  53             T *         m_ptr   ;   ///< pointer and its mark bits
  54
  55         public:
  56             typedef T       value_type      ;       ///< type of value the class points to
  57             typedef T *     pointer_type    ;       ///< type of pointer
  58             static CDS_CONSTEXPR const uintptr_t bitmask = Bitmask;   ///< bitfield bitmask
  59             static CDS_CONSTEXPR const uintptr_t pointer_bitmask = ~bitmask; ///< pointer bitmask
  60
  61         public:
  62             /// Constructs null marked pointer. The flag is cleared.
  63             CDS_CONSTEXPR marked_ptr() CDS_NOEXCEPT
  64                 : m_ptr( nullptr )
  65             {}
  66
  67             /// Constructs marked pointer with \p ptr value. The least bit(s) of \p ptr is the flag.
  68             CDS_CONSTEXPR explicit marked_ptr( value_type * ptr ) CDS_NOEXCEPT
  69                 : m_ptr( ptr )
  70             {}
  71
  72             /// Constructs marked pointer with \p ptr value and \p nMask flag.
  73             /**
  74                 The \p nMask argument defines the OR-bits
  75             */
  76             marked_ptr( value_type * ptr, int nMask ) CDS_NOEXCEPT
  77                 : m_ptr( ptr )
  78             {
  79                 assert( bits() == 0 );
  80                 *this |= nMask;
  81             }
  82
  83             /// Copy constructor
  84             marked_ptr( marked_ptr const& src ) CDS_NOEXCEPT = default;
  85             /// Copy-assignment operator
  86             marked_ptr& operator =( marked_ptr const& p ) CDS_NOEXCEPT = default;
  87 #       if !defined(CDS_DISABLE_DEFAULT_MOVE_CTOR)
  88             //@cond
  89             marked_ptr( marked_ptr&& src ) CDS_NOEXCEPT = default;
  90             marked_ptr& operator =( marked_ptr&& p ) CDS_NOEXCEPT = default;
  91             //@endcond
  92 #       endif
  93
  94             //TODO: make move ctor
  95
  96         private:
  97             //@cond
  98             union pointer_cast {
  99                 T *       ptr;
 100                 uintptr_t n;
 101
 102                 pointer_cast(T * p) : ptr(p) {}
 103                 pointer_cast(uintptr_t i) : n(i) {}
 104             };
 105             static uintptr_t   to_int( value_type * p ) CDS_NOEXCEPT
 106             {
 107                 return pointer_cast(p).n;
 108             }
 109
 110             static value_type * to_ptr( uintptr_t n ) CDS_NOEXCEPT
 111             {
 112                 return pointer_cast(n).ptr;
 113             }
 114
 115             uintptr_t   to_int() const CDS_NOEXCEPT
 116             {
 117                 return to_int( m_ptr );
 118             }
 119             //@endcond
 120
 121         public:
 122             /// Returns the pointer without mark bits (real pointer) const version
 123             value_type *        ptr() const CDS_NOEXCEPT
 124             {
 125                 return to_ptr( to_int() & ~bitmask );
 126             }
 127
 128             /// Returns the pointer and bits together
 129             value_type *        all() const CDS_NOEXCEPT
 130             {
 131                 return m_ptr;
 132             }
 133
 134             /// Returns the least bits of pointer according to \p Bitmask template argument of the class
 135             uintptr_t bits() const CDS_NOEXCEPT
 136             {
 137                 return to_int() & bitmask;
 138             }
 139
 140             /// Analogue for \ref ptr
 141             value_type * operator ->() const CDS_NOEXCEPT
 142             {
 143                 return ptr();
 144             }
 145
 146             /// Assignment operator sets markup bits to zero
 147             marked_ptr operator =( T * p ) CDS_NOEXCEPT
 148             {
 149                 m_ptr = p;
 150                 return *this;
 151             }
 152
 153             /// Set LSB bits as <tt>bits() | nBits</tt>
 154             marked_ptr& operator |=( int nBits ) CDS_NOEXCEPT
 155             {
 156                 assert( (nBits & pointer_bitmask) == 0 );
 157                 m_ptr = to_ptr( to_int() | nBits );
 158                 return *this;
 159             }
 160
 161             /// Set LSB bits as <tt>bits() & nBits</tt>
 162             marked_ptr& operator &=( int nBits ) CDS_NOEXCEPT
 163             {
 164                 assert( (nBits & pointer_bitmask) == 0 );
 165                 m_ptr = to_ptr( to_int() & (pointer_bitmask | nBits));
 166                 return *this;
 167             }
 168
 169             /// Set LSB bits as <tt>bits() ^ nBits</tt>
 170             marked_ptr& operator ^=( int nBits ) CDS_NOEXCEPT
 171             {
 172                 assert( (nBits & pointer_bitmask) == 0 );
 173                 m_ptr = to_ptr( to_int() ^ nBits );
 174                 return *this;
 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
 184             /// Returns <tt>p |= nBits</tt>
 185             friend marked_ptr operator |( int nBits, marked_ptr p ) CDS_NOEXCEPT
 186             {
 187                 p |= nBits;
 188                 return p;
 189             }
 190
 191             /// Returns <tt>p &= nBits</tt>
 192             friend marked_ptr operator &( marked_ptr p, int nBits) CDS_NOEXCEPT
 193             {
 194                 p &= nBits;
 195                 return p;
 196             }
 197
 198             /// Returns <tt>p &= nBits</tt>
 199             friend marked_ptr operator &( int nBits, marked_ptr p ) CDS_NOEXCEPT
 200             {
 201                 p &= nBits;
 202                 return p;
 203             }
 204
 205             /// Returns <tt>p ^= nBits</tt>
 206             friend marked_ptr operator ^( marked_ptr p, int nBits) CDS_NOEXCEPT
 207             {
 208                 p ^= nBits;
 209                 return p;
 210             }
 211             /// Returns <tt>p ^= nBits</tt>
 212             friend marked_ptr operator ^( int nBits, marked_ptr p ) CDS_NOEXCEPT
 213             {
 214                 p ^= nBits;
 215                 return p;
 216             }
 217
 218             /// Inverts LSBs of pointer \p p
 219             friend marked_ptr operator ~( marked_ptr p ) CDS_NOEXCEPT
 220             {
 221                 return p ^ marked_ptr::bitmask;
 222             }
 223
 224
 225             /// Comparing two marked pointer including its mark bits
 226             friend bool operator ==( marked_ptr p1, marked_ptr p2 ) CDS_NOEXCEPT
 227             {
 228                 return p1.all() == p2.all();
 229             }
 230
 231             /// Comparing marked pointer and raw pointer, mark bits of \p p1 is ignored
 232             friend bool operator ==( marked_ptr p1, value_type const * p2 ) CDS_NOEXCEPT
 233             {
 234                 return p1.ptr() == p2;
 235             }
 236
 237             /// Comparing marked pointer and raw pointer, mark bits of \p p2 is ignored
 238             friend bool operator ==( value_type const * p1, marked_ptr p2 ) CDS_NOEXCEPT
 239             {
 240                 return p1 == p2.ptr();
 241             }
 242
 243             /// Comparing two marked pointer including its mark bits
 244             friend bool operator !=( marked_ptr p1, marked_ptr p2 ) CDS_NOEXCEPT
 245             {
 246                 return p1.all() != p2.all();
 247             }
 248
 249             /// Comparing marked pointer and raw pointer, mark bits of \p p1 is ignored
 250             friend bool operator !=( marked_ptr p1, value_type const * p2 ) CDS_NOEXCEPT
 251             {
 252                 return p1.ptr() != p2;
 253             }
 254
 255             /// Comparing marked pointer and raw pointer, mark bits of \p p2 is ignored
 256             friend bool operator !=( value_type const * p1, marked_ptr p2 ) CDS_NOEXCEPT
 257             {
 258                 return p1 != p2.ptr();
 259             }
 260
 261             //@cond
 262             /// atomic< marked_ptr< T, Bitmask > > support
 263             T *& impl_ref() CDS_NOEXCEPT
 264             {
 265                 return m_ptr;
 266             }
 267             //@endcond
 268         };
 269     }   // namespace details
 270
 271 }   // namespace cds
 272
 273 //@cond
 274 CDS_CXX11_ATOMIC_BEGIN_NAMESPACE
 275
 276     template <typename T, int Bitmask >
 277     class atomic< cds::details::marked_ptr<T, Bitmask> >
 278     {
 279     private:
 280         typedef cds::details::marked_ptr<T, Bitmask> marked_ptr;
 281         typedef atomics::atomic<T *>  atomic_impl;
 282
 283         atomic_impl m_atomic;
 284     public:
 285         bool is_lock_free() const volatile CDS_NOEXCEPT
 286         {
 287             return m_atomic.is_lock_free();
 288         }
 289         bool is_lock_free() const CDS_NOEXCEPT
 290         {
 291             return m_atomic.is_lock_free();
 292         }
 293
 294         void store(marked_ptr val, memory_order order = memory_order_seq_cst) volatile CDS_NOEXCEPT
 295         {
 296             m_atomic.store( val.all(), order );
 297         }
 298         void store(marked_ptr val, memory_order order = memory_order_seq_cst) CDS_NOEXCEPT
 299         {
 300             m_atomic.store( val.all(), order );
 301         }
 302
 303         marked_ptr load(memory_order order = memory_order_seq_cst) const volatile CDS_NOEXCEPT
 304         {
 305             return marked_ptr( m_atomic.load( order ));
 306         }
 307         marked_ptr load(memory_order order = memory_order_seq_cst) const CDS_NOEXCEPT
 308         {
 309             return marked_ptr( m_atomic.load( order ));
 310         }
 311
 312         operator marked_ptr() const volatile CDS_NOEXCEPT
 313         {
 314             return load();
 315         }
 316         operator marked_ptr() const CDS_NOEXCEPT
 317         {
 318             return load();
 319         }
 320
 321         marked_ptr exchange(marked_ptr val, memory_order order = memory_order_seq_cst) volatile CDS_NOEXCEPT
 322         {
 323             return marked_ptr( m_atomic.exchange( val.all(), order ));
 324         }
 325         marked_ptr exchange(marked_ptr val, memory_order order = memory_order_seq_cst) CDS_NOEXCEPT
 326         {
 327             return marked_ptr( m_atomic.exchange( val.all(), order ));
 328         }
 329
 330         bool compare_exchange_weak(marked_ptr& expected, marked_ptr desired, memory_order success_order, memory_order failure_order) volatile CDS_NOEXCEPT
 331         {
 332             return m_atomic.compare_exchange_weak( expected.impl_ref(), desired.all(), success_order, failure_order );
 333         }
 334         bool compare_exchange_weak(marked_ptr& expected, marked_ptr desired, memory_order success_order, memory_order failure_order) CDS_NOEXCEPT
 335         {
 336             return m_atomic.compare_exchange_weak( expected.impl_ref(), desired.all(), success_order, failure_order );
 337         }
 338         bool compare_exchange_strong(marked_ptr& expected, marked_ptr desired, memory_order success_order, memory_order failure_order) volatile CDS_NOEXCEPT
 339         {
 340             return m_atomic.compare_exchange_strong( expected.impl_ref(), desired.all(), success_order, failure_order );
 341         }
 342         bool compare_exchange_strong(marked_ptr& expected, marked_ptr desired, memory_order success_order, memory_order failure_order) CDS_NOEXCEPT
 343         {
 344             return m_atomic.compare_exchange_strong( expected.impl_ref(), desired.all(), success_order, failure_order );
 345         }
 346         bool compare_exchange_weak(marked_ptr& expected, marked_ptr desired, memory_order success_order = memory_order_seq_cst) volatile CDS_NOEXCEPT
 347         {
 348             return m_atomic.compare_exchange_weak( expected.impl_ref(), desired.all(), success_order );
 349         }
 350         bool compare_exchange_weak(marked_ptr& expected, marked_ptr desired, memory_order success_order = memory_order_seq_cst) CDS_NOEXCEPT
 351         {
 352             return m_atomic.compare_exchange_weak( expected.impl_ref(), desired.all(), success_order );
 353         }
 354         bool compare_exchange_strong(marked_ptr& expected, marked_ptr desired, memory_order success_order = memory_order_seq_cst) volatile CDS_NOEXCEPT
 355         {
 356             return m_atomic.compare_exchange_strong( expected.impl_ref(), desired.all(), success_order );
 357         }
 358         bool compare_exchange_strong(marked_ptr& expected, marked_ptr desired, memory_order success_order = memory_order_seq_cst) CDS_NOEXCEPT
 359         {
 360             return m_atomic.compare_exchange_strong( expected.impl_ref(), desired.all(), success_order );
 361         }
 362
 363         CDS_CONSTEXPR atomic() CDS_NOEXCEPT
 364             : m_atomic( nullptr )
 365         {}
 366
 367         CDS_CONSTEXPR explicit atomic(marked_ptr val) CDS_NOEXCEPT
 368             : m_atomic( val.all())
 369         {}
 370         CDS_CONSTEXPR explicit atomic(T * p) CDS_NOEXCEPT
 371             : m_atomic( p )
 372         {}
 373
 374         atomic(const atomic&) = delete;
 375         atomic& operator=(const atomic&) = delete;
 376
 377 #if !(CDS_COMPILER == CDS_COMPILER_MSVC && CDS_COMPILER_VERSION <= CDS_COMPILER_MSVC14)
 378         // MSVC12, MSVC14: warning C4522: multiple assignment operators specified
 379         atomic& operator=(const atomic&) volatile = delete;
 380         marked_ptr operator=(marked_ptr val) volatile CDS_NOEXCEPT
 381         {
 382             store( val );
 383             return val;
 384         }
 385 #endif
 386         marked_ptr operator=(marked_ptr val) CDS_NOEXCEPT
 387         {
 388             store( val );
 389             return val;
 390         }
 391     };
 392
 393 CDS_CXX11_ATOMIC_END_NAMESPACE
 394 //@endcond
 395
 396 #endif  // #ifndef CDSLIB_DETAILS_MARKED_PTR_H