3 #ifndef CDSLIB_DETAILS_MARKED_PTR_H
4 #define CDSLIB_DETAILS_MARKED_PTR_H
6 #include <cds/algo/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 );
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)
61 marked_ptr( marked_ptr&& src ) CDS_NOEXCEPT = default;
62 marked_ptr& operator =( marked_ptr&& p ) CDS_NOEXCEPT = default;
66 //TODO: make move ctor
74 pointer_cast(T * p) : ptr(p) {}
75 pointer_cast(uintptr_t i) : n(i) {}
77 static uintptr_t to_int( value_type * p ) CDS_NOEXCEPT
79 return pointer_cast(p).n;
82 static value_type * to_ptr( uintptr_t n ) CDS_NOEXCEPT
84 return pointer_cast(n).ptr;
87 uintptr_t to_int() const CDS_NOEXCEPT
89 return to_int( m_ptr );
94 /// Returns the pointer without mark bits (real pointer) const version
95 value_type * ptr() const CDS_NOEXCEPT
97 return to_ptr( to_int() & ~bitmask );
100 /// Returns the pointer and bits together
101 value_type * all() const CDS_NOEXCEPT
106 /// Returns the least bits of pointer according to \p Bitmask template argument of the class
107 uintptr_t bits() const CDS_NOEXCEPT
109 return to_int() & bitmask;
112 /// Analogue for \ref ptr
113 value_type * operator ->() const CDS_NOEXCEPT
118 /// Assignment operator sets markup bits to zero
119 marked_ptr operator =( T * p ) CDS_NOEXCEPT
125 /// Set LSB bits as <tt>bits() | nBits</tt>
126 marked_ptr& operator |=( int nBits ) CDS_NOEXCEPT
128 assert( (nBits & pointer_bitmask) == 0 );
129 m_ptr = to_ptr( to_int() | nBits );
133 /// Set LSB bits as <tt>bits() & nBits</tt>
134 marked_ptr& operator &=( int nBits ) CDS_NOEXCEPT
136 assert( (nBits & pointer_bitmask) == 0 );
137 m_ptr = to_ptr( to_int() & (pointer_bitmask | nBits) );
141 /// Set LSB bits as <tt>bits() ^ nBits</tt>
142 marked_ptr& operator ^=( int nBits ) CDS_NOEXCEPT
144 assert( (nBits & pointer_bitmask) == 0 );
145 m_ptr = to_ptr( to_int() ^ nBits );
149 /// Returns <tt>p |= nBits</tt>
150 friend marked_ptr operator |( marked_ptr p, int nBits) CDS_NOEXCEPT
156 /// Returns <tt>p |= nBits</tt>
157 friend marked_ptr operator |( int nBits, marked_ptr p ) CDS_NOEXCEPT
163 /// Returns <tt>p &= nBits</tt>
164 friend marked_ptr operator &( marked_ptr p, int nBits) CDS_NOEXCEPT
170 /// Returns <tt>p &= nBits</tt>
171 friend marked_ptr operator &( int nBits, marked_ptr p ) CDS_NOEXCEPT
177 /// Returns <tt>p ^= nBits</tt>
178 friend marked_ptr operator ^( marked_ptr p, int nBits) CDS_NOEXCEPT
183 /// Returns <tt>p ^= nBits</tt>
184 friend marked_ptr operator ^( int nBits, marked_ptr p ) CDS_NOEXCEPT
190 /// Inverts LSBs of pointer \p p
191 friend marked_ptr operator ~( marked_ptr p ) CDS_NOEXCEPT
193 return p ^ marked_ptr::bitmask;
197 /// Comparing two marked pointer including its mark bits
198 friend bool operator ==( marked_ptr p1, marked_ptr p2 ) CDS_NOEXCEPT
200 return p1.all() == p2.all();
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
206 return p1.ptr() == p2;
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
212 return p1 == p2.ptr();
215 /// Comparing two marked pointer including its mark bits
216 friend bool operator !=( marked_ptr p1, marked_ptr p2 ) CDS_NOEXCEPT
218 return p1.all() != p2.all();
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
224 return p1.ptr() != p2;
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
230 return p1 != p2.ptr();
234 /// atomic< marked_ptr< T, Bitmask > > support
235 T *& impl_ref() CDS_NOEXCEPT
241 } // namespace details
246 CDS_CXX11_ATOMIC_BEGIN_NAMESPACE
248 template <typename T, int Bitmask >
249 class atomic< cds::details::marked_ptr<T, Bitmask> >
252 typedef cds::details::marked_ptr<T, Bitmask> marked_ptr;
253 typedef atomics::atomic<T *> atomic_impl;
255 atomic_impl m_atomic;
257 bool is_lock_free() const volatile CDS_NOEXCEPT
259 return m_atomic.is_lock_free();
261 bool is_lock_free() const CDS_NOEXCEPT
263 return m_atomic.is_lock_free();
266 void store(marked_ptr val, memory_order order = memory_order_seq_cst) volatile CDS_NOEXCEPT
268 m_atomic.store( val.all(), order );
270 void store(marked_ptr val, memory_order order = memory_order_seq_cst) CDS_NOEXCEPT
272 m_atomic.store( val.all(), order );
275 marked_ptr load(memory_order order = memory_order_seq_cst) const volatile CDS_NOEXCEPT
277 return marked_ptr( m_atomic.load( order ));
279 marked_ptr load(memory_order order = memory_order_seq_cst) const CDS_NOEXCEPT
281 return marked_ptr( m_atomic.load( order ));
284 operator marked_ptr() const volatile CDS_NOEXCEPT
288 operator marked_ptr() const CDS_NOEXCEPT
293 marked_ptr exchange(marked_ptr val, memory_order order = memory_order_seq_cst) volatile CDS_NOEXCEPT
295 return marked_ptr( m_atomic.exchange( val.all(), order ));
297 marked_ptr exchange(marked_ptr val, memory_order order = memory_order_seq_cst) CDS_NOEXCEPT
299 return marked_ptr( m_atomic.exchange( val.all(), order ));
302 bool compare_exchange_weak(marked_ptr& expected, marked_ptr desired, memory_order success_order, memory_order failure_order) volatile CDS_NOEXCEPT
304 return m_atomic.compare_exchange_weak( expected.impl_ref(), desired.all(), success_order, failure_order );
306 bool compare_exchange_weak(marked_ptr& expected, marked_ptr desired, memory_order success_order, memory_order failure_order) CDS_NOEXCEPT
308 return m_atomic.compare_exchange_weak( expected.impl_ref(), desired.all(), success_order, failure_order );
310 bool compare_exchange_strong(marked_ptr& expected, marked_ptr desired, memory_order success_order, memory_order failure_order) volatile CDS_NOEXCEPT
312 return m_atomic.compare_exchange_strong( expected.impl_ref(), desired.all(), success_order, failure_order );
314 bool compare_exchange_strong(marked_ptr& expected, marked_ptr desired, memory_order success_order, memory_order failure_order) CDS_NOEXCEPT
316 return m_atomic.compare_exchange_strong( expected.impl_ref(), desired.all(), success_order, failure_order );
318 bool compare_exchange_weak(marked_ptr& expected, marked_ptr desired, memory_order success_order = memory_order_seq_cst) volatile CDS_NOEXCEPT
320 return m_atomic.compare_exchange_weak( expected.impl_ref(), desired.all(), success_order );
322 bool compare_exchange_weak(marked_ptr& expected, marked_ptr desired, memory_order success_order = memory_order_seq_cst) CDS_NOEXCEPT
324 return m_atomic.compare_exchange_weak( expected.impl_ref(), desired.all(), success_order );
326 bool compare_exchange_strong(marked_ptr& expected, marked_ptr desired, memory_order success_order = memory_order_seq_cst) volatile CDS_NOEXCEPT
328 return m_atomic.compare_exchange_strong( expected.impl_ref(), desired.all(), success_order );
330 bool compare_exchange_strong(marked_ptr& expected, marked_ptr desired, memory_order success_order = memory_order_seq_cst) CDS_NOEXCEPT
332 return m_atomic.compare_exchange_strong( expected.impl_ref(), desired.all(), success_order );
335 CDS_CONSTEXPR atomic() CDS_NOEXCEPT
336 : m_atomic( nullptr )
339 CDS_CONSTEXPR explicit atomic(marked_ptr val) CDS_NOEXCEPT
340 : m_atomic( val.all() )
342 CDS_CONSTEXPR explicit atomic(T * p) CDS_NOEXCEPT
346 atomic(const atomic&) = delete;
347 atomic& operator=(const atomic&) = delete;
349 #if !(CDS_COMPILER == CDS_COMPILER_MSVC && CDS_COMPILER_VERSION <= CDS_COMPILER_MSVC14)
350 // MSVC12, MSVC14: warning C4522: multiple assignment operators specified
351 atomic& operator=(const atomic&) volatile = delete;
352 marked_ptr operator=(marked_ptr val) volatile CDS_NOEXCEPT
358 marked_ptr operator=(marked_ptr val) CDS_NOEXCEPT
365 CDS_CXX11_ATOMIC_END_NAMESPACE
368 #endif // #ifndef CDSLIB_DETAILS_MARKED_PTR_H