cds/container/impl/skip_list_set.h

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