X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=cds%2Fcontainer%2Fskip_list_map_rcu.h;h=201bf158e06b5c9059a5e66b434fc7e1fb1c8421;hb=df4d0c52b3eff17a49505093870a37ea8c9d565d;hp=53bcf34447a23ad406bdb73396b3d4939b92b5b4;hpb=3caf0699346f9cb714809664697aa29efc7eb429;p=libcds.git
diff --git a/cds/container/skip_list_map_rcu.h b/cds/container/skip_list_map_rcu.h
index 53bcf344..201bf158 100644
--- a/cds/container/skip_list_map_rcu.h
+++ b/cds/container/skip_list_map_rcu.h
@@ -1,4 +1,32 @@
-//$$CDS-header$$
+/*
+ This file is a part of libcds - Concurrent Data Structures library
+
+ (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017
+
+ 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
@@ -140,17 +168,37 @@ namespace cds { namespace container {
/// 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:
@@ -164,7 +212,17 @@ namespace cds { namespace container {
{}
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
@@ -173,7 +231,7 @@ namespace cds { namespace container {
/// 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
@@ -184,13 +242,13 @@ namespace cds { namespace container {
/// 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.
@@ -201,8 +259,9 @@ namespace cds { namespace container {
/// 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
@@ -302,45 +361,53 @@ namespace cds { namespace container {
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 std::pair 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 std::pair 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
- std::pair ensure( K const& key, Func func )
+ std::pair update( K const& key, Func func, bool bInsert = true )
{
scoped_node_ptr pNode( node_allocator().New( random_level(), key ));
- std::pair res = base_class::ensure( *pNode,
- [&func](bool bNew, node_type& item, node_type const& ){ func( bNew, item.m_Value ); }
+ std::pair 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
+ CDS_DEPRECATED("ensure() is deprecated, use update()")
+ std::pair 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
@@ -514,38 +581,52 @@ namespace cds { namespace container {
[&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
+ bool contains( K const& key )
+ {
+ return base_class::contains( key );
+ }
+ //@cond
+ template
+ 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 contains( key ) 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
- bool find_with( K const& key, Less pred )
+ bool contains( 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 >() );
+ return base_class::contains( key, cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor >());
+ }
+ //@cond
+ template
+ CDS_DEPRECATED("deprecated, use contains()")
+ bool find_with( K const& key, Less pred )
+ {
+ 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.
@@ -556,26 +637,25 @@ namespace cds { namespace container {
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
- 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
@@ -588,10 +668,10 @@ namespace cds { namespace container {
\p pred must imply the same element order as the comparator used for building the map.
*/
template
- value_type * get_with( K const& key, Less pred )
+ raw_ptr get_with( K const& key, Less pred )
{
CDS_UNUSED( pred );
- return to_value_ptr( base_class::get_with( key, cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor >() ));
+ return raw_ptr( base_class::get_with( key, cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor >()));
}
/// Clears the map (not atomic)
@@ -620,14 +700,6 @@ namespace cds { namespace container {
{
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