/*
This file is a part of libcds - Concurrent Data Structures library
- (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
+ (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017
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_H
namespace cds { namespace intrusive {
/// Lock-free free list
- /** @ingroup cds_intrusive_helper
+ /** @ingroup cds_intrusive_freelist
- Free list is a helper class intended for reusing objects instead of freeing them completely;
- this avoids the overhead of \p malloc(), and also avoids its worst-case behaviour of taking an operating system lock.
+ Free list is a helper class intended for reusing objects instead of freeing them completely;
+ this avoids the overhead of \p malloc(), and also avoids its worst-case behavior of taking an operating system lock.
So, the free list can be considered as a specialized allocator for objects of some type.
The algorithm is taken from <a href="http://moodycamel.com/blog/2014/solving-the-aba-problem-for-lock-free-free-lists">this article</a>.
The algo does not require any SMR like Hazard Pointer to prevent ABA problem.
- There is \ref TaggedFreeList "tagged pointers" variant of free list for processors which support double-width CAS.
+ There is \ref TaggedFreeList "tagged pointers" variant of free list for processors with double-width CAS support.
\b How to use
\code
node()
: m_freeListRefs( 0 )
- , m_freeListNext( nullptr )
- {}
+ {
+ m_freeListNext.store( nullptr, atomics::memory_order_release );
+ }
//@endcond
};
*/
~FreeList()
{
- assert( empty() );
+ assert( empty());
}
/// Puts \p pNode to the free list
while ( head != nullptr ) {
auto prevHead = head;
auto refs = head->m_freeListRefs.load( atomics::memory_order_relaxed );
- if ( (refs & c_RefsMask) == 0 || !head->m_freeListRefs.compare_exchange_strong( refs, refs + 1,
- atomics::memory_order_acquire, atomics::memory_order_relaxed ))
+
+ if ( cds_unlikely( (refs & c_RefsMask) == 0 || !head->m_freeListRefs.compare_exchange_strong( refs, refs + 1,
+ atomics::memory_order_acquire, atomics::memory_order_relaxed )))
{
head = m_Head.load( atomics::memory_order_acquire );
continue;
// we can read the next and not worry about it changing between now and the time
// we do the CAS
node * next = head->m_freeListNext.load( atomics::memory_order_relaxed );
- if ( m_Head.compare_exchange_strong( head, next, atomics::memory_order_acquire, atomics::memory_order_relaxed )) {
+ if ( cds_likely( m_Head.compare_exchange_strong( head, next, atomics::memory_order_acquire, atomics::memory_order_relaxed ))) {
// Yay, got the node. This means it was on the list, which means
// shouldBeOnFreeList must be false no matter the refcount (because
// nobody else knows it's been taken off yet, it can't have been put back on).
while ( true ) {
pNode->m_freeListNext.store( head, atomics::memory_order_relaxed );
pNode->m_freeListRefs.store( 1, atomics::memory_order_release );
- if ( !m_Head.compare_exchange_strong( head, pNode, atomics::memory_order_release, atomics::memory_order_relaxed )) {
+ if ( cds_unlikely( !m_Head.compare_exchange_strong( head, pNode, atomics::memory_order_release, atomics::memory_order_relaxed ))) {
// Hmm, the add failed, but we can only try again when the refcount goes back to zero
if ( pNode->m_freeListRefs.fetch_add( c_ShouldBeOnFreeList - 1, atomics::memory_order_release ) == 1 )
continue;