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             op_empty        ///< Empty
 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, 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()
 249         {
 250             fc_record * pRec = m_FlatCombining.acquire_record();
 251
 252             if ( c_bEliminationEnabled )
 253                 m_FlatCombining.batch_combine( op_empty, pRec, *this );
 254             else
 255                 m_FlatCombining.combine( op_empty, pRec, *this );
 256
 257             assert( pRec->is_done() );
 258             m_FlatCombining.release_record( pRec );
 259             return pRec->bEmpty;
 260         }
 261
 262         /// Internal statistics
 263         stat const& statistics() const
 264         {
 265             return m_FlatCombining.statistics();
 266         }
 267
 268
 269     public: // flat combining cooperation, not for direct use!
 270         //@cond
 271         /// Flat combining supporting function. Do not call it directly!
 272         /**
 273             The function is called by \ref cds::algo::flat_combining::kernel "flat combining kernel"
 274             object if the current thread becomes a combiner. Invocation of the function means that
 275             the stack should perform an action recorded in \p pRec.
 276         */
 277         void fc_apply( fc_record * pRec )
 278         {
 279             assert( pRec );
 280
 281             // this function is called under FC mutex, so switch TSan off
 282             CDS_TSAN_ANNOTATE_IGNORE_RW_BEGIN;
 283             switch ( pRec->op() ) {
 284             case op_push:
 285                 assert( pRec->pValPush );
 286                 m_Stack.push( *(pRec->pValPush ) );
 287                 break;
 288             case op_push_move:
 289                 assert( pRec->pValPush );
 290                 m_Stack.push( std::move( *(pRec->pValPush )) );
 291                 break;
 292             case op_pop:
 293                 assert( pRec->pValPop );
 294                 pRec->bEmpty = m_Stack.empty();
 295                 if ( !pRec->bEmpty ) {
 296                     *(pRec->pValPop) = m_Stack.top();
 297                     m_Stack.pop();
 298                 }
 299                 break;
 300             case op_clear:
 301                 while ( !m_Stack.empty() )
 302                     m_Stack.pop();
 303                 break;
 304             case op_empty:
 305                 pRec->bEmpty = m_Stack.empty();
 306                 break;
 307             default:
 308                 assert(false);
 309                 break;
 310             }
 311             CDS_TSAN_ANNOTATE_IGNORE_RW_END;
 312         }
 313
 314         /// Batch-processing flat combining
 315         void fc_process( typename fc_kernel::iterator itBegin, typename fc_kernel::iterator itEnd )
 316         {
 317             // this function is called under FC mutex, so switch TSan off
 318             CDS_TSAN_ANNOTATE_IGNORE_RW_BEGIN;
 319
 320             typedef typename fc_kernel::iterator fc_iterator;
 321             for ( fc_iterator it = itBegin, itPrev = itEnd; it != itEnd; ++it ) {
 322                 switch ( it->op() ) {
 323                 case op_push:
 324                 case op_push_move:
 325                 case op_pop:
 326                     if ( itPrev != itEnd && collide( *itPrev, *it ))
 327                         itPrev = itEnd;
 328                     else
 329                         itPrev = it;
 330                     break;
 331                 }
 332             }
 333             CDS_TSAN_ANNOTATE_IGNORE_RW_END;
 334         }
 335         //@endcond
 336
 337     private:
 338         //@cond
 339         bool collide( fc_record& rec1, fc_record& rec2 )
 340         {
 341             switch ( rec1.op() ) {
 342                 case op_push:
 343                     if ( rec2.op() == op_pop ) {
 344                         assert(rec1.pValPush);
 345                         assert(rec2.pValPop);
 346                         *rec2.pValPop = *rec1.pValPush;
 347                         rec2.bEmpty = false;
 348                         goto collided;
 349                     }
 350                     break;
 351                 case op_push_move:
 352                     if ( rec2.op() == op_pop ) {
 353                         assert(rec1.pValPush);
 354                         assert(rec2.pValPop);
 355                         *rec2.pValPop = std::move( *rec1.pValPush );
 356                         rec2.bEmpty = false;
 357                         goto collided;
 358                     }
 359                     break;
 360                 case op_pop:
 361                     switch ( rec2.op() ) {
 362                     case op_push:
 363                     case op_push_move:
 364                         return collide( rec2, rec1 );
 365                     }
 366             }
 367             return false;
 368
 369         collided:
 370             m_FlatCombining.operation_done( rec1 );
 371             m_FlatCombining.operation_done( rec2 );
 372             m_FlatCombining.internal_statistics().onCollide();
 373             return true;
 374         }
 375         //@endcond
 376     };
 377 }} // namespace cds::container
 378
 379 #endif // #ifndef CDSLIB_CONTAINER_FCSTACK_H