cds/container/skip_list_set_rcu.h

   1 //$$CDS-header$$
   2
   3 #ifndef __CDS_CONTAINER_SKIP_LIST_SET_RCU_H
   4 #define __CDS_CONTAINER_SKIP_LIST_SET_RCU_H
   5
   6 #include <cds/intrusive/skip_list_rcu.h>
   7 #include <cds/container/details/make_skip_list_set.h>
   8
   9 namespace cds { namespace container {
  10
  11     /// Lock-free skip-list set (template specialization for \ref cds_urcu_desc "RCU")
  12     /** @ingroup cds_nonintrusive_set
  13         \anchor cds_nonintrusive_SkipListSet_rcu
  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 RCU - one of \ref cds_urcu_gc "RCU type".
  37         - \p T - type to be stored in the list.
  38         - \p Traits - set traits, default is skip_list::traits for explanation.
  39
  40         It is possible to declare option-based list with cds::container::skip_list::make_traits metafunction istead of \p Traits template
  41         argument.
  42         Template argument list \p Options of cds::container::skip_list::make_traits metafunction are:
  43         - opt::compare - key comparison functor. No default functor is provided.
  44             If the option is not specified, the opt::less is used.
  45         - opt::less - specifies binary predicate used for key comparison. Default is \p std::less<T>.
  46         - opt::item_counter - the type of item counting feature. Default is \ref atomicity::empty_item_counter that is no item counting.
  47         - opt::memory_model - C++ memory ordering model. Can be opt::v::relaxed_ordering (relaxed memory model, the default)
  48             or opt::v::sequential_consistent (sequentially consisnent memory model).
  49         - skip_list::random_level_generator - random level generator. Can be skip_list::xorshift, skip_list::turbo_pascal or
  50             user-provided one. See skip_list::random_level_generator option description for explanation.
  51             Default is \p %skip_list::turbo_pascal.
  52         - opt::allocator - allocator for skip-list node. Default is \ref CDS_DEFAULT_ALLOCATOR.
  53         - opt::back_off - back-off strategy used. If the option is not specified, the cds::backoff::Default is used.
  54         - opt::stat - internal statistics. Available types: skip_list::stat, skip_list::empty_stat (the default)
  55         - opt::rcu_check_deadlock - a deadlock checking policy. Default is opt::v::rcu_throw_deadlock
  56
  57         @note Before including <tt><cds/container/skip_list_set_rcu.h></tt> you should include appropriate RCU header file,
  58         see \ref cds_urcu_gc "RCU type" for list of existing RCU class and corresponding header files.
  59
  60         <b>Iterators</b>
  61
  62         The class supports a forward iterator (\ref iterator and \ref const_iterator).
  63         The iteration is ordered.
  64
  65         You may iterate over skip-list set items only under RCU lock.
  66         Only in this case the iterator is thread-safe since
  67         while RCU is locked any set's item cannot be reclaimed.
  68
  69         The requirement of RCU lock during iterating means that deletion of the elements (i.e. \ref erase)
  70         is not possible.
  71
  72         @warning The iterator object cannot be passed between threads
  73
  74         Example how to use skip-list set iterators:
  75         \code
  76         // First, you should include the header for RCU type you have chosen
  77         #include <cds/urcu/general_buffered.h>
  78         #include <cds/container/skip_list_set_rcu.h>
  79
  80         typedef cds::urcu::gc< cds::urcu::general_buffered<> > rcu_type;
  81
  82         struct Foo {
  83             // ...
  84         };
  85
  86         // Traits for your skip-list.
  87         // At least, you should define cds::opt::less or cds::opt::compare for Foo struct
  88         struct my_traits: public cds::continer::skip_list::traits
  89         {
  90             // ...
  91         };
  92         typedef cds::container::SkipListSet< rcu_type, Foo, my_traits > my_skiplist_set;
  93
  94         my_skiplist_set theSet;
  95
  96         // ...
  97
  98         // Begin iteration
  99         {
 100             // Apply RCU locking manually
 101             typename rcu_type::scoped_lock sl;
 102
 103             for ( auto it = theList.begin(); it != theList.end(); ++it ) {
 104                 // ...
 105             }
 106
 107             // rcu_type::scoped_lock destructor releases RCU lock implicitly
 108         }
 109         \endcode
 110
 111         \warning Due to concurrent nature of skip-list set it is not guarantee that you can iterate
 112         all elements in the set: any concurrent deletion can exclude the element
 113         pointed by the iterator from the set, and your iteration can be terminated
 114         before end of the set. Therefore, such iteration is more suitable for debugging purposes
 115
 116         The iterator class supports the following minimalistic interface:
 117         \code
 118         struct iterator {
 119             // Default ctor
 120             iterator();
 121
 122             // Copy ctor
 123             iterator( iterator const& s);
 124
 125             value_type * operator ->() const;
 126             value_type& operator *() const;
 127
 128             // Pre-increment
 129             iterator& operator ++();
 130
 131             // Copy assignment
 132             iterator& operator = (const iterator& src);
 133
 134             bool operator ==(iterator const& i ) const;
 135             bool operator !=(iterator const& i ) const;
 136         };
 137         \endcode
 138         Note, the iterator object returned by \ref end, \p cend member functions points to \p nullptr and should not be dereferenced.
 139     */
 140     template <
 141         typename RCU,
 142         typename T,
 143 #ifdef CDS_DOXYGEN_INVOKED
 144         typename Traits = skip_list::traits
 145 #else
 146         typename Traits
 147 #endif
 148     >
 149     class SkipListSet< cds::urcu::gc< RCU >, T, Traits >:
 150 #ifdef CDS_DOXYGEN_INVOKED
 151         protected intrusive::SkipListSet< cds::urcu::gc< RCU >, T, Traits >
 152 #else
 153         protected details::make_skip_list_set< cds::urcu::gc< RCU >, T, Traits >::type
 154 #endif
 155     {
 156         //@cond
 157         typedef details::make_skip_list_set< cds::urcu::gc< RCU >, T, Traits >    maker;
 158         typedef typename maker::type base_class;
 159         //@endcond
 160     public:
 161         typedef typename base_class::gc gc  ; ///< Garbage collector used
 162         typedef T       value_type  ;   ///< Value type stored in the set
 163         typedef Traits  traits     ;   ///< Options specified
 164
 165         typedef typename base_class::back_off       back_off        ;   ///< Back-off strategy used
 166         typedef typename traits::allocator         allocator_type  ;   ///< Allocator type used for allocate/deallocate the skip-list nodes
 167         typedef typename base_class::item_counter   item_counter    ;   ///< Item counting policy used
 168         typedef typename maker::key_comparator      key_comparator  ;   ///< key compare functor
 169         typedef typename base_class::memory_model   memory_model    ;   ///< Memory ordering. See cds::opt::memory_model option
 170         typedef typename traits::random_level_generator random_level_generator ; ///< random level generator
 171         typedef typename traits::stat              stat            ;   ///< internal statistics type
 172         typedef typename traits::rcu_check_deadlock    rcu_check_deadlock ; ///< Deadlock checking policy
 173
 174     protected:
 175         //@cond
 176         typedef typename maker::node_type           node_type;
 177         typedef typename maker::node_allocator      node_allocator;
 178
 179         typedef std::unique_ptr< node_type, typename maker::node_deallocator >    scoped_node_ptr;
 180         //@endcond
 181
 182     public:
 183         typedef typename base_class::rcu_lock  rcu_lock;   ///< RCU scoped lock
 184         /// Group of \p extract_xxx functions do not require external locking
 185         static CDS_CONSTEXPR const bool c_bExtractLockExternal = base_class::c_bExtractLockExternal;
 186
 187         /// pointer to extracted node
 188         using exempt_ptr = cds::urcu::exempt_ptr< gc, node_type, value_type, typename maker::intrusive_traits::disposer >;
 189
 190     protected:
 191         //@cond
 192         unsigned int random_level()
 193         {
 194             return base_class::random_level();
 195         }
 196
 197         value_type * to_value_ptr( node_type * pNode ) const CDS_NOEXCEPT
 198         {
 199             return pNode ? &pNode->m_Value : nullptr;
 200         }
 201         //@endcond
 202
 203     public:
 204         /// Default ctor
 205         SkipListSet()
 206             : base_class()
 207         {}
 208
 209         /// Destructor destroys the set object
 210         ~SkipListSet()
 211         {}
 212
 213     public:
 214         /// Iterator type
 215         typedef skip_list::details::iterator< typename base_class::iterator >  iterator;
 216
 217         /// Const iterator type
 218         typedef skip_list::details::iterator< typename base_class::const_iterator >   const_iterator;
 219
 220         /// Returns a forward iterator addressing the first element in a set
 221         iterator begin()
 222         {
 223             return iterator( base_class::begin() );
 224         }
 225
 226         /// Returns a forward const iterator addressing the first element in a set
 227         //@{
 228         const_iterator begin() const
 229         {
 230             return const_iterator( base_class::begin() );
 231         }
 232         const_iterator cbegin() const
 233         {
 234             return const_iterator( base_class::cbegin() );
 235         }
 236         //@}
 237
 238         /// Returns a forward iterator that addresses the location succeeding the last element in a set.
 239         iterator end()
 240         {
 241             return iterator( base_class::end() );
 242         }
 243
 244         /// Returns a forward const iterator that addresses the location succeeding the last element in a set.
 245         //@{
 246         const_iterator end() const
 247         {
 248             return const_iterator( base_class::end() );
 249         }
 250         const_iterator cend() const
 251         {
 252             return const_iterator( base_class::cend() );
 253         }
 254         //@}
 255
 256     public:
 257         /// Inserts new node
 258         /**
 259             The function creates a node with copy of \p val value
 260             and then inserts the node created into the set.
 261
 262             The type \p Q should contain as minimum the complete key for the node.
 263             The object of \ref value_type should be constructible from a value of type \p Q.
 264             In trivial case, \p Q is equal to \ref value_type.
 265
 266             RCU \p synchronize method can be called. RCU should not be locked.
 267
 268             Returns \p true if \p val is inserted into the set, \p false otherwise.
 269         */
 270         template <typename Q>
 271         bool insert( Q const& val )
 272         {
 273             scoped_node_ptr sp( node_allocator().New( random_level(), val ));
 274             if ( base_class::insert( *sp.get() )) {
 275                 sp.release();
 276                 return true;
 277             }
 278             return false;
 279         }
 280
 281         /// Inserts new node
 282         /**
 283             The function allows to split creating of new item into two part:
 284             - create item with key only
 285             - insert new item into the set
 286             - if inserting is success, calls  \p f functor to initialize value-fields of \p val.
 287
 288             The functor signature is:
 289             \code
 290                 void func( value_type& val );
 291             \endcode
 292             where \p val is the item inserted. User-defined functor \p f should guarantee that during changing
 293             \p val no any other changes could be made on this set's item by concurrent threads.
 294             The user-defined functor is called only if the inserting is success.
 295
 296             RCU \p synchronize method can be called. RCU should not be locked.
 297         */
 298         template <typename Q, typename Func>
 299         bool insert( Q const& val, Func f )
 300         {
 301             scoped_node_ptr sp( node_allocator().New( random_level(), val ));
 302             if ( base_class::insert( *sp.get(), [&f]( node_type& val ) { f( val.m_Value ); } )) {
 303                 sp.release();
 304                 return true;
 305             }
 306             return false;
 307         }
 308
 309         /// Ensures that the item exists in the set
 310         /**
 311             The operation performs inserting or changing data with lock-free manner.
 312
 313             If the \p val key not found in the set, then the new item created from \p val
 314             is inserted into the set. Otherwise, the functor \p func is called with the item found.
 315             The functor \p Func should be a function with signature:
 316             \code
 317                 void func( bool bNew, value_type& item, const Q& val );
 318             \endcode
 319             or a functor:
 320             \code
 321                 struct my_functor {
 322                     void operator()( bool bNew, value_type& item, const Q& val );
 323                 };
 324             \endcode
 325
 326             with arguments:
 327             - \p bNew - \p true if the item has been inserted, \p false otherwise
 328             - \p item - item of the set
 329             - \p val - argument \p key passed into the \p ensure function
 330
 331             The functor may change non-key fields of the \p item; however, \p func must guarantee
 332             that during changing no any other modifications could be made on this item by concurrent threads.
 333
 334             RCU \p synchronize method can be called. RCU should not be locked.
 335
 336             Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
 337             \p second is true if new item has been added or \p false if the item with \p key
 338             already is in the set.
 339         */
 340         template <typename Q, typename Func>
 341         std::pair<bool, bool> ensure( const Q& val, Func func )
 342         {
 343             scoped_node_ptr sp( node_allocator().New( random_level(), val ));
 344             std::pair<bool, bool> bRes = base_class::ensure( *sp,
 345                 [&func, &val](bool bNew, node_type& node, node_type&){ func( bNew, node.m_Value, val ); });
 346             if ( bRes.first && bRes.second )
 347                 sp.release();
 348             return bRes;
 349         }
 350
 351         /// Inserts data of type \ref value_type constructed with <tt>std::forward<Args>(args)...</tt>
 352         /**
 353             Returns \p true if inserting successful, \p false otherwise.
 354
 355             RCU \p synchronize method can be called. RCU should not be locked.
 356         */
 357         template <typename... Args>
 358         bool emplace( Args&&... args )
 359         {
 360             scoped_node_ptr sp( node_allocator().New( random_level(), std::forward<Args>(args)... ));
 361             if ( base_class::insert( *sp.get() )) {
 362                 sp.release();
 363                 return true;
 364             }
 365             return false;
 366         }
 367
 368         /// Delete \p key from the set
 369         /** \anchor cds_nonintrusive_SkipListSet_rcu_erase_val
 370
 371             The item comparator should be able to compare the type \p value_type
 372             and the type \p Q.
 373
 374             RCU \p synchronize method can be called. RCU should not be locked.
 375
 376             Return \p true if key is found and deleted, \p false otherwise
 377         */
 378         template <typename Q>
 379         bool erase( Q const& key )
 380         {
 381             return base_class::erase( key );
 382         }
 383
 384         /// Deletes the item from the set using \p pred predicate for searching
 385         /**
 386             The function is an analog of \ref cds_nonintrusive_SkipListSet_rcu_erase_val "erase(Q const&)"
 387             but \p pred is used for key comparing.
 388             \p Less functor has the interface like \p std::less.
 389             \p Less must imply the same element order as the comparator used for building the set.
 390         */
 391         template <typename Q, typename Less>
 392         bool erase_with( Q const& key, Less pred )
 393         {
 394             return base_class::erase_with( key, cds::details::predicate_wrapper< node_type, Less, typename maker::value_accessor >());
 395         }
 396
 397         /// Delete \p key from the set
 398         /** \anchor cds_nonintrusive_SkipListSet_rcu_erase_func
 399
 400             The function searches an item with key \p key, calls \p f functor
 401             and deletes the item. If \p key is not found, the functor is not called.
 402
 403             The functor \p Func interface:
 404             \code
 405             struct extractor {
 406                 void operator()(value_type const& val);
 407             };
 408             \endcode
 409
 410             Since the key of MichaelHashSet's \p value_type is not explicitly specified,
 411             template parameter \p Q defines the key type searching in the list.
 412             The list item comparator should be able to compare the type \p T of list item
 413             and the type \p Q.
 414
 415             RCU \p synchronize method can be called. RCU should not be locked.
 416
 417             Return \p true if key is found and deleted, \p false otherwise
 418
 419             See also: \ref erase
 420         */
 421         template <typename Q, typename Func>
 422         bool erase( Q const& key, Func f )
 423         {
 424             return base_class::erase( key, [&f]( node_type const& node) { f( node.m_Value ); } );
 425         }
 426
 427         /// Deletes the item from the set using \p pred predicate for searching
 428         /**
 429             The function is an analog of \ref cds_nonintrusive_SkipListSet_rcu_erase_func "erase(Q const&, Func)"
 430             but \p pred is used for key comparing.
 431             \p Less functor has the interface like \p std::less.
 432             \p Less must imply the same element order as the comparator used for building the set.
 433         */
 434         template <typename Q, typename Less, typename Func>
 435         bool erase_with( Q const& key, Less pred, Func f )
 436         {
 437             return base_class::erase_with( key, cds::details::predicate_wrapper< node_type, Less, typename maker::value_accessor >(),
 438                 [&f]( node_type const& node) { f( node.m_Value ); } );
 439         }
 440
 441         /// Extracts the item from the set with specified \p key
 442         /** \anchor cds_nonintrusive_SkipListSet_rcu_extract
 443             The function searches an item with key equal to \p key in the set,
 444             unlinks it from the set, and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the item found.
 445             If the item is not found the function returns an empty \p exempt_ptr
 446
 447             Note the compare functor from \p Traits class' template argument
 448             should accept a parameter of type \p Q that can be not the same as \p value_type.
 449
 450             RCU \p synchronize method can be called. RCU should NOT be locked.
 451
 452             The function does not free the item found.
 453             The item will be implicitly freed when the returned object is destroyed or when
 454             its \p release() member function is called.
 455         */
 456         template <typename Q>
 457         exempt_ptr extract( Q const& key )
 458         {
 459             return exempt_ptr( base_class::do_extract( key ));
 460         }
 461
 462         /// Extracts the item from the set with comparing functor \p pred
 463         /**
 464             The function is an analog of \ref cds_nonintrusive_SkipListSet_rcu_extract "extract(exempt_ptr&, Q const&)"
 465             but \p pred predicate is used for key comparing.
 466             \p Less has the semantics like \p std::less.
 467             \p pred must imply the same element order as the comparator used for building the set.
 468         */
 469         template <typename Q, typename Less>
 470         exempt_ptr extract_with( Q const& key, Less pred )
 471         {
 472             return exempt_ptr( base_class::do_extract_with( key, cds::details::predicate_wrapper< node_type, Less, typename maker::value_accessor >()));
 473         }
 474
 475         /// Extracts an item with minimal key from the set
 476         /**
 477             The function searches an item with minimal key, unlinks it,
 478             and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the item.
 479             If the skip-list is empty the function returns an empty \p exempt_ptr.
 480
 481             RCU \p synchronize method can be called. RCU should NOT be locked.
 482
 483             The function does not free the item found.
 484             The item will be implicitly freed when the returned object is destroyed or when
 485             its \p release() member function is called.
 486         */
 487         exempt_ptr extract_min()
 488         {
 489             return exempt_ptr( base_class::do_extract_min());
 490         }
 491
 492         /// Extracts an item with maximal key from the set
 493         /**
 494             The function searches an item with maximal key, unlinks it from the set,
 495             and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the item.
 496             If the skip-list is empty the function returns an empty \p exempt_ptr.
 497
 498             RCU \p synchronize method can be called. RCU should NOT be locked.
 499
 500             The function does not free the item found.
 501             The item will be implicitly freed when the returned object is destroyed or when
 502             its \p release() member function is called.
 503         */
 504         exempt_ptr extract_max()
 505         {
 506             return exempt_ptr( base_class::do_extract_max());
 507         }
 508
 509         /// Find the key \p val
 510         /**
 511             @anchor cds_nonintrusive_SkipListSet_rcu_find_func
 512
 513             The function searches the item with key equal to \p val and calls the functor \p f for item found.
 514             The interface of \p Func functor is:
 515             \code
 516             struct functor {
 517                 void operator()( value_type& item, Q& val );
 518             };
 519             \endcode
 520             where \p item is the item found, \p val is the <tt>find</tt> function argument.
 521
 522             The functor may change non-key fields of \p item. Note that the functor is only guarantee
 523             that \p item cannot be disposed during functor is executing.
 524             The functor does not serialize simultaneous access to the set's \p item. If such access is
 525             possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
 526
 527             The \p val argument is non-const since it can be used as \p f functor destination i.e., the functor
 528             can modify both arguments.
 529
 530             Note the hash functor specified for class \p Traits template parameter
 531             should accept a parameter of type \p Q that may be not the same as \p value_type.
 532
 533             The function applies RCU lock internally.
 534
 535             The function returns \p true if \p val is found, \p false otherwise.
 536         */
 537         template <typename Q, typename Func>
 538         bool find( Q& val, Func f )
 539         {
 540             return base_class::find( val, [&f]( node_type& node, Q& v ) { f( node.m_Value, v ); });
 541         }
 542         //@cond
 543         template <typename Q, typename Func>
 544         bool find( Q const& val, Func f )
 545         {
 546             return base_class::find( val, [&f]( node_type& node, Q& v ) { f( node.m_Value, v ); } );
 547         }
 548         //@endcond
 549
 550         /// Finds the key \p val using \p pred predicate for searching
 551         /**
 552             The function is an analog of \ref cds_nonintrusive_SkipListSet_rcu_find_func "find(Q&, Func)"
 553             but \p pred is used for key comparing.
 554             \p Less functor has the interface like \p std::less.
 555             \p Less must imply the same element order as the comparator used for building the set.
 556         */
 557         template <typename Q, typename Less, typename Func>
 558         bool find_with( Q& val, Less pred, Func f )
 559         {
 560             return base_class::find_with( val, cds::details::predicate_wrapper< node_type, Less, typename maker::value_accessor >(),
 561                 [&f]( node_type& node, Q& v ) { f( node.m_Value, v ); } );
 562         }
 563         //@cond
 564         template <typename Q, typename Less, typename Func>
 565         bool find_with( Q const& val, Less pred, Func f )
 566         {
 567             return base_class::find_with( val, cds::details::predicate_wrapper< node_type, Less, typename maker::value_accessor >(),
 568                                           [&f]( node_type& node, Q& v ) { f( node.m_Value, v ); } );
 569         }
 570         //@endcond
 571
 572         /// Find the key \p val
 573         /** @anchor cds_nonintrusive_SkipListSet_rcu_find_val
 574
 575             The function searches the item with key equal to \p val
 576             and returns \p true if it is found, and \p false otherwise.
 577
 578             Note the hash functor specified for class \p Traits template parameter
 579             should accept a parameter of type \p Q that may be not the same as \ref value_type.
 580
 581             The function applies RCU lock internally.
 582         */
 583         template <typename Q>
 584         bool find( Q const & val )
 585         {
 586             return base_class::find( val );
 587         }
 588
 589         /// Finds the key \p val using \p pred predicate for searching
 590         /**
 591             The function is an analog of \ref cds_nonintrusive_SkipListSet_rcu_find_val "find(Q const&)"
 592             but \p pred is used for key comparing.
 593             \p Less functor has the interface like \p std::less.
 594             \p Less must imply the same element order as the comparator used for building the set.
 595         */
 596         template <typename Q, typename Less>
 597         bool find_with( Q const& val, Less pred )
 598         {
 599             return base_class::find_with( val, cds::details::predicate_wrapper< node_type, Less, typename maker::value_accessor >());
 600         }
 601
 602         /// Finds \p key and return the item found
 603         /** \anchor cds_nonintrusive_SkipListSet_rcu_get
 604             The function searches the item with key equal to \p key and returns the pointer to item found.
 605             If \p key is not found it returns \p nullptr.
 606
 607             Note the compare functor in \p Traits class' template argument
 608             should accept a parameter of type \p Q that can be not the same as \p value_type.
 609
 610             RCU should be locked before call of this function.
 611             Returned item is valid only while RCU is locked:
 612             \code
 613             typedef cds::container::SkipListSet< cds::urcu::gc< cds::urcu::general_buffered<> >, foo, my_traits > skip_list;
 614             skip_list theList;
 615             // ...
 616             {
 617                 // Lock RCU
 618                 skip_list::rcu_lock lock;
 619
 620                 foo * pVal = theList.get( 5 );
 621                 // Deal with pVal
 622                 //...
 623
 624                 // Unlock RCU by rcu_lock destructor
 625                 // pVal can be freed at any time after RCU unlocking
 626             }
 627             \endcode
 628
 629             After RCU unlocking the \p %force_dispose member function can be called manually,
 630             see \ref force_dispose for explanation.
 631         */
 632         template <typename Q>
 633         value_type * get( Q const& key )
 634         {
 635             return to_value_ptr( base_class::get( key ));
 636         }
 637
 638         /// Finds the key \p val and return the item found
 639         /**
 640             The function is an analog of \ref cds_nonintrusive_SkipListSet_rcu_get "get(Q const&)"
 641             but \p pred is used for comparing the keys.
 642
 643             \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
 644             in any order.
 645             \p pred must imply the same element order as the comparator used for building the set.
 646         */
 647         template <typename Q, typename Less>
 648         value_type * get_with( Q const& val, Less pred )
 649         {
 650             return to_value_ptr( base_class::get_with( val, cds::details::predicate_wrapper< node_type, Less, typename maker::value_accessor >() ));
 651         }
 652
 653         /// Clears the set (non-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 atomicity::empty_item_counter this function always returns 0.
 681             Therefore, the function is not suitable for checking the set emptiness, use \ref 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         /// Clears internal list of ready-to-delete items passing them to RCU reclamation cycle
 696         /**
 697             See \ref cds_intrusive_SkipListSet_rcu_force_dispose "intrusive SkipListSet" for explanation
 698         */
 699         void force_dispose()
 700         {
 701             return base_class::force_dispose();
 702         }
 703     };
 704
 705 }} // namespace cds::container
 706
 707 #endif // #ifndef __CDS_CONTAINER_SKIP_LIST_SET_RCU_H