X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;ds=sidebyside;f=cds%2Fcontainer%2Ftreiber_stack.h;h=a559d0cb6d55a8a2826e318069ac054213cef1fd;hb=71da1f106e0d9451556720b8315f7db0f24383b7;hp=32954b7e11c32ce53a846fe79087c0e8f91bef06;hpb=f283f28b6ffbed9439ccbf10146f08fa53df8238;p=libcds.git diff --git a/cds/container/treiber_stack.h b/cds/container/treiber_stack.h index 32954b7e..a559d0cb 100644 --- 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 // unique_ptr #include @@ -9,10 +37,13 @@ namespace cds { namespace container { + /// TreiberStack related definitions + /** @ingroup cds_nonintrusive_helper + */ namespace treiber_stack { /// Internal statistics - template - using stat = cds::intrusive::treiber_stack::stat < Counter >; + template ::counter_type > + using stat = cds::intrusive::treiber_stack::stat< Counter >; /// 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; - /// 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) /** - 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. */ - typedef empty_stat stat; + typedef empty_stat stat; /** @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 - 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 /** - 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. - Default is %opt::v::static_buffer< any_type, 4 > . + Default is %opt::v::initialized_static_buffer< any_type, 4 > . */ - 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; - /// 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 /** - This is a wrapper for cds::opt::make_options< type_traits, Options...> 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). - - 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), - 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: - - 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. - Default is %opt::v::static_buffer< any_type, 4 > . - - opt::random_engine - a random engine to generate a random position in elimination array. + Default is %opt::v::initialized_static_buffer< any_type, 4 > . + - \p opt::random_engine - a random engine to generate a random position in elimination array. 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 struct make_traits { @@ -147,14 +188,14 @@ namespace cds { namespace container { { typedef cds::intrusive::treiber_stack::base_hook< cds::opt::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 - //@endecond + //@endcond /// Treiber's stack algorithm /** @ingroup cds_nonintrusive_stack @@ -162,21 +203,30 @@ namespace cds { namespace container { 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 { - 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; + + // 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 */ - template < - typename GC, - typename T, - typename Traits = treiber_stack::traits + template < + typename GC, + typename T, + typename Traits = treiber_stack::traits > class TreiberStack : public @@ -195,7 +245,7 @@ namespace cds { namespace container { /// Rebind template arguments template struct rebind { - typedef TreiberStack< GC2, T2, Traits2> other ; ///< Rebinding result + typedef TreiberStack< GC2, T2, Traits2 > other; ///< Rebinding result }; public: @@ -207,7 +257,7 @@ namespace cds { namespace container { 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; @@ -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 - \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 ) @@ -297,25 +347,17 @@ namespace cds { namespace container { */ 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 /** + \p Func can be used to copy/move popped item from the stack. \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 myStack; - //... - - std::string dest; - myStack.pop_with( [&dest]( std::string& src ) { dest = std::move( src ); } ); \endcode + where \p src - item popped. */ template bool pop_with( Func f ) @@ -364,5 +406,4 @@ namespace cds { namespace container { }} // namespace cds::container - -#endif // #ifndef __CDS_CONTAINER_TREIBER_STACK_H +#endif // #ifndef CDSLIB_CONTAINER_TREIBER_STACK_H