-//$$CDS-header$$
+/*
+ This file is a part of libcds - Concurrent Data Structures library
-#ifndef __CDS_INTRUSIVE_VYUKOV_MPMC_CYCLE_QUEUE_H
-#define __CDS_INTRUSIVE_VYUKOV_MPMC_CYCLE_QUEUE_H
+ (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
-#include <cds/intrusive/base.h>
+ 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_INTRUSIVE_VYUKOV_MPMC_CYCLE_QUEUE_H
+#define CDSLIB_INTRUSIVE_VYUKOV_MPMC_CYCLE_QUEUE_H
+
+#include <cds/intrusive/details/base.h>
#include <cds/container/vyukov_mpmc_cycle_queue.h>
namespace cds { namespace intrusive {
+ /// VyukovMPMCCycleQueue related definitions
+ /** @ingroup cds_intrusive_helper
+ */
+ namespace vyukov_queue {
+
+ /// VyukovMPMCCycleQueue traits
+ struct traits : public cds::container::vyukov_queue::traits
+ {
+ /// The functor used for dispose removed items. Default is \p opt::v::empty_disposer. This option is used only in \p clear()
+ typedef opt::v::empty_disposer disposer;
+ };
+
+ /// Metafunction converting option list to \p vyukov_queue::traits
+ /**
+ Supported \p Options are:
+ - \p opt::buffer - an uninitialized buffer type for internal cyclic array. Possible types are:
+ \p opt::v::uninitialized_dynamic_buffer (the default), \p opt::v::uninitialized_static_buffer. The type of
+ element in the buffer is not important: it will be changed via \p rebind metafunction.
+ - \p opt::disposer - the functor used for dispose removed items. Default is \p opt::v::empty_disposer.
+ This option is used only in \p clear() member function.
+ - \p opt::item_counter - the type of item counting feature. Default is \p cds::atomicity::empty_item_counter (item counting disabled)
+ To enable item counting use \p cds::atomicity::item_counter
+ - \p opt::back_off - back-off strategy used. If the option is not specified, the \p cds::backoff::Default is used.
+ - \p opt::padding - padding for internal critical atomic data. Default is \p opt::cache_line_padding
+ - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
+ or \p opt::v::sequential_consistent (sequentially consistent memory model).
+
+ Example: declare \p %VyukovMPMCCycleQueue with item counting and static internal buffer of size 1024:
+ \code
+ typedef cds::intrusive::VyukovMPMCCycleQueue< Foo,
+ typename cds::intrusive::vyukov_queue::make_traits<
+ cds::opt::buffer< cds::opt::v::uninitialized_static_buffer< void *, 1024 >,
+ cds::opt::item_counter< cds::atomicity::item_counter >
+ >::type
+ > myQueue;
+ \endcode
+ */
+ template <typename... Options>
+ struct make_traits {
+# ifdef CDS_DOXYGEN_INVOKED
+ typedef implementation_defined type; ///< Metafunction result
+# else
+ typedef typename cds::opt::make_options<
+ typename cds::opt::find_type_traits< traits, Options... >::type
+ , Options...
+ >::type type;
+# endif
+ };
+
+ } // namespace vyukov_queue
+
/// Vyukov's MPMC bounded queue
/** @ingroup cds_intrusive_queue
This algorithm is developed by Dmitry Vyukov (see http://www.1024cores.net)
- Implementation of intrusive version is based on non-intrusive class container::VyukovMPMCCycleQueue.
+ Implementation of intrusive version is based on container::VyukovMPMCCycleQueue.
Template parameters:
- \p T - type stored in queue.
- - \p Options - queue's options
-
- Options \p Options are:
- - opt::buffer - buffer to store items. Mandatory option, see option description for full list of possible types.
- - opt::item_counter - the type of item counting feature. Default is \ref atomicity::empty_item_counter
- - opt::disposer - the functor used for dispose removed items. Default is opt::v::empty_disposer. This option is used
- only in \ref clear function.
- - opt::alignment - the alignment for internal queue data. Default is opt::cache_line_alignment
- - opt::memory_model - C++ memory ordering model. Can be opt::v::relaxed_ordering (relaxed memory model, the default)
- or opt::v::sequential_consistent (sequentially consisnent memory model).
+ - \p Traits - queue traits, default is \p vyukov_queue::traits. You can use \p vyukov_queue::make_traits
+ metafunction to make your traits or just derive your traits from \p %vyukov_queue::traits:
+ \code
+ struct myTraits: public cds::intrusive::vyukov_queue::traits {
+ typedef cds::atomicity::item_counter item_counter;
+ };
+ typedef cds::intrusive::VyukovMPMCCycleQueue< Foo, myTraits > myQueue;
+ // Equivalent make_traits example:
+ typedef cds::intrusive::VyukovMPMCCycleQueue< cds::gc::HP, Foo,
+ typename cds::intrusive::vyukov_queue::make_traits<
+ cds::opt::item_counter< cds::atomicity::item_counter >
+ >::type
+ > myQueue;
+ \endcode
Instead of saving copy of enqueued data, the intrusive implementation stores pointer to passed data.
};
// Queue of Foo pointers, capacity is 1024, statically allocated buffer:
- typedef cds::intrusive::VyukovMPMCCycleQueue<
- Foo
- ,cds::opt::buffer< cds::opt::v::static_buffer< Foo, 1024 > >
+ typedef cds::intrusive::VyukovMPMCCycleQueue< Foo,
+ typename cds::intrusive::vyukov_queue::make_traits<
+ cds::opt::buffer< cds::opt::v::uninitialized_static_buffer< Foo, 1024 > >
+ >::type
> static_queue;
static_queue stQueue;
// Queue of Foo pointers, capacity is 1024, dynamically allocated buffer:
- typedef cds::intrusive::VyukovMPMCCycleQueue<
- Foo
- ,cds::opt::buffer< cds::opt::v::dynamic_buffer< Foo > >
- > dynamic_queue;
+ struct queue_traits: public cds::intrusive::vyukov_queue::traits
+ {
+ typedef cds::opt::v::uninitialized_dynamic_buffer< Foo > buffer;
+ };
+ typedef cds::intrusive::VyukovMPMCCycleQueue< Foo, queue_traits > dynamic_queue;
dynamic_queue dynQueue( 1024 );
-
\endcode
*/
- template <typename T, CDS_DECL_OPTIONS6>
+ template <typename T, typename Traits = vyukov_queue::traits >
class VyukovMPMCCycleQueue
- : private container::VyukovMPMCCycleQueue< T *, CDS_OPTIONS6 >
+ : private container::VyukovMPMCCycleQueue< T*, Traits >
{
//@cond
- typedef container::VyukovMPMCCycleQueue< T *, CDS_OPTIONS6 > base_class;
+ typedef container::VyukovMPMCCycleQueue< T*, Traits > base_class;
//@endcond
public:
- typedef T value_type ; ///< type of data stored in the queue
- typedef typename base_class::item_counter item_counter ; ///< Item counter type
- typedef typename base_class::memory_model memory_model ; ///< Memory ordering. See cds::opt::memory_model option
- typedef typename base_class::options::disposer disposer ; ///< Item disposer
-
- //@cond
- typedef typename base_class::options options;
- //@endcond
+ typedef T value_type; ///< type of data to be stored in the queue
+ typedef Traits traits; ///< Queue traits
+ typedef typename traits::item_counter item_counter; ///< Item counter type
+ typedef typename traits::memory_model memory_model; ///< Memory ordering. See cds::opt::memory_model option
+ typedef typename traits::disposer disposer; ///< Item disposer
+ typedef typename traits::back_off back_off; ///< back-off strategy
public:
/// Rebind template arguments
- template <typename T2, CDS_DECL_OTHER_OPTIONS6>
+ template <typename T2, typename Traits2>
struct rebind {
- typedef VyukovMPMCCycleQueue< T2, CDS_OTHER_OPTIONS6> other ; ///< Rebinding result
+ typedef VyukovMPMCCycleQueue< T2, Traits2> other ; ///< Rebinding result
};
public:
/// Constructs the queue of capacity \p nCapacity
/**
- For cds::opt::v::static_buffer the \p nCapacity parameter is ignored.
+ For \p cds::opt::v::uninitialized_static_buffer the \p nCapacity parameter is ignored.
*/
VyukovMPMCCycleQueue( size_t nCapacity = 0 )
: base_class( nCapacity )
/// Enqueues \p data to queue
/**
- Note that the intrusive queue stores pointer to \p data passed, not the copy of data.
+ @note The intrusive queue stores pointer to \p data passed, not the copy of \p data.
*/
bool enqueue( value_type& data )
{
/// Dequeues an item from queue
/**
- If queue is empty, returns \p NULL.
+ \p Traits::disposer is not called. You may manually delete the returned pointer.
+
+ If queue is empty, returns \p nullptr.
*/
value_type * dequeue()
{
- value_type * p = null_ptr<value_type *>();
- return base_class::dequeue( p ) ? p : null_ptr<value_type *>();
+ value_type * p = nullptr;
+ return base_class::dequeue( p ) ? p : nullptr;
}
- /// Synonym of \ref enqueue
+ /// Synonym for \p enqueue()
bool push( value_type& data )
{
return enqueue( data );
}
- /// Synonym of \ref dequeue
+ /// Synonym for \p dequeue()
value_type * pop()
{
return dequeue();
/// Clears queue in lock-free manner.
/**
\p f parameter is a functor to dispose removed items.
- The interface of \p DISPOSER is:
+ The interface of \p Disposer is:
\code
struct myDisposer {
void operator ()( T * val );
};
\endcode
- You can pass \p disposer by reference using \p boost::ref.
The disposer will be called immediately for each item.
*/
template <typename Disposer>
void clear( Disposer f )
{
value_type * pv;
- while ( (pv = pop()) != null_ptr<value_type *>() ) {
- unref(f)( pv );
+ while ( (pv = pop()) != nullptr ) {
+ f( pv );
}
}
/// Clears the queue
/**
- This function uses the disposer that is specified in \p Options.
+ This function uses the disposer that is specified in \p Traits.
*/
void clear()
{
return base_class::empty();
}
-
/// Returns queue's item count
/**
- The value returned depends on opt::item_counter option. For atomicity::empty_item_counter,
- this function always returns 0.
+ The value returned depends on \p vyukov_queue::traits::item_counter option.
+ For \p atomicity::empty_item_counter, this function always returns 0.
*/
size_t size() const
{
return base_class::size();
}
- /// Returns capacity of cyclic buffer
+ /// Returns capacity of the queue
size_t capacity() const
{
return base_class::capacity();
};
}} // namespace cds::intrusive
-#endif // #ifndef __CDS_INTRUSIVE_VYUKOV_MPMC_CYCLE_QUEUE_H
+#endif // #ifndef CDSLIB_INTRUSIVE_VYUKOV_MPMC_CYCLE_QUEUE_H