-//$$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-2016
+
+ 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>
namespace cds { namespace container {
+ /// TreiberStack related definitions
+ /** @ingroup cds_nonintrusive_helper
+ */
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;
*/
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
///@{
/// 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 <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;
- /// 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 <tt> cds::opt::make_options< type_traits, Options...> </tt>
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 <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.
- - 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 {
{
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
- //@endecond
+ //@endcond
/// Treiber's stack algorithm
/** @ingroup cds_nonintrusive_stack
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
/// 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:
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;
/// 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 )
~TreiberStack()
{}
- /// Push the item \p val on the stack
+ /// Pushes copy of \p val on the stack
bool push( value_type const& val )
{
scoped_node_ptr p( alloc_node(val));
return false;
}
- /// Pop an item from the stack
+ /// Pops an item from the stack
/**
- The value of popped item is stored in \p val.
+ The value of popped item is stored in \p val using assignment operator.
On success functions returns \p true, \p val contains value popped from the stack.
If stack is empty the function returns \p false, \p val is unchanged.
*/
bool pop( value_type& val )
+ {
+ 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 );
+ \endcode
+ where \p src - item popped.
+ */
+ template <typename Func>
+ bool pop_with( Func f )
{
node_type * p = base_class::pop();
if ( !p )
return false;
- val = p->m_value;
+ f( p->m_value );
retire_node( p );
return true;
}} // namespace cds::container
-
-#endif // #ifndef __CDS_CONTAINER_TREIBER_STACK_H
+#endif // #ifndef CDSLIB_CONTAINER_TREIBER_STACK_H
projects / libcds.git / blobdiff