cds/container/impl/bronson_avltree_map_rcu.h

   1 //$$CDS-header$$
   2
   3 #ifndef CDSLIB_CONTAINER_IMPL_BRONSON_AVLTREE_MAP_RCU_H
   4 #define CDSLIB_CONTAINER_IMPL_BRONSON_AVLTREE_MAP_RCU_H
   5
   6 #include <type_traits> // is_base_of
   7 #include <cds/container/details/bronson_avltree_base.h>
   8 #include <cds/urcu/details/check_deadlock.h>
   9 #include <cds/urcu/exempt_ptr.h>
  10
  11 namespace cds { namespace container {
  12
  13     /// Bronson et al AVL-tree (RCU specialization for storing pointer to values)
  14     /** @ingroup cds_nonintrusive_map
  15         @ingroup cds_nonintrusive_tree
  16         @headerfile cds/container/bronson_avltree_map_rcu.h
  17         @anchor cds_container_BronsonAVLTreeMap_rcu_ptr
  18
  19         This is the specialization of \ref cds_container_BronsonAVLTreeMap_rcu "RCU-based Bronson et al AVL-tree"
  20         for "key -> value pointer" map. This specialization stores the pointer to user-allocated values instead of the copy
  21         of the value. When a tree node is removed, the algorithm does not free the value pointer directly, instead, it call
  22         the disposer functor provided by \p Traits template parameter.
  23
  24         <b>Template arguments</b>:
  25         - \p RCU - one of \ref cds_urcu_gc "RCU type"
  26         - \p Key - key type
  27         - \p T - value type to be stored in tree's nodes. Note, the specialization stores the pointer to user-allocated
  28             value, not the copy.
  29         - \p Traits - tree traits, default is \p bronson_avltree::traits
  30             It is possible to declare option-based tree with \p bronson_avltree::make_traits metafunction
  31             instead of \p Traits template argument.
  32
  33         @note Before including <tt><cds/container/bronson_avltree_map_rcu.h></tt> you should include appropriate RCU header file,
  34         see \ref cds_urcu_gc "RCU type" for list of existing RCU class and corresponding header files.
  35     */
  36     template <
  37         typename RCU,
  38         typename Key,
  39         typename T,
  40 #   ifdef CDS_DOXYGEN_INVOKED
  41         typename Traits = bronson_avltree::traits
  42 #else
  43         typename Traits
  44 #endif
  45     >
  46     class BronsonAVLTreeMap< cds::urcu::gc<RCU>, Key, T*, Traits >
  47     {
  48     public:
  49         typedef cds::urcu::gc<RCU>  gc;   ///< RCU Garbage collector
  50         typedef Key     key_type;    ///< type of a key stored in the map
  51         typedef T *     mapped_type; ///< type of value stored in the map
  52         typedef Traits  traits;      ///< Traits template parameter
  53
  54 #   ifdef CDS_DOXYGEN_INVOKED
  55         typedef implementation_defined key_comparator;    ///< key compare functor based on \p Traits::compare and \p Traits::less
  56 #   else
  57         typedef typename opt::details::make_comparator< key_type, traits >::type key_comparator;
  58 #endif
  59         typedef typename traits::item_counter           item_counter;       ///< Item counting policy
  60         typedef typename traits::memory_model           memory_model;       ///< Memory ordering, see \p cds::opt::memory_model option
  61         typedef typename traits::node_allocator         node_allocator_type; ///< allocator for maintaining internal nodes
  62         typedef typename traits::stat                   stat;               ///< internal statistics
  63         typedef typename traits::rcu_check_deadlock     rcu_check_deadlock; ///< Deadlock checking policy
  64         typedef typename traits::back_off               back_off;           ///< Back-off strategy
  65         typedef typename traits::disposer               disposer;           ///< Value disposer
  66         typedef typename traits::sync_monitor           sync_monitor;       ///< @ref cds_sync_monitor "Synchronization monitor" type for node-level locking
  67
  68         /// Enabled or disabled @ref bronson_avltree::relaxed_insert "relaxed insertion"
  69         static CDS_CONSTEXPR bool const c_bRelaxedInsert = traits::relaxed_insert;
  70
  71         /// Group of \p extract_xxx functions does not require external locking
  72         static CDS_CONSTEXPR const bool c_bExtractLockExternal = false;
  73
  74 #   ifdef CDS_DOXYGEN_INVOKED
  75         /// Returned pointer to \p mapped_type of extracted node
  76         typedef cds::urcu::exempt_ptr< gc, T, T, disposer, void > exempt_ptr;
  77 #   else
  78         typedef cds::urcu::exempt_ptr< gc,
  79             typename std::remove_pointer<mapped_type>::type,
  80             typename std::remove_pointer<mapped_type>::type,
  81             disposer,
  82             void
  83         > exempt_ptr;
  84 #   endif
  85
  86         typedef typename gc::scoped_lock    rcu_lock;  ///< RCU scoped lock
  87
  88     protected:
  89         //@cond
  90         typedef bronson_avltree::node< key_type, mapped_type, sync_monitor > node_type;
  91         typedef typename node_type::version_type version_type;
  92
  93         typedef cds::details::Allocator< node_type, node_allocator_type > cxx_allocator;
  94         typedef cds::urcu::details::check_deadlock_policy< gc, rcu_check_deadlock >   check_deadlock_policy;
  95
  96         enum class find_result
  97         {
  98             not_found,
  99             found,
 100             retry
 101         };
 102
 103         struct update_flags
 104         {
 105             enum {
 106                 allow_insert = 1,
 107                 allow_update = 2,
 108                 //allow_remove = 4,
 109
 110                 retry = 1024,
 111
 112                 failed = 0,
 113                 result_inserted = allow_insert,
 114                 result_updated = allow_update,
 115                 result_removed = 4
 116             };
 117         };
 118
 119         enum node_condition
 120         {
 121             nothing_required = -3,
 122             rebalance_required = -2,
 123             unlink_required = -1
 124         };
 125
 126         enum direction {
 127             left_child = -1,
 128             right_child = 1
 129         };
 130
 131         typedef typename sync_monitor::template scoped_lock<node_type> node_scoped_lock;
 132         //@endcond
 133
 134     protected:
 135         //@cond
 136         template <typename K>
 137         static node_type * alloc_node( K&& key, int nHeight, version_type version, node_type * pParent, node_type * pLeft, node_type * pRight )
 138         {
 139             return cxx_allocator().New( std::forward<K>( key ), nHeight, version, pParent, pLeft, pRight );
 140         }
 141
 142         static void free_node( node_type * pNode )
 143         {
 144             // Free node without disposer
 145             assert( !pNode->is_valued( memory_model::memory_order_relaxed ));
 146             assert( pNode->m_SyncMonitorInjection.check_free());
 147             cxx_allocator().Delete( pNode );
 148         }
 149
 150         static void free_value( mapped_type pVal )
 151         {
 152             disposer()(pVal);
 153         }
 154
 155         static node_type * child( node_type * pNode, int nDir, atomics::memory_order order )
 156         {
 157             return pNode->child( nDir, order );
 158         }
 159
 160         static node_type * parent( node_type * pNode, atomics::memory_order order )
 161         {
 162             return pNode->parent( order );
 163         }
 164
 165         // RCU safe disposer
 166         class rcu_disposer
 167         {
 168             node_type *     m_pRetiredList;     ///< head of retired node list
 169             mapped_type     m_pRetiredValue;    ///< value retired
 170
 171         public:
 172             rcu_disposer()
 173                 : m_pRetiredList( nullptr )
 174                 , m_pRetiredValue( nullptr )
 175             {}
 176
 177             ~rcu_disposer()
 178             {
 179                 clean();
 180             }
 181
 182             void dispose( node_type * pNode )
 183             {
 184                 assert( !pNode->is_valued( memory_model::memory_order_relaxed ));
 185                 pNode->m_pNextRemoved = m_pRetiredList;
 186                 m_pRetiredList = pNode;
 187             }
 188
 189             void dispose_value( mapped_type pVal )
 190             {
 191                 assert( m_pRetiredValue == nullptr );
 192                 m_pRetiredValue = pVal;
 193             }
 194
 195         private:
 196             struct internal_disposer
 197             {
 198                 void operator()( node_type * p ) const
 199                 {
 200                     free_node( p );
 201                 }
 202             };
 203
 204             void clean()
 205             {
 206                 assert( !gc::is_locked() );
 207
 208                 // TODO: use RCU::batch_retire
 209
 210                 // Dispose nodes
 211                 for ( node_type * p = m_pRetiredList; p; ) {
 212                     node_type * pNext = static_cast<node_type *>( p->m_pNextRemoved );
 213                     // Value already disposed
 214                     gc::template retire_ptr<internal_disposer>( p );
 215                     p = pNext;
 216                 }
 217
 218                 // Dispose value
 219                 if ( m_pRetiredValue  )
 220                     gc::template retire_ptr<disposer>( m_pRetiredValue );
 221             }
 222         };
 223
 224         //@endcond
 225
 226     protected:
 227         //@cond
 228         typename node_type::base_class m_Root;
 229         node_type *             m_pRoot;
 230         item_counter            m_ItemCounter;
 231         mutable sync_monitor    m_Monitor;
 232         mutable stat            m_stat;
 233         //@endcond
 234
 235     public:
 236         /// Creates empty map
 237         BronsonAVLTreeMap()
 238             : m_pRoot( static_cast<node_type *>( &m_Root ))
 239         {}
 240
 241         /// Destroys the map
 242         ~BronsonAVLTreeMap()
 243         {
 244             unsafe_clear();
 245         }
 246
 247         /// Inserts new node
 248         /**
 249             The \p key_type should be constructible from a value of type \p K.
 250
 251             RCU \p synchronize() can be called. RCU should not be locked.
 252
 253             Returns \p true if inserting successful, \p false otherwise.
 254         */
 255         template <typename K>
 256         bool insert( K const& key, mapped_type pVal )
 257         {
 258             return do_update(key, key_comparator(),
 259                 [pVal]( node_type * pNode ) -> mapped_type
 260                 {
 261                     assert( pNode->m_pValue.load( memory_model::memory_order_relaxed ) == nullptr );
 262                     CDS_UNUSED( pNode );
 263                     return pVal;
 264                 },
 265                 update_flags::allow_insert
 266             ) == update_flags::result_inserted;
 267         }
 268
 269         /// Updates the value for \p key
 270         /**
 271             The operation performs inserting or updating the value for \p key with lock-free manner.
 272             If \p bInsert is \p false, only updating of existing node is possible.
 273
 274             If \p key is not found and inserting is allowed (i.e. \p bInsert is \p true),
 275             then the new node created from \p key will be inserted into the map; note that in this case the \ref key_type should be
 276             constructible from type \p K.
 277             Otherwise, the value for \p key will be changed to \p pVal.
 278
 279             RCU \p synchronize() method can be called. RCU should not be locked.
 280
 281             Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successfull,
 282             \p second is \p true if new node has been added or \p false if the node with \p key
 283             already exists.
 284         */
 285         template <typename K>
 286         std::pair<bool, bool> update( K const& key, mapped_type pVal, bool bInsert = true )
 287         {
 288             int result = do_update( key, key_comparator(),
 289                 [pVal]( node_type * ) -> mapped_type
 290                 {
 291                     return pVal;
 292                 },
 293                 update_flags::allow_update | (bInsert ? update_flags::allow_insert : 0)
 294             );
 295             return std::make_pair( result != 0, (result & update_flags::result_inserted) != 0 );
 296         }
 297
 298         //@endcond
 299
 300         /// Delete \p key from the map
 301         /**
 302             RCU \p synchronize() method can be called. RCU should not be locked.
 303
 304             Return \p true if \p key is found and deleted, \p false otherwise
 305         */
 306         template <typename K>
 307         bool erase( K const& key )
 308         {
 309             return do_remove(
 310                 key,
 311                 key_comparator(),
 312                 []( key_type const&, mapped_type pVal, rcu_disposer& disp ) -> bool { disp.dispose_value( pVal ); return true; }
 313             );
 314         }
 315
 316         /// Deletes the item from the map using \p pred predicate for searching
 317         /**
 318             The function is an analog of \p erase(K const&)
 319             but \p pred is used for key comparing.
 320             \p Less functor has the interface like \p std::less.
 321             \p Less must imply the same element order as the comparator used for building the map.
 322         */
 323         template <typename K, typename Less>
 324         bool erase_with( K const& key, Less pred )
 325         {
 326             CDS_UNUSED( pred );
 327             return do_remove(
 328                 key,
 329                 cds::opt::details::make_comparator_from_less<Less>(),
 330                 []( key_type const&, mapped_type pVal, rcu_disposer& disp ) -> bool { disp.dispose_value( pVal ); return true;  }
 331             );
 332         }
 333
 334         /// Delete \p key from the map
 335         /**
 336             The function searches an item with key \p key, calls \p f functor
 337             and deletes the item. If \p key is not found, the functor is not called.
 338
 339             The functor \p Func interface:
 340             \code
 341             struct extractor {
 342                 void operator()( key_type const& key, std::remove_pointer<mapped_type>::type& val) { ... }
 343             };
 344             \endcode
 345
 346             RCU \p synchronize method can be called. RCU should not be locked.
 347
 348             Return \p true if key is found and deleted, \p false otherwise
 349         */
 350         template <typename K, typename Func>
 351         bool erase( K const& key, Func f )
 352         {
 353             return do_remove(
 354                 key,
 355                 key_comparator(),
 356                 [&f]( key_type const& key, mapped_type pVal, rcu_disposer& disp ) -> bool {
 357                     assert( pVal );
 358                     f( key, *pVal );
 359                     disp.dispose_value(pVal);
 360                     return true;
 361                 }
 362             );
 363         }
 364
 365         /// Deletes the item from the map using \p pred predicate for searching
 366         /**
 367             The function is an analog of \p erase(K const&, Func)
 368             but \p pred is used for key comparing.
 369             \p Less functor has the interface like \p std::less.
 370             \p Less must imply the same element order as the comparator used for building the map.
 371         */
 372         template <typename K, typename Less, typename Func>
 373         bool erase_with( K const& key, Less pred, Func f )
 374         {
 375             CDS_UNUSED( pred );
 376             return do_remove(
 377                 key,
 378                 cds::opt::details::make_comparator_from_less<Less>(),
 379                 [&f]( key_type const& key, mapped_type pVal, rcu_disposer& disp ) -> bool {
 380                     assert( pVal );
 381                     f( key, *pVal );
 382                     disp.dispose_value(pVal);
 383                     return true;
 384                 }
 385             );
 386         }
 387
 388         /// Extracts a value with minimal key from the map
 389         /**
 390             Returns \p exempt_ptr to the leftmost item.
 391             If the tree is empty, returns empty \p exempt_ptr.
 392
 393             Note that the function returns only the value for minimal key.
 394             To retrieve its key use \p extract_min( Func ) member function.
 395
 396             @note Due the concurrent nature of the map, the function extracts <i>nearly</i> minimum key.
 397             It means that the function gets leftmost leaf of the tree and tries to unlink it.
 398             During unlinking, a concurrent thread may insert an item with key less than leftmost item's key.
 399             So, the function returns the item with minimum key at the moment of tree traversing.
 400
 401             RCU \p synchronize method can be called. RCU should NOT be locked.
 402             The function does not free the item.
 403             The deallocator will be implicitly invoked when the returned object is destroyed or when
 404             its \p release() member function is called.
 405         */
 406         exempt_ptr extract_min()
 407         {
 408             return exempt_ptr(do_extract_min( []( key_type const& ) {}));
 409         }
 410
 411         /// Extracts minimal key key and corresponding value
 412         /**
 413             Returns \p exempt_ptr to the leftmost item.
 414             If the tree is empty, returns empty \p exempt_ptr.
 415
 416             \p Func functor is used to store minimal key.
 417             \p Func has the following signature:
 418             \code
 419             struct functor {
 420                 void operator()( key_type const& key );
 421             };
 422             \endcode
 423             If the tree is empty, \p f is not called.
 424             Otherwise, is it called with minimal key, the pointer to corresponding value is returned
 425             as \p exempt_ptr.
 426
 427             @note Due the concurrent nature of the map, the function extracts <i>nearly</i> minimum key.
 428             It means that the function gets leftmost leaf of the tree and tries to unlink it.
 429             During unlinking, a concurrent thread may insert an item with key less than leftmost item's key.
 430             So, the function returns the item with minimum key at the moment of tree traversing.
 431
 432             RCU \p synchronize method can be called. RCU should NOT be locked.
 433             The function does not free the item.
 434             The deallocator will be implicitly invoked when the returned object is destroyed or when
 435             its \p release() member function is called.
 436         */
 437         template <typename Func>
 438         exempt_ptr extract_min( Func f )
 439         {
 440             return exempt_ptr(do_extract_min( [&f]( key_type const& key ) { f(key); }));
 441         }
 442
 443         /// Extracts minimal key key and corresponding value
 444         /**
 445             This function is a shortcut for the following call:
 446             \code
 447             key_type key;
 448             exempt_ptr xp = theTree.extract_min( [&key]( key_type const& k ) { key = k; } );
 449             \endode
 450             \p key_type should be copy-assignable. The copy of minimal key
 451             is returned in \p min_key argument.
 452         */
 453         typename std::enable_if< std::is_copy_assignable<key_type>::value, exempt_ptr >::type
 454         extract_min_key( key_type& min_key )
 455         {
 456             return exempt_ptr(do_extract_min( [&min_key]( key_type const& key ) { min_key = key; }));
 457         }
 458
 459         /// Extracts a value with maximal key from the tree
 460         /**
 461             Returns \p exempt_ptr pointer to the rightmost item.
 462             If the set is empty, returns empty \p exempt_ptr.
 463
 464             Note that the function returns only the value for maximal key.
 465             To retrieve its key use \p extract_max( Func ) member function.
 466
 467             @note Due the concurrent nature of the map, the function extracts <i>nearly</i> maximal key.
 468             It means that the function gets rightmost leaf of the tree and tries to unlink it.
 469             During unlinking, a concurrent thread may insert an item with key great than leftmost item's key.
 470             So, the function returns the item with maximum key at the moment of tree traversing.
 471
 472             RCU \p synchronize method can be called. RCU should NOT be locked.
 473             The function does not free the item.
 474             The deallocator will be implicitly invoked when the returned object is destroyed or when
 475             its \p release() is called.
 476         */
 477         exempt_ptr extract_max()
 478         {
 479             return exempt_ptr(do_extract_max( []( key_type const& ) {}));
 480         }
 481
 482         /// Extracts the maximal key and corresponding value
 483         /**
 484             Returns \p exempt_ptr pointer to the rightmost item.
 485             If the set is empty, returns empty \p exempt_ptr.
 486
 487             \p Func functor is used to store maximal key.
 488             \p Func has the following signature:
 489             \code
 490                 struct functor {
 491                     void operator()( key_type const& key );
 492                 };
 493             \endcode
 494             If the tree is empty, \p f is not called.
 495             Otherwise, is it called with maximal key, the pointer to corresponding value is returned
 496             as \p exempt_ptr.
 497
 498             @note Due the concurrent nature of the map, the function extracts <i>nearly</i> maximal key.
 499             It means that the function gets rightmost leaf of the tree and tries to unlink it.
 500             During unlinking, a concurrent thread may insert an item with key great than leftmost item's key.
 501             So, the function returns the item with maximum key at the moment of tree traversing.
 502
 503             RCU \p synchronize method can be called. RCU should NOT be locked.
 504             The function does not free the item.
 505             The deallocator will be implicitly invoked when the returned object is destroyed or when
 506             its \p release() is called.
 507         */
 508         template <typename Func>
 509         exempt_ptr extract_max( Func f )
 510         {
 511             return exempt_ptr(do_extract_max( [&f]( key_type const& key ) { f(key); }));
 512         }
 513
 514         /// Extracts the maximal key and corresponding value
 515         /**
 516             This function is a shortcut for the following call:
 517             \code
 518                 key_type key;
 519                 exempt_ptr xp = theTree.extract_max( [&key]( key_type const& k ) { key = k; } );
 520             \endode
 521             \p key_type should be copy-assignable. The copy of maximal key
 522             is returned in \p max_key argument.
 523         */
 524         typename std::enable_if< std::is_copy_assignable<key_type>::value, exempt_ptr >::type
 525         extract_max_key( key_type& max_key )
 526         {
 527             return exempt_ptr(do_extract_max( [&max_key]( key_type const& key ) { max_key = key; }));
 528         }
 529
 530         /// Extracts an item from the map
 531         /**
 532             The function searches an item with key equal to \p key in the tree,
 533             unlinks it, and returns \p exempt_ptr pointer to a value found.
 534             If \p key is not found the function returns an empty \p exempt_ptr.
 535
 536             RCU \p synchronize method can be called. RCU should NOT be locked.
 537             The function does not destroy the value found.
 538             The disposer will be implicitly invoked when the returned object is destroyed or when
 539             its \p release() member function is called.
 540         */
 541         template <typename Q>
 542         exempt_ptr extract( Q const& key )
 543         {
 544             return exempt_ptr(do_extract( key ));
 545         }
 546
 547
 548         /// Extracts an item from the map using \p pred for searching
 549         /**
 550             The function is an analog of \p extract(Q const&)
 551             but \p pred is used for key compare.
 552             \p Less has the interface like \p std::less.
 553             \p pred must imply the same element order as the comparator used for building the tree.
 554         */
 555         template <typename Q, typename Less>
 556         exempt_ptr extract_with( Q const& key, Less pred )
 557         {
 558             return exempt_ptr(do_extract_with( key, pred ));
 559         }
 560
 561         /// Find the key \p key
 562         /**
 563             The function searches the item with key equal to \p key and calls the functor \p f for item found.
 564             The interface of \p Func functor is:
 565             \code
 566             struct functor {
 567                 void operator()( key_type const& key, mapped_type& item );
 568             };
 569             \endcode
 570             where \p item is the item found.
 571             The functor is called under node-level lock.
 572
 573             The function applies RCU lock internally.
 574
 575             The function returns \p true if \p key is found, \p false otherwise.
 576         */
 577         template <typename K, typename Func>
 578         bool find( K const& key, Func f )
 579         {
 580             return do_find( key, key_comparator(),
 581                 [&f]( node_type * pNode ) -> bool {
 582                     assert( pNode != nullptr );
 583                     mapped_type pVal = pNode->m_pValue.load( memory_model::memory_order_relaxed );
 584                     if ( pVal ) {
 585                         f( pNode->m_key, *pVal );
 586                         return true;
 587                     }
 588                     return false;
 589                 }
 590             );
 591         }
 592
 593         /// Finds the key \p val using \p pred predicate for searching
 594         /**
 595             The function is an analog of \p find(K const&, Func)
 596             but \p pred is used for key comparing.
 597             \p Less functor has the interface like \p std::less.
 598             \p Less must imply the same element order as the comparator used for building the map.
 599         */
 600         template <typename K, typename Less, typename Func>
 601         bool find_with( K const& key, Less pred, Func f )
 602         {
 603             CDS_UNUSED( pred );
 604             return do_find( key, cds::opt::details::make_comparator_from_less<Less>(),
 605                 [&f]( node_type * pNode ) -> bool {
 606                     assert( pNode != nullptr );
 607                     mapped_type pVal = pNode->m_pValue.load( memory_model::memory_order_relaxed );
 608                     if ( pVal ) {
 609                         f( pNode->m_key, *pVal );
 610                         return true;
 611                     }
 612                     return false;
 613                 }
 614             );
 615         }
 616
 617         /// Checks whether the map contains \p key
 618         /**
 619             The function searches the item with key equal to \p key
 620             and returns \p true if it is found, and \p false otherwise.
 621
 622             The function applies RCU lock internally.
 623         */
 624         template <typename K>
 625         bool contains( K const& key )
 626         {
 627             return do_find( key, key_comparator(), []( node_type * ) -> bool { return true; });
 628         }
 629
 630         /// Checks whether the map contains \p key using \p pred predicate for searching
 631         /**
 632             The function is similar to <tt>contains( key )</tt> but \p pred is used for key comparing.
 633             \p Less functor has the interface like \p std::less.
 634             \p Less must imply the same element order as the comparator used for building the set.
 635         */
 636         template <typename K, typename Less>
 637         bool contains( K const& key, Less pred )
 638         {
 639             CDS_UNUSED( pred );
 640             return do_find( key, cds::opt::details::make_comparator_from_less<Less>(), []( node_type * ) -> bool { return true; } );
 641         }
 642
 643         /// Clears the tree (thread safe, not atomic)
 644         /**
 645             The function unlink all items from the tree.
 646             The function is thread safe but not atomic: in multi-threaded environment with parallel insertions
 647             this sequence
 648             \code
 649             set.clear();
 650             assert( set.empty() );
 651             \endcode
 652             the assertion could be raised.
 653
 654             For each node the \ref disposer will be called after unlinking.
 655
 656             RCU \p synchronize method can be called. RCU should not be locked.
 657         */
 658         void clear()
 659         {
 660             while ( extract_min() );
 661         }
 662
 663         /// Clears the tree (not thread safe)
 664         /**
 665             This function is not thread safe and may be called only when no other thread deals with the tree.
 666             The function is used in the tree destructor.
 667         */
 668         void unsafe_clear()
 669         {
 670             clear(); // temp solution
 671             //TODO
 672         }
 673
 674         /// Checks if the map is empty
 675         bool empty() const
 676         {
 677             return m_Root.m_pRight.load( memory_model::memory_order_relaxed ) == nullptr;
 678         }
 679
 680         /// Returns item count in the map
 681         /**
 682             Only leaf nodes containing user data are counted.
 683
 684             The value returned depends on item counter type provided by \p Traits template parameter.
 685             If it is \p atomicity::empty_item_counter this function always returns 0.
 686
 687             The function is not suitable for checking the tree emptiness, use \p empty()
 688             member function for this purpose.
 689         */
 690         size_t size() const
 691         {
 692             return m_ItemCounter;
 693         }
 694
 695         /// Returns const reference to internal statistics
 696         stat const& statistics() const
 697         {
 698             return m_stat;
 699         }
 700
 701         /// Returns reference to \p sync_monitor object
 702         sync_monitor& monitor()
 703         {
 704             return m_Monitor;
 705         }
 706         //@cond
 707         sync_monitor const& monitor() const
 708         {
 709             return m_Monitor;
 710         }
 711         //@endcond
 712
 713         /// Checks internal consistency (not atomic, not thread-safe)
 714         /**
 715             The debugging function to check internal consistency of the tree.
 716         */
 717         bool check_consistency() const
 718         {
 719             return check_consistency([]( size_t /*nLevel*/, size_t /*hLeft*/, size_t /*hRight*/ ){} );
 720         }
 721
 722         /// Checks internal consistency (not atomic, not thread-safe)
 723         /**
 724             The debugging function to check internal consistency of the tree.
 725             The functor \p Func is called if a violation of internal tree structure
 726             is found:
 727             \code
 728             struct functor {
 729                 void operator()( size_t nLevel, size_t hLeft, size_t hRight );
 730             };
 731             \endcode
 732             where
 733             - \p nLevel - the level where the violation is found
 734             - \p hLeft - the height of left subtree
 735             - \p hRight - the height of right subtree
 736
 737             The functor is called for each violation found.
 738         */
 739         template <typename Func>
 740         bool check_consistency( Func f ) const
 741         {
 742             node_type * pChild = child( m_pRoot, right_child, memory_model::memory_order_acquire );
 743             if ( pChild ) {
 744                 size_t nErrors = 0;
 745                 do_check_consistency( pChild, 1, f, nErrors );
 746                 return nErrors == 0;
 747             }
 748             return true;
 749         }
 750
 751     protected:
 752         //@cond
 753         template <typename Func>
 754         size_t do_check_consistency( node_type * pNode, size_t nLevel, Func f, size_t& nErrors ) const
 755         {
 756             if ( pNode ) {
 757                 key_comparator cmp;
 758                 node_type * pLeft = child( pNode, left_child, memory_model::memory_order_acquire );
 759                 node_type * pRight = child( pNode, right_child, memory_model::memory_order_acquire );
 760                 if ( pLeft && cmp( pLeft->m_key, pNode->m_key ) > 0 )
 761                     ++nErrors;
 762                 if (  pRight && cmp( pNode->m_key, pRight->m_key ) > 0 )
 763                     ++nErrors;
 764
 765                 size_t hLeft = do_check_consistency( pLeft, nLevel + 1, f, nErrors );
 766                 size_t hRight = do_check_consistency( pRight, nLevel + 1, f, nErrors );
 767
 768                 if ( hLeft >= hRight ) {
 769                     if ( hLeft - hRight > 1 ) {
 770                         f( nLevel, hLeft, hRight );
 771                         ++nErrors;
 772                     }
 773                     return hLeft;
 774                 }
 775                 else {
 776                     if ( hRight - hLeft > 1 ) {
 777                         f( nLevel, hLeft, hRight );
 778                         ++nErrors;
 779                     }
 780                     return hRight;
 781                 }
 782             }
 783             return 0;
 784         }
 785
 786         template <typename Q, typename Compare, typename Func>
 787         bool do_find( Q& key, Compare cmp, Func f ) const
 788         {
 789             find_result result;
 790             {
 791                 rcu_lock l;
 792                 result = try_find( key, cmp, f, m_pRoot, right_child, 0 );
 793             }
 794             assert( result != find_result::retry );
 795             return result == find_result::found;
 796         }
 797
 798         template <typename K, typename Compare, typename Func>
 799         int do_update( K const& key, Compare cmp, Func funcUpdate, int nFlags )
 800         {
 801             check_deadlock_policy::check();
 802
 803             rcu_disposer removed_list;
 804             {
 805                 rcu_lock l;
 806                 return try_update_root( key, cmp, nFlags, funcUpdate, removed_list );
 807             }
 808         }
 809
 810         template <typename K, typename Compare, typename Func>
 811         bool do_remove( K const& key, Compare cmp, Func func )
 812         {
 813             // Func must return true if the value was disposed
 814             //              or false if the value was extracted
 815
 816             check_deadlock_policy::check();
 817
 818             rcu_disposer removed_list;
 819             {
 820                 rcu_lock l;
 821                 return try_remove_root( key, cmp, func, removed_list );
 822             }
 823         }
 824
 825         template <typename Func>
 826         mapped_type do_extract_min( Func f )
 827         {
 828             mapped_type pExtracted = nullptr;
 829             do_extract_minmax(
 830                 left_child,
 831                 [&pExtracted, &f]( key_type const& key, mapped_type pVal, rcu_disposer& ) -> bool { f( key ); pExtracted = pVal; return false; }
 832             );
 833             return pExtracted;
 834         }
 835
 836         template <typename Func>
 837         mapped_type do_extract_max( Func f )
 838         {
 839             mapped_type pExtracted = nullptr;
 840             do_extract_minmax(
 841                 right_child,
 842                 [&pExtracted, &f]( key_type const& key, mapped_type pVal, rcu_disposer& ) -> bool { f( key ); pExtracted = pVal; return false; }
 843             );
 844             return pExtracted;
 845         }
 846
 847         template <typename Func>
 848         void do_extract_minmax( int nDir, Func func )
 849         {
 850             check_deadlock_policy::check();
 851
 852             rcu_disposer removed_list;
 853             {
 854                 rcu_lock l;
 855
 856                 while ( true ) {
 857                     int result;
 858
 859                     // get right child of root
 860                     node_type * pChild = child( m_pRoot, right_child, memory_model::memory_order_acquire );
 861                     if ( pChild ) {
 862                         version_type nChildVersion = pChild->version( memory_model::memory_order_acquire );
 863                         if ( nChildVersion & node_type::shrinking ) {
 864                             m_stat.onRemoveRootWaitShrinking();
 865                             pChild->template wait_until_shrink_completed<back_off>( memory_model::memory_order_acquire );
 866                             result = update_flags::retry;
 867                         }
 868                         else if ( pChild == child( m_pRoot, right_child, memory_model::memory_order_acquire )) {
 869                             result = try_extract_minmax( nDir, func, m_pRoot, pChild, nChildVersion, removed_list );
 870                         }
 871                         else
 872                             result = update_flags::retry;
 873                     }
 874                     else
 875                         return;
 876
 877                     if ( result == update_flags::retry )
 878                         m_stat.onRemoveRetry();
 879                     else {
 880                         m_stat.onExtract( result == update_flags::result_removed );
 881                         return;
 882                     }
 883                 }
 884             }
 885         }
 886
 887         template <typename Q>
 888         mapped_type do_extract( Q const& key )
 889         {
 890             mapped_type pExtracted = nullptr;
 891             do_remove(
 892                 key,
 893                 key_comparator(),
 894                 [&pExtracted]( key_type const&, mapped_type pVal, rcu_disposer& ) -> bool { pExtracted = pVal; return false; }
 895             );
 896             m_stat.onExtract( pExtracted != nullptr );
 897             return pExtracted;
 898         }
 899
 900         template <typename Q, typename Less>
 901         mapped_type do_extract_with( Q const& key, Less pred )
 902         {
 903             CDS_UNUSED( pred );
 904             mapped_type pExtracted = nullptr;
 905             do_remove(
 906                 key,
 907                 cds::opt::details::make_comparator_from_less<Less>(),
 908                 [&pExtracted]( key_type const&, mapped_type pVal, rcu_disposer& ) -> bool { pExtracted = pVal; return false; }
 909             );
 910             m_stat.onExtract( pExtracted != nullptr );
 911             return pExtracted;
 912         }
 913         //@endcond
 914
 915     private:
 916         //@cond
 917         static int height( node_type * pNode, atomics::memory_order order )
 918         {
 919             assert( pNode );
 920             return pNode->m_nHeight.load( order );
 921         }
 922         static void set_height( node_type * pNode, int h, atomics::memory_order order )
 923         {
 924             assert( pNode );
 925             pNode->m_nHeight.store( h, order );
 926         }
 927         static int height_null( node_type * pNode, atomics::memory_order order )
 928         {
 929             return pNode ? height( pNode, order ) : 0;
 930         }
 931
 932         static CDS_CONSTEXPR int const c_stackSize = 64;
 933
 934         template <typename Q, typename Compare, typename Func>
 935         find_result try_find( Q const& key, Compare cmp, Func f, node_type * pNode, int nDir, version_type nVersion ) const
 936         {
 937             assert( gc::is_locked() );
 938             assert( pNode );
 939
 940             struct stack_record
 941             {
 942                 node_type * pNode;
 943                 version_type nVersion;
 944                 int nDir;
 945             };
 946
 947             stack_record stack[c_stackSize];
 948             int pos = 0;
 949             stack[0].pNode = pNode;
 950             stack[0].nVersion = nVersion;
 951             stack[0].nDir = nDir;
 952
 953             while ( pos >= 0 ) {
 954                 pNode = stack[pos].pNode;
 955                 nVersion = stack[pos].nVersion;
 956                 nDir = stack[pos].nDir;
 957
 958                 while ( true ) {
 959                     node_type * pChild = child( pNode, nDir, memory_model::memory_order_acquire );
 960                     if ( !pChild ) {
 961                         if ( pNode->version(memory_model::memory_order_acquire) != nVersion ) {
 962                             --pos;
 963                             m_stat.onFindRetry();
 964                             break; // retry
 965                         }
 966                         m_stat.onFindFailed();
 967                         return find_result::not_found;
 968                     }
 969
 970                     int nCmp = cmp( key, pChild->m_key );
 971                     if ( nCmp == 0 ) {
 972                         if ( pChild->is_valued( memory_model::memory_order_acquire ) ) {
 973                             // key found
 974                             node_scoped_lock l( m_Monitor, *pChild );
 975                             if ( child(pNode, nDir, memory_model::memory_order_acquire) == pChild ) {
 976                                 if ( pChild->is_valued( memory_model::memory_order_relaxed )) {
 977                                     if ( f( pChild ) ) {
 978                                         m_stat.onFindSuccess();
 979                                         return find_result::found;
 980                                     }
 981                                 }
 982                             }
 983                             else {
 984                                 m_stat.onFindRetry();
 985                                 continue;
 986                             }
 987                         }
 988                         m_stat.onFindFailed();
 989                         return find_result::not_found;
 990                     }
 991                     else {
 992                         version_type nChildVersion = pChild->version( memory_model::memory_order_acquire );
 993                         if ( nChildVersion & node_type::shrinking ) {
 994                             m_stat.onFindWaitShrinking();
 995                             pChild->template wait_until_shrink_completed<back_off>( memory_model::memory_order_acquire );
 996
 997                             if ( pNode->version(memory_model::memory_order_acquire) != nVersion ) {
 998                                 --pos;
 999                                 m_stat.onFindRetry();
1000                                 break; // retry
1001                             }
1002                         }
1003                         else if ( nChildVersion != node_type::unlinked && child( pNode, nDir, memory_model::memory_order_acquire ) == pChild )
1004                         {
1005                             if ( pNode->version(memory_model::memory_order_acquire) != nVersion ) {
1006                                 --pos;
1007                                 m_stat.onFindRetry();
1008                                 break; // retry
1009                             }
1010
1011                             ++pos;
1012                             assert(pos < c_stackSize);
1013                             stack[pos].pNode = pChild;
1014                             stack[pos].nVersion = nChildVersion;
1015                             stack[pos].nDir = nCmp;
1016                             break; // child iteration
1017                         }
1018
1019                         if ( pNode->version(memory_model::memory_order_acquire) != nVersion ) {
1020                             --pos;
1021                             m_stat.onFindRetry();
1022                             break; // retry
1023                         }
1024                     }
1025                     m_stat.onFindRetry();
1026                 }
1027             }
1028             return find_result::retry;
1029         }
1030
1031         template <typename K, typename Compare, typename Func>
1032         int try_update_root( K const& key, Compare cmp, int nFlags, Func funcUpdate, rcu_disposer& disp )
1033         {
1034             assert( gc::is_locked() );
1035
1036             while ( true ) {
1037                 int result;
1038
1039                 // get right child of root
1040                 node_type * pChild = child( m_pRoot, right_child, memory_model::memory_order_acquire );
1041                 if ( pChild ) {
1042                     version_type nChildVersion = pChild->version( memory_model::memory_order_acquire );
1043                     if ( nChildVersion & node_type::shrinking ) {
1044                         m_stat.onUpdateRootWaitShrinking();
1045                         pChild->template wait_until_shrink_completed<back_off>( memory_model::memory_order_acquire );
1046                         result = update_flags::retry;
1047                     }
1048                     else if ( pChild == child( m_pRoot, right_child, memory_model::memory_order_acquire ))
1049                         result = try_update( key, cmp, nFlags, funcUpdate, pChild, nChildVersion, disp );
1050                     else
1051                         result = update_flags::retry;
1052                 }
1053                 else {
1054                     // the tree is empty
1055                     if ( nFlags & update_flags::allow_insert ) {
1056                         // insert into tree as right child of the root
1057                         {
1058                             node_scoped_lock l( m_Monitor, *m_pRoot );
1059                             if ( child( m_pRoot, right_child, memory_model::memory_order_acquire ) != nullptr ) {
1060                                 result = update_flags::retry;
1061                                 continue;
1062                             }
1063
1064                             node_type * pNew = alloc_node( key, 1, 0, m_pRoot, nullptr, nullptr );
1065                             mapped_type pVal = funcUpdate( pNew );
1066                             assert( pVal != nullptr );
1067                             pNew->m_pValue.store( pVal, memory_model::memory_order_release );
1068
1069                             m_pRoot->child( pNew, right_child, memory_model::memory_order_release);
1070                             set_height( m_pRoot, 2, memory_model::memory_order_release );
1071                         }
1072
1073                         ++m_ItemCounter;
1074                         m_stat.onInsertSuccess();
1075                         return update_flags::result_inserted;
1076                     }
1077
1078                     return update_flags::failed;
1079                 }
1080
1081                 if ( result != update_flags::retry )
1082                     return result;
1083             }
1084         }
1085
1086         template <typename K, typename Compare, typename Func>
1087         bool try_remove_root( K const& key, Compare cmp, Func func, rcu_disposer& disp )
1088         {
1089             assert( gc::is_locked() );
1090
1091             while ( true ) {
1092                 int result;
1093
1094                 // get right child of root
1095                 node_type * pChild = child( m_pRoot, right_child, memory_model::memory_order_acquire );
1096                 if ( pChild ) {
1097                     version_type nChildVersion = pChild->version( memory_model::memory_order_acquire );
1098                     if ( nChildVersion & node_type::shrinking ) {
1099                         m_stat.onRemoveRootWaitShrinking();
1100                         pChild->template wait_until_shrink_completed<back_off>( memory_model::memory_order_acquire );
1101                         result = update_flags::retry;
1102                     }
1103                     else if ( pChild == child( m_pRoot, right_child, memory_model::memory_order_acquire )) {
1104                         result = try_remove( key, cmp, func, m_pRoot, pChild, nChildVersion, disp );
1105                     }
1106                     else
1107                         result = update_flags::retry;
1108                 }
1109                 else
1110                     return false;
1111
1112                 if ( result == update_flags::retry )
1113                     m_stat.onRemoveRetry();
1114                 else {
1115                     m_stat.onRemove( result == update_flags::result_removed );
1116                     return result == update_flags::result_removed;
1117                 }
1118             }
1119         }
1120
1121         template <typename K, typename Compare, typename Func>
1122         int try_update( K const& key, Compare cmp, int nFlags, Func funcUpdate, node_type * pNode, version_type nVersion, rcu_disposer& disp )
1123         {
1124             assert( gc::is_locked() );
1125             assert( nVersion != node_type::unlinked );
1126
1127             struct stack_record
1128             {
1129                 node_type * pNode;
1130                 version_type nVersion;
1131             };
1132
1133             stack_record stack[c_stackSize];
1134             int pos = 0;
1135             stack[0].pNode = pNode;
1136             stack[0].nVersion = nVersion;
1137
1138             while ( pos >= 0 ) {
1139                 pNode = stack[pos].pNode;
1140                 nVersion = stack[pos].nVersion;
1141
1142                 int nCmp = cmp( key, pNode->m_key );
1143                 if ( nCmp == 0 ) {
1144                     int result = try_update_node( nFlags, funcUpdate, pNode, nVersion, disp );
1145                     if ( result != update_flags::retry )
1146                         return result;
1147                     --pos;
1148                     m_stat.onUpdateRetry();
1149                     continue;
1150                 }
1151
1152                 while ( true ) {
1153                     node_type * pChild = child( pNode, nCmp, memory_model::memory_order_acquire );
1154                     if ( pNode->version(memory_model::memory_order_acquire) != nVersion ) {
1155                         --pos;
1156                         m_stat.onUpdateRetry();
1157                         break;
1158                     }
1159
1160                     if ( pChild == nullptr ) {
1161                         // insert new node
1162                         if ( nFlags & update_flags::allow_insert ) {
1163                             int result = try_insert_node( key, funcUpdate, pNode, nCmp, nVersion, disp );
1164                             if ( result != update_flags::retry )
1165                                 return result;
1166                             --pos;
1167                             m_stat.onUpdateRetry();
1168                             break;
1169                         }
1170                         else
1171                             return update_flags::failed;
1172                     }
1173                     else {
1174                         // update child
1175                         version_type nChildVersion = pChild->version( memory_model::memory_order_acquire );
1176                         if ( nChildVersion & node_type::shrinking ) {
1177                             m_stat.onUpdateWaitShrinking();
1178                             pChild->template wait_until_shrink_completed<back_off>( memory_model::memory_order_acquire );
1179                             // retry
1180                         }
1181                         else if ( pChild == child( pNode, nCmp, memory_model::memory_order_acquire )) {
1182                             // this second read is important, because it is protected by nChildVersion
1183
1184                             // validate the read that our caller took to get to node
1185                             if ( pNode->version( memory_model::memory_order_acquire ) != nVersion ) {
1186                                 --pos;
1187                                 m_stat.onUpdateRetry();
1188                                 break; // retry
1189                             }
1190                             // At this point we know that the traversal our parent took to get to node is still valid.
1191                             // The recursive implementation will validate the traversal from node to
1192                             // child, so just prior to the node nVersion validation both traversals were definitely okay.
1193                             // This means that we are no longer vulnerable to node shrinks, and we don't need
1194                             // to validate node version any more.
1195                             ++pos;
1196                             assert( pos < c_stackSize );
1197                             stack[pos].pNode = pChild;
1198                             stack[pos].nVersion = nChildVersion;
1199                             assert( nChildVersion != node_type::unlinked );
1200                             break; // child iteration
1201                         }
1202                         m_stat.onUpdateRetry();
1203                     }
1204                 }
1205             }
1206             return update_flags::retry;
1207         }
1208
1209         template <typename K, typename Compare, typename Func>
1210         int try_remove( K const& key, Compare cmp, Func func, node_type * pParent, node_type * pNode, version_type nVersion, rcu_disposer& disp )
1211         {
1212             assert( gc::is_locked() );
1213             assert( nVersion != node_type::unlinked );
1214
1215             struct stack_record
1216             {
1217                 node_type * pParent;
1218                 node_type * pNode;
1219                 version_type nVersion;
1220             };
1221
1222             stack_record stack[c_stackSize];
1223             int pos = 0;
1224             stack[0].pParent = pParent;
1225             stack[0].pNode = pNode;
1226             stack[0].nVersion = nVersion;
1227
1228             while ( pos >= 0 ) {
1229                 pParent = stack[pos].pParent;
1230                 pNode = stack[pos].pNode;
1231                 nVersion = stack[pos].nVersion;
1232
1233                 int nCmp = cmp( key, pNode->m_key );
1234                 if ( nCmp == 0 ) {
1235                     int result = try_remove_node( pParent, pNode, nVersion, func, disp );
1236                     if ( result != update_flags::retry )
1237                         return result;
1238                     --pos;
1239                     m_stat.onRemoveRetry();
1240                     continue;
1241                 }
1242
1243                 while ( true ) {
1244                     node_type * pChild = child( pNode, nCmp, memory_model::memory_order_acquire );
1245                     if ( pNode->version(memory_model::memory_order_acquire) != nVersion ) {
1246                         --pos;
1247                         m_stat.onRemoveRetry();
1248                         break;
1249                     }
1250
1251                     if ( pChild == nullptr )
1252                         return update_flags::failed;
1253
1254                     // update child
1255                     version_type nChildVersion = pChild->version( memory_model::memory_order_acquire );
1256                     if ( nChildVersion & node_type::shrinking ) {
1257                         m_stat.onRemoveWaitShrinking();
1258                         pChild->template wait_until_shrink_completed<back_off>( memory_model::memory_order_acquire );
1259                         // retry
1260                     }
1261                     else if ( pChild == child( pNode, nCmp, memory_model::memory_order_acquire )) {
1262                         // this second read is important, because it is protected by nChildVersion
1263
1264                         // validate the read that our caller took to get to node
1265                         if ( pNode->version(memory_model::memory_order_acquire) != nVersion ) {
1266                             --pos;
1267                             m_stat.onRemoveRetry();
1268                             break;
1269                         }
1270
1271                         // At this point we know that the traversal our parent took to get to node is still valid.
1272                         // The recursive implementation will validate the traversal from node to
1273                         // child, so just prior to the node nVersion validation both traversals were definitely okay.
1274                         // This means that we are no longer vulnerable to node shrinks, and we don't need
1275                         // to validate node version any more.
1276                         ++pos;
1277                         assert( pos < c_stackSize );
1278                         stack[pos].pParent = pNode;
1279                         stack[pos].pNode = pChild;
1280                         stack[pos].nVersion = nChildVersion;
1281                         break; // child iteration
1282                     }
1283                     m_stat.onRemoveRetry();
1284                 }
1285             }
1286             return update_flags::retry;
1287         }
1288
1289         template <typename Func>
1290         int try_extract_minmax( int nDir, Func func, node_type * pParent, node_type * pNode, version_type nVersion, rcu_disposer& disp )
1291         {
1292             assert( gc::is_locked() );
1293             assert( nVersion != node_type::unlinked );
1294
1295             struct stack_record
1296             {
1297                 node_type * pParent;
1298                 node_type * pNode;
1299                 version_type nVersion;
1300             };
1301
1302             stack_record stack[c_stackSize];
1303             int pos = 0;
1304             stack[0].pParent = pParent;
1305             stack[0].pNode = pNode;
1306             stack[0].nVersion = nVersion;
1307
1308             while ( pos >= 0 ) {
1309                 pParent = stack[pos].pParent;
1310                 pNode = stack[pos].pNode;
1311                 nVersion = stack[pos].nVersion;
1312
1313                 while ( true ) {
1314                     node_type * pChild = child( pNode, nDir, memory_model::memory_order_acquire );
1315                     if ( pNode->version(memory_model::memory_order_acquire) != nVersion ) {
1316                         --pos;
1317                         m_stat.onRemoveRetry();
1318                         break;
1319                     }
1320
1321                     if ( pChild == nullptr ) {
1322                         // Found min/max
1323                         assert(pNode->is_valued( memory_model::memory_order_acquire ));
1324                         int result = try_remove_node( pParent, pNode, nVersion, func, disp );
1325                         if ( result != update_flags::retry )
1326                             return result;
1327                         --pos;
1328                         m_stat.onRemoveRetry();
1329                         break;
1330                     }
1331
1332                     version_type nChildVersion = pChild->version( memory_model::memory_order_acquire );
1333                     if ( nChildVersion & node_type::shrinking ) {
1334                         m_stat.onRemoveWaitShrinking();
1335                         pChild->template wait_until_shrink_completed<back_off>( memory_model::memory_order_acquire );
1336                         // retry
1337                     }
1338                     else if ( pChild == child( pNode, nDir, memory_model::memory_order_acquire )) {
1339                         // this second read is important, because it is protected by nChildVersion
1340
1341                         // validate the read that our caller took to get to node
1342                         if ( pNode->version( memory_model::memory_order_acquire ) != nVersion ) {
1343                             --pos;
1344                             m_stat.onRemoveRetry();
1345                             break;
1346                         }
1347
1348                         // At this point we know that the traversal our parent took to get to node is still valid.
1349                         // The recursive implementation will validate the traversal from node to
1350                         // child, so just prior to the node nVersion validation both traversals were definitely okay.
1351                         // This means that we are no longer vulnerable to node shrinks, and we don't need
1352                         // to validate node version any more.
1353                         ++pos;
1354                         assert( pos < c_stackSize );
1355                         stack[pos].pParent = pNode;
1356                         stack[pos].pNode = pChild;
1357                         stack[pos].nVersion = nChildVersion;
1358                         break; // child iteration
1359                     }
1360                     m_stat.onRemoveRetry();
1361                 }
1362             }
1363             return update_flags::retry;
1364         }
1365
1366         template <typename K, typename Func>
1367         int try_insert_node( K const& key, Func funcUpdate, node_type * pNode, int nDir, version_type nVersion, rcu_disposer& disp )
1368         {
1369             node_type * pNew;
1370
1371             auto fnCreateNode = [&funcUpdate]( node_type * pNew ) {
1372                 mapped_type pVal = funcUpdate( pNew );
1373                 assert( pVal != nullptr );
1374                 pNew->m_pValue.store( pVal, memory_model::memory_order_release );
1375             };
1376
1377             if ( c_bRelaxedInsert ) {
1378                 if ( pNode->version( memory_model::memory_order_acquire ) != nVersion
1379                      || child( pNode, nDir, memory_model::memory_order_acquire ) != nullptr )
1380                 {
1381                     m_stat.onInsertRetry();
1382                     return update_flags::retry;
1383                 }
1384
1385                 fnCreateNode( pNew = alloc_node( key, 1, 0, pNode, nullptr, nullptr ));
1386             }
1387
1388             node_type * pDamaged;
1389             {
1390                 assert( pNode != nullptr );
1391                 node_scoped_lock l( m_Monitor, *pNode );
1392
1393                 if ( pNode->version( memory_model::memory_order_acquire ) != nVersion
1394                      || child( pNode, nDir, memory_model::memory_order_acquire ) != nullptr )
1395                 {
1396                     if ( c_bRelaxedInsert ) {
1397                         mapped_type pVal = pNew->m_pValue.load( memory_model::memory_order_relaxed );
1398                         pNew->m_pValue.store( nullptr, memory_model::memory_order_relaxed );
1399                         free_value( pVal );
1400                         free_node( pNew );
1401                         m_stat.onRelaxedInsertFailed();
1402                     }
1403
1404                     m_stat.onInsertRetry();
1405                     return update_flags::retry;
1406                 }
1407
1408                 if ( !c_bRelaxedInsert )
1409                     fnCreateNode( pNew = alloc_node( key, 1, 0, pNode, nullptr, nullptr ));
1410
1411                 pNode->child( pNew, nDir, memory_model::memory_order_release );
1412                 pDamaged = fix_height_locked( pNode );
1413             }
1414
1415             ++m_ItemCounter;
1416             m_stat.onInsertSuccess();
1417
1418             if ( pDamaged ) {
1419                 fix_height_and_rebalance( pDamaged, disp );
1420                 m_stat.onInsertRebalanceRequired();
1421             }
1422
1423             return update_flags::result_inserted;
1424         }
1425
1426         template <typename Func>
1427         int try_update_node( int nFlags, Func funcUpdate, node_type * pNode, version_type nVersion, rcu_disposer& disp )
1428         {
1429             mapped_type pOld;
1430             bool bInserted;
1431             assert( pNode != nullptr );
1432             {
1433                 node_scoped_lock l( m_Monitor, *pNode );
1434
1435                 if ( pNode->version(memory_model::memory_order_acquire) != nVersion )
1436                     return update_flags::retry;
1437
1438                 if ( pNode->is_unlinked( memory_model::memory_order_acquire )) {
1439                     m_stat.onUpdateUnlinked();
1440                     return update_flags::retry;
1441                 }
1442
1443                 if ( pNode->is_valued( memory_model::memory_order_relaxed ) && !(nFlags & update_flags::allow_update) ) {
1444                     m_stat.onInsertFailed();
1445                     return update_flags::failed;
1446                 }
1447
1448                 pOld = pNode->value( memory_model::memory_order_relaxed );
1449                 bInserted = pOld == nullptr;
1450                 mapped_type pVal = funcUpdate( pNode );
1451                 if ( pVal == pOld )
1452                     pOld = nullptr;
1453                 else {
1454                     assert( pVal != nullptr );
1455                     pNode->m_pValue.store( pVal, memory_model::memory_order_release );
1456                 }
1457             }
1458
1459             if ( pOld ) {
1460                 disp.dispose_value(pOld);
1461                 m_stat.onDisposeValue();
1462             }
1463
1464             if ( bInserted ) {
1465                 ++m_ItemCounter;
1466                 m_stat.onInsertSuccess();
1467                 return update_flags::result_inserted;
1468             }
1469
1470             m_stat.onUpdateSuccess();
1471             return update_flags::result_updated;
1472         }
1473
1474         template <typename Func>
1475         int try_remove_node( node_type * pParent, node_type * pNode, version_type nVersion, Func func, rcu_disposer& disp )
1476         {
1477             assert( pParent != nullptr );
1478             assert( pNode != nullptr );
1479
1480             if ( !pNode->is_valued( memory_model::memory_order_acquire ) )
1481                 return update_flags::failed;
1482
1483             if ( child( pNode, left_child, memory_model::memory_order_acquire ) == nullptr
1484               || child( pNode, right_child, memory_model::memory_order_acquire ) == nullptr )
1485             {
1486                 // pNode can be replaced with its child
1487
1488                 node_type * pDamaged;
1489                 mapped_type pOld;
1490                 {
1491                     node_scoped_lock lp( m_Monitor, *pParent );
1492                     if ( pParent->is_unlinked( memory_model::memory_order_acquire ) || parent( pNode, memory_model::memory_order_acquire ) != pParent )
1493                         return update_flags::retry;
1494
1495                     {
1496                         node_scoped_lock ln( m_Monitor, *pNode );
1497                         if ( pNode->version( memory_model::memory_order_acquire ) != nVersion )
1498                             return update_flags::retry;
1499
1500                         pOld = pNode->value( memory_model::memory_order_relaxed );
1501                         if ( !pOld )
1502                             return update_flags::failed;
1503
1504                         if ( !try_unlink_locked( pParent, pNode, disp ))
1505                             return update_flags::retry;
1506                     }
1507                     pDamaged = fix_height_locked( pParent );
1508                 }
1509
1510                 --m_ItemCounter;
1511                 if ( func( pNode->m_key, pOld, disp ))   // calls pOld disposer inside
1512                     m_stat.onDisposeValue();
1513                 else
1514                     m_stat.onExtractValue();
1515
1516                 if ( pDamaged ) {
1517                     fix_height_and_rebalance( pDamaged, disp );
1518                     m_stat.onRemoveRebalanceRequired();
1519                 }
1520             }
1521             else {
1522                 // pNode is an internal with two children
1523
1524                 mapped_type pOld;
1525                 {
1526                     node_scoped_lock ln( m_Monitor, *pNode );
1527                     pOld = pNode->value( memory_model::memory_order_relaxed );
1528                     if ( pNode->version( memory_model::memory_order_relaxed ) != nVersion )
1529                         return update_flags::retry;
1530                     if ( !pOld )
1531                         return update_flags::failed;
1532
1533                     pNode->m_pValue.store( nullptr, memory_model::memory_order_release );
1534                     m_stat.onMakeRoutingNode();
1535                 }
1536
1537                 --m_ItemCounter;
1538                 if ( func( pNode->m_key, pOld, disp ))  // calls pOld disposer inside
1539                     m_stat.onDisposeValue();
1540                 else
1541                     m_stat.onExtractValue();
1542             }
1543             return update_flags::result_removed;
1544         }
1545
1546         bool try_unlink_locked( node_type * pParent, node_type * pNode, rcu_disposer& disp )
1547         {
1548             // pParent and pNode must be locked
1549             assert( !pParent->is_unlinked(memory_model::memory_order_relaxed) );
1550
1551             node_type * pParentLeft = child( pParent, left_child, memory_model::memory_order_relaxed );
1552             node_type * pParentRight = child( pParent, right_child, memory_model::memory_order_relaxed );
1553             if ( pNode != pParentLeft && pNode != pParentRight ) {
1554                 // node is no longer a child of parent
1555                 return false;
1556             }
1557
1558             assert( !pNode->is_unlinked( memory_model::memory_order_relaxed ));
1559             assert( pParent == parent( pNode, memory_model::memory_order_relaxed ));
1560
1561             node_type * pLeft = child( pNode, left_child, memory_model::memory_order_relaxed );
1562             node_type * pRight = child( pNode, right_child, memory_model::memory_order_relaxed );
1563             if ( pLeft != nullptr && pRight != nullptr ) {
1564                 // splicing is no longer possible
1565                 return false;
1566             }
1567             node_type * pSplice = pLeft ? pLeft : pRight;
1568
1569             if ( pParentLeft == pNode )
1570                 pParent->m_pLeft.store( pSplice, memory_model::memory_order_release );
1571             else
1572                 pParent->m_pRight.store( pSplice, memory_model::memory_order_release );
1573
1574             if ( pSplice )
1575                 pSplice->parent( pParent, memory_model::memory_order_release );
1576
1577             // Mark the node as unlinked
1578             pNode->version( node_type::unlinked, memory_model::memory_order_release );
1579
1580             // The value will be disposed by calling function
1581             pNode->m_pValue.store( nullptr, memory_model::memory_order_release );
1582
1583             disp.dispose( pNode );
1584             m_stat.onDisposeNode();
1585
1586             return true;
1587         }
1588
1589         //@endcond
1590
1591     private: // rotations
1592         //@cond
1593         int estimate_node_condition( node_type * pNode )
1594         {
1595             node_type * pLeft = child( pNode, left_child, memory_model::memory_order_acquire );
1596             node_type * pRight = child( pNode, right_child, memory_model::memory_order_acquire );
1597
1598             if ( (pLeft == nullptr || pRight == nullptr) && !pNode->is_valued( memory_model::memory_order_acquire ))
1599                 return unlink_required;
1600
1601             int h = height( pNode, memory_model::memory_order_acquire );
1602             int hL = height_null( pLeft, memory_model::memory_order_acquire );
1603             int hR = height_null( pRight, memory_model::memory_order_acquire );
1604
1605             int hNew = 1 + std::max( hL, hR );
1606             int nBalance = hL - hR;
1607
1608             if ( nBalance < -1 || nBalance > 1 )
1609                 return rebalance_required;
1610
1611             return h != hNew ? hNew : nothing_required;
1612         }
1613
1614         node_type * fix_height( node_type * pNode )
1615         {
1616             assert( pNode != nullptr );
1617             node_scoped_lock l( m_Monitor, *pNode );
1618             return fix_height_locked( pNode );
1619         }
1620
1621         node_type * fix_height_locked( node_type * pNode )
1622         {
1623             // pNode must be locked!!!
1624             int h = estimate_node_condition( pNode );
1625             switch ( h ) {
1626                 case rebalance_required:
1627                 case unlink_required:
1628                     return pNode;
1629                 case nothing_required:
1630                     return nullptr;
1631                 default:
1632                     set_height( pNode, h, memory_model::memory_order_release );
1633                     return parent( pNode, memory_model::memory_order_relaxed );
1634             }
1635         }
1636
1637         void fix_height_and_rebalance( node_type * pNode, rcu_disposer& disp )
1638         {
1639             while ( pNode && parent( pNode, memory_model::memory_order_acquire )) {
1640                 int nCond = estimate_node_condition( pNode );
1641                 if ( nCond == nothing_required || pNode->is_unlinked( memory_model::memory_order_acquire ) )
1642                     return;
1643
1644                 if ( nCond != unlink_required && nCond != rebalance_required )
1645                     pNode = fix_height( pNode );
1646                 else {
1647                     node_type * pParent = parent( pNode, memory_model::memory_order_acquire );
1648                     assert( pParent != nullptr );
1649                     {
1650                         node_scoped_lock lp( m_Monitor, *pParent );
1651                         if ( !pParent->is_unlinked( memory_model::memory_order_relaxed ) && parent( pNode, memory_model::memory_order_acquire ) == pParent ) {
1652                             node_scoped_lock ln( m_Monitor, *pNode );
1653                             pNode = rebalance_locked( pParent, pNode, disp );
1654                         }
1655                     }
1656                 }
1657             }
1658         }
1659
1660         node_type * rebalance_locked( node_type * pParent, node_type * pNode, rcu_disposer& disp )
1661         {
1662             // pParent and pNode should be locked.
1663             // Returns a damaged node, or nullptr if no more rebalancing is necessary
1664             assert( parent( pNode, memory_model::memory_order_relaxed ) == pParent );
1665
1666             node_type * pLeft = child( pNode, left_child, memory_model::memory_order_relaxed );
1667             node_type * pRight = child( pNode, right_child, memory_model::memory_order_relaxed );
1668
1669             if ( (pLeft == nullptr || pRight == nullptr) && !pNode->is_valued( memory_model::memory_order_relaxed )) {
1670                 if ( try_unlink_locked( pParent, pNode, disp ))
1671                     return fix_height_locked( pParent );
1672                 else {
1673                     // retry needed for pNode
1674                     return pNode;
1675                 }
1676             }
1677
1678             assert( child( pParent, left_child, memory_model::memory_order_relaxed ) == pNode
1679                  || child( pParent, right_child, memory_model::memory_order_relaxed ) == pNode );
1680
1681             int h = height( pNode, memory_model::memory_order_acquire );
1682             int hL = height_null( pLeft, memory_model::memory_order_acquire );
1683             int hR = height_null( pRight, memory_model::memory_order_acquire );
1684             int hNew = 1 + std::max( hL, hR );
1685             int balance = hL - hR;
1686
1687             if ( balance > 1 )
1688                 return rebalance_to_right_locked( pParent, pNode, pLeft, hR );
1689             else if ( balance < -1 )
1690                 return rebalance_to_left_locked( pParent, pNode, pRight, hL );
1691             else if ( hNew != h ) {
1692                 set_height( pNode, hNew, memory_model::memory_order_release );
1693
1694                 // pParent is already locked
1695                 return fix_height_locked( pParent );
1696             }
1697             else
1698                 return nullptr;
1699         }
1700
1701         node_type * rebalance_to_right_locked( node_type * pParent, node_type * pNode, node_type * pLeft, int hR )
1702         {
1703             assert( parent( pNode, memory_model::memory_order_relaxed ) == pParent );
1704             assert( child( pParent, left_child, memory_model::memory_order_relaxed ) == pNode
1705                  || child( pParent, right_child, memory_model::memory_order_relaxed ) == pNode );
1706
1707             // pParent and pNode is locked yet
1708             // pNode->pLeft is too large, we will rotate-right.
1709             // If pLeft->pRight is taller than pLeft->pLeft, then we will first rotate-left pLeft.
1710
1711             {
1712                 assert( pLeft != nullptr );
1713                 node_scoped_lock l( m_Monitor, *pLeft );
1714                 if ( pNode->m_pLeft.load( memory_model::memory_order_relaxed ) != pLeft )
1715                     return pNode; // retry for pNode
1716
1717                 int hL = height( pLeft, memory_model::memory_order_acquire );
1718                 if ( hL - hR <= 1 )
1719                     return pNode; // retry
1720
1721                 node_type * pLRight = child( pLeft, right_child, memory_model::memory_order_relaxed );
1722                 int hLR = height_null( pLRight, memory_model::memory_order_acquire );
1723                 node_type * pLLeft = child( pLeft, left_child, memory_model::memory_order_relaxed );
1724                 int hLL = height_null( pLLeft, memory_model::memory_order_acquire );
1725
1726                 if ( hLL > hLR ) {
1727                     // rotate right
1728                     return rotate_right_locked( pParent, pNode, pLeft, hR, hLL, pLRight, hLR );
1729                 }
1730                 else {
1731                     assert( pLRight != nullptr );
1732                     {
1733                         node_scoped_lock lr( m_Monitor, *pLRight );
1734                         if ( pLeft->m_pRight.load( memory_model::memory_order_acquire ) != pLRight )
1735                             return pNode; // retry
1736
1737                         hLR = height( pLRight, memory_model::memory_order_acquire );
1738                         if ( hLL > hLR )
1739                             return rotate_right_locked( pParent, pNode, pLeft, hR, hLL, pLRight, hLR );
1740
1741                         int hLRL = height_null( child( pLRight, left_child, memory_model::memory_order_relaxed ), memory_model::memory_order_acquire);
1742                         int balance = hLL - hLRL;
1743                         if ( balance >= -1 && balance <= 1 && !((hLL == 0 || hLRL == 0) && !pLeft->is_valued(memory_model::memory_order_relaxed))) {
1744                             // nParent.child.left won't be damaged after a double rotation
1745                             return rotate_right_over_left_locked( pParent, pNode, pLeft, hR, hLL, pLRight, hLRL );
1746                         }
1747                     }
1748
1749                     // focus on pLeft, if necessary pNode will be balanced later
1750                     return rebalance_to_left_locked( pNode, pLeft, pLRight, hLL );
1751                 }
1752             }
1753         }
1754
1755         node_type * rebalance_to_left_locked( node_type * pParent, node_type * pNode, node_type * pRight, int hL )
1756         {
1757             assert( parent( pNode, memory_model::memory_order_relaxed ) == pParent );
1758             assert( child( pParent, left_child, memory_model::memory_order_relaxed ) == pNode
1759                  || child( pParent, right_child, memory_model::memory_order_relaxed ) == pNode );
1760
1761             // pParent and pNode is locked yet
1762             {
1763                 assert( pRight != nullptr );
1764                 node_scoped_lock l( m_Monitor, *pRight );
1765                 if ( pNode->m_pRight.load( memory_model::memory_order_relaxed ) != pRight )
1766                     return pNode; // retry for pNode
1767
1768                 int hR = height( pRight, memory_model::memory_order_acquire );
1769                 if ( hL - hR >= -1 )
1770                     return pNode; // retry
1771
1772                 node_type * pRLeft = child( pRight, left_child, memory_model::memory_order_relaxed );
1773                 int hRL = height_null( pRLeft, memory_model::memory_order_acquire );
1774                 node_type * pRRight = child( pRight, right_child, memory_model::memory_order_relaxed );
1775                 int hRR = height_null( pRRight, memory_model::memory_order_acquire );
1776                 if ( hRR > hRL )
1777                     return rotate_left_locked( pParent, pNode, hL, pRight, pRLeft, hRL, hRR );
1778
1779                 {
1780                     assert( pRLeft != nullptr );
1781                     node_scoped_lock lrl( m_Monitor, *pRLeft );
1782                     if ( pRight->m_pLeft.load( memory_model::memory_order_acquire ) != pRLeft )
1783                         return pNode; // retry
1784
1785                     hRL = height( pRLeft, memory_model::memory_order_acquire );
1786                     if ( hRR >= hRL )
1787                         return rotate_left_locked( pParent, pNode, hL, pRight, pRLeft, hRL, hRR );
1788
1789                     node_type * pRLRight = child( pRLeft, right_child, memory_model::memory_order_relaxed );
1790                     int hRLR = height_null( pRLRight, memory_model::memory_order_acquire );
1791                     int balance = hRR - hRLR;
1792                     if ( balance >= -1 && balance <= 1 && !((hRR == 0 || hRLR == 0) && !pRight->is_valued( memory_model::memory_order_relaxed )))
1793                          return rotate_left_over_right_locked( pParent, pNode, hL, pRight, pRLeft, hRR, hRLR );
1794                 }
1795                 return rebalance_to_right_locked( pNode, pRight, pRLeft, hRR );
1796             }
1797         }
1798
1799         static void begin_change( node_type * pNode, version_type version )
1800         {
1801             assert(pNode->version(memory_model::memory_order_acquire) == version );
1802             assert( (version & node_type::shrinking) == 0 );
1803             pNode->version( version | node_type::shrinking, memory_model::memory_order_release );
1804         }
1805         static void end_change( node_type * pNode, version_type version )
1806         {
1807             // Clear shrinking and unlinked flags and increment version
1808             pNode->version( (version | node_type::version_flags) + 1, memory_model::memory_order_release );
1809         }
1810
1811         node_type * rotate_right_locked( node_type * pParent, node_type * pNode, node_type * pLeft, int hR, int hLL, node_type * pLRight, int hLR )
1812         {
1813             version_type nodeVersion = pNode->version( memory_model::memory_order_relaxed );
1814             node_type * pParentLeft = child( pParent, left_child, memory_model::memory_order_relaxed );
1815
1816             begin_change( pNode, nodeVersion );
1817
1818             pNode->m_pLeft.store( pLRight, memory_model::memory_order_release );
1819             if ( pLRight != nullptr )
1820                 pLRight->parent( pNode, memory_model::memory_order_release  );
1821
1822             atomics::atomic_thread_fence( memory_model::memory_order_release );
1823
1824             pLeft->m_pRight.store( pNode, memory_model::memory_order_release );
1825             pNode->parent( pLeft, memory_model::memory_order_release );
1826
1827             atomics::atomic_thread_fence( memory_model::memory_order_release );
1828
1829             if ( pParentLeft == pNode )
1830                 pParent->m_pLeft.store( pLeft, memory_model::memory_order_release );
1831             else {
1832                 assert( pParent->m_pRight.load( memory_model::memory_order_relaxed ) == pNode );
1833                 pParent->m_pRight.store( pLeft, memory_model::memory_order_release );
1834             }
1835             pLeft->parent( pParent, memory_model::memory_order_release );
1836
1837             atomics::atomic_thread_fence( memory_model::memory_order_release );
1838
1839             // fix up heights links
1840             int hNode = 1 + std::max( hLR, hR );
1841             set_height( pNode, hNode, memory_model::memory_order_release );
1842             set_height( pLeft, 1 + std::max( hLL, hNode ), memory_model::memory_order_release);
1843
1844             end_change( pNode, nodeVersion );
1845             m_stat.onRotateRight();
1846
1847             // We have damaged pParent, pNode (now parent.child.right), and pLeft (now
1848             // parent.child).  pNode is the deepest.  Perform as many fixes as we can
1849             // with the locks we've got.
1850
1851             // We've already fixed the height for pNode, but it might still be outside
1852             // our allowable balance range.  In that case a simple fix_height_locked()
1853             // won't help.
1854             int nodeBalance = hLR - hR;
1855             if ( nodeBalance < -1 || nodeBalance > 1 ) {
1856                 // we need another rotation at pNode
1857                 m_stat.onRotateAfterRightRotation();
1858                 return pNode;
1859             }
1860
1861             // we've fixed balance and height damage for pNode, now handle
1862             // extra-routing node damage
1863             if ( (pLRight == nullptr || hR == 0) && !pNode->is_valued(memory_model::memory_order_relaxed)) {
1864                 // we need to remove pNode and then repair
1865                 m_stat.onRemoveAfterRightRotation();
1866                 return pNode;
1867             }
1868
1869             // we've already fixed the height at pLeft, do we need a rotation here?
1870             int leftBalance = hLL - hNode;
1871             if ( leftBalance < -1 || leftBalance > 1 ) {
1872                 m_stat.onRotateAfterRightRotation();
1873                 return pLeft;
1874             }
1875
1876             // pLeft might also have routing node damage (if pLeft.left was null)
1877             if ( hLL == 0 && !pLeft->is_valued(memory_model::memory_order_acquire) ) {
1878                 m_stat.onDamageAfterRightRotation();
1879                 return pLeft;
1880             }
1881
1882             // try to fix the parent height while we've still got the lock
1883             return fix_height_locked( pParent );
1884         }
1885
1886         node_type * rotate_left_locked( node_type * pParent, node_type * pNode, int hL, node_type * pRight, node_type * pRLeft, int hRL, int hRR )
1887         {
1888             version_type nodeVersion = pNode->version( memory_model::memory_order_relaxed );
1889             node_type * pParentLeft = child( pParent, left_child, memory_model::memory_order_relaxed );
1890
1891             begin_change( pNode, nodeVersion );
1892
1893             // fix up pNode links, careful to be compatible with concurrent traversal for all but pNode
1894             pNode->m_pRight.store( pRLeft, memory_model::memory_order_release );
1895             if ( pRLeft != nullptr )
1896                 pRLeft->parent( pNode, memory_model::memory_order_release );
1897
1898             atomics::atomic_thread_fence( memory_model::memory_order_release );
1899
1900             pRight->m_pLeft.store( pNode, memory_model::memory_order_release );
1901             pNode->parent( pRight, memory_model::memory_order_release );
1902
1903             atomics::atomic_thread_fence( memory_model::memory_order_release );
1904
1905             if ( pParentLeft == pNode )
1906                 pParent->m_pLeft.store( pRight, memory_model::memory_order_release );
1907             else {
1908                 assert( pParent->m_pRight.load( memory_model::memory_order_relaxed ) == pNode );
1909                 pParent->m_pRight.store( pRight, memory_model::memory_order_release );
1910             }
1911             pRight->parent( pParent, memory_model::memory_order_release );
1912
1913             atomics::atomic_thread_fence( memory_model::memory_order_release );
1914
1915             // fix up heights
1916             int hNode = 1 + std::max( hL, hRL );
1917             set_height( pNode, hNode, memory_model::memory_order_release );
1918             set_height( pRight, 1 + std::max( hNode, hRR ), memory_model::memory_order_release);
1919
1920             end_change( pNode, nodeVersion );
1921             m_stat.onRotateLeft();
1922
1923             int nodeBalance = hRL - hL;
1924             if ( nodeBalance < -1 || nodeBalance > 1 ) {
1925                 m_stat.onRotateAfterLeftRotation();
1926                 return pNode;
1927             }
1928
1929             if ( (pRLeft == nullptr || hL == 0) && !pNode->is_valued(memory_model::memory_order_relaxed) ) {
1930                 m_stat.onRemoveAfterLeftRotation();
1931                 return pNode;
1932             }
1933
1934             int rightBalance = hRR - hNode;
1935             if ( rightBalance < -1 || rightBalance > 1 ) {
1936                 m_stat.onRotateAfterLeftRotation();
1937                 return pRight;
1938             }
1939
1940             if ( hRR == 0 && !pRight->is_valued(memory_model::memory_order_acquire) ) {
1941                 m_stat.onDamageAfterLeftRotation();
1942                 return pRight;
1943             }
1944
1945             return fix_height_locked( pParent );
1946         }
1947
1948         node_type * rotate_right_over_left_locked( node_type * pParent, node_type * pNode, node_type * pLeft, int hR, int hLL, node_type * pLRight, int hLRL )
1949         {
1950             version_type nodeVersion = pNode->version( memory_model::memory_order_relaxed );
1951             version_type leftVersion = pLeft->version( memory_model::memory_order_acquire );
1952
1953             node_type * pPL = child( pParent, left_child, memory_model::memory_order_relaxed );
1954             node_type * pLRL = child( pLRight, left_child, memory_model::memory_order_acquire );
1955             node_type * pLRR = child( pLRight, right_child, memory_model::memory_order_acquire );
1956             int hLRR = height_null( pLRR, memory_model::memory_order_acquire );
1957
1958             begin_change( pNode, nodeVersion );
1959             begin_change( pLeft, leftVersion );
1960
1961             // fix up pNode links, careful about the order!
1962             pNode->m_pLeft.store( pLRR, memory_model::memory_order_release );
1963             if ( pLRR != nullptr )
1964                 pLRR->parent( pNode, memory_model::memory_order_release );
1965
1966             pLeft->m_pRight.store( pLRL, memory_model::memory_order_release );
1967             if ( pLRL != nullptr )
1968                 pLRL->parent( pLeft, memory_model::memory_order_release );
1969
1970             pLRight->m_pLeft.store( pLeft, memory_model::memory_order_release );
1971             pLeft->parent( pLRight, memory_model::memory_order_release );
1972
1973             pLRight->m_pRight.store( pNode, memory_model::memory_order_release );
1974             pNode->parent( pLRight, memory_model::memory_order_release );
1975
1976             if ( pPL == pNode )
1977                 pParent->m_pLeft.store( pLRight, memory_model::memory_order_release );
1978             else {
1979                 assert( child( pParent, right_child, memory_model::memory_order_relaxed ) == pNode );
1980                 pParent->m_pRight.store( pLRight, memory_model::memory_order_release );
1981             }
1982             pLRight->parent( pParent, memory_model::memory_order_release );
1983
1984             // fix up heights
1985             int hNode = 1 + std::max( hLRR, hR );
1986             set_height( pNode, hNode, memory_model::memory_order_release );
1987             int hLeft = 1 + std::max( hLL, hLRL );
1988             set_height( pLeft, hLeft, memory_model::memory_order_release );
1989             set_height( pLRight, 1 + std::max( hLeft, hNode ), memory_model::memory_order_release);
1990
1991             end_change( pNode, nodeVersion );
1992             end_change( pLeft, leftVersion );
1993             m_stat.onRotateRightOverLeft();
1994
1995             // caller should have performed only a single rotation if pLeft was going
1996             // to end up damaged
1997             assert( hLL - hLRL <= 1 && hLRL - hLL <= 1 );
1998             assert( !((hLL == 0 || pLRL == nullptr) && !pLeft->is_valued( memory_model::memory_order_acquire )));
1999
2000             // We have damaged pParent, pLR (now parent.child), and pNode (now
2001             // parent.child.right).  pNode is the deepest.  Perform as many fixes as we
2002             // can with the locks we've got.
2003
2004             // We've already fixed the height for pNode, but it might still be outside
2005             // our allowable balance range.  In that case a simple fix_height_locked()
2006             // won't help.
2007             int nodeBalance = hLRR - hR;
2008             if ( nodeBalance < -1 || nodeBalance > 1 ) {
2009                 // we need another rotation at pNode
2010                 m_stat.onRotateAfterRLRotation();
2011                 return pNode;
2012             }
2013
2014             // pNode might also be damaged by being an unnecessary routing node
2015             if ( (pLRR == nullptr || hR == 0) && !pNode->is_valued( memory_model::memory_order_relaxed )) {
2016                 // repair involves splicing out pNode and maybe more rotations
2017                 m_stat.onRemoveAfterRLRotation();
2018                 return pNode;
2019             }
2020
2021             // we've already fixed the height at pLRight, do we need a rotation here?
2022             int balanceLR = hLeft - hNode;
2023             if ( balanceLR < -1 || balanceLR > 1 ) {
2024                 m_stat.onRotateAfterRLRotation();
2025                 return pLRight;
2026             }
2027
2028             // try to fix the parent height while we've still got the lock
2029             return fix_height_locked( pParent );
2030         }
2031
2032         node_type * rotate_left_over_right_locked( node_type * pParent, node_type * pNode, int hL, node_type * pRight, node_type * pRLeft, int hRR, int hRLR )
2033         {
2034             version_type nodeVersion = pNode->version( memory_model::memory_order_relaxed );
2035             version_type rightVersion = pRight->version( memory_model::memory_order_acquire );
2036
2037             node_type * pPL = child( pParent, left_child, memory_model::memory_order_relaxed );
2038             node_type * pRLL = child( pRLeft, left_child, memory_model::memory_order_acquire );
2039             node_type * pRLR = child( pRLeft, right_child, memory_model::memory_order_acquire );
2040             int hRLL = height_null( pRLL, memory_model::memory_order_acquire );
2041
2042             begin_change( pNode, nodeVersion );
2043             begin_change( pRight, rightVersion );
2044
2045             // fix up pNode links, careful about the order!
2046             pNode->m_pRight.store( pRLL, memory_model::memory_order_release );
2047             if ( pRLL != nullptr )
2048                 pRLL->parent( pNode, memory_model::memory_order_release );
2049
2050             pRight->m_pLeft.store( pRLR, memory_model::memory_order_release );
2051             if ( pRLR != nullptr )
2052                 pRLR->parent( pRight, memory_model::memory_order_release );
2053
2054             pRLeft->m_pRight.store( pRight, memory_model::memory_order_release );
2055             pRight->parent( pRLeft, memory_model::memory_order_release );
2056
2057             pRLeft->m_pLeft.store( pNode, memory_model::memory_order_release );
2058             pNode->parent( pRLeft, memory_model::memory_order_release );
2059
2060             if ( pPL == pNode )
2061                 pParent->m_pLeft.store( pRLeft, memory_model::memory_order_release );
2062             else {
2063                 assert( pParent->m_pRight.load( memory_model::memory_order_relaxed ) == pNode );
2064                 pParent->m_pRight.store( pRLeft, memory_model::memory_order_release );
2065             }
2066             pRLeft->parent( pParent, memory_model::memory_order_release );
2067
2068             // fix up heights
2069             int hNode = 1 + std::max( hL, hRLL );
2070             set_height( pNode, hNode, memory_model::memory_order_release );
2071             int hRight = 1 + std::max( hRLR, hRR );
2072             set_height( pRight, hRight, memory_model::memory_order_release );
2073             set_height( pRLeft, 1 + std::max( hNode, hRight ), memory_model::memory_order_release);
2074
2075             end_change( pNode, nodeVersion );
2076             end_change( pRight, rightVersion );
2077             m_stat.onRotateLeftOverRight();
2078
2079             assert( hRR - hRLR <= 1 && hRLR - hRR <= 1 );
2080
2081             int nodeBalance = hRLL - hL;
2082             if ( nodeBalance < -1 || nodeBalance > 1 ) {
2083                 m_stat.onRotateAfterLRRotation();
2084                 return pNode;
2085             }
2086
2087             if ( (pRLL == nullptr || hL == 0) && !pNode->is_valued(memory_model::memory_order_relaxed) ) {
2088                 m_stat.onRemoveAfterLRRotation();
2089                 return pNode;
2090             }
2091
2092             int balRL = hRight - hNode;
2093             if ( balRL < -1 || balRL > 1 ) {
2094                 m_stat.onRotateAfterLRRotation();
2095                 return pRLeft;
2096             }
2097
2098             return fix_height_locked( pParent );
2099         }
2100
2101         //@endcond
2102     };
2103 }} // namespace cds::container
2104
2105 #endif // #ifndef CDSLIB_CONTAINER_IMPL_BRONSON_AVLTREE_MAP_RCU_H