Merge branch 'integration' into dev
[libcds.git] / cds / container / skip_list_set_rcu.h
1 //$$CDS-header$$
2
3 #ifndef CDSLIB_CONTAINER_SKIP_LIST_SET_RCU_H
4 #define CDSLIB_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         //@cond
175         typedef cds::container::skip_list::implementation_tag implementation_tag;
176         //@endcond
177
178     protected:
179         //@cond
180         typedef typename maker::node_type           node_type;
181         typedef typename maker::node_allocator      node_allocator;
182
183         typedef std::unique_ptr< node_type, typename maker::node_deallocator >    scoped_node_ptr;
184         //@endcond
185
186     public:
187         typedef typename base_class::rcu_lock  rcu_lock;   ///< RCU scoped lock
188         /// Group of \p extract_xxx functions do not require external locking
189         static CDS_CONSTEXPR const bool c_bExtractLockExternal = base_class::c_bExtractLockExternal;
190
191         /// pointer to extracted node
192         using exempt_ptr = cds::urcu::exempt_ptr< gc, node_type, value_type, typename maker::intrusive_traits::disposer >;
193
194     protected:
195         //@cond
196         unsigned int random_level()
197         {
198             return base_class::random_level();
199         }
200
201         value_type * to_value_ptr( node_type * pNode ) const CDS_NOEXCEPT
202         {
203             return pNode ? &pNode->m_Value : nullptr;
204         }
205         //@endcond
206
207     public:
208         /// Default ctor
209         SkipListSet()
210             : base_class()
211         {}
212
213         /// Destructor destroys the set object
214         ~SkipListSet()
215         {}
216
217     public:
218         /// Iterator type
219         typedef skip_list::details::iterator< typename base_class::iterator >  iterator;
220
221         /// Const iterator type
222         typedef skip_list::details::iterator< typename base_class::const_iterator >   const_iterator;
223
224         /// Returns a forward iterator addressing the first element in a set
225         iterator begin()
226         {
227             return iterator( base_class::begin() );
228         }
229
230         /// Returns a forward const iterator addressing the first element in a set
231         //@{
232         const_iterator begin() const
233         {
234             return const_iterator( base_class::begin() );
235         }
236         const_iterator cbegin() const
237         {
238             return const_iterator( base_class::cbegin() );
239         }
240         //@}
241
242         /// Returns a forward iterator that addresses the location succeeding the last element in a set.
243         iterator end()
244         {
245             return iterator( base_class::end() );
246         }
247
248         /// Returns a forward const iterator that addresses the location succeeding the last element in a set.
249         //@{
250         const_iterator end() const
251         {
252             return const_iterator( base_class::end() );
253         }
254         const_iterator cend() const
255         {
256             return const_iterator( base_class::cend() );
257         }
258         //@}
259
260     public:
261         /// Inserts new node
262         /**
263             The function creates a node with copy of \p val value
264             and then inserts the node created into the set.
265
266             The type \p Q should contain as minimum the complete key for the node.
267             The object of \ref value_type should be constructible from a value of type \p Q.
268             In trivial case, \p Q is equal to \ref value_type.
269
270             RCU \p synchronize method can be called. RCU should not be locked.
271
272             Returns \p true if \p val is inserted into the set, \p false otherwise.
273         */
274         template <typename Q>
275         bool insert( Q const& val )
276         {
277             scoped_node_ptr sp( node_allocator().New( random_level(), val ));
278             if ( base_class::insert( *sp.get() )) {
279                 sp.release();
280                 return true;
281             }
282             return false;
283         }
284
285         /// Inserts new node
286         /**
287             The function allows to split creating of new item into two part:
288             - create item with key only
289             - insert new item into the set
290             - if inserting is success, calls  \p f functor to initialize value-fields of \p val.
291
292             The functor signature is:
293             \code
294                 void func( value_type& val );
295             \endcode
296             where \p val is the item inserted. User-defined functor \p f should guarantee that during changing
297             \p val no any other changes could be made on this set's item by concurrent threads.
298             The user-defined functor is called only if the inserting is success.
299
300             RCU \p synchronize method can be called. RCU should not be locked.
301         */
302         template <typename Q, typename Func>
303         bool insert( Q const& val, Func f )
304         {
305             scoped_node_ptr sp( node_allocator().New( random_level(), val ));
306             if ( base_class::insert( *sp.get(), [&f]( node_type& val ) { f( val.m_Value ); } )) {
307                 sp.release();
308                 return true;
309             }
310             return false;
311         }
312
313         /// Ensures that the item exists in the set
314         /**
315             The operation performs inserting or changing data with lock-free manner.
316
317             If the \p val key not found in the set, then the new item created from \p val
318             is inserted into the set. Otherwise, the functor \p func is called with the item found.
319             The functor \p Func should be a function with signature:
320             \code
321                 void func( bool bNew, value_type& item, const Q& val );
322             \endcode
323             or a functor:
324             \code
325                 struct my_functor {
326                     void operator()( bool bNew, value_type& item, const Q& val );
327                 };
328             \endcode
329
330             with arguments:
331             - \p bNew - \p true if the item has been inserted, \p false otherwise
332             - \p item - item of the set
333             - \p val - argument \p key passed into the \p ensure function
334
335             The functor may change non-key fields of the \p item; however, \p func must guarantee
336             that during changing no any other modifications could be made on this item by concurrent threads.
337
338             RCU \p synchronize method can be called. RCU should not be locked.
339
340             Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
341             \p second is true if new item has been added or \p false if the item with \p key
342             already is in the set.
343         */
344         template <typename Q, typename Func>
345         std::pair<bool, bool> ensure( const Q& val, Func func )
346         {
347             scoped_node_ptr sp( node_allocator().New( random_level(), val ));
348             std::pair<bool, bool> bRes = base_class::ensure( *sp,
349                 [&func, &val](bool bNew, node_type& node, node_type&){ func( bNew, node.m_Value, val ); });
350             if ( bRes.first && bRes.second )
351                 sp.release();
352             return bRes;
353         }
354
355         /// Inserts data of type \ref value_type constructed with <tt>std::forward<Args>(args)...</tt>
356         /**
357             Returns \p true if inserting successful, \p false otherwise.
358
359             RCU \p synchronize method can be called. RCU should not be locked.
360         */
361         template <typename... Args>
362         bool emplace( Args&&... args )
363         {
364             scoped_node_ptr sp( node_allocator().New( random_level(), std::forward<Args>(args)... ));
365             if ( base_class::insert( *sp.get() )) {
366                 sp.release();
367                 return true;
368             }
369             return false;
370         }
371
372         /// Delete \p key from the set
373         /** \anchor cds_nonintrusive_SkipListSet_rcu_erase_val
374
375             The item comparator should be able to compare the type \p value_type
376             and the type \p Q.
377
378             RCU \p synchronize method can be called. RCU should not be locked.
379
380             Return \p true if key is found and deleted, \p false otherwise
381         */
382         template <typename Q>
383         bool erase( Q const& key )
384         {
385             return base_class::erase( key );
386         }
387
388         /// Deletes the item from the set using \p pred predicate for searching
389         /**
390             The function is an analog of \ref cds_nonintrusive_SkipListSet_rcu_erase_val "erase(Q const&)"
391             but \p pred is used for key comparing.
392             \p Less functor has the interface like \p std::less.
393             \p Less must imply the same element order as the comparator used for building the set.
394         */
395         template <typename Q, typename Less>
396         bool erase_with( Q const& key, Less pred )
397         {
398             CDS_UNUSED( pred );
399             return base_class::erase_with( key, cds::details::predicate_wrapper< node_type, Less, typename maker::value_accessor >());
400         }
401
402         /// Delete \p key from the set
403         /** \anchor cds_nonintrusive_SkipListSet_rcu_erase_func
404
405             The function searches an item with key \p key, calls \p f functor
406             and deletes the item. If \p key is not found, the functor is not called.
407
408             The functor \p Func interface:
409             \code
410             struct extractor {
411                 void operator()(value_type const& val);
412             };
413             \endcode
414
415             Since the key of MichaelHashSet's \p value_type is not explicitly specified,
416             template parameter \p Q defines the key type searching in the list.
417             The list item comparator should be able to compare the type \p T of list item
418             and the type \p Q.
419
420             RCU \p synchronize method can be called. RCU should not be locked.
421
422             Return \p true if key is found and deleted, \p false otherwise
423
424             See also: \ref erase
425         */
426         template <typename Q, typename Func>
427         bool erase( Q const& key, Func f )
428         {
429             return base_class::erase( key, [&f]( node_type const& node) { f( node.m_Value ); } );
430         }
431
432         /// Deletes the item from the set using \p pred predicate for searching
433         /**
434             The function is an analog of \ref cds_nonintrusive_SkipListSet_rcu_erase_func "erase(Q const&, Func)"
435             but \p pred is used for key comparing.
436             \p Less functor has the interface like \p std::less.
437             \p Less must imply the same element order as the comparator used for building the set.
438         */
439         template <typename Q, typename Less, typename Func>
440         bool erase_with( Q const& key, Less pred, Func f )
441         {
442             CDS_UNUSED( pred );
443             return base_class::erase_with( key, cds::details::predicate_wrapper< node_type, Less, typename maker::value_accessor >(),
444                 [&f]( node_type const& node) { f( node.m_Value ); } );
445         }
446
447         /// Extracts the item from the set with specified \p key
448         /** \anchor cds_nonintrusive_SkipListSet_rcu_extract
449             The function searches an item with key equal to \p key in the set,
450             unlinks it from the set, and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the item found.
451             If the item is not found the function returns an empty \p exempt_ptr
452
453             Note the compare functor from \p Traits class' template argument
454             should accept a parameter of type \p Q that can be not the same as \p value_type.
455
456             RCU \p synchronize method can be called. RCU should NOT be locked.
457
458             The function does not free the item found.
459             The item will be implicitly freed when the returned object is destroyed or when
460             its \p release() member function is called.
461         */
462         template <typename Q>
463         exempt_ptr extract( Q const& key )
464         {
465             return exempt_ptr( base_class::do_extract( key ));
466         }
467
468         /// Extracts the item from the set with comparing functor \p pred
469         /**
470             The function is an analog of \p extract(Q const&) but \p pred predicate is used for key comparing.
471             \p Less has the semantics like \p std::less.
472             \p pred must imply the same element order as the comparator used for building the set.
473         */
474         template <typename Q, typename Less>
475         exempt_ptr extract_with( Q const& key, Less pred )
476         {
477             CDS_UNUSED( pred );
478             return exempt_ptr( base_class::do_extract_with( key, cds::details::predicate_wrapper< node_type, Less, typename maker::value_accessor >()));
479         }
480
481         /// Extracts an item with minimal key from the set
482         /**
483             The function searches an item with minimal key, unlinks it,
484             and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the item.
485             If the skip-list is empty the function returns an empty \p exempt_ptr.
486
487             RCU \p synchronize method can be called. RCU should NOT be locked.
488
489             The function does not free the item found.
490             The item will be implicitly freed when the returned object is destroyed or when
491             its \p release() member function is called.
492         */
493         exempt_ptr extract_min()
494         {
495             return exempt_ptr( base_class::do_extract_min());
496         }
497
498         /// Extracts an item with maximal key from the set
499         /**
500             The function searches an item with maximal key, unlinks it from the set,
501             and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the item.
502             If the skip-list is empty the function returns an empty \p exempt_ptr.
503
504             RCU \p synchronize method can be called. RCU should NOT be locked.
505
506             The function does not free the item found.
507             The item will be implicitly freed when the returned object is destroyed or when
508             its \p release() member function is called.
509         */
510         exempt_ptr extract_max()
511         {
512             return exempt_ptr( base_class::do_extract_max());
513         }
514
515         /// Find the key \p val
516         /**
517             @anchor cds_nonintrusive_SkipListSet_rcu_find_func
518
519             The function searches the item with key equal to \p val and calls the functor \p f for item found.
520             The interface of \p Func functor is:
521             \code
522             struct functor {
523                 void operator()( value_type& item, Q& val );
524             };
525             \endcode
526             where \p item is the item found, \p val is the <tt>find</tt> function argument.
527
528             The functor may change non-key fields of \p item. Note that the functor is only guarantee
529             that \p item cannot be disposed during functor is executing.
530             The functor does not serialize simultaneous access to the set's \p item. If such access is
531             possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
532
533             The \p val argument is non-const since it can be used as \p f functor destination i.e., the functor
534             can modify both arguments.
535
536             Note the hash functor specified for class \p Traits template parameter
537             should accept a parameter of type \p Q that may be not the same as \p value_type.
538
539             The function applies RCU lock internally.
540
541             The function returns \p true if \p val is found, \p false otherwise.
542         */
543         template <typename Q, typename Func>
544         bool find( Q& val, Func f )
545         {
546             return base_class::find( val, [&f]( node_type& node, Q& v ) { f( node.m_Value, v ); });
547         }
548         //@cond
549         template <typename Q, typename Func>
550         bool find( Q const& val, Func f )
551         {
552             return base_class::find( val, [&f]( node_type& node, Q& v ) { f( node.m_Value, v ); } );
553         }
554         //@endcond
555
556         /// Finds the key \p val using \p pred predicate for searching
557         /**
558             The function is an analog of \ref cds_nonintrusive_SkipListSet_rcu_find_func "find(Q&, Func)"
559             but \p pred is used for key comparing.
560             \p Less functor has the interface like \p std::less.
561             \p Less must imply the same element order as the comparator used for building the set.
562         */
563         template <typename Q, typename Less, typename Func>
564         bool find_with( Q& val, Less pred, Func f )
565         {
566             CDS_UNUSED( pred );
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         //@cond
571         template <typename Q, typename Less, typename Func>
572         bool find_with( Q const& val, Less pred, Func f )
573         {
574             CDS_UNUSED( pred );
575             return base_class::find_with( val, cds::details::predicate_wrapper< node_type, Less, typename maker::value_accessor >(),
576                                           [&f]( node_type& node, Q& v ) { f( node.m_Value, v ); } );
577         }
578         //@endcond
579
580         /// Find the key \p val
581         /** @anchor cds_nonintrusive_SkipListSet_rcu_find_val
582
583             The function searches the item with key equal to \p val
584             and returns \p true if it is found, and \p false otherwise.
585
586             Note the hash functor specified for class \p Traits template parameter
587             should accept a parameter of type \p Q that may be not the same as \ref value_type.
588
589             The function applies RCU lock internally.
590         */
591         template <typename Q>
592         bool find( Q const & val )
593         {
594             return base_class::find( val );
595         }
596
597         /// Finds the key \p val using \p pred predicate for searching
598         /**
599             The function is an analog of \ref cds_nonintrusive_SkipListSet_rcu_find_val "find(Q const&)"
600             but \p pred is used for key comparing.
601             \p Less functor has the interface like \p std::less.
602             \p Less must imply the same element order as the comparator used for building the set.
603         */
604         template <typename Q, typename Less>
605         bool find_with( Q const& val, Less pred )
606         {
607             CDS_UNUSED( pred );
608             return base_class::find_with( val, cds::details::predicate_wrapper< node_type, Less, typename maker::value_accessor >());
609         }
610
611         /// Finds \p key and return the item found
612         /** \anchor cds_nonintrusive_SkipListSet_rcu_get
613             The function searches the item with key equal to \p key and returns the pointer to item found.
614             If \p key is not found it returns \p nullptr.
615
616             Note the compare functor in \p Traits class' template argument
617             should accept a parameter of type \p Q that can be not the same as \p value_type.
618
619             RCU should be locked before call of this function.
620             Returned item is valid only while RCU is locked:
621             \code
622             typedef cds::container::SkipListSet< cds::urcu::gc< cds::urcu::general_buffered<> >, foo, my_traits > skip_list;
623             skip_list theList;
624             // ...
625             {
626                 // Lock RCU
627                 skip_list::rcu_lock lock;
628
629                 foo * pVal = theList.get( 5 );
630                 // Deal with pVal
631                 //...
632
633                 // Unlock RCU by rcu_lock destructor
634                 // pVal can be freed at any time after RCU unlocking
635             }
636             \endcode
637
638             After RCU unlocking the \p %force_dispose member function can be called manually,
639             see \ref force_dispose for explanation.
640         */
641         template <typename Q>
642         value_type * get( Q const& key )
643         {
644             return to_value_ptr( base_class::get( key ));
645         }
646
647         /// Finds the key \p val and return the item found
648         /**
649             The function is an analog of \ref cds_nonintrusive_SkipListSet_rcu_get "get(Q const&)"
650             but \p pred is used for comparing the keys.
651
652             \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
653             in any order.
654             \p pred must imply the same element order as the comparator used for building the set.
655         */
656         template <typename Q, typename Less>
657         value_type * get_with( Q const& val, Less pred )
658         {
659             CDS_UNUSED( pred );
660             return to_value_ptr( base_class::get_with( val, cds::details::predicate_wrapper< node_type, Less, typename maker::value_accessor >() ));
661         }
662
663         /// Clears the set (non-atomic).
664         /**
665             The function deletes all items from the set.
666             The function is not atomic, thus, in multi-threaded environment with parallel insertions
667             this sequence
668             \code
669             set.clear();
670             assert( set.empty() );
671             \endcode
672             the assertion could be raised.
673
674             For each item the \ref disposer provided by \p Traits template parameter will be called.
675         */
676         void clear()
677         {
678             base_class::clear();
679         }
680
681         /// Checks if the set is empty
682         bool empty() const
683         {
684             return base_class::empty();
685         }
686
687         /// Returns item count in the set
688         /**
689             The value returned depends on item counter type provided by \p Traits template parameter.
690             If it is atomicity::empty_item_counter this function always returns 0.
691             Therefore, the function is not suitable for checking the set emptiness, use \ref empty
692             member function for this purpose.
693         */
694         size_t size() const
695         {
696             return base_class::size();
697         }
698
699         /// Returns const reference to internal statistics
700         stat const& statistics() const
701         {
702             return base_class::statistics();
703         }
704
705         /// Clears internal list of ready-to-delete items passing them to RCU reclamation cycle
706         /**
707             See \ref cds_intrusive_SkipListSet_rcu_force_dispose "intrusive SkipListSet" for explanation
708         */
709         void force_dispose()
710         {
711             return base_class::force_dispose();
712         }
713     };
714
715 }} // namespace cds::container
716
717 #endif // #ifndef CDSLIB_CONTAINER_SKIP_LIST_SET_RCU_H