cds/container/fcdeque.h

   1 //$$CDS-header$$
   2
   3 #ifndef __CDS_CONTAINER_FCDEQUE_H
   4 #define __CDS_CONTAINER_FCDEQUE_H
   5
   6 #include <cds/algo/flat_combining.h>
   7 #include <cds/algo/elimination_opt.h>
   8 #include <deque>
   9
  10 namespace cds { namespace container {
  11
  12     /// FCDeque related definitions
  13     /** @ingroup cds_nonintrusive_helper
  14     */
  15     namespace fcdeque {
  16
  17         /// FCDeque internal statistics
  18         template <typename Counter = cds::atomicity::event_counter >
  19         struct stat: public cds::algo::flat_combining::stat<Counter>
  20         {
  21             typedef cds::algo::flat_combining::stat<Counter>    flat_combining_stat; ///< Flat-combining statistics
  22             typedef typename flat_combining_stat::counter_type  counter_type;        ///< Counter type
  23
  24             counter_type    m_nPushFront     ;  ///< Count of push_front operations
  25             counter_type    m_nPushFrontMove ;  ///< Count of push_front operations with move semantics
  26             counter_type    m_nPushBack      ;  ///< Count of push_back operations
  27             counter_type    m_nPushBackMove  ;  ///< Count of push_back operations with move semantics
  28             counter_type    m_nPopFront      ;  ///< Count of success pop_front operations
  29             counter_type    m_nFailedPopFront;  ///< Count of failed pop_front operations (pop from empty deque)
  30             counter_type    m_nPopBack       ;  ///< Count of success pop_back operations
  31             counter_type    m_nFailedPopBack ;  ///< Count of failed pop_back operations (pop from empty deque)
  32             counter_type    m_nCollided      ;  ///< How many pairs of push/pop were collided, if elimination is enabled
  33
  34             //@cond
  35             void    onPushFront()             { ++m_nPushFront; }
  36             void    onPushFrontMove()         { ++m_nPushFrontMove; }
  37             void    onPushBack()              { ++m_nPushBack; }
  38             void    onPushBackMove()          { ++m_nPushBackMove; }
  39             void    onPopFront( bool bFailed ) { if ( bFailed ) ++m_nFailedPopFront; else ++m_nPopFront;  }
  40             void    onPopBack( bool bFailed ) { if ( bFailed ) ++m_nFailedPopBack; else ++m_nPopBack;  }
  41             void    onCollide()               { ++m_nCollided; }
  42             //@endcond
  43         };
  44
  45         /// FCDeque dummy statistics, no overhead
  46         struct empty_stat: public cds::algo::flat_combining::empty_stat
  47         {
  48             //@cond
  49             void    onPushFront()       {}
  50             void    onPushFrontMove()   {}
  51             void    onPushBack()        {}
  52             void    onPushBackMove()    {}
  53             void    onPopFront(bool)    {}
  54             void    onPopBack(bool)     {}
  55             void    onCollide()         {}
  56             //@endcond
  57         };
  58
  59         /// FCDeque type traits
  60         struct type_traits: public cds::algo::flat_combining::type_traits
  61         {
  62             typedef empty_stat      stat;   ///< Internal statistics
  63             static CDS_CONSTEXPR_CONST bool enable_elimination = false; ///< Enable \ref cds_elimination_description "elimination"
  64         };
  65
  66         /// Metafunction converting option list to traits
  67         /**
  68             This is a wrapper for <tt> cds::opt::make_options< type_traits, Options...> </tt>
  69             \p Options are:
  70             - \p opt::lock_type - mutex type, default is \p cds::lock::Spin
  71             - \p opt::back_off - back-off strategy, defalt is \p cds::backoff::Default
  72             - \p opt::allocator - allocator type, default is \ref CDS_DEFAULT_ALLOCATOR
  73             - \p opt::stat - internal statistics, possible type: \ref stat, \ref empty_stat (the default)
  74             - \p opt::memory_model - C++ memory ordering model.
  75                 List of all available memory ordering see opt::memory_model.
  76                 Default if cds::opt::v:relaxed_ordering
  77             - \p opt::enable_elimination - enable/disable operation \ref cds_elimination_description "elimination"
  78                 By default, the elimination is disabled. For queue, the elimination is possible if the queue
  79                 is empty.
  80         */
  81         template <CDS_DECL_OPTIONS8>
  82         struct make_traits {
  83 #   ifdef CDS_DOXYGEN_INVOKED
  84             typedef implementation_defined type ;   ///< Metafunction result
  85 #   else
  86             typedef typename cds::opt::make_options<
  87                 typename cds::opt::find_type_traits< type_traits, CDS_OPTIONS8 >::type
  88                 ,CDS_OPTIONS8
  89             >::type   type;
  90 #   endif
  91         };
  92
  93     } // namespace fcqueue
  94
  95     /// Flat-combining deque
  96     /**
  97         @ingroup cds_nonintrusive_deque
  98         @ingroup cds_flat_combining_container
  99
 100         \ref cds_flat_combining_description "Flat combining" sequential deque.
 101         The class can be considered as a concurrent FC-based wrapper for \p std::deque.
 102
 103         Template parameters:
 104         - \p T - a value type stored in the deque
 105         - \p Deque - sequential deque implementation, for example, \p std::deque<T> (the default)
 106             or \p boost::container::deque
 107         - \p Trats - type traits of flat combining, default is \p fcdeque::type_traits.
 108             \p fcdeque::make_traits metafunction can be used to construct specialized \p %type_traits
 109     */
 110     template <typename T,
 111         class Deque = std::deque<T>,
 112         typename Traits = fcdeque::type_traits
 113     >
 114     class FCDeque
 115 #ifndef CDS_DOXYGEN_INVOKED
 116         : public cds::algo::flat_combining::container
 117 #endif
 118     {
 119     public:
 120         typedef T           value_type;     ///< Value type
 121         typedef Deque       deque_type;     ///< Sequential deque class
 122         typedef Traits      type_traits;    ///< Deque type traits
 123
 124         typedef typename type_traits::stat  stat;   ///< Internal statistics type
 125         static CDS_CONSTEXPR_CONST bool c_bEliminationEnabled = type_traits::enable_elimination; ///< \p true if elimination is enabled
 126
 127     protected:
 128         //@cond
 129         /// Deque operation IDs
 130         enum fc_operation {
 131             op_push_front = cds::algo::flat_combining::req_Operation, ///< Push front
 132             op_push_front_move,     ///< Push front (move semantics)
 133             op_push_back,           ///< Push back
 134             op_push_back_move,      ///< Push back (move semantics)
 135             op_pop_front,           ///< Pop front
 136             op_pop_back,            ///< Pop back
 137             op_clear                ///< Clear
 138         };
 139
 140         /// Flat combining publication list record
 141         struct fc_record: public cds::algo::flat_combining::publication_record
 142         {
 143             union {
 144                 value_type const *  pValPush; ///< Value to push
 145                 value_type *        pValPop;  ///< Pop destination
 146             };
 147             bool            bEmpty; ///< \p true if the deque is empty
 148         };
 149         //@endcond
 150
 151         /// Flat combining kernel
 152         typedef cds::algo::flat_combining::kernel< fc_record, type_traits > fc_kernel;
 153
 154     protected:
 155         //@cond
 156         fc_kernel   m_FlatCombining;
 157         deque_type  m_Deque;
 158         //@endcond
 159
 160     public:
 161         /// Initializes empty deque object
 162         FCDeque()
 163         {}
 164
 165         /// Initializes empty deque object and gives flat combining parameters
 166         FCDeque(
 167             unsigned int nCompactFactor     ///< Flat combining: publication list compacting factor
 168             ,unsigned int nCombinePassCount ///< Flat combining: number of combining passes for combiner thread
 169             )
 170             : m_FlatCombining( nCompactFactor, nCombinePassCount )
 171         {}
 172
 173         /// Inserts a new element at the beginning of the deque container
 174         /**
 175             The function always returns \p true
 176         */
 177         bool push_front(
 178             value_type const& val ///< Value to be copied to inserted element
 179         )
 180         {
 181             fc_record * pRec = m_FlatCombining.acquire_record();
 182             pRec->pValPush = &val;
 183
 184             if ( c_bEliminationEnabled )
 185                 m_FlatCombining.batch_combine( op_push_front, pRec, *this );
 186             else
 187                 m_FlatCombining.combine( op_push_front, pRec, *this );
 188
 189             assert( pRec->is_done() );
 190             m_FlatCombining.release_record( pRec );
 191             m_FlatCombining.internal_statistics().onPushFront();
 192             return true;
 193         }
 194
 195 #   ifdef CDS_MOVE_SEMANTICS_SUPPORT
 196         /// Inserts a new element at the beginning of the deque container (move semantics)
 197         /**
 198             The function always returns \p true
 199         */
 200         bool push_front(
 201             value_type&& val ///< Value to be moved to inserted element
 202         )
 203         {
 204             fc_record * pRec = m_FlatCombining.acquire_record();
 205             pRec->pValPush = &val;
 206
 207             if ( c_bEliminationEnabled )
 208                 m_FlatCombining.batch_combine( op_push_front_move, pRec, *this );
 209             else
 210                 m_FlatCombining.combine( op_push_front_move, pRec, *this );
 211
 212             assert( pRec->is_done() );
 213             m_FlatCombining.release_record( pRec );
 214             m_FlatCombining.internal_statistics().onPushFrontMove();
 215             return true;
 216         }
 217 #   endif
 218
 219         /// Inserts a new element at the end of the deque container
 220         /**
 221             The function always returns \p true
 222         */
 223         bool push_back(
 224             value_type const& val ///< Value to be copied to inserted element
 225         )
 226         {
 227             fc_record * pRec = m_FlatCombining.acquire_record();
 228             pRec->pValPush = &val;
 229
 230             if ( c_bEliminationEnabled )
 231                 m_FlatCombining.batch_combine( op_push_back, pRec, *this );
 232             else
 233                 m_FlatCombining.combine( op_push_back, pRec, *this );
 234
 235             assert( pRec->is_done() );
 236             m_FlatCombining.release_record( pRec );
 237             m_FlatCombining.internal_statistics().onPushBack();
 238             return true;
 239         }
 240
 241 #   ifdef CDS_MOVE_SEMANTICS_SUPPORT
 242         /// Inserts a new element at the end of the deque container (move semantics)
 243         /**
 244             The function always returns \p true
 245         */
 246         bool push_back(
 247             value_type&& val ///< Value to be moved to inserted element
 248         )
 249         {
 250             fc_record * pRec = m_FlatCombining.acquire_record();
 251             pRec->pValPush = &val;
 252
 253             if ( c_bEliminationEnabled )
 254                 m_FlatCombining.batch_combine( op_push_back_move, pRec, *this );
 255             else
 256                 m_FlatCombining.combine( op_push_back_move, pRec, *this );
 257
 258             assert( pRec->is_done() );
 259             m_FlatCombining.release_record( pRec );
 260             m_FlatCombining.internal_statistics().onPushBackMove();
 261             return true;
 262         }
 263 #   endif
 264
 265         /// Removes the first element in the deque container
 266         /**
 267             The function returns \p false if the deque is empty, \p true otherwise.
 268             If the deque is empty \p val is not changed.
 269         */
 270         bool pop_front(
 271             value_type& val ///< Target to be received the copy of removed element
 272         )
 273         {
 274             fc_record * pRec = m_FlatCombining.acquire_record();
 275             pRec->pValPop = &val;
 276
 277             if ( c_bEliminationEnabled )
 278                 m_FlatCombining.batch_combine( op_pop_front, pRec, *this );
 279             else
 280                 m_FlatCombining.combine( op_pop_front, pRec, *this );
 281
 282             assert( pRec->is_done() );
 283             m_FlatCombining.release_record( pRec );
 284             m_FlatCombining.internal_statistics().onPopFront( pRec->bEmpty );
 285             return !pRec->bEmpty;
 286         }
 287
 288         /// Removes the last element in the deque container
 289         /**
 290             The function returns \p false if the deque is empty, \p true otherwise.
 291             If the deque is empty \p val is not changed.
 292         */
 293         bool pop_back(
 294             value_type& val ///< Target to be received the copy of removed element
 295         )
 296         {
 297             fc_record * pRec = m_FlatCombining.acquire_record();
 298             pRec->pValPop = &val;
 299
 300             if ( c_bEliminationEnabled )
 301                 m_FlatCombining.batch_combine( op_pop_back, pRec, *this );
 302             else
 303                 m_FlatCombining.combine( op_pop_back, pRec, *this );
 304
 305             assert( pRec->is_done() );
 306             m_FlatCombining.release_record( pRec );
 307             m_FlatCombining.internal_statistics().onPopBack( pRec->bEmpty );
 308             return !pRec->bEmpty;
 309         }
 310
 311         /// Clears the deque
 312         void clear()
 313         {
 314             fc_record * pRec = m_FlatCombining.acquire_record();
 315
 316             if ( c_bEliminationEnabled )
 317                 m_FlatCombining.batch_combine( op_clear, pRec, *this );
 318             else
 319                 m_FlatCombining.combine( op_clear, pRec, *this );
 320
 321             assert( pRec->is_done() );
 322             m_FlatCombining.release_record( pRec );
 323         }
 324
 325         /// Returns the number of elements in the deque.
 326         /**
 327             Note that <tt>size() == 0</tt> is not mean that the deque is empty because
 328             combining record can be in process.
 329             To check emptiness use \ref empty function.
 330         */
 331         size_t size() const
 332         {
 333             return m_Deque.size();
 334         }
 335
 336         /// Checks if the deque is empty
 337         /**
 338             If the combining is in process the function waits while combining done.
 339         */
 340         bool empty() const
 341         {
 342             m_FlatCombining.wait_while_combining();
 343             return m_Deque.empty();
 344         }
 345
 346         /// Internal statistics
 347         stat const& statistics() const
 348         {
 349             return m_FlatCombining.statistics();
 350         }
 351
 352     public: // flat combining cooperation, not for direct use!
 353         //@cond
 354         /// Flat combining supporting function. Do not call it directly!
 355         /**
 356             The function is called by \ref cds::algo::flat_combining::kernel "flat combining kernel"
 357             object if the current thread becomes a combiner. Invocation of the function means that
 358             the deque should perform an action recorded in \p pRec.
 359         */
 360         void fc_apply( fc_record * pRec )
 361         {
 362             assert( pRec );
 363
 364             switch ( pRec->op() ) {
 365             case op_push_front:
 366                 assert( pRec->pValPush );
 367                 m_Deque.push_front( *(pRec->pValPush) );
 368                 break;
 369 #       ifdef CDS_MOVE_SEMANTICS_SUPPORT
 370             case op_push_front_move:
 371                 assert( pRec->pValPush );
 372                 m_Deque.push_front( std::move( *(pRec->pValPush )) );
 373                 break;
 374 #       endif
 375             case op_push_back:
 376                 assert( pRec->pValPush );
 377                 m_Deque.push_back( *(pRec->pValPush) );
 378                 break;
 379 #       ifdef CDS_MOVE_SEMANTICS_SUPPORT
 380             case op_push_back_move:
 381                 assert( pRec->pValPush );
 382                 m_Deque.push_back( std::move( *(pRec->pValPush )) );
 383                 break;
 384 #       endif
 385             case op_pop_front:
 386                 assert( pRec->pValPop );
 387                 pRec->bEmpty = m_Deque.empty();
 388                 if ( !pRec->bEmpty ) {
 389                     *(pRec->pValPop) = m_Deque.front();
 390                     m_Deque.pop_front();
 391                 }
 392                 break;
 393             case op_pop_back:
 394                 assert( pRec->pValPop );
 395                 pRec->bEmpty = m_Deque.empty();
 396                 if ( !pRec->bEmpty ) {
 397                     *(pRec->pValPop) = m_Deque.back();
 398                     m_Deque.pop_back();
 399                 }
 400                 break;
 401             case op_clear:
 402                 while ( !m_Deque.empty() )
 403                     m_Deque.pop_front();
 404                 break;
 405             default:
 406                 assert(false);
 407                 break;
 408             }
 409         }
 410
 411         /// Batch-processing flat combining
 412         void fc_process( typename fc_kernel::iterator itBegin, typename fc_kernel::iterator itEnd )
 413         {
 414             typedef typename fc_kernel::iterator fc_iterator;
 415             for ( fc_iterator it = itBegin, itPrev = itEnd; it != itEnd; ++it ) {
 416                 switch ( it->op() ) {
 417                 case op_push_front:
 418                 case op_push_front_move:
 419                     if ( itPrev != itEnd
 420                       && (itPrev->op() == op_pop_front || ( m_Deque.empty() && itPrev->op() == op_pop_back )))
 421                     {
 422                         collide( *it, *itPrev );
 423                         itPrev = itEnd;
 424                     }
 425                     else
 426                         itPrev = it;
 427                     break;
 428                 case op_push_back:
 429                 case op_push_back_move:
 430                     if ( itPrev != itEnd
 431                         && (itPrev->op() == op_pop_back || ( m_Deque.empty() && itPrev->op() == op_pop_front )))
 432                     {
 433                         collide( *it, *itPrev );
 434                         itPrev = itEnd;
 435                     }
 436                     else
 437                         itPrev = it;
 438                     break;
 439                 case op_pop_front:
 440                     if ( itPrev != itEnd
 441                         && ( itPrev->op() == op_push_front || itPrev->op() == op_push_front_move
 442                           || ( m_Deque.empty() && ( itPrev->op() == op_push_back || itPrev->op() == op_push_back_move ))))
 443                     {
 444                         collide( *itPrev, *it );
 445                         itPrev = itEnd;
 446                     }
 447                     else
 448                         itPrev = it;
 449                     break;
 450                 case op_pop_back:
 451                     if ( itPrev != itEnd
 452                         && ( itPrev->op() == op_push_back || itPrev->op() == op_push_back_move
 453                         || ( m_Deque.empty() && ( itPrev->op() == op_push_front || itPrev->op() == op_push_front_move ))))
 454                     {
 455                         collide( *itPrev, *it );
 456                         itPrev = itEnd;
 457                     }
 458                     else
 459                         itPrev = it;
 460                     break;
 461                 }
 462             }
 463         }
 464         //@endcond
 465
 466     private:
 467         //@cond
 468         void collide( fc_record& recPush, fc_record& recPop )
 469         {
 470             *(recPop.pValPop) = *(recPush.pValPush);
 471             recPop.bEmpty = false;
 472             m_FlatCombining.operation_done( recPush );
 473             m_FlatCombining.operation_done( recPop );
 474             m_FlatCombining.internal_statistics().onCollide();
 475         }
 476         //@endcond
 477     };
 478
 479 }} // namespace cds::container
 480
 481 #endif // #ifndef __CDS_CONTAINER_FCDEQUE_H