X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=cds%2Fintrusive%2Fvyukov_mpmc_cycle_queue.h;h=ea97029f8c15aa516633bae9983720c23ed912e9;hb=9e2654f9e05fa1ed4cbb78387363d735d385b74c;hp=6dcd502911ff12a15ab5ae2b585ed65a849197ae;hpb=2e8a58841ca3d7cc736cc9483b691cf70c3ecdb3;p=libcds.git diff --git a/cds/intrusive/vyukov_mpmc_cycle_queue.h b/cds/intrusive/vyukov_mpmc_cycle_queue.h index 6dcd5029..ea97029f 100644 --- a/cds/intrusive/vyukov_mpmc_cycle_queue.h +++ b/cds/intrusive/vyukov_mpmc_cycle_queue.h @@ -1,32 +1,86 @@ //$$CDS-header$$ -#ifndef __CDS_INTRUSIVE_VYUKOV_MPMC_CYCLE_QUEUE_H -#define __CDS_INTRUSIVE_VYUKOV_MPMC_CYCLE_QUEUE_H +#ifndef CDSLIB_INTRUSIVE_VYUKOV_MPMC_CYCLE_QUEUE_H +#define CDSLIB_INTRUSIVE_VYUKOV_MPMC_CYCLE_QUEUE_H -#include +#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 - the buffer type for internal cyclic array. Possible types are: + \p opt::v::dynamic_buffer (the default), \p opt::v::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::alignment - the alignment for internal queue data. Default is \p opt::cache_line_alignment + - \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 consisnent memory model). + + Example: declare \p %VyukovMPMCCycleQueue with item counting and static iternal buffer of size 1024: + \code + typedef cds::intrusive::VyukovMPMCCycleQueue< Foo, + typename cds::intrusive::vyukov_queue::make_traits< + cds::opt::buffer< cds::opt::v::static_buffer< void *, 1024 >, + cds::opt::item_counte< 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 vykov_queue::traits. You can use \p vykov_queue::make_traits + metafunction to make your traits or just derive your traits from \p %vykov_queue::traits: + \code + struct myTraits: public cds::intrusive::vykov_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::vykov_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 +93,47 @@ 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::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::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 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::static_buffer the \p nCapacity parameter is ignored. */ VyukovMPMCCycleQueue( size_t nCapacity = 0 ) : base_class( nCapacity ) @@ -89,7 +141,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,6 +150,8 @@ namespace cds { namespace intrusive { /// Dequeues an item from queue /** + \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 +160,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 +175,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 +188,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 +207,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 +225,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