cds/container/fcdeque.h

   1 //$$CDS-header$$
   2
   3 #ifndef CDSLIB_CONTAINER_FCDEQUE_H
   4 #define CDSLIB_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 traits: public cds::algo::flat_combining::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             \p Options are:
  69             - \p opt::lock_type - mutex type, default is \p cds::sync::spin
  70             - \p opt::back_off - back-off strategy, defalt is \p cds::backoff::delay_of<2>
  71             - \p opt::allocator - allocator type, default is \ref CDS_DEFAULT_ALLOCATOR
  72             - \p opt::stat - internal statistics, possible type: \ref stat, \ref empty_stat (the default)
  73             - \p opt::memory_model - C++ memory ordering model.
  74                 List of all available memory ordering see opt::memory_model.
  75                 Default if cds::opt::v:relaxed_ordering
  76             - \p opt::enable_elimination - enable/disable operation \ref cds_elimination_description "elimination"
  77                 By default, the elimination is disabled. For queue, the elimination is possible if the queue
  78                 is empty.
  79         */
  80         template <typename... Options>
  81         struct make_traits {
  82 #   ifdef CDS_DOXYGEN_INVOKED
  83             typedef implementation_defined type ;   ///< Metafunction result
  84 #   else
  85             typedef typename cds::opt::make_options<
  86                 typename cds::opt::find_type_traits< traits, Options... >::type
  87                 ,Options...
  88             >::type   type;
  89 #   endif
  90         };
  91
  92     } // namespace fcqueue
  93
  94     /// Flat-combining deque
  95     /**
  96         @ingroup cds_nonintrusive_deque
  97         @ingroup cds_flat_combining_container
  98
  99         \ref cds_flat_combining_description "Flat combining" sequential deque.
 100         The class can be considered as a concurrent FC-based wrapper for \p std::deque.
 101
 102         Template parameters:
 103         - \p T - a value type stored in the deque
 104         - \p Deque - sequential deque implementation, for example, \p std::deque<T> (the default)
 105             or \p boost::container::deque
 106         - \p Trats - type traits of flat combining, default is \p fcdeque::traits.
 107             \p fcdeque::make_traits metafunction can be used to construct specialized \p %fcdeque::traits
 108     */
 109     template <typename T,
 110         class Deque = std::deque<T>,
 111         typename Traits = fcdeque::traits
 112     >
 113     class FCDeque
 114 #ifndef CDS_DOXYGEN_INVOKED
 115         : public cds::algo::flat_combining::container
 116 #endif
 117     {
 118     public:
 119         typedef T           value_type;     ///< Value type
 120         typedef Deque       deque_type;     ///< Sequential deque class
 121         typedef Traits      traits;         ///< Deque type traits
 122
 123         typedef typename traits::stat  stat;   ///< Internal statistics type
 124         static CDS_CONSTEXPR const bool c_bEliminationEnabled = traits::enable_elimination; ///< \p true if elimination is enabled
 125
 126     protected:
 127         //@cond
 128         /// Deque operation IDs
 129         enum fc_operation {
 130             op_push_front = cds::algo::flat_combining::req_Operation, ///< Push front
 131             op_push_front_move,     ///< Push front (move semantics)
 132             op_push_back,           ///< Push back
 133             op_push_back_move,      ///< Push back (move semantics)
 134             op_pop_front,           ///< Pop front
 135             op_pop_back,            ///< Pop back
 136             op_clear,               ///< Clear
 137             op_empty                ///< Empty
 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, 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()
 337         {
 338             fc_record * pRec = m_FlatCombining.acquire_record();
 339
 340             if ( c_bEliminationEnabled )
 341                 m_FlatCombining.batch_combine( op_empty, pRec, *this );
 342             else
 343                 m_FlatCombining.combine( op_empty, pRec, *this );
 344
 345             assert( pRec->is_done() );
 346             m_FlatCombining.release_record( pRec );
 347             return pRec->bEmpty;
 348         }
 349
 350         /// Internal statistics
 351         stat const& statistics() const
 352         {
 353             return m_FlatCombining.statistics();
 354         }
 355
 356     public: // flat combining cooperation, not for direct use!
 357         //@cond
 358         /// Flat combining supporting function. Do not call it directly!
 359         /**
 360             The function is called by \ref cds::algo::flat_combining::kernel "flat combining kernel"
 361             object if the current thread becomes a combiner. Invocation of the function means that
 362             the deque should perform an action recorded in \p pRec.
 363         */
 364         void fc_apply( fc_record * pRec )
 365         {
 366             assert( pRec );
 367
 368             switch ( pRec->op() ) {
 369             case op_push_front:
 370                 assert( pRec->pValPush );
 371                 m_Deque.push_front( *(pRec->pValPush) );
 372                 break;
 373             case op_push_front_move:
 374                 assert( pRec->pValPush );
 375                 m_Deque.push_front( std::move( *(pRec->pValPush )) );
 376                 break;
 377             case op_push_back:
 378                 assert( pRec->pValPush );
 379                 m_Deque.push_back( *(pRec->pValPush) );
 380                 break;
 381             case op_push_back_move:
 382                 assert( pRec->pValPush );
 383                 m_Deque.push_back( std::move( *(pRec->pValPush )) );
 384                 break;
 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             case op_empty:
 406                 pRec->bEmpty = m_Deque.empty();
 407                 break;
 408             default:
 409                 assert(false);
 410                 break;
 411             }
 412         }
 413
 414         /// Batch-processing flat combining
 415         void fc_process( typename fc_kernel::iterator itBegin, typename fc_kernel::iterator itEnd )
 416         {
 417             typedef typename fc_kernel::iterator fc_iterator;
 418             for ( fc_iterator it = itBegin, itPrev = itEnd; it != itEnd; ++it ) {
 419                 switch ( it->op() ) {
 420                 case op_push_front:
 421                 case op_push_front_move:
 422                     if ( itPrev != itEnd
 423                       && (itPrev->op() == op_pop_front || ( m_Deque.empty() && itPrev->op() == op_pop_back )))
 424                     {
 425                         collide( *it, *itPrev );
 426                         itPrev = itEnd;
 427                     }
 428                     else
 429                         itPrev = it;
 430                     break;
 431                 case op_push_back:
 432                 case op_push_back_move:
 433                     if ( itPrev != itEnd
 434                         && (itPrev->op() == op_pop_back || ( m_Deque.empty() && itPrev->op() == op_pop_front )))
 435                     {
 436                         collide( *it, *itPrev );
 437                         itPrev = itEnd;
 438                     }
 439                     else
 440                         itPrev = it;
 441                     break;
 442                 case op_pop_front:
 443                     if ( itPrev != itEnd
 444                         && ( itPrev->op() == op_push_front || itPrev->op() == op_push_front_move
 445                           || ( m_Deque.empty() && ( itPrev->op() == op_push_back || itPrev->op() == op_push_back_move ))))
 446                     {
 447                         collide( *itPrev, *it );
 448                         itPrev = itEnd;
 449                     }
 450                     else
 451                         itPrev = it;
 452                     break;
 453                 case op_pop_back:
 454                     if ( itPrev != itEnd
 455                         && ( itPrev->op() == op_push_back || itPrev->op() == op_push_back_move
 456                         || ( m_Deque.empty() && ( itPrev->op() == op_push_front || itPrev->op() == op_push_front_move ))))
 457                     {
 458                         collide( *itPrev, *it );
 459                         itPrev = itEnd;
 460                     }
 461                     else
 462                         itPrev = it;
 463                     break;
 464                 }
 465             }
 466         }
 467         //@endcond
 468
 469     private:
 470         //@cond
 471         void collide( fc_record& recPush, fc_record& recPop )
 472         {
 473             *(recPop.pValPop) = *(recPush.pValPush);
 474             recPop.bEmpty = false;
 475             m_FlatCombining.operation_done( recPush );
 476             m_FlatCombining.operation_done( recPop );
 477             m_FlatCombining.internal_statistics().onCollide();
 478         }
 479         //@endcond
 480     };
 481
 482 }} // namespace cds::container
 483
 484 #endif // #ifndef CDSLIB_CONTAINER_FCDEQUE_H