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 cds::intrusive::mspriority_queue::stat
  47         typedef cds::intrusive::mspriority_queue::stat<> stat;
  48
  49         /// Synonym for cds::intrusive::mspriority_queue::empty_stat
  50         typedef cds::intrusive::mspriority_queue::empty_stat empty_stat;
  51 #else
  52         using cds::intrusive::mspriority_queue::stat;
  53         using cds::intrusive::mspriority_queue::empty_stat;
  54 #endif
  55
  56         /// MSPriorityQueue traits
  57         /**
  58             The traits for \p %cds::container::MSPriorityQueue is the same as for
  59             \p cds::intrusive::MSPriorityQueue (see \p cds::intrusive::mspriority_queue::traits)
  60             plus some additional properties.
  61         */
  62         struct traits: public cds::intrusive::mspriority_queue::traits
  63         {
  64             /// The allocator use to allocate memory for values
  65             typedef CDS_DEFAULT_ALLOCATOR   allocator;
  66
  67             /// Move policy
  68             /**
  69                 The move policy used in \p MSPriorityQueue::pop functions
  70                 to move item's value.
  71                 Default is \p opt::v::assignment_move_policy.
  72             */
  73             typedef cds::opt::v::assignment_move_policy  move_policy;
  74         };
  75
  76         /// Metafunction converting option list to traits
  77         /**
  78             \p Options are:
  79             - \p opt::buffer - the buffer type for heap array. Possible type are: \p opt::v::initiaized_static_buffer, \p opt::v::initialized_dynamic_buffer.
  80                 Default is \p %opt::v::initialized_dynamic_buffer.
  81                 You may specify any type of values for the buffer since at instantiation time
  82                 the \p buffer::rebind member metafunction is called to change the type of values stored in the buffer.
  83             - \p opt::compare - priority compare functor. No default functor is provided.
  84                 If the option is not specified, the \p opt::less is used.
  85             - \p opt::less - specifies binary predicate used for priority compare. Default is \p std::less<T>.
  86             - \p opt::lock_type - lock type. Default is \p cds::sync::spin.
  87             - \p opt::back_off - back-off strategy. Default is \p cds::backoff::yield
  88             - \p opt::allocator - allocator (like \p std::allocator) for the values of queue's items.
  89                 Default is \ref CDS_DEFAULT_ALLOCATOR
  90             - \p opt::move_policy - policy for moving item's value. Default is \p opt::v::assignment_move_policy.
  91                 If the compiler supports move semantics it would be better to specify the move policy
  92                 based on the move semantics for type \p T.
  93             - \p opt::stat - internal statistics. Available types: \p mspriority_queue::stat, \p mspriority_queue::empty_stat (the default, no overhead)
  94         */
  95         template <typename... Options>
  96         struct make_traits {
  97 #   ifdef CDS_DOXYGEN_INVOKED
  98             typedef implementation_defined type ;   ///< Metafunction result
  99 #   else
 100             typedef typename cds::opt::make_options<
 101                 typename cds::opt::find_type_traits< traits, Options... >::type
 102                 ,Options...
 103             >::type   type;
 104 #   endif
 105         };
 106     }   // namespace mspriority_queue
 107
 108     /// Michael & Scott array-based lock-based concurrent priority queue heap
 109     /** @ingroup cds_nonintrusive_priority_queue
 110         Source:
 111             - [1996] G.Hunt, M.Michael, S. Parthasarathy, M.Scott
 112                 "An efficient algorithm for concurrent priority queue heaps"
 113
 114         \p %MSPriorityQueue augments the standard array-based heap data structure with
 115         a mutual-exclusion lock on the heap's size and locks on each node in the heap.
 116         Each node also has a tag that indicates whether
 117         it is empty, valid, or in a transient state due to an update to the heap
 118         by an inserting thread.
 119         The algorithm allows concurrent insertions and deletions in opposite directions,
 120         without risking deadlock and without the need for special server threads.
 121         It also uses a "bit-reversal" technique to scatter accesses across the fringe
 122         of the tree to reduce contention.
 123         On large heaps the algorithm achieves significant performance improvements
 124         over serialized single-lock algorithm, for various insertion/deletion
 125         workloads. For small heaps it still performs well, but not as well as
 126         single-lock algorithm.
 127
 128         Template parameters:
 129         - \p T - type to be stored in the list. The priority is a part of \p T type.
 130         - \p Traits - the traits. See \p mspriority_queue::traits for explanation.
 131              It is possible to declare option-based queue with \p mspriority_queue::make_traits
 132              metafunction instead of \p Traits template argument.
 133     */
 134     template <typename T, class Traits = mspriority_queue::traits >
 135     class MSPriorityQueue: protected cds::intrusive::MSPriorityQueue< T, Traits >
 136     {
 137         //@cond
 138         typedef cds::intrusive::MSPriorityQueue< T, Traits > base_class;
 139         //@endcond
 140     public:
 141         typedef T           value_type  ;   ///< Value type stored in the queue
 142         typedef Traits      traits      ;   ///< Traits template parameter
 143
 144         typedef typename base_class::key_comparator key_comparator; ///< priority comparing functor based on opt::compare and opt::less option setter.
 145         typedef typename base_class::lock_type lock_type; ///< heap's size lock type
 146         typedef typename base_class::back_off  back_off ; ///< Back-off strategy
 147         typedef typename base_class::stat          stat ; ///< internal statistics type
 148         typedef typename traits::allocator::template rebind<value_type>::other allocator_type; ///< Value allocator
 149         typedef typename traits::move_policy move_policy; ///< Move policy for type \p T
 150
 151     protected:
 152         //@cond
 153         typedef cds::details::Allocator< value_type, allocator_type >  cxx_allocator;
 154
 155         struct value_deleter {
 156             void operator()( value_type * p ) const
 157             {
 158                 cxx_allocator().Delete( p );
 159             }
 160         };
 161         typedef std::unique_ptr<value_type, value_deleter> scoped_ptr;
 162         //@endcond
 163
 164     public:
 165         /// Constructs empty priority queue
 166         /**
 167             For \p cds::opt::v::initialized_static_buffer the \p nCapacity parameter is ignored.
 168         */
 169         MSPriorityQueue( size_t nCapacity )
 170             : base_class( nCapacity )
 171         {}
 172
 173         /// Clears priority queue and destructs the object
 174         ~MSPriorityQueue()
 175         {
 176             clear();
 177         }
 178
 179         /// Inserts an item into priority queue
 180         /**
 181             If the priority queue is full, the function returns \p false,
 182             no item has been added.
 183             Otherwise, the function inserts the copy of \p val into the heap
 184             and returns \p true.
 185
 186             The function use copy constructor to create new heap item from \p val.
 187         */
 188         bool push( value_type const& val )
 189         {
 190             scoped_ptr pVal( cxx_allocator().New( val ));
 191             if ( base_class::push( *(pVal.get()) )) {
 192                 pVal.release();
 193                 return true;
 194             }
 195             return false;
 196         }
 197
 198         /// Inserts an item into the queue using a functor
 199         /**
 200             \p Func is a functor called to create node.
 201             The functor \p f takes one argument - a reference to a new node of type \ref value_type :
 202             \code
 203             cds::container::MSPriorityQueue< Foo > myQueue;
 204             Bar bar;
 205             myQueue.push_with( [&bar]( Foo& dest ) { dest = bar; } );
 206             \endcode
 207         */
 208         template <typename Func>
 209         bool push_with( Func f )
 210         {
 211             scoped_ptr pVal( cxx_allocator().New() );
 212             f( *pVal );
 213             if ( base_class::push( *pVal )) {
 214                 pVal.release();
 215                 return true;
 216             }
 217             return false;
 218         }
 219
 220         /// Inserts a item into priority queue
 221         /**
 222             If the priority queue is full, the function returns \p false,
 223             no item has been added.
 224             Otherwise, the function inserts a new item created from \p args arguments
 225             into the heap and returns \p true.
 226         */
 227         template <typename... Args>
 228         bool emplace( Args&&... args )
 229         {
 230             scoped_ptr pVal( cxx_allocator().MoveNew( std::forward<Args>(args)... ));
 231             if ( base_class::push( *(pVal.get()) )) {
 232                 pVal.release();
 233                 return true;
 234             }
 235             return false;
 236         }
 237
 238         /// Extracts item with high priority
 239         /**
 240             If the priority queue is empty, the function returns \p false.
 241             Otherwise, it returns \p true and \p dest contains the copy of extracted item.
 242             The item is deleted from the heap.
 243
 244             The function uses \ref move_policy to move extracted value from the heap's top
 245             to \p dest.
 246
 247             The function is equivalent of such call:
 248             \code
 249                 pop_with( dest, [&dest]( value_type& src ) { move_policy()(dest, src); } );
 250             \endcode
 251         */
 252         bool pop( value_type& dest )
 253         {
 254             return pop_with( [&dest]( value_type& src ) { move_policy()(dest, std::move(src)); });
 255         }
 256
 257         /// Extracts an item with high priority
 258         /**
 259             If the priority queue is empty, the function returns \p false.
 260             Otherwise, it returns \p true and \p dest contains the copy of extracted item.
 261             The item is deleted from the heap.
 262
 263             \p Func is a functor called to copy popped value.
 264             The functor takes one argument - a reference to removed node:
 265             \code
 266             cds:container::MSPriorityQueue< Foo > myQueue;
 267             Bar bar;
 268             myQueue.pop_with( [&bar]( Foo& src ) { bar = std::move( src );});
 269             \endcode
 270         */
 271         template <typename Func>
 272         bool pop_with( Func f )
 273         {
 274             value_type * pVal = base_class::pop();
 275             if ( pVal ) {
 276                 f( *pVal );
 277                 cxx_allocator().Delete( pVal );
 278                 return true;
 279             }
 280             return false;
 281         }
 282
 283         /// Clears the queue (not atomic)
 284         /**
 285             This function is not atomic, but thread-safe
 286         */
 287         void clear()
 288         {
 289             base_class::clear_with( []( value_type& src ) { value_deleter()(&src); } );
 290         }
 291
 292         /// Clears the queue (not atomic)
 293         /**
 294             This function is not atomic, but thread-safe.
 295
 296             For each item removed the functor \p f is called.
 297             \p Func interface is:
 298             \code
 299                 struct clear_functor
 300                 {
 301                     void operator()( value_type& item );
 302                 };
 303             \endcode
 304         */
 305         template <typename Func>
 306         void clear_with( Func f )
 307         {
 308             base_class::clear_with( [&f]( value_type& val ) { f(val); value_deleter()( &val ); } );
 309         }
 310
 311         /// Checks is the priority queue is empty
 312         bool empty() const
 313         {
 314             return base_class::empty();
 315         }
 316
 317         /// Checks if the priority queue is full
 318         bool full() const
 319         {
 320             return base_class::full();
 321         }
 322
 323         /// Returns current size of priority queue
 324         size_t size() const
 325         {
 326             return base_class::size();
 327         }
 328
 329         /// Return capacity of the priority queue
 330         size_t capacity() const
 331         {
 332             return base_class::capacity();
 333         }
 334
 335         /// Returns const reference to internal statistics
 336         stat const& statistics() const
 337         {
 338             return base_class::statistics();
 339         }
 340     };
 341
 342 }} // namespace cds::container
 343
 344 #endif // #ifndef CDSLIB_CONTAINER_MSPRIORITY_QUEUE_H