cds/container/ellen_bintree_set_rcu.h

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