cds/intrusive/fcstack.h

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