-//$$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_IMPL_SKIP_LIST_SET_H
#define CDSLIB_CONTAINER_IMPL_SKIP_LIST_SET_H
typedef typename traits::random_level_generator random_level_generator; ///< random level generator
typedef typename traits::stat stat; ///< internal statistics type
- //@cond
- typedef cds::container::skip_list::implementation_tag implementation_tag;
- //@endcond
+ static size_t const c_nHazardPtrCount = base_class::c_nHazardPtrCount; ///< Count of hazard pointer required for the skip-list
protected:
//@cond
{}
public:
+ ///@name Forward iterators (only for debugging purpose)
+ //@{
/// Iterator type
+ /**
+ The forward iterator has some features:
+ - it has no post-increment operator
+ - to protect the value, the iterator contains a GC-specific guard + another guard is required locally for increment operator.
+ For some GC (like as \p gc::HP), a guard is a limited resource per thread, so an exception (or assertion) "no free guard"
+ may be thrown if the limit of guard count per thread is exceeded.
+ - The iterator cannot be moved across thread boundary because it contains thread-private GC's guard.
+ - Iterator ensures thread-safety even if you delete the item the iterator points to. However, in case of concurrent
+ deleting operations there is no guarantee that you iterate all item in the list.
+ Moreover, a crash is possible when you try to iterate the next element that has been deleted by concurrent thread.
+
+ @warning Use this iterator on the concurrent container for debugging purpose only.
+
+ The iterator interface:
+ \code
+ class iterator {
+ public:
+ // Default constructor
+ iterator();
+
+ // Copy construtor
+ iterator( iterator const& src );
+
+ // Dereference operator
+ value_type * operator ->() const;
+
+ // Dereference operator
+ value_type& operator *() const;
+
+ // Preincrement operator
+ iterator& operator ++();
+
+ // Assignment operator
+ iterator& operator = (iterator const& src);
+
+ // Equality operators
+ bool operator ==(iterator const& i ) const;
+ bool operator !=(iterator const& i ) const;
+ };
+ \endcode
+ */
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;
}
The operation performs inserting or changing data with lock-free manner.
If the \p val key not found in the set, then the new item created from \p val
- will be inserted into the set iff \p bInsert is \p true.
+ will be inserted into the set iff \p bInsert is \p true.
Otherwise, if \p val is found, the functor \p func will be called with the item found.
The functor \p Func signature:
The functor may change non-key fields of the \p item; however, \p func must guarantee
that during changing no any other modifications could be made on this item by concurrent threads.
- Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successfull,
+ Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successful,
i.e. the item has been inserted or updated,
\p second is \p true if new item has been added or \p false if the item with key equal to \p val
already exists.
{
scoped_node_ptr sp( node_allocator().New( random_level(), val ));
std::pair<bool, bool> bRes = base_class::update( *sp,
- [&func, &val](bool bNew, node_type& node, node_type&){ func( bNew, node.m_Value, val ); },
+ [&func, &val](bool bNew, node_type& node, node_type&){ func( bNew, node.m_Value, val ); },
bInsert );
if ( bRes.first && bRes.second )
sp.release();
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;
}
bool erase_with( Q const& key, Less pred )
{
CDS_UNUSED( pred );
- return base_class::erase_with( key, cds::details::predicate_wrapper< node_type, Less, typename maker::value_accessor >() );
+ return base_class::erase_with( key, cds::details::predicate_wrapper< node_type, Less, typename maker::value_accessor >());
}
/// Delete \p key from the set
template <typename Q>
guarded_ptr extract( Q const& key )
{
- guarded_ptr gp;
- base_class::extract_( gp.guard(), key, typename base_class::key_comparator() );
- return gp;
+ return base_class::extract_( key, typename base_class::key_comparator());
}
/// Extracts the item from the set with comparing functor \p pred
{
CDS_UNUSED( pred );
typedef cds::details::predicate_wrapper< node_type, Less, typename maker::value_accessor > wrapped_less;
- guarded_ptr gp;
- base_class::extract_( gp.guard(), key, cds::opt::details::make_comparator_from_less<wrapped_less>() );
- return gp;
+ return base_class::extract_( key, cds::opt::details::make_comparator_from_less<wrapped_less>());
}
/// Extracts an item with minimal key from the set
*/
guarded_ptr extract_min()
{
- guarded_ptr gp;
- base_class::extract_min_( gp.guard() );
- return gp;
+ return base_class::extract_min_();
}
/// Extracts an item with maximal key from the set
*/
guarded_ptr extract_max()
{
- guarded_ptr gp;
- base_class::extract_max_( gp.guard() );
- return gp;
+ return base_class::extract_max_();
}
/// Find the \p key
{
CDS_UNUSED( pred );
return base_class::find_with( key, 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
- /// Find \p key
- /** \anchor cds_nonintrusive_SkipListSet_find_val
-
+ /// Checks whether the set contains \p key
+ /**
The function searches the item with key equal to \p key
and returns \p true if it is found, and \p false otherwise.
-
- Note the hash functor specified for class \p Traits template parameter
- should accept a parameter of type \p Q that may be not the same as \ref value_type.
*/
template <typename Q>
+ bool contains( Q const& key )
+ {
+ return base_class::contains( key );
+ }
+ //@cond
+ template <typename Q>
+ CDS_DEPRECATED("deprecated, use contains()")
bool find( Q const& key )
{
- return base_class::find( key );
+ return contains( key );
}
+ //@endcond
- /// Finds \p key using \p pred predicate for searching
+ /// Checks whether the set contains \p key using \p pred predicate for searching
/**
- The function is an analog of \ref cds_nonintrusive_SkipListSet_find_val "find(Q const&)"
- but \p pred is used for key comparing.
+ The function is similar to <tt>contains( key )</tt> but \p pred is used for key comparing.
\p Less functor has the interface like \p std::less.
\p Less must imply the same element order as the comparator used for building the set.
*/
template <typename Q, typename Less>
- bool find_with( Q const& key, Less pred )
+ bool contains( Q const& key, Less pred )
{
CDS_UNUSED( pred );
- return base_class::find_with( key, cds::details::predicate_wrapper< node_type, Less, typename maker::value_accessor >());
+ return base_class::contains( key, cds::details::predicate_wrapper< node_type, Less, typename maker::value_accessor >());
}
+ //@cond
+ template <typename Q, typename Less>
+ CDS_DEPRECATED("deprecated, use contains()")
+ bool find_with( Q const& key, Less pred )
+ {
+ return contains( key, pred );
+ }
+ //@endcond
/// Finds \p key and return the item found
/** \anchor cds_nonintrusive_SkipListSet_hp_get
template <typename Q>
guarded_ptr get( Q const& key )
{
- guarded_ptr gp;
- base_class::get_with_( gp.guard(), key, typename base_class::key_comparator() );
- return gp;
+ return base_class::get_with_( key, typename base_class::key_comparator());
}
/// Finds \p key and return the item found
{
CDS_UNUSED( pred );
typedef cds::details::predicate_wrapper< node_type, Less, typename maker::value_accessor > wrapped_less;
- guarded_ptr gp;
- base_class::get_with_( gp.guard(), key, cds::opt::details::make_comparator_from_less< wrapped_less >());
- return gp;
+ return base_class::get_with_( key, cds::opt::details::make_comparator_from_less< wrapped_less >());
}
/// Clears the set (not atomic).
this sequence
\code
set.clear();
- assert( set.empty() );
+ assert( set.empty());
\endcode
the assertion could be raised.
projects / libcds.git / blobdiff