cds/container/fcstack.h

   1 //$$CDS-header$$
   2
   3 #ifndef __CDS_CONTAINER_FCSTACK_H
   4 #define __CDS_CONTAINER_FCSTACK_H
   5
   6 #include <cds/algo/flat_combining.h>
   7 #include <cds/algo/elimination_opt.h>
   8 #include <stack>
   9
  10 namespace cds { namespace container {
  11
  12     /// FCStack related definitions
  13     /** @ingroup cds_nonintrusive_helper
  14     */
  15     namespace fcstack {
  16
  17         /// FCStack 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_nPush     ;   ///< Count of push operations
  25             counter_type    m_nPushMove ;   ///< Count of push operations with move semantics
  26             counter_type    m_nPop      ;   ///< Count of success pop operations
  27             counter_type    m_nFailedPop;   ///< Count of failed pop operations (pop from empty stack)
  28             counter_type    m_nCollided ;   ///< How many pairs of push/pop were collided, if elimination is enabled
  29
  30             //@cond
  31             void    onPush()               { ++m_nPush; }
  32             void    onPushMove()           { ++m_nPushMove; }
  33             void    onPop( bool bFailed )  { if ( bFailed ) ++m_nFailedPop; else ++m_nPop;  }
  34             void    onCollide()            { ++m_nCollided; }
  35             //@endcond
  36         };
  37
  38         /// FCStack dummy statistics, no overhead
  39         struct empty_stat: public cds::algo::flat_combining::empty_stat
  40         {
  41             //@cond
  42             void    onPush()        {}
  43             void    onPushMove()    {}
  44             void    onPop(bool)     {}
  45             void    onCollide()     {}
  46             //@endcond
  47         };
  48
  49         /// FCStack type traits
  50         struct type_traits: public cds::algo::flat_combining::type_traits
  51         {
  52             typedef empty_stat      stat;   ///< Internal statistics
  53             static CDS_CONSTEXPR_CONST bool enable_elimination = false; ///< Enable \ref cds_elimination_description "elimination"
  54         };
  55
  56         /// Metafunction converting option list to traits
  57         /**
  58             This is a wrapper for <tt> cds::opt::make_options< type_traits, Options...> </tt>
  59             \p Options are:
  60             - \p opt::lock_type - mutex type, default is \p cds::lock::Spin
  61             - \p opt::back_off - back-off strategy, defalt is \p cds::backoff::Default
  62             - \p opt::allocator - allocator type, default is \ref CDS_DEFAULT_ALLOCATOR
  63             - \p opt::stat - internal statistics, possible type: \ref stat, \ref empty_stat (the default)
  64             - \p opt::memory_model - C++ memory ordering model.
  65                 List of all available memory ordering see opt::memory_model.
  66                 Default if cds::opt::v:relaxed_ordering
  67             - \p opt::enable_elimination - enable/disable operation \ref cds_elimination_description "elimination"
  68                 By default, the elimination is disabled.
  69         */
  70         template <CDS_DECL_OPTIONS8>
  71         struct make_traits {
  72 #   ifdef CDS_DOXYGEN_INVOKED
  73             typedef implementation_defined type ;   ///< Metafunction result
  74 #   else
  75             typedef typename cds::opt::make_options<
  76                 typename cds::opt::find_type_traits< type_traits, CDS_OPTIONS8 >::type
  77                 ,CDS_OPTIONS8
  78             >::type   type;
  79 #   endif
  80         };
  81
  82     } // namespace fcstack
  83
  84     /// Flat-combining stack
  85     /**
  86         @ingroup cds_nonintrusive_stack
  87         @ingroup cds_flat_combining_container
  88
  89         \ref cds_flat_combining_description "Flat combining" sequential stack.
  90
  91         Template parameters:
  92         - \p T - a value type stored in the stack
  93         - \p Stack - sequential stack implementation, default is \p std::stack<T>
  94         - \p Trats - type traits of flat combining, default is \p fcstack::type_traits
  95             \p fcstack::make_traits metafunction can be used to construct specialized \p %type_traits
  96     */
  97     template <typename T,
  98         class Stack = std::stack<T>,
  99         typename Traits = fcstack::type_traits
 100     >
 101     class FCStack
 102 #ifndef CDS_DOXYGEN_INVOKED
 103         : public cds::algo::flat_combining::container
 104 #endif
 105     {
 106     public:
 107         typedef T           value_type;     ///< Value type
 108         typedef Stack       stack_type;     ///< Sequential stack class
 109         typedef Traits      type_traits;    ///< Stack type traits
 110
 111         typedef typename type_traits::stat  stat;   ///< Internal statistics type
 112         static CDS_CONSTEXPR_CONST bool c_bEliminationEnabled = type_traits::enable_elimination; ///< \p true if elimination is enabled
 113
 114     protected:
 115         //@cond
 116         /// Stack operation IDs
 117         enum fc_operation {
 118             op_push = cds::algo::flat_combining::req_Operation, ///< Push
 119             op_push_move,   ///< Push (move semantics)
 120             op_pop,         ///< Pop
 121             op_clear        ///< Clear
 122         };
 123
 124         /// Flat combining publication list record
 125         struct fc_record: public cds::algo::flat_combining::publication_record
 126         {
 127             union {
 128                 value_type const *  pValPush; ///< Value to push
 129                 value_type *        pValPop;  ///< Pop destination
 130             };
 131             bool            bEmpty; ///< \p true if the stack is empty
 132         };
 133         //@endcond
 134
 135         /// Flat combining kernel
 136         typedef cds::algo::flat_combining::kernel< fc_record, type_traits > fc_kernel;
 137
 138     protected:
 139         //@cond
 140         fc_kernel   m_FlatCombining;
 141         stack_type  m_Stack;
 142         //@endcond
 143
 144     public:
 145         /// Initializes empty stack object
 146         FCStack()
 147         {}
 148
 149         /// Initializes empty stack object and gives flat combining parameters
 150         FCStack(
 151             unsigned int nCompactFactor     ///< Flat combining: publication list compacting factor
 152             ,unsigned int nCombinePassCount ///< Flat combining: number of combining passes for combiner thread
 153             )
 154             : m_FlatCombining( nCompactFactor, nCombinePassCount )
 155         {}
 156
 157         /// Inserts a new element at the top of stack
 158         /**
 159             The content of the new element initialized to a copy of \p val.
 160         */
 161         bool push( value_type const& val )
 162         {
 163             fc_record * pRec = m_FlatCombining.acquire_record();
 164             pRec->pValPush = &val;
 165
 166             if ( c_bEliminationEnabled )
 167                 m_FlatCombining.batch_combine( op_push, pRec, *this );
 168             else
 169                 m_FlatCombining.combine( op_push, pRec, *this );
 170
 171             assert( pRec->is_done() );
 172             m_FlatCombining.release_record( pRec );
 173             m_FlatCombining.internal_statistics().onPush();
 174             return true;
 175         }
 176
 177 #   ifdef CDS_MOVE_SEMANTICS_SUPPORT
 178         /// Inserts a new element at the top of stack (move semantics)
 179         /**
 180             The content of the new element initialized to a copy of \p val.
 181         */
 182         bool push( value_type&& val )
 183         {
 184             fc_record * pRec = m_FlatCombining.acquire_record();
 185             pRec->pValPush = &val;
 186
 187             if ( c_bEliminationEnabled )
 188                 m_FlatCombining.batch_combine( op_push_move, pRec, *this );
 189             else
 190                 m_FlatCombining.combine( op_push_move, pRec, *this );
 191
 192             assert( pRec->is_done() );
 193             m_FlatCombining.release_record( pRec );
 194
 195             m_FlatCombining.internal_statistics().onPushMove();
 196             return true;
 197         }
 198 #   endif
 199
 200         /// Removes the element on top of the stack
 201         /**
 202             \p val takes a copy of top element
 203         */
 204         bool pop( value_type& val )
 205         {
 206             fc_record * pRec = m_FlatCombining.acquire_record();
 207             pRec->pValPop = &val;
 208
 209             if ( c_bEliminationEnabled )
 210                 m_FlatCombining.batch_combine( op_pop, pRec, *this );
 211             else
 212                 m_FlatCombining.combine( op_pop, pRec, *this );
 213
 214             assert( pRec->is_done() );
 215             m_FlatCombining.release_record( pRec );
 216
 217             m_FlatCombining.internal_statistics().onPop( pRec->bEmpty );
 218             return !pRec->bEmpty;
 219         }
 220
 221         /// Clears the stack
 222         void clear()
 223         {
 224             fc_record * pRec = m_FlatCombining.acquire_record();
 225
 226             if ( c_bEliminationEnabled )
 227                 m_FlatCombining.batch_combine( op_clear, pRec, *this );
 228             else
 229                 m_FlatCombining.combine( op_clear, pRec, *this );
 230
 231             assert( pRec->is_done() );
 232             m_FlatCombining.release_record( pRec );
 233         }
 234
 235         /// Returns the number of elements in the stack.
 236         /**
 237             Note that <tt>size() == 0</tt> is not mean that the stack is empty because
 238             combining record can be in process.
 239             To check emptiness use \ref empty function.
 240         */
 241         size_t size() const
 242         {
 243             return m_Stack.size();
 244         }
 245
 246         /// Checks if the stack is empty
 247         /**
 248             If the combining is in process the function waits while combining done.
 249         */
 250         bool empty() const
 251         {
 252             m_FlatCombining.wait_while_combining();
 253             return m_Stack.empty();
 254         }
 255
 256         /// Internal statistics
 257         stat const& statistics() const
 258         {
 259             return m_FlatCombining.statistics();
 260         }
 261
 262
 263     public: // flat combining cooperation, not for direct use!
 264         //@cond
 265         /// Flat combining supporting function. Do not call it directly!
 266         /**
 267             The function is called by \ref cds::algo::flat_combining::kernel "flat combining kernel"
 268             object if the current thread becomes a combiner. Invocation of the function means that
 269             the stack should perform an action recorded in \p pRec.
 270         */
 271         void fc_apply( fc_record * pRec )
 272         {
 273             assert( pRec );
 274
 275             switch ( pRec->op() ) {
 276             case op_push:
 277                 assert( pRec->pValPush );
 278                 m_Stack.push( *(pRec->pValPush ) );
 279                 break;
 280 #       ifdef CDS_MOVE_SEMANTICS_SUPPORT
 281             case op_push_move:
 282                 assert( pRec->pValPush );
 283                 m_Stack.push( std::move( *(pRec->pValPush )) );
 284                 break;
 285 #       endif
 286             case op_pop:
 287                 assert( pRec->pValPop );
 288                 pRec->bEmpty = m_Stack.empty();
 289                 if ( !pRec->bEmpty ) {
 290                     *(pRec->pValPop) = m_Stack.top();
 291                     m_Stack.pop();
 292                 }
 293                 break;
 294             case op_clear:
 295                 while ( !m_Stack.empty() )
 296                     m_Stack.pop();
 297                 break;
 298             default:
 299                 assert(false);
 300                 break;
 301             }
 302         }
 303
 304         /// Batch-processing flat combining
 305         void fc_process( typename fc_kernel::iterator itBegin, typename fc_kernel::iterator itEnd )
 306         {
 307             typedef typename fc_kernel::iterator fc_iterator;
 308             for ( fc_iterator it = itBegin, itPrev = itEnd; it != itEnd; ++it ) {
 309                 switch ( it->op() ) {
 310                 case op_push:
 311                 case op_push_move:
 312                 case op_pop:
 313                     if ( itPrev != itEnd && collide( *itPrev, *it ))
 314                         itPrev = itEnd;
 315                     else
 316                         itPrev = it;
 317                     break;
 318                 }
 319             }
 320         }
 321         //@endcond
 322
 323     private:
 324         //@cond
 325         bool collide( fc_record& rec1, fc_record& rec2 )
 326         {
 327             switch ( rec1.op() ) {
 328                 case op_push:
 329                     if ( rec2.op() == op_pop ) {
 330                         assert(rec1.pValPush);
 331                         assert(rec2.pValPop);
 332                         *rec2.pValPop = *rec1.pValPush;
 333                         rec2.bEmpty = false;
 334                         goto collided;
 335                     }
 336                     break;
 337 #       ifdef CDS_MOVE_SEMANTICS_SUPPORT
 338                 case op_push_move:
 339                     if ( rec2.op() == op_pop ) {
 340                         assert(rec1.pValPush);
 341                         assert(rec2.pValPop);
 342                         *rec2.pValPop = std::move( *rec1.pValPush );
 343                         rec2.bEmpty = false;
 344                         goto collided;
 345                     }
 346                     break;
 347 #       endif
 348                 case op_pop:
 349                     switch ( rec2.op() ) {
 350                     case op_push:
 351 #       ifdef CDS_MOVE_SEMANTICS_SUPPORT
 352                     case op_push_move:
 353 #       endif
 354                         return collide( rec2, rec1 );
 355                     }
 356             }
 357             return false;
 358
 359         collided:
 360             m_FlatCombining.operation_done( rec1 );
 361             m_FlatCombining.operation_done( rec2 );
 362             m_FlatCombining.internal_statistics().onCollide();
 363             return true;
 364         }
 365         //@endcond
 366     };
 367 }} // namespace cds::container
 368
 369 #endif // #ifndef __CDS_CONTAINER_FCSTACK_H