-//$$CDS-header$$
-
-#ifndef __CDS_CONTAINER_SKIP_LIST_MAP_RCU_H
-#define __CDS_CONTAINER_SKIP_LIST_MAP_RCU_H
+/*
+ This file is a part of libcds - Concurrent Data Structures library
+
+ (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
+
+ 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_SKIP_LIST_MAP_RCU_H
+#define CDSLIB_CONTAINER_SKIP_LIST_MAP_RCU_H
#include <cds/container/details/skip_list_base.h>
#include <cds/intrusive/skip_list_rcu.h>
static CDS_CONSTEXPR const bool c_bExtractLockExternal = base_class::c_bExtractLockExternal;
/// pointer to extracted node
- typedef cds::urcu::exempt_ptr< gc, node_type, value_type, typename maker::intrusive_type_traits::disposer > exempt_ptr;
+ using exempt_ptr = cds::urcu::exempt_ptr< gc, node_type, value_type, typename maker::intrusive_type_traits::disposer >;
+
+ private:
+ //@cond
+ struct raw_ptr_converter
+ {
+ value_type * operator()( node_type * p ) const
+ {
+ return p ? &p->m_Value : nullptr;
+ }
+
+ value_type& operator()( node_type& n ) const
+ {
+ return n.m_Value;
+ }
+
+ value_type const& operator()( node_type const& n ) const
+ {
+ return n.m_Value;
+ }
+ };
+ //@endcond
+
+ public:
+ /// Result of \p get(), \p get_with() functions - pointer to the node found
+ typedef cds::urcu::raw_ptr_adaptor< value_type, typename base_class::raw_ptr, raw_ptr_converter > raw_ptr;
protected:
//@cond
{
return base_class::random_level();
}
-
- value_type * to_value_ptr( node_type * pNode ) const CDS_NOEXCEPT
- {
- return pNode ? &pNode->m_Value : nullptr;
- }
//@endcond
public:
{}
public:
- /// Iterator type
+ ///@name Forward ordered iterators (thread-safe under RCU lock)
+ //@{
+ /// Forward iterator
+ /**
+ The forward iterator has some features:
+ - it has no post-increment operator
+ - it depends on iterator of underlying \p OrderedList
+
+ You may safely use iterators in multi-threaded environment only under RCU lock.
+ Otherwise, a crash is possible if another thread deletes the element the iterator points to.
+ */
typedef skip_list::details::iterator< typename base_class::iterator > iterator;
/// Const iterator type
{
return const_iterator( base_class::cend() );
}
+ //@}
public:
/// Inserts new node with key and default value
template <typename K>
bool insert( K const& key )
{
- return insert_key( key, [](value_type&){} );
+ return insert_with( key, [](value_type&){} );
}
/// Inserts new node
RCU \p synchronize method can be called. RCU should not be locked.
*/
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 ); } )) {
return false;
}
- /// Ensures that the \p key exists in the map
+ /// Updates data by \p key
/**
The operation performs inserting or changing data with lock-free manner.
If the \p key not found in the map, then the new item created from \p key
- is inserted into the map (note that in this case the \ref key_type should be
- constructible from type \p K).
- Otherwise, the functor \p func is called with item found.
+ is inserted into the map iff \p bInsert is \p true.
+ Otherwise, if \p key found, the functor \p func is called with item found.
The functor \p Func interface is:
\code
struct my_functor {
void operator()( bool bNew, value_type& item );
};
\endcode
- with arguments:
+ where:
- \p bNew - \p true if the item has been inserted, \p false otherwise
- - \p item - item of the list
+ - \p item - item of the map
The functor may change any fields of \p item.second.
RCU \p synchronize() method can be called. RCU should not be locked.
- Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
- \p second is true if new item has been added or \p false if the item with \p key
- already is in the list.
+ Returns <tt> std::pair<bool, bool> </tt> 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 exists.
@warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
*/
template <typename K, typename Func>
- std::pair<bool, bool> ensure( K const& key, Func func )
+ std::pair<bool, bool> update( K const& key, Func func, bool bInsert = true )
{
scoped_node_ptr pNode( node_allocator().New( random_level(), key ));
- std::pair<bool, bool> res = base_class::ensure( *pNode,
- [&func](bool bNew, node_type& item, node_type const& ){ func( bNew, item.m_Value ); }
+ std::pair<bool, bool> res = base_class::update( *pNode,
+ [&func](bool bNew, node_type& item, node_type const& ){ func( bNew, item.m_Value );},
+ bInsert
);
if ( res.first && res.second )
pNode.release();
return res;
}
+ //@cond
+ template <typename K, typename Func>
+ CDS_DEPRECATED("ensure() is deprecated, use update()")
+ std::pair<bool, bool> ensure( K const& key, Func func )
+ {
+ return update( key, func, true );
+ }
+ //@endcond
/// Delete \p key from the map
/**\anchor cds_nonintrusive_SkipListMap_rcu_erase_val
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_rcu_extract
The function searches an item with key equal to \p key in the map,
- unlinks it from the set, and returns it in \p result parameter.
- If the item with key equal to \p key is not found the function returns \p false.
+ unlinks it from the set, and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the item found.
+ If the item is not found the function returns an empty \p exempt_ptr
Note the compare functor from \p Traits class' template argument
should accept a parameter of type \p K that can be not the same as \p key_type.
RCU \p synchronize() method can be called. RCU should NOT be locked.
The function does not free the item found.
- The item will be implicitly freed when \p result object is destroyed or when
- <tt>result.release()</tt> is called, see cds::urcu::exempt_ptr for explanation.
- @note Before reusing \p result object you should call its \p release() method.
+ The item will be implicitly freed when the returned object is destroyed or when
+ its \p release() member function is called.
*/
template <typename K>
- bool extract( exempt_ptr& result, K const& key )
+ exempt_ptr extract( K const& key )
{
- return base_class::do_extract( result, key );
+ return exempt_ptr( base_class::do_extract( key ));
}
/// Extracts the item from the map with comparing functor \p pred
/**
- The function is an analog of \ref cds_nonintrusive_SkipListMap_rcu_extract "extract(exempt_ptr&, K const&)"
- but \p pred predicate is used for key comparing.
+ The function is an analog of \p extract(K const&) but \p pred predicate is used for key comparing.
\p Less has the semantics like \p std::less.
\p pred must imply the same element order as the comparator used for building the map.
*/
template <typename K, typename Less>
- bool extract_with( exempt_ptr& result, K const& key, Less pred )
+ exempt_ptr extract_with( K const& key, Less pred )
{
- return base_class::do_extract_with( result, key, cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor >());
+ CDS_UNUSED( pred );
+ return exempt_ptr( base_class::do_extract_with( key, cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor >()));
}
/// 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 result parameter.
- If the skip-list is empty the function returns \p false.
+ The function searches an item with minimal key, unlinks it,
+ and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the item.
+ If the skip-list is empty the function returns an empty \p exempt_ptr.
RCU \p synchronize method can be called. RCU should NOT be locked.
The function does not free the item found.
- The item will be implicitly freed when \p result object is destroyed or when
- <tt>result.release()</tt> is called, see cds::urcu::exempt_ptr for explanation.
- @note Before reusing \p result object you should call its \p release() method.
+ The item will be implicitly freed when the returned object is destroyed or when
+ its \p release() member function is called.
*/
- bool extract_min( exempt_ptr& result )
+ exempt_ptr extract_min()
{
- return base_class::do_extract_min(result);
+ return exempt_ptr( base_class::do_extract_min());
}
/// Extracts an item with maximal key from the map
/**
- The function searches an item with maximal key, unlinks it from the set, and returns the item found
- in \p result parameter. If the skip-list is empty the function returns \p false.
+ The function searches an item with maximal key, unlinks it from the set,
+ and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the item.
+ If the skip-list is empty the function returns an empty \p exempt_ptr.
RCU \p synchronize method can be called. RCU should NOT be locked.
The function does not free the item found.
- The item will be implicitly freed when \p result object is destroyed or when
- <tt>result.release()</tt> is called, see cds::urcu::exempt_ptr for explanation.
- @note Before reusing \p result object you should call its \p release() method.
- */
- bool extract_max( exempt_ptr& result )
+ The item will be implicitly freed when the returned object is destroyed or when
+ its \p release() member function is called.
+ */
+ exempt_ptr extract_max()
{
- return base_class::do_extract_max(result);
+ return exempt_ptr( base_class::do_extract_max());
}
/// 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 );});
}
- /// Find the key \p key
- /** \anchor cds_nonintrusive_SkipListMap_rcu_find_val
-
+ /// Checks whether the map 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.
The function applies RCU lock internally.
*/
template <typename K>
+ bool contains( K const& key )
+ {
+ return base_class::contains( key );
+ }
+ //@cond
+ template <typename K>
+ CDS_DEPRECATED("deprecated, use contains()")
bool find( K const& key )
{
- return base_class::find( key );
+ return contains( key );
}
+ //@endcond
- /// Finds the key \p val using \p pred predicate for searching
+ /// Checks whether the map contains \p key using \p pred predicate for searching
/**
- The function is an analog of \ref cds_nonintrusive_SkipListMap_rcu_find_val "find(K 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 map.
+ \p Less must imply the same element order as the comparator used for building the set.
*/
template <typename K, typename Less>
+ bool contains( K const& key, Less pred )
+ {
+ CDS_UNUSED( pred );
+ return base_class::contains( key, cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor >() );
+ }
+ //@cond
+ template <typename K, typename Less>
+ CDS_DEPRECATED("deprecated, use contains()")
bool find_with( K const& key, Less pred )
{
- return base_class::find_with( key, cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor >() );
+ return contains( key, pred );
}
+ //@endcond
/// Finds the key \p key and return the item found
/** \anchor cds_nonintrusive_SkipListMap_rcu_get
- The function searches the item with key equal to \p key and returns the pointer to item found.
- If \p key is not found it returns \p nullptr.
+ The function searches the item with key equal to \p key and returns a \p raw_ptr object pointing to an item found.
+ If \p key is not found it returns empty \p raw_ptr.
Note the compare functor in \p Traits class' template argument
should accept a parameter of type \p K that can be not the same as \p key_type.
typedef cds::container::SkipListMap< cds::urcu::gc< cds::urcu::general_buffered<> >, int, foo, my_traits > skip_list;
skip_list theList;
// ...
+ typename skip_list::raw_ptr pVal;
{
// Lock RCU
skip_list::rcu_lock lock;
- skip_list::value_type * pVal = theList.get( 5 );
- // Deal with pVal
- //...
-
- // Unlock RCU by rcu_lock destructor
- // pVal can be freed at any time after RCU unlocking
+ pVal = theList.get( 5 );
+ if ( pVal ) {
+ // Deal with pVal
+ //...
+ }
}
+ // You can manually release pVal after RCU-locked section
+ pVal.release();
\endcode
-
- After RCU unlocking the \p %force_dispose member function can be called manually,
- see \ref force_dispose for explanation.
*/
template <typename K>
- value_type * get( K const& key )
+ raw_ptr get( K const& key )
{
- return to_value_ptr( base_class::get( key ));
+ return raw_ptr( base_class::get( key ));
}
/// Finds the key \p key and return the item found
\p pred must imply the same element order as the comparator used for building the map.
*/
template <typename K, typename Less>
- value_type * get_with( K const& key, Less pred )
+ raw_ptr get_with( K const& key, Less pred )
{
- return to_value_ptr( base_class::get_with( key, cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor >() ));
+ CDS_UNUSED( pred );
+ return raw_ptr( base_class::get_with( key, cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor >() ));
}
/// Clears the map (not atomic)
{
return base_class::statistics();
}
-
- /// Clears internal list of ready-to-delete items passing them to RCU reclamation cycle
- /** @copydetails cds_intrusive_SkipListSet_rcu_force_dispose
- */
- void force_dispose()
- {
- return base_class::force_dispose();
- }
};
}} // namespace cds::container
-#endif // #ifndef __CDS_CONTAINER_SKIP_LIST_MAP_RCU_H
+#endif // #ifndef CDSLIB_CONTAINER_SKIP_LIST_MAP_RCU_H
projects / libcds.git / blobdiff