3 #ifndef __CDS_DETAILS_MARKED_PTR_H
4 #define __CDS_DETAILS_MARKED_PTR_H
6 #include <cds/cxx11_atomic.h>
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.
20 - Bitmask - bitmask of least unused bits
22 template <typename T, int Bitmask>
25 T * m_ptr ; ///< pointer and its mark bits
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
34 /// Constructs null marked pointer. The flag is cleared.
35 CDS_CONSTEXPR marked_ptr() CDS_NOEXCEPT
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
44 /// Constructs marked pointer with \p ptr value and \p nMask flag.
46 The \p nMask argument defines the OR-bits
48 marked_ptr( value_type * ptr, int nMask ) CDS_NOEXCEPT
51 assert( bits() == 0 );
55 # ifdef CDS_CXX11_EXPLICITLY_DEFAULTED_FUNCTION_SUPPORT
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)
62 marked_ptr( marked_ptr&& src ) CDS_NOEXCEPT_DEFAULTED = default;
63 marked_ptr& operator =( marked_ptr&& p ) CDS_NOEXCEPT_DEFAULTED = default;
68 marked_ptr( marked_ptr const& src ) CDS_NOEXCEPT
72 /// Copy-assignment operator
73 marked_ptr& operator =( marked_ptr const& p ) CDS_NOEXCEPT
80 //TODO: make move ctor
84 static uintptr_t to_int( value_type * p ) CDS_NOEXCEPT
86 return reinterpret_cast<uintptr_t>( p );
89 static value_type * to_ptr( uintptr_t n ) CDS_NOEXCEPT
91 return reinterpret_cast< value_type *>( n );
94 uintptr_t to_int() const CDS_NOEXCEPT
96 return to_int( m_ptr );
101 /// Returns the pointer without mark bits (real pointer) const version
102 value_type * ptr() const CDS_NOEXCEPT
104 return to_ptr( to_int() & ~bitmask );
107 /// Returns the pointer and bits together
108 value_type * all() const CDS_NOEXCEPT
113 /// Returns the least bits of pointer according to \p Bitmask template argument of the class
114 uintptr_t bits() const CDS_NOEXCEPT
116 return to_int() & bitmask;
119 /// Analogue for \ref ptr
120 value_type * operator ->() const CDS_NOEXCEPT
125 /// Assignment operator sets markup bits to zero
126 marked_ptr operator =( T * p ) CDS_NOEXCEPT
132 /// Set LSB bits as <tt>bits() | nBits</tt>
133 marked_ptr& operator |=( int nBits ) CDS_NOEXCEPT
135 assert( (nBits & pointer_bitmask) == 0 );
136 m_ptr = to_ptr( to_int() | nBits );
140 /// Set LSB bits as <tt>bits() & nBits</tt>
141 marked_ptr& operator &=( int nBits ) CDS_NOEXCEPT
143 assert( (nBits & pointer_bitmask) == 0 );
144 m_ptr = to_ptr( to_int() & (pointer_bitmask | nBits) );
148 /// Set LSB bits as <tt>bits() ^ nBits</tt>
149 marked_ptr& operator ^=( int nBits ) CDS_NOEXCEPT
151 assert( (nBits & pointer_bitmask) == 0 );
152 m_ptr = to_ptr( to_int() ^ nBits );
156 /// Returns <tt>p |= nBits</tt>
157 friend marked_ptr operator |( marked_ptr p, int nBits) CDS_NOEXCEPT
163 /// Returns <tt>p |= nBits</tt>
164 friend marked_ptr operator |( int nBits, marked_ptr p ) CDS_NOEXCEPT
170 /// Returns <tt>p &= nBits</tt>
171 friend marked_ptr operator &( marked_ptr p, int nBits) CDS_NOEXCEPT
177 /// Returns <tt>p &= nBits</tt>
178 friend marked_ptr operator &( int nBits, marked_ptr p ) CDS_NOEXCEPT
184 /// Returns <tt>p ^= nBits</tt>
185 friend marked_ptr operator ^( marked_ptr p, int nBits) CDS_NOEXCEPT
190 /// Returns <tt>p ^= nBits</tt>
191 friend marked_ptr operator ^( int nBits, marked_ptr p ) CDS_NOEXCEPT
197 /// Inverts LSBs of pointer \p p
198 friend marked_ptr operator ~( marked_ptr p ) CDS_NOEXCEPT
200 return p ^ marked_ptr::bitmask;
204 /// Comparing two marked pointer including its mark bits
205 friend bool operator ==( marked_ptr p1, marked_ptr p2 ) CDS_NOEXCEPT
207 return p1.all() == p2.all();
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
213 return p1.ptr() == p2;
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
219 return p1 == p2.ptr();
222 /// Comparing two marked pointer including its mark bits
223 friend bool operator !=( marked_ptr p1, marked_ptr p2 ) CDS_NOEXCEPT
225 return p1.all() != p2.all();
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
231 return p1.ptr() != p2;
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
237 return p1 != p2.ptr();
241 /// atomic< marked_ptr< T, Bitmask > > support
242 T *& impl_ref() CDS_NOEXCEPT
248 } // namespace details
253 CDS_CXX11_ATOMIC_BEGIN_NAMESPACE
255 template <typename T, int Bitmask >
256 class atomic< cds::details::marked_ptr<T, Bitmask> >
259 typedef cds::details::marked_ptr<T, Bitmask> marked_ptr;
260 typedef CDS_ATOMIC::atomic<T *> atomic_impl;
262 atomic_impl m_atomic;
264 bool is_lock_free() const volatile CDS_NOEXCEPT
266 return m_atomic.is_lock_free();
268 bool is_lock_free() const CDS_NOEXCEPT
270 return m_atomic.is_lock_free();
273 void store(marked_ptr val, memory_order order = memory_order_seq_cst) volatile CDS_NOEXCEPT
275 m_atomic.store( val.all(), order );
277 void store(marked_ptr val, memory_order order = memory_order_seq_cst) CDS_NOEXCEPT
279 m_atomic.store( val.all(), order );
282 marked_ptr load(memory_order order = memory_order_seq_cst) const volatile CDS_NOEXCEPT
284 return marked_ptr( m_atomic.load( order ));
286 marked_ptr load(memory_order order = memory_order_seq_cst) const CDS_NOEXCEPT
288 return marked_ptr( m_atomic.load( order ));
291 operator marked_ptr() const volatile CDS_NOEXCEPT
295 operator marked_ptr() const CDS_NOEXCEPT
300 marked_ptr exchange(marked_ptr val, memory_order order = memory_order_seq_cst) volatile CDS_NOEXCEPT
302 return marked_ptr( m_atomic.exchange( val.all(), order ));
304 marked_ptr exchange(marked_ptr val, memory_order order = memory_order_seq_cst) CDS_NOEXCEPT
306 return marked_ptr( m_atomic.exchange( val.all(), order ));
309 bool compare_exchange_weak(marked_ptr& expected, marked_ptr desired, memory_order success_order, memory_order failure_order) volatile CDS_NOEXCEPT
311 return m_atomic.compare_exchange_weak( expected.impl_ref(), desired.all(), success_order, failure_order );
313 bool compare_exchange_weak(marked_ptr& expected, marked_ptr desired, memory_order success_order, memory_order failure_order) CDS_NOEXCEPT
315 return m_atomic.compare_exchange_weak( expected.impl_ref(), desired.all(), success_order, failure_order );
317 bool compare_exchange_strong(marked_ptr& expected, marked_ptr desired, memory_order success_order, memory_order failure_order) volatile CDS_NOEXCEPT
319 return m_atomic.compare_exchange_strong( expected.impl_ref(), desired.all(), success_order, failure_order );
321 bool compare_exchange_strong(marked_ptr& expected, marked_ptr desired, memory_order success_order, memory_order failure_order) CDS_NOEXCEPT
323 return m_atomic.compare_exchange_strong( expected.impl_ref(), desired.all(), success_order, failure_order );
325 bool compare_exchange_weak(marked_ptr& expected, marked_ptr desired, memory_order success_order = memory_order_seq_cst) volatile CDS_NOEXCEPT
327 return m_atomic.compare_exchange_weak( expected.impl_ref(), desired.all(), success_order );
329 bool compare_exchange_weak(marked_ptr& expected, marked_ptr desired, memory_order success_order = memory_order_seq_cst) CDS_NOEXCEPT
331 return m_atomic.compare_exchange_weak( expected.impl_ref(), desired.all(), success_order );
333 bool compare_exchange_strong(marked_ptr& expected, marked_ptr desired, memory_order success_order = memory_order_seq_cst) volatile CDS_NOEXCEPT
335 return m_atomic.compare_exchange_strong( expected.impl_ref(), desired.all(), success_order );
337 bool compare_exchange_strong(marked_ptr& expected, marked_ptr desired, memory_order success_order = memory_order_seq_cst) CDS_NOEXCEPT
339 return m_atomic.compare_exchange_strong( expected.impl_ref(), desired.all(), success_order );
342 CDS_CONSTEXPR atomic() CDS_NOEXCEPT
343 : m_atomic( nullptr )
346 CDS_CONSTEXPR explicit atomic(marked_ptr val) CDS_NOEXCEPT
347 : m_atomic( val.all() )
349 CDS_CONSTEXPR explicit atomic(T * p) CDS_NOEXCEPT
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;
359 marked_ptr operator=(marked_ptr val) volatile CDS_NOEXCEPT
364 marked_ptr operator=(marked_ptr val) CDS_NOEXCEPT
371 CDS_CXX11_ATOMIC_END_NAMESPACE
374 #endif // #ifndef __CDS_DETAILS_MARKED_PTR_H