cds/container/fcstack.h

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