-//$$CDS-header$$
+/*
+ This file is a part of libcds - Concurrent Data Structures library
-#ifndef __CDS_CONTAINER_SKIP_LIST_MAP_RCU_H
-#define __CDS_CONTAINER_SKIP_LIST_MAP_RCU_H
+ (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>
- \p RCU - one of \ref cds_urcu_gc "RCU type".
- \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 - type traits. See skip_list::type_traits for explanation.
-
- It is possible to declare option-based list with cds::container::skip_list::make_traits metafunction istead of \p Traits template
- argument.
- Template argument list \p Options of cds::container::skip_list::make_traits metafunction are:
- - opt::compare - key compare functor. No default functor is provided.
- If the option is not specified, the opt::less is used.
- - opt::less - specifies binary predicate used for key comparison. Default is \p std::less<K>.
- - opt::item_counter - the type of item counting feature. Default is \ref atomicity::empty_item_counter that is no item counting.
- - opt::memory_model - C++ memory ordering model. Can be opt::v::relaxed_ordering (relaxed memory model, the default)
- or opt::v::sequential_consistent (sequentially consisnent memory model).
- - skip_list::random_level_generator - random level generator. Can be skip_list::xorshift, skip_list::turbo_pascal or
- user-provided one. See skip_list::random_level_generator option description for explanation.
- Default is \p %skip_list::turbo_pascal.
- - opt::allocator - allocator for skip-list node. Default is \ref CDS_DEFAULT_ALLOCATOR.
- - opt::back_off - back-off strategy used. If the option is not specified, the cds::backoff::Default is used.
- - opt::stat - internal statistics. Available types: skip_list::stat, skip_list::empty_stat (the default)
- - opt::rcu_check_deadlock - a deadlock checking policy. Default is opt::v::rcu_throw_deadlock
+ - \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
+ instead of \p Traits template argument.
Like STL map class, \p %SkipListMap stores its key-value pair as <tt>std:pair< K const, T></tt>.
typename Key,
typename T,
#ifdef CDS_DOXYGEN_INVOKED
- typename Traits = skip_list::type_traits
+ typename Traits = skip_list::traits
#else
typename Traits
#endif
typedef typename maker::type base_class;
//@endcond
public:
- typedef typename base_class::gc gc ; ///< Garbage collector used
- typedef Key key_type ; ///< Key type
- typedef T mapped_type ; ///< Mapped type
+ typedef cds::urcu::gc< RCU > gc; ///< Garbage collector used
+ typedef Key key_type; ///< Key type
+ typedef T mapped_type; ///< Mapped type
# ifdef CDS_DOXYGEN_INVOKED
- typedef std::pair< K const, T> value_type ; ///< Value type stored in the map
+ typedef std::pair< K const, T> value_type; ///< Value type stored in the map
# else
typedef typename maker::value_type value_type;
# endif
- typedef Traits options ; ///< Options specified
+ typedef Traits traits; ///< Map traits
- typedef typename base_class::back_off back_off ; ///< Back-off strategy used
- typedef typename options::allocator allocator_type ; ///< Allocator type used for allocate/deallocate the skip-list nodes
- typedef typename base_class::item_counter item_counter ; ///< Item counting policy used
- typedef typename maker::key_comparator key_comparator ; ///< key comparison functor
- typedef typename base_class::memory_model memory_model ; ///< Memory ordering. See cds::opt::memory_model option
- typedef typename options::random_level_generator random_level_generator ; ///< random level generator
- typedef typename options::stat stat ; ///< internal statistics type
+ typedef typename base_class::back_off back_off; ///< Back-off strategy used
+ typedef typename traits::allocator allocator_type; ///< Allocator type used for allocate/deallocate the skip-list nodes
+ typedef typename base_class::item_counter item_counter; ///< Item counting policy used
+ typedef typename maker::key_comparator key_comparator; ///< key comparison functor
+ typedef typename base_class::memory_model memory_model; ///< Memory ordering. See cds::opt::memory_model option
+ typedef typename traits::random_level_generator random_level_generator; ///< random level generator
+ typedef typename traits::stat stat; ///< internal statistics type
protected:
//@cond
public:
typedef typename base_class::rcu_lock rcu_lock; ///< RCU scoped lock
/// Group of \p extract_xxx functions do not require external locking
- static CDS_CONSTEXPR_CONST bool c_bExtractLockExternal = base_class::c_bExtractLockExternal;
+ 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
/// Returns a forward iterator addressing the first element in a map
iterator begin()
{
- return iterator( base_class::begin() );
+ return iterator( base_class::begin());
}
/// Returns a forward const iterator addressing the first element in a map
- //@{
const_iterator begin() const
{
return cbegin();
}
- const_iterator cbegin()
+ /// Returns a forward const iterator addressing the first element in a map
+ const_iterator cbegin() const
{
- return const_iterator( base_class::cbegin() );
+ return const_iterator( base_class::cbegin());
}
- //@}
/// Returns a forward iterator that addresses the location succeeding the last element in a map.
iterator end()
{
- return iterator( base_class::end() );
+ return iterator( base_class::end());
}
/// Returns a forward const iterator that addresses the location succeeding the last element in a map.
- //@{
const_iterator end() const
{
return cend();
}
- const_iterator cend()
+ /// Returns a forward const iterator that addresses the location succeeding the last element in a map.
+ const_iterator cend() const
{
- return const_iterator( base_class::cend() );
+ return const_iterator( base_class::cend());
}
- //@}
+ //@}
public:
/// Inserts new node with key and default value
The function creates a node with \p key and default value, and then inserts the node created into the map.
Preconditions:
- - The \ref key_type should be constructible from a value of type \p K.
- In trivial case, \p K is equal to \ref key_type.
- - The \ref mapped_type should be default-constructible.
+ - The \p key_type should be constructible from a value of type \p K.
+ In trivial case, \p K is equal to \p key_type.
+ - The \p mapped_type should be default-constructible.
RCU \p synchronize method can be called. RCU should not be locked.
template <typename K>
bool insert( K const& key )
{
- return insert_key( key, [](value_type&){} );
+ return insert_with( key, [](value_type&){} );
}
/// Inserts new node
and then inserts the node created into the map.
Preconditions:
- - The \ref key_type should be constructible from \p key of type \p K.
- - The \ref value_type should be constructible from \p val of type \p V.
+ - The \p key_type should be constructible from \p key of type \p K.
+ - The \p value_type should be constructible from \p val of type \p V.
RCU \p synchronize method can be called. RCU should not be locked.
- <tt>item.first</tt> is a const reference to item's key that cannot be changed.
- <tt>item.second</tt> is a reference to item's value that may be changed.
- The user-defined functor can be passed by reference using \p std::ref
- and it is called only if inserting is successful.
-
- The key_type should be constructible from value of type \p K.
-
- The function allows to split creating of new item into two part:
+ The function allows to split creating of new item into three part:
- create item from \p key;
- insert new item into the map;
- if inserting is successful, initialize the value of item by calling \p func functor
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;
}
- /// For key \p key inserts data of type \ref value_type constructed with <tt>std::forward<Args>(args)...</tt>
+ /// For key \p key inserts data of type \p value_type created in-place from \p args
/**
Returns \p true if inserting successful, \p false otherwise.
- RCU \p synchronize method can be called. RCU should not be locked.
+ RCU \p synchronize() method can be called. RCU should not be locked.
*/
template <typename K, typename... Args>
bool emplace( K&& key, Args&&... args )
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.
- The functor \p Func may be a function with signature:
- \code
- void func( bool bNew, value_type& item );
- \endcode
- or a functor:
+ 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 the \p item.second that is \ref value_type.
+ The functor may change any fields of \p item.second.
- You may pass \p func argument by reference using \p std::ref
+ RCU \p synchronize() method can be called. RCU should not be locked.
- RCU \p synchronize method can be called. RCU should not be locked.
+ 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.
- 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.
+ @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 >());
}
void operator()(value_type& item) { ... }
};
\endcode
- The functor may be passed by reference using <tt>boost:ref</tt>
RCU \p synchronize method can be called. RCU should not be locked.
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.
+ 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
\endcode
where \p item is the item found.
- You can pass \p f argument by reference using \p std::ref.
-
The functor may change \p item.second.
The function applies RCU lock internally.
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
+ /// Clears the map (not atomic)
void clear()
{
base_class::clear();
{
return base_class::statistics();
}
-
- /// Clears internal list of ready-to-delete items passing them to RCU reclamation cycle
- /**
- See \ref cds_intrusive_SkipListSet_rcu_force_dispose "intrusive SkipListSet" for explanation
- */
- 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