cds/container/impl/skip_list_set.h

   1 //$$CDS-header$$
   2
   3 #ifndef __CDS_CONTAINER_IMPL_SKIP_LIST_SET_H
   4 #define __CDS_CONTAINER_IMPL_SKIP_LIST_SET_H
   5
   6 #include <cds/details/binary_functor_wrapper.h>
   7 #include <cds/gc/guarded_ptr.h>
   8 #include <cds/container/details/guarded_ptr_cast.h>
   9
  10 namespace cds { namespace container {
  11
  12     /// Lock-free skip-list set
  13     /** @ingroup cds_nonintrusive_set
  14         \anchor cds_nonintrusive_SkipListSet_hp
  15
  16         The implementation of well-known probabilistic data structure called skip-list
  17         invented by W.Pugh in his papers:
  18             - [1989] W.Pugh Skip Lists: A Probabilistic Alternative to Balanced Trees
  19             - [1990] W.Pugh A Skip List Cookbook
  20
  21         A skip-list is a probabilistic data structure that provides expected logarithmic
  22         time search without the need of rebalance. The skip-list is a collection of sorted
  23         linked list. Nodes are ordered by key. Each node is linked into a subset of the lists.
  24         Each list has a level, ranging from 0 to 32. The bottom-level list contains
  25         all the nodes, and each higher-level list is a sublist of the lower-level lists.
  26         Each node is created with a random top level (with a random height), and belongs
  27         to all lists up to that level. The probability that a node has the height 1 is 1/2.
  28         The probability that a node has the height N is 1/2 ** N (more precisely,
  29         the distribution depends on an random generator provided, but our generators
  30         have this property).
  31
  32         The lock-free variant of skip-list is implemented according to book
  33             - [2008] M.Herlihy, N.Shavit "The Art of Multiprocessor Programming",
  34                 chapter 14.4 "A Lock-Free Concurrent Skiplist"
  35
  36         Template arguments:
  37         - \p GC - Garbage collector used.
  38         - \p T - type to be stored in the list.
  39         - \p Traits - type traits. See skip_list::type_traits for explanation.
  40
  41         It is possible to declare option-based list with cds::container::skip_list::make_traits metafunction istead of \p Traits template
  42         argument.
  43         Template argument list \p Options of cds::container::skip_list::make_traits metafunction are:
  44         - opt::compare - key comparison functor. No default functor is provided.
  45             If the option is not specified, the opt::less is used.
  46         - opt::less - specifies binary predicate used for key comparison. Default is \p std::less<T>.
  47         - opt::item_counter - the type of item counting feature. Default is \ref atomicity::empty_item_counter that is no item counting.
  48         - opt::memory_model - C++ memory ordering model. Can be opt::v::relaxed_ordering (relaxed memory model, the default)
  49             or opt::v::sequential_consistent (sequentially consisnent memory model).
  50         - skip_list::random_level_generator - random level generator. Can be skip_list::xorshift, skip_list::turbo_pascal or
  51             user-provided one. See skip_list::random_level_generator option description for explanation.
  52             Default is \p %skip_list::turbo_pascal.
  53         - opt::allocator - allocator for skip-list node. Default is \ref CDS_DEFAULT_ALLOCATOR.
  54         - opt::back_off - back-off strategy used. If the option is not specified, the cds::backoff::Default is used.
  55         - opt::stat - internal statistics. Available types: skip_list::stat, skip_list::empty_stat (the default)
  56
  57         \warning The skip-list requires up to 67 hazard pointers that may be critical for some GCs for which
  58             the guard count is limited (like as \p gc::HP). Those GCs should be explicitly initialized with
  59             hazard pointer enough: \code cds::gc::HP myhp( 67 ) \endcode. Otherwise an run-time exception may be raised
  60             when you try to create skip-list object.
  61
  62         \note There are several specializations of \p %SkipListSet for each \p GC. You should include:
  63         - <tt><cds/container/skip_list_set_hp.h></tt> for gc::HP garbage collector
  64         - <tt><cds/container/skip_list_set_ptb.h></tt> for gc::PTB garbage collector
  65         - <tt><cds/container/skip_list_set_rcu.h></tt> for \ref cds_nonintrusive_SkipListSet_rcu "RCU type"
  66         - <tt><cds/container/skip_list_set_nogc.h></tt> for \ref cds_nonintrusive_SkipListSet_nogc "non-deletable SkipListSet"
  67
  68         <b>Iterators</b>
  69
  70         The class supports a forward iterator (\ref iterator and \ref const_iterator).
  71         The iteration is ordered.
  72         The iterator object is thread-safe: the element pointed by the iterator object is guarded,
  73         so, the element cannot be reclaimed while the iterator object is alive.
  74         However, passing an iterator object between threads is dangerous.
  75
  76         \warning Due to concurrent nature of skip-list set it is not guarantee that you can iterate
  77         all elements in the set: any concurrent deletion can exclude the element
  78         pointed by the iterator from the set, and your iteration can be terminated
  79         before end of the set. Therefore, such iteration is more suitable for debugging purpose only
  80
  81         Remember, each iterator object requires 2 additional hazard pointers, that may be
  82         a limited resource for \p GC like \p gc::HP (for \p gc::PTB the count of
  83         guards is unlimited).
  84
  85         The iterator class supports the following minimalistic interface:
  86         \code
  87         struct iterator {
  88             // Default ctor
  89             iterator();
  90
  91             // Copy ctor
  92             iterator( iterator const& s);
  93
  94             value_type * operator ->() const;
  95             value_type& operator *() const;
  96
  97             // Pre-increment
  98             iterator& operator ++();
  99
 100             // Copy assignment
 101             iterator& operator = (const iterator& src);
 102
 103             bool operator ==(iterator const& i ) const;
 104             bool operator !=(iterator const& i ) const;
 105         };
 106         \endcode
 107         Note, the iterator object returned by \ref end, \p cend member functions points to \p nullptr and should not be dereferenced.
 108
 109     */
 110     template <
 111         typename GC,
 112         typename T,
 113 #ifdef CDS_DOXYGEN_INVOKED
 114         typename Traits = skip_list::type_traits
 115 #else
 116         typename Traits
 117 #endif
 118     >
 119     class SkipListSet:
 120 #ifdef CDS_DOXYGEN_INVOKED
 121         protected intrusive::SkipListSet< GC, T, Traits >
 122 #else
 123         protected details::make_skip_list_set< GC, T, Traits >::type
 124 #endif
 125     {
 126         //@cond
 127         typedef details::make_skip_list_set< GC, T, Traits >    maker;
 128         typedef typename maker::type base_class;
 129         //@endcond
 130     public:
 131         typedef typename base_class::gc          gc  ; ///< Garbage collector used
 132         typedef T       value_type  ;   ///< @anchor cds_containewr_SkipListSet_value_type Value type stored in the set
 133         typedef Traits  options     ;   ///< Options specified
 134
 135         typedef typename base_class::back_off       back_off        ;   ///< Back-off strategy used
 136         typedef typename options::allocator         allocator_type  ;   ///< Allocator type used for allocate/deallocate the skip-list nodes
 137         typedef typename base_class::item_counter   item_counter    ;   ///< Item counting policy used
 138         typedef typename maker::key_comparator      key_comparator  ;   ///< key comparison functor
 139         typedef typename base_class::memory_model   memory_model    ;   ///< Memory ordering. See cds::opt::memory_model option
 140         typedef typename options::random_level_generator random_level_generator ; ///< random level generator
 141         typedef typename options::stat              stat            ;   ///< internal statistics type
 142
 143     protected:
 144         //@cond
 145         typedef typename maker::node_type           node_type;
 146         typedef typename maker::node_allocator      node_allocator;
 147
 148         typedef std::unique_ptr< node_type, typename maker::node_deallocator >    scoped_node_ptr;
 149         //@endcond
 150
 151     public:
 152         /// Guarded pointer
 153         typedef cds::gc::guarded_ptr< gc, node_type, value_type, details::guarded_ptr_cast_set<node_type, value_type> > guarded_ptr;
 154
 155     protected:
 156         //@cond
 157         unsigned int random_level()
 158         {
 159             return base_class::random_level();
 160         }
 161         //@endcond
 162
 163     public:
 164         /// Default ctor
 165         SkipListSet()
 166             : base_class()
 167         {}
 168
 169         /// Destructor destroys the set object
 170         ~SkipListSet()
 171         {}
 172
 173     public:
 174         /// Iterator type
 175         typedef skip_list::details::iterator< typename base_class::iterator >  iterator;
 176
 177         /// Const iterator type
 178         typedef skip_list::details::iterator< typename base_class::const_iterator >   const_iterator;
 179
 180         /// Returns a forward iterator addressing the first element in a set
 181         iterator begin()
 182         {
 183             return iterator( base_class::begin() );
 184         }
 185
 186         /// Returns a forward const iterator addressing the first element in a set
 187         const_iterator begin() const
 188         {
 189             return const_iterator( base_class::begin() );
 190         }
 191
 192         /// Returns a forward const iterator addressing the first element in a set
 193         const_iterator cbegin()
 194         {
 195             return const_iterator( base_class::cbegin() );
 196         }
 197
 198         /// Returns a forward iterator that addresses the location succeeding the last element in a set.
 199         iterator end()
 200         {
 201             return iterator( base_class::end() );
 202         }
 203
 204         /// Returns a forward const iterator that addresses the location succeeding the last element in a set.
 205         const_iterator end() const
 206         {
 207             return const_iterator( base_class::end() );
 208         }
 209
 210         /// Returns a forward const iterator that addresses the location succeeding the last element in a set.
 211         const_iterator cend()
 212         {
 213             return const_iterator( base_class::cend() );
 214         }
 215
 216     public:
 217         /// Inserts new node
 218         /**
 219             The function creates a node with copy of \p val value
 220             and then inserts the node created into the set.
 221
 222             The type \p Q should contain as minimum the complete key for the node.
 223             The object of \ref value_type should be constructible from a value of type \p Q.
 224             In trivial case, \p Q is equal to \ref value_type.
 225
 226             Returns \p true if \p val is inserted into the set, \p false otherwise.
 227         */
 228         template <typename Q>
 229         bool insert( Q const& val )
 230         {
 231             scoped_node_ptr sp( node_allocator().New( random_level(), val ));
 232             if ( base_class::insert( *sp.get() )) {
 233                 sp.release();
 234                 return true;
 235             }
 236             return false;
 237         }
 238
 239         /// Inserts new node
 240         /**
 241             The function allows to split creating of new item into two part:
 242             - create item with key only
 243             - insert new item into the set
 244             - if inserting is success, calls  \p f functor to initialize value-fields of \p val.
 245
 246             The functor signature is:
 247             \code
 248                 void func( value_type& val );
 249             \endcode
 250             where \p val is the item inserted. User-defined functor \p f should guarantee that during changing
 251             \p val no any other changes could be made on this set's item by concurrent threads.
 252             The user-defined functor is called only if the inserting is success. It may be passed by reference
 253             using \p std::ref
 254         */
 255         template <typename Q, typename Func>
 256         bool insert( Q const& val, Func f )
 257         {
 258             scoped_node_ptr sp( node_allocator().New( random_level(), val ));
 259             if ( base_class::insert( *sp.get(), [&f]( node_type& val ) { f( val.m_Value ); } )) {
 260                 sp.release();
 261                 return true;
 262             }
 263             return false;
 264         }
 265
 266         /// Ensures that the item exists in the set
 267         /**
 268             The operation performs inserting or changing data with lock-free manner.
 269
 270             If the \p val key not found in the set, then the new item created from \p val
 271             is inserted into the set. Otherwise, the functor \p func is called with the item found.
 272             The functor \p Func should be a function with signature:
 273             \code
 274                 void func( bool bNew, value_type& item, const Q& val );
 275             \endcode
 276             or a functor:
 277             \code
 278                 struct my_functor {
 279                     void operator()( bool bNew, value_type& item, const Q& val );
 280                 };
 281             \endcode
 282
 283             with arguments:
 284             - \p bNew - \p true if the item has been inserted, \p false otherwise
 285             - \p item - item of the set
 286             - \p val - argument \p key passed into the \p ensure function
 287
 288             The functor may change non-key fields of the \p item; however, \p func must guarantee
 289             that during changing no any other modifications could be made on this item by concurrent threads.
 290
 291             You may pass \p func argument by reference using \p std::ref
 292
 293             Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
 294             \p second is true if new item has been added or \p false if the item with \p key
 295             already is in the set.
 296         */
 297         template <typename Q, typename Func>
 298         std::pair<bool, bool> ensure( const Q& val, Func func )
 299         {
 300             scoped_node_ptr sp( node_allocator().New( random_level(), val ));
 301             std::pair<bool, bool> bRes = base_class::ensure( *sp,
 302                 [&func, &val](bool bNew, node_type& node, node_type&){ func( bNew, node.m_Value, val ); });
 303             if ( bRes.first && bRes.second )
 304                 sp.release();
 305             return bRes;
 306         }
 307
 308         /// Inserts data of type \ref cds_containewr_SkipListSet_value_type "value_type" constructed with <tt>std::forward<Args>(args)...</tt>
 309         /**
 310             Returns \p true if inserting successful, \p false otherwise.
 311         */
 312         template <typename... Args>
 313         bool emplace( Args&&... args )
 314         {
 315             scoped_node_ptr sp( node_allocator().New( random_level(), std::forward<Args>(args)... ));
 316             if ( base_class::insert( *sp.get() )) {
 317                 sp.release();
 318                 return true;
 319             }
 320             return false;
 321         }
 322
 323         /// Delete \p key from the set
 324         /** \anchor cds_nonintrusive_SkipListSet_erase_val
 325
 326             The set item comparator should be able to compare the type \p value_type
 327             and the type \p Q.
 328
 329             Return \p true if key is found and deleted, \p false otherwise
 330         */
 331         template <typename Q>
 332         bool erase( Q const& key )
 333         {
 334             return base_class::erase( key );
 335         }
 336
 337         /// Deletes the item from the set using \p pred predicate for searching
 338         /**
 339             The function is an analog of \ref cds_nonintrusive_SkipListSet_erase_val "erase(Q const&)"
 340             but \p pred is used for key comparing.
 341             \p Less functor has the interface like \p std::less.
 342             \p Less must imply the same element order as the comparator used for building the set.
 343         */
 344         template <typename Q, typename Less>
 345         bool erase_with( Q const& key, Less pred )
 346         {
 347             return base_class::erase_with( key, cds::details::predicate_wrapper< node_type, Less, typename maker::value_accessor >() );
 348         }
 349
 350         /// Delete \p key from the set
 351         /** \anchor cds_nonintrusive_SkipListSet_erase_func
 352
 353             The function searches an item with key \p key, calls \p f functor
 354             and deletes the item. If \p key is not found, the functor is not called.
 355
 356             The functor \p Func interface:
 357             \code
 358             struct extractor {
 359                 void operator()(value_type const& val);
 360             };
 361             \endcode
 362             The functor may be passed by reference using <tt>boost:ref</tt>
 363
 364             Since the key of \p value_type is not explicitly specified,
 365             template parameter \p Q defines the key type to search in the list.
 366             The list item comparator should be able to compare the type \p T of list item
 367             and the type \p Q.
 368
 369             Return \p true if key is found and deleted, \p false otherwise
 370
 371             See also: \ref erase
 372         */
 373         template <typename Q, typename Func>
 374         bool erase( Q const& key, Func f )
 375         {
 376             return base_class::erase( key, [&f]( node_type const& node) { f( node.m_Value ); } );
 377         }
 378
 379         /// Deletes the item from the set using \p pred predicate for searching
 380         /**
 381             The function is an analog of \ref cds_nonintrusive_SkipListSet_erase_func "erase(Q const&, Func)"
 382             but \p pred is used for key comparing.
 383             \p Less functor has the interface like \p std::less.
 384             \p Less must imply the same element order as the comparator used for building the set.
 385         */
 386         template <typename Q, typename Less, typename Func>
 387         bool erase_with( Q const& key, Less pred, Func f )
 388         {
 389             return base_class::erase_with( key, cds::details::predicate_wrapper< node_type, Less, typename maker::value_accessor >(),
 390                 [&f]( node_type const& node) { f( node.m_Value ); } );
 391         }
 392
 393         /// Extracts the item from the set with specified \p key
 394         /** \anchor cds_nonintrusive_SkipListSet_hp_extract
 395             The function searches an item with key equal to \p key in the set,
 396             unlinks it from the set, and returns it in \p result parameter.
 397             If the item with key equal to \p key is not found the function returns \p false.
 398
 399             Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
 400
 401             The item extracted is freed automatically by garbage collector \p GC
 402             when returned \ref guarded_ptr object will be destroyed or released.
 403             @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
 404
 405             Usage:
 406             \code
 407             typedef cds::container::SkipListSet< cds::gc::HP, foo, my_traits >  skip_list;
 408             skip_list theList;
 409             // ...
 410             {
 411                 skip_list::guarded_ptr gp;
 412                 if ( theList.extract( gp, 5 ) ) {
 413                     // Deal with gp
 414                     // ...
 415                 }
 416                 // Destructor of gp releases internal HP guard and frees the pointer
 417             }
 418             \endcode
 419         */
 420         template <typename Q>
 421         bool extract( guarded_ptr& result, Q const& key )
 422         {
 423             return base_class::extract_( result.guard(), key, typename base_class::key_comparator() );
 424         }
 425
 426         /// Extracts the item from the set with comparing functor \p pred
 427         /**
 428             The function is an analog of \ref cds_nonintrusive_SkipListSet_hp_extract "extract(Q const&)"
 429             but \p pred predicate is used for key comparing.
 430
 431             \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
 432             in any order.
 433             \p pred must imply the same element order as the comparator used for building the set.
 434         */
 435         template <typename Q, typename Less>
 436         bool extract_with( guarded_ptr& ptr, Q const& key, Less pred )
 437         {
 438             typedef cds::details::predicate_wrapper< node_type, Less, typename maker::value_accessor >  wrapped_less;
 439             return base_class::extract_( ptr.guard(), key, cds::opt::details::make_comparator_from_less<wrapped_less>() );
 440         }
 441
 442         /// Extracts an item with minimal key from the set
 443         /**
 444             The function searches an item with minimal key, unlinks it, and returns the item found in \p result parameter.
 445             If the skip-list is empty the function returns \p false.
 446
 447             The item extracted is freed automatically by garbage collector \p GC
 448             when returned \ref guarded_ptr object will be destroyed or released.
 449             @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
 450
 451             Usage:
 452             \code
 453             typedef cds::continer::SkipListSet< cds::gc::HP, foo, my_traits >  skip_list;
 454             skip_list theList;
 455             // ...
 456             {
 457                 skip_list::guarded_ptr gp;
 458                 if ( theList.extract_min( gp )) {
 459                     // Deal with gp
 460                     //...
 461                 }
 462                 // Destructor of gp releases internal HP guard and then frees the pointer
 463             }
 464             \endcode
 465         */
 466         bool extract_min( guarded_ptr& result)
 467         {
 468             return base_class::extract_min_( result.guard() );
 469         }
 470
 471         /// Extracts an item with maximal key from the set
 472         /**
 473             The function searches an item with maximal key, unlinks it, and returns the pointer to item found in \p result parameter.
 474             If the skip-list is empty the function returns \p false.
 475
 476             The item found is freed by garbage collector \p GC automatically
 477             when returned \ref guarded_ptr object will be destroyed or released.
 478             @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
 479
 480             Usage:
 481             \code
 482             typedef cds::container::SkipListSet< cds::gc::HP, foo, my_traits >  skip_list;
 483             skip_list theList;
 484             // ...
 485             {
 486                 skip_list::guarded_ptr gp;
 487                 if ( theList.extract_max( gp )) {
 488                     // Deal with gp
 489                     //...
 490                 }
 491                 // Destructor of gp releases internal HP guard and then frees the pointer
 492             }
 493             \endcode
 494         */
 495         bool extract_max( guarded_ptr& result )
 496         {
 497             return base_class::extract_max_( result.guard() );
 498         }
 499
 500         /// Find the key \p val
 501         /** \anchor cds_nonintrusive_SkipListSet_find_func
 502
 503             The function searches the item with key equal to \p val and calls the functor \p f for item found.
 504             The interface of \p Func functor is:
 505             \code
 506             struct functor {
 507                 void operator()( value_type& item, Q& val );
 508             };
 509             \endcode
 510             where \p item is the item found, \p val is the <tt>find</tt> function argument.
 511
 512             You may pass \p f argument by reference using \p std::ref
 513
 514             The functor may change non-key fields of \p item. Note that the functor is only guarantee
 515             that \p item cannot be disposed during functor is executing.
 516             The functor does not serialize simultaneous access to the set's \p item. If such access is
 517             possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
 518
 519             The \p val argument is non-const since it can be used as \p f functor destination i.e., the functor
 520             can modify both arguments.
 521
 522             Note the hash functor specified for class \p Traits template parameter
 523             should accept a parameter of type \p Q that may be not the same as \p value_type.
 524
 525             The function returns \p true if \p val is found, \p false otherwise.
 526         */
 527         template <typename Q, typename Func>
 528         bool find( Q& val, Func f )
 529         {
 530             return base_class::find( val, [&f]( node_type& node, Q& v ) { f( node.m_Value, v ); });
 531         }
 532
 533         /// Finds the key \p val using \p pred predicate for searching
 534         /**
 535             The function is an analog of \ref cds_nonintrusive_SkipListSet_find_func "find(Q&, Func)"
 536             but \p pred is used for key comparing.
 537             \p Less functor has the interface like \p std::less.
 538             \p Less must imply the same element order as the comparator used for building the set.
 539         */
 540         template <typename Q, typename Less, typename Func>
 541         bool find_with( Q& val, Less pred, Func f )
 542         {
 543             return base_class::find_with( val, cds::details::predicate_wrapper< node_type, Less, typename maker::value_accessor >(),
 544                 [&f]( node_type& node, Q& v ) { f( node.m_Value, v ); } );
 545         }
 546
 547         /// Find the key \p val
 548         /** \anchor cds_nonintrusive_SkipListSet_find_cfunc
 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 const& 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 \p std::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             Note the hash functor specified for class \p Traits template parameter
 567             should accept a parameter of type \p Q that may be not the same as \p value_type.
 568
 569             The function returns \p true if \p val is found, \p false otherwise.
 570         */
 571         template <typename Q, typename Func>
 572         bool find( Q const& val, Func f )
 573         {
 574             return base_class::find( val, [&f]( node_type& node, Q const& v ) { f( node.m_Value, v ); });
 575         }
 576
 577         /// Finds the key \p val using \p pred predicate for searching
 578         /**
 579             The function is an analog of \ref cds_nonintrusive_SkipListSet_find_cfunc "find(Q const&, Func)"
 580             but \p pred is used for key comparing.
 581             \p Less functor has the interface like \p std::less.
 582             \p Less must imply the same element order as the comparator used for building the set.
 583         */
 584         template <typename Q, typename Less, typename Func>
 585         bool find_with( Q const& val, Less cmp, Func f )
 586         {
 587             return base_class::find_with( val, cds::details::predicate_wrapper< node_type, Less, typename maker::value_accessor >(),
 588                 [&f]( node_type& node, Q const& v ) { f( node.m_Value, v ); } );
 589         }
 590
 591         /// Find the key \p val
 592         /** \anchor cds_nonintrusive_SkipListSet_find_val
 593
 594             The function searches the item with key equal to \p val
 595             and returns \p true if it is found, and \p false otherwise.
 596
 597             Note the hash functor specified for class \p Traits template parameter
 598             should accept a parameter of type \p Q that may be not the same as \ref value_type.
 599         */
 600         template <typename Q>
 601         bool find( Q const& val )
 602         {
 603             return base_class::find( val );
 604         }
 605
 606         /// Finds the key \p val using \p pred predicate for searching
 607         /**
 608             The function is an analog of \ref cds_nonintrusive_SkipListSet_find_val "find(Q const&)"
 609             but \p pred is used for key comparing.
 610             \p Less functor has the interface like \p std::less.
 611             \p Less must imply the same element order as the comparator used for building the set.
 612         */
 613         template <typename Q, typename Less>
 614         bool find_with( Q const& val, Less pred )
 615         {
 616             return base_class::find_with( val, cds::details::predicate_wrapper< node_type, Less, typename maker::value_accessor >());
 617         }
 618
 619         /// Finds \p key and return the item found
 620         /** \anchor cds_nonintrusive_SkipListSet_hp_get
 621             The function searches the item with key equal to \p key
 622             and assigns the item found to guarded pointer \p result.
 623             The function returns \p true if \p key is found, and \p false otherwise.
 624             If \p key is not found the \p result parameter is left unchanged.
 625
 626             It is safe when a concurrent thread erases the item returned in \p result guarded pointer.
 627             In this case the item will be freed later by garbage collector \p GC automatically
 628             when \p guarded_ptr object will be destroyed or released.
 629             @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
 630
 631             Usage:
 632             \code
 633             typedef cds::container::SkipListSet< cds::gc::HP, foo, my_traits >  skip_list;
 634             skip_list theList;
 635             // ...
 636             {
 637                 skip_list::guarded_ptr gp;
 638                 if ( theList.get( gp, 5 ) ) {
 639                     // Deal with gp
 640                     //...
 641                 }
 642                 // Destructor of guarded_ptr releases internal HP guard
 643             }
 644             \endcode
 645
 646             Note the compare functor specified for class \p Traits template parameter
 647             should accept a parameter of type \p Q that can be not the same as \p value_type.
 648         */
 649         template <typename Q>
 650         bool get( guarded_ptr& result, Q const& key )
 651         {
 652             return base_class::get_with_( result.guard(), key, typename base_class::key_comparator() );
 653         }
 654
 655         /// Finds \p key and return the item found
 656         /**
 657             The function is an analog of \ref cds_nonintrusive_SkipListSet_hp_get "get( guarded_ptr&, Q const&)"
 658             but \p pred is used for comparing the keys.
 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 get_with( guarded_ptr& result, Q const& key, Less pred )
 666         {
 667             typedef cds::details::predicate_wrapper< node_type, Less, typename maker::value_accessor >  wrapped_less;
 668             return base_class::get_with_( result.guard(), key, cds::opt::details::make_comparator_from_less< wrapped_less >());
 669         }
 670
 671         /// Clears the set (non-atomic).
 672         /**
 673             The function deletes all items from the set.
 674             The function is not atomic, thus, in multi-threaded environment with parallel insertions
 675             this sequence
 676             \code
 677             set.clear();
 678             assert( set.empty() );
 679             \endcode
 680             the assertion could be raised.
 681
 682             For each item the \ref disposer provided by \p Traits template parameter will be called.
 683         */
 684         void clear()
 685         {
 686             base_class::clear();
 687         }
 688
 689         /// Checks if the set is empty
 690         bool empty() const
 691         {
 692             return base_class::empty();
 693         }
 694
 695         /// Returns item count in the set
 696         /**
 697             The value returned depends on item counter type provided by \p Traits template parameter.
 698             If it is atomicity::empty_item_counter this function always returns 0.
 699             Therefore, the function is not suitable for checking the set emptiness, use \ref empty
 700             member function for this purpose.
 701         */
 702         size_t size() const
 703         {
 704             return base_class::size();
 705         }
 706
 707         /// Returns const reference to internal statistics
 708         stat const& statistics() const
 709         {
 710             return base_class::statistics();
 711         }
 712
 713     };
 714
 715 }} // namespace cds::container
 716
 717 #endif // #ifndef __CDS_CONTAINER_IMPL_SKIP_LIST_SET_H