cds/intrusive/fcstack.h

   1 //$$CDS-header$$
   2
   3 #ifndef __CDS_INTRUSIVE_FCSTACK_H
   4 #define __CDS_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 type_traits: public cds::algo::flat_combining::type_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             This is a wrapper for <tt> cds::opt::make_options< type_traits, Options...> </tt>
  56             \p Options are:
  57             - \p opt::lock_type - mutex type, default is \p cds::lock::Spin
  58             - \p opt::back_off - back-off strategy, defalt is \p cds::backoff::Default
  59             - \p opt::disposer - the functor used for dispose removed items. Default is opt::intrusive::v::empty_disposer.
  60                 This option is used only in \p FCStack::clear() function.
  61             - \p opt::allocator - allocator type, default is \ref CDS_DEFAULT_ALLOCATOR
  62             - \p opt::stat - internal statistics, possible type: \ref stat, \ref empty_stat (the default)
  63             - \p opt::memory_model - C++ memory ordering model.
  64                 List of all available memory ordering see opt::memory_model.
  65                 Default if 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 <CDS_DECL_OPTIONS8>
  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< type_traits, CDS_OPTIONS8 >::type
  76                 ,CDS_OPTIONS8
  77             >::type   type;
  78 #   endif
  79         };
  80
  81     } // namespace fcstack
  82
  83     /// Flat-combining intrusive stack
  84     /**
  85         @ingroup cds_intrusive_stack
  86         @ingroup cds_flat_combining_intrusive
  87
  88         \ref cds_flat_combining_description "Flat combining" sequential intrusive stack.
  89
  90         Template parameters:
  91         - \p T - a value type stored in the stack
  92         - \p Container - sequential intrusive container with \p push_front and \p pop_front functions.
  93             Possible containers are \p boost::intrusive::slist (the default), \p boost::inrtrusive::list
  94         - \p Traits - 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 Container = boost::intrusive::slist<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 Container   container_type; ///< Sequential container type
 109         typedef Traits      type_traits;    ///< Stack type traits
 110
 111         typedef typename type_traits::disposer  disposer;   ///< The disposer functor. The disposer is used only in \ref clear() function
 112         typedef typename type_traits::stat  stat;   ///< Internal statistics type
 113         static CDS_CONSTEXPR_CONST bool c_bEliminationEnabled = type_traits::enable_elimination; ///< \p true if elimination is enabled
 114
 115     protected:
 116         //@cond
 117         /// Stack operation IDs
 118         enum fc_operation {
 119             op_push = cds::algo::flat_combining::req_Operation, ///< Push
 120             op_pop,                 ///< Pop
 121             op_clear,               ///< Clear
 122             op_clear_and_dispose    ///< Clear and dispose
 123         };
 124
 125         /// Flat combining publication list record
 126         struct fc_record: public cds::algo::flat_combining::publication_record
 127         {
 128             value_type * pVal;  ///< Value to push or pop
 129             bool         bEmpty; ///< \p true if the stack is empty
 130         };
 131         //@endcond
 132
 133         /// Flat combining kernel
 134         typedef cds::algo::flat_combining::kernel< fc_record, type_traits > fc_kernel;
 135
 136     protected:
 137         //@cond
 138         fc_kernel       m_FlatCombining;
 139         container_type  m_Stack;
 140         //@endcond
 141
 142     public:
 143         /// Initializes empty stack object
 144         FCStack()
 145         {}
 146
 147         /// Initializes empty stack object and gives flat combining parameters
 148         FCStack(
 149             unsigned int nCompactFactor     ///< Flat combining: publication list compacting factor
 150             ,unsigned int nCombinePassCount ///< Flat combining: number of combining passes for combiner thread
 151             )
 152             : m_FlatCombining( nCompactFactor, nCombinePassCount )
 153         {}
 154
 155         /// Inserts a new element at the top of stack
 156         /**
 157             The content of the new element initialized to a copy of \p val.
 158         */
 159         bool push( value_type& val )
 160         {
 161             fc_record * pRec = m_FlatCombining.acquire_record();
 162             pRec->pVal = &val;
 163
 164             if ( c_bEliminationEnabled )
 165                 m_FlatCombining.batch_combine( op_push, pRec, *this );
 166             else
 167                 m_FlatCombining.combine( op_push, pRec, *this );
 168
 169             assert( pRec->is_done() );
 170             m_FlatCombining.release_record( pRec );
 171             m_FlatCombining.internal_statistics().onPush();
 172             return true;
 173         }
 174
 175         /// Removes the element on top of the stack
 176         value_type * pop()
 177         {
 178             fc_record * pRec = m_FlatCombining.acquire_record();
 179             pRec->pVal = null_ptr<value_type *>();
 180
 181             if ( c_bEliminationEnabled )
 182                 m_FlatCombining.batch_combine( op_pop, pRec, *this );
 183             else
 184                 m_FlatCombining.combine( op_pop, pRec, *this );
 185
 186             assert( pRec->is_done() );
 187             m_FlatCombining.release_record( pRec );
 188
 189             m_FlatCombining.internal_statistics().onPop( pRec->bEmpty );
 190             return pRec->pVal;
 191         }
 192
 193         /// Clears the stack
 194         /**
 195             If \p bDispose is \p true, the disposer provided in \p Traits class' template parameter
 196             will be called for each removed element.
 197         */
 198         void clear( bool bDispose = false )
 199         {
 200             fc_record * pRec = m_FlatCombining.acquire_record();
 201
 202             if ( c_bEliminationEnabled )
 203                 m_FlatCombining.batch_combine( bDispose ? op_clear_and_dispose : op_clear, pRec, *this );
 204             else
 205                 m_FlatCombining.combine( bDispose ? op_clear_and_dispose : op_clear, pRec, *this );
 206
 207             assert( pRec->is_done() );
 208             m_FlatCombining.release_record( pRec );
 209         }
 210
 211         /// Returns the number of elements in the stack.
 212         /**
 213             Note that <tt>size() == 0</tt> is not mean that the stack is empty because
 214             combining record can be in process.
 215             To check emptiness use \ref empty function.
 216         */
 217         size_t size() const
 218         {
 219             return m_Stack.size();
 220         }
 221
 222         /// Checks if the stack is empty
 223         /**
 224             If the combining is in process the function waits while it is done.
 225         */
 226         bool empty() const
 227         {
 228             m_FlatCombining.wait_while_combining();
 229             return m_Stack.empty();
 230         }
 231
 232         /// Internal statistics
 233         stat const& statistics() const
 234         {
 235             return m_FlatCombining.statistics();
 236         }
 237
 238
 239     public: // flat combining cooperation, not for direct use!
 240         //@cond
 241         /// Flat combining supporting function. Do not call it directly!
 242         /**
 243             The function is called by \ref cds::algo::flat_combining::kernel "flat combining kernel"
 244             object if the current thread becomes a combiner. Invocation of the function means that
 245             the stack should perform an action recorded in \p pRec.
 246         */
 247         void fc_apply( fc_record * pRec )
 248         {
 249             assert( pRec );
 250
 251             switch ( pRec->op() ) {
 252             case op_push:
 253                 assert( pRec->pVal );
 254                 m_Stack.push_front( *(pRec->pVal ) );
 255                 break;
 256             case op_pop:
 257                 pRec->bEmpty = m_Stack.empty();
 258                 if ( !pRec->bEmpty ) {
 259                     pRec->pVal = &m_Stack.front();
 260                     m_Stack.pop_front();
 261                 }
 262                 break;
 263             case op_clear:
 264                 m_Stack.clear();
 265                 break;
 266             case op_clear_and_dispose:
 267                 m_Stack.clear_and_dispose( disposer() );
 268                 break;
 269             default:
 270                 assert(false);
 271                 break;
 272             }
 273         }
 274
 275         /// Batch-processing flat combining
 276         void fc_process( typename fc_kernel::iterator itBegin, typename fc_kernel::iterator itEnd )
 277         {
 278             typedef typename fc_kernel::iterator fc_iterator;
 279             for ( fc_iterator it = itBegin, itPrev = itEnd; it != itEnd; ++it ) {
 280                 switch ( it->op() ) {
 281                 case op_push:
 282                 case op_pop:
 283                     if ( itPrev != itEnd && collide( *itPrev, *it ))
 284                         itPrev = itEnd;
 285                     else
 286                         itPrev = it;
 287                     break;
 288                 }
 289             }
 290         }
 291         //@endcond
 292
 293     private:
 294         //@cond
 295         bool collide( fc_record& rec1, fc_record& rec2 )
 296         {
 297             switch ( rec1.op() ) {
 298                 case op_push:
 299                     if ( rec2.op() == op_pop ) {
 300                         assert(rec1.pVal);
 301                         rec2.pVal = rec1.pVal;
 302                         rec2.bEmpty = false;
 303                         m_FlatCombining.operation_done( rec1 );
 304                         m_FlatCombining.operation_done( rec2 );
 305                         m_FlatCombining.internal_statistics().onCollide();
 306                         return true;
 307                     }
 308                     break;
 309                 case op_pop:
 310                     if ( rec2.op() == op_push ) {
 311                         assert(rec2.pVal);
 312                         rec1.pVal = rec2.pVal;
 313                         rec1.bEmpty = false;
 314                         m_FlatCombining.operation_done( rec1 );
 315                         m_FlatCombining.operation_done( rec2 );
 316                         m_FlatCombining.internal_statistics().onCollide();
 317                         return true;
 318                     }
 319                     break;
 320             }
 321             return false;
 322         }
 323         //@endcond
 324
 325     };
 326
 327 }} // namespace cds::intrusive
 328
 329 #endif // #ifndef __CDS_INTRUSIVE_FCSTACK_H