cds/container/michael_deque.h

   1 //$$CDS-header$$
   2
   3 #ifndef __CDS_CONTAINER_MICHAEL_DEQUE_H
   4 #define __CDS_CONTAINER_MICHAEL_DEQUE_H
   5
   6 #include <cds/intrusive/michael_deque.h>
   7 #include <cds/details/trivial_assign.h>
   8 #include <cds/details/std/memory.h>
   9
  10 namespace cds { namespace container {
  11
  12     //@cond
  13     namespace details {
  14         template <typename GC, typename T, CDS_DECL_OPTIONS7>
  15         struct make_michael_deque
  16         {
  17             typedef GC gc;
  18             typedef T   value_type;
  19
  20             struct default_options
  21             {
  22                 typedef cds::backoff::empty                         back_off;
  23                 typedef cds::atomicity::empty_item_counter          item_counter;
  24                 typedef cds::intrusive::michael_deque::dummy_stat   stat;
  25                 typedef cds::opt::v::relaxed_ordering               memory_model;
  26                 enum { alignment = cds::opt::cache_line_alignment };
  27                 typedef CDS_DEFAULT_ALLOCATOR           allocator;
  28             };
  29
  30             typedef typename cds::opt::make_options<
  31                 typename cds::opt::find_type_traits< default_options, CDS_OPTIONS7 >::type
  32                 ,CDS_OPTIONS7
  33             >::type   options;
  34
  35             struct node_type : public cds::intrusive::michael_deque::node< gc >
  36             {
  37                 value_type  m_value;
  38                 node_type()
  39                 {}
  40                 node_type(const value_type& val)
  41                     : m_value( val )
  42                 {}
  43 #       ifdef CDS_EMPLACE_SUPPORT
  44                 template <typename... Args>
  45                 node_type( Args&&... args )
  46                     : m_value( std::forward<Args>(args)...)
  47                 {}
  48 #       endif
  49             };
  50
  51             typedef typename options::allocator::template rebind<node_type>::other allocator_type;
  52             typedef cds::details::Allocator< node_type, allocator_type >           cxx_allocator;
  53
  54             struct node_deallocator
  55             {
  56                 void operator ()( node_type * pNode )
  57                 {
  58                     cxx_allocator().Delete( pNode );
  59                 }
  60             };
  61
  62             typedef cds::intrusive::MichaelDeque< gc,
  63                 node_type
  64                 ,cds::intrusive::opt::hook<
  65                     cds::intrusive::michael_deque::base_hook< cds::opt::gc<gc> >
  66                 >
  67                 ,cds::opt::back_off< typename options::back_off >
  68                 ,cds::intrusive::opt::disposer< node_deallocator >
  69                 ,cds::opt::item_counter< typename options::item_counter >
  70                 ,cds::opt::stat< typename options::stat >
  71                 ,cds::opt::alignment< options::alignment >
  72                 ,cds::opt::memory_model< typename options::memory_model >
  73             > type;
  74         };
  75     }
  76     //@endcond
  77
  78     /// Michael's deque
  79     /** @ingroup cds_nonintrusive_deque
  80
  81         Implementation of Michael's deque algorithm.
  82
  83         \par Source:
  84             [2003] Maged Michael "CAS-based Lock-free Algorithm for Shared Deque"
  85
  86         <b>Short description</b> (from Michael's paper)
  87
  88             The deque is represented as a doubly-linked list. Each node in the list contains two link pointers,
  89             \p pRight and \p pLeft, and a data field. A shared variable, \p Anchor, holds the two anchor
  90             pointers to the leftmost and rightmost nodes in the list, if any, and a three-value
  91             status tag. Anchor must fit in a memory block that can be read and manipulated
  92             using CAS or LL/SC, atomically. Initially both anchor pointers have null values
  93             and the status tag holds the value stable, indicating an empty deque.
  94
  95             The status tag serves to indicate if the deque is in an unstable state. When
  96             a process finds the deque in an unstable state, it must first attempt to take it
  97             to a stable state before attempting its own operation.
  98
  99             The algorithm can use 64bit CAS. Instead of a pointer the node contains two
 100             31bit link indices + one bit for status tag;
 101             this trick allows use 64bit CAS to manipulate \p Anchor. Internal mapper
 102             (based on intrusive::MichaelHashSet intrusive container)
 103             reflects link indices to item pointers. The maximum number of item in
 104             the deque is limited by <tt>2**31 - 1</tt> that is practically unbounded.
 105
 106         Template arguments:
 107         - \p GC - garbage collector type: gc::HP, gc::PTB. Note that gc::HRC is <b>NOT</b> supported for this container.
 108         - \p T is a type stored in the queue. It should be default-constructible, copy-constructible, assignable type.
 109         - \p Options - options
 110
 111         Permissible \p Options:
 112         - opt::allocator - allocator (like \p std::allocator). Default is \ref CDS_DEFAULT_ALLOCATOR.
 113             Used for item allocation.
 114         - opt::back_off - back-off strategy used. If the option is not specified, the cds::backoff::empty is used
 115         - opt::item_counter - the type of item counting feature. Default is \ref atomicity::empty_item_counter that means no item counting feature
 116         - opt::stat - the type to gather internal statistics.
 117             Possible option value are: \ref intrusive::michael_deque::stat, \ref intrusive::michael_deque::dummy_stat,
 118             user-provided class that supports intrusive::michael_deque::stat interface.
 119             Default is \ref intrusive::michael_deque::dummy_stat.
 120         - opt::alignment - the alignment for internal deque data. Default is opt::cache_line_alignment
 121         - opt::memory_model - C++ memory ordering model. Can be opt::v::relaxed_ordering (relaxed memory model, the default)
 122             or opt::v::sequential_consistent (sequentially consisnent memory model).
 123     */
 124     template <typename GC, typename T, CDS_DECL_OPTIONS7>
 125     class MichaelDeque:
 126 #ifdef CDS_DOXYGEN_INVOKED
 127         intrusive::MichaelDeque< GC, intrusive::michael_deque::node< T >, Options... >
 128 #else
 129         details::make_michael_deque< GC, T, CDS_OPTIONS7 >::type
 130 #endif
 131     {
 132         //@cond
 133         typedef details::make_michael_deque< GC, T, CDS_OPTIONS7 > options;
 134         typedef typename options::type base_class;
 135         //@endcond
 136
 137     public:
 138         /// Rebind template arguments
 139         template <typename GC2, typename T2, CDS_DECL_OTHER_OPTIONS7>
 140         struct rebind {
 141             typedef MichaelDeque< GC2, T2, CDS_OTHER_OPTIONS7> other   ;   ///< Rebinding result
 142         };
 143
 144     public:
 145         typedef T value_type ; ///< Value type stored in the deque
 146
 147         typedef typename base_class::gc                 gc              ; ///< Garbage collector used
 148         typedef typename base_class::back_off           back_off        ; ///< Back-off strategy used
 149         typedef typename options::allocator_type        allocator_type  ; ///< Allocator type used for allocate/deallocate the nodes
 150         typedef typename options::options::item_counter item_counter    ; ///< Item counting policy used
 151         typedef typename options::options::stat         stat            ; ///< Internal statistics policy used
 152         typedef typename base_class::memory_model       memory_model    ; ///< Memory ordering. See cds::opt::memory_model option
 153
 154     protected:
 155         typedef typename options::node_type  node_type   ;   ///< queue node type (derived from intrusive::single_link::node)
 156
 157         //@cond
 158         typedef typename options::cxx_allocator     cxx_allocator;
 159         typedef typename options::node_deallocator  node_deallocator;   // deallocate node
 160         typedef typename base_class::node_traits    node_traits;
 161         //@endcond
 162
 163     protected:
 164         ///@cond
 165         static node_type * alloc_node()
 166         {
 167             return cxx_allocator().New();
 168         }
 169         static node_type * alloc_node( const value_type& val )
 170         {
 171             return cxx_allocator().New( val );
 172         }
 173 #   ifdef CDS_EMPLACE_SUPPORT
 174         template <typename... Args>
 175         static node_type * alloc_node( Args&&... args )
 176         {
 177             return cxx_allocator().MoveNew( std::forward<Args>(args)... );
 178         }
 179 #   endif
 180         static void free_node( node_type * p )
 181         {
 182             node_deallocator()( p );
 183         }
 184
 185         struct node_disposer {
 186             void operator()( node_type * pNode )
 187             {
 188                 free_node( pNode );
 189             }
 190         };
 191         typedef std::unique_ptr< node_type, node_disposer >     scoped_node_ptr;
 192
 193         bool push_node_back( node_type * pNode )
 194         {
 195             assert( pNode != nullptr );
 196             scoped_node_ptr p(pNode);
 197
 198             if ( base_class::push_back( *pNode ) ) {
 199                 p.release();
 200                 return true;
 201             }
 202             return false;
 203         }
 204
 205         bool push_node_front( node_type * pNode )
 206         {
 207             assert( pNode != nullptr );
 208             scoped_node_ptr p(pNode);
 209
 210             if ( base_class::push_front( *pNode ) ) {
 211                 p.release();
 212                 return true;
 213             }
 214             return false;
 215         }
 216         //@endcond
 217
 218     public:
 219         /// Default constructor
 220         /**
 221             Initializes the deque object that can contain up to <tt>2**16 - 1</tt> items
 222         */
 223         MichaelDeque()
 224         {}
 225
 226         /// Constructor
 227         /**
 228             Initializes the deque object with estimated item count \p nMaxItemCount.
 229             \p nLoadFactor is a parameter of internal memory mapper based on intrusive::MichaelHashSet;
 230             see MichaelHashSet ctor for details
 231         */
 232         MichaelDeque( unsigned int nMaxItemCount, unsigned int nLoadFactor = 4 )
 233             : base_class( nMaxItemCount, nLoadFactor )
 234             {}
 235
 236         /// Destructor clears the deque
 237         ~MichaelDeque()
 238         {}
 239
 240     public:
 241         /// Push back (right) side
 242         /**
 243             Push new item \p val to right side of the deque.
 244         */
 245         bool push_back( value_type const& val )
 246         {
 247             return push_node_back( alloc_node( val ));
 248         }
 249
 250         /// Push back (right) side using copy functor
 251         /**
 252             \p Func is a functor called to copy value \p data of type \p Type
 253             which may be differ from type \p T stored in the deque.
 254             The functor's interface is:
 255             \code
 256             struct myFunctor {
 257                 void operator()(T& dest, Type const& data)
 258                 {
 259                     // Code to copy \p data to \p dest
 260                     dest = data;
 261                 }
 262             };
 263             \endcode
 264             You may use \p boost:ref construction to pass functor \p f by reference.
 265
 266             <b>Requirements</b> The functor \p Func should not throw any exception.
 267         */
 268         template <typename Type, typename Func>
 269         bool push_back( Type const& val, Func f )
 270         {
 271             scoped_node_ptr p( alloc_node());
 272             unref(f)( p->m_value, val );
 273             if ( base_class::push_back( *p )) {
 274                 p.release();
 275                 return true;
 276             }
 277             return false;
 278         }
 279
 280 #   ifdef CDS_EMPLACE_SUPPORT
 281         /// Push back (right side) data of type \ref value_type constructed with <tt>std::forward<Args>(args)...</tt>
 282         /**
 283             Returns \p true if the oprration successful, \p false otherwise.
 284
 285             This function is available only for compiler that supports
 286             variadic template and move semantics
 287         */
 288         template <typename... Args>
 289         bool emplace_back( Args&&... args )
 290         {
 291             return push_node_back( alloc_node( std::forward<Args>(args)... ));
 292         }
 293 #   endif
 294
 295         /// Push front (left) side
 296         /**
 297             Push new item \p val to left side of the deque.
 298         */
 299         bool push_front( value_type const& val )
 300         {
 301             return push_node_front( alloc_node( val ));
 302         }
 303
 304         /// Push front side using copy functor
 305         /**
 306             \p Func is a functor called to copy value \p data of type \p Type
 307             which may be differ from type \p T stored in the deque.
 308             The functor's interface is:
 309             \code
 310             struct myFunctor {
 311                 void operator()(T& dest, Type const& data)
 312                 {
 313                     // Code to copy \p data to \p dest
 314                     dest = data;
 315                 }
 316             };
 317             \endcode
 318             You may use \p boost:ref construction to pass functor \p f by reference.
 319
 320             <b>Requirements</b> The functor \p Func should not throw any exception.
 321         */
 322         template <typename Type, typename Func>
 323         bool push_front( Type const& val, Func f )
 324         {
 325             scoped_node_ptr p( alloc_node());
 326             unref(f)( p->m_value, val );
 327             if ( base_class::push_front( *p )) {
 328                 p.release();
 329                 return true;
 330             }
 331             return false;
 332         }
 333
 334 #   ifdef CDS_EMPLACE_SUPPORT
 335         /// Push front (left side) data of type \ref value_type constructed with <tt>std::forward<Args>(args)...</tt>
 336         /**
 337             Returns \p true if the operation successful, \p false otherwise.
 338
 339             This function is available only for compiler that supports
 340             variadic template and move semantics
 341         */
 342         template <typename... Args>
 343         bool emplace_front( Args&&... args )
 344         {
 345             return push_node_front( alloc_node( std::forward<Args>(args)... ));
 346         }
 347 #   endif
 348
 349         /// Pops back side, no return value
 350         /**
 351             The function returns \p true if the deque has not been empty (in other words, an item has been popped),
 352             otherwise the function returns \p false.
 353         */
 354         bool pop_back()
 355         {
 356             return base_class::pop_back() != nullptr;
 357         }
 358
 359         /// Pops back side a value using copy functor
 360         /**
 361             \p Func is a functor called to copy value popped to \p dest of type \p Type
 362             which may be differ from type \p T stored in the deque.
 363             The functor's interface is:
 364             \code
 365             struct myFunctor {
 366                 void operator()(Type& dest, T const& data)
 367                 {
 368                     // Code to copy \p data to \p dest
 369                     dest = data;
 370                 }
 371             };
 372             \endcode
 373             You may use \p boost:ref construction to pass functor \p f by reference.
 374
 375             <b>Requirements</b> The functor \p Func should not throw any exception.
 376         */
 377         template <typename Type, typename Func>
 378         bool pop_back( Type& dest, Func f )
 379         {
 380             typename base_class::pop_result res;
 381             if ( base_class::do_pop_back( res )) {
 382                 unref(f)( dest, node_traits::to_value_ptr( res.pPopped )->m_value );
 383                 base_class::dispose_result( res );
 384                 return true;
 385             }
 386             return false;
 387         }
 388
 389
 390         /// Pops back side, store value popped into \p dest
 391         /**
 392             If deque is not empty, the function returns \p true, \p dest contains copy of
 393             value popped. The assignment operator for type \ref value_type is invoked.
 394             If deque is empty, the function returns \p false, \p dest is unchanged.
 395         */
 396         bool pop_back( value_type& dest )
 397         {
 398             typedef cds::details::trivial_assign<value_type, value_type> functor;
 399             return pop_back( dest, functor() );
 400         }
 401
 402         /// Pops front side, no return value
 403         /**
 404             The function returns \p true if the deque has not been empty (in other words, an item has been popped),
 405             otherwise the function returns \p false.
 406         */
 407         bool pop_front()
 408         {
 409             return base_class::pop_front() != nullptr;
 410         }
 411
 412         /// Pops front side a value using copy functor
 413         /**
 414             \p Func is a functor called to copy value popped to \p dest of type \p Type
 415             which may be differ from type \p T stored in the deque.
 416             The functor's interface is:
 417             \code
 418             struct myFunctor {
 419                 void operator()(Type& dest, T const& data)
 420                 {
 421                     // Code to copy \p data to \p dest
 422                     dest = data;
 423                 }
 424             };
 425             \endcode
 426             You may use \p boost:ref construction to pass functor \p f by reference.
 427
 428             <b>Requirements</b> The functor \p Func should not throw any exception.
 429         */
 430         template <typename Type, typename Func>
 431         bool pop_front( Type& dest, Func f )
 432         {
 433             typename base_class::pop_result res;
 434             if ( base_class::do_pop_front( res )) {
 435                 unref(f)( dest, node_traits::to_value_ptr( res.pPopped )->m_value );
 436                 base_class::dispose_result( res );
 437                 return true;
 438             }
 439             return false;
 440         }
 441
 442
 443         /// Pops front side, store value popped into \p dest
 444         /**
 445             If deque is not empty, the function returns \p true, \p dest contains copy of
 446             value popped. The assignment operator for type \ref value_type is invoked.
 447             If deque is empty, the function returns \p false, \p dest is unchanged.
 448         */
 449         bool pop_front( value_type& dest )
 450         {
 451             typedef cds::details::trivial_assign<value_type, value_type> functor;
 452             return pop_front( dest, functor() );
 453         }
 454
 455         /// Returns deque's item count
 456         /**
 457             The value returned depends on opt::item_counter option. For atomicity::empty_item_counter,
 458             this function always returns 0.
 459
 460             <b>Warning</b>: even if you use real item counter and it returns 0, this fact does not mean that the deque
 461             is empty. To check deque emptyness use \ref empty() method.
 462         */
 463         size_t size() const
 464         {
 465             return base_class::size();
 466         }
 467
 468         /// Checks if the dequeue is empty
 469         bool empty() const
 470         {
 471             return base_class::empty();
 472         }
 473
 474         /// Clear the deque
 475         /**
 476             The function repeatedly calls \ref pop_back until it returns \p NULL.
 477         */
 478         void clear()
 479         {
 480             return base_class::clear();
 481         }
 482
 483         /// Returns reference to internal statistics
 484         const stat& statistics() const
 485         {
 486             return base_class::statistics();
 487         }
 488     };
 489
 490 }}  // namespace cds::container
 491
 492
 493 #endif // #ifndef __CDS_CONTAINER_MICHAEL_DEQUE_H