X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=cds%2Fcontainer%2Fmoir_queue.h;h=809328ed9a827e271d7fccc8c1dddc54c3ca61e3;hb=68c4bb6ce67fc8fccf8d850868e1e95b91f334a4;hp=e0dd331329fd13bba7c7a442355d14c7a86f6667;hpb=f9c9349624ddf418216d00cd16b303e42ce34813;p=libcds.git diff --git a/cds/container/moir_queue.h b/cds/container/moir_queue.h index e0dd3313..809328ed 100644 --- a/cds/container/moir_queue.h +++ b/cds/container/moir_queue.h @@ -4,123 +4,83 @@ #define __CDS_CONTAINER_MOIR_QUEUE_H #include +#include #include -#include -#include -#include -#include namespace cds { namespace container { //@cond namespace details { - template - struct make_moir_queue + template + struct make_moir_queue: public cds::container::details::make_msqueue< GC, T, Traits > { - typedef GC gc; - typedef T value_type; - - struct default_options { - typedef cds::backoff::empty back_off; - typedef CDS_DEFAULT_ALLOCATOR allocator; - typedef atomicity::empty_item_counter item_counter; - typedef intrusive::queue_dummy_stat stat; - typedef opt::v::relaxed_ordering memory_model; - enum { alignment = opt::cache_line_alignment }; - }; - - typedef typename opt::make_options< - typename cds::opt::find_type_traits< default_options, Options... >::type - ,Options... - >::type options; - - struct node_type: public intrusive::single_link::node< gc > - { - value_type m_value; - - node_type( const value_type& val ) - : m_value( val ) - {} - - template - node_type( Args&&... args ) - : m_value( std::forward(args)...) - {} - }; - - typedef typename options::allocator::template rebind::other allocator_type; - typedef cds::details::Allocator< node_type, allocator_type > cxx_allocator; - - struct node_deallocator - { - void operator ()( node_type * pNode ) - { - cxx_allocator().Delete( pNode ); - } - }; - - typedef intrusive::MoirQueue< - gc - ,node_type - ,intrusive::opt::hook< - intrusive::single_link::base_hook< opt::gc > - > - ,opt::back_off< typename options::back_off > - ,intrusive::opt::disposer< node_deallocator > - ,opt::item_counter< typename options::item_counter > - ,opt::stat< typename options::stat > - ,opt::alignment< options::alignment > - ,opt::memory_model< typename options::memory_model > - > type; + typedef cds::container::details::make_msqueue< GC, T, Traits > base_class; + typedef cds::intrusive::MoirQueue< GC, typename base_class::node_type, typename base_class::intrusive_traits > type; }; } //@endcond /// A variation of Michael & Scott's lock-free queue /** @ingroup cds_nonintrusive_queue - It is non-intrusive version of intrusive::MoirQueue. - - \p T is a type stored in the queue. It should be default-constructible, copy-constructible, assignable type. + It is non-intrusive version of \p cds::intrusive::MoirQueue. - \p Options description see MSQueue + Template arguments: + - \p GC - garbage collector type: \p gc::HP, \p gc::DHP + - \p T - a type stored in the queue. + - \p Traits - queue traits, default is \p msqueue::traits. You can use \p msqueue::make_traits + metafunction to make your traits or just derive your traits from \p %msqueue::traits: + \code + struct myTraits: public cds::container::msqueue::traits { + typedef cds::intrusive::msqueue::stat<> stat; + typedef cds::atomicity::item_counter item_counter; + }; + typedef cds::container::MoirQueue< cds::gc::HP, Foo, myTraits > myQueue; + + // Equivalent make_traits example: + typedef cds::container::MoirQueue< cds::gc::HP, Foo, + typename cds::container::msqueue::make_traits< + cds::opt::stat< cds::container::msqueue::stat<> >, + cds::opt::item_counter< cds::atomicity::item_counter > + >::type + > myQueue; + \endcode */ - template + template class MoirQueue: #ifdef CDS_DOXYGEN_INVOKED - intrusive::MoirQueue< GC, intrusive::single_link::node< T >, Options... > + private intrusive::MoirQueue< GC, intrusive::msqueue::node< T >, Traits > #else - details::make_moir_queue< GC, T, Options... >::type + private details::make_moir_queue< GC, T, Traits >::type #endif { //@cond - typedef details::make_moir_queue< GC, T, Options... > options; - typedef typename options::type base_class; + typedef details::make_moir_queue< GC, T, Traits > maker; + typedef typename maker::type base_class; //@endcond public: /// Rebind template arguments - template + template struct rebind { - typedef MoirQueue< GC2, T2, Options2...> other ; ///< Rebinding result + typedef MoirQueue< GC2, T2, Traits2 > other ; ///< Rebinding result }; public: - typedef T value_type ; ///< Value type stored in the stack - - typedef typename base_class::gc gc ; ///< Garbage collector used - typedef typename base_class::back_off back_off ; ///< Back-off strategy used - typedef typename options::allocator_type allocator_type ; ///< Allocator type used for allocate/deallocate the nodes - typedef typename options::options::item_counter item_counter ; ///< Item counting policy used - typedef typename options::options::stat stat ; ///< Internal statistics policy used - typedef typename base_class::memory_model memory_model ; ///< Memory ordering. See cds::opt::memory_model option + typedef T value_type ; ///< Value type stored in the queue + typedef typename base_class::gc gc; ///< Garbage collector + typedef typename base_class::back_off back_off; ///< Back-off strategy + typedef typename maker::allocator_type allocator_type; ///< Allocator type used for allocate/deallocate the nodes + typedef typename base_class::item_counter item_counter; ///< Item counting policy used + 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 protected: - typedef typename options::node_type node_type ; ///< queue node type (derived from intrusive::single_link::node) - //@cond - typedef typename options::cxx_allocator cxx_allocator; - typedef typename options::node_deallocator node_deallocator; // deallocate node - typedef typename base_class::node_traits node_traits; + typedef typename maker::node_type node_type; ///< queue node type (derived from intrusive::msqueue::node) + + typedef typename maker::cxx_allocator cxx_allocator; + typedef typename maker::node_deallocator node_deallocator; // deallocate node + typedef typename base_class::node_traits node_traits; //@endcond protected: @@ -161,22 +121,10 @@ namespace cds { namespace container { ~MoirQueue() {} - /// Returns queue's item count (see \ref intrusive::MSQueue::size for explanation) - size_t size() const - { - return base_class::size(); - } - - /// Returns refernce to internal statistics - const stat& statistics() const - { - return base_class::statistics(); - } - /// Enqueues \p val value into the queue. /** The function makes queue node in dynamic memory calling copy constructor for \p val - and then it calls intrusive::MSQueue::enqueue. + and then it calls intrusive::MoirQueue::enqueue. Returns \p true if success, \p false otherwise. */ bool enqueue( value_type const& val ) @@ -189,29 +137,22 @@ namespace cds { namespace container { return false; } - /// Enqueues \p data to queue using copy functor + /// Enqueues \p data to queue using a functor /** - \p Func is a functor called to copy value \p data of type \p Type - which may be differ from type \p T stored in the queue. - The functor's interface is: + \p Func is a functor calling to create a new node. + The functor should initialize creating node + and it takes one argument - a reference to a new node of type \ref value_type : \code - struct myFunctor { - void operator()(T& dest, SOURCE const& data) - { - // // Code to copy \p data to \p dest - dest = data; - } - }; + cds:container::MoirQueue< cds::gc::HP, Foo > myQueue; + Bar bar; + myQueue.enqueue_with( [&bar]( Foo& dest ) { dest = bar; } ); \endcode - You may use \p boost:ref construction to pass functor \p f by reference. - - Requirements The functor \p Func should not throw any exception. */ - template - bool enqueue( const Type& data, Func f ) + template + bool enqueue_with( Func f ) { - scoped_node_ptr p( alloc_node()); - unref(f)( node_traits::to_value_ptr( *p )->m_value, data ); + scoped_node_ptr p( alloc_node() ); + f( p->m_value ); if ( base_class::enqueue( *p )) { p.release(); return true; @@ -219,38 +160,31 @@ namespace cds { namespace container { return false; } - /// Dequeues a value using copy functor - /** - \p Func is a functor called to copy dequeued value to \p dest of type \p Type - which may be differ from type \p T stored in the queue. - The functor's interface is: - \code - struct myFunctor { - void operator()(Type& dest, T const& data) - { - // // Code to copy \p data to \p dest - dest = data; - } - }; - \endcode - You may use \p boost:ref construction to pass functor \p f by reference. - - Requirements The functor \p Func should not throw any exception. - */ - template - bool dequeue( Type& dest, Func f ) + /// Enqueues data of type \ref value_type constructed with std::forward(args)... + template + bool emplace( Args&&... args ) { - typename base_class::dequeue_result res; - if ( base_class::do_dequeue( res )) { - unref(f)( dest, node_traits::to_value_ptr( *res.pNext )->m_value ); - - base_class::dispose_result( res ); - + scoped_node_ptr p( alloc_node_move( std::forward( args )... ) ); + if ( base_class::enqueue( *p ) ) { + p.release(); return true; } return false; } + /// Synonym for \p enqueue() function + bool push( value_type const& val ) + { + return enqueue( val ); + } + + /// Synonym for \p enqueue_with() function + template + bool push_with( Func f ) + { + return enqueue_with( f ); + } + /// Dequeues a value from the queue /** If queue is not empty, the function returns \p true, \p dest contains copy of @@ -259,64 +193,74 @@ namespace cds { namespace container { */ bool dequeue( value_type& dest ) { - typedef cds::details::trivial_assign functor; - return dequeue( dest, functor() ); + return dequeue_with( [&dest]( value_type& src ) { dest = src; } ); } - /// Synonym for \ref enqueue function - bool push( const value_type& val ) - { - return enqueue( val ); - } - - /// Synonym for template version of \ref enqueue function - template - bool push( const Type& data, Func f ) - { - return enqueue( data, f ); - } - - /// Enqueues data of type \ref value_type constructed with std::forward(args)... - template - bool emplace( Args&&... args ) + /// Dequeues a value using a functor + /** + \p Func is a functor called to copy dequeued value. + The functor takes one argument - a reference to removed node: + \code + cds:container::MoirQueue< cds::gc::HP, Foo > myQueue; + Bar bar; + myQueue.dequeue_with( [&bar]( Foo& src ) { bar = std::move( src );}); + \endcode + The functor is called only if the queue is not empty. + */ + template + bool dequeue_with( Func f ) { - scoped_node_ptr p( alloc_node_move( std::forward(args)... )); - if ( base_class::enqueue( *p )) { - p.release(); + typename base_class::dequeue_result res; + if ( base_class::do_dequeue( res )) { + f( node_traits::to_value_ptr( *res.pNext )->m_value ); + base_class::dispose_result( res ); return true; } return false; } - /// Synonym for \ref dequeue function + /// Synonym for \p dequeue() function bool pop( value_type& dest ) { return dequeue( dest ); } - /// Synonym for template version of \ref dequeue function - template - bool pop( Type& dest, Func f ) + /// Synonym for \p dequeue_with() function + template + bool pop_with( Func f ) { - return dequeue( dest, f ); - } - - /// Checks if the queue is empty - bool empty() const - { - return base_class::empty(); + return dequeue_with( f ); } /// Clear the queue /** - The function repeatedly calls \ref dequeue until it returns nullptr. - The disposer defined in template \p Options is called for each item + The function repeatedly calls \ref dequeue until it returns \p nullptr. + The disposer defined in template \p Traits is called for each item that can be safely disposed. */ void clear() { base_class::clear(); } + + /// Checks if the queue is empty + bool empty() const + { + return base_class::empty(); + } + + /// Returns queue's item count (see \ref intrusive::MSQueue::size for explanation) + size_t size() const + { + return base_class::size(); + } + + /// Returns refernce to internal statistics + const stat& statistics() const + { + return base_class::statistics(); + } + }; }} // namespace cds::container