-//$$CDS-header$$
+/*
+ This file is a part of libcds - Concurrent Data Structures library
+
+ (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:
+
+ * Redistributions of source code must retain the above copyright notice, this
+ list of conditions and the following disclaimer.
+
+ * Redistributions in binary form must reproduce the above copyright notice,
+ this list of conditions and the following disclaimer in the documentation
+ and/or other materials provided with the distribution.
+
+ THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+ FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ 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.
+*/
#ifndef CDSLIB_CONTAINER_BASKET_QUEUE_H
#define CDSLIB_CONTAINER_BASKET_QUEUE_H
<b>Key idea</b>
- In the \93basket\94 approach, instead of
+ In the 'basket' approach, instead of
the traditional ordered list of nodes, the queue consists of an ordered list of groups
of nodes (logical baskets). The order of nodes in each basket need not be specified, and in
fact, it is easiest to maintain them in LIFO order. The baskets fulfill the following basic
rules:
- - Each basket has a time interval in which all its nodes\92 enqueue operations overlap.
+ - Each basket has a time interval in which all its nodes' enqueue operations overlap.
- The baskets are ordered by the order of their respective time intervals.
- - For each basket, its nodes\92 dequeue operations occur after its time interval.
+ - For each basket, its nodes' dequeue operations occur after its time interval.
- The dequeue operations are performed according to the order of baskets.
Two properties define the FIFO order of nodes:
In algorithms such as the MS-queue or optimistic
queue, threads enqueue items by applying a Compare-and-swap (CAS) operation to the
- queue\92s tail pointer, and all the threads that fail on a particular CAS operation (and also
+ queue's tail pointer, and all the threads that fail on a particular CAS operation (and also
the winner of that CAS) overlap in time. In particular, they share the time interval of
the CAS operation itself. Hence, all the threads that fail to CAS on the tail-node of
the queue may be inserted into the same basket. By integrating the basket-mechanism
onto the new tail, can now be utilized to insert the failed operations into the basket,
allowing enqueues to complete sooner. In the meantime, the next successful CAS operations
by enqueues allow new baskets to be formed down the list, and these can be
- filled concurrently. Moreover, the failed operations don\92t retry their link attempt on the
+ filled concurrently. Moreover, the failed operations don't retry their link attempt on the
new tail, lowering the overall contention on it. This leads to a queue
algorithm that unlike all former concurrent queue algorithms requires virtually no tuning
of the backoff mechanisms to reduce contention, making the algorithm an attractive
typedef typename base_class::stat stat; ///< Internal statistics policy used
typedef typename base_class::memory_model memory_model; ///< Memory ordering. See cds::opt::memory_model option
+ static CDS_CONSTEXPR const size_t c_nHazardPtrCount = base_class::c_nHazardPtrCount; ///< Count of hazard pointer required for the algorithm
+
protected:
typedef typename maker::node_type node_type; ///< queue node type (derived from intrusive::basket_queue::node)
return false;
}
+ /// Enqueues \p val value into the queue, move semantics
+ bool enqueue( value_type&& val )
+ {
+ scoped_node_ptr p( alloc_node_move( std::move( val )));
+ if ( base_class::enqueue( *p )) {
+ p.release();
+ return true;
+ }
+ return false;
+ }
+
/// Enqueues \p data to queue using a functor
/**
\p Func is a functor called to create node.
template <typename Func>
bool enqueue_with( Func f )
{
- scoped_node_ptr p( alloc_node() );
+ scoped_node_ptr p( alloc_node());
f( p->m_value );
if ( base_class::enqueue( *p )) {
p.release();
}
/// Synonym for \p enqueue() function
- bool push( const value_type& val )
+ bool push( value_type const& val )
{
return enqueue( val );
}
+ /// Synonym for \p enqueue() function, move semantics
+ bool push( value_type&& val )
+ {
+ return enqueue( std::move( val ));
+ }
+
/// Synonym for \p enqueue_with() function
template <typename Func>
bool push_with( Func f )
/// Dequeues a value from the queue
/**
If queue is not empty, the function returns \p true, \p dest contains copy of
- dequeued value. The assignment operator for type \ref value_type is invoked.
+ dequeued value. The assignment operator for \p value_type is invoked.
If queue is empty, the function returns \p false, \p dest is unchanged.
*/
bool dequeue( value_type& dest )
{
- return dequeue_with( [&dest]( value_type& src ) { dest = src; } );
+ return dequeue_with( [&dest]( value_type& src ) {
+ // TSan finds a race between this read of \p src and node_type constructor
+ // I think, it is wrong
+ CDS_TSAN_ANNOTATE_IGNORE_READS_BEGIN;
+ dest = std::move( src );
+ CDS_TSAN_ANNOTATE_IGNORE_READS_END;
+ });
}
/// Dequeues a value using a functor