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 = memory_model::memory_order_relaxed )
 156         {
 157             return pNode->child( nDir ).load( order );
 158         }
 159
 160         static node_type * parent( node_type * pNode, atomics::memory_order order = memory_model::memory_order_relaxed )
 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         //@cond
 299         template <typename K>
 300         std::pair<bool, bool> ensure( K const& key, mapped_type pVal )
 301         {
 302             return update( key, pVal, true );
 303         }
 304
 305         //@endcond
 306
 307         /// Delete \p key from the map
 308         /**
 309             RCU \p synchronize() method can be called. RCU should not be locked.
 310
 311             Return \p true if \p key is found and deleted, \p false otherwise
 312         */
 313         template <typename K>
 314         bool erase( K const& key )
 315         {
 316             return do_remove(
 317                 key,
 318                 key_comparator(),
 319                 []( key_type const&, mapped_type pVal, rcu_disposer& disp ) -> bool { disp.dispose_value( pVal ); return true; }
 320             );
 321         }
 322
 323         /// Deletes the item from the map using \p pred predicate for searching
 324         /**
 325             The function is an analog of \p erase(K const&)
 326             but \p pred is used for key comparing.
 327             \p Less functor has the interface like \p std::less.
 328             \p Less must imply the same element order as the comparator used for building the map.
 329         */
 330         template <typename K, typename Less>
 331         bool erase_with( K const& key, Less pred )
 332         {
 333             CDS_UNUSED( pred );
 334             return do_remove(
 335                 key,
 336                 cds::opt::details::make_comparator_from_less<Less>(),
 337                 []( key_type const&, mapped_type pVal, rcu_disposer& disp ) -> bool { disp.dispose_value( pVal ); return true;  }
 338             );
 339         }
 340
 341         /// Delete \p key from the map
 342         /**
 343             The function searches an item with key \p key, calls \p f functor
 344             and deletes the item. If \p key is not found, the functor is not called.
 345
 346             The functor \p Func interface:
 347             \code
 348             struct extractor {
 349                 void operator()( key_type const& key, std::remove_pointer<mapped_type>::type& val) { ... }
 350             };
 351             \endcode
 352
 353             RCU \p synchronize method can be called. RCU should not be locked.
 354
 355             Return \p true if key is found and deleted, \p false otherwise
 356         */
 357         template <typename K, typename Func>
 358         bool erase( K const& key, Func f )
 359         {
 360             return do_remove(
 361                 key,
 362                 key_comparator(),
 363                 [&f]( key_type const& key, mapped_type pVal, rcu_disposer& disp ) -> bool {
 364                     assert( pVal );
 365                     f( key, *pVal );
 366                     disp.dispose_value(pVal);
 367                     return true;
 368                 }
 369             );
 370         }
 371
 372         /// Deletes the item from the map using \p pred predicate for searching
 373         /**
 374             The function is an analog of \p erase(K const&, Func)
 375             but \p pred is used for key comparing.
 376             \p Less functor has the interface like \p std::less.
 377             \p Less must imply the same element order as the comparator used for building the map.
 378         */
 379         template <typename K, typename Less, typename Func>
 380         bool erase_with( K const& key, Less pred, Func f )
 381         {
 382             CDS_UNUSED( pred );
 383             return do_remove(
 384                 key,
 385                 cds::opt::details::make_comparator_from_less<Less>(),
 386                 [&f]( key_type const& key, mapped_type pVal, rcu_disposer& disp ) -> bool {
 387                     assert( pVal );
 388                     f( key, *pVal );
 389                     disp.dispose_value(pVal);
 390                     return true;
 391                 }
 392             );
 393         }
 394
 395         /// Extracts a value with minimal key from the map
 396         /**
 397             Returns \p exempt_ptr to the leftmost item.
 398             If the tree is empty, returns empty \p exempt_ptr.
 399
 400             Note that the function returns only the value for minimal key.
 401             To retrieve its key use \p extract_min( Func ) member function.
 402
 403             @note Due the concurrent nature of the map, the function extracts <i>nearly</i> minimum key.
 404             It means that the function gets leftmost leaf of the tree and tries to unlink it.
 405             During unlinking, a concurrent thread may insert an item with key less than leftmost item's key.
 406             So, the function returns the item with minimum key at the moment of tree traversing.
 407
 408             RCU \p synchronize method can be called. RCU should NOT be locked.
 409             The function does not free the item.
 410             The deallocator will be implicitly invoked when the returned object is destroyed or when
 411             its \p release() member function is called.
 412         */
 413         exempt_ptr extract_min()
 414         {
 415             return exempt_ptr(do_extract_min( []( key_type const& ) {}));
 416         }
 417
 418         /// Extracts minimal key key and corresponding value
 419         /**
 420             Returns \p exempt_ptr to the leftmost item.
 421             If the tree is empty, returns empty \p exempt_ptr.
 422
 423             \p Func functor is used to store minimal key.
 424             \p Func has the following signature:
 425             \code
 426             struct functor {
 427                 void operator()( key_type const& key );
 428             };
 429             \endcode
 430             If the tree is empty, \p f is not called.
 431             Otherwise, is it called with minimal key, the pointer to corresponding value is returned
 432             as \p exempt_ptr.
 433
 434             @note Due the concurrent nature of the map, the function extracts <i>nearly</i> minimum key.
 435             It means that the function gets leftmost leaf of the tree and tries to unlink it.
 436             During unlinking, a concurrent thread may insert an item with key less than leftmost item's key.
 437             So, the function returns the item with minimum key at the moment of tree traversing.
 438
 439             RCU \p synchronize method can be called. RCU should NOT be locked.
 440             The function does not free the item.
 441             The deallocator will be implicitly invoked when the returned object is destroyed or when
 442             its \p release() member function is called.
 443         */
 444         template <typename Func>
 445         exempt_ptr extract_min( Func f )
 446         {
 447             return exempt_ptr(do_extract_min( [&f]( key_type const& key ) { f(key); }));
 448         }
 449
 450         /// Extracts minimal key key and corresponding value
 451         /**
 452             This function is a shortcut for the following call:
 453             \code
 454             key_type key;
 455             exempt_ptr xp = theTree.extract_min( [&key]( key_type const& k ) { key = k; } );
 456             \endode
 457             \p key_type should be copy-assignable. The copy of minimal key
 458             is returned in \p min_key argument.
 459         */
 460         typename std::enable_if< std::is_copy_assignable<key_type>::value, exempt_ptr >::type
 461         extract_min_key( key_type& min_key )
 462         {
 463             return exempt_ptr(do_extract_min( [&min_key]( key_type const& key ) { min_key = key; }));
 464         }
 465
 466         /// Extracts a value with maximal key from the tree
 467         /**
 468             Returns \p exempt_ptr pointer to the rightmost item.
 469             If the set is empty, returns empty \p exempt_ptr.
 470
 471             Note that the function returns only the value for maximal key.
 472             To retrieve its key use \p extract_max( Func ) member function.
 473
 474             @note Due the concurrent nature of the map, the function extracts <i>nearly</i> maximal key.
 475             It means that the function gets rightmost leaf of the tree and tries to unlink it.
 476             During unlinking, a concurrent thread may insert an item with key great than leftmost item's key.
 477             So, the function returns the item with maximum key at the moment of tree traversing.
 478
 479             RCU \p synchronize method can be called. RCU should NOT be locked.
 480             The function does not free the item.
 481             The deallocator will be implicitly invoked when the returned object is destroyed or when
 482             its \p release() is called.
 483         */
 484         exempt_ptr extract_max()
 485         {
 486             return exempt_ptr(do_extract_max( []( key_type const& ) {}));
 487         }
 488
 489         /// Extracts the maximal key and corresponding value
 490         /**
 491             Returns \p exempt_ptr pointer to the rightmost item.
 492             If the set is empty, returns empty \p exempt_ptr.
 493
 494             \p Func functor is used to store maximal key.
 495             \p Func has the following signature:
 496             \code
 497                 struct functor {
 498                     void operator()( key_type const& key );
 499                 };
 500             \endcode
 501             If the tree is empty, \p f is not called.
 502             Otherwise, is it called with maximal key, the pointer to corresponding value is returned
 503             as \p exempt_ptr.
 504
 505             @note Due the concurrent nature of the map, the function extracts <i>nearly</i> maximal key.
 506             It means that the function gets rightmost leaf of the tree and tries to unlink it.
 507             During unlinking, a concurrent thread may insert an item with key great than leftmost item's key.
 508             So, the function returns the item with maximum key at the moment of tree traversing.
 509
 510             RCU \p synchronize method can be called. RCU should NOT be locked.
 511             The function does not free the item.
 512             The deallocator will be implicitly invoked when the returned object is destroyed or when
 513             its \p release() is called.
 514         */
 515         template <typename Func>
 516         exempt_ptr extract_max( Func f )
 517         {
 518             return exempt_ptr(do_extract_max( [&f]( key_type const& key ) { f(key); }));
 519         }
 520
 521         /// Extracts the maximal key and corresponding value
 522         /**
 523             This function is a shortcut for the following call:
 524             \code
 525                 key_type key;
 526                 exempt_ptr xp = theTree.extract_max( [&key]( key_type const& k ) { key = k; } );
 527             \endode
 528             \p key_type should be copy-assignable. The copy of maximal key
 529             is returned in \p max_key argument.
 530         */
 531         typename std::enable_if< std::is_copy_assignable<key_type>::value, exempt_ptr >::type
 532         extract_max_key( key_type& max_key )
 533         {
 534             return exempt_ptr(do_extract_max( [&max_key]( key_type const& key ) { max_key = key; }));
 535         }
 536
 537         /// Extracts an item from the map
 538         /**
 539             The function searches an item with key equal to \p key in the tree,
 540             unlinks it, and returns \p exempt_ptr pointer to a value found.
 541             If \p key is not found the function returns an empty \p exempt_ptr.
 542
 543             RCU \p synchronize method can be called. RCU should NOT be locked.
 544             The function does not destroy the value found.
 545             The disposer will be implicitly invoked when the returned object is destroyed or when
 546             its \p release() member function is called.
 547         */
 548         template <typename Q>
 549         exempt_ptr extract( Q const& key )
 550         {
 551             return exempt_ptr(do_extract( key ));
 552         }
 553
 554
 555         /// Extracts an item from the map using \p pred for searching
 556         /**
 557             The function is an analog of \p extract(Q const&)
 558             but \p pred is used for key compare.
 559             \p Less has the interface like \p std::less.
 560             \p pred must imply the same element order as the comparator used for building the tree.
 561         */
 562         template <typename Q, typename Less>
 563         exempt_ptr extract_with( Q const& key, Less pred )
 564         {
 565             return exempt_ptr(do_extract_with( key, pred ));
 566         }
 567
 568         /// Find the key \p key
 569         /**
 570             The function searches the item with key equal to \p key and calls the functor \p f for item found.
 571             The interface of \p Func functor is:
 572             \code
 573             struct functor {
 574                 void operator()( key_type const& key, mapped_type& item );
 575             };
 576             \endcode
 577             where \p item is the item found.
 578             The functor is called under node-level lock.
 579
 580             The function applies RCU lock internally.
 581
 582             The function returns \p true if \p key is found, \p false otherwise.
 583         */
 584         template <typename K, typename Func>
 585         bool find( K const& key, Func f )
 586         {
 587             return do_find( key, key_comparator(),
 588                 [&f]( node_type * pNode ) -> bool {
 589                     assert( pNode != nullptr );
 590                     mapped_type pVal = pNode->m_pValue.load( memory_model::memory_order_relaxed );
 591                     if ( pVal ) {
 592                         f( pNode->m_key, *pVal );
 593                         return true;
 594                     }
 595                     return false;
 596                 }
 597             );
 598         }
 599
 600         /// Finds the key \p val using \p pred predicate for searching
 601         /**
 602             The function is an analog of \p find(K const&, Func)
 603             but \p pred is used for key comparing.
 604             \p Less functor has the interface like \p std::less.
 605             \p Less must imply the same element order as the comparator used for building the map.
 606         */
 607         template <typename K, typename Less, typename Func>
 608         bool find_with( K const& key, Less pred, Func f )
 609         {
 610             CDS_UNUSED( pred );
 611             return do_find( key, cds::opt::details::make_comparator_from_less<Less>(),
 612                 [&f]( node_type * pNode ) -> bool {
 613                     assert( pNode != nullptr );
 614                     mapped_type pVal = pNode->m_pValue.load( memory_model::memory_order_relaxed );
 615                     if ( pVal ) {
 616                         f( pNode->m_key, *pVal );
 617                         return true;
 618                     }
 619                     return false;
 620                 }
 621             );
 622         }
 623
 624         /// Find the key \p key
 625         /**
 626             The function searches the item with key equal to \p key
 627             and returns \p true if it is found, and \p false otherwise.
 628
 629             The function applies RCU lock internally.
 630         */
 631         template <typename K>
 632         bool find( K const& key )
 633         {
 634             return do_find( key, key_comparator(), []( node_type * ) -> bool { return true; });
 635         }
 636
 637         /// Finds the key \p val using \p pred predicate for searching
 638         /**
 639             The function is an analog of \p find(K const&)
 640             but \p pred is used for key comparing.
 641             \p Less functor has the interface like \p std::less.
 642             \p Less must imply the same element order as the comparator used for building the map.
 643         */
 644         template <typename K, typename Less>
 645         bool find_with( K const& key, Less pred )
 646         {
 647             CDS_UNUSED( pred );
 648             return do_find( key, cds::opt::details::make_comparator_from_less<Less>(), []( node_type * ) -> bool { return true; } );
 649         }
 650
 651         /// Clears the tree (thread safe, not atomic)
 652         /**
 653             The function unlink all items from the tree.
 654             The function is thread safe but not atomic: in multi-threaded environment with parallel insertions
 655             this sequence
 656             \code
 657             set.clear();
 658             assert( set.empty() );
 659             \endcode
 660             the assertion could be raised.
 661
 662             For each node the \ref disposer will be called after unlinking.
 663
 664             RCU \p synchronize method can be called. RCU should not be locked.
 665         */
 666         void clear()
 667         {
 668             while ( extract_min() );
 669         }
 670
 671         /// Clears the tree (not thread safe)
 672         /**
 673             This function is not thread safe and may be called only when no other thread deals with the tree.
 674             The function is used in the tree destructor.
 675         */
 676         void unsafe_clear()
 677         {
 678             clear(); // temp solution
 679             //TODO
 680         }
 681
 682         /// Checks if the map is empty
 683         bool empty() const
 684         {
 685             return m_Root.m_pRight.load( memory_model::memory_order_relaxed ) == nullptr;
 686         }
 687
 688         /// Returns item count in the map
 689         /**
 690             Only leaf nodes containing user data are counted.
 691
 692             The value returned depends on item counter type provided by \p Traits template parameter.
 693             If it is \p atomicity::empty_item_counter this function always returns 0.
 694
 695             The function is not suitable for checking the tree emptiness, use \p empty()
 696             member function for this purpose.
 697         */
 698         size_t size() const
 699         {
 700             return m_ItemCounter;
 701         }
 702
 703         /// Returns const reference to internal statistics
 704         stat const& statistics() const
 705         {
 706             return m_stat;
 707         }
 708
 709         /// Returns reference to \p sync_monitor object
 710         sync_monitor& monitor()
 711         {
 712             return m_Monitor;
 713         }
 714         //@cond
 715         sync_monitor const& monitor() const
 716         {
 717             return m_Monitor;
 718         }
 719         //@endcond
 720
 721         /// Checks internal consistency (not atomic, not thread-safe)
 722         /**
 723             The debugging function to check internal consistency of the tree.
 724         */
 725         bool check_consistency() const
 726         {
 727             return check_consistency([]( size_t /*nLevel*/, size_t /*hLeft*/, size_t /*hRight*/ ){} );
 728         }
 729
 730         /// Checks internal consistency (not atomic, not thread-safe)
 731         /**
 732             The debugging function to check internal consistency of the tree.
 733             The functor \p Func is called if a violation of internal tree structure
 734             is found:
 735             \code
 736             struct functor {
 737                 void operator()( size_t nLevel, size_t hLeft, size_t hRight );
 738             };
 739             \endcode
 740             where
 741             - \p nLevel - the level where the violation is found
 742             - \p hLeft - the height of left subtree
 743             - \p hRight - the height of right subtree
 744
 745             The functor is called for each violation found.
 746         */
 747         template <typename Func>
 748         bool check_consistency( Func f ) const
 749         {
 750             node_type * pChild = child( m_pRoot, right_child );
 751             if ( pChild ) {
 752                 size_t nErrors = 0;
 753                 do_check_consistency( pChild, 1, f, nErrors );
 754                 return nErrors == 0;
 755             }
 756             return true;
 757         }
 758
 759     protected:
 760         //@cond
 761         template <typename Func>
 762         size_t do_check_consistency( node_type * pNode, size_t nLevel, Func f, size_t& nErrors ) const
 763         {
 764             if ( pNode ) {
 765                 key_comparator cmp;
 766                 node_type * pLeft = child( pNode, left_child );
 767                 node_type * pRight = child( pNode, right_child );
 768                 if ( pLeft && cmp( pLeft->m_key, pNode->m_key ) > 0 )
 769                     ++nErrors;
 770                 if (  pRight && cmp( pNode->m_key, pRight->m_key ) > 0 )
 771                     ++nErrors;
 772
 773                 size_t hLeft = do_check_consistency( pLeft, nLevel + 1, f, nErrors );
 774                 size_t hRight = do_check_consistency( pRight, nLevel + 1, f, nErrors );
 775
 776                 if ( hLeft >= hRight ) {
 777                     if ( hLeft - hRight > 1 ) {
 778                         f( nLevel, hLeft, hRight );
 779                         ++nErrors;
 780                     }
 781                     return hLeft;
 782                 }
 783                 else {
 784                     if ( hRight - hLeft > 1 ) {
 785                         f( nLevel, hLeft, hRight );
 786                         ++nErrors;
 787                     }
 788                     return hRight;
 789                 }
 790             }
 791             return 0;
 792         }
 793
 794         template <typename Q, typename Compare, typename Func>
 795         bool do_find( Q& key, Compare cmp, Func f ) const
 796         {
 797             find_result result;
 798             {
 799                 rcu_lock l;
 800                 result = try_find( key, cmp, f, m_pRoot, right_child, 0 );
 801             }
 802             assert( result != find_result::retry );
 803             return result == find_result::found;
 804         }
 805
 806         template <typename K, typename Compare, typename Func>
 807         int do_update( K const& key, Compare cmp, Func funcUpdate, int nFlags )
 808         {
 809             check_deadlock_policy::check();
 810
 811             rcu_disposer removed_list;
 812             {
 813                 rcu_lock l;
 814                 return try_update_root( key, cmp, nFlags, funcUpdate, removed_list );
 815             }
 816         }
 817
 818         template <typename K, typename Compare, typename Func>
 819         bool do_remove( K const& key, Compare cmp, Func func )
 820         {
 821             // Func must return true if the value was disposed
 822             //              or false if the value was extracted
 823
 824             check_deadlock_policy::check();
 825
 826             rcu_disposer removed_list;
 827             {
 828                 rcu_lock l;
 829                 return try_remove_root( key, cmp, func, removed_list );
 830             }
 831         }
 832
 833         template <typename Func>
 834         mapped_type do_extract_min( Func f )
 835         {
 836             mapped_type pExtracted = nullptr;
 837             do_extract_minmax(
 838                 left_child,
 839                 [&pExtracted, &f]( key_type const& key, mapped_type pVal, rcu_disposer& ) -> bool { f( key ); pExtracted = pVal; return false; }
 840             );
 841             return pExtracted;
 842         }
 843
 844         template <typename Func>
 845         mapped_type do_extract_max( Func f )
 846         {
 847             mapped_type pExtracted = nullptr;
 848             do_extract_minmax(
 849                 right_child,
 850                 [&pExtracted, &f]( key_type const& key, mapped_type pVal, rcu_disposer& ) -> bool { f( key ); pExtracted = pVal; return false; }
 851             );
 852             return pExtracted;
 853         }
 854
 855         template <typename Func>
 856         void do_extract_minmax( int nDir, Func func )
 857         {
 858             check_deadlock_policy::check();
 859
 860             rcu_disposer removed_list;
 861             {
 862                 rcu_lock l;
 863
 864                 while ( true ) {
 865                     int result;
 866
 867                     // get right child of root
 868                     node_type * pChild = child( m_pRoot, right_child, memory_model::memory_order_acquire );
 869                     if ( pChild ) {
 870                         version_type nChildVersion = pChild->version( memory_model::memory_order_acquire );
 871                         if ( nChildVersion & node_type::shrinking ) {
 872                             m_stat.onRemoveRootWaitShrinking();
 873                             pChild->template wait_until_shrink_completed<back_off>( memory_model::memory_order_relaxed );
 874                             result = update_flags::retry;
 875                         }
 876                         else if ( pChild == child( m_pRoot, right_child, memory_model::memory_order_acquire )) {
 877                             result = try_extract_minmax( nDir, func, m_pRoot, pChild, nChildVersion, removed_list );
 878                         }
 879                         else
 880                             result = update_flags::retry;
 881                     }
 882                     else
 883                         return;
 884
 885                     if ( result == update_flags::retry )
 886                         m_stat.onRemoveRetry();
 887                     else
 888                         return;
 889                 }
 890             }
 891         }
 892
 893         template <typename Q>
 894         mapped_type do_extract( Q const& key )
 895         {
 896             mapped_type pExtracted = nullptr;
 897             do_remove(
 898                 key,
 899                 key_comparator(),
 900                 [&pExtracted]( key_type const&, mapped_type pVal, rcu_disposer& ) -> bool { pExtracted = pVal; return false; }
 901             );
 902             return pExtracted;
 903         }
 904
 905         template <typename Q, typename Less>
 906         mapped_type do_extract_with( Q const& key, Less pred )
 907         {
 908             CDS_UNUSED( pred );
 909             mapped_type pExtracted = nullptr;
 910             do_remove(
 911                 key,
 912                 cds::opt::details::make_comparator_from_less<Less>(),
 913                 [&pExtracted]( key_type const&, mapped_type pVal, rcu_disposer& ) -> bool { pExtracted = pVal; return false; }
 914             );
 915             return pExtracted;
 916         }
 917         //@endcond
 918
 919     private:
 920         //@cond
 921         static int height( node_type * pNode, atomics::memory_order order = memory_model::memory_order_relaxed )
 922         {
 923             assert( pNode );
 924             return pNode->m_nHeight.load( order );
 925         }
 926         static void set_height( node_type * pNode, int h, atomics::memory_order order = memory_model::memory_order_relaxed )
 927         {
 928             assert( pNode );
 929             pNode->m_nHeight.store( h, order );
 930         }
 931         static int height_null( node_type * pNode, atomics::memory_order order = memory_model::memory_order_relaxed )
 932         {
 933             return pNode ? height( pNode, order ) : 0;
 934         }
 935
 936         static CDS_CONSTEXPR int const c_stackSize = 64;
 937
 938         template <typename Q, typename Compare, typename Func>
 939         find_result try_find( Q const& key, Compare cmp, Func f, node_type * pNode, int nDir, version_type nVersion ) const
 940         {
 941             assert( gc::is_locked() );
 942             assert( pNode );
 943
 944             struct stack_record
 945             {
 946                 node_type * pNode;
 947                 version_type nVersion;
 948                 int nDir;
 949             };
 950
 951             stack_record stack[c_stackSize];
 952             int pos = 0;
 953             stack[0].pNode = pNode;
 954             stack[0].nVersion = nVersion;
 955             stack[0].nDir = nDir;
 956
 957             while ( pos >= 0 ) {
 958                 pNode = stack[pos].pNode;
 959                 nVersion = stack[pos].nVersion;
 960                 nDir = stack[pos].nDir;
 961
 962                 while ( true ) {
 963                     node_type * pChild = child( pNode, nDir );
 964                     if ( !pChild ) {
 965                         if ( pNode->version(memory_model::memory_order_acquire) != nVersion ) {
 966                             --pos;
 967                             m_stat.onFindRetry();
 968                             break; // retry
 969                         }
 970                         m_stat.onFindFailed();
 971                         return find_result::not_found;
 972                     }
 973
 974                     int nCmp = cmp( key, pChild->m_key );
 975                     if ( nCmp == 0 ) {
 976                         if ( pChild->is_valued( memory_model::memory_order_relaxed ) ) {
 977                             // key found
 978                             node_scoped_lock l( m_Monitor, *pChild );
 979                             if ( child(pNode, nDir) == pChild ) {
 980                                 if ( pChild->is_valued( memory_model::memory_order_relaxed )) {
 981                                     if ( f( pChild ) ) {
 982                                         m_stat.onFindSuccess();
 983                                         return find_result::found;
 984                                     }
 985                                 }
 986                             }
 987                             else {
 988                                 m_stat.onFindRetry();
 989                                 continue;
 990                             }
 991                         }
 992                         m_stat.onFindFailed();
 993                         return find_result::not_found;
 994                     }
 995                     else {
 996                         version_type nChildVersion = pChild->version( memory_model::memory_order_acquire );
 997                         if ( nChildVersion & node_type::shrinking ) {
 998                             m_stat.onFindWaitShrinking();
 999                             pChild->template wait_until_shrink_completed<back_off>( memory_model::memory_order_relaxed );
1000
1001                             if ( pNode->version(memory_model::memory_order_acquire) != nVersion ) {
1002                                 --pos;
1003                                 m_stat.onFindRetry();
1004                                 break; // retry
1005                             }
1006                         }
1007                         else if ( nChildVersion != node_type::unlinked && child( pNode, nDir ) == pChild )
1008                         {
1009                             if ( pNode->version(memory_model::memory_order_acquire) != nVersion ) {
1010                                 --pos;
1011                                 m_stat.onFindRetry();
1012                                 break; // retry
1013                             }
1014
1015                             ++pos;
1016                             assert(pos < c_stackSize);
1017                             stack[pos].pNode = pChild;
1018                             stack[pos].nVersion = nChildVersion;
1019                             stack[pos].nDir = nCmp;
1020                             break; // child iteration
1021                         }
1022
1023                         if ( pNode->version(memory_model::memory_order_acquire) != nVersion ) {
1024                             --pos;
1025                             m_stat.onFindRetry();
1026                             break; // retry
1027                         }
1028                     }
1029                     m_stat.onFindRetry();
1030                 }
1031             }
1032             return find_result::retry;
1033         }
1034
1035 #if 0
1036         template <typename Q, typename Compare, typename Func>
1037         find_result try_find( Q const& key, Compare cmp, Func f, node_type * pNode, int nDir, version_type nVersion ) const
1038         {
1039             assert( gc::is_locked() );
1040             assert( pNode );
1041
1042             while ( true ) {
1043                 node_type * pChild = child( pNode, nDir );
1044                 if ( !pChild ) {
1045                     if ( pNode->version( memory_model::memory_order_acquire ) != nVersion )
1046                         return find_result::retry;
1047
1048                     m_stat.onFindFailed();
1049                     return find_result::not_found;
1050                 }
1051
1052                 int nCmp = cmp( key, pChild->m_key );
1053                 if ( nCmp == 0 ) {
1054                     if ( pChild->is_valued( memory_model::memory_order_relaxed ) ) {
1055                         // key found
1056                         node_scoped_lock l( m_Monitor, *pChild );
1057                         if ( pChild->is_valued( memory_model::memory_order_relaxed )) {
1058                             if ( f( pChild ) ) {
1059                                 m_stat.onFindSuccess();
1060                                 return find_result::found;
1061                             }
1062                         }
1063                     }
1064
1065                     m_stat.onFindFailed();
1066                     return find_result::not_found;
1067                 }
1068
1069                 version_type nChildVersion = pChild->version( memory_model::memory_order_acquire );
1070                 if ( nChildVersion & node_type::shrinking ) {
1071                     m_stat.onFindWaitShrinking();
1072                     pChild->template wait_until_shrink_completed<back_off>( memory_model::memory_order_relaxed );
1073
1074                     if ( pNode->version( memory_model::memory_order_acquire ) != nVersion )
1075                         return find_result::retry;
1076                 }
1077                 else if ( nChildVersion != node_type::unlinked && child( pNode, nDir ) == pChild )
1078                 {
1079                     if ( pNode->version(memory_model::memory_order_acquire) != nVersion )
1080                         return find_result::retry;
1081
1082                     find_result found = try_find( key, cmp, f, pChild, nCmp, nChildVersion );
1083                     if ( found != find_result::retry )
1084                         return found;
1085                 }
1086
1087                 if ( pNode->version( memory_model::memory_order_acquire ) != nVersion )
1088                     return find_result::retry;
1089
1090                 m_stat.onFindRetry();
1091             }
1092         }
1093 #endif
1094
1095         template <typename K, typename Compare, typename Func>
1096         int try_update_root( K const& key, Compare cmp, int nFlags, Func funcUpdate, rcu_disposer& disp )
1097         {
1098             assert( gc::is_locked() );
1099
1100             while ( true ) {
1101                 int result;
1102
1103                 // get right child of root
1104                 node_type * pChild = child( m_pRoot, right_child, memory_model::memory_order_acquire );
1105                 if ( pChild ) {
1106                     version_type nChildVersion = pChild->version( memory_model::memory_order_acquire );
1107                     if ( nChildVersion & node_type::shrinking ) {
1108                         m_stat.onUpdateRootWaitShrinking();
1109                         pChild->template wait_until_shrink_completed<back_off>( memory_model::memory_order_relaxed );
1110                         result = update_flags::retry;
1111                     }
1112                     else if ( pChild == child( m_pRoot, right_child, memory_model::memory_order_acquire ))
1113                         result = try_update( key, cmp, nFlags, funcUpdate, pChild, nChildVersion, disp );
1114                     else
1115                         result = update_flags::retry;
1116                 }
1117                 else {
1118                     // the tree is empty
1119                     if ( nFlags & update_flags::allow_insert ) {
1120                         // insert into tree as right child of the root
1121                         {
1122                             node_scoped_lock l( m_Monitor, *m_pRoot );
1123                             if ( child( m_pRoot, right_child, memory_model::memory_order_acquire ) != nullptr ) {
1124                                 result = update_flags::retry;
1125                                 continue;
1126                             }
1127
1128                             node_type * pNew = alloc_node( key, 1, 0, m_pRoot, nullptr, nullptr );
1129                             mapped_type pVal = funcUpdate( pNew );
1130                             assert( pVal != nullptr );
1131                             pNew->m_pValue.store( pVal, memory_model::memory_order_release );
1132
1133                             m_pRoot->child( pNew, right_child, memory_model::memory_order_relaxed );
1134                             set_height( m_pRoot, 2 );
1135                         }
1136
1137                         ++m_ItemCounter;
1138                         m_stat.onInsertSuccess();
1139                         return update_flags::result_inserted;
1140                     }
1141
1142                     return update_flags::failed;
1143                 }
1144
1145                 if ( result != update_flags::retry )
1146                     return result;
1147             }
1148         }
1149
1150         template <typename K, typename Compare, typename Func>
1151         bool try_remove_root( K const& key, Compare cmp, Func func, rcu_disposer& disp )
1152         {
1153             assert( gc::is_locked() );
1154
1155             while ( true ) {
1156                 int result;
1157
1158                 // get right child of root
1159                 node_type * pChild = child( m_pRoot, right_child, memory_model::memory_order_acquire );
1160                 if ( pChild ) {
1161                     version_type nChildVersion = pChild->version( memory_model::memory_order_acquire );
1162                     if ( nChildVersion & node_type::shrinking ) {
1163                         m_stat.onRemoveRootWaitShrinking();
1164                         pChild->template wait_until_shrink_completed<back_off>( memory_model::memory_order_relaxed );
1165                         result = update_flags::retry;
1166                     }
1167                     else if ( pChild == child( m_pRoot, right_child, memory_model::memory_order_acquire )) {
1168                         result = try_remove( key, cmp, func, m_pRoot, pChild, nChildVersion, disp );
1169                     }
1170                     else
1171                         result = update_flags::retry;
1172                 }
1173                 else
1174                     return false;
1175
1176                 if ( result == update_flags::retry )
1177                     m_stat.onRemoveRetry();
1178                 else
1179                     return result == update_flags::result_removed;
1180             }
1181         }
1182
1183         template <typename K, typename Compare, typename Func>
1184         int try_update( K const& key, Compare cmp, int nFlags, Func funcUpdate, node_type * pNode, version_type nVersion, rcu_disposer& disp )
1185         {
1186             assert( gc::is_locked() );
1187             assert( nVersion != node_type::unlinked );
1188
1189             struct stack_record
1190             {
1191                 node_type * pNode;
1192                 version_type nVersion;
1193             };
1194
1195             stack_record stack[c_stackSize];
1196             int pos = 0;
1197             stack[0].pNode = pNode;
1198             stack[0].nVersion = nVersion;
1199
1200             while ( pos >= 0 ) {
1201                 pNode = stack[pos].pNode;
1202                 nVersion = stack[pos].nVersion;
1203
1204                 int nCmp = cmp( key, pNode->m_key );
1205                 if ( nCmp == 0 ) {
1206                     int result = try_update_node( nFlags, funcUpdate, pNode, nVersion, disp );
1207                     if ( result != update_flags::retry )
1208                         return result;
1209                     --pos;
1210                     m_stat.onUpdateRetry();
1211                     continue;
1212                 }
1213
1214                 while ( true ) {
1215                     node_type * pChild = child( pNode, nCmp );
1216                     if ( pNode->version(memory_model::memory_order_acquire) != nVersion ) {
1217                         --pos;
1218                         m_stat.onUpdateRetry();
1219                         break;
1220                     }
1221
1222                     if ( pChild == nullptr ) {
1223                         // insert new node
1224                         if ( nFlags & update_flags::allow_insert ) {
1225                             int result = try_insert_node( key, funcUpdate, pNode, nCmp, nVersion, disp );
1226                             if ( result != update_flags::retry )
1227                                 return result;
1228                             --pos;
1229                             m_stat.onUpdateRetry();
1230                             break;
1231                         }
1232                         else
1233                             return update_flags::failed;
1234                     }
1235                     else {
1236                         // update child
1237                         version_type nChildVersion = pChild->version( memory_model::memory_order_acquire );
1238                         if ( nChildVersion & node_type::shrinking ) {
1239                             m_stat.onUpdateWaitShrinking();
1240                             pChild->template wait_until_shrink_completed<back_off>( memory_model::memory_order_relaxed );
1241                             // retry
1242                         }
1243                         else if ( pChild == child( pNode, nCmp )) {
1244                             // this second read is important, because it is protected by nChildVersion
1245
1246                             // validate the read that our caller took to get to node
1247                             if ( pNode->version( memory_model::memory_order_acquire ) != nVersion ) {
1248                                 --pos;
1249                                 m_stat.onUpdateRetry();
1250                                 break; // retry
1251                             }
1252                             // At this point we know that the traversal our parent took to get to node is still valid.
1253                             // The recursive implementation will validate the traversal from node to
1254                             // child, so just prior to the node nVersion validation both traversals were definitely okay.
1255                             // This means that we are no longer vulnerable to node shrinks, and we don't need
1256                             // to validate node version any more.
1257                             ++pos;
1258                             assert( pos < c_stackSize );
1259                             stack[pos].pNode = pChild;
1260                             stack[pos].nVersion = nChildVersion;
1261                             assert( nChildVersion != node_type::unlinked );
1262                             break; // child iteration
1263                         }
1264                         m_stat.onUpdateRetry();
1265                     }
1266                 }
1267             }
1268             return update_flags::retry;
1269         }
1270
1271 #if 0
1272         template <typename K, typename Compare, typename Func>
1273         int try_update( K const& key, Compare cmp, int nFlags, Func funcUpdate, node_type * pNode, version_type nVersion, rcu_disposer& disp )
1274         {
1275             assert( gc::is_locked() );
1276             assert( nVersion != node_type::unlinked );
1277
1278             int nCmp = cmp( key, pNode->m_key );
1279             if ( nCmp == 0 )
1280                 return try_update_node( nFlags, funcUpdate, pNode, nVersion, disp );
1281
1282             while ( true ) {
1283                 int result;
1284                 node_type * pChild = child( pNode, nCmp );
1285                 if ( pNode->version(memory_model::memory_order_acquire) != nVersion )
1286                     return update_flags::retry;
1287
1288                 if ( pChild == nullptr ) {
1289                     // insert new node
1290                     if ( nFlags & update_flags::allow_insert )
1291                         result = try_insert_node( key, funcUpdate, pNode, nCmp, nVersion, disp );
1292                     else
1293                         result = update_flags::failed;
1294                 }
1295                 else {
1296                     // update child
1297                     version_type nChildVersion = pChild->version( memory_model::memory_order_acquire );
1298                     if ( nChildVersion & node_type::shrinking ) {
1299                         m_stat.onUpdateWaitShrinking();
1300                         pChild->template wait_until_shrink_completed<back_off>( memory_model::memory_order_relaxed );
1301                         // retry
1302                         result = update_flags::retry;
1303                     }
1304                     else if ( pChild == child( pNode, nCmp )) {
1305                         // this second read is important, because it is protected by nChildVersion
1306
1307                         // validate the read that our caller took to get to node
1308                         if ( pNode->version( memory_model::memory_order_acquire ) != nVersion )
1309                             return update_flags::retry;
1310
1311                         // At this point we know that the traversal our parent took to get to node is still valid.
1312                         // The recursive implementation will validate the traversal from node to
1313                         // child, so just prior to the node nVersion validation both traversals were definitely okay.
1314                         // This means that we are no longer vulnerable to node shrinks, and we don't need
1315                         // to validate node version any more.
1316                         result = try_update( key, cmp, nFlags, funcUpdate, pChild, nChildVersion, disp );
1317                     }
1318                     else
1319                         result = update_flags::retry;
1320                 }
1321
1322                 if ( result == update_flags::retry ) {
1323                     if ( pNode->version( memory_model::memory_order_acquire ) != nVersion )
1324                         return update_flags::retry;
1325                     m_stat.onUpdateRetry();
1326                 }
1327                 else
1328                     return result;
1329             }
1330         }
1331 #endif
1332
1333         template <typename K, typename Compare, typename Func>
1334         int try_remove( K const& key, Compare cmp, Func func, node_type * pParent, node_type * pNode, version_type nVersion, rcu_disposer& disp )
1335         {
1336             assert( gc::is_locked() );
1337             assert( nVersion != node_type::unlinked );
1338
1339             struct stack_record
1340             {
1341                 node_type * pParent;
1342                 node_type * pNode;
1343                 version_type nVersion;
1344             };
1345
1346             stack_record stack[c_stackSize];
1347             int pos = 0;
1348             stack[0].pParent = pParent;
1349             stack[0].pNode = pNode;
1350             stack[0].nVersion = nVersion;
1351
1352             while ( pos >= 0 ) {
1353                 pParent = stack[pos].pParent;
1354                 pNode = stack[pos].pNode;
1355                 nVersion = stack[pos].nVersion;
1356
1357                 int nCmp = cmp( key, pNode->m_key );
1358                 if ( nCmp == 0 ) {
1359                     int result = try_remove_node( pParent, pNode, nVersion, func, disp );
1360                     if ( result != update_flags::retry )
1361                         return result;
1362                     --pos;
1363                     m_stat.onRemoveRetry();
1364                     continue;
1365                 }
1366
1367                 while ( true ) {
1368                     node_type * pChild = child( pNode, nCmp );
1369                     if ( pNode->version(memory_model::memory_order_acquire) != nVersion ) {
1370                         --pos;
1371                         m_stat.onRemoveRetry();
1372                         break;
1373                     }
1374
1375                     if ( pChild == nullptr )
1376                         return update_flags::failed;
1377
1378                     // update child
1379                     version_type nChildVersion = pChild->version( memory_model::memory_order_acquire );
1380                     if ( nChildVersion & node_type::shrinking ) {
1381                         m_stat.onRemoveWaitShrinking();
1382                         pChild->template wait_until_shrink_completed<back_off>( memory_model::memory_order_relaxed );
1383                         // retry
1384                     }
1385                     else if ( pChild == child( pNode, nCmp )) {
1386                         // this second read is important, because it is protected by nChildVersion
1387
1388                         // validate the read that our caller took to get to node
1389                         if ( pNode->version(memory_model::memory_order_acquire) != nVersion ) {
1390                             --pos;
1391                             m_stat.onRemoveRetry();
1392                             break;
1393                         }
1394
1395                         // At this point we know that the traversal our parent took to get to node is still valid.
1396                         // The recursive implementation will validate the traversal from node to
1397                         // child, so just prior to the node nVersion validation both traversals were definitely okay.
1398                         // This means that we are no longer vulnerable to node shrinks, and we don't need
1399                         // to validate node version any more.
1400                         ++pos;
1401                         assert( pos < c_stackSize );
1402                         stack[pos].pParent = pNode;
1403                         stack[pos].pNode = pChild;
1404                         stack[pos].nVersion = nChildVersion;
1405                         break; // child iteration
1406                     }
1407                     m_stat.onRemoveRetry();
1408                 }
1409             }
1410             return update_flags::retry;
1411         }
1412
1413 #if 0
1414         template <typename K, typename Compare, typename Func>
1415         int try_remove( K const& key, Compare cmp, Func func, node_type * pParent, node_type * pNode, version_type nVersion, rcu_disposer& disp )
1416         {
1417             assert( gc::is_locked() );
1418             assert( nVersion != node_type::unlinked );
1419
1420             int nCmp = cmp( key, pNode->m_key );
1421             if ( nCmp == 0 )
1422                 return try_remove_node( pParent, pNode, nVersion, func, disp );
1423
1424             while ( true ) {
1425                 int result;
1426
1427                 node_type * pChild = child( pNode, nCmp );
1428                 if ( pNode->version(memory_model::memory_order_acquire) != nVersion )
1429                     return update_flags::retry;
1430
1431                 if ( pChild == nullptr )
1432                     return update_flags::failed;
1433                 else {
1434                     // update child
1435                     result = update_flags::retry;
1436                     version_type nChildVersion = pChild->version( memory_model::memory_order_acquire );
1437                     if ( nChildVersion & node_type::shrinking ) {
1438                         m_stat.onRemoveWaitShrinking();
1439                         pChild->template wait_until_shrink_completed<back_off>( memory_model::memory_order_relaxed );
1440                         // retry
1441                     }
1442                     else if ( pChild == child( pNode, nCmp )) {
1443                         // this second read is important, because it is protected by nChildVersion
1444
1445                         // validate the read that our caller took to get to node
1446                         if ( pNode->version( memory_model::memory_order_acquire ) != nVersion )
1447                             return update_flags::retry;
1448
1449                         // At this point we know that the traversal our parent took to get to node is still valid.
1450                         // The recursive implementation will validate the traversal from node to
1451                         // child, so just prior to the node nVersion validation both traversals were definitely okay.
1452                         // This means that we are no longer vulnerable to node shrinks, and we don't need
1453                         // to validate node version any more.
1454                         result = try_remove( key, cmp, func, pNode, pChild, nChildVersion, disp );
1455                     }
1456                     else
1457                         result = update_flags::retry;
1458                 }
1459
1460                 if ( result == update_flags::retry ) {
1461                     if ( pNode->version( memory_model::memory_order_acquire ) != nVersion )
1462                         return update_flags::retry;
1463                     m_stat.onRemoveRetry();
1464                 }
1465                 else
1466                     return result;
1467             }
1468         }
1469 #endif
1470
1471         template <typename Func>
1472         int try_extract_minmax( int nDir, Func func, node_type * pParent, node_type * pNode, version_type nVersion, rcu_disposer& disp )
1473         {
1474             assert( gc::is_locked() );
1475             assert( nVersion != node_type::unlinked );
1476
1477             struct stack_record
1478             {
1479                 node_type * pParent;
1480                 node_type * pNode;
1481                 version_type nVersion;
1482             };
1483
1484             stack_record stack[c_stackSize];
1485             int pos = 0;
1486             stack[0].pParent = pParent;
1487             stack[0].pNode = pNode;
1488             stack[0].nVersion = nVersion;
1489
1490             while ( pos >= 0 ) {
1491                 pParent = stack[pos].pParent;
1492                 pNode = stack[pos].pNode;
1493                 nVersion = stack[pos].nVersion;
1494
1495                 while ( true ) {
1496                     node_type * pChild = child( pNode, nDir );
1497                     if ( pNode->version(memory_model::memory_order_acquire) != nVersion ) {
1498                         --pos;
1499                         m_stat.onRemoveRetry();
1500                         break;
1501                     }
1502
1503                     if ( pChild == nullptr ) {
1504                         // Found min/max
1505                         assert(pNode->is_valued( memory_model::memory_order_relaxed ));
1506                         int result = try_remove_node( pParent, pNode, nVersion, func, disp );
1507                         if ( result != update_flags::retry )
1508                             return result;
1509                         --pos;
1510                         m_stat.onRemoveRetry();
1511                         break;
1512                     }
1513
1514                     version_type nChildVersion = pChild->version( memory_model::memory_order_acquire );
1515                     if ( nChildVersion & node_type::shrinking ) {
1516                         m_stat.onRemoveWaitShrinking();
1517                         pChild->template wait_until_shrink_completed<back_off>( memory_model::memory_order_relaxed );
1518                         // retry
1519                     }
1520                     else if ( pChild == child( pNode, nDir )) {
1521                         // this second read is important, because it is protected by nChildVersion
1522
1523                         // validate the read that our caller took to get to node
1524                         if ( pNode->version( memory_model::memory_order_acquire ) != nVersion ) {
1525                             --pos;
1526                             m_stat.onRemoveRetry();
1527                             break;
1528                         }
1529
1530                         // At this point we know that the traversal our parent took to get to node is still valid.
1531                         // The recursive implementation will validate the traversal from node to
1532                         // child, so just prior to the node nVersion validation both traversals were definitely okay.
1533                         // This means that we are no longer vulnerable to node shrinks, and we don't need
1534                         // to validate node version any more.
1535                         ++pos;
1536                         assert( pos < c_stackSize );
1537                         stack[pos].pParent = pNode;
1538                         stack[pos].pNode = pChild;
1539                         stack[pos].nVersion = nChildVersion;
1540                         break; // child iteration
1541                     }
1542                     m_stat.onRemoveRetry();
1543                 }
1544             }
1545             return update_flags::retry;
1546         }
1547
1548 #if 0
1549         template <typename Func>
1550         int try_extract_minmax( int nDir, Func func, node_type * pParent, node_type * pNode, version_type nVersion, rcu_disposer& disp )
1551         {
1552             assert( gc::is_locked() );
1553             assert( nVersion != node_type::unlinked );
1554
1555             while ( true ) {
1556                 int result;
1557                 node_type * pChild = child( pNode, nDir );
1558                 if ( pNode->version(memory_model::memory_order_acquire) != nVersion )
1559                     return update_flags::retry;
1560
1561                 if ( pChild == nullptr ) {
1562                     // Found min/max
1563                     assert(pNode->is_valued( memory_model::memory_order_relaxed ));
1564                     return try_remove_node( pParent, pNode, nVersion, func, disp );
1565                 }
1566                 else {
1567                     //result = update_flags::retry;
1568                     version_type nChildVersion = pChild->version( memory_model::memory_order_acquire );
1569                     if ( nChildVersion & node_type::shrinking ) {
1570                         m_stat.onRemoveWaitShrinking();
1571                         pChild->template wait_until_shrink_completed<back_off>( memory_model::memory_order_relaxed );
1572                         // retry
1573                         result = update_flags::retry;
1574                     }
1575                     else if ( pChild == child( pNode, nDir )) {
1576                         // this second read is important, because it is protected by nChildVersion
1577
1578                         // validate the read that our caller took to get to node
1579                         if ( pNode->version( memory_model::memory_order_acquire ) != nVersion )
1580                             return update_flags::retry;
1581
1582                         // At this point we know that the traversal our parent took to get to node is still valid.
1583                         // The recursive implementation will validate the traversal from node to
1584                         // child, so just prior to the node nVersion validation both traversals were definitely okay.
1585                         // This means that we are no longer vulnerable to node shrinks, and we don't need
1586                         // to validate node version any more.
1587                         result = try_extract_minmax( nDir, func, pNode, pChild, nChildVersion, disp );
1588                     }
1589                     else
1590                         result = update_flags::retry;
1591                 }
1592
1593                 if ( result == update_flags::retry ) {
1594                     if ( pNode->version( memory_model::memory_order_acquire ) != nVersion )
1595                         return update_flags::retry;
1596                     m_stat.onRemoveRetry();
1597                 }
1598                 else
1599                     return result;
1600             }
1601         }
1602 #endif
1603
1604         template <typename K, typename Func>
1605         int try_insert_node( K const& key, Func funcUpdate, node_type * pNode, int nDir, version_type nVersion, rcu_disposer& disp )
1606         {
1607             node_type * pNew;
1608
1609             auto fnCreateNode = [&funcUpdate]( node_type * pNew ) {
1610                 mapped_type pVal = funcUpdate( pNew );
1611                 assert( pVal != nullptr );
1612                 pNew->m_pValue.store( pVal, memory_model::memory_order_relaxed );
1613             };
1614
1615             if ( c_bRelaxedInsert ) {
1616                 if ( pNode->version( memory_model::memory_order_acquire ) != nVersion
1617                      || child( pNode, nDir ) != nullptr )
1618                 {
1619                     m_stat.onInsertRetry();
1620                     return update_flags::retry;
1621                 }
1622
1623                 fnCreateNode( pNew = alloc_node( key, 1, 0, pNode, nullptr, nullptr ));
1624             }
1625
1626             node_type * pDamaged;
1627             {
1628                 assert( pNode != nullptr );
1629                 node_scoped_lock l( m_Monitor, *pNode );
1630
1631                 if ( pNode->version( memory_model::memory_order_acquire ) != nVersion
1632                      || child( pNode, nDir ) != nullptr )
1633                 {
1634                     if ( c_bRelaxedInsert ) {
1635                         mapped_type pVal = pNew->m_pValue.load( memory_model::memory_order_relaxed );
1636                         pNew->m_pValue.store( nullptr, memory_model::memory_order_relaxed );
1637                         free_value( pVal );
1638                         free_node( pNew );
1639                         m_stat.onRelaxedInsertFailed();
1640                     }
1641
1642                     m_stat.onInsertRetry();
1643                     return update_flags::retry;
1644                 }
1645
1646                 if ( !c_bRelaxedInsert )
1647                     fnCreateNode( pNew = alloc_node( key, 1, 0, pNode, nullptr, nullptr ));
1648
1649                 pNode->child( pNew, nDir, memory_model::memory_order_relaxed );
1650                 pDamaged = fix_height_locked( pNode );
1651             }
1652
1653             ++m_ItemCounter;
1654             m_stat.onInsertSuccess();
1655
1656             if ( pDamaged ) {
1657                 fix_height_and_rebalance( pDamaged, disp );
1658                 m_stat.onInsertRebalanceRequired();
1659             }
1660
1661             return update_flags::result_inserted;
1662         }
1663
1664         template <typename Func>
1665         int try_update_node( int nFlags, Func funcUpdate, node_type * pNode, version_type nVersion, rcu_disposer& disp )
1666         {
1667             mapped_type pOld;
1668             bool bInserted;
1669             assert( pNode != nullptr );
1670             {
1671                 node_scoped_lock l( m_Monitor, *pNode );
1672
1673                 if ( pNode->version(memory_model::memory_order_acquire) != nVersion )
1674                     return update_flags::retry;
1675
1676                 if ( pNode->is_unlinked( memory_model::memory_order_relaxed )) {
1677                     m_stat.onUpdateUnlinked();
1678                     return update_flags::retry;
1679                 }
1680
1681                 if ( pNode->is_valued( memory_model::memory_order_relaxed ) && !(nFlags & update_flags::allow_update) ) {
1682                     m_stat.onInsertFailed();
1683                     return update_flags::failed;
1684                 }
1685
1686                 pOld = pNode->value( memory_model::memory_order_relaxed );
1687                 bInserted = pOld == nullptr;
1688                 mapped_type pVal = funcUpdate( pNode );
1689                 if ( pVal == pOld )
1690                     pOld = nullptr;
1691                 else {
1692                     assert( pVal != nullptr );
1693                     pNode->m_pValue.store( pVal, memory_model::memory_order_relaxed );
1694                 }
1695             }
1696
1697             if ( pOld ) {
1698                 disp.dispose_value(pOld);
1699                 m_stat.onDisposeValue();
1700             }
1701
1702             if ( bInserted ) {
1703                 m_stat.onInsertSuccess();
1704                 return update_flags::result_inserted;
1705             }
1706
1707             m_stat.onUpdateSuccess();
1708             return update_flags::result_updated;
1709         }
1710
1711         template <typename Func>
1712         int try_remove_node( node_type * pParent, node_type * pNode, version_type nVersion, Func func, rcu_disposer& disp )
1713         {
1714             assert( pParent != nullptr );
1715             assert( pNode != nullptr );
1716
1717             if ( !pNode->is_valued( memory_model::memory_order_relaxed ) )
1718                 return update_flags::failed;
1719
1720             if ( child( pNode, left_child ) == nullptr || child( pNode, right_child ) == nullptr ) {
1721                 // pNode can be replaced with its child
1722
1723                 node_type * pDamaged;
1724                 mapped_type pOld;
1725                 {
1726                     node_scoped_lock lp( m_Monitor, *pParent );
1727                     if ( pParent->is_unlinked( memory_model::memory_order_relaxed ) || parent( pNode ) != pParent )
1728                         return update_flags::retry;
1729
1730                     {
1731                         node_scoped_lock ln( m_Monitor, *pNode );
1732                         if ( pNode->version( memory_model::memory_order_acquire ) != nVersion )
1733                             return update_flags::retry;
1734
1735                         pOld = pNode->value( memory_model::memory_order_relaxed );
1736                         if ( !pOld )
1737                             return update_flags::failed;
1738
1739                         if ( !try_unlink_locked( pParent, pNode, disp ))
1740                             return update_flags::retry;
1741                     }
1742                     pDamaged = fix_height_locked( pParent );
1743                 }
1744
1745                 --m_ItemCounter;
1746                 if ( func( pNode->m_key, pOld, disp ))   // calls pOld disposer inside
1747                     m_stat.onDisposeValue();
1748                 else
1749                     m_stat.onExtractValue();
1750
1751                 if ( pDamaged ) {
1752                     fix_height_and_rebalance( pDamaged, disp );
1753                     m_stat.onRemoveRebalanceRequired();
1754                 }
1755             }
1756             else {
1757                 // pNode is an internal with two children
1758
1759                 mapped_type pOld;
1760                 {
1761                     node_scoped_lock ln( m_Monitor, *pNode );
1762                     pOld = pNode->value( memory_model::memory_order_relaxed );
1763                     if ( pNode->version( memory_model::memory_order_acquire ) != nVersion )
1764                         return update_flags::retry;
1765                     if ( !pOld )
1766                         return update_flags::failed;
1767
1768                     pNode->m_pValue.store( nullptr, memory_model::memory_order_relaxed );
1769                 }
1770
1771                 --m_ItemCounter;
1772                 if ( func( pNode->m_key, pOld, disp ))  // calls pOld disposer inside
1773                     m_stat.onDisposeValue();
1774                 else
1775                     m_stat.onExtractValue();
1776             }
1777             return update_flags::result_removed;
1778         }
1779
1780         bool try_unlink_locked( node_type * pParent, node_type * pNode, rcu_disposer& disp )
1781         {
1782             // pParent and pNode must be locked
1783             assert( !pParent->is_unlinked(memory_model::memory_order_relaxed) );
1784
1785             node_type * pParentLeft = child( pParent, left_child );
1786             node_type * pParentRight = child( pParent, right_child );
1787             if ( pNode != pParentLeft && pNode != pParentRight ) {
1788                 // node is no longer a child of parent
1789                 return false;
1790             }
1791
1792             assert( !pNode->is_unlinked( memory_model::memory_order_relaxed ));
1793             assert( pParent == parent( pNode ));
1794
1795             node_type * pLeft = child( pNode, left_child );
1796             node_type * pRight = child( pNode, right_child );
1797             if ( pLeft != nullptr && pRight != nullptr ) {
1798                 // splicing is no longer possible
1799                 return false;
1800             }
1801             node_type * pSplice = pLeft ? pLeft : pRight;
1802
1803             if ( pParentLeft == pNode )
1804                 pParent->m_pLeft.store( pSplice, memory_model::memory_order_relaxed );
1805             else
1806                 pParent->m_pRight.store( pSplice, memory_model::memory_order_relaxed );
1807
1808             if ( pSplice )
1809                 pSplice->parent( pParent, memory_model::memory_order_relaxed );
1810
1811             // Mark the node as unlinked
1812             pNode->version( node_type::unlinked, memory_model::memory_order_release );
1813
1814             // The value will be disposed by calling function
1815             pNode->m_pValue.store( nullptr, memory_model::memory_order_relaxed );
1816
1817             disp.dispose( pNode );
1818             m_stat.onDisposeNode();
1819
1820             return true;
1821         }
1822
1823         //@endcond
1824
1825     private: // rotations
1826         //@cond
1827         int estimate_node_condition( node_type * pNode )
1828         {
1829             node_type * pLeft = child( pNode, left_child );
1830             node_type * pRight = child( pNode, right_child );
1831
1832             if ( (pLeft == nullptr || pRight == nullptr) && !pNode->is_valued( memory_model::memory_order_relaxed ))
1833                 return unlink_required;
1834
1835             int h = height( pNode );
1836             int hL = height_null( pLeft );
1837             int hR = height_null( pRight );
1838
1839             int hNew = 1 + std::max( hL, hR );
1840             int nBalance = hL - hR;
1841
1842             if ( nBalance < -1 || nBalance > 1 )
1843                 return rebalance_required;
1844
1845             return h != hNew ? hNew : nothing_required;
1846         }
1847
1848         node_type * fix_height( node_type * pNode )
1849         {
1850             assert( pNode != nullptr );
1851             node_scoped_lock l( m_Monitor, *pNode );
1852             return fix_height_locked( pNode );
1853         }
1854
1855         node_type * fix_height_locked( node_type * pNode )
1856         {
1857             // pNode must be locked!!!
1858             int h = estimate_node_condition( pNode );
1859             switch ( h ) {
1860                 case rebalance_required:
1861                 case unlink_required:
1862                     return pNode;
1863                 case nothing_required:
1864                     return nullptr;
1865                 default:
1866                     set_height( pNode, h );
1867                     return parent( pNode );
1868             }
1869         }
1870
1871         void fix_height_and_rebalance( node_type * pNode, rcu_disposer& disp )
1872         {
1873             while ( pNode && parent( pNode )) {
1874                 int nCond = estimate_node_condition( pNode );
1875                 if ( nCond == nothing_required || pNode->is_unlinked( memory_model::memory_order_relaxed ) )
1876                     return;
1877
1878                 if ( nCond != unlink_required && nCond != rebalance_required )
1879                     pNode = fix_height( pNode );
1880                 else {
1881                     node_type * pParent = parent( pNode );
1882                     assert( pParent != nullptr );
1883                     {
1884                         node_scoped_lock lp( m_Monitor, *pParent );
1885                         if ( !pParent->is_unlinked( memory_model::memory_order_relaxed ) && parent( pNode ) == pParent ) {
1886                             node_scoped_lock ln( m_Monitor, *pNode );
1887                             pNode = rebalance_locked( pParent, pNode, disp );
1888                         }
1889                     }
1890                 }
1891             }
1892         }
1893
1894         node_type * rebalance_locked( node_type * pParent, node_type * pNode, rcu_disposer& disp )
1895         {
1896             // pParent and pNode should be locked.
1897             // Returns a damaged node, or nullptr if no more rebalancing is necessary
1898             assert( parent( pNode ) == pParent );
1899
1900             node_type * pLeft = child( pNode, left_child );
1901             node_type * pRight = child( pNode, right_child );
1902
1903             if ( (pLeft == nullptr || pRight == nullptr) && !pNode->is_valued( memory_model::memory_order_relaxed )) {
1904                 if ( try_unlink_locked( pParent, pNode, disp ))
1905                     return fix_height_locked( pParent );
1906                 else {
1907                     // retry needed for pNode
1908                     return pNode;
1909                 }
1910             }
1911
1912             assert( child( pParent, left_child ) == pNode || child( pParent, right_child ) == pNode );
1913
1914             int h = height( pNode );
1915             int hL = height_null( pLeft );
1916             int hR = height_null( pRight );
1917             int hNew = 1 + std::max( hL, hR );
1918             int balance = hL - hR;
1919
1920             if ( balance > 1 )
1921                 return rebalance_to_right_locked( pParent, pNode, pLeft, hR );
1922             else if ( balance < -1 )
1923                 return rebalance_to_left_locked( pParent, pNode, pRight, hL );
1924             else if ( hNew != h ) {
1925                 set_height( pNode, hNew );
1926
1927                 // pParent is already locked
1928                 return fix_height_locked( pParent );
1929             }
1930             else
1931                 return nullptr;
1932         }
1933
1934         node_type * rebalance_to_right_locked( node_type * pParent, node_type * pNode, node_type * pLeft, int hR )
1935         {
1936             assert( parent( pNode ) == pParent );
1937             assert( child( pParent, left_child ) == pNode || child( pParent, right_child ) == pNode );
1938
1939             // pParent and pNode is locked yet
1940             // pNode->pLeft is too large, we will rotate-right.
1941             // If pLeft->pRight is taller than pLeft->pLeft, then we will first rotate-left pLeft.
1942
1943             {
1944                 assert( pLeft != nullptr );
1945                 node_scoped_lock l( m_Monitor, *pLeft );
1946                 if ( pNode->m_pLeft.load( memory_model::memory_order_relaxed ) != pLeft )
1947                     return pNode; // retry for pNode
1948
1949                 int hL = height( pLeft );
1950                 if ( hL - hR <= 1 )
1951                     return pNode; // retry
1952
1953                 node_type * pLRight = child( pLeft, right_child );
1954                 int hLR = height_null( pLRight );
1955                 node_type * pLLeft = child( pLeft, left_child );
1956                 int hLL = height_null( pLLeft );
1957
1958                 if ( hLL > hLR ) {
1959                     // rotate right
1960                     return rotate_right_locked( pParent, pNode, pLeft, hR, hLL, pLRight, hLR );
1961                 }
1962                 else {
1963                     assert( pLRight != nullptr );
1964                     {
1965                         node_scoped_lock lr( m_Monitor, *pLRight );
1966                         if ( pLeft->m_pRight.load( memory_model::memory_order_relaxed ) != pLRight )
1967                             return pNode; // retry
1968
1969                         hLR = height( pLRight );
1970                         if ( hLL > hLR )
1971                             return rotate_right_locked( pParent, pNode, pLeft, hR, hLL, pLRight, hLR );
1972
1973                         int hLRL = height_null( child( pLRight, left_child ));
1974                         int balance = hLL - hLRL;
1975                         if ( balance >= -1 && balance <= 1 && !((hLL == 0 || hLRL == 0) && !pLeft->is_valued(memory_model::memory_order_relaxed))) {
1976                             // nParent.child.left won't be damaged after a double rotation
1977                             return rotate_right_over_left_locked( pParent, pNode, pLeft, hR, hLL, pLRight, hLRL );
1978                         }
1979                     }
1980
1981                     // focus on pLeft, if necessary pNode will be balanced later
1982                     return rebalance_to_left_locked( pNode, pLeft, pLRight, hLL );
1983                 }
1984             }
1985         }
1986
1987         node_type * rebalance_to_left_locked( node_type * pParent, node_type * pNode, node_type * pRight, int hL )
1988         {
1989             assert( parent( pNode ) == pParent );
1990             assert( child( pParent, left_child ) == pNode || child( pParent, right_child ) == pNode );
1991
1992             // pParent and pNode is locked yet
1993             {
1994                 assert( pRight != nullptr );
1995                 node_scoped_lock l( m_Monitor, *pRight );
1996                 if ( pNode->m_pRight.load( memory_model::memory_order_relaxed ) != pRight )
1997                     return pNode; // retry for pNode
1998
1999                 int hR = height( pRight );
2000                 if ( hL - hR >= -1 )
2001                     return pNode; // retry
2002
2003                 node_type * pRLeft = child( pRight, left_child );
2004                 int hRL = height_null( pRLeft );
2005                 node_type * pRRight = child( pRight, right_child );
2006                 int hRR = height_null( pRRight );
2007                 if ( hRR > hRL )
2008                     return rotate_left_locked( pParent, pNode, hL, pRight, pRLeft, hRL, hRR );
2009
2010                 {
2011                     assert( pRLeft != nullptr );
2012                     node_scoped_lock lrl( m_Monitor, *pRLeft );
2013                     if ( pRight->m_pLeft.load( memory_model::memory_order_relaxed ) != pRLeft )
2014                         return pNode; // retry
2015
2016                     hRL = height( pRLeft );
2017                     if ( hRR >= hRL )
2018                         return rotate_left_locked( pParent, pNode, hL, pRight, pRLeft, hRL, hRR );
2019
2020                     node_type * pRLRight = child( pRLeft, right_child );
2021                     int hRLR = height_null( pRLRight );
2022                     int balance = hRR - hRLR;
2023                     if ( balance >= -1 && balance <= 1 && !((hRR == 0 || hRLR == 0) && !pRight->is_valued( memory_model::memory_order_relaxed )))
2024                          return rotate_left_over_right_locked( pParent, pNode, hL, pRight, pRLeft, hRR, hRLR );
2025                 }
2026                 return rebalance_to_right_locked( pNode, pRight, pRLeft, hRR );
2027             }
2028         }
2029
2030         static void begin_change( node_type * pNode, version_type version )
2031         {
2032             assert(pNode->version(memory_model::memory_order_acquire) == version );
2033             assert( (version & node_type::shrinking) == 0 );
2034             pNode->version( version | node_type::shrinking, memory_model::memory_order_release );
2035         }
2036         static void end_change( node_type * pNode, version_type version )
2037         {
2038             // Clear shrinking and unlinked flags and increment version
2039             pNode->version( (version | node_type::version_flags) + 1, memory_model::memory_order_release );
2040         }
2041
2042         node_type * rotate_right_locked( node_type * pParent, node_type * pNode, node_type * pLeft, int hR, int hLL, node_type * pLRight, int hLR )
2043         {
2044             version_type nodeVersion = pNode->version( memory_model::memory_order_acquire );
2045             node_type * pParentLeft = child( pParent, left_child );
2046
2047             begin_change( pNode, nodeVersion );
2048
2049             pNode->m_pLeft.store( pLRight, memory_model::memory_order_relaxed );
2050             if ( pLRight != nullptr )
2051                 pLRight->parent( pNode, memory_model::memory_order_relaxed  );
2052
2053             atomics::atomic_thread_fence( memory_model::memory_order_release );
2054
2055             pLeft->m_pRight.store( pNode, memory_model::memory_order_relaxed );
2056             pNode->parent( pLeft, memory_model::memory_order_relaxed );
2057
2058             atomics::atomic_thread_fence( memory_model::memory_order_release );
2059
2060             if ( pParentLeft == pNode )
2061                 pParent->m_pLeft.store( pLeft, memory_model::memory_order_relaxed );
2062             else {
2063                 assert( pParent->m_pRight.load( memory_model::memory_order_relaxed ) == pNode );
2064                 pParent->m_pRight.store( pLeft, memory_model::memory_order_relaxed );
2065             }
2066             pLeft->parent( pParent, memory_model::memory_order_relaxed );
2067
2068             atomics::atomic_thread_fence( memory_model::memory_order_release );
2069
2070             // fix up heights links
2071             int hNode = 1 + std::max( hLR, hR );
2072             set_height( pNode, hNode );
2073             set_height( pLeft, 1 + std::max( hLL, hNode ));
2074
2075             end_change( pNode, nodeVersion );
2076             m_stat.onRotateRight();
2077
2078             // We have damaged pParent, pNode (now parent.child.right), and pLeft (now
2079             // parent.child).  pNode is the deepest.  Perform as many fixes as we can
2080             // with the locks we've got.
2081
2082             // We've already fixed the height for pNode, but it might still be outside
2083             // our allowable balance range.  In that case a simple fix_height_locked()
2084             // won't help.
2085             int nodeBalance = hLR - hR;
2086             if ( nodeBalance < -1 || nodeBalance > 1 ) {
2087                 // we need another rotation at pNode
2088                 m_stat.onRotateAfterRightRotation();
2089                 return pNode;
2090             }
2091
2092             // we've fixed balance and height damage for pNode, now handle
2093             // extra-routing node damage
2094             if ( (pLRight == nullptr || hR == 0) && !pNode->is_valued(memory_model::memory_order_relaxed)) {
2095                 // we need to remove pNode and then repair
2096                 m_stat.onRemoveAfterRightRotation();
2097                 return pNode;
2098             }
2099
2100             // we've already fixed the height at pLeft, do we need a rotation here?
2101             int leftBalance = hLL - hNode;
2102             if ( leftBalance < -1 || leftBalance > 1 ) {
2103                 m_stat.onRotateAfterRightRotation();
2104                 return pLeft;
2105             }
2106
2107             // pLeft might also have routing node damage (if pLeft.left was null)
2108             if ( hLL == 0 && !pLeft->is_valued(memory_model::memory_order_relaxed) ) {
2109                 m_stat.onDamageAfterRightRotation();
2110                 return pLeft;
2111             }
2112
2113             // try to fix the parent height while we've still got the lock
2114             return fix_height_locked( pParent );
2115         }
2116
2117         node_type * rotate_left_locked( node_type * pParent, node_type * pNode, int hL, node_type * pRight, node_type * pRLeft, int hRL, int hRR )
2118         {
2119             version_type nodeVersion = pNode->version( memory_model::memory_order_acquire );
2120             node_type * pParentLeft = child( pParent, left_child );
2121
2122             begin_change( pNode, nodeVersion );
2123
2124             // fix up pNode links, careful to be compatible with concurrent traversal for all but pNode
2125             pNode->m_pRight.store( pRLeft, memory_model::memory_order_relaxed );
2126             if ( pRLeft != nullptr )
2127                 pRLeft->parent( pNode, memory_model::memory_order_relaxed );
2128
2129             atomics::atomic_thread_fence( memory_model::memory_order_release );
2130
2131             pRight->m_pLeft.store( pNode, memory_model::memory_order_relaxed );
2132             pNode->parent( pRight, memory_model::memory_order_relaxed );
2133
2134             atomics::atomic_thread_fence( memory_model::memory_order_release );
2135
2136             if ( pParentLeft == pNode )
2137                 pParent->m_pLeft.store( pRight, memory_model::memory_order_relaxed );
2138             else {
2139                 assert( pParent->m_pRight.load( memory_model::memory_order_relaxed ) == pNode );
2140                 pParent->m_pRight.store( pRight, memory_model::memory_order_relaxed );
2141             }
2142             pRight->parent( pParent, memory_model::memory_order_relaxed );
2143
2144             atomics::atomic_thread_fence( memory_model::memory_order_release );
2145
2146             // fix up heights
2147             int hNode = 1 + std::max( hL, hRL );
2148             set_height( pNode, hNode );
2149             set_height( pRight, 1 + std::max( hNode, hRR ));
2150
2151             end_change( pNode, nodeVersion );
2152             m_stat.onRotateLeft();
2153
2154             int nodeBalance = hRL - hL;
2155             if ( nodeBalance < -1 || nodeBalance > 1 ) {
2156                 m_stat.onRotateAfterLeftRotation();
2157                 return pNode;
2158             }
2159
2160             if ( (pRLeft == nullptr || hL == 0) && !pNode->is_valued(memory_model::memory_order_relaxed) ) {
2161                 m_stat.onRemoveAfterLeftRotation();
2162                 return pNode;
2163             }
2164
2165             int rightBalance = hRR - hNode;
2166             if ( rightBalance < -1 || rightBalance > 1 ) {
2167                 m_stat.onRotateAfterLeftRotation();
2168                 return pRight;
2169             }
2170
2171             if ( hRR == 0 && !pRight->is_valued(memory_model::memory_order_relaxed) ) {
2172                 m_stat.onDamageAfterLeftRotation();
2173                 return pRight;
2174             }
2175
2176             return fix_height_locked( pParent );
2177         }
2178
2179         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 )
2180         {
2181             version_type nodeVersion = pNode->version( memory_model::memory_order_acquire );
2182             version_type leftVersion = pLeft->version( memory_model::memory_order_acquire );
2183
2184             node_type * pPL = child( pParent, left_child );
2185             node_type * pLRL = child( pLRight, left_child );
2186             node_type * pLRR = child( pLRight, right_child );
2187             int hLRR = height_null( pLRR );
2188
2189             begin_change( pNode, nodeVersion );
2190             begin_change( pLeft, leftVersion );
2191
2192             // fix up pNode links, careful about the order!
2193             pNode->m_pLeft.store( pLRR, memory_model::memory_order_relaxed );
2194             if ( pLRR != nullptr )
2195                 pLRR->parent( pNode, memory_model::memory_order_relaxed );
2196             atomics::atomic_thread_fence( memory_model::memory_order_release );
2197
2198             pLeft->m_pRight.store( pLRL, memory_model::memory_order_relaxed );
2199             if ( pLRL != nullptr )
2200                 pLRL->parent( pLeft, memory_model::memory_order_relaxed );
2201             atomics::atomic_thread_fence( memory_model::memory_order_release );
2202
2203             pLRight->m_pLeft.store( pLeft, memory_model::memory_order_relaxed );
2204             pLeft->parent( pLRight, memory_model::memory_order_relaxed );
2205             atomics::atomic_thread_fence( memory_model::memory_order_release );
2206
2207             pLRight->m_pRight.store( pNode, memory_model::memory_order_relaxed );
2208             pNode->parent( pLRight, memory_model::memory_order_relaxed );
2209             atomics::atomic_thread_fence( memory_model::memory_order_release );
2210
2211             if ( pPL == pNode )
2212                 pParent->m_pLeft.store( pLRight, memory_model::memory_order_relaxed );
2213             else {
2214                 assert( child( pParent, right_child ) == pNode );
2215                 pParent->m_pRight.store( pLRight, memory_model::memory_order_relaxed );
2216             }
2217             pLRight->parent( pParent, memory_model::memory_order_relaxed );
2218             atomics::atomic_thread_fence( memory_model::memory_order_release );
2219
2220             // fix up heights
2221             int hNode = 1 + std::max( hLRR, hR );
2222             set_height( pNode, hNode );
2223             int hLeft = 1 + std::max( hLL, hLRL );
2224             set_height( pLeft, hLeft );
2225             set_height( pLRight, 1 + std::max( hLeft, hNode ));
2226
2227             end_change( pNode, nodeVersion );
2228             end_change( pLeft, leftVersion );
2229             m_stat.onRotateRightOverLeft();
2230
2231             // caller should have performed only a single rotation if pLeft was going
2232             // to end up damaged
2233             assert( hLL - hLRL <= 1 && hLRL - hLL <= 1 );
2234             assert( !((hLL == 0 || pLRL == nullptr) && !pLeft->is_valued( memory_model::memory_order_relaxed )));
2235
2236             // We have damaged pParent, pLR (now parent.child), and pNode (now
2237             // parent.child.right).  pNode is the deepest.  Perform as many fixes as we
2238             // can with the locks we've got.
2239
2240             // We've already fixed the height for pNode, but it might still be outside
2241             // our allowable balance range.  In that case a simple fix_height_locked()
2242             // won't help.
2243             int nodeBalance = hLRR - hR;
2244             if ( nodeBalance < -1 || nodeBalance > 1 ) {
2245                 // we need another rotation at pNode
2246                 m_stat.onRotateAfterRLRotation();
2247                 return pNode;
2248             }
2249
2250             // pNode might also be damaged by being an unnecessary routing node
2251             if ( (pLRR == nullptr || hR == 0) && !pNode->is_valued( memory_model::memory_order_relaxed )) {
2252                 // repair involves splicing out pNode and maybe more rotations
2253                 m_stat.onRemoveAfterRLRotation();
2254                 return pNode;
2255             }
2256
2257             // we've already fixed the height at pLRight, do we need a rotation here?
2258             int balanceLR = hLeft - hNode;
2259             if ( balanceLR < -1 || balanceLR > 1 ) {
2260                 m_stat.onRotateAfterRLRotation();
2261                 return pLRight;
2262             }
2263
2264             // try to fix the parent height while we've still got the lock
2265             return fix_height_locked( pParent );
2266         }
2267
2268         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 )
2269         {
2270             version_type nodeVersion = pNode->version( memory_model::memory_order_acquire );
2271             version_type rightVersion = pRight->version( memory_model::memory_order_acquire );
2272
2273             node_type * pPL = child( pParent, left_child );
2274             node_type * pRLL = child( pRLeft, left_child );
2275             node_type * pRLR = child( pRLeft, right_child );
2276             int hRLL = height_null( pRLL );
2277
2278             begin_change( pNode, nodeVersion );
2279             begin_change( pRight, rightVersion );
2280
2281             // fix up pNode links, careful about the order!
2282             pNode->m_pRight.store( pRLL, memory_model::memory_order_relaxed );
2283             if ( pRLL != nullptr )
2284                 pRLL->parent( pNode, memory_model::memory_order_relaxed );
2285             atomics::atomic_thread_fence( memory_model::memory_order_release );
2286
2287             pRight->m_pLeft.store( pRLR, memory_model::memory_order_relaxed );
2288             if ( pRLR != nullptr )
2289                 pRLR->parent( pRight, memory_model::memory_order_relaxed );
2290             atomics::atomic_thread_fence( memory_model::memory_order_release );
2291
2292             pRLeft->m_pRight.store( pRight, memory_model::memory_order_relaxed );
2293             pRight->parent( pRLeft, memory_model::memory_order_relaxed );
2294             atomics::atomic_thread_fence( memory_model::memory_order_release );
2295
2296             pRLeft->m_pLeft.store( pNode, memory_model::memory_order_relaxed );
2297             pNode->parent( pRLeft, memory_model::memory_order_relaxed );
2298             atomics::atomic_thread_fence( memory_model::memory_order_release );
2299
2300             if ( pPL == pNode )
2301                 pParent->m_pLeft.store( pRLeft, memory_model::memory_order_relaxed );
2302             else {
2303                 assert( pParent->m_pRight.load( memory_model::memory_order_relaxed ) == pNode );
2304                 pParent->m_pRight.store( pRLeft, memory_model::memory_order_relaxed );
2305             }
2306             pRLeft->parent( pParent, memory_model::memory_order_relaxed );
2307             atomics::atomic_thread_fence( memory_model::memory_order_release );
2308
2309             // fix up heights
2310             int hNode = 1 + std::max( hL, hRLL );
2311             set_height( pNode, hNode );
2312             int hRight = 1 + std::max( hRLR, hRR );
2313             set_height( pRight, hRight );
2314             set_height( pRLeft, 1 + std::max( hNode, hRight ));
2315
2316             end_change( pNode, nodeVersion );
2317             end_change( pRight, rightVersion );
2318             m_stat.onRotateLeftOverRight();
2319
2320             assert( hRR - hRLR <= 1 && hRLR - hRR <= 1 );
2321
2322             int nodeBalance = hRLL - hL;
2323             if ( nodeBalance < -1 || nodeBalance > 1 ) {
2324                 m_stat.onRotateAfterLRRotation();
2325                 return pNode;
2326             }
2327
2328             if ( (pRLL == nullptr || hL == 0) && !pNode->is_valued(memory_model::memory_order_relaxed) ) {
2329                 m_stat.onRemoveAfterLRRotation();
2330                 return pNode;
2331             }
2332
2333             int balRL = hRight - hNode;
2334             if ( balRL < -1 || balRL > 1 ) {
2335                 m_stat.onRotateAfterLRRotation();
2336                 return pRLeft;
2337             }
2338
2339             return fix_height_locked( pParent );
2340         }
2341
2342         //@endcond
2343     };
2344 }} // namespace cds::container
2345
2346 #endif // #ifndef CDSLIB_CONTAINER_IMPL_BRONSON_AVLTREE_MAP_RCU_H