cds/container/split_list_set.h

   1 //$$CDS-header$$
   2
   3 #ifndef __CDS_CONTAINER_SPLIT_LIST_SET_H
   4 #define __CDS_CONTAINER_SPLIT_LIST_SET_H
   5
   6 #include <cds/intrusive/split_list.h>
   7 #include <cds/container/details/make_split_list_set.h>
   8 #include <cds/details/functor_wrapper.h>
   9
  10 namespace cds { namespace container {
  11
  12     /// Split-ordered list set
  13     /** @ingroup cds_nonintrusive_set
  14         \anchor cds_nonintrusive_SplitListSet_hp
  15
  16         Hash table implementation based on split-ordered list algorithm discovered by Ori Shalev and Nir Shavit, see
  17         - [2003] Ori Shalev, Nir Shavit "Split-Ordered Lists - Lock-free Resizable Hash Tables"
  18         - [2008] Nir Shavit "The Art of Multiprocessor Programming"
  19
  20         See intrusive::SplitListSet for a brief description of the split-list algorithm.
  21
  22         Template parameters:
  23         - \p GC - Garbage collector used
  24         - \p T - type stored in the split-list. The type must be default- and copy-constructible.
  25         - \p Traits - type traits, default is split_list::type_traits. Instead of declaring split_list::type_traits -based
  26             struct you may apply option-based notation with split_list::make_traits metafunction.
  27
  28         There are the specializations:
  29         - for \ref cds_urcu_desc "RCU" - declared in <tt>cd/container/split_list_set_rcu.h</tt>,
  30             see \ref cds_nonintrusive_SplitListSet_rcu "SplitListSet<RCU>".
  31         - for \ref cds::gc::nogc declared in <tt>cds/container/split_list_set_nogc.h</tt>,
  32             see \ref cds_nonintrusive_SplitListSet_nogc "SplitListSet<gc::nogc>".
  33
  34         \par Usage
  35
  36         You should decide what garbage collector you want, and what ordered list you want to use. Split-ordered list
  37         is original data structure based on an ordered list. Suppose, you want construct split-list set based on gc::PTB GC
  38         and LazyList as ordered list implementation. So, you beginning your program with following include:
  39         \code
  40         #include <cds/container/lazy_list_ptb.h>
  41         #include <cds/container/split_list_set.h>
  42
  43         namespace cc = cds::container;
  44
  45         // The data belonged to split-ordered list
  46         sturuct foo {
  47             int     nKey;   // key field
  48             std::string strValue    ;   // value field
  49         };
  50         \endcode
  51         The inclusion order is important: first, include header for ordered-list implementation (for this example, <tt>cds/container/lazy_list_ptb.h</tt>),
  52         then the header for split-list set <tt>cds/container/split_list_set.h</tt>.
  53
  54         Now, you should declare traits for split-list set. The main parts of traits are a hash functor for the set and a comparing functor for ordered list.
  55         Note that we define several function in <tt>foo_hash</tt> and <tt>foo_less</tt> functors for different argument types since we want call our \p %SplitListSet
  56         object by the key of type <tt>int</tt> and by the value of type <tt>foo</tt>.
  57
  58         The second attention: instead of using \p %LazyList in \p %SplitListSet traits we use a tag <tt>cds::contaner::lazy_list_tag</tt> for the lazy list.
  59         The split-list requires significant support from underlying ordered list class and it is not good idea to dive you
  60         into deep implementation details of split-list and ordered list interrelations. The tag paradigm simplifies split-list interface.
  61
  62         \code
  63         // foo hash functor
  64         struct foo_hash {
  65             size_t operator()( int key ) const { return std::hash( key ) ; }
  66             size_t operator()( foo const& item ) const { return std::hash( item.nKey ) ; }
  67         };
  68
  69         // foo comparator
  70         struct foo_less {
  71             bool operator()(int i, foo const& f ) const { return i < f.nKey ; }
  72             bool operator()(foo const& f, int i ) const { return f.nKey < i ; }
  73             bool operator()(foo const& f1, foo const& f2) const { return f1.nKey < f2.nKey; }
  74         };
  75
  76         // SplitListSet traits
  77         struct foo_set_traits: public cc::split_list::type_traits
  78         {
  79             typedef cc::lazy_list_tag   ordered_list    ;   // what type of ordered list we want to use
  80             typedef foo_hash            hash            ;   // hash functor for our data stored in split-list set
  81
  82             // Type traits for our LazyList class
  83             struct ordered_list_traits: public cc::lazy_list::type_traits
  84             {
  85                 typedef foo_less less   ;   // use our foo_less as comparator to order list nodes
  86             };
  87         };
  88         \endcode
  89
  90         Now you are ready to declare our set class based on \p %SplitListSet:
  91         \code
  92         typedef cc::SplitListSet< cds::gc::PTB, foo, foo_set_traits > foo_set;
  93         \endcode
  94
  95         You may use the modern option-based declaration instead of classic type-traits-based one:
  96         \code
  97         typedef cc:SplitListSet<
  98             cs::gc::PTB             // GC used
  99             ,foo                    // type of data stored
 100             ,cc::split_list::make_traits<      // metafunction to build split-list traits
 101                 cc::split_list::ordered_list<cc::lazy_list_tag>     // tag for underlying ordered list implementation
 102                 ,cc::opt::hash< foo_hash >               // hash functor
 103                 ,cc::split_list::ordered_list_traits<    // ordered list traits desired
 104                     cc::lazy_list::make_traits<    // metafunction to build lazy list traits
 105                         cc::opt::less< foo_less >           // less-based compare functor
 106                     >::type
 107                 >
 108             >::type
 109         >  foo_set;
 110         \endcode
 111         In case of option-based declaration using split_list::make_traits metafunction
 112         the struct \p foo_set_traits is not required.
 113
 114         Now, the set of type \p foo_set is ready to use in your program.
 115
 116         Note that in this example we show only mandatory type_traits parts, optional ones is the default and they are inherited
 117         from cds::container::split_list::type_traits.
 118         The <b>cds</b> library contains many other options for deep tuning of behavior of the split-list and
 119         ordered-list containers.
 120     */
 121     template <
 122         class GC,
 123         class T,
 124 #ifdef CDS_DOXYGEN_INVOKED
 125         class Traits = split_list::type_traits
 126 #else
 127         class Traits
 128 #endif
 129     >
 130     class SplitListSet:
 131 #ifdef CDS_DOXYGEN_INVOKED
 132         protected intrusive::SplitListSet<GC, typename Traits::ordered_list, Traits>
 133 #else
 134         protected details::make_split_list_set< GC, T, typename Traits::ordered_list, split_list::details::wrap_set_traits<T, Traits> >::type
 135 #endif
 136     {
 137     protected:
 138         //@cond
 139         typedef details::make_split_list_set< GC, T, typename Traits::ordered_list, split_list::details::wrap_set_traits<T, Traits> > maker;
 140         typedef typename maker::type  base_class;
 141         //@endcond
 142
 143     public:
 144         typedef Traits                            options         ; ///< \p Traits template argument
 145         typedef typename maker::gc                gc              ; ///< Garbage collector
 146         typedef typename maker::value_type        value_type      ; ///< type of value stored in the list
 147         typedef typename maker::ordered_list      ordered_list    ; ///< Underlying ordered list class
 148         typedef typename base_class::key_comparator key_comparator; ///< key compare functor
 149
 150         /// Hash functor for \p %value_type and all its derivatives that you use
 151         typedef typename base_class::hash           hash;
 152         typedef typename base_class::item_counter   item_counter  ;   ///< Item counter type
 153
 154     protected:
 155         //@cond
 156         typedef typename maker::cxx_node_allocator    cxx_node_allocator;
 157         typedef typename maker::node_type             node_type;
 158         //@endcond
 159
 160     public:
 161         /// Guarded pointer
 162         typedef cds::gc::guarded_ptr< gc, node_type, value_type, details::guarded_ptr_cast_set<node_type, value_type> > guarded_ptr;
 163
 164     protected:
 165         //@cond
 166         template <typename Q>
 167         static node_type * alloc_node(Q const& v )
 168         {
 169             return cxx_node_allocator().New( v );
 170         }
 171
 172         template <typename Q, typename Func>
 173         bool find_( Q& val, Func f )
 174         {
 175 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
 176             return base_class::find( val, [&f]( node_type& item, Q& val ) { cds::unref(f)(item.m_Value, val) ; } );
 177 #       else
 178             find_functor_wrapper<Func> fw(f);
 179             return base_class::find( val, cds::ref(fw) );
 180 #       endif
 181         }
 182
 183         template <typename Q, typename Less, typename Func>
 184         bool find_with_( Q& val, Less pred, Func f )
 185         {
 186 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
 187             return base_class::find_with( val, typename maker::template predicate_wrapper<Less>::type(),
 188                 [&f]( node_type& item, Q& val ) { cds::unref(f)(item.m_Value, val) ; } );
 189 #       else
 190             find_functor_wrapper<Func> fw(f);
 191             return base_class::find_with( val, typename maker::template predicate_wrapper<Less>::type(), cds::ref(fw) );
 192 #       endif
 193         }
 194
 195 #   ifdef CDS_EMPLACE_SUPPORT
 196         template <typename... Args>
 197         static node_type * alloc_node( Args&&... args )
 198         {
 199             return cxx_node_allocator().MoveNew( std::forward<Args>(args)...);
 200         }
 201 #   endif
 202
 203         static void free_node( node_type * pNode )
 204         {
 205             cxx_node_allocator().Delete( pNode );
 206         }
 207
 208         struct node_disposer {
 209             void operator()( node_type * pNode )
 210             {
 211                 free_node( pNode );
 212             }
 213         };
 214         typedef std::unique_ptr< node_type, node_disposer >     scoped_node_ptr;
 215
 216         bool insert_node( node_type * pNode )
 217         {
 218             assert( pNode != nullptr );
 219             scoped_node_ptr p(pNode);
 220
 221             if ( base_class::insert( *pNode ) ) {
 222                 p.release();
 223                 return true;
 224             }
 225
 226             return false;
 227         }
 228
 229         //@endcond
 230
 231     protected:
 232         //@cond
 233 #   ifndef CDS_CXX11_LAMBDA_SUPPORT
 234         template <typename Func>
 235         class insert_functor_wrapper: protected cds::details::functor_wrapper<Func>
 236         {
 237             typedef cds::details::functor_wrapper<Func> base_class;
 238         public:
 239             insert_functor_wrapper( Func f ): base_class(f) {}
 240
 241             void operator()(node_type& node)
 242             {
 243                 base_class::get()( node.m_Value );
 244             }
 245         };
 246
 247         template <typename Func, typename Q>
 248         class ensure_functor_wrapper: protected cds::details::functor_wrapper<Func>
 249         {
 250             typedef cds::details::functor_wrapper<Func> base_class;
 251             Q const&    m_val;
 252         public:
 253             ensure_functor_wrapper( Func f, Q const& v ): base_class(f), m_val(v) {}
 254
 255             void operator()( bool bNew, node_type& item, node_type const& /*val*/ )
 256             {
 257                 base_class::get()( bNew, item.m_Value, m_val );
 258             }
 259         };
 260
 261         template <typename Func>
 262         class find_functor_wrapper: protected cds::details::functor_wrapper<Func>
 263         {
 264             typedef cds::details::functor_wrapper<Func> base_class;
 265         public:
 266             find_functor_wrapper( Func f ): base_class(f) {}
 267
 268             template <typename Q>
 269             void operator()( node_type& item, Q& val )
 270             {
 271                 base_class::get()( item.m_Value, val );
 272             }
 273         };
 274
 275         template <typename Func>
 276         class erase_functor_wrapper: protected cds::details::functor_wrapper<Func>
 277         {
 278             typedef cds::details::functor_wrapper<Func> base_class;
 279         public:
 280             erase_functor_wrapper( Func f ): base_class( f ) {}
 281
 282             void operator()(node_type& node)
 283             {
 284                 base_class::get()( node.m_Value );
 285             }
 286         };
 287 #   endif // ifndef CDS_CXX11_LAMBDA_SUPPORT
 288         //@endcond
 289
 290     protected:
 291         /// Forward iterator
 292         /**
 293             \p IsConst - constness boolean flag
 294
 295             The forward iterator for a split-list has the following features:
 296             - it has no post-increment operator
 297             - it depends on underlying ordered list iterator
 298             - The iterator object cannot be moved across thread boundary since it contains GC's guard that is thread-private GC data.
 299             - Iterator ensures thread-safety even if you delete the item that iterator points to. However, in case of concurrent
 300               deleting operations it is no guarantee that you iterate all item in the split-list.
 301
 302             Therefore, the use of iterators in concurrent environment is not good idea. Use it for debug purpose only.
 303         */
 304         template <bool IsConst>
 305         class iterator_type: protected base_class::template iterator_type<IsConst>
 306         {
 307             //@cond
 308             typedef typename base_class::template iterator_type<IsConst> iterator_base_class;
 309             friend class SplitListSet;
 310             //@endcond
 311         public:
 312             /// Value pointer type (const for const iterator)
 313             typedef typename cds::details::make_const_type<value_type, IsConst>::pointer   value_ptr;
 314             /// Value reference type (const for const iterator)
 315             typedef typename cds::details::make_const_type<value_type, IsConst>::reference value_ref;
 316
 317         public:
 318             /// Default ctor
 319             iterator_type()
 320             {}
 321
 322             /// Copy ctor
 323             iterator_type( iterator_type const& src )
 324                 : iterator_base_class( src )
 325             {}
 326
 327         protected:
 328             //@cond
 329             explicit iterator_type( iterator_base_class const& src )
 330                 : iterator_base_class( src )
 331             {}
 332             //@endcond
 333
 334         public:
 335             /// Dereference operator
 336             value_ptr operator ->() const
 337             {
 338                 return &(iterator_base_class::operator->()->m_Value);
 339             }
 340
 341             /// Dereference operator
 342             value_ref operator *() const
 343             {
 344                 return iterator_base_class::operator*().m_Value;
 345             }
 346
 347             /// Pre-increment
 348             iterator_type& operator ++()
 349             {
 350                 iterator_base_class::operator++();
 351                 return *this;
 352             }
 353
 354             /// Assignment operator
 355             iterator_type& operator = (iterator_type const& src)
 356             {
 357                 iterator_base_class::operator=(src);
 358                 return *this;
 359             }
 360
 361             /// Equality operator
 362             template <bool C>
 363             bool operator ==(iterator_type<C> const& i ) const
 364             {
 365                 return iterator_base_class::operator==(i);
 366             }
 367
 368             /// Equality operator
 369             template <bool C>
 370             bool operator !=(iterator_type<C> const& i ) const
 371             {
 372                 return iterator_base_class::operator!=(i);
 373             }
 374         };
 375
 376     public:
 377         /// Initializes split-ordered list of default capacity
 378         /**
 379             The default capacity is defined in bucket table constructor.
 380             See intrusive::split_list::expandable_bucket_table, intrusive::split_list::static_bucket_table
 381             which selects by intrusive::split_list::dynamic_bucket_table option.
 382         */
 383         SplitListSet()
 384             : base_class()
 385         {}
 386
 387         /// Initializes split-ordered list
 388         SplitListSet(
 389             size_t nItemCount           ///< estimate average of item count
 390             , size_t nLoadFactor = 1    ///< load factor - average item count per bucket. Small integer up to 8, default is 1.
 391             )
 392             : base_class( nItemCount, nLoadFactor )
 393         {}
 394
 395     public:
 396         /// Forward iterator
 397         typedef iterator_type<false>  iterator;
 398
 399         /// Const forward iterator
 400         typedef iterator_type<true>    const_iterator;
 401
 402         /// Returns a forward iterator addressing the first element in a set
 403         /**
 404             For empty set \code begin() == end() \endcode
 405         */
 406         iterator begin()
 407         {
 408             return iterator( base_class::begin() );
 409         }
 410
 411         /// Returns an iterator that addresses the location succeeding the last element in a set
 412         /**
 413             Do not use the value returned by <tt>end</tt> function to access any item.
 414             The returned value can be used only to control reaching the end of the set.
 415             For empty set \code begin() == end() \endcode
 416         */
 417         iterator end()
 418         {
 419             return iterator( base_class::end() );
 420         }
 421
 422         /// Returns a forward const iterator addressing the first element in a set
 423         const_iterator begin() const
 424         {
 425             return const_iterator( base_class::begin() );
 426         }
 427
 428         /// Returns an const iterator that addresses the location succeeding the last element in a set
 429         const_iterator end() const
 430         {
 431             return const_iterator( base_class::end() );
 432         }
 433
 434     public:
 435         /// Inserts new node
 436         /**
 437             The function creates a node with copy of \p val value
 438             and then inserts the node created into the set.
 439
 440             The type \p Q should contain as minimum the complete key for the node.
 441             The object of \ref value_type should be constructible from a value of type \p Q.
 442             In trivial case, \p Q is equal to \ref value_type.
 443
 444             Returns \p true if \p val is inserted into the set, \p false otherwise.
 445         */
 446         template <typename Q>
 447         bool insert( Q const& val )
 448         {
 449             return insert_node( alloc_node( val ) );
 450         }
 451
 452         /// Inserts new node
 453         /**
 454             The function allows to split creating of new item into two part:
 455             - create item with key only
 456             - insert new item into the set
 457             - if inserting is success, calls  \p f functor to initialize value-field of \p val.
 458
 459             The functor signature is:
 460             \code
 461                 void func( value_type& val );
 462             \endcode
 463             where \p val is the item inserted. User-defined functor \p f should guarantee that during changing
 464             \p val no any other changes could be made on this set's item by concurrent threads.
 465             The user-defined functor is called only if the inserting is success. It may be passed by reference
 466             using <tt>boost::ref</tt>
 467         */
 468         template <typename Q, typename Func>
 469         bool insert( Q const& val, Func f )
 470         {
 471             scoped_node_ptr pNode( alloc_node( val ));
 472
 473 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
 474             if ( base_class::insert( *pNode, [&f](node_type& node) { cds::unref(f)( node.m_Value ) ; } ))
 475 #       else
 476             insert_functor_wrapper<Func> fw(f);
 477             if ( base_class::insert( *pNode, cds::ref(fw) ) )
 478 #       endif
 479             {
 480                 pNode.release();
 481                 return true;
 482             }
 483             return false;
 484         }
 485
 486 #   ifdef CDS_EMPLACE_SUPPORT
 487         /// Inserts data of type \p %value_type constructed with <tt>std::forward<Args>(args)...</tt>
 488         /**
 489             Returns \p true if inserting successful, \p false otherwise.
 490
 491             @note This function is available only for compiler that supports
 492             variadic template and move semantics
 493         */
 494         template <typename... Args>
 495         bool emplace( Args&&... args )
 496         {
 497             return insert_node( alloc_node( std::forward<Args>(args)...));
 498         }
 499 #   endif
 500
 501         /// Ensures that the \p item exists in the set
 502         /**
 503             The operation performs inserting or changing data with lock-free manner.
 504
 505             If the \p val key not found in the set, then the new item created from \p val
 506             is inserted into the set. Otherwise, the functor \p func is called with the item found.
 507             The functor \p Func should be a function with signature:
 508             \code
 509                 void func( bool bNew, value_type& item, const Q& val );
 510             \endcode
 511             or a functor:
 512             \code
 513                 struct my_functor {
 514                     void operator()( bool bNew, value_type& item, const Q& val );
 515                 };
 516             \endcode
 517
 518             with arguments:
 519             - \p bNew - \p true if the item has been inserted, \p false otherwise
 520             - \p item - item of the set
 521             - \p val - argument \p val passed into the \p ensure function
 522
 523             The functor may change non-key fields of the \p item; however, \p func must guarantee
 524             that during changing no any other modifications could be made on this item by concurrent threads.
 525
 526             You may pass \p func argument by reference using <tt>boost::ref</tt>.
 527
 528             Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
 529             \p second is true if new item has been added or \p false if the item with \p key
 530             already is in the set.
 531         */
 532         template <typename Q, typename Func>
 533         std::pair<bool, bool> ensure( Q const& val, Func func )
 534         {
 535             scoped_node_ptr pNode( alloc_node( val ));
 536
 537 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
 538             std::pair<bool, bool> bRet = base_class::ensure( *pNode,
 539                 [&func, &val]( bool bNew, node_type& item,  node_type const& /*val*/ ) {
 540                     cds::unref(func)( bNew, item.m_Value, val );
 541                 } );
 542 #       else
 543             ensure_functor_wrapper<Func, Q> fw( func, val );
 544             std::pair<bool, bool> bRet = base_class::ensure( *pNode, cds::ref(fw) );
 545 #       endif
 546
 547             if ( bRet.first && bRet.second )
 548                 pNode.release();
 549             return bRet;
 550         }
 551
 552         /// Deletes \p key from the set
 553         /** \anchor cds_nonintrusive_SplitListSet_erase_val
 554
 555             The item comparator should be able to compare the values of type \p value_type
 556             and the type \p Q.
 557
 558             Return \p true if key is found and deleted, \p false otherwise
 559         */
 560         template <typename Q>
 561         bool erase( Q const& key )
 562         {
 563             return base_class::erase( key );
 564         }
 565
 566         /// Deletes the item from the set using \p pred predicate for searching
 567         /**
 568             The function is an analog of \ref cds_nonintrusive_SplitListSet_erase_val "erase(Q const&)"
 569             but \p pred is used for key comparing.
 570             \p Less functor has the interface like \p std::less.
 571             \p Less must imply the same element order as the comparator used for building the set.
 572         */
 573         template <typename Q, typename Less>
 574         bool erase_with( Q const& key, Less pred )
 575         {
 576             return base_class::erase_with( key, typename maker::template predicate_wrapper<Less>::type() );
 577         }
 578
 579         /// Deletes \p key from the set
 580         /** \anchor cds_nonintrusive_SplitListSet_erase_func
 581
 582             The function searches an item with key \p key, calls \p f functor
 583             and deletes the item. If \p key is not found, the functor is not called.
 584
 585             The functor \p Func interface:
 586             \code
 587             struct extractor {
 588                 void operator()(value_type const& val);
 589             };
 590             \endcode
 591             The functor may be passed by reference using <tt>boost:ref</tt>
 592
 593             Since the key of SplitListSet's \p value_type is not explicitly specified,
 594             template parameter \p Q defines the key type searching in the list.
 595             The list item comparator should be able to compare the values of the type \p value_type
 596             and the type \p Q.
 597
 598             Return \p true if key is found and deleted, \p false otherwise
 599         */
 600         template <typename Q, typename Func>
 601         bool erase( Q const& key, Func f )
 602         {
 603 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
 604             return base_class::erase( key, [&f](node_type& node) { cds::unref(f)( node.m_Value ); } );
 605 #       else
 606             erase_functor_wrapper<Func> fw( f );
 607             return base_class::erase( key, cds::ref(fw) );
 608 #       endif
 609         }
 610
 611         /// Deletes the item from the set using \p pred predicate for searching
 612         /**
 613             The function is an analog of \ref cds_nonintrusive_SplitListSet_erase_func "erase(Q const&, Func)"
 614             but \p pred is used for key comparing.
 615             \p Less functor has the interface like \p std::less.
 616             \p Less must imply the same element order as the comparator used for building the set.
 617         */
 618         template <typename Q, typename Less, typename Func>
 619         bool erase_with( Q const& key, Less pred, Func f )
 620         {
 621 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
 622             return base_class::erase_with( key, typename maker::template predicate_wrapper<Less>::type(),
 623                 [&f](node_type& node) { cds::unref(f)( node.m_Value ); } );
 624 #       else
 625             erase_functor_wrapper<Func> fw( f );
 626             return base_class::erase_with( key, typename maker::template predicate_wrapper<Less>::type(), cds::ref(fw) );
 627 #       endif
 628         }
 629
 630         /// Extracts the item with specified \p key
 631         /** \anchor cds_nonintrusive_SplitListSet_hp_extract
 632             The function searches an item with key equal to \p key,
 633             unlinks it from the set, and returns it in \p dest parameter.
 634             If the item with key equal to \p key is not found the function returns \p false.
 635
 636             Note the compare functor should accept a parameter of type \p Q that may be not the same as \p value_type.
 637
 638             The extracted item is freed automatically when returned \ref guarded_ptr object will be destroyed or released.
 639             @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
 640
 641             Usage:
 642             \code
 643             typedef cds::container::SplitListSet< your_template_args > splitlist_set;
 644             splitlist_set theSet;
 645             // ...
 646             {
 647                 splitlist_set::guarded_ptr gp;
 648                 theSet.extract( gp, 5 );
 649                 // Deal with gp
 650                 // ...
 651
 652                 // Destructor of gp releases internal HP guard
 653             }
 654             \endcode
 655         */
 656         template <typename Q>
 657         bool extract( guarded_ptr& dest, Q const& key )
 658         {
 659             return extract_( dest.guard(), key );
 660         }
 661
 662         /// Extracts the item using compare functor \p pred
 663         /**
 664             The function is an analog of \ref cds_nonintrusive_SplitListSet_hp_extract "extract(guarded_ptr&, Q const&)"
 665             but \p pred predicate is used for key comparing.
 666
 667             \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
 668             in any order.
 669             \p pred must imply the same element order as the comparator used for building the set.
 670         */
 671         template <typename Q, typename Less>
 672         bool extract_with( guarded_ptr& dest, Q const& key, Less pred )
 673         {
 674             return extract_with_( dest.guard(), key, pred );
 675         }
 676
 677         /// Finds the key \p val
 678         /** \anchor cds_nonintrusive_SplitListSet_find_func
 679
 680             The function searches the item with key equal to \p val and calls the functor \p f for item found.
 681             The interface of \p Func functor is:
 682             \code
 683             struct functor {
 684                 void operator()( value_type& item, Q& val );
 685             };
 686             \endcode
 687             where \p item is the item found, \p val is the <tt>find</tt> function argument.
 688
 689             You may pass \p f argument by reference using <tt>boost::ref</tt> or cds::ref.
 690
 691             The functor may change non-key fields of \p item. Note that the functor is only guarantee
 692             that \p item cannot be disposed during functor is executing.
 693             The functor does not serialize simultaneous access to the set's \p item. If such access is
 694             possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
 695
 696             The \p val argument is non-const since it can be used as \p f functor destination i.e., the functor
 697             may modify both arguments.
 698
 699             Note the hash functor specified for class \p Traits template parameter
 700             should accept a parameter of type \p Q that can be not the same as \p value_type.
 701
 702             The function returns \p true if \p val is found, \p false otherwise.
 703         */
 704         template <typename Q, typename Func>
 705         bool find( Q& val, Func f )
 706         {
 707             return find_( val, f );
 708         }
 709
 710         /// Finds the key \p val using \p pred predicate for searching
 711         /**
 712             The function is an analog of \ref cds_nonintrusive_SplitListSet_find_func "find(Q&, Func)"
 713             but \p pred is used for key comparing.
 714             \p Less functor has the interface like \p std::less.
 715             \p Less must imply the same element order as the comparator used for building the set.
 716         */
 717         template <typename Q, typename Less, typename Func>
 718         bool find_with( Q& val, Less pred, Func f )
 719         {
 720             return find_with_( val, pred, f );
 721         }
 722
 723         /// Finds the key \p val
 724         /** \anchor cds_nonintrusive_SplitListSet_find_cfunc
 725
 726             The function searches the item with key equal to \p val and calls the functor \p f for item found.
 727             The interface of \p Func functor is:
 728             \code
 729             struct functor {
 730                 void operator()( value_type& item, Q const& val );
 731             };
 732             \endcode
 733             where \p item is the item found, \p val is the <tt>find</tt> function argument.
 734
 735             You may pass \p f argument by reference using <tt>boost::ref</tt> or cds::ref.
 736
 737             The functor may change non-key fields of \p item. Note that the functor is only guarantee
 738             that \p item cannot be disposed during functor is executing.
 739             The functor does not serialize simultaneous access to the set's \p item. If such access is
 740             possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
 741
 742             Note the hash functor specified for class \p Traits template parameter
 743             should accept a parameter of type \p Q that can be not the same as \p value_type.
 744
 745             The function returns \p true if \p val is found, \p false otherwise.
 746         */
 747         template <typename Q, typename Func>
 748         bool find( Q const& val, Func f )
 749         {
 750             return find_( val, f );
 751         }
 752
 753         /// Finds the key \p val using \p pred predicate for searching
 754         /**
 755             The function is an analog of \ref cds_nonintrusive_SplitListSet_find_cfunc "find(Q const&, Func)"
 756             but \p pred is used for key comparing.
 757             \p Less functor has the interface like \p std::less.
 758             \p Less must imply the same element order as the comparator used for building the set.
 759         */
 760         template <typename Q, typename Less, typename Func>
 761         bool find_with( Q const& val, Less pred, Func f )
 762         {
 763             return find_with_( val, pred, f );
 764         }
 765
 766         /// Finds the key \p val
 767         /** \anchor cds_nonintrusive_SplitListSet_find_val
 768
 769             The function searches the item with key equal to \p val
 770             and returns \p true if it is found, and \p false otherwise.
 771
 772             Note the hash functor specified for class \p Traits template parameter
 773             should accept a parameter of type \p Q that can be not the same as \ref value_type.
 774         */
 775         template <typename Q>
 776         bool find( Q const& val )
 777         {
 778             return base_class::find( val );
 779         }
 780
 781         /// Finds the key \p val using \p pred predicate for searching
 782         /**
 783             The function is an analog of \ref cds_nonintrusive_SplitListSet_find_val "find(Q const&)"
 784             but \p pred is used for key comparing.
 785             \p Less functor has the interface like \p std::less.
 786             \p Less must imply the same element order as the comparator used for building the set.
 787         */
 788         template <typename Q, typename Less>
 789         bool find_with( Q const& val, Less pred )
 790         {
 791             return base_class::find_with( val, typename maker::template predicate_wrapper<Less>::type() );
 792         }
 793
 794         /// Finds the key \p key and return the item found
 795         /** \anchor cds_nonintrusive_SplitListSet_hp_get
 796             The function searches the item with key equal to \p key
 797             and assigns the item found to guarded pointer \p ptr.
 798             The function returns \p true if \p key is found, and \p false otherwise.
 799             If \p key is not found the \p ptr parameter is not changed.
 800
 801             @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
 802
 803             Usage:
 804             \code
 805             typedef cds::container::SplitListSet< your_template_params >  splitlist_set;
 806             splitlist_set theSet;
 807             // ...
 808             {
 809                 splitlist_set::guarded_ptr gp;
 810                 if ( theSet.get( gp, 5 )) {
 811                     // Deal with gp
 812                     //...
 813                 }
 814                 // Destructor of guarded_ptr releases internal HP guard
 815             }
 816             \endcode
 817
 818             Note the compare functor specified for split-list set
 819             should accept a parameter of type \p Q that can be not the same as \p value_type.
 820         */
 821         template <typename Q>
 822         bool get( guarded_ptr& ptr, Q const& key )
 823         {
 824             return get_( ptr.guard(), key );
 825         }
 826
 827         /// Finds \p key and return the item found
 828         /**
 829             The function is an analog of \ref cds_nonintrusive_SplitListSet_hp_get "get( guarded_ptr&, Q const&)"
 830             but \p pred is used for comparing the keys.
 831
 832             \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
 833             in any order.
 834             \p pred must imply the same element order as the comparator used for building the set.
 835         */
 836         template <typename Q, typename Less>
 837         bool get_with( guarded_ptr& ptr, Q const& key, Less pred )
 838         {
 839             return get_with_( ptr.guard(), key, pred );
 840         }
 841
 842         /// Clears the set (non-atomic)
 843         /**
 844             The function unlink all items from the set.
 845             The function is not atomic and not lock-free and should be used for debugging only.
 846         */
 847         void clear()
 848         {
 849             base_class::clear();
 850         }
 851
 852         /// Checks if the set is empty
 853         /**
 854             Emptiness is checked by item counting: if item count is zero then assume that the set is empty.
 855             Thus, the correct item counting feature is an important part of split-list set implementation.
 856         */
 857         bool empty() const
 858         {
 859             return base_class::empty();
 860         }
 861
 862         /// Returns item count in the set
 863         size_t size() const
 864         {
 865             return base_class::size();
 866         }
 867
 868     protected:
 869         //@cond
 870         using base_class::extract_;
 871         using base_class::get_;
 872
 873         template <typename Q, typename Less>
 874         bool extract_with_( typename gc::Guard& guard, Q const& key, Less pred )
 875         {
 876             return base_class::extract_with_( guard, key, typename maker::template predicate_wrapper<Less>::type() );
 877         }
 878
 879         template <typename Q, typename Less>
 880         bool get_with_( typename gc::Guard& guard, Q const& key, Less pred )
 881         {
 882             return base_class::get_with_( guard, key, typename maker::template predicate_wrapper<Less>::type() );
 883         }
 884
 885         //@endcond
 886
 887     };
 888
 889
 890 }}  // namespace cds::container
 891
 892 #endif // #ifndef __CDS_CONTAINER_SPLIT_LIST_SET_H