gdax-orderbook-hpp/demo/dependencies/libcds-2.3.2/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 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 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             constexpr_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             constexpr_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             constexpr_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             constexpr_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             constexpr_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             constexpr_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             constexpr_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         /// Exclusive access to underlying deque object
 344         /**
 345             The functor \p f can do any operation with underlying \p deque_type in exclusive mode.
 346             For example, you can iterate over the deque.
 347             \p Func signature is:
 348             \code
 349                 void f( deque_type& deque );
 350             \endcode
 351         */
 352         template <typename Func>
 353         void apply( Func f )
 354         {
 355             auto& deque = m_Deque;
 356             m_FlatCombining.invoke_exclusive( [&deque, &f]() { f( deque ); } );
 357         }
 358
 359         /// Exclusive access to underlying deque object
 360         /**
 361             The functor \p f can do any operation with underlying \p deque_type in exclusive mode.
 362             For example, you can iterate over the deque.
 363             \p Func signature is:
 364             \code
 365                 void f( deque_type const& deque );
 366             \endcode
 367         */
 368         template <typename Func>
 369         void apply( Func f ) const
 370         {
 371             auto const& deque = m_Deque;
 372             m_FlatCombining.invoke_exclusive( [&deque, &f]() { f( deque ); } );
 373         }
 374
 375         /// Returns the number of elements in the deque.
 376         /**
 377             Note that <tt>size() == 0</tt> is not mean that the deque is empty because
 378             combining record can be in process.
 379             To check emptiness use \ref empty function.
 380         */
 381         size_t size() const
 382         {
 383             return m_Deque.size();
 384         }
 385
 386         /// Checks if the deque is empty
 387         /**
 388             If the combining is in process the function waits while combining done.
 389         */
 390         bool empty() const
 391         {
 392             bool bRet = false;
 393             auto const& deq = m_Deque;
 394             m_FlatCombining.invoke_exclusive( [&deq, &bRet]() { bRet = deq.empty(); } );
 395             return bRet;
 396         }
 397
 398         /// Internal statistics
 399         stat const& statistics() const
 400         {
 401             return m_FlatCombining.statistics();
 402         }
 403
 404     public: // flat combining cooperation, not for direct use!
 405         //@cond
 406         /// Flat combining supporting function. Do not call it directly!
 407         /**
 408             The function is called by \ref cds::algo::flat_combining::kernel "flat combining kernel"
 409             object if the current thread becomes a combiner. Invocation of the function means that
 410             the deque should perform an action recorded in \p pRec.
 411         */
 412         void fc_apply( fc_record * pRec )
 413         {
 414             assert( pRec );
 415
 416             switch ( pRec->op()) {
 417             case op_push_front:
 418                 assert( pRec->pValPush );
 419                 m_Deque.push_front( *(pRec->pValPush));
 420                 break;
 421             case op_push_front_move:
 422                 assert( pRec->pValPush );
 423                 m_Deque.push_front( std::move( *(pRec->pValPush )));
 424                 break;
 425             case op_push_back:
 426                 assert( pRec->pValPush );
 427                 m_Deque.push_back( *(pRec->pValPush));
 428                 break;
 429             case op_push_back_move:
 430                 assert( pRec->pValPush );
 431                 m_Deque.push_back( std::move( *(pRec->pValPush )));
 432                 break;
 433             case op_pop_front:
 434                 assert( pRec->pValPop );
 435                 pRec->bEmpty = m_Deque.empty();
 436                 if ( !pRec->bEmpty ) {
 437                     *(pRec->pValPop) = std::move( m_Deque.front());
 438                     m_Deque.pop_front();
 439                 }
 440                 break;
 441             case op_pop_back:
 442                 assert( pRec->pValPop );
 443                 pRec->bEmpty = m_Deque.empty();
 444                 if ( !pRec->bEmpty ) {
 445                     *(pRec->pValPop) = std::move( m_Deque.back());
 446                     m_Deque.pop_back();
 447                 }
 448                 break;
 449             case op_clear:
 450                 while ( !m_Deque.empty())
 451                     m_Deque.pop_front();
 452                 break;
 453             default:
 454                 assert(false);
 455                 break;
 456             }
 457         }
 458
 459         /// Batch-processing flat combining
 460         void fc_process( typename fc_kernel::iterator itBegin, typename fc_kernel::iterator itEnd )
 461         {
 462             typedef typename fc_kernel::iterator fc_iterator;
 463
 464             for ( fc_iterator it = itBegin, itPrev = itEnd; it != itEnd; ++it ) {
 465                 switch ( it->op( atomics::memory_order_acquire )) {
 466                 case op_push_front:
 467                     if ( itPrev != itEnd
 468                         && (itPrev->op() == op_pop_front || (m_Deque.empty() && itPrev->op() == op_pop_back)))
 469                     {
 470                         collide( *it, *itPrev );
 471                         itPrev = itEnd;
 472                     }
 473                     else
 474                         itPrev = it;
 475                     break;
 476                 case op_push_front_move:
 477                     if ( itPrev != itEnd
 478                       && (itPrev->op() == op_pop_front || ( m_Deque.empty() && itPrev->op() == op_pop_back )))
 479                     {
 480                         collide_move( *it, *itPrev );
 481                         itPrev = itEnd;
 482                     }
 483                     else
 484                         itPrev = it;
 485                     break;
 486                 case op_push_back:
 487                     if ( itPrev != itEnd
 488                         && (itPrev->op() == op_pop_back || (m_Deque.empty() && itPrev->op() == op_pop_front)))
 489                     {
 490                         collide( *it, *itPrev );
 491                         itPrev = itEnd;
 492                     }
 493                     else
 494                         itPrev = it;
 495                     break;
 496                 case op_push_back_move:
 497                     if ( itPrev != itEnd
 498                         && (itPrev->op() == op_pop_back || ( m_Deque.empty() && itPrev->op() == op_pop_front )))
 499                     {
 500                         collide_move( *it, *itPrev );
 501                         itPrev = itEnd;
 502                     }
 503                     else
 504                         itPrev = it;
 505                     break;
 506                 case op_pop_front:
 507                     if ( itPrev != itEnd ) {
 508                         if ( m_Deque.empty()) {
 509                             switch ( itPrev->op()) {
 510                             case op_push_back:
 511                                 collide( *itPrev, *it );
 512                                 itPrev = itEnd;
 513                                 break;
 514                             case op_push_back_move:
 515                                 collide_move( *itPrev, *it );
 516                                 itPrev = itEnd;
 517                                 break;
 518                             default:
 519                                 itPrev = it;
 520                                 break;
 521                             }
 522                         }
 523                         else {
 524                             switch ( itPrev->op()) {
 525                             case op_push_front:
 526                                 collide( *itPrev, *it );
 527                                 itPrev = itEnd;
 528                                 break;
 529                             case op_push_front_move:
 530                                 collide_move( *itPrev, *it );
 531                                 itPrev = itEnd;
 532                                 break;
 533                             default:
 534                                 itPrev = it;
 535                                 break;
 536                             }
 537                         }
 538                     }
 539                     else
 540                         itPrev = it;
 541                     break;
 542                 case op_pop_back:
 543                     if ( itPrev != itEnd ) {
 544                         if ( m_Deque.empty()) {
 545                             switch ( itPrev->op()) {
 546                             case op_push_front:
 547                                 collide( *itPrev, *it );
 548                                 itPrev = itEnd;
 549                                 break;
 550                             case op_push_front_move:
 551                                 collide_move( *itPrev, *it );
 552                                 itPrev = itEnd;
 553                                 break;
 554                             default:
 555                                 itPrev = it;
 556                                 break;
 557                             }
 558                         }
 559                         else {
 560                             switch ( itPrev->op()) {
 561                             case op_push_back:
 562                                 collide( *itPrev, *it );
 563                                 itPrev = itEnd;
 564                                 break;
 565                             case op_push_back_move:
 566                                 collide_move( *itPrev, *it );
 567                                 itPrev = itEnd;
 568                                 break;
 569                             default:
 570                                 itPrev = it;
 571                                 break;
 572                             }
 573                         }
 574                     }
 575                     else
 576                         itPrev = it;
 577                     break;
 578                 }
 579             }
 580         }
 581         //@endcond
 582
 583     private:
 584         //@cond
 585         void collide( fc_record& recPush, fc_record& recPop )
 586         {
 587             *(recPop.pValPop) = *(recPush.pValPush);
 588             recPop.bEmpty = false;
 589             m_FlatCombining.operation_done( recPush );
 590             m_FlatCombining.operation_done( recPop );
 591             m_FlatCombining.internal_statistics().onCollide();
 592         }
 593
 594         void collide_move( fc_record& recPush, fc_record& recPop )
 595         {
 596             *(recPop.pValPop) = std::move( *(recPush.pValPush));
 597             recPop.bEmpty = false;
 598             m_FlatCombining.operation_done( recPush );
 599             m_FlatCombining.operation_done( recPop );
 600             m_FlatCombining.internal_statistics().onCollide();
 601         }
 602         //@endcond
 603     };
 604
 605 }} // namespace cds::container
 606
 607 #endif // #ifndef CDSLIB_CONTAINER_FCDEQUE_H