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