X-Git-Url: http://plrg.eecs.uci.edu/git/?p=libcds.git;a=blobdiff_plain;f=cds%2Fintrusive%2Fvyukov_mpmc_cycle_queue.h;h=709d69b27e90f7ecae3e2ad1e0dd1448d88282f3;hp=1b049bf511162f0d4e1d72a6d5b83ea792bbfba5;hb=91dbaa8005237a46dc5993083833df1e7f4fc047;hpb=98aa954aa9d1b640f6f6d81018542eec1c2046bb diff --git a/cds/intrusive/vyukov_mpmc_cycle_queue.h b/cds/intrusive/vyukov_mpmc_cycle_queue.h index 1b049bf5..709d69b2 100644 --- a/cds/intrusive/vyukov_mpmc_cycle_queue.h +++ b/cds/intrusive/vyukov_mpmc_cycle_queue.h @@ -1,32 +1,115 @@ -//$$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 + 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 #include 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 + 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. @@ -39,49 +122,48 @@ namespace cds { namespace intrusive { }; // 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 + template 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 + template 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 ) @@ -89,7 +171,7 @@ namespace cds { namespace intrusive { /// 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 ) { @@ -98,7 +180,9 @@ namespace cds { namespace intrusive { /// 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() { @@ -106,13 +190,13 @@ namespace cds { namespace intrusive { 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(); @@ -121,13 +205,12 @@ namespace cds { namespace intrusive { /// 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 @@ -135,13 +218,13 @@ namespace cds { namespace intrusive { { value_type * pv; while ( (pv = pop()) != nullptr ) { - unref(f)( pv ); + 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() { @@ -154,18 +237,17 @@ namespace cds { namespace intrusive { 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(); @@ -173,4 +255,4 @@ namespace cds { namespace intrusive { }; }} // namespace cds::intrusive -#endif // #ifndef __CDS_INTRUSIVE_VYUKOV_MPMC_CYCLE_QUEUE_H +#endif // #ifndef CDSLIB_INTRUSIVE_VYUKOV_MPMC_CYCLE_QUEUE_H