cds/container/impl/bronson_avltree_map_rcu.h

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