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         //@cond
 128         typedef cds::container::skip_list::implementation_tag implementation_tag;
 129         //@endcond
 130
 131     protected:
 132         //@cond
 133         typedef typename maker::node_type           node_type;
 134         typedef typename maker::node_allocator      node_allocator;
 135
 136         typedef std::unique_ptr< node_type, typename maker::node_deallocator >    scoped_node_ptr;
 137         //@endcond
 138
 139     public:
 140         /// Guarded pointer
 141         typedef typename gc::template guarded_ptr< node_type, value_type, details::guarded_ptr_cast_set<node_type, value_type> > guarded_ptr;
 142
 143     protected:
 144         //@cond
 145         unsigned int random_level()
 146         {
 147             return base_class::random_level();
 148         }
 149         //@endcond
 150
 151     public:
 152         /// Default ctor
 153         SkipListSet()
 154             : base_class()
 155         {}
 156
 157         /// Destructor destroys the set object
 158         ~SkipListSet()
 159         {}
 160
 161     public:
 162         /// Iterator type
 163         typedef skip_list::details::iterator< typename base_class::iterator >  iterator;
 164
 165         /// Const iterator type
 166         typedef skip_list::details::iterator< typename base_class::const_iterator >   const_iterator;
 167
 168         /// Returns a forward iterator addressing the first element in a set
 169         iterator begin()
 170         {
 171             return iterator( base_class::begin() );
 172         }
 173
 174         /// Returns a forward const iterator addressing the first element in a set
 175         const_iterator begin() const
 176         {
 177             return const_iterator( base_class::begin() );
 178         }
 179
 180         /// Returns a forward const iterator addressing the first element in a set
 181         const_iterator cbegin() const
 182         {
 183             return const_iterator( base_class::cbegin() );
 184         }
 185
 186         /// Returns a forward iterator that addresses the location succeeding the last element in a set.
 187         iterator end()
 188         {
 189             return iterator( base_class::end() );
 190         }
 191
 192         /// Returns a forward const iterator that addresses the location succeeding the last element in a set.
 193         const_iterator end() const
 194         {
 195             return const_iterator( base_class::end() );
 196         }
 197
 198         /// Returns a forward const iterator that addresses the location succeeding the last element in a set.
 199         const_iterator cend() const
 200         {
 201             return const_iterator( base_class::cend() );
 202         }
 203
 204     public:
 205         /// Inserts new node
 206         /**
 207             The function creates a node with copy of \p val value
 208             and then inserts the node created into the set.
 209
 210             The type \p Q should contain as minimum the complete key for the node.
 211             The object of \ref value_type should be constructible from a value of type \p Q.
 212             In trivial case, \p Q is equal to \ref value_type.
 213
 214             Returns \p true if \p val is inserted into the set, \p false otherwise.
 215         */
 216         template <typename Q>
 217         bool insert( Q const& val )
 218         {
 219             scoped_node_ptr sp( node_allocator().New( random_level(), val ));
 220             if ( base_class::insert( *sp.get() )) {
 221                 sp.release();
 222                 return true;
 223             }
 224             return false;
 225         }
 226
 227         /// Inserts new node
 228         /**
 229             The function allows to split creating of new item into two part:
 230             - create item with key only
 231             - insert new item into the set
 232             - if inserting is success, calls  \p f functor to initialize value-fields of \p val.
 233
 234             The functor signature is:
 235             \code
 236                 void func( value_type& val );
 237             \endcode
 238             where \p val is the item inserted. User-defined functor \p f should guarantee that during changing
 239             \p val no any other changes could be made on this set's item by concurrent threads.
 240             The user-defined functor is called only if the inserting is success.
 241         */
 242         template <typename Q, typename Func>
 243         bool insert( Q const& val, Func f )
 244         {
 245             scoped_node_ptr sp( node_allocator().New( random_level(), val ));
 246             if ( base_class::insert( *sp.get(), [&f]( node_type& val ) { f( val.m_Value ); } )) {
 247                 sp.release();
 248                 return true;
 249             }
 250             return false;
 251         }
 252
 253         /// Updates the item
 254         /**
 255             The operation performs inserting or changing data with lock-free manner.
 256
 257             If the \p val key not found in the set, then the new item created from \p val
 258             will be inserted into the set iff \p bInsert is \p true.
 259             Otherwise, if \p val is found, the functor \p func will be called with the item found.
 260
 261             The functor \p Func signature:
 262             \code
 263                 struct my_functor {
 264                     void operator()( bool bNew, value_type& item, const Q& val );
 265                 };
 266             \endcode
 267             where:
 268             - \p bNew - \p true if the item has been inserted, \p false otherwise
 269             - \p item - item of the set
 270             - \p val - argument \p key passed into the \p %update() function
 271
 272             The functor may change non-key fields of the \p item; however, \p func must guarantee
 273             that during changing no any other modifications could be made on this item by concurrent threads.
 274
 275             Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successfull,
 276             i.e. the item has been inserted or updated,
 277             \p second is \p true if new item has been added or \p false if the item with key equal to \p val
 278             already exists.
 279
 280             @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
 281         */
 282         template <typename Q, typename Func>
 283         std::pair<bool, bool> update( const Q& val, Func func, bool bInsert = true )
 284         {
 285             scoped_node_ptr sp( node_allocator().New( random_level(), val ));
 286             std::pair<bool, bool> bRes = base_class::update( *sp,
 287                 [&func, &val](bool bNew, node_type& node, node_type&){ func( bNew, node.m_Value, val ); },
 288                 bInsert );
 289             if ( bRes.first && bRes.second )
 290                 sp.release();
 291             return bRes;
 292         }
 293
 294         //@cond
 295         // Deprecated, use update()
 296         template <typename Q, typename Func>
 297         std::pair<bool, bool> ensure( const Q& val, Func func )
 298         {
 299             return update( val, func, true );
 300         }
 301         //@endcond
 302
 303         /// Inserts data of type \p value_type created in-place from <tt>std::forward<Args>(args)...</tt>
 304         /**
 305             Returns \p true if inserting successful, \p false otherwise.
 306         */
 307         template <typename... Args>
 308         bool emplace( Args&&... args )
 309         {
 310             scoped_node_ptr sp( node_allocator().New( random_level(), std::forward<Args>(args)... ));
 311             if ( base_class::insert( *sp.get() )) {
 312                 sp.release();
 313                 return true;
 314             }
 315             return false;
 316         }
 317
 318         /// Delete \p key from the set
 319         /** \anchor cds_nonintrusive_SkipListSet_erase_val
 320
 321             The set item comparator should be able to compare the type \p value_type
 322             and the type \p Q.
 323
 324             Return \p true if key is found and deleted, \p false otherwise
 325         */
 326         template <typename Q>
 327         bool erase( Q const& key )
 328         {
 329             return base_class::erase( key );
 330         }
 331
 332         /// Deletes the item from the set using \p pred predicate for searching
 333         /**
 334             The function is an analog of \ref cds_nonintrusive_SkipListSet_erase_val "erase(Q const&)"
 335             but \p pred is used for key comparing.
 336             \p Less functor has the interface like \p std::less.
 337             \p Less must imply the same element order as the comparator used for building the set.
 338         */
 339         template <typename Q, typename Less>
 340         bool erase_with( Q const& key, Less pred )
 341         {
 342             CDS_UNUSED( pred );
 343             return base_class::erase_with( key, cds::details::predicate_wrapper< node_type, Less, typename maker::value_accessor >() );
 344         }
 345
 346         /// Delete \p key from the set
 347         /** \anchor cds_nonintrusive_SkipListSet_erase_func
 348
 349             The function searches an item with key \p key, calls \p f functor
 350             and deletes the item. If \p key is not found, the functor is not called.
 351
 352             The functor \p Func interface:
 353             \code
 354             struct extractor {
 355                 void operator()(value_type const& val);
 356             };
 357             \endcode
 358
 359             Since the key of \p value_type is not explicitly specified,
 360             template parameter \p Q defines the key type to search in the list.
 361             The list item comparator should be able to compare the type \p T of list item
 362             and the type \p Q.
 363
 364             Return \p true if key is found and deleted, \p false otherwise
 365         */
 366         template <typename Q, typename Func>
 367         bool erase( Q const& key, Func f )
 368         {
 369             return base_class::erase( key, [&f]( node_type const& node) { f( node.m_Value ); } );
 370         }
 371
 372         /// Deletes the item from the set using \p pred predicate for searching
 373         /**
 374             The function is an analog of \ref cds_nonintrusive_SkipListSet_erase_func "erase(Q const&, Func)"
 375             but \p pred is used for key comparing.
 376             \p Less functor has the interface like \p std::less.
 377             \p Less must imply the same element order as the comparator used for building the set.
 378         */
 379         template <typename Q, typename Less, typename Func>
 380         bool erase_with( Q const& key, Less pred, Func f )
 381         {
 382             CDS_UNUSED( pred );
 383             return base_class::erase_with( key, cds::details::predicate_wrapper< node_type, Less, typename maker::value_accessor >(),
 384                 [&f]( node_type const& node) { f( node.m_Value ); } );
 385         }
 386
 387         /// Extracts the item from the set with specified \p key
 388         /** \anchor cds_nonintrusive_SkipListSet_hp_extract
 389             The function searches an item with key equal to \p key in the set,
 390             unlinks it from the set, and returns it as \p guarded_ptr.
 391             If \p key is not found the function returns an empty guarded pointer.
 392
 393             Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
 394
 395             The item extracted is freed automatically by garbage collector \p GC
 396             when returned \p guarded_ptr object will be destroyed or released.
 397             @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
 398
 399             Usage:
 400             \code
 401             typedef cds::container::SkipListSet< cds::gc::HP, foo, my_traits >  skip_list;
 402             skip_list theList;
 403             // ...
 404             {
 405                 skip_list::guarded_ptr gp(theList.extract( 5 ))
 406                 if (  gp ) {
 407                     // Deal with gp
 408                     // ...
 409                 }
 410                 // Destructor of gp releases internal HP guard and frees the pointer
 411             }
 412             \endcode
 413         */
 414         template <typename Q>
 415         guarded_ptr extract( Q const& key )
 416         {
 417             guarded_ptr gp;
 418             base_class::extract_( gp.guard(), key, typename base_class::key_comparator() );
 419             return gp;
 420         }
 421
 422         /// Extracts the item from the set with comparing functor \p pred
 423         /**
 424             The function is an analog of \ref cds_nonintrusive_SkipListSet_hp_extract "extract(Q const&)"
 425             but \p pred predicate is used for key comparing.
 426
 427             \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
 428             in any order.
 429             \p pred must imply the same element order as the comparator used for building the set.
 430         */
 431         template <typename Q, typename Less>
 432         guarded_ptr extract_with( Q const& key, Less pred )
 433         {
 434             CDS_UNUSED( pred );
 435             typedef cds::details::predicate_wrapper< node_type, Less, typename maker::value_accessor >  wrapped_less;
 436             guarded_ptr gp;
 437             base_class::extract_( gp.guard(), key, cds::opt::details::make_comparator_from_less<wrapped_less>() );
 438             return gp;
 439         }
 440
 441         /// Extracts an item with minimal key from the set
 442         /**
 443             The function searches an item with minimal key, unlinks it, and returns pointer to the item found as \p guarded_ptr.
 444             If the skip-list is empty the function returns an empty guarded pointer.
 445
 446             The item extracted is freed automatically by garbage collector \p GC
 447             when returned \p guarded_ptr object will be destroyed or released.
 448             @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
 449
 450             Usage:
 451             \code
 452             typedef cds::continer::SkipListSet< cds::gc::HP, foo, my_traits >  skip_list;
 453             skip_list theList;
 454             // ...
 455             {
 456                 skip_list::guarded_ptr gp( theList.extract_min());
 457                 if ( gp ) {
 458                     // Deal with gp
 459                     //...
 460                 }
 461                 // Destructor of gp releases internal HP guard and then frees the pointer
 462             }
 463             \endcode
 464         */
 465         guarded_ptr extract_min()
 466         {
 467             guarded_ptr gp;
 468             base_class::extract_min_( gp.guard() );
 469             return gp;
 470         }
 471
 472         /// Extracts an item with maximal key from the set
 473         /**
 474             The function searches an item with maximal key, unlinks it, and returns the pointer to item found as \p guarded_ptr.
 475             If the skip-list is empty the function returns an empty guarded pointer.
 476
 477             The item found is freed by garbage collector \p GC automatically
 478             when returned \p guarded_ptr object will be destroyed or released.
 479             @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
 480
 481             Usage:
 482             \code
 483             typedef cds::container::SkipListSet< cds::gc::HP, foo, my_traits >  skip_list;
 484             skip_list theList;
 485             // ...
 486             {
 487                 skip_list::guarded_ptr gp( theList.extract_max());
 488                 if ( gp ) {
 489                     // Deal with gp
 490                     //...
 491                 }
 492                 // Destructor of gp releases internal HP guard and then frees the pointer
 493             }
 494             \endcode
 495         */
 496         guarded_ptr extract_max()
 497         {
 498             guarded_ptr gp;
 499             base_class::extract_max_( gp.guard() );
 500             return gp;
 501         }
 502
 503         /// Find the \p key
 504         /** \anchor cds_nonintrusive_SkipListSet_find_func
 505
 506             The function searches the item with key equal to \p key and calls the functor \p f for item found.
 507             The interface of \p Func functor is:
 508             \code
 509             struct functor {
 510                 void operator()( value_type& item, Q& key );
 511             };
 512             \endcode
 513             where \p item is the item found, \p key is the <tt>find</tt> function argument.
 514
 515             The functor may change non-key fields of \p item. Note that the functor is only guarantee
 516             that \p item cannot be disposed during functor is executing.
 517             The functor does not serialize simultaneous access to the set's \p item. If such access is
 518             possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
 519
 520             Note the hash functor specified for class \p Traits template parameter
 521             should accept a parameter of type \p Q that may be not the same as \p value_type.
 522
 523             The function returns \p true if \p key is found, \p false otherwise.
 524         */
 525         template <typename Q, typename Func>
 526         bool find( Q& key, Func f )
 527         {
 528             return base_class::find( key, [&f]( node_type& node, Q& v ) { f( node.m_Value, v ); });
 529         }
 530         //@cond
 531         template <typename Q, typename Func>
 532         bool find( Q const& key, Func f )
 533         {
 534             return base_class::find( key, [&f]( node_type& node, Q& v ) { f( node.m_Value, v ); } );
 535         }
 536         //@endcond
 537
 538         /// Finds \p key using \p pred predicate for searching
 539         /**
 540             The function is an analog of \ref cds_nonintrusive_SkipListSet_find_func "find(Q&, Func)"
 541             but \p pred is used for key comparing.
 542             \p Less functor has the interface like \p std::less.
 543             \p Less must imply the same element order as the comparator used for building the set.
 544         */
 545         template <typename Q, typename Less, typename Func>
 546         bool find_with( Q& key, Less pred, Func f )
 547         {
 548             CDS_UNUSED( pred );
 549             return base_class::find_with( key, cds::details::predicate_wrapper< node_type, Less, typename maker::value_accessor >(),
 550                 [&f]( node_type& node, Q& v ) { f( node.m_Value, v ); } );
 551         }
 552         //@cond
 553         template <typename Q, typename Less, typename Func>
 554         bool find_with( Q const& key, Less pred, Func f )
 555         {
 556             CDS_UNUSED( pred );
 557             return base_class::find_with( key, cds::details::predicate_wrapper< node_type, Less, typename maker::value_accessor >(),
 558                                           [&f]( node_type& node, Q& v ) { f( node.m_Value, v ); } );
 559         }
 560         //@endcond
 561
 562         /// Find \p key
 563         /** \anchor cds_nonintrusive_SkipListSet_find_val
 564
 565             The function searches the item with key equal to \p key
 566             and returns \p true if it is found, and \p false otherwise.
 567
 568             Note the hash functor specified for class \p Traits template parameter
 569             should accept a parameter of type \p Q that may be not the same as \ref value_type.
 570         */
 571         template <typename Q>
 572         bool find( Q const& key )
 573         {
 574             return base_class::find( key );
 575         }
 576
 577         /// Finds \p key using \p pred predicate for searching
 578         /**
 579             The function is an analog of \ref cds_nonintrusive_SkipListSet_find_val "find(Q const&)"
 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>
 585         bool find_with( Q const& key, Less pred )
 586         {
 587             CDS_UNUSED( pred );
 588             return base_class::find_with( key, cds::details::predicate_wrapper< node_type, Less, typename maker::value_accessor >());
 589         }
 590
 591         /// Finds \p key and return the item found
 592         /** \anchor cds_nonintrusive_SkipListSet_hp_get
 593             The function searches the item with key equal to \p key
 594             and returns a guarded pointer to the item found.
 595             If \p key is not found the function returns an empty guarded pointer.
 596
 597             It is safe when a concurrent thread erases the item returned in \p result guarded pointer.
 598             In this case the item will be freed later by garbage collector \p GC automatically
 599             when \p guarded_ptr object will be destroyed or released.
 600             @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
 601
 602             Usage:
 603             \code
 604             typedef cds::container::SkipListSet< cds::gc::HP, foo, my_traits >  skip_list;
 605             skip_list theList;
 606             // ...
 607             {
 608                 skip_list::guarded_ptr gp( theList.get( 5 ));
 609                 if ( theList.get( 5 )) {
 610                     // Deal with gp
 611                     //...
 612                 }
 613                 // Destructor of guarded_ptr releases internal HP guard
 614             }
 615             \endcode
 616
 617             Note the compare functor specified for class \p Traits template parameter
 618             should accept a parameter of type \p Q that can be not the same as \p value_type.
 619         */
 620         template <typename Q>
 621         guarded_ptr get( Q const& key )
 622         {
 623             guarded_ptr gp;
 624             base_class::get_with_( gp.guard(), key, typename base_class::key_comparator() );
 625             return gp;
 626         }
 627
 628         /// Finds \p key and return the item found
 629         /**
 630             The function is an analog of \ref cds_nonintrusive_SkipListSet_hp_get "get(Q const&)"
 631             but \p pred is used for comparing the keys.
 632
 633             \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
 634             in any order.
 635             \p pred must imply the same element order as the comparator used for building the set.
 636         */
 637         template <typename Q, typename Less>
 638         guarded_ptr get_with( Q const& key, Less pred )
 639         {
 640             CDS_UNUSED( pred );
 641             typedef cds::details::predicate_wrapper< node_type, Less, typename maker::value_accessor >  wrapped_less;
 642             guarded_ptr gp;
 643             base_class::get_with_( gp.guard(), key, cds::opt::details::make_comparator_from_less< wrapped_less >());
 644             return gp;
 645         }
 646
 647         /// Clears the set (not atomic).
 648         /**
 649             The function deletes all items from the set.
 650             The function is not atomic, thus, in multi-threaded environment with parallel insertions
 651             this sequence
 652             \code
 653             set.clear();
 654             assert( set.empty() );
 655             \endcode
 656             the assertion could be raised.
 657
 658             For each item the \ref disposer provided by \p Traits template parameter will be called.
 659         */
 660         void clear()
 661         {
 662             base_class::clear();
 663         }
 664
 665         /// Checks if the set is empty
 666         bool empty() const
 667         {
 668             return base_class::empty();
 669         }
 670
 671         /// Returns item count in the set
 672         /**
 673             The value returned depends on item counter type provided by \p Traits template parameter.
 674             If it is \p atomicity::empty_item_counter this function always returns 0.
 675             Therefore, the function is not suitable for checking the set emptiness, use \p empty()
 676             member function for this purpose.
 677         */
 678         size_t size() const
 679         {
 680             return base_class::size();
 681         }
 682
 683         /// Returns const reference to internal statistics
 684         stat const& statistics() const
 685         {
 686             return base_class::statistics();
 687         }
 688     };
 689
 690 }} // namespace cds::container
 691
 692 #endif // #ifndef CDSLIB_CONTAINER_IMPL_SKIP_LIST_SET_H