2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
6 Source code repo: http://github.com/khizmax/libcds/
7 Download: http://sourceforge.net/projects/libcds/files/
9 Redistribution and use in source and binary forms, with or without
10 modification, are permitted provided that the following conditions are met:
12 * Redistributions of source code must retain the above copyright notice, this
13 list of conditions and the following disclaimer.
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.
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.
31 #ifndef CDSLIB_DETAILS_MARKED_PTR_H
32 #define CDSLIB_DETAILS_MARKED_PTR_H
34 #include <cds/algo/atomic.h>
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.
48 - Bitmask - bitmask of least unused bits
50 template <typename T, int Bitmask>
53 T * m_ptr ; ///< pointer and its mark bits
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
62 /// Constructs null marked pointer. The flag is cleared.
63 CDS_CONSTEXPR marked_ptr() CDS_NOEXCEPT
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
72 /// Constructs marked pointer with \p ptr value and \p nMask flag.
74 The \p nMask argument defines the OR-bits
76 marked_ptr( value_type * ptr, int nMask ) CDS_NOEXCEPT
79 assert( bits() == 0 );
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)
89 marked_ptr( marked_ptr&& src ) CDS_NOEXCEPT = default;
90 marked_ptr& operator =( marked_ptr&& p ) CDS_NOEXCEPT = default;
94 //TODO: make move ctor
102 pointer_cast(T * p) : ptr(p) {}
103 pointer_cast(uintptr_t i) : n(i) {}
105 static uintptr_t to_int( value_type * p ) CDS_NOEXCEPT
107 return pointer_cast(p).n;
110 static value_type * to_ptr( uintptr_t n ) CDS_NOEXCEPT
112 return pointer_cast(n).ptr;
115 uintptr_t to_int() const CDS_NOEXCEPT
117 return to_int( m_ptr );
122 /// Returns the pointer without mark bits (real pointer) const version
123 value_type * ptr() const CDS_NOEXCEPT
125 return to_ptr( to_int() & ~bitmask );
128 /// Returns the pointer and bits together
129 value_type * all() const CDS_NOEXCEPT
134 /// Returns the least bits of pointer according to \p Bitmask template argument of the class
135 uintptr_t bits() const CDS_NOEXCEPT
137 return to_int() & bitmask;
140 /// Analogue for \ref ptr
141 value_type * operator ->() const CDS_NOEXCEPT
146 /// Assignment operator sets markup bits to zero
147 marked_ptr operator =( T * p ) CDS_NOEXCEPT
153 /// Set LSB bits as <tt>bits() | nBits</tt>
154 marked_ptr& operator |=( int nBits ) CDS_NOEXCEPT
156 assert( (nBits & pointer_bitmask) == 0 );
157 m_ptr = to_ptr( to_int() | nBits );
161 /// Set LSB bits as <tt>bits() & nBits</tt>
162 marked_ptr& operator &=( int nBits ) CDS_NOEXCEPT
164 assert( (nBits & pointer_bitmask) == 0 );
165 m_ptr = to_ptr( to_int() & (pointer_bitmask | nBits));
169 /// Set LSB bits as <tt>bits() ^ nBits</tt>
170 marked_ptr& operator ^=( int nBits ) CDS_NOEXCEPT
172 assert( (nBits & pointer_bitmask) == 0 );
173 m_ptr = to_ptr( to_int() ^ nBits );
177 /// Returns <tt>p |= nBits</tt>
178 friend marked_ptr operator |( marked_ptr p, int nBits) CDS_NOEXCEPT
184 /// Returns <tt>p |= nBits</tt>
185 friend marked_ptr operator |( int nBits, marked_ptr p ) CDS_NOEXCEPT
191 /// Returns <tt>p &= nBits</tt>
192 friend marked_ptr operator &( marked_ptr p, int nBits) CDS_NOEXCEPT
198 /// Returns <tt>p &= nBits</tt>
199 friend marked_ptr operator &( int nBits, marked_ptr p ) CDS_NOEXCEPT
205 /// Returns <tt>p ^= nBits</tt>
206 friend marked_ptr operator ^( marked_ptr p, int nBits) CDS_NOEXCEPT
211 /// Returns <tt>p ^= nBits</tt>
212 friend marked_ptr operator ^( int nBits, marked_ptr p ) CDS_NOEXCEPT
218 /// Inverts LSBs of pointer \p p
219 friend marked_ptr operator ~( marked_ptr p ) CDS_NOEXCEPT
221 return p ^ marked_ptr::bitmask;
225 /// Comparing two marked pointer including its mark bits
226 friend bool operator ==( marked_ptr p1, marked_ptr p2 ) CDS_NOEXCEPT
228 return p1.all() == p2.all();
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
234 return p1.ptr() == p2;
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
240 return p1 == p2.ptr();
243 /// Comparing two marked pointer including its mark bits
244 friend bool operator !=( marked_ptr p1, marked_ptr p2 ) CDS_NOEXCEPT
246 return p1.all() != p2.all();
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
252 return p1.ptr() != p2;
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
258 return p1 != p2.ptr();
262 /// atomic< marked_ptr< T, Bitmask > > support
263 T *& impl_ref() CDS_NOEXCEPT
269 } // namespace details
274 CDS_CXX11_ATOMIC_BEGIN_NAMESPACE
276 template <typename T, int Bitmask >
277 class atomic< cds::details::marked_ptr<T, Bitmask> >
280 typedef cds::details::marked_ptr<T, Bitmask> marked_ptr;
281 typedef atomics::atomic<T *> atomic_impl;
283 atomic_impl m_atomic;
285 bool is_lock_free() const volatile CDS_NOEXCEPT
287 return m_atomic.is_lock_free();
289 bool is_lock_free() const CDS_NOEXCEPT
291 return m_atomic.is_lock_free();
294 void store(marked_ptr val, memory_order order = memory_order_seq_cst) volatile CDS_NOEXCEPT
296 m_atomic.store( val.all(), order );
298 void store(marked_ptr val, memory_order order = memory_order_seq_cst) CDS_NOEXCEPT
300 m_atomic.store( val.all(), order );
303 marked_ptr load(memory_order order = memory_order_seq_cst) const volatile CDS_NOEXCEPT
305 return marked_ptr( m_atomic.load( order ));
307 marked_ptr load(memory_order order = memory_order_seq_cst) const CDS_NOEXCEPT
309 return marked_ptr( m_atomic.load( order ));
312 operator marked_ptr() const volatile CDS_NOEXCEPT
316 operator marked_ptr() const CDS_NOEXCEPT
321 marked_ptr exchange(marked_ptr val, memory_order order = memory_order_seq_cst) volatile CDS_NOEXCEPT
323 return marked_ptr( m_atomic.exchange( val.all(), order ));
325 marked_ptr exchange(marked_ptr val, memory_order order = memory_order_seq_cst) CDS_NOEXCEPT
327 return marked_ptr( m_atomic.exchange( val.all(), order ));
330 bool compare_exchange_weak(marked_ptr& expected, marked_ptr desired, memory_order success_order, memory_order failure_order) volatile CDS_NOEXCEPT
332 return m_atomic.compare_exchange_weak( expected.impl_ref(), desired.all(), success_order, failure_order );
334 bool compare_exchange_weak(marked_ptr& expected, marked_ptr desired, memory_order success_order, memory_order failure_order) CDS_NOEXCEPT
336 return m_atomic.compare_exchange_weak( expected.impl_ref(), desired.all(), success_order, failure_order );
338 bool compare_exchange_strong(marked_ptr& expected, marked_ptr desired, memory_order success_order, memory_order failure_order) volatile CDS_NOEXCEPT
340 return m_atomic.compare_exchange_strong( expected.impl_ref(), desired.all(), success_order, failure_order );
342 bool compare_exchange_strong(marked_ptr& expected, marked_ptr desired, memory_order success_order, memory_order failure_order) CDS_NOEXCEPT
344 return m_atomic.compare_exchange_strong( expected.impl_ref(), desired.all(), success_order, failure_order );
346 bool compare_exchange_weak(marked_ptr& expected, marked_ptr desired, memory_order success_order = memory_order_seq_cst) volatile CDS_NOEXCEPT
348 return m_atomic.compare_exchange_weak( expected.impl_ref(), desired.all(), success_order );
350 bool compare_exchange_weak(marked_ptr& expected, marked_ptr desired, memory_order success_order = memory_order_seq_cst) CDS_NOEXCEPT
352 return m_atomic.compare_exchange_weak( expected.impl_ref(), desired.all(), success_order );
354 bool compare_exchange_strong(marked_ptr& expected, marked_ptr desired, memory_order success_order = memory_order_seq_cst) volatile CDS_NOEXCEPT
356 return m_atomic.compare_exchange_strong( expected.impl_ref(), desired.all(), success_order );
358 bool compare_exchange_strong(marked_ptr& expected, marked_ptr desired, memory_order success_order = memory_order_seq_cst) CDS_NOEXCEPT
360 return m_atomic.compare_exchange_strong( expected.impl_ref(), desired.all(), success_order );
363 CDS_CONSTEXPR atomic() CDS_NOEXCEPT
364 : m_atomic( nullptr )
367 CDS_CONSTEXPR explicit atomic(marked_ptr val) CDS_NOEXCEPT
368 : m_atomic( val.all())
370 CDS_CONSTEXPR explicit atomic(T * p) CDS_NOEXCEPT
374 atomic(const atomic&) = delete;
375 atomic& operator=(const atomic&) = delete;
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
386 marked_ptr operator=(marked_ptr val) CDS_NOEXCEPT
393 CDS_CXX11_ATOMIC_END_NAMESPACE
396 #endif // #ifndef CDSLIB_DETAILS_MARKED_PTR_H