X-Git-Url: http://plrg.eecs.uci.edu/git/?p=libcds.git;a=blobdiff_plain;f=cds%2Fintrusive%2Fmspriority_queue.h;h=5ba498ab1b10c12bf16aff059eaa9cfa26084242;hp=0f29612a8d076311c91afdc6e61b82d9c7b4d92b;hb=6777cc22570e8a3def3a35924a172d537bfb006f;hpb=abe9634d97a9fece9abe5b0cfc78dc62f62f08c8 diff --git a/cds/intrusive/mspriority_queue.h b/cds/intrusive/mspriority_queue.h index 0f29612a..5ba498ab 100644 --- a/cds/intrusive/mspriority_queue.h +++ b/cds/intrusive/mspriority_queue.h @@ -1,17 +1,17 @@ //$$CDS-header$$ -#ifndef __CDS_INTRUSIVE_MSPRIORITY_QUEUE_H -#define __CDS_INTRUSIVE_MSPRIORITY_QUEUE_H +#ifndef CDSLIB_INTRUSIVE_MSPRIORITY_QUEUE_H +#define CDSLIB_INTRUSIVE_MSPRIORITY_QUEUE_H -#include -#include +#include // std::unique_lock +#include +#include #include #include #include #include #include #include -#include namespace cds { namespace intrusive { @@ -54,11 +54,11 @@ namespace cds { namespace intrusive { //@endcond }; - /// Type traits for MSPriorityQueue - struct type_traits { + /// MSPriorityQueue traits + struct traits { /// Storage type /** - The storage type for the heap array. Default is cds::opt::v::dynamic_buffer. + The storage type for the heap array. Default is \p cds::opt::v::dynamic_buffer. You may specify any type of buffer's value since at instantiation time the \p buffer::rebind member metafunction is called to change type @@ -70,23 +70,23 @@ namespace cds { namespace intrusive { /** No default functor is provided. If the option is not specified, the \p less is used. */ - typedef opt::none compare; + typedef opt::none compare; - /// specifies binary predicate used for priority comparing. + /// Specifies binary predicate used for priority comparing. /** Default is \p std::less. */ - typedef opt::none less; + typedef opt::none less; /// Type of mutual-exclusion lock - typedef lock::Spin lock_type; + typedef cds::sync::spin lock_type; /// Back-off strategy typedef backoff::yield back_off; /// Internal statistics /** - Possible types: mspriority_queue::empty_stat (the default), mspriority_queue::stat + Possible types: \p mspriority_queue::empty_stat (the default, no overhead), \p mspriority_queue::stat or any other with interface like \p %mspriority_queue::stat */ typedef empty_stat stat; @@ -94,9 +94,17 @@ namespace cds { namespace intrusive { /// Metafunction converting option list to traits /** - This is a wrapper for cds::opt::make_options< type_traits, Options...> - - See \ref MSPriorityQueue, \ref type_traits, \ref cds::opt::make_options. + \p Options: + - \p opt::buffer - the buffer type for heap array. Possible type are: \p opt::v::static_buffer, \p opt::v::dynamic_buffer. + Default is \p %opt::v::dynamic_buffer. + You may specify any type of values for the buffer since at instantiation time + the \p buffer::rebind member metafunction is called to change the type of values stored in the buffer. + - \p opt::compare - priority compare functor. No default functor is provided. + If the option is not specified, the \p opt::less is used. + - \p opt::less - specifies binary predicate used for priority compare. Default is \p std::less. + - \p opt::lock_type - lock type. Default is \p cds::sync::spin + - \p opt::back_off - back-off strategy. Default is \p cds::backoff::yield + - \p opt::stat - internal statistics. Available types: \p mspriority_queue::stat, \p mspriority_queue::empty_stat (the default, no overhead) */ template struct make_traits { @@ -104,7 +112,7 @@ namespace cds { namespace intrusive { typedef implementation_defined type ; ///< Metafunction result # else typedef typename cds::opt::make_options< - typename cds::opt::find_type_traits< type_traits, Options... >::type + typename cds::opt::find_type_traits< traits, Options... >::type ,Options... >::type type; # endif @@ -133,24 +141,12 @@ namespace cds { namespace intrusive { single-lock algorithm. Template parameters: - - \p T - type to be stored in the list. The priority is a part of \p T type. - - \p Traits - type traits. See mspriority_queue::type_traits for explanation. - - It is possible to declare option-based queue with cds::container::mspriority_queue::make_traits - metafunction instead of \p Traits template argument. - Template argument list \p Options of \p %cds::container::mspriority_queue::make_traits metafunction are: - - opt::buffer - the buffer type for heap array. Possible type are: opt::v::static_buffer, opt::v::dynamic_buffer. - Default is \p %opt::v::dynamic_buffer. - You may specify any type of values for the buffer since at instantiation time - the \p buffer::rebind member metafunction is called to change the type of values stored in the buffer. - - opt::compare - priority compare functor. No default functor is provided. - If the option is not specified, the opt::less is used. - - opt::less - specifies binary predicate used for priority compare. Default is \p std::less. - - opt::lock_type - lock type. Default is cds::lock::Spin. - - opt::back_off - back-off strategy. Default is cds::backoff::yield - - opt::stat - internal statistics. Available types: mspriority_queue::stat, mspriority_queue::empty_stat (the default) + - \p T - type to be stored in the queue. The priority is a part of \p T type. + - \p Traits - type traits. See \p mspriority_queue::traits for explanation. + It is possible to declare option-based queue with \p cds::container::mspriority_queue::make_traits + metafunction instead of \p Traits template argument. */ - template + template class MSPriorityQueue: public cds::bounded_container { public: @@ -204,17 +200,6 @@ namespace cds { namespace intrusive { }; //@endcond - protected: - //@cond -# ifndef CDS_CXX11_LAMBDA_SUPPORT - struct empty_cleaner - { - void operator()( value_type const& ) const - {} - }; -# endif - //@endcond - public: typedef typename traits::buffer::template rebind::other buffer_type ; ///< Heap array buffer type @@ -248,14 +233,14 @@ namespace cds { namespace intrusive { /** If the priority queue is full, the function returns \p false, no item has been added. - Otherwise, the function inserts the copy of \p val into the heap + Otherwise, the function inserts the pointer to \p val into the heap and returns \p true. - The function use copy constructor to create new heap item from \p val. + The function does not make a copy of \p val. */ bool push( value_type& val ) { - tag_type const curId = cds::OS::getCurrentThreadId(); + tag_type const curId = cds::OS::get_current_thread_id(); // Insert new item at bottom of the heap m_Lock.lock(); @@ -287,8 +272,6 @@ namespace cds { namespace intrusive { /** If the priority queue is empty, the function returns \p nullptr. Otherwise, it returns the item extracted. - - The item returned may be disposed immediately. */ value_type * pop() { @@ -297,7 +280,7 @@ namespace cds { namespace intrusive { // the heap is empty m_Lock.unlock(); m_Stat.onPopFailed(); - return false; + return nullptr; } counter_type nBottom = m_ItemCounter.reversed_value(); m_ItemCounter.dec(); @@ -326,8 +309,6 @@ namespace cds { namespace intrusive { std::swap( refTop.m_pVal, pVal ); refTop.m_nTag = tag_type( Available ); - assert( nBottom > 1 ); - // refTop will be unlocked inside heapify_after_pop heapify_after_pop( 1, &refTop ); @@ -341,11 +322,7 @@ namespace cds { namespace intrusive { */ void clear() { -# ifdef CDS_CXX11_LAMBDA_SUPPORT - clear_with( []( value_type const& src ) {} ); -# else - clear_with( empty_cleaner() ); -# endif + clear_with( []( value_type const& /*src*/ ) {} ); } /// Clears the queue (not atomic) @@ -368,7 +345,7 @@ namespace cds { namespace intrusive { while ( !empty() ) { value_type * pVal = pop(); if ( pVal ) - cds::unref(f)( *pVal ); + f( *pVal ); } } @@ -387,9 +364,8 @@ namespace cds { namespace intrusive { /// Returns current size of priority queue size_t size() const { - m_Lock.lock(); + std::unique_lock l( m_Lock ); size_t nSize = (size_t) m_ItemCounter.value(); - m_Lock.unlock(); return nSize; } @@ -512,4 +488,4 @@ namespace cds { namespace intrusive { }} // namespace cds::intrusive -#endif // #ifndef __CDS_INTRUSIVE_MSPRIORITY_QUEUE_H +#endif // #ifndef CDSLIB_INTRUSIVE_MSPRIORITY_QUEUE_H