--- /dev/null
+/*
+ This file is a part of libcds - Concurrent Data Structures library
+
+ (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017
+
+ 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_CONTAINER_MSPRIORITY_QUEUE_H
+#define CDSLIB_CONTAINER_MSPRIORITY_QUEUE_H
+
+#include <memory>
+#include <cds/container/details/base.h>
+#include <cds/intrusive/mspriority_queue.h>
+
+namespace cds { namespace container {
+
+ /// MSPriorityQueue related definitions
+ /** @ingroup cds_nonintrusive_helper
+ */
+ namespace mspriority_queue {
+
+#ifdef CDS_DOXYGEN_INVOKED
+ /// Synonym for \p cds::intrusive::mspriority_queue::stat
+ typedef cds::intrusive::mspriority_queue::stat<> stat;
+
+ /// Synonym for \p cds::intrusive::mspriority_queue::empty_stat
+ typedef cds::intrusive::mspriority_queue::empty_stat empty_stat;
+#else
+ using cds::intrusive::mspriority_queue::stat;
+ using cds::intrusive::mspriority_queue::empty_stat;
+#endif
+
+ /// MSPriorityQueue traits
+ /**
+ The traits for \p %cds::container::MSPriorityQueue is the same as for
+ \p cds::intrusive::MSPriorityQueue (see \p cds::intrusive::mspriority_queue::traits)
+ plus some additional properties.
+ */
+ struct traits: public cds::intrusive::mspriority_queue::traits
+ {
+ /// The allocator use to allocate memory for values
+ typedef CDS_DEFAULT_ALLOCATOR allocator;
+
+ /// Move policy
+ /**
+ The move policy used in \p MSPriorityQueue::pop() function to move item's value.
+ Default is \p opt::v::assignment_move_policy.
+ */
+ typedef cds::opt::v::assignment_move_policy move_policy;
+ };
+
+ /// Metafunction converting option list to traits
+ /**
+ \p Options are:
+ - \p opt::buffer - the buffer type for heap array. Possible type are: \p opt::v::initiaized_static_buffer, \p opt::v::initialized_dynamic_buffer.
+ Default is \p %opt::v::initialized_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::allocator - allocator (like \p std::allocator) for the values of queue's items.
+ Default is \ref CDS_DEFAULT_ALLOCATOR
+ - \p opt::move_policy - policy for moving item's value. Default is \p opt::v::assignment_move_policy.
+ If the compiler supports move semantics it would be better to specify the move policy
+ based on the move semantics for type \p T.
+ - \p opt::stat - internal statistics. Available types: \p mspriority_queue::stat, \p mspriority_queue::empty_stat (the default, no overhead)
+ */
+ 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< traits, Options... >::type
+ ,Options...
+ >::type type;
+# endif
+ };
+ } // namespace mspriority_queue
+
+ /// Michael & Scott array-based lock-based concurrent priority queue heap
+ /** @ingroup cds_nonintrusive_priority_queue
+ Source:
+ - [1996] G.Hunt, M.Michael, S. Parthasarathy, M.Scott
+ "An efficient algorithm for concurrent priority queue heaps"
+
+ \p %MSPriorityQueue augments the standard array-based heap data structure with
+ a mutual-exclusion lock on the heap's size and locks on each node in the heap.
+ Each node also has a tag that indicates whether
+ it is empty, valid, or in a transient state due to an update to the heap
+ by an inserting thread.
+ The algorithm allows concurrent insertions and deletions in opposite directions,
+ without risking deadlock and without the need for special server threads.
+ It also uses a "bit-reversal" technique to scatter accesses across the fringe
+ of the tree to reduce contention.
+ On large heaps the algorithm achieves significant performance improvements
+ over serialized single-lock algorithm, for various insertion/deletion
+ workloads. For small heaps it still performs well, but not as well as
+ 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 - the traits. See \p mspriority_queue::traits for explanation.
+ It is possible to declare option-based queue with \p mspriority_queue::make_traits
+ metafunction instead of \p Traits template argument.
+ */
+ template <typename T, class Traits = mspriority_queue::traits >
+ class MSPriorityQueue: protected cds::intrusive::MSPriorityQueue< T, Traits >
+ {
+ //@cond
+ typedef cds::intrusive::MSPriorityQueue< T, Traits > base_class;
+ //@endcond
+ public:
+ typedef T value_type ; ///< Value type stored in the queue
+ typedef Traits traits ; ///< Traits template parameter
+
+ typedef typename base_class::key_comparator key_comparator; ///< priority comparing functor based on opt::compare and opt::less option setter.
+ typedef typename base_class::lock_type lock_type; ///< heap's size lock type
+ typedef typename base_class::back_off back_off ; ///< Back-off strategy
+ typedef typename traits::stat stat; ///< internal statistics type, see \p intrusive::mspriority_queue::traits::stat
+ typedef typename base_class::item_counter item_counter;///< Item counter type
+ typedef typename traits::allocator::template rebind<value_type>::other allocator_type; ///< Value allocator
+ typedef typename traits::move_policy move_policy; ///< Move policy for type \p T
+
+ protected:
+ //@cond
+ typedef cds::details::Allocator< value_type, allocator_type > cxx_allocator;
+
+ struct value_deleter {
+ void operator()( value_type * p ) const
+ {
+ cxx_allocator().Delete( p );
+ }
+ };
+ typedef std::unique_ptr<value_type, value_deleter> scoped_ptr;
+ //@endcond
+
+ public:
+ /// Constructs empty priority queue
+ /**
+ For \p cds::opt::v::initialized_static_buffer the \p nCapacity parameter is ignored.
+ */
+ MSPriorityQueue( size_t nCapacity )
+ : base_class( nCapacity )
+ {}
+
+ /// Clears priority queue and destructs the object
+ ~MSPriorityQueue()
+ {
+ clear();
+ }
+
+ /// Inserts an item into priority queue
+ /**
+ 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
+ and returns \p true.
+
+ The function use copy constructor to create new heap item from \p val.
+ */
+ bool push( value_type const& val )
+ {
+ scoped_ptr pVal( cxx_allocator().New( val ));
+ if ( base_class::push( *(pVal.get()))) {
+ pVal.release();
+ return true;
+ }
+ return false;
+ }
+
+ /// Inserts an item into the queue using a functor
+ /**
+ \p Func is a functor called to create node.
+ The functor \p f takes one argument - a reference to a new node of type \ref value_type :
+ \code
+ cds::container::MSPriorityQueue< Foo > myQueue;
+ Bar bar;
+ myQueue.push_with( [&bar]( Foo& dest ) { dest = bar; } );
+ \endcode
+ */
+ template <typename Func>
+ bool push_with( Func f )
+ {
+ scoped_ptr pVal( cxx_allocator().New());
+ f( *pVal );
+ if ( base_class::push( *pVal )) {
+ pVal.release();
+ return true;
+ }
+ return false;
+ }
+
+ /// Inserts a item into priority queue
+ /**
+ If the priority queue is full, the function returns \p false,
+ no item has been added.
+ Otherwise, the function inserts a new item created from \p args arguments
+ into the heap and returns \p true.
+ */
+ template <typename... Args>
+ bool emplace( Args&&... args )
+ {
+ scoped_ptr pVal( cxx_allocator().MoveNew( std::forward<Args>(args)... ));
+ if ( base_class::push( *(pVal.get()))) {
+ pVal.release();
+ return true;
+ }
+ return false;
+ }
+
+ /// Extracts item with high priority
+ /**
+ If the priority queue is empty, the function returns \p false.
+ Otherwise, it returns \p true and \p dest contains the copy of extracted item.
+ The item is deleted from the heap.
+
+ The function uses \ref move_policy to move extracted value from the heap's top
+ to \p dest.
+
+ The function is equivalent of such call:
+ \code
+ pop_with( dest, [&dest]( value_type& src ) { move_policy()(dest, src); } );
+ \endcode
+ */
+ bool pop( value_type& dest )
+ {
+ return pop_with( [&dest]( value_type& src ) { move_policy()(dest, std::move(src)); });
+ }
+
+ /// Extracts an item with high priority
+ /**
+ If the priority queue is empty, the function returns \p false.
+ Otherwise, it returns \p true and \p dest contains the copy of extracted item.
+ The item is deleted from the heap.
+
+ \p Func is a functor called to copy popped value.
+ The functor takes one argument - a reference to removed node:
+ \code
+ cds:container::MSPriorityQueue< Foo > myQueue;
+ Bar bar;
+ myQueue.pop_with( [&bar]( Foo& src ) { bar = std::move( src );});
+ \endcode
+ */
+ template <typename Func>
+ bool pop_with( Func f )
+ {
+ value_type * pVal = base_class::pop();
+ if ( pVal ) {
+ f( *pVal );
+ cxx_allocator().Delete( pVal );
+ return true;
+ }
+ return false;
+ }
+
+ /// Clears the queue (not atomic)
+ /**
+ This function is not atomic, but thread-safe
+ */
+ void clear()
+ {
+ base_class::clear_with( []( value_type& src ) { value_deleter()(&src); } );
+ }
+
+ /// Clears the queue (not atomic)
+ /**
+ This function is not atomic, but thread-safe.
+
+ For each item removed the functor \p f is called.
+ \p Func interface is:
+ \code
+ struct clear_functor
+ {
+ void operator()( value_type& item );
+ };
+ \endcode
+ */
+ template <typename Func>
+ void clear_with( Func f )
+ {
+ base_class::clear_with( [&f]( value_type& val ) { f(val); value_deleter()( &val ); } );
+ }
+
+ /// Checks is the priority queue is empty
+ bool empty() const
+ {
+ return base_class::empty();
+ }
+
+ /// Checks if the priority queue is full
+ bool full() const
+ {
+ return base_class::full();
+ }
+
+ /// Returns current size of priority queue
+ size_t size() const
+ {
+ return base_class::size();
+ }
+
+ /// Return capacity of the priority queue
+ size_t capacity() const
+ {
+ return base_class::capacity();
+ }
+
+ /// Returns const reference to internal statistics
+ stat const& statistics() const
+ {
+ return base_class::statistics();
+ }
+ };
+
+}} // namespace cds::container
+
+#endif // #ifndef CDSLIB_CONTAINER_MSPRIORITY_QUEUE_H
projects / c11concurrency-benchmarks.git / blobdiff