-//$$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>
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 )
*/
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<cds::gc::HP, std::string > myStack;
- //...
-
- std::string dest;
- myStack.pop_with( [&dest]( std::string& src ) { dest = std::move( src ); } );
\endcode
+ where \p src - item popped.
*/
template <typename Func>
bool pop_with( Func f )
}} // namespace cds::container
-
-#endif // #ifndef __CDS_CONTAINER_TREIBER_STACK_H
+#endif // #ifndef CDSLIB_CONTAINER_TREIBER_STACK_H
projects / libcds.git / blobdiff