cds/intrusive/fcstack.h

   1 /*
   2     This file is a part of libcds - Concurrent Data Structures library
   3
   4     (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017
   5
   6     Source code repo: http://github.com/khizmax/libcds/
   7     Download: http://sourceforge.net/projects/libcds/files/
   8
   9     Redistribution and use in source and binary forms, with or without
  10     modification, are permitted provided that the following conditions are met:
  11
  12     * Redistributions of source code must retain the above copyright notice, this
  13       list of conditions and the following disclaimer.
  14
  15     * Redistributions in binary form must reproduce the above copyright notice,
  16       this list of conditions and the following disclaimer in the documentation
  17       and/or other materials provided with the distribution.
  18
  19     THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  20     AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  21     IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  22     DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
  23     FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  24     DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
  25     SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  26     CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  27     OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  28     OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  29 */
  30
  31 #ifndef CDSLIB_INTRUSIVE_FCSTACK_H
  32 #define CDSLIB_INTRUSIVE_FCSTACK_H
  33
  34 #include <cds/algo/flat_combining.h>
  35 #include <cds/algo/elimination_opt.h>
  36 #include <cds/intrusive/options.h>
  37 #include <boost/intrusive/slist.hpp>
  38
  39 namespace cds { namespace intrusive {
  40
  41     /// FCStack related definitions
  42     namespace fcstack {
  43
  44         /// FCStack internal statistics
  45         template <typename Counter = cds::atomicity::event_counter >
  46         struct stat: public cds::algo::flat_combining::stat<Counter>
  47         {
  48             typedef cds::algo::flat_combining::stat<Counter>    flat_combining_stat; ///< Flat-combining statistics
  49             typedef typename flat_combining_stat::counter_type  counter_type;        ///< Counter type
  50
  51             counter_type    m_nPush     ;   ///< Count of push operations
  52             counter_type    m_nPop      ;   ///< Count of success pop operations
  53             counter_type    m_nFailedPop;   ///< Count of failed pop operations (pop from empty stack)
  54             counter_type    m_nCollided ;   ///< How many pairs of push/pop were collided, if elimination is enabled
  55
  56             //@cond
  57             void    onPush()               { ++m_nPush; }
  58             void    onPop( bool bFailed )  { if ( bFailed ) ++m_nFailedPop; else ++m_nPop;  }
  59             void    onCollide()            { ++m_nCollided; }
  60             //@endcond
  61         };
  62
  63         /// FCStack dummy statistics, no overhead
  64         struct empty_stat: public cds::algo::flat_combining::empty_stat
  65         {
  66             //@cond
  67             void    onPush()        {}
  68             void    onPop(bool)     {}
  69             void    onCollide()     {}
  70             //@endcond
  71         };
  72
  73         /// FCStack type traits
  74         struct traits: public cds::algo::flat_combining::traits
  75         {
  76             typedef cds::intrusive::opt::v::empty_disposer  disposer ; ///< Disposer to erase removed elements. Used only in \p FCStack::clear() function
  77             typedef empty_stat      stat;   ///< Internal statistics
  78             static CDS_CONSTEXPR const bool enable_elimination = false; ///< Enable \ref cds_elimination_description "elimination"
  79         };
  80
  81         /// Metafunction converting option list to traits
  82         /**
  83             \p Options are:
  84             - any \p cds::algo::flat_combining::make_traits options
  85             - \p opt::disposer - the functor used for dispose removed items. Default is \p opt::intrusive::v::empty_disposer.
  86                 This option is used only in \p FCStack::clear() function.
  87             - \p opt::stat - internal statistics, possible type: \p fcstack::stat, \p fcstack::empty_stat (the default)
  88             - \p opt::enable_elimination - enable/disable operation \ref cds_elimination_description "elimination"
  89                 By default, the elimination is disabled.
  90         */
  91         template <typename... Options>
  92         struct make_traits {
  93 #   ifdef CDS_DOXYGEN_INVOKED
  94             typedef implementation_defined type ;   ///< Metafunction result
  95 #   else
  96             typedef typename cds::opt::make_options<
  97                 typename cds::opt::find_type_traits< traits, Options... >::type
  98                 ,Options...
  99             >::type   type;
 100 #   endif
 101         };
 102
 103     } // namespace fcstack
 104
 105     /// Flat-combining intrusive stack
 106     /**
 107         @ingroup cds_intrusive_stack
 108         @ingroup cds_flat_combining_intrusive
 109
 110         \ref cds_flat_combining_description "Flat combining" sequential intrusive stack.
 111
 112         Template parameters:
 113         - \p T - a value type stored in the stack
 114         - \p Container - sequential intrusive container with \p push_front and \p pop_front functions.
 115             Possible containers are \p boost::intrusive::slist (the default), \p boost::inrtrusive::list
 116         - \p Traits - type traits of flat combining, default is \p fcstack::traits.
 117             \p fcstack::make_traits metafunction can be used to construct specialized \p %traits
 118     */
 119     template <typename T
 120         ,class Container = boost::intrusive::slist<T>
 121         ,typename Traits = fcstack::traits
 122     >
 123     class FCStack
 124 #ifndef CDS_DOXYGEN_INVOKED
 125         : public cds::algo::flat_combining::container
 126 #endif
 127     {
 128     public:
 129         typedef T           value_type;     ///< Value type
 130         typedef Container   container_type; ///< Sequential container type
 131         typedef Traits      traits;         ///< Stack traits
 132
 133         typedef typename traits::disposer  disposer;   ///< The disposer functor. The disposer is used only in \ref clear() function
 134         typedef typename traits::stat  stat;   ///< Internal statistics type
 135         static CDS_CONSTEXPR const bool c_bEliminationEnabled = traits::enable_elimination; ///< \p true if elimination is enabled
 136
 137     protected:
 138         //@cond
 139         /// Stack operation IDs
 140         enum fc_operation {
 141             op_push = cds::algo::flat_combining::req_Operation, ///< Push
 142             op_pop,                 ///< Pop
 143             op_clear,               ///< Clear
 144             op_clear_and_dispose    ///< Clear and dispose
 145         };
 146
 147         /// Flat combining publication list record
 148         struct fc_record: public cds::algo::flat_combining::publication_record
 149         {
 150             value_type * pVal;  ///< Value to push or pop
 151             bool         bEmpty; ///< \p true if the stack is empty
 152         };
 153         //@endcond
 154
 155         /// Flat combining kernel
 156         typedef cds::algo::flat_combining::kernel< fc_record, traits > fc_kernel;
 157
 158     protected:
 159         //@cond
 160         mutable fc_kernel m_FlatCombining;
 161         container_type    m_Stack;
 162         //@endcond
 163
 164     public:
 165         /// Initializes empty stack object
 166         FCStack()
 167         {}
 168
 169         /// Initializes empty stack object and gives flat combining parameters
 170         FCStack(
 171             unsigned int nCompactFactor     ///< Flat combining: publication list compacting factor
 172             ,unsigned int nCombinePassCount ///< Flat combining: number of combining passes for combiner thread
 173             )
 174             : m_FlatCombining( nCompactFactor, nCombinePassCount )
 175         {}
 176
 177         /// Inserts a new element at the top of stack
 178         /**
 179             The content of the new element initialized to a copy of \p val.
 180         */
 181         bool push( value_type& val )
 182         {
 183             auto pRec = m_FlatCombining.acquire_record();
 184             pRec->pVal = &val;
 185
 186             if ( c_bEliminationEnabled )
 187                 m_FlatCombining.batch_combine( op_push, pRec, *this );
 188             else
 189                 m_FlatCombining.combine( op_push, pRec, *this );
 190
 191             assert( pRec->is_done());
 192             m_FlatCombining.release_record( pRec );
 193             m_FlatCombining.internal_statistics().onPush();
 194             return true;
 195         }
 196
 197         /// Removes the element on top of the stack
 198         value_type * pop()
 199         {
 200             auto pRec = m_FlatCombining.acquire_record();
 201             pRec->pVal = nullptr;
 202
 203             if ( c_bEliminationEnabled )
 204                 m_FlatCombining.batch_combine( op_pop, pRec, *this );
 205             else
 206                 m_FlatCombining.combine( op_pop, pRec, *this );
 207
 208             assert( pRec->is_done());
 209             m_FlatCombining.release_record( pRec );
 210
 211             m_FlatCombining.internal_statistics().onPop( pRec->bEmpty );
 212             return pRec->pVal;
 213         }
 214
 215         /// Clears the stack
 216         /**
 217             If \p bDispose is \p true, the disposer provided in \p Traits class' template parameter
 218             will be called for each removed element.
 219         */
 220         void clear( bool bDispose = false )
 221         {
 222             auto pRec = m_FlatCombining.acquire_record();
 223
 224             if ( c_bEliminationEnabled )
 225                 m_FlatCombining.batch_combine( bDispose ? op_clear_and_dispose : op_clear, pRec, *this );
 226             else
 227                 m_FlatCombining.combine( bDispose ? op_clear_and_dispose : 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 it is done.
 247         */
 248         bool empty() const
 249         {
 250             bool bRet = false;
 251             auto const& stack = m_Stack;
 252             m_FlatCombining.invoke_exclusive( [&stack, &bRet]() { bRet = stack.empty(); } );
 253             return bRet;
 254         }
 255
 256         /// Internal statistics
 257         stat const& statistics() const
 258         {
 259             return m_FlatCombining.statistics();
 260         }
 261
 262
 263     public: // flat combining cooperation, not for direct use!
 264         //@cond
 265         /// Flat combining supporting function. Do not call it directly!
 266         /**
 267             The function is called by \ref cds::algo::flat_combining::kernel "flat combining kernel"
 268             object if the current thread becomes a combiner. Invocation of the function means that
 269             the stack should perform an action recorded in \p pRec.
 270         */
 271         void fc_apply( fc_record* pRec )
 272         {
 273             assert( pRec );
 274
 275             // this function is called under FC mutex, so switch TSan off
 276             CDS_TSAN_ANNOTATE_IGNORE_RW_BEGIN;
 277             switch ( pRec->op()) {
 278             case op_push:
 279                 assert( pRec->pVal );
 280                 m_Stack.push_front( *(pRec->pVal ));
 281                 break;
 282             case op_pop:
 283                 pRec->bEmpty = m_Stack.empty();
 284                 if ( !pRec->bEmpty ) {
 285                     pRec->pVal = &m_Stack.front();
 286                     m_Stack.pop_front();
 287                 }
 288                 break;
 289             case op_clear:
 290                 m_Stack.clear();
 291                 break;
 292             case op_clear_and_dispose:
 293                 m_Stack.clear_and_dispose( disposer());
 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_pop:
 313                     if ( itPrev != itEnd && collide( *itPrev, *it ))
 314                         itPrev = itEnd;
 315                     else
 316                         itPrev = it;
 317                     break;
 318                 }
 319             }
 320             CDS_TSAN_ANNOTATE_IGNORE_RW_END;
 321         }
 322         //@endcond
 323
 324     private:
 325         //@cond
 326         bool collide( fc_record& rec1, fc_record& rec2 )
 327         {
 328             switch ( rec1.op()) {
 329                 case op_push:
 330                     if ( rec2.op() == op_pop ) {
 331                         assert(rec1.pVal);
 332                         rec2.pVal = rec1.pVal;
 333                         rec2.bEmpty = false;
 334                         m_FlatCombining.operation_done( rec1 );
 335                         m_FlatCombining.operation_done( rec2 );
 336                         m_FlatCombining.internal_statistics().onCollide();
 337                         return true;
 338                     }
 339                     break;
 340                 case op_pop:
 341                     if ( rec2.op() == op_push ) {
 342                         assert(rec2.pVal);
 343                         rec1.pVal = rec2.pVal;
 344                         rec1.bEmpty = false;
 345                         m_FlatCombining.operation_done( rec1 );
 346                         m_FlatCombining.operation_done( rec2 );
 347                         m_FlatCombining.internal_statistics().onCollide();
 348                         return true;
 349                     }
 350                     break;
 351             }
 352             return false;
 353         }
 354         //@endcond
 355
 356     };
 357
 358 }} // namespace cds::intrusive
 359
 360 #endif // #ifndef CDSLIB_INTRUSIVE_FCSTACK_H