#ifndef __CDS_CONTAINER_IMPL_ELLEN_BINTREE_MAP_H
#define __CDS_CONTAINER_IMPL_ELLEN_BINTREE_MAP_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>
@note Do not include <tt><cds/container/impl/ellen_bintree_map.h></tt> header file directly.
There are header file for each GC type:
- <tt><cds/container/ellen_bintree_map_hp.h></tt> - for Hazard Pointer GC cds::gc::HP
- - <tt><cds/container/ellen_bintree_map_dhp.h></tt> - for Pass-the-Buck GC cds::gc::DHP
+ - <tt><cds/container/ellen_bintree_map_dhp.h></tt> - for Dynamic Hazard Pointer GC cds::gc::DHP
- <tt><cds/container/ellen_bintree_map_rcu.h></tt> - for RCU GC
(see \ref cds_container_EllenBinTreeMap_rcu "RCU-based EllenBinTreeMap")
*/
typedef Key key_type; ///< type of a key stored in the map
typedef T mapped_type; ///< type of value stored in the map
typedef std::pair< key_type const, mapped_type > value_type ; ///< Key-value pair stored in leaf node of the mp
- typedef Traits traits; ///< Map traits
+ typedef Traits traits; ///< Map traits
# ifdef CDS_DOXYGEN_INVOKED
typedef implementation_defined key_comparator; ///< key compare functor based on \p Traits::compare and \p Traits::less
# 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
typedef typename base_class::memory_model memory_model; ///< Memory ordering, see \p cds::opt::memory_model
typedef typename base_class::node_allocator node_allocator_type; ///< allocator for maintaining internal node
typedef typename base_class::stat stat; ///< internal statistics type
typedef typename traits::copy_policy copy_policy; ///< key copy policy
+ 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
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 K>
bool insert( K const& key )
{
- return insert_key( key, [](value_type&){} );
+ return insert_with( key, [](value_type&){} );
}
/// Inserts new node
it is preferable that the initialization should be completed only if inserting is successful.
*/
template <typename K, typename Func>
- bool insert_key( const K& key, Func func )
+ bool insert_with( const K& key, Func func )
{
scoped_node_ptr pNode( cxx_leaf_node_allocator().New( key ));
if ( base_class::insert( *pNode, [&func]( leaf_node& item ) { func( item.m_Value ); } )) {
template <typename K, typename Less>
bool erase_with( K const& key, Less pred )
{
+ CDS_UNUSED( pred );
return base_class::erase_with( key, cds::details::predicate_wrapper< leaf_node, Less, typename maker::key_accessor >());
}
template <typename K, typename Less, typename Func>
bool erase_with( K const& key, Less pred, Func f )
{
+ CDS_UNUSED( pred );
return base_class::erase_with( key, cds::details::predicate_wrapper< leaf_node, Less, typename maker::key_accessor >(),
[&f]( leaf_node& node) { f( node.m_Value ); } );
}
/// Extracts an item with minimal key from the map
/**
- If the map is not empty, the function returns \p true, \p result contains a pointer to minimum value.
- If the map is empty, the function returns \p false, \p result is left unchanged.
+ If the map is not empty, the function returns an guarded pointer to minimum value.
+ If the map is empty, the function returns an empty \p guarded_ptr.
@note Due the concurrent nature of the map, 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 result 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 map
/**
- If the map is not empty, the function returns \p true, \p result contains a pointer to maximal value.
- If the map is empty, the function returns \p false, \p result is left unchanged.
+ If the map is not empty, the function returns a guarded pointer to maximal value.
+ If the map is empty, the function returns an empty \p guarded_ptr.
@note Due the concurrent nature of the map, 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 result 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_EllenBinTreeMap_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 a guarded pointer to an item found.
+ If the item is not found the function returns an empty \p guarded_ptr.
- The guarded pointer \p result 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 map using \p pred for searching
/**
- The function is an analog of \ref cds_nonintrusive_EllenBinTreeMap_extract "extract(guarded_ptr&, Q const&)"
+ The function is an analog of \ref cds_nonintrusive_EllenBinTreeMap_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 map.
*/
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::key_accessor >());
+ return gp;
}
/// Find the key \p key
template <typename K, typename Less, typename Func>
bool find_with( K const& key, Less pred, Func f )
{
+ CDS_UNUSED( pred );
return base_class::find_with( key, cds::details::predicate_wrapper< leaf_node, Less, typename maker::key_accessor >(),
[&f](leaf_node& item, K const& ) { f( item.m_Value );});
}
template <typename K, typename Less>
bool find_with( K const& key, Less pred )
{
+ CDS_UNUSED( pred );
return base_class::find_with( key, cds::details::predicate_wrapper< leaf_node, Less, typename maker::key_accessor >() );
}
/// Finds \p key and returns the item found
/** @anchor cds_nonintrusive_EllenBinTreeMap_get
- The function searches the item with key equal to \p key and returns the item found in \p result parameter.
- The function returns \p true if \p key is found, \p false otherwise.
+ The function searches the item with key equal to \p key and returns the item found as a guarded pointer.
+ If \p key is not foudn the function returns an empty \p guarded_ptr.
- The guarded pointer \p result 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_EllenBinTreeMap_get "get(guarded_ptr&, Q const&)"
+ The function is an analog of \ref cds_nonintrusive_EllenBinTreeMap_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 map.
*/
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::key_accessor >() );
+ return gp;
}
/// Clears the map (not atomic)
projects / libcds.git / blobdiff