-//$$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>
/// pointer to extracted node
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
unsigned int random_level()
{
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
/// 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.
/// 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
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 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>
exempt_ptr extract_with( K const& key, Less pred )
{
+ 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,
+ 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.
/// Extracts an item with maximal key from the map
/**
- The function searches an item with maximal key, unlinks it from the set,
+ 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.
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