-//$$CDS-header$$
+/*
+ This file is a part of libcds - Concurrent Data Structures library
-#ifndef __CDS_INTRUSIVE_SKIP_LIST_NOGC_H
-#define __CDS_INTRUSIVE_SKIP_LIST_NOGC_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_INTRUSIVE_SKIP_LIST_NOGC_H
+#define CDSLIB_INTRUSIVE_SKIP_LIST_NOGC_H
#include <type_traits>
#include <memory>
#include <cds/gc/nogc.h>
-#include <cds/intrusive/skip_list_base.h>
+#include <cds/intrusive/details/skip_list_base.h>
#include <cds/opt/compare.h>
-#include <cds/ref.h>
#include <cds/details/binary_functor_wrapper.h>
namespace cds { namespace intrusive {
class node< cds::gc::nogc, Tag >
{
public:
- typedef cds::gc::nogc gc ; ///< Garbage collector
- typedef Tag tag ; ///< tag
+ typedef cds::gc::nogc gc; ///< Garbage collector
+ typedef Tag tag; ///< tag
- typedef CDS_ATOMIC::atomic<node * > atomic_ptr;
- typedef atomic_ptr tower_item_type;
+ typedef atomics::atomic<node * > atomic_ptr;
+ typedef atomic_ptr tower_item_type;
protected:
- atomic_ptr m_pNext ; ///< Next item in bottom-list (list at level 0)
- unsigned int m_nHeight ; ///< Node height (size of m_arrNext array). For node at level 0 the height is 1.
- atomic_ptr * m_arrNext ; ///< Array of next items for levels 1 .. m_nHeight - 1. For node at level 0 \p m_arrNext is \p nullptr
+ atomic_ptr m_pNext; ///< Next item in bottom-list (list at level 0)
+ unsigned int m_nHeight; ///< Node height (size of m_arrNext array). For node at level 0 the height is 1.
+ atomic_ptr * m_arrNext; ///< Array of next items for levels 1 .. m_nHeight - 1. For node at level 0 \p m_arrNext is \p nullptr
public:
/// Constructs a node of height 1 (a bottom-list node)
/// Access to element of next pointer array
atomic_ptr& next( unsigned int nLevel )
{
- assert( nLevel < height() );
- assert( nLevel == 0 || (nLevel > 0 && m_arrNext != nullptr) );
+ assert( nLevel < height());
+ assert( nLevel == 0 || (nLevel > 0 && m_arrNext != nullptr));
return nLevel ? m_arrNext[ nLevel - 1] : m_pNext;
}
/// Access to element of next pointer array (const version)
atomic_ptr const& next( unsigned int nLevel ) const
{
- assert( nLevel < height() );
+ assert( nLevel < height());
assert( nLevel == 0 || nLevel > 0 && m_arrNext != nullptr );
return nLevel ? m_arrNext[ nLevel - 1] : m_pNext;
void clear()
{
assert( m_arrNext == nullptr );
- m_pNext.store( nullptr, CDS_ATOMIC::memory_order_release );
+ m_pNext.store( nullptr, atomics::memory_order_release );
}
bool is_cleared() const
{
- return m_pNext.load( CDS_ATOMIC::memory_order_relaxed ) == nullptr
+ return m_pNext.load( atomics::memory_order_relaxed ) == nullptr
&& m_arrNext == nullptr
&& m_nHeight <= 1
;
typedef BackOff back_off;
typedef typename node_traits::node_type node_type;
typedef typename node_traits::value_type value_type;
- static bool const c_isConst = IsConst;
+ static CDS_CONSTEXPR bool const c_isConst = IsConst;
typedef typename std::conditional< c_isConst, value_type const &, value_type &>::type value_ref;
+ friend class iterator< gc, node_traits, back_off, !c_isConst >;
protected:
- typedef typename node_type::atomic_ptr atomic_ptr;
- node_type * m_pNode;
+ typedef typename node_type::atomic_ptr atomic_ptr;
+ node_type * m_pNode;
public: // for internal use only!!!
iterator( node_type& refHead )
- : m_pNode( refHead[0].load( CDS_ATOMIC::memory_order_relaxed ) )
+ : m_pNode( refHead[0].load( atomics::memory_order_relaxed ))
{}
static iterator from_node( node_type * pNode )
iterator& operator ++()
{
if ( m_pNode )
- m_pNode = m_pNode->next(0).load( CDS_ATOMIC::memory_order_relaxed );
+ m_pNode = m_pNode->next(0).load( atomics::memory_order_relaxed );
return *this;
}
- iterator& operator = (const iterator& src)
+ iterator& operator =(const iterator& src)
{
m_pNode = src.m_pNode;
return *this;
/** @ingroup cds_intrusive_map
@anchor cds_intrusive_SkipListSet_nogc
- This specialization is intended for so-called persistent usage when no item
+ This specialization is so-called append-only when no item
reclamation may be performed. The class does not support deleting of list item.
See \ref cds_intrusive_SkipListSet_hp "SkipListSet" for description of skip-list.
<b>Template arguments</b> :
- - \p T - type to be stored in the set. The type must be based on skip_list::node (for skip_list::base_hook)
- or it must have a member of type skip_list::node (for skip_list::member_hook).
- - \p Traits - type traits. See skip_list::type_traits for explanation.
-
- It is possible to declare option-based list with cds::intrusive::skip_list::make_traits metafunction istead of \p Traits template
- argument.
- Template argument list \p Options of cds::intrusive::skip_list::make_traits metafunction are:
- - opt::hook - hook used. Possible values are: skip_list::base_hook, skip_list::member_hook, skip_list::traits_hook.
- If the option is not specified, <tt>skip_list::base_hook<></tt> and gc::HP is used.
- - opt::compare - key comparison functor. No default functor is provided.
- If the option is not specified, the opt::less is used.
- - opt::less - specifies binary predicate used for key comparison. Default is \p std::less<T>.
- - 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.
- - opt::allocator - although the skip-list is an intrusive container,
- an allocator should be provided to maintain variable randomly-calculated height of the node
- since the node can contain up to 32 next pointers. The allocator option is used to allocate an array of next pointers
- for nodes which height is more than 1. 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)
- - opt::disposer - the functor used for dispose removed items. Default is opt::v::empty_disposer.
- The disposer is used only in object destructor and in \ref clear function.
+ - \p T - type to be stored in the set. The type must be based on \p skip_list::node (for \p skip_list::base_hook)
+ or it must have a member of type \p skip_list::node (for \p skip_list::member_hook).
+ - \p Traits - type traits, default is \p skip_list::traits.
+ It is possible to declare option-based list with \p cds::intrusive::skip_list::make_traits metafunction
+ istead of \p Traits template argument.
<b>Iterators</b>
<b>How to use</b>
- You should incorporate skip_list::node into your struct \p T and provide
- appropriate skip_list::type_traits::hook in your \p Traits template parameters. Usually, for \p Traits you
- define a struct based on skip_list::type_traits.
+ You should incorporate \p skip_list::node into your struct \p T and provide
+ appropriate \p skip_list::traits::hook in your \p Traits template parameters. Usually, for \p Traits you
+ define a struct based on \p skip_list::traits.
Example for base hook:
\code
};
- // Declare type_traits
- struct my_traits: public cds::intrusive::skip_list::type_traits
+ // Declare traits
+ struct my_traits: public cds::intrusive::skip_list::traits
{
- typedef cds::intrusive::skip_list::base_hook< cds::opt::gc< cds::gc::nogc > > hook;
+ typedef cds::intrusive::skip_list::base_hook< cds::opt::gc< cds::gc::nogc > > hook;
typedef my_data_cmp compare;
};
// Declare skip-list set type
- typedef cds::intrusive::SkipListSet< cds::gc::nogc, my_data, my_traits > traits_based_set;
+ typedef cds::intrusive::SkipListSet< cds::gc::nogc, my_data, my_traits > traits_based_set;
\endcode
Equivalent option-based code:
,cds::intrusive::opt::compare< my_data_cmp >
>::type
> option_based_set;
-
\endcode
-
*/
template <
typename T
#ifdef CDS_DOXYGEN_INVOKED
- ,typename Traits = skip_list::type_traits
+ ,typename Traits = skip_list::traits
#else
,typename Traits
#endif
class SkipListSet< cds::gc::nogc, T, Traits >
{
public:
- typedef T value_type ; ///< type of value stored in the skip-list
- typedef Traits options ; ///< Traits template parameter
+ typedef cds::gc::nogc gc; ///< No garbage collector is used
+ typedef T value_type; ///< type of value stored in the skip-list
+ typedef Traits traits; ///< Traits template parameter
- typedef typename options::hook hook ; ///< hook type
- typedef typename hook::node_type node_type ; ///< node type
+ typedef typename traits::hook hook; ///< hook type
+ typedef typename hook::node_type node_type; ///< node type
# ifdef CDS_DOXYGEN_INVOKED
- typedef implementation_defined key_comparator ; ///< key comparison functor based on opt::compare and opt::less option setter.
+ typedef implementation_defined key_comparator; ///< key comparison functor based on \p Traits::compare and \p Traits::less
# else
- typedef typename opt::details::make_comparator< value_type, options >::type key_comparator;
+ typedef typename opt::details::make_comparator< value_type, traits >::type key_comparator;
# endif
- typedef typename get_node_traits< value_type, node_type, hook>::type node_traits ; ///< node traits
+ typedef typename get_node_traits< value_type, node_type, hook>::type node_traits; ///< node traits
- typedef cds::gc::nogc gc ; ///< No garbage collector is used
- typedef typename options::item_counter item_counter ; ///< Item counting policy used
- typedef typename options::memory_model memory_model; ///< Memory ordering. See cds::opt::memory_model option
- typedef typename options::random_level_generator random_level_generator ; ///< random level generator
- typedef typename options::allocator allocator_type ; ///< allocator for maintaining array of next pointers of the node
- typedef typename options::back_off back_off ; ///< Back-off trategy
- typedef typename options::stat stat ; ///< internal statistics type
- typedef typename options::disposer disposer ; ///< disposer used
+ typedef typename traits::item_counter item_counter; ///< Item counting policy
+ typedef typename traits::memory_model memory_model; ///< Memory ordering. See \p cds::opt::memory_model option
+ typedef typename traits::random_level_generator random_level_generator ; ///< random level generator
+ typedef typename traits::allocator allocator_type; ///< allocator for maintaining array of next pointers of the node
+ typedef typename traits::back_off back_off; ///< Back-off strategy
+ typedef typename traits::stat stat; ///< internal statistics type
+ typedef typename traits::disposer disposer; ///< disposer
/// Max node height. The actual node height should be in range <tt>[0 .. c_nMaxHeight)</tt>
/**
The max height is specified by \ref skip_list::random_level_generator "random level generator" constant \p m_nUpperBound
- but it should be no more than 32 (\ref skip_list::c_nHeightLimit).
+ but it should be no more than 32 (\p skip_list::c_nHeightLimit).
*/
static unsigned int const c_nMaxHeight = std::conditional<
(random_level_generator::c_nUpperBound <= skip_list::c_nHeightLimit),
//@endcond
protected:
- typedef typename node_type::atomic_ptr atomic_node_ptr ; ///< Atomic node pointer
+ typedef typename node_type::atomic_ptr atomic_node_ptr; ///< Atomic node pointer
protected:
//@cond
typedef skip_list::details::intrusive_node_builder< node_type, atomic_node_ptr, allocator_type > intrusive_node_builder;
typedef typename std::conditional<
- std::is_same< typename options::internal_node_builder, cds::opt::none >::value
+ std::is_same< typename traits::internal_node_builder, cds::opt::none >::value
,intrusive_node_builder
- ,typename options::internal_node_builder
+ ,typename traits::internal_node_builder
>::type node_builder;
typedef std::unique_ptr< node_type, typename node_builder::node_disposer > scoped_node_ptr;
node_type * pCur;
};
-# ifndef CDS_CXX11_LAMBDA_SUPPORT
- struct empty_insert_functor {
- void operator()( value_type& )
- {}
- };
-
- struct empty_find_functor {
- template <typename Q>
- void operator()( value_type& item, Q& val )
- {}
- };
-
- template <typename Func>
- struct insert_at_ensure_functor {
- Func m_func;
- insert_at_ensure_functor( Func f ) : m_func(f) {}
-
- void operator()( value_type& item )
- {
- cds::unref( m_func)( true, item, item );
- }
- };
-
-# endif // ifndef CDS_CXX11_LAMBDA_SUPPORT
-
class head_node: public node_type
{
typename node_type::atomic_ptr m_Tower[c_nMaxHeight];
head_node( unsigned int nHeight )
{
for ( size_t i = 0; i < sizeof(m_Tower) / sizeof(m_Tower[0]); ++i )
- m_Tower[i].store( nullptr, CDS_ATOMIC::memory_order_relaxed );
+ m_Tower[i].store( nullptr, atomics::memory_order_relaxed );
node_type::make_tower( nHeight, m_Tower );
}
void clear()
{
for (unsigned int i = 0; i < sizeof(m_Tower) / sizeof(m_Tower[0]); ++i )
- m_Tower[i].store( nullptr, CDS_ATOMIC::memory_order_relaxed );
- node_type::m_pNext.store( nullptr, CDS_ATOMIC::memory_order_relaxed );
+ m_Tower[i].store( nullptr, atomics::memory_order_relaxed );
+ node_type::m_pNext.store( nullptr, atomics::memory_order_relaxed );
}
};
//@endcond
protected:
- head_node m_Head ; ///< head tower (max height)
+ head_node m_Head; ///< head tower (max height)
- item_counter m_ItemCounter ; ///< item counter
- random_level_generator m_RandomLevelGen ; ///< random level generator instance
- CDS_ATOMIC::atomic<unsigned int> m_nHeight ; ///< estimated high level
- mutable stat m_Stat ; ///< internal statistics
+ item_counter m_ItemCounter; ///< item counter
+ random_level_generator m_RandomLevelGen; ///< random level generator instance
+ atomics::atomic<unsigned int> m_nHeight; ///< estimated high level
+ mutable stat m_Stat; ///< internal statistics
protected:
//@cond
{
node_type * p = pos.pSucc[0];
pNode->next( 0 ).store( pos.pSucc[ 0 ], memory_model::memory_order_release );
- if ( !pos.pPrev[0]->next(0).compare_exchange_strong( p, pNode, memory_model::memory_order_release, memory_model::memory_order_relaxed ) ) {
+ if ( !pos.pPrev[0]->next(0).compare_exchange_strong( p, pNode, memory_model::memory_order_release, memory_model::memory_order_relaxed )) {
return false;
}
- cds::unref( f )( val );
+ f( val );
}
for ( unsigned int nLevel = 1; nLevel < nHeight; ++nLevel ) {
if ( pNode->next( nLevel ).compare_exchange_strong( p, q, memory_model::memory_order_release, memory_model::memory_order_relaxed )) {
p = q;
- if ( pos.pPrev[nLevel]->next(nLevel).compare_exchange_strong( q, pNode, memory_model::memory_order_release, memory_model::memory_order_relaxed ) )
+ if ( pos.pPrev[nLevel]->next(nLevel).compare_exchange_strong( q, pNode, memory_model::memory_order_release, memory_model::memory_order_relaxed ))
break;
}
if ( find_position( val, pos, cmp, true, false )) {
assert( cmp( *node_traits::to_value_ptr( pos.pCur ), val ) == 0 );
- cds::unref(f)( *node_traits::to_value_ptr( pos.pCur ), val );
+ f( *node_traits::to_value_ptr( pos.pCur ), val );
m_Stat.onFindFastSuccess();
return pos.pCur;
void increase_height( unsigned int nHeight )
{
unsigned int nCur = m_nHeight.load( memory_model::memory_order_relaxed );
- while ( nCur < nHeight && !m_nHeight.compare_exchange_weak( nCur, nHeight, memory_model::memory_order_acquire, CDS_ATOMIC::memory_order_relaxed ) );
+ while ( nCur < nHeight && !m_nHeight.compare_exchange_weak( nCur, nHeight, memory_model::memory_order_acquire, atomics::memory_order_relaxed ));
}
//@endcond
static_assert( (std::is_same< gc, typename node_type::gc >::value), "GC and node_type::gc must be the same type" );
// Barrier for head node
- CDS_ATOMIC::atomic_thread_fence( memory_model::memory_order_release );
+ atomics::atomic_thread_fence( memory_model::memory_order_release );
}
/// Clears and destructs the skip-list
}
public:
- /// Iterator type
+ ///@name Forward iterators
+ //@{
+ /// Forward iterator
+ /**
+ The forward iterator for a split-list has some features:
+ - it has no post-increment operator
+ - it depends on iterator of underlying \p OrderedList
+ */
typedef skip_list::details::iterator< gc, node_traits, back_off, false > iterator;
/// Const iterator type
/// Returns a forward iterator addressing the first element in a set
iterator begin()
{
- return iterator( *m_Head.head() );
+ return iterator( *m_Head.head());
}
/// Returns a forward const iterator addressing the first element in a set
- //@{
const_iterator begin() const
{
- return const_iterator( *m_Head.head() );
+ return const_iterator( *m_Head.head());
}
- const_iterator cbegin()
+ /// Returns a forward const iterator addressing the first element in a set
+ const_iterator cbegin() const
{
- return const_iterator( *m_Head.head() );
+ return const_iterator( *m_Head.head());
}
- //@}
/// Returns a forward iterator that addresses the location succeeding the last element in a set.
iterator end()
}
/// Returns a forward const iterator that addresses the location succeeding the last element in a set.
- //@{
const_iterator end() const
{
return const_iterator();
}
- const_iterator cend()
+ /// Returns a forward const iterator that addresses the location succeeding the last element in a set.
+ const_iterator cend() const
{
return const_iterator();
}
- //@}
+ //@}
protected:
//@cond
bTowerOk = true;
}
-# ifndef CDS_CXX11_LAMBDA_SUPPORT
- if ( !insert_at_position( val, pNode, pos, empty_insert_functor() ))
-# else
- if ( !insert_at_position( val, pNode, pos, []( value_type& ) {} ))
-# endif
- {
+ if ( !insert_at_position( val, pNode, pos, []( value_type& ) {} )) {
m_Stat.onInsertRetry();
continue;
}
}
}
- /// Ensures that the \p val exists in the set
+ /// Updates the node
/**
The operation performs inserting or changing data with lock-free manner.
- If the item \p val is not found in the set, then \p val is inserted into the set.
+ If the item \p val is not found in the set, then \p val is inserted into the set
+ iff \p bInsert is \p true.
Otherwise, the functor \p func is called with item found.
The functor signature is:
\code
with arguments:
- \p bNew - \p true if the item has been inserted, \p false otherwise
- \p item - item of the set
- - \p val - argument \p val passed into the \p ensure function
+ - \p val - argument \p val passed into the \p %update() function
If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
refer to the same thing.
The functor can 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.
- You can pass \p func argument by value or by reference using <tt>boost::ref</tt> or cds::ref.
-
- Returns std::pair<bool, bool> where \p first is \p true if operation is successfull,
+ Returns std::pair<bool, bool> where \p first is \p true if operation is successful,
\p second is \p true if new item has been added or \p false if the item with \p key
already is in the set.
+
+ @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
*/
template <typename Func>
- std::pair<bool, bool> ensure( value_type& val, Func func )
+ std::pair<bool, bool> update( value_type& val, Func func, bool bInsert = true )
{
node_type * pNode = node_traits::to_node_ptr( val );
scoped_node_ptr scp( pNode );
bool bTowerOk = nHeight > 1 && pNode->get_tower() != nullptr;
bool bTowerMade = false;
-# ifndef CDS_CXX11_LAMBDA_SUPPORT
- insert_at_ensure_functor<Func> wrapper( func );
-# endif
-
position pos;
while ( true )
{
if ( !bTowerMade )
scp.release();
- cds::unref(func)( false, *node_traits::to_value_ptr(pos.pCur), val );
- m_Stat.onEnsureExist();
+ func( false, *node_traits::to_value_ptr(pos.pCur), val );
+ m_Stat.onUpdateExist();
return std::make_pair( true, false );
}
+ if ( !bInsert ) {
+ scp.release();
+ return std::make_pair( false, false );
+ }
+
if ( !bTowerOk ) {
build_node( pNode );
nHeight = pNode->height();
bTowerOk = true;
}
-# ifdef CDS_CXX11_LAMBDA_SUPPORT
- if ( !insert_at_position( val, pNode, pos, [&func]( value_type& item ) { cds::unref(func)( true, item, item ); }))
-# else
- if ( !insert_at_position( val, pNode, pos, cds::ref(wrapper) ))
-# endif
- {
+ if ( !insert_at_position( val, pNode, pos, [&func]( value_type& item ) { func( true, item, item ); })) {
m_Stat.onInsertRetry();
continue;
}
++m_ItemCounter;
scp.release();
m_Stat.onAddNode( nHeight );
- m_Stat.onEnsureNew();
+ m_Stat.onUpdateNew();
return std::make_pair( true, true );
}
}
+ //@cond
+ template <typename Func>
+ CDS_DEPRECATED("ensure() is deprecated, use update()")
+ std::pair<bool, bool> ensure( value_type& val, Func func )
+ {
+ return update( val, func, true );
+ }
+ //@endcond
- /// Finds the key \p val
+ /// Finds \p key
/** \anchor cds_intrusive_SkipListSet_nogc_find_func
- The function searches the item with key equal to \p val and calls the functor \p f for item found.
+ The function searches the item with key equal to \p key and calls the functor \p f for item found.
The interface of \p Func functor is:
\code
struct functor {
- void operator()( value_type& item, Q& val );
+ void operator()( value_type& item, Q& key );
};
\endcode
- where \p item is the item found, \p val is the <tt>find</tt> function argument.
-
- You can pass \p f argument by value or by reference using <tt>boost::ref</tt> or cds::ref.
+ where \p item is the item found, \p key is the <tt>find</tt> function argument.
The functor can change non-key fields of \p item. Note that the functor is only guarantee
that \p item cannot be disposed during functor is executing.
The functor does not serialize simultaneous access to the set \p item. If such access is
possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
- The \p val argument is non-const since it can be used as \p f functor destination i.e., the functor
+ The \p key argument is non-const since it can be used as \p f functor destination i.e., the functor
can modify both arguments.
Note the hash functor specified for class \p Traits template parameter
should accept a parameter of type \p Q that can be not the same as \p value_type.
- The function returns \p true if \p val is found, \p false otherwise.
+ The function returns \p true if \p key is found, \p false otherwise.
*/
template <typename Q, typename Func>
- bool find( Q& val, Func f ) const
+ bool find( Q& key, Func f ) const
{
- return find_with_( val, key_comparator(), f ) != nullptr;
+ return find_with_( key, key_comparator(), f ) != nullptr;
}
+ //@cond
+ template <typename Q, typename Func>
+ bool find( Q const& key, Func f ) const
+ {
+ return find_with_( key, key_comparator(), f ) != nullptr;
+ }
+ //@endcond
- /// Finds the key \p val using \p pred predicate for comparing
+ /// Finds the key \p key using \p pred predicate for comparing
/**
The function is an analog of \ref cds_intrusive_SkipListSet_nogc_find_func "find(Q&, Func)"
but \p pred predicate is used for key compare.
\p pred must imply the same element order as the comparator used for building the set.
*/
template <typename Q, typename Less, typename Func>
- bool find_with( Q& val, Less pred, Func f ) const
- {
- return find_with_( val, cds::opt::details::make_comparator_from_less<Less>(), f ) != nullptr;
- }
-
- /// Finds the key \p val
- /** \anchor cds_intrusive_SkipListSet_nogc_find_cfunc
- The function searches the item with key equal to \p val and calls the functor \p f for item found.
- The interface of \p Func functor is:
- \code
- struct functor {
- void operator()( value_type& item, Q const& val );
- };
- \endcode
- where \p item is the item found, \p val is the <tt>find</tt> function argument.
-
- You can pass \p f argument by value or by reference using <tt>boost::ref</tt> or cds::ref.
-
- The functor can change non-key fields of \p item. Note that the functor is only guarantee
- that \p item cannot be disposed during functor is executing.
- The functor does not serialize simultaneous access to the set \p item. If such access is
- possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
-
- Note the hash functor specified for class \p Traits template parameter
- should accept a parameter of type \p Q that can be not the same as \p value_type.
-
- The function returns \p true if \p val is found, \p false otherwise.
- */
- template <typename Q, typename Func>
- bool find( Q const& val, Func f ) const
+ bool find_with( Q& key, Less pred, Func f ) const
{
- return find_with_( val, key_comparator(), f ) != nullptr;
+ CDS_UNUSED( pred );
+ return find_with_( key, cds::opt::details::make_comparator_from_less<Less>(), f ) != nullptr;
}
-
- /// Finds the key \p val using \p pred predicate for comparing
- /**
- The function is an analog of \ref cds_intrusive_SkipListSet_nogc_find_cfunc "find(Q const&, Func)"
- but \p pred predicate is used for key compare.
- \p Less has the interface like \p std::less.
- \p pred must imply the same element order as the comparator used for building the set.
- */
+ //@cond
template <typename Q, typename Less, typename Func>
- bool find_with( Q const& val, Less pred, Func f ) const
+ bool find_with( Q const& key, Less pred, Func f ) const
{
- return find_with_( val, cds::opt::details::make_comparator_from_less<Less>(), f ) != nullptr;
+ CDS_UNUSED( pred );
+ return find_with_( key, cds::opt::details::make_comparator_from_less<Less>(), f ) != nullptr;
}
+ //@endcond
- /// Finds the key \p val
- /** \anchor cds_intrusive_SkipListSet_nogc_find_val
- The function searches the item with key equal to \p val
- 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 can be not the same as \p value_type.
+ /// Checks whether the set contains \p key
+ /**
+ The function searches the item with key equal to \p key
+ and returns pointer to item found or \p nullptr.
*/
template <typename Q>
- value_type * find( Q const& val ) const
+ value_type * contains( Q const& key ) const
{
- node_type * pNode =
-# ifdef CDS_CXX11_LAMBDA_SUPPORT
- find_with_( val, key_comparator(), [](value_type& , Q const& ) {} );
-# else
- find_with_( val, key_comparator(), empty_find_functor() );
-# endif
+ node_type * pNode = find_with_( key, key_comparator(), [](value_type& , Q const& ) {} );
if ( pNode )
return node_traits::to_value_ptr( pNode );
return nullptr;
}
+ //@cond
+ template <typename Q>
+ CDS_DEPRECATED("deprecated, use contains()")
+ value_type * find( Q const& key ) const
+ {
+ return contains( key );
+ }
+ //@endcond
- /// Finds the key \p val using \p pred predicate for comparing
+ /// Checks whether the set contains \p key using \p pred predicate for searching
/**
- The function is an analog of \ref cds_intrusive_SkipListSet_nogc_find_val "find(Q const&)"
- but \p pred predicate is used for key compare.
- \p Less has the interface like \p std::less.
- \p pred must imply the same element order as the comparator used for building the set.
+ 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>
- value_type * find_with( Q const& val, Less pred ) const
+ value_type * contains( Q const& key, Less pred ) const
{
- node_type * pNode =
-# ifdef CDS_CXX11_LAMBDA_SUPPORT
- find_with_( val, cds::opt::details::make_comparator_from_less<Less>(), [](value_type& , Q const& ) {} );
-# else
- find_with_( val, cds::opt::details::make_comparator_from_less<Less>(), empty_find_functor() );
-# endif
+ CDS_UNUSED( pred );
+ node_type * pNode = find_with_( key, cds::opt::details::make_comparator_from_less<Less>(), [](value_type& , Q const& ) {} );
if ( pNode )
return node_traits::to_value_ptr( pNode );
return nullptr;
}
+ //@cond
+ template <typename Q, typename Less>
+ CDS_DEPRECATED("deprecated, use contains()")
+ value_type * find_with( Q const& key, Less pred ) const
+ {
+ return contains( key, pred );
+ }
+ //@endcond
/// Gets minimum key from the set
/**
/// Returns item count in the set
/**
The value returned depends on item counter type provided by \p Traits template parameter.
- If it is atomicity::empty_item_counter this function always returns 0.
- The function is not suitable for checking the set emptiness, use \ref empty
- member function for this purpose.
+ For \p atomicity::empty_item_counter the function always returns 0.
+ The function is not suitable for checking the set emptiness, use \p empty().
*/
size_t size() const
{
}} // namespace cds::intrusive
-#endif // #ifndef __CDS_INTRUSIVE_SKIP_LIST_IMPL_H
+#endif // #ifndef CDSLIB_INTRUSIVE_SKIP_LIST_IMPL_H
projects / libcds.git / blobdiff