{
static internal_node const& to_internal_node( tree_node const& n )
{
- assert( n.is_internal() );
+ assert( n.is_internal());
return static_cast<internal_node const&>( n );
}
static leaf_node const& to_leaf_node( tree_node const& n )
{
- assert( n.is_leaf() );
+ assert( n.is_leaf());
return static_cast<leaf_node const&>( n );
}
};
void retire_node( tree_node * pNode ) const
{
- if ( pNode->is_leaf() ) {
+ if ( pNode->is_leaf()) {
assert( static_cast<leaf_node *>( pNode ) != &m_LeafInf1 );
assert( static_cast<leaf_node *>( pNode ) != &m_LeafInf2 );
back_off bkoff;
for ( ;; ) {
- if ( search( res, val, node_compare() )) {
- if ( pNewInternal.get() )
+ if ( search( res, val, node_compare())) {
+ if ( pNewInternal.get())
m_Stat.onInternalNodeDeleted() ; // unique_internal_node_ptr deletes internal node
m_Stat.onInsertFailed();
return false;
if ( res.updGrandParent.bits() == update_desc::Clean && res.updParent.bits() == update_desc::Clean ) {
- if ( !pNewInternal.get() )
- pNewInternal.reset( alloc_internal_node() );
+ if ( !pNewInternal.get())
+ pNewInternal.reset( alloc_internal_node());
if ( try_insert( val, pNewInternal.get(), res )) {
f( val );
back_off bkoff;
for ( ;; ) {
- if ( search( res, val, node_compare() )) {
+ if ( search( res, val, node_compare())) {
func( false, *node_traits::to_value_ptr( res.pLeaf ), val );
- if ( pNewInternal.get() )
+ if ( pNewInternal.get())
m_Stat.onInternalNodeDeleted() ; // unique_internal_node_ptr deletes internal node
m_Stat.onUpdateExist();
return std::make_pair( true, false );
if ( !bAllowInsert )
return std::make_pair( false, false );
- if ( !pNewInternal.get() )
- pNewInternal.reset( alloc_internal_node() );
+ if ( !pNewInternal.get())
+ pNewInternal.reset( alloc_internal_node());
if ( try_insert( val, pNewInternal.get(), res )) {
func( true, val, val );
bool contains( Q const& key ) const
{
search_result res;
- if ( search( res, key, node_compare() )) {
+ if ( search( res, key, node_compare())) {
m_Stat.onFindSuccess();
return true;
}
> compare_functor;
search_result res;
- if ( search( res, key, compare_functor() )) {
+ if ( search( res, key, compare_functor())) {
m_Stat.onFindSuccess();
return true;
}
this sequence
\code
tree.clear();
- assert( tree.empty() );
+ assert( tree.empty());
\endcode
the assertion could be raised.
tree_node * pLeaf = const_cast<internal_node *>( &m_Root );
// Get leftmost leaf
- while ( pLeaf->is_internal() ) {
+ while ( pLeaf->is_internal()) {
pGrandParent = pParent;
pParent = static_cast<internal_node *>( pLeaf );
pLeaf = pParent->m_pLeft.load( memory_model::memory_order_relaxed );
// Remove leftmost leaf and its parent node
assert( pGrandParent );
assert( pParent );
- assert( pLeaf->is_leaf() );
+ assert( pLeaf->is_leaf());
pGrandParent->m_pLeft.store( pParent->m_pRight.load( memory_model::memory_order_relaxed ), memory_model::memory_order_relaxed );
- free_leaf_node( node_traits::to_value_ptr( static_cast<leaf_node *>( pLeaf ) ) );
+ free_leaf_node( node_traits::to_value_ptr( static_cast<leaf_node *>( pLeaf )) );
free_internal_node( pParent );
}
}
&& node_compare()( *pLeft, *pRight ) < 0 )
{
bool bRet = true;
- if ( pLeft->is_internal() )
- bRet = check_consistency( static_cast<internal_node *>( pLeft ) );
+ if ( pLeft->is_internal())
+ bRet = check_consistency( static_cast<internal_node *>( pLeft ));
assert( bRet );
- if ( bRet && pRight->is_internal() )
+ if ( bRet && pRight->is_internal())
bRet = bRet && check_consistency( static_cast<internal_node *>( pRight ));
assert( bRet );
updParent = nullptr;
bRightLeaf = false;
tree_node * pLeaf = const_cast<internal_node *>( &m_Root );
- while ( pLeaf->is_internal() ) {
+ while ( pLeaf->is_internal()) {
res.guards.copy( search_result::Guard_GrandParent, search_result::Guard_Parent );
pGrandParent = pParent;
res.guards.copy( search_result::Guard_Parent, search_result::Guard_Leaf );
updParent = search_protect_update( res, pParent->m_pUpdate );
- switch ( updParent.bits() ) {
+ switch ( updParent.bits()) {
case update_desc::DFlag:
case update_desc::Mark:
m_Stat.onSearchRetry();
}
}
- assert( pLeaf->is_leaf() );
- nCmp = cmp( key, *static_cast<leaf_node *>(pLeaf) );
+ assert( pLeaf->is_leaf());
+ nCmp = cmp( key, *static_cast<leaf_node *>(pLeaf));
res.pGrandParent = pGrandParent;
res.pParent = pParent;
pGrandParent = nullptr;
updParent = nullptr;
tree_node * pLeaf = const_cast<internal_node *>( &m_Root );
- while ( pLeaf->is_internal() ) {
+ while ( pLeaf->is_internal()) {
res.guards.copy( search_result::Guard_GrandParent, search_result::Guard_Parent );
pGrandParent = pParent;
res.guards.copy( search_result::Guard_Parent, search_result::Guard_Leaf );
updParent = search_protect_update( res, pParent->m_pUpdate );
- switch ( updParent.bits() ) {
+ switch ( updParent.bits()) {
case update_desc::DFlag:
case update_desc::Mark:
m_Stat.onSearchRetry();
res.pGrandParent = pGrandParent;
res.pParent = pParent;
- assert( pLeaf->is_leaf() );
+ assert( pLeaf->is_leaf());
res.pLeaf = static_cast<leaf_node *>( pLeaf );
res.updParent = updParent;
res.updGrandParent = updGrandParent;
updParent = nullptr;
bRightLeaf = false;
tree_node * pLeaf = const_cast<internal_node *>( &m_Root );
- while ( pLeaf->is_internal() ) {
+ while ( pLeaf->is_internal()) {
res.guards.copy( search_result::Guard_GrandParent, search_result::Guard_Parent );
pGrandParent = pParent;
res.guards.copy( search_result::Guard_Parent, search_result::Guard_Leaf );
updParent = search_protect_update( res, pParent->m_pUpdate );
- switch ( updParent.bits() ) {
+ switch ( updParent.bits()) {
case update_desc::DFlag:
case update_desc::Mark:
m_Stat.onSearchRetry();
res.pGrandParent = pGrandParent;
res.pParent = pParent;
- assert( pLeaf->is_leaf() );
+ assert( pLeaf->is_leaf());
res.pLeaf = static_cast<leaf_node *>( pLeaf );
res.updParent = updParent;
res.updGrandParent = updGrandParent;
void help( update_ptr pUpdate )
{
// pUpdate must be guarded!
- switch ( pUpdate.bits() ) {
+ switch ( pUpdate.bits()) {
case update_desc::IFlag:
- help_insert( pUpdate.ptr() );
+ help_insert( pUpdate.ptr());
m_Stat.onHelpInsert();
break;
case update_desc::DFlag:
- help_delete( pUpdate.ptr() );
+ help_delete( pUpdate.ptr());
m_Stat.onHelpDelete();
break;
case update_desc::Mark:
//m_Stat.onHelpMark();
- //help_marked( pUpdate.ptr() );
+ //help_marked( pUpdate.ptr());
break;
}
}
static tree_node * protect_sibling( typename gc::Guard& guard, atomics::atomic<tree_node *>& sibling )
{
tree_node * pSibling = guard.protect( sibling, [](tree_node * p) -> internal_node* { return static_cast<internal_node *>(p); } );
- if ( pSibling->is_leaf() )
+ if ( pSibling->is_leaf())
guard.assign( node_traits::to_value_ptr( static_cast<leaf_node *>( pSibling )));
return pSibling;
}
bool try_insert( value_type& val, internal_node * pNewInternal, search_result& res )
{
assert( res.updParent.bits() == update_desc::Clean );
- assert( res.pLeaf->is_leaf() );
+ assert( res.pLeaf->is_leaf());
// check search result
if ( res.pParent->get_child( res.bRightLeaf, memory_model::memory_order_acquire ) == res.pLeaf ) {
int nCmp = node_compare()(val, *res.pLeaf);
if ( nCmp < 0 ) {
if ( res.pGrandParent ) {
- assert( !res.pLeaf->infinite_key() );
+ assert( !res.pLeaf->infinite_key());
pNewInternal->infinite_key( 0 );
key_extractor()(pNewInternal->m_Key, *node_traits::to_value_ptr( res.pLeaf ));
}
pNewInternal->m_pRight.store( static_cast<tree_node *>(res.pLeaf), memory_model::memory_order_release );
}
else {
- assert( !res.pLeaf->is_internal() );
+ assert( !res.pLeaf->is_internal());
pNewInternal->infinite_key( 0 );
key_extractor()(pNewInternal->m_Key, val);
pNewInternal->m_pLeft.store( static_cast<tree_node *>(res.pLeaf), memory_model::memory_order_relaxed );
pNewInternal->m_pRight.store( static_cast<tree_node *>(pNewLeaf), memory_model::memory_order_release );
- assert( !res.pLeaf->infinite_key() );
+ assert( !res.pLeaf->infinite_key());
}
typename gc::Guard guard;
pOp->iInfo.pLeaf = res.pLeaf;
pOp->iInfo.bRightLeaf = res.bRightLeaf;
- update_ptr updCur( res.updParent.ptr() );
+ update_ptr updCur( res.updParent.ptr());
if ( res.pParent->m_pUpdate.compare_exchange_strong( updCur, update_ptr( pOp, update_desc::IFlag ),
- memory_model::memory_order_acquire, atomics::memory_order_relaxed ) ) {
+ memory_model::memory_order_acquire, atomics::memory_order_relaxed )) {
// do insert
help_insert( pOp );
retire_update_desc( pOp );
back_off bkoff;
for ( ;; ) {
- if ( !search( res, val, cmp ) || !eq( val, *res.pLeaf ) ) {
+ if ( !search( res, val, cmp ) || !eq( val, *res.pLeaf )) {
if ( pOp )
retire_update_desc( pOp );
m_Stat.onEraseFailed();
if ( res.updGrandParent.bits() == update_desc::Clean && res.updParent.bits() == update_desc::Clean ) {
if ( !pOp )
pOp = alloc_update_desc();
- if ( check_delete_precondition( res ) ) {
+ if ( check_delete_precondition( res )) {
typename gc::Guard guard;
guard.assign( pOp );
pOp->dInfo.bRightParent = res.bRightParent;
pOp->dInfo.bRightLeaf = res.bRightLeaf;
- update_ptr updGP( res.updGrandParent.ptr() );
+ update_ptr updGP( res.updGrandParent.ptr());
if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
- memory_model::memory_order_acquire, atomics::memory_order_relaxed ) ) {
- if ( help_delete( pOp ) ) {
+ memory_model::memory_order_acquire, atomics::memory_order_relaxed )) {
+ if ( help_delete( pOp )) {
// res.pLeaf is not deleted yet since it is guarded
- f( *node_traits::to_value_ptr( res.pLeaf ) );
+ f( *node_traits::to_value_ptr( res.pLeaf ));
break;
}
pOp = nullptr;
if ( res.updGrandParent.bits() == update_desc::Clean && res.updParent.bits() == update_desc::Clean ) {
if ( !pOp )
pOp = alloc_update_desc();
- if ( check_delete_precondition( res ) ) {
+ if ( check_delete_precondition( res )) {
typename gc::Guard guard;
guard.assign( pOp );
pOp->dInfo.bRightParent = res.bRightParent;
pOp->dInfo.bRightLeaf = res.bRightLeaf;
- update_ptr updGP( res.updGrandParent.ptr() );
+ update_ptr updGP( res.updGrandParent.ptr());
if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
- memory_model::memory_order_acquire, atomics::memory_order_relaxed ) ) {
+ memory_model::memory_order_acquire, atomics::memory_order_relaxed )) {
if ( help_delete( pOp ))
break;
pOp = nullptr;
if ( res.updGrandParent.bits() == update_desc::Clean && res.updParent.bits() == update_desc::Clean ) {
if ( !pOp )
pOp = alloc_update_desc();
- if ( check_delete_precondition( res ) ) {
+ if ( check_delete_precondition( res )) {
typename gc::Guard guard;
guard.assign( pOp );
pOp->dInfo.bRightParent = res.bRightParent;
pOp->dInfo.bRightLeaf = res.bRightLeaf;
- update_ptr updGP( res.updGrandParent.ptr() );
+ update_ptr updGP( res.updGrandParent.ptr());
if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
- memory_model::memory_order_acquire, atomics::memory_order_relaxed ) )
+ memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
{
- if ( help_delete( pOp ) )
+ if ( help_delete( pOp ))
break;
pOp = nullptr;
}
if ( res.updGrandParent.bits() == update_desc::Clean && res.updParent.bits() == update_desc::Clean ) {
if ( !pOp )
pOp = alloc_update_desc();
- if ( check_delete_precondition( res ) ) {
+ if ( check_delete_precondition( res )) {
typename gc::Guard guard;
guard.assign( pOp );
pOp->dInfo.bRightParent = res.bRightParent;
pOp->dInfo.bRightLeaf = res.bRightLeaf;
- update_ptr updGP( res.updGrandParent.ptr() );
+ update_ptr updGP( res.updGrandParent.ptr());
if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
{
bool find_( Q& val, Func f ) const
{
search_result res;
- if ( search( res, val, node_compare() )) {
+ if ( search( res, val, node_compare())) {
assert( res.pLeaf );
f( *node_traits::to_value_ptr( res.pLeaf ), val );
> compare_functor;
search_result res;
- if ( search( res, val, compare_functor() )) {
+ if ( search( res, val, compare_functor())) {
assert( res.pLeaf );
f( *node_traits::to_value_ptr( res.pLeaf ), val );
guarded_ptr get_( Q const& val ) const
{
search_result res;
- if ( search( res, val, node_compare() ) ) {
+ if ( search( res, val, node_compare()) ) {
assert( res.pLeaf );
m_Stat.onFindSuccess();
return guarded_ptr( res.guards.release( search_result::Guard_Leaf ));
> compare_functor;
search_result res;
- if ( search( res, val, compare_functor() ) ) {
+ if ( search( res, val, compare_functor()) ) {
assert( res.pLeaf );
m_Stat.onFindSuccess();
return guarded_ptr( res.guards.release( search_result::Guard_Leaf ));