cds/container/mspriority_queue.h

   1 /*
   2     This file is a part of libcds - Concurrent Data Structures library
   3
   4     (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
   5
   6     Source code repo: http://github.com/khizmax/libcds/
   7     Download: http://sourceforge.net/projects/libcds/files/
   8
   9     Redistribution and use in source and binary forms, with or without
  10     modification, are permitted provided that the following conditions are met:
  11
  12     * Redistributions of source code must retain the above copyright notice, this
  13       list of conditions and the following disclaimer.
  14
  15     * Redistributions in binary form must reproduce the above copyright notice,
  16       this list of conditions and the following disclaimer in the documentation
  17       and/or other materials provided with the distribution.
  18
  19     THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  20     AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  21     IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  22     DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
  23     FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  24     DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
  25     SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  26     CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  27     OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  28     OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  29 */
  30
  31 #ifndef CDSLIB_CONTAINER_MSPRIORITY_QUEUE_H
  32 #define CDSLIB_CONTAINER_MSPRIORITY_QUEUE_H
  33
  34 #include <memory>
  35 #include <cds/container/details/base.h>
  36 #include <cds/intrusive/mspriority_queue.h>
  37
  38 namespace cds { namespace container {
  39
  40     /// MSPriorityQueue related definitions
  41     /** @ingroup cds_nonintrusive_helper
  42     */
  43     namespace mspriority_queue {
  44
  45 #ifdef CDS_DOXYGEN_INVOKED
  46         /// Synonym for \p cds::intrusive::mspriority_queue::stat
  47         typedef cds::intrusive::mspriority_queue::stat<> stat;
  48
  49         /// Synonym for \p cds::intrusive::mspriority_queue::empty_stat
  50         typedef cds::intrusive::mspriority_queue::empty_stat empty_stat;
  51
  52         /// Synonym for \p cds::intrusive::mspriority_queue::monotonic_counter
  53         typedef cds::intrusive::mspriority_queue::monotonic_counter monotonic_counter;
  54 #else
  55         using cds::intrusive::mspriority_queue::stat;
  56         using cds::intrusive::mspriority_queue::empty_stat;
  57         using cds::intrusive::mspriority_queue::monotonic_counter;
  58 #endif
  59
  60         /// MSPriorityQueue traits
  61         /**
  62             The traits for \p %cds::container::MSPriorityQueue is the same as for
  63             \p cds::intrusive::MSPriorityQueue (see \p cds::intrusive::mspriority_queue::traits)
  64             plus some additional properties.
  65         */
  66         struct traits: public cds::intrusive::mspriority_queue::traits
  67         {
  68             /// The allocator use to allocate memory for values
  69             typedef CDS_DEFAULT_ALLOCATOR   allocator;
  70
  71             /// Move policy
  72             /**
  73                 The move policy used in \p MSPriorityQueue::pop functions
  74                 to move item's value.
  75                 Default is \p opt::v::assignment_move_policy.
  76             */
  77             typedef cds::opt::v::assignment_move_policy  move_policy;
  78         };
  79
  80         /// Metafunction converting option list to traits
  81         /**
  82             \p Options are:
  83             - \p opt::buffer - the buffer type for heap array. Possible type are: \p opt::v::initiaized_static_buffer, \p opt::v::initialized_dynamic_buffer.
  84                 Default is \p %opt::v::initialized_dynamic_buffer.
  85                 You may specify any type of values for the buffer since at instantiation time
  86                 the \p buffer::rebind member metafunction is called to change the type of values stored in the buffer.
  87             - \p opt::compare - priority compare functor. No default functor is provided.
  88                 If the option is not specified, the \p opt::less is used.
  89             - \p opt::less - specifies binary predicate used for priority compare. Default is \p std::less<T>.
  90             - \p opt::lock_type - lock type. Default is \p cds::sync::spin.
  91             - \p opt::back_off - back-off strategy. Default is \p cds::backoff::yield
  92             - \p opt::allocator - allocator (like \p std::allocator) for the values of queue's items.
  93                 Default is \ref CDS_DEFAULT_ALLOCATOR
  94             - \p opt::move_policy - policy for moving item's value. Default is \p opt::v::assignment_move_policy.
  95                 If the compiler supports move semantics it would be better to specify the move policy
  96                 based on the move semantics for type \p T.
  97             - \p opt::stat - internal statistics. Available types: \p mspriority_queue::stat, \p mspriority_queue::empty_stat (the default, no overhead)
  98             - \p opt::item_counter - an item counter type for \p MSPriorityQueue.
  99                 Available type: \p cds::bitop::bit_reverse_counter, \p mspriority_queue::monotonic_counter. See \p cds::intrusive::mspriority_queue::traits::item_counter for details.
 100             */
 101         template <typename... Options>
 102         struct make_traits {
 103 #   ifdef CDS_DOXYGEN_INVOKED
 104             typedef implementation_defined type ;   ///< Metafunction result
 105 #   else
 106             typedef typename cds::opt::make_options<
 107                 typename cds::opt::find_type_traits< traits, Options... >::type
 108                 ,Options...
 109             >::type   type;
 110 #   endif
 111         };
 112     }   // namespace mspriority_queue
 113
 114     /// Michael & Scott array-based lock-based concurrent priority queue heap
 115     /** @ingroup cds_nonintrusive_priority_queue
 116         Source:
 117             - [1996] G.Hunt, M.Michael, S. Parthasarathy, M.Scott
 118                 "An efficient algorithm for concurrent priority queue heaps"
 119
 120         \p %MSPriorityQueue augments the standard array-based heap data structure with
 121         a mutual-exclusion lock on the heap's size and locks on each node in the heap.
 122         Each node also has a tag that indicates whether
 123         it is empty, valid, or in a transient state due to an update to the heap
 124         by an inserting thread.
 125         The algorithm allows concurrent insertions and deletions in opposite directions,
 126         without risking deadlock and without the need for special server threads.
 127         It also uses a "bit-reversal" technique to scatter accesses across the fringe
 128         of the tree to reduce contention.
 129         On large heaps the algorithm achieves significant performance improvements
 130         over serialized single-lock algorithm, for various insertion/deletion
 131         workloads. For small heaps it still performs well, but not as well as
 132         single-lock algorithm.
 133
 134         Template parameters:
 135         - \p T - type to be stored in the list. The priority is a part of \p T type.
 136         - \p Traits - the traits. See \p mspriority_queue::traits for explanation.
 137              It is possible to declare option-based queue with \p mspriority_queue::make_traits
 138              metafunction instead of \p Traits template argument.
 139     */
 140     template <typename T, class Traits = mspriority_queue::traits >
 141     class MSPriorityQueue: protected cds::intrusive::MSPriorityQueue< T, Traits >
 142     {
 143         //@cond
 144         typedef cds::intrusive::MSPriorityQueue< T, Traits > base_class;
 145         //@endcond
 146     public:
 147         typedef T           value_type  ;   ///< Value type stored in the queue
 148         typedef Traits      traits      ;   ///< Traits template parameter
 149
 150         typedef typename base_class::key_comparator key_comparator; ///< priority comparing functor based on opt::compare and opt::less option setter.
 151         typedef typename base_class::lock_type lock_type;   ///< heap's size lock type
 152         typedef typename base_class::back_off  back_off ;   ///< Back-off strategy
 153         typedef typename traits::stat          stat;        ///< internal statistics type, see \p intrusive::mspriority_queue::traits::stat
 154         typedef typename traits::item_counter  item_counter;///< Item counter type, see \p intrusive::mspriority_queue::traits::item_counter
 155         typedef typename traits::allocator::template rebind<value_type>::other allocator_type; ///< Value allocator
 156         typedef typename traits::move_policy   move_policy; ///< Move policy for type \p T
 157
 158     protected:
 159         //@cond
 160         typedef cds::details::Allocator< value_type, allocator_type >  cxx_allocator;
 161
 162         struct value_deleter {
 163             void operator()( value_type * p ) const
 164             {
 165                 cxx_allocator().Delete( p );
 166             }
 167         };
 168         typedef std::unique_ptr<value_type, value_deleter> scoped_ptr;
 169         //@endcond
 170
 171     public:
 172         /// Constructs empty priority queue
 173         /**
 174             For \p cds::opt::v::initialized_static_buffer the \p nCapacity parameter is ignored.
 175         */
 176         MSPriorityQueue( size_t nCapacity )
 177             : base_class( nCapacity )
 178         {}
 179
 180         /// Clears priority queue and destructs the object
 181         ~MSPriorityQueue()
 182         {
 183             clear();
 184         }
 185
 186         /// Inserts an item into priority queue
 187         /**
 188             If the priority queue is full, the function returns \p false,
 189             no item has been added.
 190             Otherwise, the function inserts the copy of \p val into the heap
 191             and returns \p true.
 192
 193             The function use copy constructor to create new heap item from \p val.
 194         */
 195         bool push( value_type const& val )
 196         {
 197             scoped_ptr pVal( cxx_allocator().New( val ));
 198             if ( base_class::push( *(pVal.get()) )) {
 199                 pVal.release();
 200                 return true;
 201             }
 202             return false;
 203         }
 204
 205         /// Inserts an item into the queue using a functor
 206         /**
 207             \p Func is a functor called to create node.
 208             The functor \p f takes one argument - a reference to a new node of type \ref value_type :
 209             \code
 210             cds::container::MSPriorityQueue< Foo > myQueue;
 211             Bar bar;
 212             myQueue.push_with( [&bar]( Foo& dest ) { dest = bar; } );
 213             \endcode
 214         */
 215         template <typename Func>
 216         bool push_with( Func f )
 217         {
 218             scoped_ptr pVal( cxx_allocator().New() );
 219             f( *pVal );
 220             if ( base_class::push( *pVal )) {
 221                 pVal.release();
 222                 return true;
 223             }
 224             return false;
 225         }
 226
 227         /// Inserts a item into priority queue
 228         /**
 229             If the priority queue is full, the function returns \p false,
 230             no item has been added.
 231             Otherwise, the function inserts a new item created from \p args arguments
 232             into the heap and returns \p true.
 233         */
 234         template <typename... Args>
 235         bool emplace( Args&&... args )
 236         {
 237             scoped_ptr pVal( cxx_allocator().MoveNew( std::forward<Args>(args)... ));
 238             if ( base_class::push( *(pVal.get()) )) {
 239                 pVal.release();
 240                 return true;
 241             }
 242             return false;
 243         }
 244
 245         /// Extracts item with high priority
 246         /**
 247             If the priority queue is empty, the function returns \p false.
 248             Otherwise, it returns \p true and \p dest contains the copy of extracted item.
 249             The item is deleted from the heap.
 250
 251             The function uses \ref move_policy to move extracted value from the heap's top
 252             to \p dest.
 253
 254             The function is equivalent of such call:
 255             \code
 256                 pop_with( dest, [&dest]( value_type& src ) { move_policy()(dest, src); } );
 257             \endcode
 258         */
 259         bool pop( value_type& dest )
 260         {
 261             return pop_with( [&dest]( value_type& src ) { move_policy()(dest, std::move(src)); });
 262         }
 263
 264         /// Extracts an item with high priority
 265         /**
 266             If the priority queue is empty, the function returns \p false.
 267             Otherwise, it returns \p true and \p dest contains the copy of extracted item.
 268             The item is deleted from the heap.
 269
 270             \p Func is a functor called to copy popped value.
 271             The functor takes one argument - a reference to removed node:
 272             \code
 273             cds:container::MSPriorityQueue< Foo > myQueue;
 274             Bar bar;
 275             myQueue.pop_with( [&bar]( Foo& src ) { bar = std::move( src );});
 276             \endcode
 277         */
 278         template <typename Func>
 279         bool pop_with( Func f )
 280         {
 281             value_type * pVal = base_class::pop();
 282             if ( pVal ) {
 283                 f( *pVal );
 284                 cxx_allocator().Delete( pVal );
 285                 return true;
 286             }
 287             return false;
 288         }
 289
 290         /// Clears the queue (not atomic)
 291         /**
 292             This function is not atomic, but thread-safe
 293         */
 294         void clear()
 295         {
 296             base_class::clear_with( []( value_type& src ) { value_deleter()(&src); } );
 297         }
 298
 299         /// Clears the queue (not atomic)
 300         /**
 301             This function is not atomic, but thread-safe.
 302
 303             For each item removed the functor \p f is called.
 304             \p Func interface is:
 305             \code
 306                 struct clear_functor
 307                 {
 308                     void operator()( value_type& item );
 309                 };
 310             \endcode
 311         */
 312         template <typename Func>
 313         void clear_with( Func f )
 314         {
 315             base_class::clear_with( [&f]( value_type& val ) { f(val); value_deleter()( &val ); } );
 316         }
 317
 318         /// Checks is the priority queue is empty
 319         bool empty() const
 320         {
 321             return base_class::empty();
 322         }
 323
 324         /// Checks if the priority queue is full
 325         bool full() const
 326         {
 327             return base_class::full();
 328         }
 329
 330         /// Returns current size of priority queue
 331         size_t size() const
 332         {
 333             return base_class::size();
 334         }
 335
 336         /// Return capacity of the priority queue
 337         size_t capacity() const
 338         {
 339             return base_class::capacity();
 340         }
 341
 342         /// Returns const reference to internal statistics
 343         stat const& statistics() const
 344         {
 345             return base_class::statistics();
 346         }
 347     };
 348
 349 }} // namespace cds::container
 350
 351 #endif // #ifndef CDSLIB_CONTAINER_MSPRIORITY_QUEUE_H