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         template <typename... Args>
 196         static node_type * alloc_node( Args&&... args )
 197         {
 198             return cxx_node_allocator().MoveNew( std::forward<Args>(args)...);
 199         }
 200
 201         static void free_node( node_type * pNode )
 202         {
 203             cxx_node_allocator().Delete( pNode );
 204         }
 205
 206         struct node_disposer {
 207             void operator()( node_type * pNode )
 208             {
 209                 free_node( pNode );
 210             }
 211         };
 212         typedef std::unique_ptr< node_type, node_disposer >     scoped_node_ptr;
 213
 214         bool insert_node( node_type * pNode )
 215         {
 216             assert( pNode != nullptr );
 217             scoped_node_ptr p(pNode);
 218
 219             if ( base_class::insert( *pNode ) ) {
 220                 p.release();
 221                 return true;
 222             }
 223
 224             return false;
 225         }
 226
 227         //@endcond
 228
 229     protected:
 230         //@cond
 231 #   ifndef CDS_CXX11_LAMBDA_SUPPORT
 232         template <typename Func>
 233         class insert_functor_wrapper: protected cds::details::functor_wrapper<Func>
 234         {
 235             typedef cds::details::functor_wrapper<Func> base_class;
 236         public:
 237             insert_functor_wrapper( Func f ): base_class(f) {}
 238
 239             void operator()(node_type& node)
 240             {
 241                 base_class::get()( node.m_Value );
 242             }
 243         };
 244
 245         template <typename Func, typename Q>
 246         class ensure_functor_wrapper: protected cds::details::functor_wrapper<Func>
 247         {
 248             typedef cds::details::functor_wrapper<Func> base_class;
 249             Q const&    m_val;
 250         public:
 251             ensure_functor_wrapper( Func f, Q const& v ): base_class(f), m_val(v) {}
 252
 253             void operator()( bool bNew, node_type& item, node_type const& /*val*/ )
 254             {
 255                 base_class::get()( bNew, item.m_Value, m_val );
 256             }
 257         };
 258
 259         template <typename Func>
 260         class find_functor_wrapper: protected cds::details::functor_wrapper<Func>
 261         {
 262             typedef cds::details::functor_wrapper<Func> base_class;
 263         public:
 264             find_functor_wrapper( Func f ): base_class(f) {}
 265
 266             template <typename Q>
 267             void operator()( node_type& item, Q& val )
 268             {
 269                 base_class::get()( item.m_Value, val );
 270             }
 271         };
 272
 273         template <typename Func>
 274         class erase_functor_wrapper: protected cds::details::functor_wrapper<Func>
 275         {
 276             typedef cds::details::functor_wrapper<Func> base_class;
 277         public:
 278             erase_functor_wrapper( Func f ): base_class( f ) {}
 279
 280             void operator()(node_type& node)
 281             {
 282                 base_class::get()( node.m_Value );
 283             }
 284         };
 285 #   endif // ifndef CDS_CXX11_LAMBDA_SUPPORT
 286         //@endcond
 287
 288     protected:
 289         /// Forward iterator
 290         /**
 291             \p IsConst - constness boolean flag
 292
 293             The forward iterator for a split-list has the following features:
 294             - it has no post-increment operator
 295             - it depends on underlying ordered list iterator
 296             - The iterator object cannot be moved across thread boundary since it contains GC's guard that is thread-private GC data.
 297             - Iterator ensures thread-safety even if you delete the item that iterator points to. However, in case of concurrent
 298               deleting operations it is no guarantee that you iterate all item in the split-list.
 299
 300             Therefore, the use of iterators in concurrent environment is not good idea. Use it for debug purpose only.
 301         */
 302         template <bool IsConst>
 303         class iterator_type: protected base_class::template iterator_type<IsConst>
 304         {
 305             //@cond
 306             typedef typename base_class::template iterator_type<IsConst> iterator_base_class;
 307             friend class SplitListSet;
 308             //@endcond
 309         public:
 310             /// Value pointer type (const for const iterator)
 311             typedef typename cds::details::make_const_type<value_type, IsConst>::pointer   value_ptr;
 312             /// Value reference type (const for const iterator)
 313             typedef typename cds::details::make_const_type<value_type, IsConst>::reference value_ref;
 314
 315         public:
 316             /// Default ctor
 317             iterator_type()
 318             {}
 319
 320             /// Copy ctor
 321             iterator_type( iterator_type const& src )
 322                 : iterator_base_class( src )
 323             {}
 324
 325         protected:
 326             //@cond
 327             explicit iterator_type( iterator_base_class const& src )
 328                 : iterator_base_class( src )
 329             {}
 330             //@endcond
 331
 332         public:
 333             /// Dereference operator
 334             value_ptr operator ->() const
 335             {
 336                 return &(iterator_base_class::operator->()->m_Value);
 337             }
 338
 339             /// Dereference operator
 340             value_ref operator *() const
 341             {
 342                 return iterator_base_class::operator*().m_Value;
 343             }
 344
 345             /// Pre-increment
 346             iterator_type& operator ++()
 347             {
 348                 iterator_base_class::operator++();
 349                 return *this;
 350             }
 351
 352             /// Assignment operator
 353             iterator_type& operator = (iterator_type const& src)
 354             {
 355                 iterator_base_class::operator=(src);
 356                 return *this;
 357             }
 358
 359             /// Equality operator
 360             template <bool C>
 361             bool operator ==(iterator_type<C> const& i ) const
 362             {
 363                 return iterator_base_class::operator==(i);
 364             }
 365
 366             /// Equality operator
 367             template <bool C>
 368             bool operator !=(iterator_type<C> const& i ) const
 369             {
 370                 return iterator_base_class::operator!=(i);
 371             }
 372         };
 373
 374     public:
 375         /// Initializes split-ordered list of default capacity
 376         /**
 377             The default capacity is defined in bucket table constructor.
 378             See intrusive::split_list::expandable_bucket_table, intrusive::split_list::static_bucket_table
 379             which selects by intrusive::split_list::dynamic_bucket_table option.
 380         */
 381         SplitListSet()
 382             : base_class()
 383         {}
 384
 385         /// Initializes split-ordered list
 386         SplitListSet(
 387             size_t nItemCount           ///< estimate average of item count
 388             , size_t nLoadFactor = 1    ///< load factor - average item count per bucket. Small integer up to 8, default is 1.
 389             )
 390             : base_class( nItemCount, nLoadFactor )
 391         {}
 392
 393     public:
 394         /// Forward iterator
 395         typedef iterator_type<false>  iterator;
 396
 397         /// Const forward iterator
 398         typedef iterator_type<true>    const_iterator;
 399
 400         /// Returns a forward iterator addressing the first element in a set
 401         /**
 402             For empty set \code begin() == end() \endcode
 403         */
 404         iterator begin()
 405         {
 406             return iterator( base_class::begin() );
 407         }
 408
 409         /// Returns an iterator that addresses the location succeeding the last element in a set
 410         /**
 411             Do not use the value returned by <tt>end</tt> function to access any item.
 412             The returned value can be used only to control reaching the end of the set.
 413             For empty set \code begin() == end() \endcode
 414         */
 415         iterator end()
 416         {
 417             return iterator( base_class::end() );
 418         }
 419
 420         /// Returns a forward const iterator addressing the first element in a set
 421         const_iterator begin() const
 422         {
 423             return const_iterator( base_class::begin() );
 424         }
 425
 426         /// Returns an const iterator that addresses the location succeeding the last element in a set
 427         const_iterator end() const
 428         {
 429             return const_iterator( base_class::end() );
 430         }
 431
 432     public:
 433         /// Inserts new node
 434         /**
 435             The function creates a node with copy of \p val value
 436             and then inserts the node created into the set.
 437
 438             The type \p Q should contain as minimum the complete key for the node.
 439             The object of \ref value_type should be constructible from a value of type \p Q.
 440             In trivial case, \p Q is equal to \ref value_type.
 441
 442             Returns \p true if \p val is inserted into the set, \p false otherwise.
 443         */
 444         template <typename Q>
 445         bool insert( Q const& val )
 446         {
 447             return insert_node( alloc_node( val ) );
 448         }
 449
 450         /// Inserts new node
 451         /**
 452             The function allows to split creating of new item into two part:
 453             - create item with key only
 454             - insert new item into the set
 455             - if inserting is success, calls  \p f functor to initialize value-field of \p val.
 456
 457             The functor signature is:
 458             \code
 459                 void func( value_type& val );
 460             \endcode
 461             where \p val is the item inserted. User-defined functor \p f should guarantee that during changing
 462             \p val no any other changes could be made on this set's item by concurrent threads.
 463             The user-defined functor is called only if the inserting is success. It may be passed by reference
 464             using <tt>boost::ref</tt>
 465         */
 466         template <typename Q, typename Func>
 467         bool insert( Q const& val, Func f )
 468         {
 469             scoped_node_ptr pNode( alloc_node( val ));
 470
 471 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
 472             if ( base_class::insert( *pNode, [&f](node_type& node) { cds::unref(f)( node.m_Value ) ; } ))
 473 #       else
 474             insert_functor_wrapper<Func> fw(f);
 475             if ( base_class::insert( *pNode, cds::ref(fw) ) )
 476 #       endif
 477             {
 478                 pNode.release();
 479                 return true;
 480             }
 481             return false;
 482         }
 483
 484         /// Inserts data of type \p %value_type constructed with <tt>std::forward<Args>(args)...</tt>
 485         /**
 486             Returns \p true if inserting successful, \p false otherwise.
 487         */
 488         template <typename... Args>
 489         bool emplace( Args&&... args )
 490         {
 491             return insert_node( alloc_node( std::forward<Args>(args)...));
 492         }
 493
 494         /// Ensures that the \p item exists in the set
 495         /**
 496             The operation performs inserting or changing data with lock-free manner.
 497
 498             If the \p val key not found in the set, then the new item created from \p val
 499             is inserted into the set. Otherwise, the functor \p func is called with the item found.
 500             The functor \p Func should be a function with signature:
 501             \code
 502                 void func( bool bNew, value_type& item, const Q& val );
 503             \endcode
 504             or a functor:
 505             \code
 506                 struct my_functor {
 507                     void operator()( bool bNew, value_type& item, const Q& val );
 508                 };
 509             \endcode
 510
 511             with arguments:
 512             - \p bNew - \p true if the item has been inserted, \p false otherwise
 513             - \p item - item of the set
 514             - \p val - argument \p val passed into the \p ensure function
 515
 516             The functor may change non-key fields of the \p item; however, \p func must guarantee
 517             that during changing no any other modifications could be made on this item by concurrent threads.
 518
 519             You may pass \p func argument by reference using <tt>boost::ref</tt>.
 520
 521             Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
 522             \p second is true if new item has been added or \p false if the item with \p key
 523             already is in the set.
 524         */
 525         template <typename Q, typename Func>
 526         std::pair<bool, bool> ensure( Q const& val, Func func )
 527         {
 528             scoped_node_ptr pNode( alloc_node( val ));
 529
 530 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
 531             std::pair<bool, bool> bRet = base_class::ensure( *pNode,
 532                 [&func, &val]( bool bNew, node_type& item,  node_type const& /*val*/ ) {
 533                     cds::unref(func)( bNew, item.m_Value, val );
 534                 } );
 535 #       else
 536             ensure_functor_wrapper<Func, Q> fw( func, val );
 537             std::pair<bool, bool> bRet = base_class::ensure( *pNode, cds::ref(fw) );
 538 #       endif
 539
 540             if ( bRet.first && bRet.second )
 541                 pNode.release();
 542             return bRet;
 543         }
 544
 545         /// Deletes \p key from the set
 546         /** \anchor cds_nonintrusive_SplitListSet_erase_val
 547
 548             The item comparator should be able to compare the values of type \p value_type
 549             and the type \p Q.
 550
 551             Return \p true if key is found and deleted, \p false otherwise
 552         */
 553         template <typename Q>
 554         bool erase( Q const& key )
 555         {
 556             return base_class::erase( key );
 557         }
 558
 559         /// Deletes the item from the set using \p pred predicate for searching
 560         /**
 561             The function is an analog of \ref cds_nonintrusive_SplitListSet_erase_val "erase(Q const&)"
 562             but \p pred is used for key comparing.
 563             \p Less functor has the interface like \p std::less.
 564             \p Less must imply the same element order as the comparator used for building the set.
 565         */
 566         template <typename Q, typename Less>
 567         bool erase_with( Q const& key, Less pred )
 568         {
 569             return base_class::erase_with( key, typename maker::template predicate_wrapper<Less>::type() );
 570         }
 571
 572         /// Deletes \p key from the set
 573         /** \anchor cds_nonintrusive_SplitListSet_erase_func
 574
 575             The function searches an item with key \p key, calls \p f functor
 576             and deletes the item. If \p key is not found, the functor is not called.
 577
 578             The functor \p Func interface:
 579             \code
 580             struct extractor {
 581                 void operator()(value_type const& val);
 582             };
 583             \endcode
 584             The functor may be passed by reference using <tt>boost:ref</tt>
 585
 586             Since the key of SplitListSet's \p value_type is not explicitly specified,
 587             template parameter \p Q defines the key type searching in the list.
 588             The list item comparator should be able to compare the values of the type \p value_type
 589             and the type \p Q.
 590
 591             Return \p true if key is found and deleted, \p false otherwise
 592         */
 593         template <typename Q, typename Func>
 594         bool erase( Q const& key, Func f )
 595         {
 596 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
 597             return base_class::erase( key, [&f](node_type& node) { cds::unref(f)( node.m_Value ); } );
 598 #       else
 599             erase_functor_wrapper<Func> fw( f );
 600             return base_class::erase( key, cds::ref(fw) );
 601 #       endif
 602         }
 603
 604         /// Deletes the item from the set using \p pred predicate for searching
 605         /**
 606             The function is an analog of \ref cds_nonintrusive_SplitListSet_erase_func "erase(Q const&, Func)"
 607             but \p pred is used for key comparing.
 608             \p Less functor has the interface like \p std::less.
 609             \p Less must imply the same element order as the comparator used for building the set.
 610         */
 611         template <typename Q, typename Less, typename Func>
 612         bool erase_with( Q const& key, Less pred, Func f )
 613         {
 614 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
 615             return base_class::erase_with( key, typename maker::template predicate_wrapper<Less>::type(),
 616                 [&f](node_type& node) { cds::unref(f)( node.m_Value ); } );
 617 #       else
 618             erase_functor_wrapper<Func> fw( f );
 619             return base_class::erase_with( key, typename maker::template predicate_wrapper<Less>::type(), cds::ref(fw) );
 620 #       endif
 621         }
 622
 623         /// Extracts the item with specified \p key
 624         /** \anchor cds_nonintrusive_SplitListSet_hp_extract
 625             The function searches an item with key equal to \p key,
 626             unlinks it from the set, and returns it in \p dest parameter.
 627             If the item with key equal to \p key is not found the function returns \p false.
 628
 629             Note the compare functor should accept a parameter of type \p Q that may be not the same as \p value_type.
 630
 631             The extracted item is freed automatically when returned \ref guarded_ptr object will be destroyed or released.
 632             @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
 633
 634             Usage:
 635             \code
 636             typedef cds::container::SplitListSet< your_template_args > splitlist_set;
 637             splitlist_set theSet;
 638             // ...
 639             {
 640                 splitlist_set::guarded_ptr gp;
 641                 theSet.extract( gp, 5 );
 642                 // Deal with gp
 643                 // ...
 644
 645                 // Destructor of gp releases internal HP guard
 646             }
 647             \endcode
 648         */
 649         template <typename Q>
 650         bool extract( guarded_ptr& dest, Q const& key )
 651         {
 652             return extract_( dest.guard(), key );
 653         }
 654
 655         /// Extracts the item using compare functor \p pred
 656         /**
 657             The function is an analog of \ref cds_nonintrusive_SplitListSet_hp_extract "extract(guarded_ptr&, Q const&)"
 658             but \p pred predicate is used for key comparing.
 659
 660             \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
 661             in any order.
 662             \p pred must imply the same element order as the comparator used for building the set.
 663         */
 664         template <typename Q, typename Less>
 665         bool extract_with( guarded_ptr& dest, Q const& key, Less pred )
 666         {
 667             return extract_with_( dest.guard(), key, pred );
 668         }
 669
 670         /// Finds the key \p val
 671         /** \anchor cds_nonintrusive_SplitListSet_find_func
 672
 673             The function searches the item with key equal to \p val and calls the functor \p f for item found.
 674             The interface of \p Func functor is:
 675             \code
 676             struct functor {
 677                 void operator()( value_type& item, Q& val );
 678             };
 679             \endcode
 680             where \p item is the item found, \p val is the <tt>find</tt> function argument.
 681
 682             You may pass \p f argument by reference using <tt>boost::ref</tt> or cds::ref.
 683
 684             The functor may change non-key fields of \p item. Note that the functor is only guarantee
 685             that \p item cannot be disposed during functor is executing.
 686             The functor does not serialize simultaneous access to the set's \p item. If such access is
 687             possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
 688
 689             The \p val argument is non-const since it can be used as \p f functor destination i.e., the functor
 690             may modify both arguments.
 691
 692             Note the hash functor specified for class \p Traits template parameter
 693             should accept a parameter of type \p Q that can be not the same as \p value_type.
 694
 695             The function returns \p true if \p val is found, \p false otherwise.
 696         */
 697         template <typename Q, typename Func>
 698         bool find( Q& val, Func f )
 699         {
 700             return find_( val, f );
 701         }
 702
 703         /// Finds the key \p val using \p pred predicate for searching
 704         /**
 705             The function is an analog of \ref cds_nonintrusive_SplitListSet_find_func "find(Q&, Func)"
 706             but \p pred is used for key comparing.
 707             \p Less functor has the interface like \p std::less.
 708             \p Less must imply the same element order as the comparator used for building the set.
 709         */
 710         template <typename Q, typename Less, typename Func>
 711         bool find_with( Q& val, Less pred, Func f )
 712         {
 713             return find_with_( val, pred, f );
 714         }
 715
 716         /// Finds the key \p val
 717         /** \anchor cds_nonintrusive_SplitListSet_find_cfunc
 718
 719             The function searches the item with key equal to \p val and calls the functor \p f for item found.
 720             The interface of \p Func functor is:
 721             \code
 722             struct functor {
 723                 void operator()( value_type& item, Q const& val );
 724             };
 725             \endcode
 726             where \p item is the item found, \p val is the <tt>find</tt> function argument.
 727
 728             You may pass \p f argument by reference using <tt>boost::ref</tt> or cds::ref.
 729
 730             The functor may change non-key fields of \p item. Note that the functor is only guarantee
 731             that \p item cannot be disposed during functor is executing.
 732             The functor does not serialize simultaneous access to the set's \p item. If such access is
 733             possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
 734
 735             Note the hash functor specified for class \p Traits template parameter
 736             should accept a parameter of type \p Q that can be not the same as \p value_type.
 737
 738             The function returns \p true if \p val is found, \p false otherwise.
 739         */
 740         template <typename Q, typename Func>
 741         bool find( Q const& val, Func f )
 742         {
 743             return find_( val, f );
 744         }
 745
 746         /// Finds the key \p val using \p pred predicate for searching
 747         /**
 748             The function is an analog of \ref cds_nonintrusive_SplitListSet_find_cfunc "find(Q const&, Func)"
 749             but \p pred is used for key comparing.
 750             \p Less functor has the interface like \p std::less.
 751             \p Less must imply the same element order as the comparator used for building the set.
 752         */
 753         template <typename Q, typename Less, typename Func>
 754         bool find_with( Q const& val, Less pred, Func f )
 755         {
 756             return find_with_( val, pred, f );
 757         }
 758
 759         /// Finds the key \p val
 760         /** \anchor cds_nonintrusive_SplitListSet_find_val
 761
 762             The function searches the item with key equal to \p val
 763             and returns \p true if it is found, and \p false otherwise.
 764
 765             Note the hash functor specified for class \p Traits template parameter
 766             should accept a parameter of type \p Q that can be not the same as \ref value_type.
 767         */
 768         template <typename Q>
 769         bool find( Q const& val )
 770         {
 771             return base_class::find( val );
 772         }
 773
 774         /// Finds the key \p val using \p pred predicate for searching
 775         /**
 776             The function is an analog of \ref cds_nonintrusive_SplitListSet_find_val "find(Q const&)"
 777             but \p pred is used for key comparing.
 778             \p Less functor has the interface like \p std::less.
 779             \p Less must imply the same element order as the comparator used for building the set.
 780         */
 781         template <typename Q, typename Less>
 782         bool find_with( Q const& val, Less pred )
 783         {
 784             return base_class::find_with( val, typename maker::template predicate_wrapper<Less>::type() );
 785         }
 786
 787         /// Finds the key \p key and return the item found
 788         /** \anchor cds_nonintrusive_SplitListSet_hp_get
 789             The function searches the item with key equal to \p key
 790             and assigns the item found to guarded pointer \p ptr.
 791             The function returns \p true if \p key is found, and \p false otherwise.
 792             If \p key is not found the \p ptr parameter is not changed.
 793
 794             @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
 795
 796             Usage:
 797             \code
 798             typedef cds::container::SplitListSet< your_template_params >  splitlist_set;
 799             splitlist_set theSet;
 800             // ...
 801             {
 802                 splitlist_set::guarded_ptr gp;
 803                 if ( theSet.get( gp, 5 )) {
 804                     // Deal with gp
 805                     //...
 806                 }
 807                 // Destructor of guarded_ptr releases internal HP guard
 808             }
 809             \endcode
 810
 811             Note the compare functor specified for split-list set
 812             should accept a parameter of type \p Q that can be not the same as \p value_type.
 813         */
 814         template <typename Q>
 815         bool get( guarded_ptr& ptr, Q const& key )
 816         {
 817             return get_( ptr.guard(), key );
 818         }
 819
 820         /// Finds \p key and return the item found
 821         /**
 822             The function is an analog of \ref cds_nonintrusive_SplitListSet_hp_get "get( guarded_ptr&, Q const&)"
 823             but \p pred is used for comparing the keys.
 824
 825             \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
 826             in any order.
 827             \p pred must imply the same element order as the comparator used for building the set.
 828         */
 829         template <typename Q, typename Less>
 830         bool get_with( guarded_ptr& ptr, Q const& key, Less pred )
 831         {
 832             return get_with_( ptr.guard(), key, pred );
 833         }
 834
 835         /// Clears the set (non-atomic)
 836         /**
 837             The function unlink all items from the set.
 838             The function is not atomic and not lock-free and should be used for debugging only.
 839         */
 840         void clear()
 841         {
 842             base_class::clear();
 843         }
 844
 845         /// Checks if the set is empty
 846         /**
 847             Emptiness is checked by item counting: if item count is zero then assume that the set is empty.
 848             Thus, the correct item counting feature is an important part of split-list set implementation.
 849         */
 850         bool empty() const
 851         {
 852             return base_class::empty();
 853         }
 854
 855         /// Returns item count in the set
 856         size_t size() const
 857         {
 858             return base_class::size();
 859         }
 860
 861     protected:
 862         //@cond
 863         using base_class::extract_;
 864         using base_class::get_;
 865
 866         template <typename Q, typename Less>
 867         bool extract_with_( typename gc::Guard& guard, Q const& key, Less pred )
 868         {
 869             return base_class::extract_with_( guard, key, typename maker::template predicate_wrapper<Less>::type() );
 870         }
 871
 872         template <typename Q, typename Less>
 873         bool get_with_( typename gc::Guard& guard, Q const& key, Less pred )
 874         {
 875             return base_class::get_with_( guard, key, typename maker::template predicate_wrapper<Less>::type() );
 876         }
 877
 878         //@endcond
 879
 880     };
 881
 882
 883 }}  // namespace cds::container
 884
 885 #endif // #ifndef __CDS_CONTAINER_SPLIT_LIST_SET_H