gdax-orderbook-hpp/demo/dependencies/libcds-2.3.2/cds/container/fcstack.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_FCSTACK_H
  32 #define CDSLIB_CONTAINER_FCSTACK_H
  33
  34 #include <cds/algo/flat_combining.h>
  35 #include <cds/algo/elimination_opt.h>
  36 #include <stack>
  37
  38 namespace cds { namespace container {
  39
  40     /// FCStack related definitions
  41     /** @ingroup cds_nonintrusive_helper
  42     */
  43     namespace fcstack {
  44
  45         /// FCStack 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_nPush     ;   ///< Count of push operations
  53             counter_type    m_nPushMove ;   ///< Count of push operations with move semantics
  54             counter_type    m_nPop      ;   ///< Count of success pop operations
  55             counter_type    m_nFailedPop;   ///< Count of failed pop operations (pop from empty stack)
  56             counter_type    m_nCollided ;   ///< How many pairs of push/pop were collided, if elimination is enabled
  57
  58             //@cond
  59             void    onPush()               { ++m_nPush; }
  60             void    onPushMove()           { ++m_nPushMove; }
  61             void    onPop( bool bFailed )  { if ( bFailed ) ++m_nFailedPop; else ++m_nPop;  }
  62             void    onCollide()            { ++m_nCollided; }
  63             //@endcond
  64         };
  65
  66         /// FCStack dummy statistics, no overhead
  67         struct empty_stat: public cds::algo::flat_combining::empty_stat
  68         {
  69             //@cond
  70             void    onPush()        {}
  71             void    onPushMove()    {}
  72             void    onPop(bool)     {}
  73             void    onCollide()     {}
  74             //@endcond
  75         };
  76
  77         /// FCStack type traits
  78         struct traits: public cds::algo::flat_combining::traits
  79         {
  80             typedef empty_stat      stat;   ///< Internal statistics
  81             static constexpr const bool enable_elimination = false; ///< Enable \ref cds_elimination_description "elimination"
  82         };
  83
  84         /// Metafunction converting option list to traits
  85         /**
  86             \p Options are:
  87             - any \p cds::algo::flat_combining::make_traits options
  88             - \p opt::stat - internal statistics, possible type: \p fcstack::stat, \p fcstack::empty_stat (the default)
  89             - \p opt::enable_elimination - enable/disable operation \ref cds_elimination_description "elimination"
  90                 By default, the elimination is disabled.
  91         */
  92         template <typename... Options>
  93         struct make_traits {
  94 #   ifdef CDS_DOXYGEN_INVOKED
  95             typedef implementation_defined type ;   ///< Metafunction result
  96 #   else
  97             typedef typename cds::opt::make_options<
  98                 typename cds::opt::find_type_traits< traits, Options... >::type
  99                 ,Options...
 100             >::type   type;
 101 #   endif
 102         };
 103
 104     } // namespace fcstack
 105
 106     /// Flat-combining stack
 107     /**
 108         @ingroup cds_nonintrusive_stack
 109         @ingroup cds_flat_combining_container
 110
 111         \ref cds_flat_combining_description "Flat combining" sequential stack.
 112
 113         Template parameters:
 114         - \p T - a value type stored in the stack
 115         - \p Stack - sequential stack implementation, default is \p std::stack<T>
 116         - \p Trats - type traits of flat combining, default is \p fcstack::traits
 117             \p fcstack::make_traits metafunction can be used to construct specialized \p %fcstack::traits
 118     */
 119     template <typename T,
 120         class Stack = std::stack<T>,
 121         typename Traits = fcstack::traits
 122     >
 123     class FCStack
 124 #ifndef CDS_DOXYGEN_INVOKED
 125         : public cds::algo::flat_combining::container
 126 #endif
 127     {
 128     public:
 129         typedef T           value_type;     ///< Value type
 130         typedef Stack       stack_type;     ///< Sequential stack class
 131         typedef Traits      traits;         ///< Stack traits
 132
 133         typedef typename traits::stat  stat;   ///< Internal statistics type
 134         static constexpr const bool c_bEliminationEnabled = traits::enable_elimination; ///< \p true if elimination is enabled
 135
 136     protected:
 137         //@cond
 138         /// Stack operation IDs
 139         enum fc_operation {
 140             op_push = cds::algo::flat_combining::req_Operation, ///< Push
 141             op_push_move,   ///< Push (move semantics)
 142             op_pop,         ///< Pop
 143             op_clear,       ///< Clear
 144             op_empty        ///< Empty
 145         };
 146
 147         /// Flat combining publication list record
 148         struct fc_record: public cds::algo::flat_combining::publication_record
 149         {
 150             union {
 151                 value_type const *  pValPush; ///< Value to push
 152                 value_type *        pValPop;  ///< Pop destination
 153             };
 154             bool            bEmpty; ///< \p true if the stack is empty
 155         };
 156         //@endcond
 157
 158         /// Flat combining kernel
 159         typedef cds::algo::flat_combining::kernel< fc_record, traits > fc_kernel;
 160
 161     protected:
 162         //@cond
 163         mutable fc_kernel m_FlatCombining;
 164         stack_type        m_Stack;
 165         //@endcond
 166
 167     public:
 168         /// Initializes empty stack object
 169         FCStack()
 170         {}
 171
 172         /// Initializes empty stack object and gives flat combining parameters
 173         FCStack(
 174             unsigned int nCompactFactor     ///< Flat combining: publication list compacting factor
 175             ,unsigned int nCombinePassCount ///< Flat combining: number of combining passes for combiner thread
 176             )
 177             : m_FlatCombining( nCompactFactor, nCombinePassCount )
 178         {}
 179
 180         /// Inserts a new element at the top of stack
 181         /**
 182             The content of the new element initialized to a copy of \p val.
 183         */
 184         bool push( value_type const& val )
 185         {
 186             auto pRec = m_FlatCombining.acquire_record();
 187             pRec->pValPush = &val;
 188
 189             constexpr_if ( c_bEliminationEnabled )
 190                 m_FlatCombining.batch_combine( op_push, pRec, *this );
 191             else
 192                 m_FlatCombining.combine( op_push, pRec, *this );
 193
 194             assert( pRec->is_done());
 195             m_FlatCombining.release_record( pRec );
 196             m_FlatCombining.internal_statistics().onPush();
 197             return true;
 198         }
 199
 200         /// Inserts a new element at the top of stack (move semantics)
 201         /**
 202             The content of the new element initialized to a copy of \p val.
 203         */
 204         bool push( value_type&& val )
 205         {
 206             auto pRec = m_FlatCombining.acquire_record();
 207             pRec->pValPush = &val;
 208
 209             constexpr_if ( c_bEliminationEnabled )
 210                 m_FlatCombining.batch_combine( op_push_move, pRec, *this );
 211             else
 212                 m_FlatCombining.combine( op_push_move, pRec, *this );
 213
 214             assert( pRec->is_done());
 215             m_FlatCombining.release_record( pRec );
 216
 217             m_FlatCombining.internal_statistics().onPushMove();
 218             return true;
 219         }
 220
 221         /// Removes the element on top of the stack
 222         /**
 223             \p val takes a copy of top element
 224         */
 225         bool pop( value_type& val )
 226         {
 227             auto pRec = m_FlatCombining.acquire_record();
 228             pRec->pValPop = &val;
 229
 230             constexpr_if ( c_bEliminationEnabled )
 231                 m_FlatCombining.batch_combine( op_pop, pRec, *this );
 232             else
 233                 m_FlatCombining.combine( op_pop, pRec, *this );
 234
 235             assert( pRec->is_done());
 236             m_FlatCombining.release_record( pRec );
 237
 238             m_FlatCombining.internal_statistics().onPop( pRec->bEmpty );
 239             return !pRec->bEmpty;
 240         }
 241
 242         /// Clears the stack
 243         void clear()
 244         {
 245             auto pRec = m_FlatCombining.acquire_record();
 246
 247             constexpr_if ( c_bEliminationEnabled )
 248                 m_FlatCombining.batch_combine( op_clear, pRec, *this );
 249             else
 250                 m_FlatCombining.combine( op_clear, pRec, *this );
 251
 252             assert( pRec->is_done());
 253             m_FlatCombining.release_record( pRec );
 254         }
 255
 256         /// Exclusive access to underlying stack object
 257         /**
 258             The functor \p f can do any operation with underlying \p stack_type in exclusive mode.
 259             For example, you can iterate over the stack.
 260             \p Func signature is:
 261             \code
 262                 void f( stack_type& stack );
 263             \endcode
 264         */
 265         template <typename Func>
 266         void apply( Func f )
 267         {
 268             auto& stack = m_Stack;
 269             m_FlatCombining.invoke_exclusive( [&stack, &f]() { f( stack ); } );
 270         }
 271
 272         /// Exclusive access to underlying stack object
 273         /**
 274             The functor \p f can do any operation with underlying \p stack_type in exclusive mode.
 275             For example, you can iterate over the stack.
 276             \p Func signature is:
 277             \code
 278                 void f( stack_type const& stack );
 279             \endcode
 280         */
 281         template <typename Func>
 282         void apply( Func f ) const
 283         {
 284             auto const& stack = m_Stack;
 285             m_FlatCombining.invoke_exclusive( [&stack, &f]() { f( stack ); } );
 286         }
 287
 288         /// Returns the number of elements in the stack.
 289         /**
 290             Note that <tt>size() == 0</tt> is not mean that the stack is empty because
 291             combining record can be in process.
 292             To check emptiness use \ref empty() function.
 293         */
 294         size_t size() const
 295         {
 296             return m_Stack.size();
 297         }
 298
 299         /// Checks if the stack is empty
 300         /**
 301             If the combining is in process the function waits while combining done.
 302         */
 303         bool empty()
 304         {
 305             auto pRec = m_FlatCombining.acquire_record();
 306
 307             constexpr_if ( c_bEliminationEnabled )
 308                 m_FlatCombining.batch_combine( op_empty, pRec, *this );
 309             else
 310                 m_FlatCombining.combine( op_empty, pRec, *this );
 311
 312             assert( pRec->is_done());
 313             m_FlatCombining.release_record( pRec );
 314             return pRec->bEmpty;
 315         }
 316
 317         /// Internal statistics
 318         stat const& statistics() const
 319         {
 320             return m_FlatCombining.statistics();
 321         }
 322
 323
 324     public: // flat combining cooperation, not for direct use!
 325         //@cond
 326         /// Flat combining supporting function. Do not call it directly!
 327         /**
 328             The function is called by \ref cds::algo::flat_combining::kernel "flat combining kernel"
 329             object if the current thread becomes a combiner. Invocation of the function means that
 330             the stack should perform an action recorded in \p pRec.
 331         */
 332         void fc_apply( fc_record * pRec )
 333         {
 334             assert( pRec );
 335
 336             switch ( pRec->op()) {
 337             case op_push:
 338                 assert( pRec->pValPush );
 339                 m_Stack.push( *(pRec->pValPush ));
 340                 break;
 341             case op_push_move:
 342                 assert( pRec->pValPush );
 343                 m_Stack.push( std::move( *(pRec->pValPush )));
 344                 break;
 345             case op_pop:
 346                 assert( pRec->pValPop );
 347                 pRec->bEmpty = m_Stack.empty();
 348                 if ( !pRec->bEmpty ) {
 349                     *(pRec->pValPop) = std::move( m_Stack.top());
 350                     m_Stack.pop();
 351                 }
 352                 break;
 353             case op_clear:
 354                 while ( !m_Stack.empty())
 355                     m_Stack.pop();
 356                 break;
 357             case op_empty:
 358                 pRec->bEmpty = m_Stack.empty();
 359                 break;
 360             default:
 361                 assert(false);
 362                 break;
 363             }
 364         }
 365
 366         /// Batch-processing flat combining
 367         void fc_process( typename fc_kernel::iterator itBegin, typename fc_kernel::iterator itEnd )
 368         {
 369             typedef typename fc_kernel::iterator fc_iterator;
 370             for ( fc_iterator it = itBegin, itPrev = itEnd; it != itEnd; ++it ) {
 371                 switch ( it->op( atomics::memory_order_acquire )) {
 372                 case op_push:
 373                 case op_push_move:
 374                 case op_pop:
 375                     if ( itPrev != itEnd && collide( *itPrev, *it ))
 376                         itPrev = itEnd;
 377                     else
 378                         itPrev = it;
 379                     break;
 380                 }
 381             }
 382         }
 383         //@endcond
 384
 385     private:
 386         //@cond
 387         bool collide( fc_record& rec1, fc_record& rec2 )
 388         {
 389             switch ( rec1.op()) {
 390                 case op_push:
 391                     if ( rec2.op() == op_pop ) {
 392                         assert(rec1.pValPush);
 393                         assert(rec2.pValPop);
 394                         *rec2.pValPop = *rec1.pValPush;
 395                         rec2.bEmpty = false;
 396                         goto collided;
 397                     }
 398                     break;
 399                 case op_push_move:
 400                     if ( rec2.op() == op_pop ) {
 401                         assert(rec1.pValPush);
 402                         assert(rec2.pValPop);
 403                         *rec2.pValPop = std::move( *rec1.pValPush );
 404                         rec2.bEmpty = false;
 405                         goto collided;
 406                     }
 407                     break;
 408                 case op_pop:
 409                     switch ( rec2.op()) {
 410                     case op_push:
 411                     case op_push_move:
 412                         return collide( rec2, rec1 );
 413                     }
 414             }
 415             return false;
 416
 417         collided:
 418             m_FlatCombining.operation_done( rec1 );
 419             m_FlatCombining.operation_done( rec2 );
 420             m_FlatCombining.internal_statistics().onCollide();
 421             return true;
 422         }
 423         //@endcond
 424     };
 425 }} // namespace cds::container
 426
 427 #endif // #ifndef CDSLIB_CONTAINER_FCSTACK_H