- {
- assert( pLeft != nullptr );
- node_scoped_lock l( m_Monitor, *pLeft );
- if ( pNode->m_pLeft.load( memory_model::memory_order_relaxed ) != pLeft )
- return pNode; // retry for pNode
-
- int hL = height( pLeft, memory_model::memory_order_acquire );
- if ( hL - hR <= 1 )
- return pNode; // retry
-
- node_type * pLRight = child( pLeft, right_child, memory_model::memory_order_relaxed );
- int hLR = height_null( pLRight, memory_model::memory_order_acquire );
- node_type * pLLeft = child( pLeft, left_child, memory_model::memory_order_relaxed );
- int hLL = height_null( pLLeft, memory_model::memory_order_acquire );
-
- if ( hLL > hLR ) {
- // rotate right
- return rotate_right_locked( pParent, pNode, pLeft, hR, hLL, pLRight, hLR );
- }
- else {
- if ( pLRight ) {
- node_scoped_lock lr( m_Monitor, *pLRight );
- if ( pLeft->m_pRight.load( memory_model::memory_order_acquire ) != pLRight )
- return pNode; // retry
-
- hLR = height( pLRight, memory_model::memory_order_acquire );
- if ( hLL > hLR )
- return rotate_right_locked( pParent, pNode, pLeft, hR, hLL, pLRight, hLR );
-
- int hLRL = height_null( child( pLRight, left_child, memory_model::memory_order_relaxed ), memory_model::memory_order_acquire);
- int balance = hLL - hLRL;
- if ( balance >= -1 && balance <= 1 && !((hLL == 0 || hLRL == 0) && !pLeft->is_valued(memory_model::memory_order_relaxed))) {
- // nParent.child.left won't be damaged after a double rotation
- return rotate_right_over_left_locked( pParent, pNode, pLeft, hR, hLL, pLRight, hLRL );
- }
- }
- else
+ assert( pLeft != nullptr );
+ node_scoped_lock l( m_Monitor, *pLeft );
+ if ( pNode->m_pLeft.load( memory_model::memory_order_relaxed ) != pLeft )
+ return pNode; // retry for pNode
+
+ assert( check_node_ordering( pNode, pLeft ) > 0 );
+
+ int hL = height( pLeft, memory_model::memory_order_acquire );
+ if ( hL - hR <= 1 )
+ return pNode; // retry
+
+ node_type * pLRight = child( pLeft, right_child, memory_model::memory_order_relaxed );
+ int hLR = height_null( pLRight, memory_model::memory_order_acquire );
+ node_type * pLLeft = child( pLeft, left_child, memory_model::memory_order_relaxed );
+ int hLL = height_null( pLLeft, memory_model::memory_order_acquire );
+
+ if ( pLRight ) {
+ {
+ node_scoped_lock lr( m_Monitor, *pLRight );
+ if ( pLeft->m_pRight.load( memory_model::memory_order_acquire ) != pLRight )