//$$CDS-header$$
-#ifndef __CDS_CONTAINER_IMPL_ELLEN_BINTREE_SET_H
-#define __CDS_CONTAINER_IMPL_ELLEN_BINTREE_SET_H
+#ifndef CDSLIB_CONTAINER_IMPL_ELLEN_BINTREE_SET_H
+#define CDSLIB_CONTAINER_IMPL_ELLEN_BINTREE_SET_H
-#include <traits>
+#include <type_traits>
#include <cds/container/details/ellen_bintree_base.h>
#include <cds/intrusive/impl/ellen_bintree.h>
#include <cds/container/details/guarded_ptr_cast.h>
# ifdef CDS_DOXYGEN_INVOKED
typedef implementation_defined key_comparator ; ///< key compare functor based on opt::compare and opt::less option setter.
# else
- typedef typename maker::intrusive_type_traits::compare key_comparator;
+ typedef typename maker::intrusive_traits::compare key_comparator;
# endif
typedef typename base_class::item_counter item_counter; ///< Item counting policy used
typedef typename base_class::memory_model memory_model; ///< Memory ordering. See cds::opt::memory_model option
typedef typename base_class::stat stat; ///< internal statistics type
typedef typename traits::key_extractor key_extractor; ///< key extracting functor
+ typedef typename traits::back_off back_off; ///< Back-off strategy
typedef typename traits::allocator allocator_type; ///< Allocator for leaf nodes
typedef typename base_class::node_allocator node_allocator; ///< Internal node allocator
typedef typename base_class::update_desc_allocator update_desc_allocator; ///< Update descriptor allocator
+ //@cond
+ typedef cds::container::ellen_bintree::implementation_tag implementation_tag;
+ //@endcond
+
protected:
//@cond
typedef typename maker::cxx_leaf_node_allocator cxx_leaf_node_allocator;
public:
/// Guarded pointer
- typedef cds::gc::guarded_ptr< gc, leaf_node, value_type, details::guarded_ptr_cast_set<leaf_node, value_type> > guarded_ptr;
+ typedef typename gc::template guarded_ptr< leaf_node, value_type, details::guarded_ptr_cast_set<leaf_node, value_type> > guarded_ptr;
public:
/// Default constructor
template <typename Q, typename Less>
bool erase_with( Q const& key, Less pred )
{
+ CDS_UNUSED( pred );
return base_class::erase_with( key, cds::details::predicate_wrapper< leaf_node, Less, typename maker::value_accessor >());
}
template <typename Q, typename Less, typename Func>
bool erase_with( Q const& key, Less pred, Func f )
{
+ CDS_UNUSED( pred );
return base_class::erase_with( key, cds::details::predicate_wrapper< leaf_node, Less, typename maker::value_accessor >(),
[&f]( leaf_node const& node) { f( node.m_Value ); } );
}
/// Extracts an item with minimal key from the set
/**
- If the set is not empty, the function returns \p true, \p result contains a pointer to minimum value.
- If the set is empty, the function returns \p false, \p result is left unchanged.
+ If the set is not empty, the function returns a guarded pointer to minimum value.
+ If the set is empty, the function returns an empty \p guarded_ptr.
@note Due the concurrent nature of the set, the function extracts <i>nearly</i> minimum key.
It means that the function gets leftmost leaf of the tree and tries to unlink it.
During unlinking, a concurrent thread may insert an item with key less than leftmost item's key.
So, the function returns the item with minimum key at the moment of tree traversing.
- The guarded pointer \p dest prevents deallocation of returned item,
- see cds::gc::guarded_ptr for explanation.
+ The guarded pointer prevents deallocation of returned item,
+ see \p cds::gc::guarded_ptr for explanation.
@note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
*/
- bool extract_min( guarded_ptr& result )
+ guarded_ptr extract_min()
{
- return base_class::extract_min_( result.guard() );
+ guarded_ptr gp;
+ base_class::extract_min_( gp.guard() );
+ return gp;
}
/// Extracts an item with maximal key from the set
/**
- If the set is not empty, the function returns \p true, \p result contains a pointer to maximal value.
- If the set is empty, the function returns \p false, \p result is left unchanged.
+ If the set is not empty, the function returns a guarded pointer to maximal value.
+ If the set is empty, the function returns an empty \p guarded_ptr.
@note Due the concurrent nature of the set, the function extracts <i>nearly</i> maximal key.
It means that the function gets rightmost leaf of the tree and tries to unlink it.
During unlinking, a concurrent thread may insert an item with key great than leftmost item's key.
So, the function returns the item with maximum key at the moment of tree traversing.
- The guarded pointer \p dest prevents deallocation of returned item,
- see cds::gc::guarded_ptr for explanation.
+ The guarded pointer prevents deallocation of returned item,
+ see \p cds::gc::guarded_ptr for explanation.
@note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
*/
- bool extract_max( guarded_ptr& result )
+ guarded_ptr extract_max()
{
- return base_class::extract_max_( result.guard() );
+ guarded_ptr gp;
+ base_class::extract_max_( gp.guard() );
+ return gp;
}
/// Extracts an item from the tree
/** \anchor cds_nonintrusive_EllenBinTreeSet_extract
The function searches an item with key equal to \p key in the tree,
- unlinks it, and returns pointer to an item found in \p result parameter.
- If the item is not found the function returns \p false.
+ unlinks it, and returns an guarded pointer to it.
+ If the item is not found the function returns an empty \p guarded_ptr.
- The guarded pointer \p dest prevents deallocation of returned item,
- see cds::gc::guarded_ptr for explanation.
+ The guarded pointer prevents deallocation of returned item,
+ see \p cds::gc::guarded_ptr for explanation.
@note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
*/
template <typename Q>
- bool extract( guarded_ptr& result, Q const& key )
+ guarded_ptr extract( Q const& key )
{
- return base_class::extract_( result.guard(), key );
+ guarded_ptr gp;
+ base_class::extract_( gp.guard(), key );
+ return gp;
}
/// Extracts an item from the set using \p pred for searching
/**
- The function is an analog of \ref cds_nonintrusive_EllenBinTreeSet_extract "extract(guarded_ptr& dest, Q const&)"
+ The function is an analog of \ref cds_nonintrusive_EllenBinTreeSet_extract "extract(Q const&)"
but \p pred 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.
*/
template <typename Q, typename Less>
- bool extract_with( guarded_ptr& result, Q const& key, Less pred )
+ guarded_ptr extract_with( Q const& key, Less pred )
{
- return base_class::extract_with_( result.guard(), key,
+ CDS_UNUSED( pred );
+ guarded_ptr gp;
+ base_class::extract_with_( gp.guard(), key,
cds::details::predicate_wrapper< leaf_node, Less, typename maker::value_accessor >());
+ return gp;
}
/// Find the key \p key
template <typename Q, typename Less, typename Func>
bool find_with( Q& key, Less pred, Func f )
{
+ CDS_UNUSED( pred );
return base_class::find_with( key, cds::details::predicate_wrapper< leaf_node, Less, typename maker::value_accessor >(),
[&f]( leaf_node& node, Q& v ) { f( node.m_Value, v ); } );
}
template <typename Q, typename Less, typename Func>
bool find_with( Q const& key, Less pred, Func f )
{
+ CDS_UNUSED( pred );
return base_class::find_with( key, cds::details::predicate_wrapper< leaf_node, Less, typename maker::value_accessor >(),
[&f]( leaf_node& node, Q const& v ) { f( node.m_Value, v ); } );
}
template <typename Q, typename Less>
bool find_with( Q const& key, Less pred )
{
+ CDS_UNUSED( pred );
return base_class::find_with( key, cds::details::predicate_wrapper< leaf_node, Less, typename maker::value_accessor >());
}
/// Finds \p key and returns the item found
/** @anchor cds_nonintrusive_EllenBinTreeSet_get
- The function searches the item with key equal to \p key and returns the item found in \p result parameter.
+ The function searches the item with key equal to \p key and returns the item found as an guarded pointer.
The function returns \p true if \p key is found, \p false otherwise.
- The guarded pointer \p dest prevents deallocation of returned item,
- see cds::gc::guarded_ptr for explanation.
+ The guarded pointer prevents deallocation of returned item,
+ see \p cds::gc::guarded_ptr for explanation.
@note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
*/
template <typename Q>
- bool get( guarded_ptr& result, Q const& key )
+ guarded_ptr get( Q const& key )
{
- return base_class::get_( result.guard(), key );
+ guarded_ptr gp;
+ base_class::get_( gp.guard(), key );
+ return gp;
}
/// Finds \p key with predicate \p pred and returns the item found
/**
- The function is an analog of \ref cds_nonintrusive_EllenBinTreeSet_get "get(guarded_ptr&, Q const&)"
+ The function is an analog of \ref cds_nonintrusive_EllenBinTreeSet_get "get(Q const&)"
but \p pred is used for key comparing.
\p Less functor has the interface like \p std::less.
\p pred must imply the same element order as the comparator used for building the set.
*/
template <typename Q, typename Less>
- bool get_with( guarded_ptr& result, Q const& key, Less pred )
+ guarded_ptr get_with( Q const& key, Less pred )
{
- return base_class::get_with_( result.guard(), key,
+ CDS_UNUSED(pred);
+ guarded_ptr gp;
+ base_class::get_with_( gp.guard(), key,
cds::details::predicate_wrapper< leaf_node, Less, typename maker::value_accessor >() );
+ return gp;
}
/// Clears the set (not atomic)
}} // namespace cds::container
-#endif // #ifndef __CDS_CONTAINER_IMPL_ELLEN_BINTREE_SET_H
+#endif // #ifndef CDSLIB_CONTAINER_IMPL_ELLEN_BINTREE_SET_H
projects / libcds.git / blobdiff