//$$CDS-header$$
-#ifndef __CDS_CONTAINER_MICHAEL_KVLIST_RCU_H
-#define __CDS_CONTAINER_MICHAEL_KVLIST_RCU_H
+#ifndef CDSLIB_CONTAINER_MICHAEL_KVLIST_RCU_H
+#define CDSLIB_CONTAINER_MICHAEL_KVLIST_RCU_H
#include <memory>
#include <functional> // ref
#endif
typedef Traits traits; ///< List traits
- typedef typename base_class::back_off back_off; ///< Back-off strategy
- typedef typename maker::allocator_type allocator_type; ///< Allocator type used for allocate/deallocate the nodes
- typedef typename base_class::item_counter item_counter; ///< Item counting policy
- typedef typename maker::key_comparator key_comparator; ///< key comparison functor
- typedef typename base_class::memory_model memory_model; ///< Memory ordering. See \p michael_list::traits::memory_model
+ typedef typename base_class::back_off back_off; ///< Back-off strategy
+ typedef typename maker::allocator_type allocator_type; ///< Allocator type used for allocate/deallocate the nodes
+ typedef typename base_class::item_counter item_counter; ///< Item counting policy
+ typedef typename maker::key_comparator key_comparator; ///< key comparison functor
+ typedef typename base_class::memory_model memory_model; ///< Memory ordering. See \p michael_list::traits::memory_model
typedef typename base_class::rcu_check_deadlock rcu_check_deadlock ; ///< RCU deadlock checking policy
typedef typename gc::scoped_lock rcu_lock ; ///< RCU scoped lock
- static CDS_CONSTEXPR const bool c_bExtractLockExternal = base_class::c_bExtractLockExternal; ///< Group of \p extract_xxx functions require external locking
+ static CDS_CONSTEXPR const bool c_bExtractLockExternal = base_class::c_bExtractLockExternal; ///< Group of \p extract_xxx functions do not require external locking
protected:
//@cond
cds::urcu::details::conventional_exempt_pair_cast<node_type, value_type>
>;
+ private:
+ //@cond
+ struct raw_ptr_converter
+ {
+ value_type * operator()( node_type * p ) const
+ {
+ return p ? &p->m_Data : nullptr;
+ }
+
+ value_type& operator()( node_type& n ) const
+ {
+ return n.m_Data;
+ }
+
+ value_type const& operator()( node_type const& n ) const
+ {
+ return n.m_Data;
+ }
+ };
+ //@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
template <typename K>
In trivial case, \p K is equal to \ref key_type.
- The \ref mapped_type should be default-constructible.
- The function makes RCU lock internally.
+ The function applies RCU lock internally.
Returns \p true if inserting successful, \p false otherwise.
*/
- The \ref key_type should be constructible from \p key of type \p K.
- The \ref mapped_type should be constructible from \p val of type \p V.
- The function makes RCU lock internally.
+ The function applies RCU lock internally.
Returns \p true if inserting successful, \p false otherwise.
*/
This can be useful if complete initialization of object of \p mapped_type is heavyweight and
it is preferable that the initialization should be completed only if inserting is successful.
- The function makes RCU lock internally.
+ The function applies RCU lock internally.
@warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
*/
template <typename K, typename Func>
- bool insert_key( const K& key, Func func )
+ bool insert_with( const K& key, Func func )
{
- return insert_key_at( head(), key, func );
+ return insert_with_at( head(), key, func );
}
/// Ensures that the \p key exists in the list
however, \p func must guarantee that during changing no any other modifications
could be made on this item by concurrent threads.
- The function makes RCU lock internally.
+ The function applies RCU lock internally.
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
/**
Returns \p true if inserting successful, \p false otherwise.
- The function makes RCU lock internally.
+ The function applies RCU lock internally.
*/
template <typename K, typename... Args>
bool emplace( K&& key, Args&&... args )
The functor \p Func interface:
\code
- struct extractor {
+ struct functor {
void operator()(value_type& val) { ... }
};
\endcode
unlinks it from the list, and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the item found.
If \p key is not found the function returns an empty \p exempt_ptr.
- @note The function does NOT call RCU read-side lock or synchronization,
- and does NOT dispose the item found. It just excludes the item from the list
- and returns a pointer to item found.
- You should lock RCU before calling this function.
+ @note The function does NOT dispose the item found.
+ It just excludes the item from the list and returns a pointer to item found.
+ You shouldn't lock RCU before calling this function.
\code
#include <cds/urcu/general_buffered.h>
// ...
rcu_michael_list::exempt_ptr p;
- {
- // first, we should lock RCU
- rcu_michael_list::rcu_lock sl;
-
- // Now, you can apply extract function
- // Note that you must not delete the item found inside the RCU lock
- p = theList.extract( 10 );
- if ( p ) {
- // do something with p
- ...
- }
+
+ // The RCU should NOT be locked when extract() is called!
+ assert( !rcu::is_locked() );
+
+ // extract() call
+ p = theList.extract( 10 );
+ if ( p ) {
+ // do something with p
+ ...
}
- // Outside RCU lock section we may safely release extracted pointer.
+
+ // we may safely release extracted pointer here.
// release() passes the pointer to RCU reclamation cycle.
p.release();
\endcode
/// Extracts an item from the list using \p pred predicate for searching
/**
- This function is the analog for \ref cds_nonintrusive_MichaelKVList_rcu_extract "extract(exempt_ptr&, K const&)".
+ This function is the analog for \p extract(K const&).
The \p pred is a predicate used for key comparing.
\p Less has the interface like \p std::less.
\p pred must imply the same element order as \ref key_comparator.
The function makes RCU lock internally.
*/
template <typename Q>
- bool find( Q const& key ) const
+ bool find( Q const& key )
{
return find_at( head(), key, intrusive_key_comparator() );
}
\p pred must imply the same element order as the comparator used for building the list.
*/
template <typename Q, typename Less>
- bool find_with( Q const& key, Less pred ) const
+ bool find_with( Q const& key, Less pred )
{
CDS_UNUSED( pred );
return find_at( head(), key, typename maker::template less_wrapper<Less>::type() );
The function returns \p true if \p key is found, \p false otherwise.
*/
template <typename Q, typename Func>
- bool find( Q const& key, Func f ) const
+ bool find( Q const& key, Func f )
{
return find_at( head(), key, intrusive_key_comparator(), f );
}
\p pred must imply the same element order as the comparator used for building the list.
*/
template <typename Q, typename Less, typename Func>
- bool find_with( Q const& key, Less pred, Func f ) const
+ bool find_with( Q const& key, Less pred, Func f )
{
CDS_UNUSED( pred );
return find_at( head(), key, typename maker::template less_wrapper<Less>::type(), f );
/// Finds \p key and return the item found
/** \anchor cds_nonintrusive_MichaelKVList_rcu_get
The function searches the item with \p key and returns the pointer to item found.
- If \p key is not found it returns \p nullptr.
+ If \p key is not found it returns an empty \p raw_ptr object.
Note the compare functor should accept a parameter of type \p K that can be not the same as \p key_type.
typedef cds::container::MichaelKVList< cds::urcu::gc< cds::urcu::general_buffered<> >, int, foo, my_traits > ord_list;
ord_list theList;
// ...
+ tyename ord_list::raw_ptr rp;
{
// Lock RCU
ord_list::rcu_lock lock;
- ord_list::value_type * pVal = theList.get( 5 );
- if ( pVal ) {
- // Deal with pVal
+ rp = theList.get( 5 );
+ if ( rp ) {
+ // Deal with rp
//...
}
// Unlock RCU by rcu_lock destructor
- // pVal can be freed at any time after RCU has been unlocked
}
+ // rp can be released at any time after RCU has been unlocked
+ rp.release();
\endcode
*/
template <typename K>
- value_type * get( K const& key ) const
+ raw_ptr get( K const& key )
{
return get_at( head(), key, intrusive_key_comparator());
}
\p pred must imply the same element order as the comparator used for building the list.
*/
template <typename K, typename Less>
- value_type * get_with( K const& key, Less pred ) const
+ raw_ptr get_with( K const& key, Less pred )
{
CDS_UNUSED( pred );
return get_at( head(), key, typename maker::template less_wrapper<Less>::type() );
}
template <typename K, typename Func>
- bool insert_key_at( head_type& refHead, const K& key, Func f )
+ bool insert_with_at( head_type& refHead, const K& key, Func f )
{
scoped_node_ptr pNode( alloc_node( key ));
}
template <typename K, typename Compare>
- bool find_at( head_type& refHead, K const& key, Compare cmp ) const
+ bool find_at( head_type& refHead, K const& key, Compare cmp )
{
return base_class::find_at( refHead, key, cmp, [](node_type&, K const&) {} );
}
template <typename K, typename Compare, typename Func>
- bool find_at( head_type& refHead, K& key, Compare cmp, Func f ) const
+ bool find_at( head_type& refHead, K& key, Compare cmp, Func f )
{
return base_class::find_at( refHead, key, cmp, [&f](node_type& node, K const&){ f( node.m_Data ); });
}
template <typename K, typename Compare>
- value_type * get_at( head_type& refHead, K const& val, Compare cmp ) const
+ raw_ptr get_at( head_type& refHead, K const& val, Compare cmp )
{
- node_type * pNode = base_class::get_at( refHead, val, cmp );
- return pNode ? &pNode->m_Data : nullptr;
+ return raw_ptr( base_class::get_at( refHead, val, cmp ));
}
//@endcond
}} // namespace cds::container
-#endif // #ifndef __CDS_CONTAINER_MICHAEL_KVLIST_RCU_H
+#endif // #ifndef CDSLIB_CONTAINER_MICHAEL_KVLIST_RCU_H