#ifndef __CDS_CONTAINER_IMPL_SKIP_LIST_MAP_H
#define __CDS_CONTAINER_IMPL_SKIP_LIST_MAP_H
-#include <cds/gc/guarded_ptr.h>
#include <cds/container/details/guarded_ptr_cast.h>
namespace cds { namespace container {
- \p K - type of a key to be stored in the list.
- \p T - type of a value to be stored in the list.
- \p Traits - map traits, default is \p skip_list::traits
- It is possible to declare option-based list with \p cds::container::skip_list::make_traits metafunction
+ It is possible to declare option-based list with \p cds::container::skip_list::make_traits metafunction
istead of \p Traits template argument.
Like STL map class, \p %SkipListMap stores the key-value pair as <tt>std:pair< K const, T></tt>.
before end of the map. Therefore, such iteration is more suitable for debugging purpose only
Remember, each iterator object requires 2 additional hazard pointers, that may be
- a limited resource for \p GC like \p gc::HP (for gc::PTB the count of
+ a limited resource for \p GC like \p gc::HP (for gc::DHP the count of
guards is unlimited).
The iterator class supports the following minimalistic interface:
public:
/// Guarded pointer
- typedef cds::gc::guarded_ptr< gc, node_type, value_type, details::guarded_ptr_cast_set<node_type, value_type> > guarded_ptr;
+ typedef typename gc::template guarded_ptr< node_type, value_type, details::guarded_ptr_cast_set<node_type, value_type> > guarded_ptr;
protected:
//@cond
template <typename K>
bool insert( K const& key )
{
- return insert_key( key, [](value_type&){} );
+ return insert_with( key, [](value_type&){} );
}
/// Inserts new node
template <typename K, typename V>
bool insert( K const& key, V const& val )
{
- return insert_key( key, [&val](value_type& item) { item.second = val ; } );
+ return insert_with( key, [&val](value_type& item) { item.second = val ; } );
}
/// Inserts new node and initialize it by a functor
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( node_allocator().New( random_level(), key ));
if ( base_class::insert( *pNode, [&func]( node_type& 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< node_type, 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< node_type, Less, typename maker::key_accessor >(),
[&f]( node_type& node) { f( node.m_Value ); } );
/// Extracts the item from the map with specified \p key
/** \anchor cds_nonintrusive_SkipListMap_hp_extract
The function searches an item with key equal to \p key in the map,
- unlinks it from the map, and returns it in \p ptr parameter.
- If the item with key equal to \p key is not found the function returns \p false.
+ unlinks it from the map, and returns a guarded pointer to the item found.
+ If \p key is not found the function returns an empty guarded pointer.
Note the compare functor should accept a parameter of type \p K that can be not the same as \p key_type.
The item extracted is freed automatically by garbage collector \p GC
- when returned \ref guarded_ptr object will be destroyed or released.
+ when returned \p guarded_ptr object will be destroyed or released.
@note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
Usage:
skip_list theList;
// ...
{
- skip_list::guarded_ptr gp;
- if ( theList.extract( gp, 5 ) ) {
+ skip_list::guarded_ptr gp( theList.extract( 5 ));
+ if ( gp ) {
// Deal with gp
// ...
}
\endcode
*/
template <typename K>
- bool extract( guarded_ptr& ptr, K const& key )
+ guarded_ptr extract( K const& key )
{
- return base_class::extract_( ptr.guard(), key, typename base_class::key_comparator() );
+ guarded_ptr gp;
+ base_class::extract_( gp.guard(), key, typename base_class::key_comparator() );
+ return gp;
}
/// Extracts the item from the map with comparing functor \p pred
\p pred must imply the same element order as the comparator used for building the map.
*/
template <typename K, typename Less>
- bool extract_with( guarded_ptr& ptr, K const& key, Less pred )
+ guarded_ptr extract_with( K const& key, Less pred )
{
+ CDS_UNUSED( pred );
typedef cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor > wrapped_less;
- return base_class::extract_( ptr.guard(), key, cds::opt::details::make_comparator_from_less<wrapped_less>() );
+ guarded_ptr gp;
+ base_class::extract_( gp.guard(), key, cds::opt::details::make_comparator_from_less<wrapped_less>() );
+ return gp;
}
/// Extracts an item with minimal key from the map
/**
- The function searches an item with minimal key, unlinks it, and returns the item found in \p ptr parameter.
- If the skip-list is empty the function returns \p false.
+ The function searches an item with minimal key, unlinks it, and returns an guarded pointer to the item found.
+ If the skip-list is empty the function returns an empty guarded pointer.
The item extracted is freed automatically by garbage collector \p GC
- when returned \ref guarded_ptr object will be destroyed or released.
+ when returned \p guarded_ptr object will be destroyed or released.
@note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
Usage:
skip_list theList;
// ...
{
- skip_list::guarded_ptr gp;
- if ( theList.extract_min( gp )) {
+ skip_list::guarded_ptr gp( theList.extract_min());
+ if ( gp ) {
// Deal with gp
//...
}
}
\endcode
*/
- bool extract_min( guarded_ptr& ptr)
+ guarded_ptr extract_min()
{
- return base_class::extract_min_( ptr.guard() );
+ guarded_ptr gp;
+ base_class::extract_min_( gp.guard() );
+ return gp;
}
/// Extracts an item with maximal key from the map
/**
- The function searches an item with maximal key, unlinks it, and returns the pointer to item found in \p ptr parameter.
- If the skip-list is empty the function returns empty \p guarded_ptr.
+ The function searches an item with maximal key, unlinks it, and returns a guarded pointer to item found.
+ If the skip-list is empty the function returns an empty \p guarded_ptr.
The item found is freed by garbage collector \p GC automatically
- when returned \ref guarded_ptr object will be destroyed or released.
+ when returned \p guarded_ptr object will be destroyed or released.
@note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
Usage:
skip_list theList;
// ...
{
- skip_list::guarded_ptr gp;
- if ( theList.extract_max( gp )) {
+ skip_list::guarded_ptr gp( theList.extract_max());
+ if ( gp ) {
// Deal with gp
//...
}
}
\endcode
*/
- bool extract_max( guarded_ptr& dest )
+ guarded_ptr extract_max()
{
- return base_class::extract_max_( dest.guard() );
+ guarded_ptr gp;
+ base_class::extract_max_( gp.guard() );
+ 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< node_type, Less, typename maker::key_accessor >(),
[&f](node_type& 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< node_type, Less, typename maker::key_accessor >() );
}
/// Finds the key \p key and return the item found
/** \anchor cds_nonintrusive_SkipListMap_hp_get
The function searches the item with key equal to \p key
- and assigns the item found to guarded pointer \p ptr.
- The function returns \p true if \p key is found, and \p false otherwise.
- If \p key is not found the \p ptr parameter is not changed.
+ and returns an guarded pointer to the item found.
+ If \p key is not found the function returns an empty guarded pointer.
- It is safe when a concurrent thread erases the item returned in \p ptr guarded pointer.
+ It is safe when a concurrent thread erases the item returned as \p guarded_ptr.
In this case the item will be freed later by garbage collector \p GC automatically
when \p guarded_ptr object will be destroyed or released.
@note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
skip_list theList;
// ...
{
- skip_list::guarded_ptr gp;
- if ( theList.get( gp, 5 ) ) {
+ skip_list::guarded_ptr gp( theList.get( 5 ));
+ if ( gp ) {
// Deal with gp
//...
}
should accept a parameter of type \p K that can be not the same as \p value_type.
*/
template <typename K>
- bool get( guarded_ptr& ptr, K const& key )
+ guarded_ptr get( K const& key )
{
- return base_class::get_with_( ptr.guard(), key, typename base_class::key_comparator() );
+ guarded_ptr gp;
+ base_class::get_with_( gp.guard(), key, typename base_class::key_comparator() );
+ return gp;
}
/// Finds the key \p key and return the item found
/**
- The function is an analog of \ref cds_nonintrusive_SkipListMap_hp_get "get( guarded_ptr& ptr, K const&)"
+ The function is an analog of \ref cds_nonintrusive_SkipListMap_hp_get "get( K const&)"
but \p pred is used for comparing the keys.
\p Less functor has the semantics like \p std::less but should take arguments of type \ref key_type and \p K
\p pred must imply the same element order as the comparator used for building the map.
*/
template <typename K, typename Less>
- bool get_with( guarded_ptr& ptr, K const& key, Less pred )
+ guarded_ptr get_with( K const& key, Less pred )
{
+ CDS_UNUSED( pred );
typedef cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor > wrapped_less;
- return base_class::get_with_( ptr.guard(), key, cds::opt::details::make_comparator_from_less< wrapped_less >());
+ guarded_ptr gp;
+ base_class::get_with_( gp.guard(), key, cds::opt::details::make_comparator_from_less< wrapped_less >());
+ return gp;
}
/// Clears the map
projects / libcds.git / blobdiff