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 <typename... Options>
  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, Options... >::type
  77                 ,Options...
  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         /// Inserts a new element at the top of stack (move semantics)
 178         /**
 179             The content of the new element initialized to a copy of \p val.
 180         */
 181         bool push( value_type&& val )
 182         {
 183             fc_record * pRec = m_FlatCombining.acquire_record();
 184             pRec->pValPush = &val;
 185
 186             if ( c_bEliminationEnabled )
 187                 m_FlatCombining.batch_combine( op_push_move, pRec, *this );
 188             else
 189                 m_FlatCombining.combine( op_push_move, pRec, *this );
 190
 191             assert( pRec->is_done() );
 192             m_FlatCombining.release_record( pRec );
 193
 194             m_FlatCombining.internal_statistics().onPushMove();
 195             return true;
 196         }
 197
 198         /// Removes the element on top of the stack
 199         /**
 200             \p val takes a copy of top element
 201         */
 202         bool pop( value_type& val )
 203         {
 204             fc_record * pRec = m_FlatCombining.acquire_record();
 205             pRec->pValPop = &val;
 206
 207             if ( c_bEliminationEnabled )
 208                 m_FlatCombining.batch_combine( op_pop, pRec, *this );
 209             else
 210                 m_FlatCombining.combine( op_pop, pRec, *this );
 211
 212             assert( pRec->is_done() );
 213             m_FlatCombining.release_record( pRec );
 214
 215             m_FlatCombining.internal_statistics().onPop( pRec->bEmpty );
 216             return !pRec->bEmpty;
 217         }
 218
 219         /// Clears the stack
 220         void clear()
 221         {
 222             fc_record * pRec = m_FlatCombining.acquire_record();
 223
 224             if ( c_bEliminationEnabled )
 225                 m_FlatCombining.batch_combine( op_clear, pRec, *this );
 226             else
 227                 m_FlatCombining.combine( op_clear, pRec, *this );
 228
 229             assert( pRec->is_done() );
 230             m_FlatCombining.release_record( pRec );
 231         }
 232
 233         /// Returns the number of elements in the stack.
 234         /**
 235             Note that <tt>size() == 0</tt> is not mean that the stack is empty because
 236             combining record can be in process.
 237             To check emptiness use \ref empty function.
 238         */
 239         size_t size() const
 240         {
 241             return m_Stack.size();
 242         }
 243
 244         /// Checks if the stack is empty
 245         /**
 246             If the combining is in process the function waits while combining done.
 247         */
 248         bool empty() const
 249         {
 250             m_FlatCombining.wait_while_combining();
 251             return m_Stack.empty();
 252         }
 253
 254         /// Internal statistics
 255         stat const& statistics() const
 256         {
 257             return m_FlatCombining.statistics();
 258         }
 259
 260
 261     public: // flat combining cooperation, not for direct use!
 262         //@cond
 263         /// Flat combining supporting function. Do not call it directly!
 264         /**
 265             The function is called by \ref cds::algo::flat_combining::kernel "flat combining kernel"
 266             object if the current thread becomes a combiner. Invocation of the function means that
 267             the stack should perform an action recorded in \p pRec.
 268         */
 269         void fc_apply( fc_record * pRec )
 270         {
 271             assert( pRec );
 272
 273             switch ( pRec->op() ) {
 274             case op_push:
 275                 assert( pRec->pValPush );
 276                 m_Stack.push( *(pRec->pValPush ) );
 277                 break;
 278             case op_push_move:
 279                 assert( pRec->pValPush );
 280                 m_Stack.push( std::move( *(pRec->pValPush )) );
 281                 break;
 282             case op_pop:
 283                 assert( pRec->pValPop );
 284                 pRec->bEmpty = m_Stack.empty();
 285                 if ( !pRec->bEmpty ) {
 286                     *(pRec->pValPop) = m_Stack.top();
 287                     m_Stack.pop();
 288                 }
 289                 break;
 290             case op_clear:
 291                 while ( !m_Stack.empty() )
 292                     m_Stack.pop();
 293                 break;
 294             default:
 295                 assert(false);
 296                 break;
 297             }
 298         }
 299
 300         /// Batch-processing flat combining
 301         void fc_process( typename fc_kernel::iterator itBegin, typename fc_kernel::iterator itEnd )
 302         {
 303             typedef typename fc_kernel::iterator fc_iterator;
 304             for ( fc_iterator it = itBegin, itPrev = itEnd; it != itEnd; ++it ) {
 305                 switch ( it->op() ) {
 306                 case op_push:
 307                 case op_push_move:
 308                 case op_pop:
 309                     if ( itPrev != itEnd && collide( *itPrev, *it ))
 310                         itPrev = itEnd;
 311                     else
 312                         itPrev = it;
 313                     break;
 314                 }
 315             }
 316         }
 317         //@endcond
 318
 319     private:
 320         //@cond
 321         bool collide( fc_record& rec1, fc_record& rec2 )
 322         {
 323             switch ( rec1.op() ) {
 324                 case op_push:
 325                     if ( rec2.op() == op_pop ) {
 326                         assert(rec1.pValPush);
 327                         assert(rec2.pValPop);
 328                         *rec2.pValPop = *rec1.pValPush;
 329                         rec2.bEmpty = false;
 330                         goto collided;
 331                     }
 332                     break;
 333                 case op_push_move:
 334                     if ( rec2.op() == op_pop ) {
 335                         assert(rec1.pValPush);
 336                         assert(rec2.pValPop);
 337                         *rec2.pValPop = std::move( *rec1.pValPush );
 338                         rec2.bEmpty = false;
 339                         goto collided;
 340                     }
 341                     break;
 342                 case op_pop:
 343                     switch ( rec2.op() ) {
 344                     case op_push:
 345                     case op_push_move:
 346                         return collide( rec2, rec1 );
 347                     }
 348             }
 349             return false;
 350
 351         collided:
 352             m_FlatCombining.operation_done( rec1 );
 353             m_FlatCombining.operation_done( rec2 );
 354             m_FlatCombining.internal_statistics().onCollide();
 355             return true;
 356         }
 357         //@endcond
 358     };
 359 }} // namespace cds::container
 360
 361 #endif // #ifndef __CDS_CONTAINER_FCSTACK_H