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