cds/container/ellen_bintree_map_rcu.h

   1 //$$CDS-header$$
   2
   3 #ifndef __CDS_CONTAINER_ELLEN_BINTREE_MAP_RCU_H
   4 #define __CDS_CONTAINER_ELLEN_BINTREE_MAP_RCU_H
   5
   6 #include <cds/container/ellen_bintree_base.h>
   7 #include <cds/intrusive/ellen_bintree_rcu.h>
   8 #include <cds/details/functor_wrapper.h>
   9
  10 namespace cds { namespace container {
  11
  12     /// Map based on Ellen's et al binary search tree (RCU specialization)
  13     /** @ingroup cds_nonintrusive_map
  14         @ingroup cds_nonintrusive_tree
  15         @anchor cds_container_EllenBinTreeMap_rcu
  16
  17         Source:
  18             - [2010] F.Ellen, P.Fatourou, E.Ruppert, F.van Breugel "Non-blocking Binary Search Tree"
  19
  20         %EllenBinTreeMap is an unbalanced leaf-oriented binary search tree that implements the <i>map</i>
  21         abstract data type. Nodes maintains child pointers but not parent pointers.
  22         Every internal node has exactly two children, and all data of type <tt>std::pair<Key const, T></tt>
  23         currently in the tree are stored in the leaves. Internal nodes of the tree are used to direct \p find
  24         operation along the path to the correct leaf. The keys (of \p Key type) stored in internal nodes
  25         may or may not be in the map.
  26         Unlike \ref cds_container_EllenBinTreeSet_rcu "EllenBinTreeSet" keys are not a part of \p T type.
  27         The map can be represented as a set containing <tt>std::pair< Key const, T> </tt> values.
  28
  29         Due to \p extract_min and \p extract_max member functions the \p %EllenBinTreeMap can act as
  30         a <i>priority queue</i>. In this case you should provide unique compound key, for example,
  31         the priority value plus some uniformly distributed random value.
  32
  33         @warning Recall the tree is <b>unbalanced</b>. The complexity of operations is <tt>O(log N)</tt>
  34         for uniformly distributed random keys, but in worst case the complexity is <tt>O(N)</tt>.
  35
  36         @note In the current implementation we do not use helping technique described in original paper.
  37         So, the current implementation is near to fine-grained lock-based tree.
  38         Helping will be implemented in future release
  39
  40         <b>Template arguments</b> :
  41         - \p RCU - one of \ref cds_urcu_gc "RCU type"
  42         - \p Key - key type
  43         - \p T - value type to be stored in tree's leaf nodes.
  44         - \p Traits - type traits. See ellen_bintree::type_traits for explanation.
  45
  46         It is possible to declare option-based tree with ellen_bintree::make_map_traits metafunction
  47         instead of \p Traits template argument.
  48         Template argument list \p Options of ellen_bintree::make_map_traits metafunction are:
  49         - opt::compare - key compare functor. No default functor is provided.
  50             If the option is not specified, \p %opt::less is used.
  51         - opt::less - specifies binary predicate used for key compare. At least \p %opt::compare or \p %opt::less should be defined.
  52         - opt::item_counter - the type of item counting feature. Default is \ref atomicity::empty_item_counter that is no item counting.
  53         - opt::memory_model - C++ memory ordering model. Can be opt::v::relaxed_ordering (relaxed memory model, the default)
  54             or opt::v::sequential_consistent (sequentially consisnent memory model).
  55         - opt::allocator - the allocator used for \ref ellen_bintree::map_node "leaf nodes" which contains data.
  56             Default is \ref CDS_DEFAULT_ALLOCATOR.
  57         - opt::node_allocator - the allocator used for \ref ellen_bintree::internal_node "internal nodes".
  58             Default is \ref CDS_DEFAULT_ALLOCATOR.
  59         - ellen_bintree::update_desc_allocator - an allocator of \ref ellen_bintree::update_desc "update descriptors",
  60             default is \ref CDS_DEFAULT_ALLOCATOR.
  61             Note that update descriptor is helping data structure with short lifetime and it is good candidate for pooling.
  62             The number of simultaneously existing descriptors is a relatively small number limited the number of threads
  63             working with the tree and RCU buffer size.
  64             Therefore, a bounded lock-free container like \p cds::container::VyukovMPMCCycleQueue is good choice for the free-list
  65             of update descriptors, see cds::memory::vyukov_queue_pool free-list implementation.
  66             Also notice that size of update descriptor is not dependent on the type of data
  67             stored in the tree so single free-list object can be used for several EllenBinTree-based object.
  68         - opt::stat - internal statistics. Available types: ellen_bintree::stat, ellen_bintree::empty_stat (the default)
  69         - opt::rcu_check_deadlock - a deadlock checking policy. Default is opt::v::rcu_throw_deadlock
  70         - opt::copy_policy - key copy policy defines a functor to copy leaf node's key to internal node.
  71             By default, assignment operator is used.
  72             The copy functor interface is:
  73             \code
  74             struct copy_functor {
  75                 void operator()( Key& dest, Key const& src );
  76             };
  77             \endcode
  78
  79         @note Before including <tt><cds/container/ellen_bintree_map_rcu.h></tt> you should include appropriate RCU header file,
  80         see \ref cds_urcu_gc "RCU type" for list of existing RCU class and corresponding header files.
  81     */
  82     template <
  83         class RCU,
  84         typename Key,
  85         typename T,
  86 #ifdef CDS_DOXYGEN_INVOKED
  87         class Traits = ellen_bintree::type_traits
  88 #else
  89         class Traits
  90 #endif
  91     >
  92     class EllenBinTreeMap< cds::urcu::gc<RCU>, Key, T, Traits >
  93 #ifdef CDS_DOXYGEN_INVOKED
  94         : public cds::intrusive::EllenBinTree< cds::urcu::gc<RCU>, Key, T, Traits >
  95 #else
  96         : public ellen_bintree::details::make_ellen_bintree_map< cds::urcu::gc<RCU>, Key, T, Traits >::type
  97 #endif
  98     {
  99         //@cond
 100         typedef ellen_bintree::details::make_ellen_bintree_map< cds::urcu::gc<RCU>, Key, T, Traits > maker;
 101         typedef typename maker::type base_class;
 102         //@endcond
 103     public:
 104         typedef cds::urcu::gc<RCU>  gc  ;   ///< RCU Garbage collector
 105         typedef Key     key_type        ;   ///< type of a key stored in the map
 106         typedef T       mapped_type      ;  ///< type of value stored in the map
 107         typedef std::pair< key_type const, mapped_type >    value_type  ;   ///< Key-value pair stored in leaf node of the mp
 108         typedef Traits  options         ;   ///< Traits template parameter
 109
 110 #   ifdef CDS_DOXYGEN_INVOKED
 111         typedef implementation_defined key_comparator  ;    ///< key compare functor based on opt::compare and opt::less option setter.
 112 #   else
 113         typedef typename maker::intrusive_type_traits::compare   key_comparator;
 114 #   endif
 115         typedef typename base_class::item_counter           item_counter        ; ///< Item counting policy used
 116         typedef typename base_class::memory_model           memory_model        ; ///< Memory ordering. See cds::opt::memory_model option
 117         typedef typename base_class::node_allocator         node_allocator_type ; ///< allocator for maintaining internal node
 118         typedef typename base_class::stat                   stat                ; ///< internal statistics type
 119         typedef typename base_class::rcu_check_deadlock     rcu_check_deadlock  ; ///< Deadlock checking policy
 120         typedef typename options::copy_policy               copy_policy         ; ///< key copy policy
 121
 122         typedef typename options::allocator                 allocator_type      ;   ///< Allocator for leaf nodes
 123         typedef typename base_class::node_allocator         node_allocator      ;   ///< Internal node allocator
 124         typedef typename base_class::update_desc_allocator  update_desc_allocator ; ///< Update descriptor allocator
 125
 126         static CDS_CONSTEXPR_CONST bool c_bExtractLockExternal = base_class::c_bExtractLockExternal; ///< Group of \p extract_xxx functions do not require external locking
 127
 128     protected:
 129         //@cond
 130         typedef typename base_class::value_type         leaf_node;
 131         typedef typename base_class::internal_node      internal_node;
 132         typedef typename base_class::update_desc        update_desc;
 133
 134         typedef typename maker::cxx_leaf_node_allocator cxx_leaf_node_allocator;
 135
 136         typedef std::unique_ptr< leaf_node, typename maker::leaf_deallocator >    scoped_node_ptr;
 137         //@endcond
 138
 139     public:
 140         typedef typename gc::scoped_lock    rcu_lock ;  ///< RCU scoped lock
 141
 142         /// pointer to extracted node
 143         typedef cds::urcu::exempt_ptr< gc, leaf_node, value_type, typename maker::intrusive_type_traits::disposer,
 144             cds::urcu::details::conventional_exempt_member_cast<leaf_node, value_type>
 145         > exempt_ptr;
 146
 147     protected:
 148         //@cond
 149 #   ifndef CDS_CXX11_LAMBDA_SUPPORT
 150         struct empty_insert_functor
 151         {
 152             void operator()( value_type& ) const
 153             {}
 154         };
 155
 156         template <typename Q>
 157         class insert_value_functor
 158         {
 159             Q const&    m_val;
 160         public:
 161             insert_value_functor( Q const& v)
 162                 : m_val(v)
 163             {}
 164
 165             void operator()( value_type& item )
 166             {
 167                 item.second = m_val;
 168             }
 169         };
 170
 171         template <typename Func>
 172         class insert_key_wrapper: protected cds::details::functor_wrapper<Func>
 173         {
 174             typedef cds::details::functor_wrapper<Func> base_class;
 175         public:
 176             insert_key_wrapper( Func f ): base_class(f) {}
 177
 178             void operator()( leaf_node& item )
 179             {
 180                 base_class::get()( item.m_Value );
 181             }
 182         };
 183
 184         template <typename Func>
 185         class ensure_wrapper: protected cds::details::functor_wrapper<Func>
 186         {
 187             typedef cds::details::functor_wrapper<Func> base_class;
 188         public:
 189             ensure_wrapper( Func f) : base_class(f) {}
 190
 191             void operator()( bool bNew, leaf_node& item, leaf_node const& )
 192             {
 193                 base_class::get()( bNew, item.m_Value );
 194             }
 195         };
 196
 197         template <typename Func>
 198         struct erase_functor
 199         {
 200             Func        m_func;
 201
 202             erase_functor( Func f )
 203                 : m_func(f)
 204             {}
 205
 206             void operator()( leaf_node& node )
 207             {
 208                 cds::unref(m_func)( node.m_Value );
 209             }
 210         };
 211
 212         template <typename Func>
 213         class find_wrapper: protected cds::details::functor_wrapper<Func>
 214         {
 215             typedef cds::details::functor_wrapper<Func> base_class;
 216         public:
 217             find_wrapper( Func f )
 218                 : base_class(f)
 219             {}
 220
 221             template <typename Q>
 222             void operator()( leaf_node& item, Q& val )
 223             {
 224                 base_class::get()( item.m_Value, val );
 225             }
 226         };
 227 #   endif
 228         //@endcond
 229
 230     public:
 231         /// Default constructor
 232         EllenBinTreeMap()
 233             : base_class()
 234         {}
 235
 236         /// Clears the map
 237         ~EllenBinTreeMap()
 238         {}
 239
 240         /// Inserts new node with key and default value
 241         /**
 242             The function creates a node with \p key and default value, and then inserts the node created into the map.
 243
 244             Preconditions:
 245             - The \ref key_type should be constructible from a value of type \p K.
 246                 In trivial case, \p K is equal to \ref key_type.
 247             - The \ref mapped_type should be default-constructible.
 248
 249             RCU \p synchronize method can be called. RCU should not be locked.
 250
 251             Returns \p true if inserting successful, \p false otherwise.
 252         */
 253         template <typename K>
 254         bool insert( K const& key )
 255         {
 256 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
 257             return insert_key( key, [](value_type&){} );
 258 #       else
 259             return insert_key( key, empty_insert_functor() );
 260 #       endif
 261         }
 262
 263         /// Inserts new node
 264         /**
 265             The function creates a node with copy of \p val value
 266             and then inserts the node created into the map.
 267
 268             Preconditions:
 269             - The \ref key_type should be constructible from \p key of type \p K.
 270             - The \ref value_type should be constructible from \p val of type \p V.
 271
 272             RCU \p synchronize method can be called. RCU should not be locked.
 273
 274             Returns \p true if \p val is inserted into the map, \p false otherwise.
 275         */
 276         template <typename K, typename V>
 277         bool insert( K const& key, V const& val )
 278         {
 279             scoped_node_ptr pNode( cxx_leaf_node_allocator().New( key, val ));
 280             if ( base_class::insert( *pNode ))
 281             {
 282                 pNode.release();
 283                 return true;
 284             }
 285             return false;
 286         }
 287
 288         /// Inserts new node and initialize it by a functor
 289         /**
 290             This function inserts new node with key \p key and if inserting is successful then it calls
 291             \p func functor with signature
 292             \code
 293                 struct functor {
 294                     void operator()( value_type& item );
 295                 };
 296             \endcode
 297
 298             The argument \p item of user-defined functor \p func is the reference
 299             to the map's item inserted:
 300                 - <tt>item.first</tt> is a const reference to item's key that cannot be changed.
 301                 - <tt>item.second</tt> is a reference to item's value that may be changed.
 302
 303             The user-defined functor can be passed by reference using <tt>boost::ref</tt>
 304             and it is called only if inserting is successful.
 305
 306             The key_type should be constructible from value of type \p K.
 307
 308             The function allows to split creating of new item into two part:
 309             - create item from \p key;
 310             - insert new item into the map;
 311             - if inserting is successful, initialize the value of item by calling \p func functor
 312
 313             This can be useful if complete initialization of object of \p value_type is heavyweight and
 314             it is preferable that the initialization should be completed only if inserting is successful.
 315
 316             RCU \p synchronize method can be called. RCU should not be locked.
 317         */
 318         template <typename K, typename Func>
 319         bool insert_key( const K& key, Func func )
 320         {
 321             scoped_node_ptr pNode( cxx_leaf_node_allocator().New( key ));
 322 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
 323             if ( base_class::insert( *pNode, [&func]( leaf_node& item ) { cds::unref(func)( item.m_Value ); } ))
 324 #       else
 325             insert_key_wrapper<Func> wrapper(func);
 326             if ( base_class::insert( *pNode, cds::ref(wrapper) ))
 327 #endif
 328             {
 329                 pNode.release();
 330                 return true;
 331             }
 332             return false;
 333         }
 334
 335         /// For key \p key inserts data of type \ref value_type constructed with <tt>std::forward<Args>(args)...</tt>
 336         /**
 337             Returns \p true if inserting successful, \p false otherwise.
 338
 339             RCU \p synchronize method can be called. RCU should not be locked.
 340         */
 341         template <typename K, typename... Args>
 342         bool emplace( K&& key, Args&&... args )
 343         {
 344             scoped_node_ptr pNode( cxx_leaf_node_allocator().New( std::forward<K>(key), std::forward<Args>(args)... ));
 345             if ( base_class::insert( *pNode )) {
 346                 pNode.release();
 347                 return true;
 348             }
 349             return false;
 350         }
 351
 352         /// Ensures that the \p key exists in the map
 353         /**
 354             The operation performs inserting or changing data with lock-free manner.
 355
 356             If the \p key not found in the map, then the new item created from \p key
 357             is inserted into the map (note that in this case the \ref key_type should be
 358             constructible from type \p K).
 359             Otherwise, the functor \p func is called with item found.
 360             The functor \p Func may be a function with signature:
 361             \code
 362                 void func( bool bNew, value_type& item );
 363             \endcode
 364             or a functor:
 365             \code
 366                 struct my_functor {
 367                     void operator()( bool bNew, value_type& item );
 368                 };
 369             \endcode
 370
 371             with arguments:
 372             - \p bNew - \p true if the item has been inserted, \p false otherwise
 373             - \p item - item of the list
 374
 375             The functor may change any fields of the \p item.second that is \ref value_type.
 376
 377             You may pass \p func argument by reference using <tt>boost::ref</tt>.
 378
 379             RCU \p synchronize method can be called. RCU should not be locked.
 380
 381             Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
 382             \p second is true if new item has been added or \p false if the item with \p key
 383             already is in the list.
 384         */
 385         template <typename K, typename Func>
 386         std::pair<bool, bool> ensure( K const& key, Func func )
 387         {
 388             scoped_node_ptr pNode( cxx_leaf_node_allocator().New( key ));
 389 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
 390             std::pair<bool, bool> res = base_class::ensure( *pNode,
 391                 [&func](bool bNew, leaf_node& item, leaf_node const& ){ cds::unref(func)( bNew, item.m_Value ); }
 392             );
 393 #       else
 394             ensure_wrapper<Func> wrapper( func );
 395             std::pair<bool, bool> res = base_class::ensure( *pNode, cds::ref(wrapper) );
 396 #       endif
 397             if ( res.first && res.second )
 398                 pNode.release();
 399             return res;
 400         }
 401
 402         /// Delete \p key from the map
 403         /**\anchor cds_nonintrusive_EllenBinTreeMap_rcu_erase_val
 404
 405             RCU \p synchronize method can be called. RCU should not be locked.
 406
 407             Return \p true if \p key is found and deleted, \p false otherwise
 408         */
 409         template <typename K>
 410         bool erase( K const& key )
 411         {
 412             return base_class::erase(key);
 413         }
 414
 415         /// Deletes the item from the map using \p pred predicate for searching
 416         /**
 417             The function is an analog of \ref cds_nonintrusive_EllenBinTreeMap_rcu_erase_val "erase(K const&)"
 418             but \p pred is used for key comparing.
 419             \p Less functor has the interface like \p std::less.
 420             \p Less must imply the same element order as the comparator used for building the map.
 421         */
 422         template <typename K, typename Less>
 423         bool erase_with( K const& key, Less pred )
 424         {
 425             return base_class::erase_with( key, cds::details::predicate_wrapper< leaf_node, Less, typename maker::key_accessor >());
 426         }
 427
 428         /// Delete \p key from the map
 429         /** \anchor cds_nonintrusive_EllenBinTreeMap_rcu_erase_func
 430
 431             The function searches an item with key \p key, calls \p f functor
 432             and deletes the item. If \p key is not found, the functor is not called.
 433
 434             The functor \p Func interface:
 435             \code
 436             struct extractor {
 437                 void operator()(value_type& item) { ... }
 438             };
 439             \endcode
 440             The functor may be passed by reference using <tt>boost:ref</tt>
 441
 442             RCU \p synchronize method can be called. RCU should not be locked.
 443
 444             Return \p true if key is found and deleted, \p false otherwise
 445         */
 446         template <typename K, typename Func>
 447         bool erase( K const& key, Func f )
 448         {
 449 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
 450             return base_class::erase( key, [&f]( leaf_node& node) { cds::unref(f)( node.m_Value ); } );
 451 #       else
 452             erase_functor<Func> wrapper(f);
 453             return base_class::erase( key, cds::ref(wrapper));
 454 #       endif
 455         }
 456
 457         /// Deletes the item from the map using \p pred predicate for searching
 458         /**
 459             The function is an analog of \ref cds_nonintrusive_EllenBinTreeMap_rcu_erase_func "erase(K const&, Func)"
 460             but \p pred is used for key comparing.
 461             \p Less functor has the interface like \p std::less.
 462             \p Less must imply the same element order as the comparator used for building the map.
 463         */
 464         template <typename K, typename Less, typename Func>
 465         bool erase_with( K const& key, Less pred, Func f )
 466         {
 467 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
 468             return base_class::erase_with( key, cds::details::predicate_wrapper< leaf_node, Less, typename maker::key_accessor >(),
 469                 [&f]( leaf_node& node) { cds::unref(f)( node.m_Value ); } );
 470 #       else
 471             erase_functor<Func> wrapper(f);
 472             return base_class::erase_with( key, cds::details::predicate_wrapper< leaf_node, Less, typename maker::key_accessor >(), cds::ref(wrapper));
 473 #       endif
 474         }
 475
 476         /// Extracts an item with minimal key from the map
 477         /**
 478             If the map is not empty, the function returns \p true, \p result contains a pointer to value.
 479             If the map is empty, the function returns \p false, \p result is left unchanged.
 480
 481             @note Due the concurrent nature of the map, the function extracts <i>nearly</i> minimum key.
 482             It means that the function gets leftmost leaf of the tree and tries to unlink it.
 483             During unlinking, a concurrent thread may insert an item with key less than leftmost item's key.
 484             So, the function returns the item with minimum key at the moment of tree traversing.
 485
 486             RCU \p synchronize method can be called. RCU should NOT be locked.
 487             The function does not free the item.
 488             The deallocator will be implicitly invoked when \p result object is destroyed or when
 489             <tt>result.release()</tt> is called, see cds::urcu::exempt_ptr for explanation.
 490             @note Before reusing \p result object you should call its \p release() method.
 491         */
 492         bool extract_min( exempt_ptr& result )
 493         {
 494             return base_class::extract_min_( result );
 495         }
 496
 497         /// Extracts an item with maximal key from the map
 498         /**
 499             If the map is not empty, the function returns \p true, \p result contains a pointer to extracted item.
 500             If the map is empty, the function returns \p false, \p result is left unchanged.
 501
 502             @note Due the concurrent nature of the map, the function extracts <i>nearly</i> maximal key.
 503             It means that the function gets rightmost leaf of the tree and tries to unlink it.
 504             During unlinking, a concurrent thread may insert an item with key great than leftmost item's key.
 505             So, the function returns the item with maximum key at the moment of tree traversing.
 506
 507             RCU \p synchronize method can be called. RCU should NOT be locked.
 508             The function does not free the item.
 509             The deallocator will be implicitly invoked when \p result object is destroyed or when
 510             <tt>result.release()</tt> is called, see cds::urcu::exempt_ptr for explanation.
 511             @note Before reusing \p result object you should call its \p release() method.
 512         */
 513         bool extract_max( exempt_ptr& result )
 514         {
 515             return base_class::extract_max_( result );
 516         }
 517
 518         /// Extracts an item from the map
 519         /** \anchor cds_nonintrusive_EllenBinTreeMap_rcu_extract
 520             The function searches an item with key equal to \p key in the tree,
 521             unlinks it, and returns pointer to an item found in \p result parameter.
 522             If \p key is not found the function returns \p false.
 523
 524             RCU \p synchronize method can be called. RCU should NOT be locked.
 525             The function does not destroy the item found.
 526             The dealloctor will be implicitly invoked when \p result object is destroyed or when
 527             <tt>result.release()</tt> is called, see cds::urcu::exempt_ptr for explanation.
 528             @note Before reusing \p result object you should call its \p release() method.
 529         */
 530         template <typename Q>
 531         bool extract( exempt_ptr& result, Q const& key )
 532         {
 533             return base_class::extract_( result, key, typename base_class::node_compare());
 534         }
 535
 536         /// Extracts an item from the map using \p pred for searching
 537         /**
 538             The function is an analog of \ref cds_nonintrusive_EllenBinTreeMap_rcu_extract "extract(exempt_ptr&, Q const&)"
 539             but \p pred is used for key compare.
 540             \p Less has the interface like \p std::less and should meet \ref cds_container_EllenBinTreeSet_rcu_less
 541             "predicate requirements".
 542             \p pred must imply the same element order as the comparator used for building the map.
 543         */
 544         template <typename Q, typename Less>
 545         bool extract_with( exempt_ptr& result,  Q const& val, Less pred )
 546         {
 547             return base_class::extract_with_( result, val,
 548                 cds::details::predicate_wrapper< leaf_node, Less, typename maker::key_accessor >() );
 549         }
 550
 551         /// Find the key \p key
 552         /** \anchor cds_nonintrusive_EllenBinTreeMap_rcu_find_cfunc
 553
 554             The function searches the item with key equal to \p key and calls the functor \p f for item found.
 555             The interface of \p Func functor is:
 556             \code
 557             struct functor {
 558                 void operator()( value_type& item );
 559             };
 560             \endcode
 561             where \p item is the item found.
 562
 563             You can pass \p f argument by reference using <tt>boost::ref</tt> or cds::ref.
 564
 565             The functor may change \p item.second.
 566
 567             The function applies RCU lock internally.
 568
 569             The function returns \p true if \p key is found, \p false otherwise.
 570         */
 571         template <typename K, typename Func>
 572         bool find( K const& key, Func f )
 573         {
 574 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
 575             return base_class::find( key, [&f](leaf_node& item, K const& ) { cds::unref(f)( item.m_Value );});
 576 #       else
 577             find_wrapper<Func> wrapper(f);
 578             return base_class::find( key, cds::ref(wrapper) );
 579 #       endif
 580         }
 581
 582         /// Finds the key \p val using \p pred predicate for searching
 583         /**
 584             The function is an analog of \ref cds_nonintrusive_EllenBinTreeMap_rcu_find_cfunc "find(K const&, Func)"
 585             but \p pred is used for key comparing.
 586             \p Less functor has the interface like \p std::less.
 587             \p Less must imply the same element order as the comparator used for building the map.
 588         */
 589         template <typename K, typename Less, typename Func>
 590         bool find_with( K const& key, Less pred, Func f )
 591         {
 592 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
 593             return base_class::find_with( key, cds::details::predicate_wrapper< leaf_node, Less, typename maker::key_accessor >(),
 594                 [&f](leaf_node& item, K const& ) { cds::unref(f)( item.m_Value );});
 595 #       else
 596             find_wrapper<Func> wrapper(f);
 597             return base_class::find_with( key, cds::details::predicate_wrapper< leaf_node, Less, typename maker::key_accessor >(), cds::ref(wrapper) );
 598 #       endif
 599         }
 600
 601         /// Find the key \p key
 602         /** \anchor cds_nonintrusive_EllenBinTreeMap_rcu_find_val
 603
 604             The function searches the item with key equal to \p key
 605             and returns \p true if it is found, and \p false otherwise.
 606
 607             The function applies RCU lock internally.
 608         */
 609         template <typename K>
 610         bool find( K const& key )
 611         {
 612             return base_class::find( key );
 613         }
 614
 615         /// Finds the key \p val using \p pred predicate for searching
 616         /**
 617             The function is an analog of \ref cds_nonintrusive_EllenBinTreeMap_rcu_find_val "find(K const&)"
 618             but \p pred is used for key comparing.
 619             \p Less functor has the interface like \p std::less.
 620             \p Less must imply the same element order as the comparator used for building the map.
 621         */
 622         template <typename K, typename Less>
 623         bool find_with( K const& key, Less pred )
 624         {
 625             return base_class::find_with( key, cds::details::predicate_wrapper< leaf_node, Less, typename maker::key_accessor >() );
 626         }
 627
 628         /// Finds \p key and return the item found
 629         /** \anchor cds_nonintrusive_EllenBinTreeMap_rcu_get
 630             The function searches the item with key equal to \p key and returns the pointer to item found.
 631             If \p key is not found it returns \p nullptr.
 632
 633             RCU should be locked before call the function.
 634             Returned pointer is valid while RCU is locked.
 635         */
 636         template <typename Q>
 637         value_type * get( Q const& key ) const
 638         {
 639             leaf_node * pNode = base_class::get( key );
 640             return pNode ? &pNode->m_Value : nullptr;
 641         }
 642
 643         /// Finds \p key with \p pred predicate and return the item found
 644         /**
 645             The function is an analog of \ref cds_nonintrusive_EllenBinTreeMap_rcu_get "get(Q const&)"
 646             but \p pred is used for comparing the keys.
 647
 648             \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type
 649             and \p Q in any order.
 650             \p pred must imply the same element order as the comparator used for building the map.
 651         */
 652         template <typename Q, typename Less>
 653         value_type * get_with( Q const& key, Less pred ) const
 654         {
 655             leaf_node * pNode = base_class::get_with( key,
 656                 cds::details::predicate_wrapper< leaf_node, Less, typename maker::key_accessor >());
 657             return pNode ? &pNode->m_Value : nullptr;
 658         }
 659
 660         /// Clears the map
 661         void clear()
 662         {
 663             base_class::clear();
 664         }
 665
 666         /// Checks if the map is empty
 667         /**
 668             Emptiness is checked by item counting: if item count is zero then the map is empty.
 669         */
 670         bool empty() const
 671         {
 672             return base_class::empty();
 673         }
 674
 675         /// Returns item count in the map
 676         size_t size() const
 677         {
 678             return base_class::size();
 679         }
 680
 681         /// Returns const reference to internal statistics
 682         stat const& statistics() const
 683         {
 684             return base_class::statistics();
 685         }
 686
 687         /// Checks internal consistency (not atomic, not thread-safe)
 688         /**
 689             The debugging function to check internal consistency of the tree.
 690         */
 691         bool check_consistency() const
 692         {
 693             return base_class::check_consistency();
 694         }
 695
 696     };
 697 }} // namespace cds::container
 698
 699 #endif //#ifndef __CDS_CONTAINER_ELLEN_BINTREE_MAP_RCU_H