cds/container/impl/skip_list_set.h

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