//$$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 <cds/intrusive/base.h>
-#include <cds/lock/spinlock.h>
+#include <mutex> // std::unique_lock
+#include <cds/intrusive/details/base.h>
+#include <cds/sync/spinlock.h>
#include <cds/os/thread.h>
#include <cds/details/bit_reverse_counter.h>
#include <cds/intrusive/options.h>
#include <cds/opt/buffer.h>
#include <cds/opt/compare.h>
#include <cds/details/bounded_container.h>
-#include <cds/ref.h>
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
+ You may specify any type of buffer's value since at instantiation time
+ the \p buffer::rebind member metafunction is called to change type
of values stored in the buffer.
*/
typedef opt::v::dynamic_buffer<void *> buffer;
/**
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<T>.
*/
- 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;
/// Metafunction converting option list to traits
/**
- This is a wrapper for <tt> cds::opt::make_options< type_traits, Options...> </tt>
-
- 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<T>.
+ - \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 <CDS_DECL_OPTIONS7>
+ 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< type_traits, CDS_OPTIONS7 >::type
- ,CDS_OPTIONS7
+ typename cds::opt::find_type_traits< traits, Options... >::type
+ ,Options...
>::type type;
# endif
};
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<T>.
- - 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 <typename T, class Traits>
+ template <typename T, class Traits = mspriority_queue::traits >
class MSPriorityQueue: public cds::bounded_container
{
public:
/// Creates empty node
node()
- : m_pVal( null_ptr<value_type *>() )
+ : m_pVal( nullptr )
, m_nTag( tag_type(Empty) )
{}
};
//@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<node>::other buffer_type ; ///< Heap array buffer type
/**
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();
/**
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()
{
// the heap is empty
m_Lock.unlock();
m_Stat.onPopFailed();
- return false;
+ return nullptr;
}
counter_type nBottom = m_ItemCounter.reversed_value();
m_ItemCounter.dec();
m_Lock.unlock();
refBottom.m_nTag = tag_type(Empty);
value_type * pVal = refBottom.m_pVal;
- refBottom.m_pVal = null_ptr<value_type *>();
+ refBottom.m_pVal = nullptr;
refBottom.unlock();
node& refTop = m_Heap[ 1 ];
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 );
*/
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)
while ( !empty() ) {
value_type * pVal = pop();
if ( pVal )
- cds::unref(f)( *pVal );
+ f( *pVal );
}
}
/// Returns current size of priority queue
size_t size() const
{
- m_Lock.lock();
+ std::unique_lock<lock_type> l( m_Lock );
size_t nSize = (size_t) m_ItemCounter.value();
- m_Lock.unlock();
return nSize;
}
}} // namespace cds::intrusive
-#endif // #ifndef __CDS_INTRUSIVE_MSPRIORITY_QUEUE_H
+#endif // #ifndef CDSLIB_INTRUSIVE_MSPRIORITY_QUEUE_H
projects / libcds.git / blobdiff