cds/container/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_BRONSON_AVLTREE_MAP_RCU_H
  32 #define CDSLIB_CONTAINER_BRONSON_AVLTREE_MAP_RCU_H
  33
  34 #include <functional>
  35 #include <cds/container/impl/bronson_avltree_map_rcu.h>
  36
  37 namespace cds { namespace container {
  38
  39     namespace bronson_avltree {
  40         //@cond
  41         namespace details {
  42             template < class RCU, typename Key, typename T, typename Traits>
  43             struct make_map
  44             {
  45                 typedef Key key_type;
  46                 typedef T mapped_type;
  47                 typedef Traits original_traits;
  48
  49                 typedef cds::details::Allocator< mapped_type, typename original_traits::allocator > cxx_allocator;
  50
  51                 struct traits : public original_traits
  52                 {
  53                     struct disposer {
  54                         void operator()( mapped_type * p ) const
  55                         {
  56                             cxx_allocator().Delete( p );
  57                         }
  58                     };
  59                 };
  60
  61                 // Metafunction result
  62                 typedef BronsonAVLTreeMap< RCU, Key, mapped_type *, traits > type;
  63             };
  64         } // namespace details
  65         //@endcond
  66     } // namespace bronson_avltree
  67
  68     /// Bronson et al AVL-tree (RCU specialization)
  69     /** @ingroup cds_nonintrusive_map
  70         @ingroup cds_nonintrusive_tree
  71         @anchor cds_container_BronsonAVLTreeMap_rcu
  72
  73         Source:
  74             - [2010] N.Bronson, J.Casper, H.Chafi, K.Olukotun "A Practical Concurrent Binary Search Tree"
  75             - <a href="http://github.com/nbronson/snaptree">Java implementation</a>
  76
  77         This is a concurrent AVL tree algorithm that uses hand-over-hand optimistic validation,
  78         a concurrency control mechanism for searching and navigating a binary search tree.
  79         This mechanism minimizes spurious retries when concurrent structural changes cannot
  80         affect the correctness of the search or navigation result.
  81         The algorithm is based on partially external trees, a simple scheme that simplifies deletions
  82         by leaving a routing node in the tree when deleting a node that has two children,
  83         then opportunistically unlinking routing nodes during rebalancing. As in external trees,
  84         which store values only in leaf nodes, deletions can be performed locally while holding
  85         a fixed number of locks. Partially external trees, however, require far fewer routing nodes
  86         than an external tree for most sequences of insertions and deletions.
  87         The algorithm uses optimistic concurrency control, but carefully manage the
  88         tree in such a way that all atomic regions have fixed read and write sets
  89         that are known ahead of time. This allows to reduce practical overheads by embedding
  90         the concurrency control directly. To perform tree operations using only fixed sized
  91         atomic regions the algo uses the following mechanisms: search operations overlap atomic blocks as
  92         in the hand-over-hand locking technique; mutations perform rebalancing separately;
  93         and deletions occasionally leave a routing node in the tree.
  94
  95         <b>Template arguments</b>:
  96         - \p RCU - one of \ref cds_urcu_gc "RCU type"
  97         - \p Key - key type
  98         - \p T - value type to be stored in tree's nodes.
  99         - \p Traits - tree traits, default is \p bronson_avltree::traits
 100             It is possible to declare option-based tree with \p bronson_avltree::make_traits metafunction
 101             instead of \p Traits template argument.
 102
 103         There is \ref cds_container_BronsonAVLTreeMap_rcu_ptr "a specialization" for "key -> value pointer" map.
 104
 105         @note Before including <tt><cds/container/bronson_avltree_map_rcu.h></tt> you should include appropriate RCU header file,
 106         see \ref cds_urcu_gc "RCU type" for list of existing RCU class and corresponding header files.
 107     */
 108     template <
 109         typename RCU,
 110         typename Key,
 111         typename T,
 112 #   ifdef CDS_DOXYGEN_INVOKED
 113         typename Traits = bronson_avltree::traits
 114 #else
 115         typename Traits
 116 #endif
 117     >
 118     class BronsonAVLTreeMap< cds::urcu::gc<RCU>, Key, T, Traits >
 119 #ifdef CDS_DOXYGEN_INVOKED
 120         : private BronsonAVLTreeMap< cds::urcu::gc<RCU>, Key, T*, Traits >
 121 #else
 122         : private bronson_avltree::details::make_map< cds::urcu::gc<RCU>, Key, T, Traits >::type
 123 #endif
 124     {
 125         //@cond
 126         typedef bronson_avltree::details::make_map< cds::urcu::gc<RCU>, Key, T, Traits > maker;
 127         typedef typename maker::type base_class;
 128         //@endcond
 129
 130     public:
 131         typedef cds::urcu::gc<RCU>  gc;   ///< RCU Garbage collector
 132         typedef Key     key_type;    ///< type of a key stored in the map
 133         typedef T       mapped_type; ///< type of value stored in the map
 134         typedef Traits  traits;      ///< Traits template parameter
 135
 136         typedef typename base_class::key_comparator     key_comparator;     ///< key compare functor based on \p Traits::compare and \p Traits::less
 137         typedef typename traits::item_counter           item_counter;       ///< Item counting policy
 138         typedef typename traits::memory_model           memory_model;       ///< Memory ordering, see \p cds::opt::memory_model option
 139         typedef typename traits::allocator              allocator_type;     ///< allocator for value
 140         typedef typename traits::node_allocator         node_allocator_type;///< allocator for maintaining internal nodes
 141         typedef typename traits::stat                   stat;               ///< internal statistics
 142         typedef typename traits::rcu_check_deadlock     rcu_check_deadlock; ///< Deadlock checking policy
 143         typedef typename traits::back_off               back_off;           ///< Back-off strategy
 144         typedef typename traits::sync_monitor           sync_monitor;       ///< @ref cds_sync_monitor "Synchronization monitor" type for node-level locking
 145
 146         /// Enabled or disabled @ref bronson_avltree::relaxed_insert "relaxed insertion"
 147         static bool const c_bRelaxedInsert = traits::relaxed_insert;
 148
 149         /// Group of \p extract_xxx functions does not require external locking
 150         static CDS_CONSTEXPR const bool c_bExtractLockExternal = base_class::c_bExtractLockExternal;
 151
 152         typedef typename base_class::rcu_lock   rcu_lock;  ///< RCU scoped lock
 153
 154         /// Returned pointer to \p mapped_type of extracted node
 155         typedef typename base_class::exempt_ptr exempt_ptr;
 156
 157     protected:
 158         //@cond
 159         typedef typename base_class::node_type        node_type;
 160         typedef typename base_class::node_scoped_lock node_scoped_lock;
 161         typedef typename maker::cxx_allocator         cxx_allocator;
 162
 163         typedef typename base_class::update_flags update_flags;
 164         //@endcond
 165
 166     public:
 167         /// Creates empty map
 168         BronsonAVLTreeMap()
 169         {}
 170
 171         /// Destroys the map
 172         ~BronsonAVLTreeMap()
 173         {}
 174
 175         /// Inserts new node with \p key and default value
 176         /**
 177             The function creates a node with \p key and default value, and then inserts the node created into the map.
 178
 179             Preconditions:
 180             - The \p key_type should be constructible from a value of type \p K.
 181             - The \p mapped_type should be default-constructible.
 182
 183             RCU \p synchronize() can be called. RCU should not be locked.
 184
 185             Returns \p true if inserting successful, \p false otherwise.
 186         */
 187         template <typename K>
 188         bool insert( K const& key )
 189         {
 190             return base_class::do_update(key, key_comparator(),
 191                 []( node_type * pNode ) -> mapped_type*
 192                 {
 193                     assert( pNode->m_pValue.load( memory_model::memory_order_relaxed ) == nullptr );
 194                     CDS_UNUSED( pNode );
 195                     return cxx_allocator().New();
 196                 },
 197                 update_flags::allow_insert
 198             ) == update_flags::result_inserted;
 199         }
 200
 201         /// Inserts new node
 202         /**
 203             The function creates a node with copy of \p val value
 204             and then inserts the node created into the map.
 205
 206             Preconditions:
 207             - The \p key_type should be constructible from \p key of type \p K.
 208             - The \p mapped_type should be constructible from \p val of type \p V.
 209
 210             RCU \p synchronize() method can be called. RCU should not be locked.
 211
 212             Returns \p true if \p val is inserted into the map, \p false otherwise.
 213         */
 214         template <typename K, typename V>
 215         bool insert( K const& key, V const& val )
 216         {
 217             return base_class::do_update( key, key_comparator(),
 218                 [&val]( node_type * pNode ) -> mapped_type*
 219                 {
 220                     assert( pNode->m_pValue.load( memory_model::memory_order_relaxed ) == nullptr );
 221                     CDS_UNUSED( pNode );
 222                     return cxx_allocator().New( val );
 223                 },
 224                 update_flags::allow_insert
 225             ) == update_flags::result_inserted;
 226         }
 227
 228         /// Inserts new node and initialize it by a functor
 229         /**
 230             This function inserts new node with key \p key and if inserting is successful then it calls
 231             \p func functor with signature
 232             \code
 233                 struct functor {
 234                     void operator()( key_type const& key, mapped_type& item );
 235                 };
 236             \endcode
 237
 238             The key_type should be constructible from value of type \p K.
 239
 240             The function allows to split creating of new item into two part:
 241             - create item from \p key;
 242             - insert new item into the map;
 243             - if inserting is successful, initialize the value of item by calling \p func functor
 244
 245             This can be useful if complete initialization of object of \p value_type is heavyweight and
 246             it is preferable that the initialization should be completed only if inserting is successful.
 247             The functor is called under the node lock.
 248
 249             RCU \p synchronize() method can be called. RCU should not be locked.
 250         */
 251         template <typename K, typename Func>
 252         bool insert_with( K const& key, Func func )
 253         {
 254             return base_class::do_update( key, key_comparator(),
 255                 [&func]( node_type * pNode ) -> mapped_type*
 256                 {
 257                     assert( pNode->m_pValue.load( memory_model::memory_order_relaxed ) == nullptr );
 258                     mapped_type * pVal = cxx_allocator().New();
 259                     func( pNode->m_key, *pVal );
 260                     return pVal;
 261                 },
 262                 update_flags::allow_insert
 263             ) == update_flags::result_inserted;
 264         }
 265
 266         /// For \p key inserts data of type \p mapped_type created in-place from \p args
 267         /**
 268             Returns \p true if inserting successful, \p false otherwise.
 269
 270             RCU \p synchronize() method can be called. RCU should not be locked.
 271         */
 272         template <typename K, typename... Args>
 273         bool emplace( K&& key, Args&&... args )
 274         {
 275             struct scoped_ptr
 276             {
 277                 mapped_type * pVal;
 278                 scoped_ptr( mapped_type * p ): pVal( p ) {}
 279                 ~scoped_ptr() { if ( pVal ) cxx_allocator().Delete( pVal ); }
 280                 void release() { pVal = nullptr; }
 281             };
 282
 283             scoped_ptr p( cxx_allocator().MoveNew( std::forward<Args>( args )... ));
 284             if ( base_class::insert( std::forward<K>( key ), p.pVal )) {
 285                 p.release();
 286                 return true;
 287             }
 288             return false;
 289         }
 290
 291         /// Updates the value for \p key
 292         /**
 293             The operation performs inserting or changing data with lock-free manner.
 294
 295             If the \p key not found in the map, then the new item created from \p key
 296             will be inserted into the map iff \p bAllowInsert is \p true
 297             (note that in this case the \ref key_type should be constructible from type \p K).
 298             Otherwise, the functor \p func is called with item found.
 299             The functor \p Func signature is:
 300             \code
 301                 struct my_functor {
 302                     void operator()( bool bNew, key_type const& key, mapped_type& item );
 303                 };
 304             \endcode
 305
 306             with arguments:
 307             - \p bNew - \p true if the item has been inserted, \p false otherwise
 308             - \p item - value
 309
 310             The functor may change any fields of the \p item. The functor is called under the node lock,
 311             the caller can change any field of \p item.
 312
 313             RCU \p synchronize() method can be called. RCU should not be locked.
 314
 315             Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successful,
 316             \p second is \p true if new item has been added or \p false if the item with \p key
 317             already exists.
 318         */
 319         template <typename K, typename Func>
 320         std::pair<bool, bool> update( K const& key, Func func, bool bAllowInsert = true )
 321         {
 322             int result = base_class::do_update( key, key_comparator(),
 323                 [&func]( node_type * pNode ) -> mapped_type*
 324                 {
 325                     mapped_type * pVal = pNode->m_pValue.load( memory_model::memory_order_relaxed );
 326                     if ( !pVal ) {
 327                         pVal = cxx_allocator().New();
 328                         func( true, pNode->m_key, *pVal );
 329                     }
 330                     else
 331                         func( false, pNode->m_key, *pVal );
 332                     return pVal;
 333                 },
 334                 (bAllowInsert ? update_flags::allow_insert : 0) | update_flags::allow_update
 335             );
 336             return std::make_pair( result != 0, (result & update_flags::result_inserted) != 0 );
 337         }
 338
 339
 340         /// Delete \p key from the map
 341         /**
 342             RCU \p synchronize() method can be called. RCU should not be locked.
 343
 344             Return \p true if \p key is found and deleted, \p false otherwise
 345         */
 346         template <typename K>
 347         bool erase( K const& key )
 348         {
 349             return base_class::erase( key );
 350         }
 351
 352         /// Deletes the item from the map using \p pred predicate for searching
 353         /**
 354             The function is an analog of \p erase(K const&)
 355             but \p pred is used for key comparing.
 356             \p Less functor has the interface like \p std::less.
 357             \p Less must imply the same element order as the comparator used for building the map.
 358         */
 359         template <typename K, typename Less>
 360         bool erase_with( K const& key, Less pred )
 361         {
 362             return base_class::erase_with( key, pred );
 363         }
 364
 365         /// Delete \p key from the map
 366         /** \anchor cds_nonintrusive_BronsonAVLTreeMap_rcu_erase_func
 367
 368             The function searches an item with key \p key, calls \p f functor
 369             and deletes the item. If \p key is not found, the functor is not called.
 370
 371             The functor \p Func interface:
 372             \code
 373             struct extractor {
 374                 void operator()(key_type const& key, mapped_type& item) { ... }
 375             };
 376             \endcode
 377
 378             RCU \p synchronize method can be called. RCU should not be locked.
 379
 380             Return \p true if key is found and deleted, \p false otherwise
 381         */
 382         template <typename K, typename Func>
 383         bool erase( K const& key, Func f )
 384         {
 385             return base_class::erase( key, f );
 386         }
 387
 388         /// Deletes the item from the map using \p pred predicate for searching
 389         /**
 390             The function is an analog of \ref cds_nonintrusive_BronsonAVLTreeMap_rcu_erase_func "erase(K const&, Func)"
 391             but \p pred is used for key comparing.
 392             \p Less functor has the interface like \p std::less.
 393             \p Less must imply the same element order as the comparator used for building the map.
 394         */
 395         template <typename K, typename Less, typename Func>
 396         bool erase_with( K const& key, Less pred, Func f )
 397         {
 398             return base_class::erase_with( key, pred, f );
 399         }
 400
 401         /// Extracts a value with minimal key from the map
 402         /**
 403             Returns \p exempt_ptr pointer to the leftmost item.
 404             If the set is empty, returns empty \p exempt_ptr.
 405
 406             Note that the function returns only the value for minimal key.
 407             To retrieve its key use \p extract_min( Func ) member function.
 408
 409             @note Due the concurrent nature of the map, the function extracts <i>nearly</i> minimum key.
 410             It means that the function gets leftmost leaf of the tree and tries to unlink it.
 411             During unlinking, a concurrent thread may insert an item with key less than leftmost item's key.
 412             So, the function returns the item with minimum key at the moment of tree traversing.
 413
 414             RCU \p synchronize method can be called. RCU should NOT be locked.
 415             The function does not free the item.
 416             The deallocator will be implicitly invoked when the returned object is destroyed or when
 417             its \p release() member function is called.
 418         */
 419         exempt_ptr extract_min()
 420         {
 421             return base_class::extract_min();
 422         }
 423
 424         /// Extracts minimal key and corresponding value
 425         /**
 426             Returns \p exempt_ptr to the leftmost item.
 427             If the tree is empty, returns empty \p exempt_ptr.
 428
 429             \p Func functor is used to store minimal key.
 430             \p Func has the following signature:
 431             \code
 432                 struct functor {
 433                     void operator()( key_type const& key );
 434                 };
 435             \endcode
 436             If the tree is empty, \p f is not called.
 437             Otherwise, is it called with minimal key, the pointer to corresponding value is returned
 438             as \p exempt_ptr.
 439
 440             @note Due the concurrent nature of the map, the function extracts <i>nearly</i> minimum key.
 441             It means that the function gets leftmost leaf of the tree and tries to unlink it.
 442             During unlinking, a concurrent thread may insert an item with key less than leftmost item's key.
 443             So, the function returns the item with minimum key at the moment of tree traversing.
 444
 445             RCU \p synchronize method can be called. RCU should NOT be locked.
 446             The function does not free the item.
 447             The deallocator will be implicitly invoked when the returned object is destroyed or when
 448             its \p release() member function is called.
 449         */
 450         template <typename Func>
 451         exempt_ptr extract_min( Func f )
 452         {
 453             return base_class::extract_min( f );
 454         }
 455
 456         /// Extracts minimal key and corresponding value
 457         /**
 458             This function is a shortcut for the following call:
 459             \code
 460                 key_type key;
 461                 exempt_ptr xp = theTree.extract_min( [&key]( key_type const& k ) { key = k; } );
 462             \endcode
 463             \p key_type should be copy-assignable. The copy of minimal key
 464             is returned in \p min_key argument.
 465         */
 466         typename std::enable_if< std::is_copy_assignable<key_type>::value, exempt_ptr >::type
 467         extract_min_key( key_type& min_key )
 468         {
 469             return base_class::extract_min_key( min_key );
 470         }
 471
 472         /// Extracts an item with maximal key from the map
 473         /**
 474             Returns \p exempt_ptr pointer to the rightmost item.
 475             If the set is empty, returns empty \p exempt_ptr.
 476
 477             Note that the function returns only the value for maximal key.
 478             To retrieve its key use \p extract_max( Func ) or \p extract_max_key(key_type&) member function.
 479
 480             @note Due the concurrent nature of the map, the function extracts <i>nearly</i> maximal key.
 481             It means that the function gets rightmost leaf of the tree and tries to unlink it.
 482             During unlinking, a concurrent thread may insert an item with key greater than rightmost item's key.
 483             So, the function returns the item with maximum key at the moment of tree traversing.
 484
 485             RCU \p synchronize method can be called. RCU should NOT be locked.
 486             The function does not free the item.
 487             The deallocator will be implicitly invoked when the returned object is destroyed or when
 488             its \p release() is called.
 489         */
 490         exempt_ptr extract_max()
 491         {
 492             return base_class::extract_max();
 493         }
 494
 495         /// Extracts the maximal key and corresponding value
 496         /**
 497             Returns \p exempt_ptr pointer to the rightmost item.
 498             If the set is empty, returns empty \p exempt_ptr.
 499
 500             \p Func functor is used to store maximal key.
 501             \p Func has the following signature:
 502             \code
 503                 struct functor {
 504                     void operator()( key_type const& key );
 505                 };
 506             \endcode
 507             If the tree is empty, \p f is not called.
 508             Otherwise, is it called with maximal key, the pointer to corresponding value is returned
 509             as \p exempt_ptr.
 510
 511             @note Due the concurrent nature of the map, the function extracts <i>nearly</i> maximal key.
 512             It means that the function gets rightmost leaf of the tree and tries to unlink it.
 513             During unlinking, a concurrent thread may insert an item with key greater than rightmost item's key.
 514             So, the function returns the item with maximum key at the moment of tree traversing.
 515
 516             RCU \p synchronize method can be called. RCU should NOT be locked.
 517             The function does not free the item.
 518             The deallocator will be implicitly invoked when the returned object is destroyed or when
 519             its \p release() is called.
 520         */
 521         template <typename Func>
 522         exempt_ptr extract_max( Func f )
 523         {
 524             return base_class::extract_max( f );
 525         }
 526
 527         /// Extracts the maximal key and corresponding value
 528         /**
 529             This function is a shortcut for the following call:
 530             \code
 531                 key_type key;
 532                 exempt_ptr xp = theTree.extract_max( [&key]( key_type const& k ) { key = k; } );
 533             \endcode
 534             \p key_type should be copy-assignable. The copy of maximal key
 535             is returned in \p max_key argument.
 536         */
 537         typename std::enable_if< std::is_copy_assignable<key_type>::value, exempt_ptr >::type
 538         extract_max_key( key_type& max_key )
 539         {
 540             return base_class::extract_max_key( max_key );
 541         }
 542
 543         /// Extracts an item from the map
 544         /**
 545             The function searches an item with key equal to \p key in the tree,
 546             unlinks it, and returns \p exempt_ptr pointer to a value found.
 547             If \p key is not found the function returns an empty \p exempt_ptr.
 548
 549             RCU \p synchronize method can be called. RCU should NOT be locked.
 550             The function does not destroy the value found.
 551             The dealloctor will be implicitly invoked when the returned object is destroyed or when
 552             its \p release() member function is called.
 553         */
 554         template <typename Q>
 555         exempt_ptr extract( Q const& key )
 556         {
 557             return base_class::extract( key );
 558         }
 559
 560         /// Extracts an item from the map using \p pred for searching
 561         /**
 562             The function is an analog of \p extract(Q const&)
 563             but \p pred is used for key compare.
 564             \p Less has the interface like \p std::less.
 565             \p pred must imply the same element order as the comparator used for building the map.
 566         */
 567         template <typename Q, typename Less>
 568         exempt_ptr extract_with( Q const& key, Less pred )
 569         {
 570             return base_class::extract_with( key, pred );
 571         }
 572
 573         /// Find the key \p key
 574         /**
 575             The function searches the item with key equal to \p key and calls the functor \p f for item found.
 576             The interface of \p Func functor is:
 577             \code
 578             struct functor {
 579                 void operator()( key_type const& key, mapped_type& val );
 580             };
 581             \endcode
 582             where \p val is the item found for \p key
 583             The functor is called under node-level lock.
 584
 585             The function applies RCU lock internally.
 586
 587             The function returns \p true if \p key is found, \p false otherwise.
 588         */
 589         template <typename K, typename Func>
 590         bool find( K const& key, Func f )
 591         {
 592             return base_class::find( key, f );
 593         }
 594
 595         /// Finds the key \p val using \p pred predicate for searching
 596         /**
 597             The function is an analog of \p find(K const&, Func)
 598             but \p pred is used for key comparing.
 599             \p Less functor has the interface like \p std::less.
 600             \p Less must imply the same element order as the comparator used for building the map.
 601         */
 602         template <typename K, typename Less, typename Func>
 603         bool find_with( K const& key, Less pred, Func f )
 604         {
 605             return base_class::find_with( key, pred, f );
 606         }
 607
 608         /// Checks whether the map contains \p key
 609         /**
 610             The function searches the item with key equal to \p key
 611             and returns \p true if it is found, and \p false otherwise.
 612
 613             The function applies RCU lock internally.
 614         */
 615         template <typename K>
 616         bool contains( K const& key )
 617         {
 618             return base_class::contains( key );
 619         }
 620
 621         /// Checks whether the map contains \p key using \p pred predicate for searching
 622         /**
 623             The function is similar to <tt>contains( key )</tt> but \p pred is used for key comparing.
 624             \p Less functor has the interface like \p std::less.
 625             \p Less must imply the same element order as the comparator used for building the set.
 626         */
 627         template <typename K, typename Less>
 628         bool contains( K const& key, Less pred )
 629         {
 630             return base_class::contains( key, pred );
 631         }
 632
 633         /// Clears the map
 634         void clear()
 635         {
 636             base_class::clear();
 637         }
 638
 639         /// Checks if the map is empty
 640         bool empty() const
 641         {
 642             return base_class::empty();
 643         }
 644
 645         /// Returns item count in the map
 646         /**
 647             Only leaf nodes containing user data are counted.
 648
 649             The value returned depends on item counter type provided by \p Traits template parameter.
 650             If it is \p atomicity::empty_item_counter this function always returns 0.
 651
 652             The function is not suitable for checking the tree emptiness, use \p empty()
 653             member function for this purpose.
 654         */
 655         size_t size() const
 656         {
 657             return base_class::size();
 658         }
 659
 660         /// Returns const reference to internal statistics
 661         stat const& statistics() const
 662         {
 663             return base_class::statistics();
 664         }
 665
 666         /// Returns reference to \p sync_monitor object
 667         sync_monitor& monitor()
 668         {
 669             return base_class::monitor();
 670         }
 671         //@cond
 672         sync_monitor const& monitor() const
 673         {
 674             return base_class::monitor();
 675         }
 676         //@endcond
 677
 678         /// Checks internal consistency (not atomic, not thread-safe)
 679         /**
 680             The debugging function to check internal consistency of the tree.
 681         */
 682         bool check_consistency() const
 683         {
 684             return base_class::check_consistency();
 685         }
 686
 687         /// Checks internal consistency (not atomic, not thread-safe)
 688         /**
 689             The debugging function to check internal consistency of the tree.
 690             The functor \p Func is called if a violation of internal tree structure
 691             is found:
 692             \code
 693             struct functor {
 694                 void operator()( size_t nLevel, size_t hLeft, size_t hRight );
 695             };
 696             \endcode
 697             where
 698             - \p nLevel - the level where the violation is found
 699             - \p hLeft - the height of left subtree
 700             - \p hRight - the height of right subtree
 701
 702             The functor is called for each violation found.
 703         */
 704         template <typename Func>
 705         bool check_consistency( Func f ) const
 706         {
 707             return base_class::check_consistency( f );
 708         }
 709     };
 710 }} // namespace cds::container
 711
 712 #endif // #ifndef CDSLIB_CONTAINER_IMPL_BRONSON_AVLTREE_MAP_RCU_H