-//$$CDS-header$$
+/*
+ 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_IMPL_BRONSON_AVLTREE_MAP_RCU_H
#define CDSLIB_CONTAINER_IMPL_BRONSON_AVLTREE_MAP_RCU_H
namespace cds { namespace container {
- /// Bronson et al AVL-tree (RCU specialization for storing pointer to values)
+ /// Bronson et al AVL-tree (RCU specialization for pointers)
/** @ingroup cds_nonintrusive_map
@ingroup cds_nonintrusive_tree
@headerfile cds/container/bronson_avltree_map_rcu.h
static node_type * child( node_type * pNode, int nDir, atomics::memory_order order )
{
- return pNode->child( nDir ).load( order );
+ return pNode->child( nDir, order );
}
static node_type * parent( node_type * pNode, atomics::memory_order order )
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 successfull,
+ Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successful,
\p second is \p true if new node has been added or \p false if the node with \p key
already exists.
*/
return std::make_pair( result != 0, (result & update_flags::result_inserted) != 0 );
}
- //@cond
- template <typename K>
- std::pair<bool, bool> ensure( K const& key, mapped_type pVal )
- {
- return update( key, pVal, true );
- }
-
//@endcond
/// Delete \p key from the map
The functor \p Func interface:
\code
- struct extractor {
+ struct functor {
void operator()( key_type const& key, std::remove_pointer<mapped_type>::type& val) { ... }
};
\endcode
return exempt_ptr(do_extract_min( []( key_type const& ) {}));
}
- /// Extracts minimal key key and corresponding value
+ /// Extracts minimal key and corresponding value
/**
Returns \p exempt_ptr to the leftmost item.
If the tree is empty, returns empty \p exempt_ptr.
};
\endcode
If the tree is empty, \p f is not called.
- Otherwise, is it called with minimal key, the pointer to corresponding value is returned
+ Otherwise, it is called with minimal key, the pointer to corresponding value is returned
as \p exempt_ptr.
@note Due the concurrent nature of the map, the function extracts <i>nearly</i> minimum key.
return exempt_ptr(do_extract_min( [&f]( key_type const& key ) { f(key); }));
}
- /// Extracts minimal key key and corresponding value
+ /// Extracts minimal key and corresponding value
/**
This function is a shortcut for the following call:
\code
key_type key;
exempt_ptr xp = theTree.extract_min( [&key]( key_type const& k ) { key = k; } );
- \endode
+ \endcode
\p key_type should be copy-assignable. The copy of minimal key
is returned in \p min_key argument.
*/
};
\endcode
If the tree is empty, \p f is not called.
- Otherwise, is it called with maximal key, the pointer to corresponding value is returned
+ Otherwise, it is called with maximal key, the pointer to corresponding value is returned
as \p exempt_ptr.
@note Due the concurrent nature of the map, the function extracts <i>nearly</i> maximal key.
\code
key_type key;
exempt_ptr xp = theTree.extract_max( [&key]( key_type const& k ) { key = k; } );
- \endode
+ \endcode
\p key_type should be copy-assignable. The copy of maximal key
is returned in \p max_key argument.
*/
The interface of \p Func functor is:
\code
struct functor {
- void operator()( key_type const& key, mapped_type& item );
+ void operator()( key_type const& key, std::remove_pointer< mapped_type )::type& item );
};
\endcode
where \p item is the item found.
);
}
- /// Find the key \p key
+ /// 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 find( K const& key )
+ bool contains( K const& key )
{
return do_find( key, key_comparator(), []( node_type * ) -> bool { return true; });
}
- /// 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 \p 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 find_with( K const& key, Less pred )
+ bool contains( K const& key, Less pred )
{
CDS_UNUSED( pred );
return do_find( key, cds::opt::details::make_comparator_from_less<Less>(), []( node_type * ) -> bool { return true; } );
}
if ( bInserted ) {
+ ++m_ItemCounter;
m_stat.onInsertSuccess();
return update_flags::result_inserted;
}
if ( !pNode->is_valued( memory_model::memory_order_acquire ) )
return update_flags::failed;
- if ( child( pNode, left_child, memory_model::memory_order_acquire ) == nullptr
- || child( pNode, right_child, memory_model::memory_order_acquire ) == nullptr )
+ if ( child( pNode, left_child, memory_model::memory_order_acquire ) == nullptr
+ || child( pNode, right_child, memory_model::memory_order_acquire ) == nullptr )
{
// pNode can be replaced with its child
}
}
- assert( child( pParent, left_child, memory_model::memory_order_relaxed ) == pNode
+ assert( child( pParent, left_child, memory_model::memory_order_relaxed ) == pNode
|| child( pParent, right_child, memory_model::memory_order_relaxed ) == pNode );
int h = height( pNode, memory_model::memory_order_acquire );
node_type * rebalance_to_right_locked( node_type * pParent, node_type * pNode, node_type * pLeft, int hR )
{
assert( parent( pNode, memory_model::memory_order_relaxed ) == pParent );
- assert( child( pParent, left_child, memory_model::memory_order_relaxed ) == pNode
+ assert( child( pParent, left_child, memory_model::memory_order_relaxed ) == pNode
|| child( pParent, right_child, memory_model::memory_order_relaxed ) == pNode );
// pParent and pNode is locked yet
return rotate_right_locked( pParent, pNode, pLeft, hR, hLL, pLRight, hLR );
}
else {
- assert( pLRight != nullptr );
- {
+ if ( pLRight ) {
node_scoped_lock lr( m_Monitor, *pLRight );
if ( pLeft->m_pRight.load( memory_model::memory_order_acquire ) != pLRight )
return pNode; // retry
return rotate_right_over_left_locked( pParent, pNode, pLeft, hR, hLL, pLRight, hLRL );
}
}
+ else
+ return pNode; // retry
// focus on pLeft, if necessary pNode will be balanced later
return rebalance_to_left_locked( pNode, pLeft, pLRight, hLL );
node_type * rebalance_to_left_locked( node_type * pParent, node_type * pNode, node_type * pRight, int hL )
{
assert( parent( pNode, memory_model::memory_order_relaxed ) == pParent );
- assert( child( pParent, left_child, memory_model::memory_order_relaxed ) == pNode
+ assert( child( pParent, left_child, memory_model::memory_order_relaxed ) == pNode
|| child( pParent, right_child, memory_model::memory_order_relaxed ) == pNode );
// pParent and pNode is locked yet
if ( hRR > hRL )
return rotate_left_locked( pParent, pNode, hL, pRight, pRLeft, hRL, hRR );
- {
- assert( pRLeft != nullptr );
+ if ( pRLeft ) {
node_scoped_lock lrl( m_Monitor, *pRLeft );
if ( pRight->m_pLeft.load( memory_model::memory_order_acquire ) != pRLeft )
return pNode; // retry
if ( balance >= -1 && balance <= 1 && !((hRR == 0 || hRLR == 0) && !pRight->is_valued( memory_model::memory_order_relaxed )))
return rotate_left_over_right_locked( pParent, pNode, hL, pRight, pRLeft, hRR, hRLR );
}
+ else
+ return pNode; // retry
return rebalance_to_right_locked( pNode, pRight, pRLeft, hRR );
}
}
projects / libcds.git / blobdiff