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         /// Inserts a new element at the beginning of the deque container (move semantics)
 196         /**
 197             The function always returns \p true
 198         */
 199         bool push_front(
 200             value_type&& val ///< Value to be moved to inserted element
 201         )
 202         {
 203             fc_record * pRec = m_FlatCombining.acquire_record();
 204             pRec->pValPush = &val;
 205
 206             if ( c_bEliminationEnabled )
 207                 m_FlatCombining.batch_combine( op_push_front_move, pRec, *this );
 208             else
 209                 m_FlatCombining.combine( op_push_front_move, pRec, *this );
 210
 211             assert( pRec->is_done() );
 212             m_FlatCombining.release_record( pRec );
 213             m_FlatCombining.internal_statistics().onPushFrontMove();
 214             return true;
 215         }
 216
 217         /// Inserts a new element at the end of the deque container
 218         /**
 219             The function always returns \p true
 220         */
 221         bool push_back(
 222             value_type const& val ///< Value to be copied to inserted element
 223         )
 224         {
 225             fc_record * pRec = m_FlatCombining.acquire_record();
 226             pRec->pValPush = &val;
 227
 228             if ( c_bEliminationEnabled )
 229                 m_FlatCombining.batch_combine( op_push_back, pRec, *this );
 230             else
 231                 m_FlatCombining.combine( op_push_back, pRec, *this );
 232
 233             assert( pRec->is_done() );
 234             m_FlatCombining.release_record( pRec );
 235             m_FlatCombining.internal_statistics().onPushBack();
 236             return true;
 237         }
 238
 239         /// Inserts a new element at the end of the deque container (move semantics)
 240         /**
 241             The function always returns \p true
 242         */
 243         bool push_back(
 244             value_type&& val ///< Value to be moved to inserted element
 245         )
 246         {
 247             fc_record * pRec = m_FlatCombining.acquire_record();
 248             pRec->pValPush = &val;
 249
 250             if ( c_bEliminationEnabled )
 251                 m_FlatCombining.batch_combine( op_push_back_move, pRec, *this );
 252             else
 253                 m_FlatCombining.combine( op_push_back_move, pRec, *this );
 254
 255             assert( pRec->is_done() );
 256             m_FlatCombining.release_record( pRec );
 257             m_FlatCombining.internal_statistics().onPushBackMove();
 258             return true;
 259         }
 260
 261         /// Removes the first element in the deque container
 262         /**
 263             The function returns \p false if the deque is empty, \p true otherwise.
 264             If the deque is empty \p val is not changed.
 265         */
 266         bool pop_front(
 267             value_type& val ///< Target to be received the copy of removed element
 268         )
 269         {
 270             fc_record * pRec = m_FlatCombining.acquire_record();
 271             pRec->pValPop = &val;
 272
 273             if ( c_bEliminationEnabled )
 274                 m_FlatCombining.batch_combine( op_pop_front, pRec, *this );
 275             else
 276                 m_FlatCombining.combine( op_pop_front, pRec, *this );
 277
 278             assert( pRec->is_done() );
 279             m_FlatCombining.release_record( pRec );
 280             m_FlatCombining.internal_statistics().onPopFront( pRec->bEmpty );
 281             return !pRec->bEmpty;
 282         }
 283
 284         /// Removes the last element in the deque container
 285         /**
 286             The function returns \p false if the deque is empty, \p true otherwise.
 287             If the deque is empty \p val is not changed.
 288         */
 289         bool pop_back(
 290             value_type& val ///< Target to be received the copy of removed element
 291         )
 292         {
 293             fc_record * pRec = m_FlatCombining.acquire_record();
 294             pRec->pValPop = &val;
 295
 296             if ( c_bEliminationEnabled )
 297                 m_FlatCombining.batch_combine( op_pop_back, pRec, *this );
 298             else
 299                 m_FlatCombining.combine( op_pop_back, pRec, *this );
 300
 301             assert( pRec->is_done() );
 302             m_FlatCombining.release_record( pRec );
 303             m_FlatCombining.internal_statistics().onPopBack( pRec->bEmpty );
 304             return !pRec->bEmpty;
 305         }
 306
 307         /// Clears the deque
 308         void clear()
 309         {
 310             fc_record * pRec = m_FlatCombining.acquire_record();
 311
 312             if ( c_bEliminationEnabled )
 313                 m_FlatCombining.batch_combine( op_clear, pRec, *this );
 314             else
 315                 m_FlatCombining.combine( op_clear, pRec, *this );
 316
 317             assert( pRec->is_done() );
 318             m_FlatCombining.release_record( pRec );
 319         }
 320
 321         /// Returns the number of elements in the deque.
 322         /**
 323             Note that <tt>size() == 0</tt> is not mean that the deque is empty because
 324             combining record can be in process.
 325             To check emptiness use \ref empty function.
 326         */
 327         size_t size() const
 328         {
 329             return m_Deque.size();
 330         }
 331
 332         /// Checks if the deque is empty
 333         /**
 334             If the combining is in process the function waits while combining done.
 335         */
 336         bool empty() const
 337         {
 338             m_FlatCombining.wait_while_combining();
 339             return m_Deque.empty();
 340         }
 341
 342         /// Internal statistics
 343         stat const& statistics() const
 344         {
 345             return m_FlatCombining.statistics();
 346         }
 347
 348     public: // flat combining cooperation, not for direct use!
 349         //@cond
 350         /// Flat combining supporting function. Do not call it directly!
 351         /**
 352             The function is called by \ref cds::algo::flat_combining::kernel "flat combining kernel"
 353             object if the current thread becomes a combiner. Invocation of the function means that
 354             the deque should perform an action recorded in \p pRec.
 355         */
 356         void fc_apply( fc_record * pRec )
 357         {
 358             assert( pRec );
 359
 360             switch ( pRec->op() ) {
 361             case op_push_front:
 362                 assert( pRec->pValPush );
 363                 m_Deque.push_front( *(pRec->pValPush) );
 364                 break;
 365             case op_push_front_move:
 366                 assert( pRec->pValPush );
 367                 m_Deque.push_front( std::move( *(pRec->pValPush )) );
 368                 break;
 369             case op_push_back:
 370                 assert( pRec->pValPush );
 371                 m_Deque.push_back( *(pRec->pValPush) );
 372                 break;
 373             case op_push_back_move:
 374                 assert( pRec->pValPush );
 375                 m_Deque.push_back( std::move( *(pRec->pValPush )) );
 376                 break;
 377             case op_pop_front:
 378                 assert( pRec->pValPop );
 379                 pRec->bEmpty = m_Deque.empty();
 380                 if ( !pRec->bEmpty ) {
 381                     *(pRec->pValPop) = m_Deque.front();
 382                     m_Deque.pop_front();
 383                 }
 384                 break;
 385             case op_pop_back:
 386                 assert( pRec->pValPop );
 387                 pRec->bEmpty = m_Deque.empty();
 388                 if ( !pRec->bEmpty ) {
 389                     *(pRec->pValPop) = m_Deque.back();
 390                     m_Deque.pop_back();
 391                 }
 392                 break;
 393             case op_clear:
 394                 while ( !m_Deque.empty() )
 395                     m_Deque.pop_front();
 396                 break;
 397             default:
 398                 assert(false);
 399                 break;
 400             }
 401         }
 402
 403         /// Batch-processing flat combining
 404         void fc_process( typename fc_kernel::iterator itBegin, typename fc_kernel::iterator itEnd )
 405         {
 406             typedef typename fc_kernel::iterator fc_iterator;
 407             for ( fc_iterator it = itBegin, itPrev = itEnd; it != itEnd; ++it ) {
 408                 switch ( it->op() ) {
 409                 case op_push_front:
 410                 case op_push_front_move:
 411                     if ( itPrev != itEnd
 412                       && (itPrev->op() == op_pop_front || ( m_Deque.empty() && itPrev->op() == op_pop_back )))
 413                     {
 414                         collide( *it, *itPrev );
 415                         itPrev = itEnd;
 416                     }
 417                     else
 418                         itPrev = it;
 419                     break;
 420                 case op_push_back:
 421                 case op_push_back_move:
 422                     if ( itPrev != itEnd
 423                         && (itPrev->op() == op_pop_back || ( m_Deque.empty() && itPrev->op() == op_pop_front )))
 424                     {
 425                         collide( *it, *itPrev );
 426                         itPrev = itEnd;
 427                     }
 428                     else
 429                         itPrev = it;
 430                     break;
 431                 case op_pop_front:
 432                     if ( itPrev != itEnd
 433                         && ( itPrev->op() == op_push_front || itPrev->op() == op_push_front_move
 434                           || ( m_Deque.empty() && ( itPrev->op() == op_push_back || itPrev->op() == op_push_back_move ))))
 435                     {
 436                         collide( *itPrev, *it );
 437                         itPrev = itEnd;
 438                     }
 439                     else
 440                         itPrev = it;
 441                     break;
 442                 case op_pop_back:
 443                     if ( itPrev != itEnd
 444                         && ( itPrev->op() == op_push_back || itPrev->op() == op_push_back_move
 445                         || ( m_Deque.empty() && ( itPrev->op() == op_push_front || itPrev->op() == op_push_front_move ))))
 446                     {
 447                         collide( *itPrev, *it );
 448                         itPrev = itEnd;
 449                     }
 450                     else
 451                         itPrev = it;
 452                     break;
 453                 }
 454             }
 455         }
 456         //@endcond
 457
 458     private:
 459         //@cond
 460         void collide( fc_record& recPush, fc_record& recPop )
 461         {
 462             *(recPop.pValPop) = *(recPush.pValPush);
 463             recPop.bEmpty = false;
 464             m_FlatCombining.operation_done( recPush );
 465             m_FlatCombining.operation_done( recPop );
 466             m_FlatCombining.internal_statistics().onCollide();
 467         }
 468         //@endcond
 469     };
 470
 471 }} // namespace cds::container
 472
 473 #endif // #ifndef __CDS_CONTAINER_FCDEQUE_H