-//$$CDS-header$$
+/*
+ This file is a part of libcds - Concurrent Data Structures library
+
+ (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_SKIP_LIST_SET_RCU_H
#define CDSLIB_CONTAINER_SKIP_LIST_SET_RCU_H
- opt::item_counter - the type of item counting feature. Default is \ref atomicity::empty_item_counter that is no item counting.
- opt::memory_model - C++ memory ordering model. Can be opt::v::relaxed_ordering (relaxed memory model, the default)
or opt::v::sequential_consistent (sequentially consisnent memory model).
- - skip_list::random_level_generator - random level generator. Can be skip_list::xorshift, skip_list::turbo_pascal or
- user-provided one. See skip_list::random_level_generator option description for explanation.
- Default is \p %skip_list::turbo_pascal.
+ - skip_list::random_level_generator - random level generator. Can be \p skip_list::xor_shift, \p skip_list::turbo or
+ user-provided one. See \p skip_list::random_level_generator option description for explanation.
+ Default is \p skip_list::turbo32.
- opt::allocator - allocator for skip-list node. Default is \ref CDS_DEFAULT_ALLOCATOR.
- opt::back_off - back-off strategy used. If the option is not specified, the cds::backoff::Default is used.
- opt::stat - internal statistics. Available types: skip_list::stat, skip_list::empty_stat (the default)
typedef typename traits::stat stat ; ///< internal statistics type
typedef typename traits::rcu_check_deadlock rcu_check_deadlock ; ///< Deadlock checking policy
- //@cond
- typedef cds::container::skip_list::implementation_tag implementation_tag;
- //@endcond
-
protected:
//@cond
typedef typename maker::node_type node_type;
{}
public:
- /// Iterator type
+ ///@name Forward ordered iterators (thread-safe under RCU lock)
+ //@{
+ /// Forward iterator
+ /**
+ The forward iterator has some features:
+ - it has no post-increment operator
+ - it depends on iterator of underlying \p OrderedList
+
+ You may safely use iterators in multi-threaded environment only under RCU lock.
+ Otherwise, a crash is possible if another thread deletes the element the iterator points to.
+ */
typedef skip_list::details::iterator< typename base_class::iterator > iterator;
/// Const iterator type
/// Returns a forward iterator addressing the first element in a set
iterator begin()
{
- return iterator( base_class::begin() );
+ return iterator( base_class::begin());
}
/// Returns a forward const iterator addressing the first element in a set
- //@{
const_iterator begin() const
{
- return const_iterator( base_class::begin() );
+ return const_iterator( base_class::begin());
}
+
+ /// Returns a forward const iterator addressing the first element in a set
const_iterator cbegin() const
{
- return const_iterator( base_class::cbegin() );
+ return const_iterator( base_class::cbegin());
}
- //@}
/// Returns a forward iterator that addresses the location succeeding the last element in a set.
iterator end()
{
- return iterator( base_class::end() );
+ return iterator( base_class::end());
}
/// Returns a forward const iterator that addresses the location succeeding the last element in a set.
- //@{
const_iterator end() const
{
- return const_iterator( base_class::end() );
+ return const_iterator( base_class::end());
}
+
+ /// Returns a forward const iterator that addresses the location succeeding the last element in a set.
const_iterator cend() const
{
- return const_iterator( base_class::cend() );
+ return const_iterator( base_class::cend());
}
- //@}
+ //@}
public:
/// Inserts new node
bool insert( Q const& val )
{
scoped_node_ptr sp( node_allocator().New( random_level(), val ));
- if ( base_class::insert( *sp.get() )) {
+ if ( base_class::insert( *sp.get())) {
sp.release();
return true;
}
RCU \p synchronize method can be called. RCU should not be locked.
- Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
+ Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successful,
\p second is true if new item has been added or \p false if the item with \p key
already exists.
*/
return bRes;
}
//@cond
- // Deprecated, use update()
template <typename Q, typename Func>
+ CDS_DEPRECATED("ensure() is deprecated, use update()")
std::pair<bool, bool> ensure( const Q& val, Func func )
{
return update( val, func, true );
bool emplace( Args&&... args )
{
scoped_node_ptr sp( node_allocator().New( random_level(), std::forward<Args>(args)... ));
- if ( base_class::insert( *sp.get() )) {
+ if ( base_class::insert( *sp.get())) {
sp.release();
return true;
}
{
CDS_UNUSED( pred );
return base_class::find_with( val, cds::details::predicate_wrapper< node_type, Less, typename maker::value_accessor >(),
- [&f]( node_type& node, Q& v ) { f( node.m_Value, v ); } );
+ [&f]( node_type& node, Q const& v ) { f( node.m_Value, v ); } );
}
//@endcond
return base_class::contains( key );
}
//@cond
- // Deprecated, use contains()
template <typename Q>
+ CDS_DEPRECATED("deprecated, use contains()")
bool find( Q const & key )
{
return contains( key );
return base_class::contains( key, cds::details::predicate_wrapper< node_type, Less, typename maker::value_accessor >());
}
//@cond
- // Deprecated, use contains()
template <typename Q, typename Less>
+ CDS_DEPRECATED("deprecated, use contains()")
bool find_with( Q const& key, Less pred )
{
return contains( key, pred );
raw_ptr get_with( Q const& val, Less pred )
{
CDS_UNUSED( pred );
- return raw_ptr( base_class::get_with( val, cds::details::predicate_wrapper< node_type, Less, typename maker::value_accessor >() ));
+ return raw_ptr( base_class::get_with( val, cds::details::predicate_wrapper< node_type, Less, typename maker::value_accessor >()));
}
/// Clears the set (non-atomic).
this sequence
\code
set.clear();
- assert( set.empty() );
+ assert( set.empty());
\endcode
the assertion could be raised.