Source code repo: http://github.com/khizmax/libcds/
Download: http://sourceforge.net/projects/libcds/files/
-
+
Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions are met:
SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
- OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
#ifndef CDSLIB_INTRUSIVE_FREE_LIST_TAGGED_H
namespace cds { namespace intrusive {
/// Lock-free free list based on tagged pointers (required double-width CAS)
- /** @ingroup cds_intrusive_helper
+ /** @ingroup cds_intrusive_freelist
+
This variant of \p FreeList is intended for processor architectures that support double-width CAS.
It uses <a href="https://en.wikipedia.org/wiki/Tagged_pointer">tagged pointer</a> technique to solve ABA problem.
//@endcond
};
+ private:
+ //@cond
+ struct tagged_ptr
+ {
+ node * ptr;
+ uintptr_t tag;
+
+ tagged_ptr()
+ : ptr( nullptr )
+ , tag( 0 )
+ {}
+
+ tagged_ptr( node* p )
+ : ptr( p )
+ , tag( 0 )
+ {}
+ };
+
+ static_assert(sizeof( tagged_ptr ) == sizeof( void * ) * 2, "sizeof( tagged_ptr ) violation");
+ //@endcond
+
public:
/// Creates empty free-list
TaggedFreeList()
+ : m_Head( tagged_ptr())
{
// Your platform must support double-width CAS
assert( m_Head.is_lock_free());
assert( empty() );
}
-
/// Puts \p pNode to the free list
void put( node * pNode )
{
+ assert( m_Head.is_lock_free());
+
tagged_ptr currentHead = m_Head.load( atomics::memory_order_relaxed );
tagged_ptr newHead = { pNode };
do {
newHead.tag = currentHead.tag + 1;
pNode->m_freeListNext.store( currentHead.ptr, atomics::memory_order_relaxed );
- } while ( !m_Head.compare_exchange_weak( currentHead, newHead, atomics::memory_order_release, atomics::memory_order_relaxed ));
+ } while ( cds_unlikely( !m_Head.compare_exchange_weak( currentHead, newHead, atomics::memory_order_release, atomics::memory_order_relaxed )));
}
/// Gets a node from the free list. If the list is empty, returns \p nullptr
while ( currentHead.ptr != nullptr ) {
newHead.ptr = currentHead.ptr->m_freeListNext.load( atomics::memory_order_relaxed );
newHead.tag = currentHead.tag + 1;
- if ( m_Head.compare_exchange_weak( currentHead, newHead, atomics::memory_order_release, atomics::memory_order_acquire ) )
+ if ( cds_likely( m_Head.compare_exchange_weak( currentHead, newHead, atomics::memory_order_release, atomics::memory_order_acquire )))
break;
}
return currentHead.ptr;
private:
//@cond
- struct tagged_ptr
- {
- node * ptr;
- uintptr_t tag;
-
- tagged_ptr()
- : ptr( nullptr )
- , tag( 0 )
- {}
- };
-
- static_assert(sizeof( tagged_ptr ) == sizeof(void *) * 2, "sizeof( tagged_ptr ) violation" );
-
atomics::atomic<tagged_ptr> m_Head;
//@endcond
};
}} // namespace cds::intrusive
-#endif // CDSLIB_INTRUSIVE_FREE_LIST_TAGGED_H
\ No newline at end of file
+#endif // CDSLIB_INTRUSIVE_FREE_LIST_TAGGED_H