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 #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 traits::stat          stat;        ///< internal statistics type, see \p intrusive::mspriority_queue::traits::stat
 148         typedef typename base_class::item_counter  item_counter;///< Item counter type
 149         typedef typename traits::allocator::template rebind<value_type>::other allocator_type; ///< Value allocator
 150         typedef typename traits::move_policy   move_policy; ///< Move policy for type \p T
 151
 152     protected:
 153         //@cond
 154         typedef cds::details::Allocator< value_type, allocator_type >  cxx_allocator;
 155
 156         struct value_deleter {
 157             void operator()( value_type * p ) const
 158             {
 159                 cxx_allocator().Delete( p );
 160             }
 161         };
 162         typedef std::unique_ptr<value_type, value_deleter> scoped_ptr;
 163         //@endcond
 164
 165     public:
 166         /// Constructs empty priority queue
 167         /**
 168             For \p cds::opt::v::initialized_static_buffer the \p nCapacity parameter is ignored.
 169         */
 170         MSPriorityQueue( size_t nCapacity )
 171             : base_class( nCapacity )
 172         {}
 173
 174         /// Clears priority queue and destructs the object
 175         ~MSPriorityQueue()
 176         {
 177             clear();
 178         }
 179
 180         /// Inserts an item into priority queue
 181         /**
 182             If the priority queue is full, the function returns \p false,
 183             no item has been added.
 184             Otherwise, the function inserts the copy of \p val into the heap
 185             and returns \p true.
 186
 187             The function use copy constructor to create new heap item from \p val.
 188         */
 189         bool push( value_type const& val )
 190         {
 191             scoped_ptr pVal( cxx_allocator().New( val ));
 192             if ( base_class::push( *(pVal.get()))) {
 193                 pVal.release();
 194                 return true;
 195             }
 196             return false;
 197         }
 198
 199         /// Inserts an item into the queue using a functor
 200         /**
 201             \p Func is a functor called to create node.
 202             The functor \p f takes one argument - a reference to a new node of type \ref value_type :
 203             \code
 204             cds::container::MSPriorityQueue< Foo > myQueue;
 205             Bar bar;
 206             myQueue.push_with( [&bar]( Foo& dest ) { dest = bar; } );
 207             \endcode
 208         */
 209         template <typename Func>
 210         bool push_with( Func f )
 211         {
 212             scoped_ptr pVal( cxx_allocator().New());
 213             f( *pVal );
 214             if ( base_class::push( *pVal )) {
 215                 pVal.release();
 216                 return true;
 217             }
 218             return false;
 219         }
 220
 221         /// Inserts a item into priority queue
 222         /**
 223             If the priority queue is full, the function returns \p false,
 224             no item has been added.
 225             Otherwise, the function inserts a new item created from \p args arguments
 226             into the heap and returns \p true.
 227         */
 228         template <typename... Args>
 229         bool emplace( Args&&... args )
 230         {
 231             scoped_ptr pVal( cxx_allocator().MoveNew( std::forward<Args>(args)... ));
 232             if ( base_class::push( *(pVal.get()))) {
 233                 pVal.release();
 234                 return true;
 235             }
 236             return false;
 237         }
 238
 239         /// Extracts item with high priority
 240         /**
 241             If the priority queue is empty, the function returns \p false.
 242             Otherwise, it returns \p true and \p dest contains the copy of extracted item.
 243             The item is deleted from the heap.
 244
 245             The function uses \ref move_policy to move extracted value from the heap's top
 246             to \p dest.
 247
 248             The function is equivalent of such call:
 249             \code
 250                 pop_with( dest, [&dest]( value_type& src ) { move_policy()(dest, src); } );
 251             \endcode
 252         */
 253         bool pop( value_type& dest )
 254         {
 255             return pop_with( [&dest]( value_type& src ) { move_policy()(dest, std::move(src)); });
 256         }
 257
 258         /// Extracts an item with high priority
 259         /**
 260             If the priority queue is empty, the function returns \p false.
 261             Otherwise, it returns \p true and \p dest contains the copy of extracted item.
 262             The item is deleted from the heap.
 263
 264             \p Func is a functor called to copy popped value.
 265             The functor takes one argument - a reference to removed node:
 266             \code
 267             cds:container::MSPriorityQueue< Foo > myQueue;
 268             Bar bar;
 269             myQueue.pop_with( [&bar]( Foo& src ) { bar = std::move( src );});
 270             \endcode
 271         */
 272         template <typename Func>
 273         bool pop_with( Func f )
 274         {
 275             value_type * pVal = base_class::pop();
 276             if ( pVal ) {
 277                 f( *pVal );
 278                 cxx_allocator().Delete( pVal );
 279                 return true;
 280             }
 281             return false;
 282         }
 283
 284         /// Clears the queue (not atomic)
 285         /**
 286             This function is not atomic, but thread-safe
 287         */
 288         void clear()
 289         {
 290             base_class::clear_with( []( value_type& src ) { value_deleter()(&src); } );
 291         }
 292
 293         /// Clears the queue (not atomic)
 294         /**
 295             This function is not atomic, but thread-safe.
 296
 297             For each item removed the functor \p f is called.
 298             \p Func interface is:
 299             \code
 300                 struct clear_functor
 301                 {
 302                     void operator()( value_type& item );
 303                 };
 304             \endcode
 305         */
 306         template <typename Func>
 307         void clear_with( Func f )
 308         {
 309             base_class::clear_with( [&f]( value_type& val ) { f(val); value_deleter()( &val ); } );
 310         }
 311
 312         /// Checks is the priority queue is empty
 313         bool empty() const
 314         {
 315             return base_class::empty();
 316         }
 317
 318         /// Checks if the priority queue is full
 319         bool full() const
 320         {
 321             return base_class::full();
 322         }
 323
 324         /// Returns current size of priority queue
 325         size_t size() const
 326         {
 327             return base_class::size();
 328         }
 329
 330         /// Return capacity of the priority queue
 331         size_t capacity() const
 332         {
 333             return base_class::capacity();
 334         }
 335
 336         /// Returns const reference to internal statistics
 337         stat const& statistics() const
 338         {
 339             return base_class::statistics();
 340         }
 341     };
 342
 343 }} // namespace cds::container
 344
 345 #endif // #ifndef CDSLIB_CONTAINER_MSPRIORITY_QUEUE_H