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