Changed default back-off strategy

[libcds.git] / cds / container / treiber_stack.h

diff --git a/cds/container/treiber_stack.h b/cds/container/treiber_stack.h
index 32954b7e11c32ce53a846fe79087c0e8f91bef06..a559d0cb6d55a8a2826e318069ac054213cef1fd 100644 (file)
--- a/cds/container/treiber_stack.h
+++ b/cds/container/treiber_stack.h
@@ -1,7 +1,35 @@
-//$$CDS-header$$
+/*
+    This file is a part of libcds - Concurrent Data Structures library

 
 

-#ifndef __CDS_CONTAINER_TREIBER_STACK_H
-#define __CDS_CONTAINER_TREIBER_STACK_H
+    (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017
+
+    Source code repo: http://github.com/khizmax/libcds/
+    Download: http://sourceforge.net/projects/libcds/files/
+
+    Redistribution and use in source and binary forms, with or without
+    modification, are permitted provided that the following conditions are met:
+
+    * Redistributions of source code must retain the above copyright notice, this
+      list of conditions and the following disclaimer.
+
+    * Redistributions in binary form must reproduce the above copyright notice,
+      this list of conditions and the following disclaimer in the documentation
+      and/or other materials provided with the distribution.
+
+    THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+    AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+    IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+    DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+    FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+    DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+    SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+    CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
+    OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+*/
+
+#ifndef CDSLIB_CONTAINER_TREIBER_STACK_H
+#define CDSLIB_CONTAINER_TREIBER_STACK_H

 
 #include <memory>   // unique_ptr
 #include <cds/intrusive/treiber_stack.h>
 
 #include <memory>   // unique_ptr
 #include <cds/intrusive/treiber_stack.h>


@@ -9,10 +37,13 @@
 
 namespace cds { namespace container {
 
 
 namespace cds { namespace container {
 

+    /// TreiberStack related definitions
+    /** @ingroup cds_nonintrusive_helper
+    */

     namespace treiber_stack {
         /// Internal statistics
     namespace treiber_stack {
         /// Internal statistics

-        template <typename Counter = cds::atomicity::event_counter>
-        using stat = cds::intrusive::treiber_stack::stat < Counter >;
+        template <typename Counter = cds::intrusive::treiber_stack::stat<>::counter_type >
+        using stat = cds::intrusive::treiber_stack::stat< Counter >;

 
         /// Dummy internal statistics
         typedef cds::intrusive::treiber_stack::empty_stat empty_stat;
 
         /// Dummy internal statistics
         typedef cds::intrusive::treiber_stack::empty_stat empty_stat;


@@ -33,15 +64,15 @@ namespace cds { namespace container {
             */
             typedef opt::v::relaxed_ordering    memory_model;
 
             */
             typedef opt::v::relaxed_ordering    memory_model;
 

-            /// Item counting feature; by default, disabled
+            /// Item counting feature; by default, disabled. Use \p cds::atomicity::item_counter to enable item counting

             typedef cds::atomicity::empty_item_counter  item_counter;
 
             /// Internal statistics (by default, no internal statistics)
             /**
             typedef cds::atomicity::empty_item_counter  item_counter;
 
             /// Internal statistics (by default, no internal statistics)
             /**

-                Possible option value are: \ref treiber_stack::stat, \ref treiber_stack::empty_stat (the default),
+                Possible types are: \ref treiber_stack::stat, \ref treiber_stack::empty_stat (the default),

                 user-provided class that supports treiber_stack::stat interface.
             */
                 user-provided class that supports treiber_stack::stat interface.
             */

-            typedef empty_stat                          stat;
+            typedef empty_stat stat;

 
             /** @name Elimination back-off traits
                 The following traits is used only if elimination enabled
 
             /** @name Elimination back-off traits
                 The following traits is used only if elimination enabled


@@ -49,52 +80,62 @@ namespace cds { namespace container {
             ///@{
 
             /// Enable elimination back-off; by default, it is disabled
             ///@{
 
             /// Enable elimination back-off; by default, it is disabled

-            static CDS_CONSTEXPR_CONST bool enable_elimination = false;
+            static CDS_CONSTEXPR const bool enable_elimination = false;

 
             /// Back-off strategy to wait for elimination, default is cds::backoff::delay<>
             typedef cds::backoff::delay<>          elimination_backoff;
 
             /// Buffer type for elimination array
             /**
 
             /// Back-off strategy to wait for elimination, default is cds::backoff::delay<>
             typedef cds::backoff::delay<>          elimination_backoff;
 
             /// Buffer type for elimination array
             /**

-                Possible types are \p opt::v::static_buffer, \p opt::v::dynamic_buffer.
+                Possible types are \p opt::v::initialized_static_buffer, \p opt::v::initialized_dynamic_buffer.

                 The buffer can be any size: \p Exp2 template parameter of those classes can be \p false.
                 The size should be selected empirically for your application and hardware, there are no common rules for that.
                 The buffer can be any size: \p Exp2 template parameter of those classes can be \p false.
                 The size should be selected empirically for your application and hardware, there are no common rules for that.

-                Default is <tt> %opt::v::static_buffer< any_type, 4 > </tt>.
+                Default is <tt> %opt::v::initialized_static_buffer< any_type, 4 > </tt>.

             */
             */

-            typedef opt::v::static_buffer< int, 4 > buffer;
+            typedef opt::v::initialized_static_buffer< int, 4 > buffer;

 
             /// Random engine to generate a random position in elimination array
             typedef opt::v::c_rand  random_engine;
 
 
             /// Random engine to generate a random position in elimination array
             typedef opt::v::c_rand  random_engine;
 

-            /// Lock type used in elimination, default is cds::lock::Spin
-            typedef cds::lock::Spin lock_type;
+            /// Lock type used in elimination, default is cds::sync::spin
+            typedef cds::sync::spin lock_type;

 
             ///@}
         };
 
         /// Metafunction converting option list to \p TreiberStack traits
         /**
 
             ///@}
         };
 
         /// Metafunction converting option list to \p TreiberStack traits
         /**

-            This is a wrapper for <tt> cds::opt::make_options< type_traits, Options...> </tt>

             Supported \p Options are:
             Supported \p Options are:

-            - opt::allocator - allocator (like \p std::allocator) used for allocating stack nodes. Default is \ref CDS_DEFAULT_ALLOCATOR
-            - opt::back_off - back-off strategy used. If the option is not specified, the \p cds::backoff::Default is used.
-            - opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
+            - \p opt::allocator - allocator (like \p std::allocator) used for allocating stack nodes. Default is \ref CDS_DEFAULT_ALLOCATOR
+            - \p opt::back_off - back-off strategy used. If the option is not specified, the \p cds::backoff::Default is used.
+            - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)

                 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
                 or \p opt::v::sequential_consistent (sequentially consisnent memory model).

-            - opt::item_counter - the type of item counting feature. Default is \p cds::atomicity::empty_item_counter
-            - opt::stat - the type to gather internal statistics.
+            - \p opt::item_counter - the type of item counting feature. Default is \p cds::atomicity::empty_item_counter, i.e.
+                no item counting. Use \p cds::atomicity::item_counter to enable item counting.
+            - \p opt::stat - the type to gather internal statistics.

                 Possible option value are: \p treiber_stack::stat, \p treiber_stack::empty_stat (the default),
                 Possible option value are: \p treiber_stack::stat, \p treiber_stack::empty_stat (the default),

-                user-provided class that supports \p treiber_stack::stat interface.
-            - opt::enable_elimination - enable elimination back-off for the stack. Default value is \p false.
+                user-provided class that supports \p %treiber_stack::stat interface.
+            - \p opt::enable_elimination - enable elimination back-off for the stack. Default value is \p false.

 
             If elimination back-off is enabled, additional options can be specified:
 
             If elimination back-off is enabled, additional options can be specified:

-            - opt::buffer - a buffer type for elimination array, see \p opt::v::static_buffer, \p opt::v::dynamic_buffer.
+            - \p opt::buffer - an initialized buffer type for elimination array, see \p opt::v::initialized_static_buffer, \p opt::v::initialized_dynamic_buffer.

                 The buffer can be any size: \p Exp2 template parameter of those classes can be \p false.
                 The size should be selected empirically for your application and hardware, there are no common rules for that.
                 The buffer can be any size: \p Exp2 template parameter of those classes can be \p false.
                 The size should be selected empirically for your application and hardware, there are no common rules for that.

-                Default is <tt> %opt::v::static_buffer< any_type, 4 > </tt>.
-            - opt::random_engine - a random engine to generate a random position in elimination array.
+                Default is <tt> %opt::v::initialized_static_buffer< any_type, 4 > </tt>.
+            - \p opt::random_engine - a random engine to generate a random position in elimination array.

                 Default is \p opt::v::c_rand.
                 Default is \p opt::v::c_rand.

-            - opt::elimination_backoff - back-off strategy to wait for elimination, default is \p cds::backoff::delay<>
-            - opt::lock_type - a lock type used in elimination back-off, default is \p cds::lock::Spin.
+            - \p opt::elimination_backoff - back-off strategy to wait for elimination, default is \p cds::backoff::delay<>
+            - \p opt::lock_type - a lock type used in elimination back-off, default is \p cds::sync::spin.
+
+            Example: declare %TreiberStack with item counting and internal statistics using \p %make_traits
+            \code
+            typedef cds::container::TreiberStack< cds::gc::HP, Foo,
+                typename cds::container::treiber_stack::make_traits<
+                    cds::opt::item_counter< cds::atomicity::item_counter >,
+                    cds::opt::stat< cds::intrusive::treiber_stack::stat<> >
+                >::type
+            > myStack;
+            \endcode

         */
         template <typename... Options>
         struct make_traits {
         */
         template <typename... Options>
         struct make_traits {


@@ -147,14 +188,14 @@ namespace cds { namespace container {
             {
                 typedef cds::intrusive::treiber_stack::base_hook< cds::opt::gc<gc> > hook;
                 typedef node_deallocator disposer;
             {
                 typedef cds::intrusive::treiber_stack::base_hook< cds::opt::gc<gc> > hook;
                 typedef node_deallocator disposer;

-                static CDS_CONSTEXPR_CONST opt::link_check_type link_checker = cds::intrusive::treiber_stack::traits::link_checker;
+                static CDS_CONSTEXPR const opt::link_check_type link_checker = cds::intrusive::treiber_stack::traits::link_checker;

             };
 
             // Result of metafunction
             typedef intrusive::TreiberStack< gc, node_type, intrusive_traits > type;
         };
     } // namespace details
             };
 
             // Result of metafunction
             typedef intrusive::TreiberStack< gc, node_type, intrusive_traits > type;
         };
     } // namespace details

-    //@endecond
+    //@endcond

 
     /// Treiber's stack algorithm
     /** @ingroup cds_nonintrusive_stack
 
     /// Treiber's stack algorithm
     /** @ingroup cds_nonintrusive_stack


@@ -162,21 +203,30 @@ namespace cds { namespace container {
         intrusive::TreiberStack.
 
         Template arguments:
         intrusive::TreiberStack.
 
         Template arguments:

-        - \p GC - garbage collector type: gc::HP, gc::PTB
-        - \p T - type stored in the stack. It should be default-constructible, copy-constructible, assignable type.
+        - \p GC - garbage collector type: \p gc::HP, gc::DHP
+        - \p T - type stored in the stack.

         - \p Traits - stack traits, default is \p treiber_stack::traits. You can use \p treiber_stack::make_traits
             metafunction to make your traits or just derive your traits from \p %treiber_stack::traits:
             \code
             struct myTraits: public cds::container::treiber_stack::traits {
         - \p Traits - stack traits, default is \p treiber_stack::traits. You can use \p treiber_stack::make_traits
             metafunction to make your traits or just derive your traits from \p %treiber_stack::traits:
             \code
             struct myTraits: public cds::container::treiber_stack::traits {

-                typedef cds::container::treiber_stack::stat<> stat;
+                typedef cds::intrusive::treiber_stack::stat<> stat;
+                typedef cds::atomicity::item_counter  item_counter;

             };
             typedef cds::container::TreiberStack< cds::gc::HP, Foo, myTraits > myStack;
             };
             typedef cds::container::TreiberStack< cds::gc::HP, Foo, myTraits > myStack;

+
+            // Equivalent make_traits example:
+            typedef cds::intrusive::TreiberStack< cds::gc::HP, Foo,
+                typename cds::intrusive::treiber_stack::make_traits<
+                    cds::opt::item_counter< cds::atomicity::item_counter >,
+                    cds::opt::stat< cds::intrusive::treiber_stack::stat<> >
+                >::type
+            > myStack;

             \endcode
     */
             \endcode
     */

-    template < 
-        typename GC, 
-        typename T, 
-        typename Traits = treiber_stack::traits 
+    template <
+        typename GC,
+        typename T,
+        typename Traits = treiber_stack::traits

     >
     class TreiberStack
         : public
     >
     class TreiberStack
         : public


@@ -195,7 +245,7 @@ namespace cds { namespace container {
         /// Rebind template arguments
         template <typename GC2, typename T2, typename Traits2>
         struct rebind {
         /// Rebind template arguments
         template <typename GC2, typename T2, typename Traits2>
         struct rebind {

-            typedef TreiberStack< GC2, T2, Traits2> other   ;   ///< Rebinding result
+            typedef TreiberStack< GC2, T2, Traits2 > other;   ///< Rebinding result

         };
 
     public:
         };
 
     public:


@@ -207,7 +257,7 @@ namespace cds { namespace container {
         typedef typename base_class::stat       stat           ;   ///< Internal statistics policy used
 
     protected:
         typedef typename base_class::stat       stat           ;   ///< Internal statistics policy used
 
     protected:

-        typedef typename maker::node_type  node_type   ;   ///< stack node type (derived from intrusive::treiber_stack::node)
+        typedef typename maker::node_type  node_type   ;   ///< stack node type (derived from \p intrusive::treiber_stack::node)

 
         //@cond
         typedef typename maker::cxx_allocator     cxx_allocator;
 
         //@cond
         typedef typename maker::cxx_allocator     cxx_allocator;


@@ -252,7 +302,7 @@ namespace cds { namespace container {
         /// Constructs empty stack and initializes elimination back-off data
         /**
             This form should be used if you use elimination back-off with dynamically allocated collision array, i.e
         /// Constructs empty stack and initializes elimination back-off data
         /**
             This form should be used if you use elimination back-off with dynamically allocated collision array, i.e

-            \p Options... contains cds::opt::buffer< cds::opt::v::dynamic_buffer >.
+            \p Options... contains cds::opt::buffer< cds::opt::v::initialized_dynamic_buffer >.

             \p nCollisionCapacity parameter specifies the capacity of collision array.
         */
         TreiberStack( size_t nCollisionCapacity )
             \p nCollisionCapacity parameter specifies the capacity of collision array.
         */
         TreiberStack( size_t nCollisionCapacity )


@@ -297,25 +347,17 @@ namespace cds { namespace container {
         */
         bool pop( value_type& val )
         {
         */
         bool pop( value_type& val )
         {

-            return pop_with( [&val]( value_type& src ) { val = src; } );
+            return pop_with( [&val]( value_type& src ) { val = std::move(src); } );

         }
 
         /// Pops an item from the stack with functor
         /**
         }
 
         /// Pops an item from the stack with functor
         /**

+            \p Func can be used to copy/move popped item from the stack.

             \p Func interface is:
             \code
             void func( value_type& src );
             \p Func interface is:
             \code
             void func( value_type& src );

-            \endcond
-            where \p src - item popped.
-
-            The \p %pop_with can be used to move item from the stack to user-provided storage:
-            \code
-            cds::container::TreiberStack<cds::gc::HP, std::string > myStack;
-            //...
-
-            std::string dest;
-            myStack.pop_with( [&dest]( std::string& src ) { dest = std::move( src ); } );

             \endcode
             \endcode

+            where \p src - item popped.

         */
         template <typename Func>
         bool pop_with( Func f )
         */
         template <typename Func>
         bool pop_with( Func f )


@@ -364,5 +406,4 @@ namespace cds { namespace container {
 
 }}  // namespace cds::container
 
 
 }}  // namespace cds::container
 

-
-#endif // #ifndef __CDS_CONTAINER_TREIBER_STACK_H
+#endif // #ifndef CDSLIB_CONTAINER_TREIBER_STACK_H