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             CDS_UNUSED( pred );
 395             return base_class::erase_with( key, cds::details::predicate_wrapper< node_type, Less, typename maker::value_accessor >());
 396         }
 397
 398         /// Delete \p key from the set
 399         /** \anchor cds_nonintrusive_SkipListSet_rcu_erase_func
 400
 401             The function searches an item with key \p key, calls \p f functor
 402             and deletes the item. If \p key is not found, the functor is not called.
 403
 404             The functor \p Func interface:
 405             \code
 406             struct extractor {
 407                 void operator()(value_type const& val);
 408             };
 409             \endcode
 410
 411             Since the key of MichaelHashSet's \p value_type is not explicitly specified,
 412             template parameter \p Q defines the key type searching in the list.
 413             The list item comparator should be able to compare the type \p T of list item
 414             and the type \p Q.
 415
 416             RCU \p synchronize method can be called. RCU should not be locked.
 417
 418             Return \p true if key is found and deleted, \p false otherwise
 419
 420             See also: \ref erase
 421         */
 422         template <typename Q, typename Func>
 423         bool erase( Q const& key, Func f )
 424         {
 425             return base_class::erase( key, [&f]( node_type const& node) { f( node.m_Value ); } );
 426         }
 427
 428         /// Deletes the item from the set using \p pred predicate for searching
 429         /**
 430             The function is an analog of \ref cds_nonintrusive_SkipListSet_rcu_erase_func "erase(Q const&, Func)"
 431             but \p pred is used for key comparing.
 432             \p Less functor has the interface like \p std::less.
 433             \p Less must imply the same element order as the comparator used for building the set.
 434         */
 435         template <typename Q, typename Less, typename Func>
 436         bool erase_with( Q const& key, Less pred, Func f )
 437         {
 438             CDS_UNUSED( pred );
 439             return base_class::erase_with( key, cds::details::predicate_wrapper< node_type, Less, typename maker::value_accessor >(),
 440                 [&f]( node_type const& node) { f( node.m_Value ); } );
 441         }
 442
 443         /// Extracts the item from the set with specified \p key
 444         /** \anchor cds_nonintrusive_SkipListSet_rcu_extract
 445             The function searches an item with key equal to \p key in the set,
 446             unlinks it from the set, and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the item found.
 447             If the item is not found the function returns an empty \p exempt_ptr
 448
 449             Note the compare functor from \p Traits class' template argument
 450             should accept a parameter of type \p Q that can be not the same as \p value_type.
 451
 452             RCU \p synchronize method can be called. RCU should NOT be locked.
 453
 454             The function does not free the item found.
 455             The item will be implicitly freed when the returned object is destroyed or when
 456             its \p release() member function is called.
 457         */
 458         template <typename Q>
 459         exempt_ptr extract( Q const& key )
 460         {
 461             return exempt_ptr( base_class::do_extract( key ));
 462         }
 463
 464         /// Extracts the item from the set with comparing functor \p pred
 465         /**
 466             The function is an analog of \ref cds_nonintrusive_SkipListSet_rcu_extract "extract(exempt_ptr&, Q const&)"
 467             but \p pred predicate is used for key comparing.
 468             \p Less has the semantics like \p std::less.
 469             \p pred must imply the same element order as the comparator used for building the set.
 470         */
 471         template <typename Q, typename Less>
 472         exempt_ptr extract_with( Q const& key, Less pred )
 473         {
 474             CDS_UNUSED( pred );
 475             return exempt_ptr( base_class::do_extract_with( key, cds::details::predicate_wrapper< node_type, Less, typename maker::value_accessor >()));
 476         }
 477
 478         /// Extracts an item with minimal key from the set
 479         /**
 480             The function searches an item with minimal key, unlinks it,
 481             and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the item.
 482             If the skip-list is empty the function returns an empty \p exempt_ptr.
 483
 484             RCU \p synchronize method can be called. RCU should NOT be locked.
 485
 486             The function does not free the item found.
 487             The item will be implicitly freed when the returned object is destroyed or when
 488             its \p release() member function is called.
 489         */
 490         exempt_ptr extract_min()
 491         {
 492             return exempt_ptr( base_class::do_extract_min());
 493         }
 494
 495         /// Extracts an item with maximal key from the set
 496         /**
 497             The function searches an item with maximal key, unlinks it from the set,
 498             and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the item.
 499             If the skip-list is empty the function returns an empty \p exempt_ptr.
 500
 501             RCU \p synchronize method can be called. RCU should NOT be locked.
 502
 503             The function does not free the item found.
 504             The item will be implicitly freed when the returned object is destroyed or when
 505             its \p release() member function is called.
 506         */
 507         exempt_ptr extract_max()
 508         {
 509             return exempt_ptr( base_class::do_extract_max());
 510         }
 511
 512         /// Find the key \p val
 513         /**
 514             @anchor cds_nonintrusive_SkipListSet_rcu_find_func
 515
 516             The function searches the item with key equal to \p val and calls the functor \p f for item found.
 517             The interface of \p Func functor is:
 518             \code
 519             struct functor {
 520                 void operator()( value_type& item, Q& val );
 521             };
 522             \endcode
 523             where \p item is the item found, \p val is the <tt>find</tt> function argument.
 524
 525             The functor may change non-key fields of \p item. Note that the functor is only guarantee
 526             that \p item cannot be disposed during functor is executing.
 527             The functor does not serialize simultaneous access to the set's \p item. If such access is
 528             possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
 529
 530             The \p val argument is non-const since it can be used as \p f functor destination i.e., the functor
 531             can modify both arguments.
 532
 533             Note the hash functor specified for class \p Traits template parameter
 534             should accept a parameter of type \p Q that may be not the same as \p value_type.
 535
 536             The function applies RCU lock internally.
 537
 538             The function returns \p true if \p val is found, \p false otherwise.
 539         */
 540         template <typename Q, typename Func>
 541         bool find( Q& val, Func f )
 542         {
 543             return base_class::find( val, [&f]( node_type& node, Q& v ) { f( node.m_Value, v ); });
 544         }
 545         //@cond
 546         template <typename Q, typename Func>
 547         bool find( Q const& val, Func f )
 548         {
 549             return base_class::find( val, [&f]( node_type& node, Q& v ) { f( node.m_Value, v ); } );
 550         }
 551         //@endcond
 552
 553         /// Finds the key \p val using \p pred predicate for searching
 554         /**
 555             The function is an analog of \ref cds_nonintrusive_SkipListSet_rcu_find_func "find(Q&, Func)"
 556             but \p pred is used for key comparing.
 557             \p Less functor has the interface like \p std::less.
 558             \p Less must imply the same element order as the comparator used for building the set.
 559         */
 560         template <typename Q, typename Less, typename Func>
 561         bool find_with( Q& val, Less pred, Func f )
 562         {
 563             CDS_UNUSED( pred );
 564             return base_class::find_with( val, cds::details::predicate_wrapper< node_type, Less, typename maker::value_accessor >(),
 565                 [&f]( node_type& node, Q& v ) { f( node.m_Value, v ); } );
 566         }
 567         //@cond
 568         template <typename Q, typename Less, typename Func>
 569         bool find_with( Q const& val, Less pred, Func f )
 570         {
 571             CDS_UNUSED( pred );
 572             return base_class::find_with( val, 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         //@endcond
 576
 577         /// Find the key \p val
 578         /** @anchor cds_nonintrusive_SkipListSet_rcu_find_val
 579
 580             The function searches the item with key equal to \p val
 581             and returns \p true if it is found, and \p false otherwise.
 582
 583             Note the hash functor specified for class \p Traits template parameter
 584             should accept a parameter of type \p Q that may be not the same as \ref value_type.
 585
 586             The function applies RCU lock internally.
 587         */
 588         template <typename Q>
 589         bool find( Q const & val )
 590         {
 591             return base_class::find( val );
 592         }
 593
 594         /// Finds the key \p val using \p pred predicate for searching
 595         /**
 596             The function is an analog of \ref cds_nonintrusive_SkipListSet_rcu_find_val "find(Q const&)"
 597             but \p pred is used for key comparing.
 598             \p Less functor has the interface like \p std::less.
 599             \p Less must imply the same element order as the comparator used for building the set.
 600         */
 601         template <typename Q, typename Less>
 602         bool find_with( Q const& val, Less pred )
 603         {
 604             CDS_UNUSED( pred );
 605             return base_class::find_with( val, cds::details::predicate_wrapper< node_type, Less, typename maker::value_accessor >());
 606         }
 607
 608         /// Finds \p key and return the item found
 609         /** \anchor cds_nonintrusive_SkipListSet_rcu_get
 610             The function searches the item with key equal to \p key and returns the pointer to item found.
 611             If \p key is not found it returns \p nullptr.
 612
 613             Note the compare functor in \p Traits class' template argument
 614             should accept a parameter of type \p Q that can be not the same as \p value_type.
 615
 616             RCU should be locked before call of this function.
 617             Returned item is valid only while RCU is locked:
 618             \code
 619             typedef cds::container::SkipListSet< cds::urcu::gc< cds::urcu::general_buffered<> >, foo, my_traits > skip_list;
 620             skip_list theList;
 621             // ...
 622             {
 623                 // Lock RCU
 624                 skip_list::rcu_lock lock;
 625
 626                 foo * pVal = theList.get( 5 );
 627                 // Deal with pVal
 628                 //...
 629
 630                 // Unlock RCU by rcu_lock destructor
 631                 // pVal can be freed at any time after RCU unlocking
 632             }
 633             \endcode
 634
 635             After RCU unlocking the \p %force_dispose member function can be called manually,
 636             see \ref force_dispose for explanation.
 637         */
 638         template <typename Q>
 639         value_type * get( Q const& key )
 640         {
 641             return to_value_ptr( base_class::get( key ));
 642         }
 643
 644         /// Finds the key \p val and return the item found
 645         /**
 646             The function is an analog of \ref cds_nonintrusive_SkipListSet_rcu_get "get(Q const&)"
 647             but \p pred is used for comparing the keys.
 648
 649             \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
 650             in any order.
 651             \p pred must imply the same element order as the comparator used for building the set.
 652         */
 653         template <typename Q, typename Less>
 654         value_type * get_with( Q const& val, Less pred )
 655         {
 656             CDS_UNUSED( pred );
 657             return to_value_ptr( base_class::get_with( val, cds::details::predicate_wrapper< node_type, Less, typename maker::value_accessor >() ));
 658         }
 659
 660         /// Clears the set (non-atomic).
 661         /**
 662             The function deletes all items from the set.
 663             The function is not atomic, thus, in multi-threaded environment with parallel insertions
 664             this sequence
 665             \code
 666             set.clear();
 667             assert( set.empty() );
 668             \endcode
 669             the assertion could be raised.
 670
 671             For each item the \ref disposer provided by \p Traits template parameter will be called.
 672         */
 673         void clear()
 674         {
 675             base_class::clear();
 676         }
 677
 678         /// Checks if the set is empty
 679         bool empty() const
 680         {
 681             return base_class::empty();
 682         }
 683
 684         /// Returns item count in the set
 685         /**
 686             The value returned depends on item counter type provided by \p Traits template parameter.
 687             If it is atomicity::empty_item_counter this function always returns 0.
 688             Therefore, the function is not suitable for checking the set emptiness, use \ref empty
 689             member function for this purpose.
 690         */
 691         size_t size() const
 692         {
 693             return base_class::size();
 694         }
 695
 696         /// Returns const reference to internal statistics
 697         stat const& statistics() const
 698         {
 699             return base_class::statistics();
 700         }
 701
 702         /// Clears internal list of ready-to-delete items passing them to RCU reclamation cycle
 703         /**
 704             See \ref cds_intrusive_SkipListSet_rcu_force_dispose "intrusive SkipListSet" for explanation
 705         */
 706         void force_dispose()
 707         {
 708             return base_class::force_dispose();
 709         }
 710     };
 711
 712 }} // namespace cds::container
 713
 714 #endif // #ifndef __CDS_CONTAINER_SKIP_LIST_SET_RCU_H