3 #ifndef __CDS_INTRUSIVE_STRIPED_SET_H
4 #define __CDS_INTRUSIVE_STRIPED_SET_H
6 #include <cds/intrusive/details/base.h>
7 #include <cds/intrusive/striped_set/adapter.h>
8 #include <cds/intrusive/striped_set/striping_policy.h>
10 namespace cds { namespace intrusive {
11 /// StripedSet related definitions
12 namespace striped_set {
13 } // namespace striped_set
16 /** @ingroup cds_intrusive_map
19 - [2008] Maurice Herlihy, Nir Shavit "The Art of Multiprocessor Programming"
21 Lock striping is very simple technique.
22 The set consists of the bucket table and the array of locks.
23 Initially, the capacity of lock array and bucket table is the same.
24 When set is resized, bucket table capacity will be doubled but lock array will not.
25 The lock \p i protects each bucket \p j, where <tt> j = i mod L </tt>,
26 where \p L - the size of lock array.
29 - \p Container - the container class that is used as bucket table entry. The \p Container class should support
30 an uniform interface described below.
31 - \p Options - options
33 The \p %StripedSet class does not exactly dictate the type of container that should be used as a \p Container bucket.
34 Instead, the class supports different intrusive container type for the bucket, for exampe, \p boost::intrusive::list, \p boost::intrusive::set and others.
36 Remember that \p %StripedSet class algorithm ensures sequential blocking access to its bucket through the mutex type you specify
37 among \p Options template arguments.
40 - opt::mutex_policy - concurrent access policy.
41 Available policies: striped_set::striping, striped_set::refinable.
42 Default is striped_set::striping.
43 - cds::opt::hash - hash functor. Default option value see <tt>opt::v::hash_selector <opt::none></tt> which selects default hash functor for
45 - cds::opt::compare - key comparison functor. No default functor is provided.
46 If the option is not specified, the opt::less is used.
47 - cds::opt::less - specifies binary predicate used for key comparison. Default is \p std::less<T>.
48 - cds::opt::item_counter - item counter type. Default is \p atomicity::item_counter since some operation on the counter is performed
49 without locks. Note that item counting is an essential part of the set algorithm, so dummy type like atomicity::empty_item_counter
51 - cds::opt::allocator - the allocator type using for memory allocation of bucket table and lock array. Default is CDS_DEFAULT_ALLOCATOR.
52 - cds::opt::resizing_policy - the resizing policy that is a functor that decides when to resize the hash set.
53 Default option value depends on bucket container type:
54 for sequential containers like \p boost::intrusive::list the resizing policy is <tt>cds::container::striped_set::load_factor_resizing <4></tt>;
55 for other type of containers like \p boost::intrusive::set the resizing policy is cds::container::striped_set::no_resizing.
56 See cds::container::striped_set namespace for list of all possible types of the option.
57 Note that the choose of resizing policy depends of \p Container type:
58 for sequential containers like \p boost::intrusive::list right choosing of the policy can significantly improve performance.
59 For other, non-sequential types of \p Container (like a \p boost::intrusive::set) the resizing policy is not so important.
60 - cds::opt::buffer - a buffer type used only for boost::intrusive::unordered_set.
61 Default is cds::opt::v::static_buffer< cds::any_type, 256 >.
63 opt::compare or opt::less options are used in some \p Container class for ordering.
64 opt::compare option has the highest priority: if opt::compare is specified, opt::less is not used.
66 You can pass other option that would be passed to <tt>adapt</tt> metafunction, see below.
68 <b>Internal details</b>
70 The \p %StripedSet class cannot utilize the \p Container container specified directly, but only its adapted variant which
71 supports an unified interface. Internally, the adaptation is made via intrusive::striped_set::adapt metafunction that wraps bucket container
72 and provides the unified bucket interface suitable for \p %StripedSet. Such adaptation is completely transparent for you -
73 you don't need to call \p adapt metafunction directly, \p %StripedSet class's internal machinery itself invokes appropriate
74 \p adapt metafunction specialization to adjust your \p Container container class to \p %StripedSet bucket's internal interface.
75 All you need is to include a right header before <tt>striped_set.h</tt>.
77 By default, <tt>intrusive::striped_set::adapt<AnyContainer, OptionPack> </tt> metafunction does not make any wrapping to \p AnyContainer,
78 so, the result <tt>intrusive::striped_set::adapt<AnyContainer, OptionPack>::type </tt> is the same as \p AnyContainer.
79 However, there are a lot of specializations of \p %intrusive::striped_set::adapt for \p boost::intrusive containers, see table below.
80 Any of this specialization wraps corresponding container making it suitable for the set's bucket.
81 Remember, you should include the proper header file for \p adapt <b>before</b> including <tt>striped_set.h</tt>.
83 \note It is important to specify <tt>boost::intrusive::constant_time_size<true></tt> option
84 for all \p boost::intrusive container that supports this option. Fast item counting feature is essential part of
85 \p %StripedSet resizing algorithm.
90 <th>.h-file for \p adapt</th>
95 <td> \p boost::intrusive::list</td>
96 <td><tt><cds/intrusive/striped_set/boost_list.h></tt></td>
98 #include <cds/intrusive/striped_set/boost_list.h>
99 #include <cds/intrusive/striped_set.h>
100 typedef cds::intrusive::StripedSet<
101 boost::intrusive::list<T, boost::intrusive::constant_time_size<true> >,
102 cds::opt::less< std::less<T> >
108 Template argument pack \p Options <b>must</b> contain cds::opt::less or cds::opt::compare for type \p T stored in the list
112 <td> \p boost::intrusive::slist</td>
113 <td><tt><cds/intrusive/striped_set/boost_slist.h></tt></td>
115 #include <cds/intrusive/striped_set/boost_slist.h>
116 #include <cds/intrusive/striped_set.h>
117 typedef cds::intrusive::StripedSet<
118 boost::intrusive::slist<T, boost::intrusive::constant_time_size<true> >,
119 cds::opt::less< std::less<T> >
125 Template argument pack \p Options <b>must</b> contain cds::opt::less or cds::opt::compare for type \p T stored in the list
129 <td> \p boost::intrusive::set</td>
130 <td><tt><cds/intrusive/striped_set/boost_set.h></tt></td>
132 #include <cds/intrusive/striped_set/boost_set.h>
133 #include <cds/intrusive/striped_set.h>
134 typedef cds::intrusive::StripedSet<
135 boost::intrusive::set<T, boost::intrusive::constant_time_size<true> >
140 Note that \p boost::intrusive::compare option using in \p boost::intrusive::set
141 should support \p T type stored in the set and any type \p Q that you can use
142 in \p erase and \p find member functions.
146 <td> \p boost::intrusive::unordered_set</td>
147 <td><tt><cds/intrusive/striped_set/boost_unordered_set.h></tt></td>
149 #include <cds/intrusive/striped_set/boost_unordered_set.h>
150 #include <cds/intrusive/striped_set.h>
151 typedef cds::intrusive::StripedSet<
152 boost::intrusive::unordered_set<T
153 ,boost::intrusive::constant_time_size<true>
154 ,boost::intrusive::hash< user_provided_hash_functor >
160 You should provide two different hash function h1 and h2 - one for boost::intrusive::unordered_set
161 and other for %StripedSet. For the best result, h1 and h2 must be orthogonal i.e. h1(X) != h2(X) for any value X
163 The option opt::buffer is used for boost::intrusive::bucket_traits. Default is cds::opt::v::static_buffer< cds::any_type, 256 >.
164 The resizing policy should correlate with the buffer capacity.
165 The default resizing policy is cds::container::striped_set::load_factor_resizing<256> what gives load factor 1 for
166 default bucket buffer that is the best for \p boost::intrusive::unordered_set.
170 <td> \p boost::intrusive::avl_set</td>
171 <td><tt><cds/intrusive/striped_set/boost_avl_set.h></tt></td>
173 #include <cds/intrusive/striped_set/boost_avl_set.h>
174 #include <cds/intrusive/striped_set.h>
175 typedef cds::intrusive::StripedSet<
176 boost::intrusive::avl_set<T, boost::intrusive::constant_time_size<true> >
181 Note that \p boost::intrusive::compare option using in \p boost::intrusive::avl_set
182 should support \p T type stored in the set and any type \p Q that you can use
183 in \p erase and \p find member functions.
187 <td> \p boost::intrusive::sg_set</td>
188 <td><tt><cds/intrusive/striped_set/boost_sg_set.h></tt></td>
190 #include <cds/intrusive/striped_set/boost_sg_set.h>
191 #include <cds/intrusive/striped_set.h>
192 typedef cds::intrusive::StripedSet<
193 boost::intrusive::sg_set<T, boost::intrusive::constant_time_size<true> >
198 Note that \p boost::intrusive::compare option using in \p boost::intrusive::sg_set
199 should support \p T type stored in the set and any type \p Q that you can use
200 in \p erase and \p find member functions.
204 <td> \p boost::intrusive::splay_set</td>
205 <td><tt><cds/intrusive/striped_set/boost_splay_set.h></tt></td>
207 #include <cds/intrusive/striped_set/boost_splay_set.h>
208 #include <cds/intrusive/striped_set.h>
209 typedef cds::intrusive::StripedSet<
210 boost::intrusive::splay_set<T, boost::intrusive::constant_time_size<true> >
215 Note that \p boost::intrusive::compare option using in \p boost::intrusive::splay_set
216 should support \p T type stored in the set and any type \p Q that you can use
217 in \p erase and \p find member functions.
221 <td> \p boost::intrusive::treap_set</td>
222 <td><tt><cds/intrusive/striped_set/boost_treap_set.h></tt></td>
224 #include <cds/intrusive/striped_set/boost_treap_set.h>
225 #include <cds/intrusive/striped_set.h>
226 typedef cds::intrusive::StripedSet<
227 boost::intrusive::treap_set<T, boost::intrusive::constant_time_size<true> >
232 Note that \p boost::intrusive::compare option using in \p boost::intrusive::treap_set
233 should support \p T type stored in the set and any type \p Q that you can use
234 in \p erase and \p find member functions.
239 You can use another intrusive container type as striped set's bucket.
240 Suppose, you have a container class \p MyBestContainer and you want to integrate it with \p StripedSet as bucket type.
241 There are two possibility:
242 - either your \p MyBestContainer class has native support of bucket's interface;
243 in this case, you can use default \p intrusive::striped_set::adapt metafunction;
244 - or your \p MyBestContainer class does not support bucket's interface, which means, that you should develop a specialization
245 <tt>cds::intrusive::striped_set::adapt<MyBestContainer> </tt> metafunction providing necessary interface.
247 The <tt>intrusive::striped_set::adapt< Container, OptionPack ></tt> metafunction has two template argument:
248 - \p Container is the class that should be used as the bucket, for example, <tt>boost::intrusive::list< T ></tt>.
249 - \p OptionPack is the packed options from \p %StripedSet declaration. The \p adapt metafunction can use
250 any option from \p OptionPack for its internal use. For example, a \p compare option can be passed to \p adapt
251 metafunction via \p OptionPack argument of \p %StripedSet declaration.
253 See intrusive::striped_set::adapt metafunction for the description of interface that the bucket container must provide
254 to be \p %StripedSet compatible.
256 template <class Container, typename... Options>
261 struct default_options {
262 typedef striped_set::striping<> mutex_policy;
263 typedef typename cds::opt::v::hash_selector< cds::opt::none >::type hash;
264 typedef cds::atomicity::item_counter item_counter;
265 typedef CDS_DEFAULT_ALLOCATOR allocator;
266 typedef cds::opt::none resizing_policy;
267 typedef cds::opt::none compare;
268 typedef cds::opt::none less;
271 typedef typename cds::opt::make_options<
272 typename cds::opt::find_type_traits< default_options, Options... >::type
277 typedef Container underlying_container_type ; ///< original intrusive container type for the bucket
278 typedef typename cds::intrusive::striped_set::adapt< underlying_container_type, Options... >::type bucket_type ; ///< container type adapted for hash set
279 typedef typename bucket_type::value_type value_type ; ///< value type stored in the set
281 typedef typename options::hash hash ; ///< Hash functor
282 typedef typename options::item_counter item_counter ; ///< Item counter
283 typedef typename cds::opt::select_default<
284 typename options::resizing_policy,
285 typename bucket_type::default_resizing_policy
286 >::type resizing_policy ; ///< Resizing policy
287 typedef typename options::allocator allocator_type ; ///< allocator type specified in options.
288 typedef typename options::mutex_policy mutex_policy ; ///< Mutex policy
290 typedef cds::details::Allocator< bucket_type, allocator_type > bucket_allocator; ///< bucket allocator type based on allocator_type
293 bucket_type * m_Buckets ; ///< Bucket table
294 size_t m_nBucketMask ; ///< Bucket table size - 1. m_nBucketMask + 1 should be power of two.
295 item_counter m_ItemCounter ; ///< Item counter
296 hash m_Hash ; ///< Hash functor
298 mutex_policy m_MutexPolicy ; ///< Mutex policy
299 resizing_policy m_ResizingPolicy; ///< Resizing policy
301 static const size_t c_nMinimalCapacity = 16 ; ///< Minimal capacity
305 typedef typename mutex_policy::scoped_cell_lock scoped_cell_lock;
306 typedef typename mutex_policy::scoped_full_lock scoped_full_lock;
307 typedef typename mutex_policy::scoped_resize_lock scoped_resize_lock;
312 static size_t calc_init_capacity( size_t nCapacity )
314 nCapacity = cds::beans::ceil2( nCapacity );
315 return nCapacity < c_nMinimalCapacity ? c_nMinimalCapacity : nCapacity;
318 void alloc_bucket_table( size_t nSize )
320 assert( cds::beans::is_power2( nSize ));
321 m_nBucketMask = nSize - 1;
322 m_Buckets = bucket_allocator().NewArray( nSize );
325 static void free_bucket_table( bucket_type * pBuckets, size_t nSize )
327 bucket_allocator().Delete( pBuckets, nSize );
330 template <typename Q>
331 size_t hashing( Q const& v ) const
336 bucket_type * bucket( size_t nHash ) const CDS_NOEXCEPT
338 return m_Buckets + (nHash & m_nBucketMask);
341 template <typename Q, typename Func>
342 bool find_( Q& val, Func f )
344 size_t nHash = hashing( val );
346 scoped_cell_lock sl( m_MutexPolicy, nHash );
347 return bucket( nHash )->find( val, f );
350 template <typename Q, typename Less, typename Func>
351 bool find_with_( Q& val, Less pred, Func f )
353 size_t nHash = hashing( val );
354 scoped_cell_lock sl( m_MutexPolicy, nHash );
355 return bucket( nHash )->find( val, pred, f );
358 void internal_resize( size_t nNewCapacity )
360 // All locks are already locked!
361 m_MutexPolicy.resize( nNewCapacity );
363 size_t nOldCapacity = bucket_count();
364 bucket_type * pOldBuckets = m_Buckets;
366 alloc_bucket_table( nNewCapacity );
368 typedef typename bucket_type::iterator bucket_iterator;
369 bucket_type * pEnd = pOldBuckets + nOldCapacity;
370 for ( bucket_type * pCur = pOldBuckets; pCur != pEnd; ++pCur ) {
371 bucket_iterator itEnd = pCur->end();
372 bucket_iterator itNext;
373 for ( bucket_iterator it = pCur->begin(); it != itEnd; it = itNext ) {
376 bucket( m_Hash( *it ) )->move_item( *pCur, it );
381 free_bucket_table( pOldBuckets, nOldCapacity );
383 m_ResizingPolicy.reset();
388 size_t nOldCapacity = bucket_count();
389 size_t volatile& refBucketMask = m_nBucketMask;
391 scoped_resize_lock al( m_MutexPolicy );
392 if ( al.success() ) {
393 if ( nOldCapacity != refBucketMask + 1 ) {
394 // someone resized already
398 internal_resize( nOldCapacity * 2 );
405 /// Default ctor. The initial capacity is 16.
407 : m_Buckets( nullptr )
408 , m_nBucketMask( c_nMinimalCapacity - 1 )
409 , m_MutexPolicy( c_nMinimalCapacity )
411 alloc_bucket_table( m_nBucketMask + 1 );
414 /// Ctor with initial capacity specified
416 size_t nCapacity ///< Initial size of bucket table and lock array. Must be power of two, the minimum is 16.
418 : m_Buckets( nullptr )
419 , m_nBucketMask( calc_init_capacity(nCapacity) - 1 )
420 , m_MutexPolicy( m_nBucketMask + 1 )
422 alloc_bucket_table( m_nBucketMask + 1 );
425 /// Ctor with resizing policy (copy semantics)
427 This constructor initializes m_ResizingPolicy member with copy of \p resizingPolicy parameter
430 size_t nCapacity ///< Initial size of bucket table and lock array. Must be power of two, the minimum is 16.
431 ,resizing_policy const& resizingPolicy ///< Resizing policy
433 : m_Buckets( nullptr )
434 , m_nBucketMask( ( nCapacity ? calc_init_capacity(nCapacity) : c_nMinimalCapacity ) - 1 )
435 , m_MutexPolicy( m_nBucketMask + 1 )
436 , m_ResizingPolicy( resizingPolicy )
438 alloc_bucket_table( m_nBucketMask + 1 );
441 /// Ctor with resizing policy (move semantics)
443 This constructor initializes m_ResizingPolicy member moving \p resizingPolicy parameter
444 Move semantics is used.
447 size_t nCapacity ///< Initial size of bucket table and lock array. Must be power of two, the minimum is 16.
448 ,resizing_policy&& resizingPolicy ///< Resizing policy
450 : m_Buckets( nullptr )
451 , m_nBucketMask( ( nCapacity ? calc_init_capacity(nCapacity) : c_nMinimalCapacity ) - 1 )
452 , m_MutexPolicy( m_nBucketMask + 1 )
453 , m_ResizingPolicy( std::forward<resizing_policy>( resizingPolicy ) )
455 alloc_bucket_table( m_nBucketMask + 1 );
458 /// Destructor destroys internal data
461 free_bucket_table( m_Buckets, m_nBucketMask + 1 );
467 The function inserts \p val in the set if it does not contain
468 an item with key equal to \p val.
470 Returns \p true if \p val is placed into the set, \p false otherwise.
472 bool insert( value_type& val )
474 return insert( val, []( value_type& ) {} );
479 The function allows to split creating of new item into two part:
480 - create item with key only
481 - insert new item into the set
482 - if inserting is success, calls \p f functor to initialize value-field of \p val.
484 The functor signature is:
486 void func( value_type& val );
488 where \p val is the item inserted.
490 The user-defined functor is called only if the inserting is success and can be passed by reference
491 using <tt>boost::ref</tt>
493 template <typename Func>
494 bool insert( value_type& val, Func f )
498 size_t nHash = hashing( val );
499 bucket_type * pBucket;
501 scoped_cell_lock sl( m_MutexPolicy, nHash );
502 pBucket = bucket( nHash );
503 bOk = pBucket->insert( val, f );
504 bResize = bOk && m_ResizingPolicy( ++m_ItemCounter, *this, *pBucket );
512 /// Ensures that the \p val exists in the set
514 The operation performs inserting or changing data with lock-free manner.
516 If the item \p val not found in the set, then \p val is inserted into the set.
517 Otherwise, the functor \p func is called with item found.
518 The functor signature is:
520 void func( bool bNew, value_type& item, value_type& val );
523 - \p bNew - \p true if the item has been inserted, \p false otherwise
524 - \p item - item of the set
525 - \p val - argument \p val passed into the \p ensure function
526 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
527 refers to the same thing.
529 The functor may change non-key fields of the \p item.
531 You may pass \p func argument by reference using <tt>boost::ref</tt> or cds::ref.
533 Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successful,
534 \p second is \p true if new item has been added or \p false if the item with \p key
535 already is in the set.
537 template <typename Func>
538 std::pair<bool, bool> ensure( value_type& val, Func func )
540 std::pair<bool, bool> result;
542 size_t nHash = hashing( val );
543 bucket_type * pBucket;
545 scoped_cell_lock sl( m_MutexPolicy, nHash );
546 pBucket = bucket( nHash );
548 result = pBucket->ensure( val, func );
549 bResize = result.first && result.second && m_ResizingPolicy( ++m_ItemCounter, *this, *pBucket );
557 /// Unlink the item \p val from the set
559 The function searches the item \p val in the set and unlink it
560 if it is found and is equal to \p val (here, the equality means that
561 \p val belongs to the set: if \p item is an item found then
562 unlink is successful iif <tt>&val == &item</tt>)
564 The function returns \p true if success and \p false otherwise.
566 bool unlink( value_type& val )
569 size_t nHash = hashing( val );
571 scoped_cell_lock sl( m_MutexPolicy, nHash );
572 bOk = bucket( nHash )->unlink( val );
580 /// Deletes the item from the set
581 /** \anchor cds_intrusive_StripedSet_erase
582 The function searches an item with key equal to \p val in the set,
583 unlinks it from the set, and returns a pointer to unlinked item.
585 If the item with key equal to \p val is not found the function return \p nullptr.
587 Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
589 template <typename Q>
590 value_type * erase( Q const& val )
592 return erase( val, [](value_type const&) {} );
595 /// Deletes the item from the set using \p pred predicate for searching
597 The function is an analog of \ref cds_intrusive_StripedSet_erase "erase(Q const&)"
598 but \p pred is used for key comparing
599 \p Less has the interface like \p std::less.
600 \p pred must imply the same element order as the comparator used for building the set.
602 template <typename Q, typename Less>
603 value_type * erase_with( Q const& val, Less pred )
605 return erase_with( val, pred, [](value_type const&) {} );
608 /// Deletes the item from the set
609 /** \anchor cds_intrusive_StripedSet_erase_func
611 The function searches an item with key equal to \p val in the set,
612 call \p f functor with item found, unlinks it from the set, and returns a pointer to unlinked item.
614 The \p Func interface is
617 void operator()( value_type const& item );
620 The functor may be passed by reference with <tt>boost:ref</tt>
622 If the item with key equal to \p val is not found the function return \p false.
624 Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
626 template <typename Q, typename Func>
627 value_type * erase( Q const& val, Func f )
629 size_t nHash = hashing( val );
632 scoped_cell_lock sl( m_MutexPolicy, nHash );
633 pVal = bucket( nHash )->erase( val, f );
641 /// Deletes the item from the set using \p pred predicate for searching
643 The function is an analog of \ref cds_intrusive_StripedSet_erase_func "erase(Q const&, Func)"
644 but \p pred is used for key comparing
645 \p Less has the interface like \p std::less.
646 \p pred must imply the same element order as the comparator used for building the set.
648 template <typename Q, typename Less, typename Func>
649 value_type * erase_with( Q const& val, Less pred, Func f )
651 size_t nHash = hashing( val );
654 scoped_cell_lock sl( m_MutexPolicy, nHash );
655 pVal = bucket( nHash )->erase( val, pred, f );
663 /// Find the key \p val
664 /** \anchor cds_intrusive_StripedSet_find_func
665 The function searches the item with key equal to \p val and calls the functor \p f for item found.
666 The interface of \p Func functor is:
669 void operator()( value_type& item, Q& val );
672 where \p item is the item found, \p val is the <tt>find</tt> function argument.
674 You can pass \p f argument by reference using <tt>boost::ref</tt> or cds::ref.
676 The functor may change non-key fields of \p item.
678 The \p val argument is non-const since it can be used as \p f functor destination i.e., the functor
679 may modify both arguments.
681 Note the hash functor specified for class \p Traits template parameter
682 should accept a parameter of type \p Q that can be not the same as \p value_type.
684 The function returns \p true if \p val is found, \p false otherwise.
686 template <typename Q, typename Func>
687 bool find( Q& val, Func f )
689 return find_( val, f );
692 /// Find the key \p val using \p pred predicate
694 The function is an analog of \ref cds_intrusive_StripedSet_find_func "find(Q&, Func)"
695 but \p pred is used for key comparing
696 \p Less has the interface like \p std::less.
697 \p pred must imply the same element order as the comparator used for building the set.
699 template <typename Q, typename Less, typename Func>
700 bool find_with( Q& val, Less pred, Func f )
702 return find_with_( val, pred, f );
705 /// Find the key \p val
706 /** \anchor cds_intrusive_StripedSet_find_cfunc
707 The function searches the item with key equal to \p val and calls the functor \p f for item found.
708 The interface of \p Func functor is:
711 void operator()( value_type& item, Q const& val );
714 where \p item is the item found, \p val is the <tt>find</tt> function argument.
716 You can pass \p f argument by reference using <tt>boost::ref</tt> or cds::ref.
718 The functor may change non-key fields of \p item.
720 The \p val argument is non-const since it can be used as \p f functor destination i.e., the functor
721 may modify both arguments.
723 The function returns \p true if \p val is found, \p false otherwise.
725 template <typename Q, typename Func>
726 bool find( Q const& val, Func f )
728 return find_( val, f );
731 /// Find the key \p val using \p pred predicate
733 The function is an analog of \ref cds_intrusive_StripedSet_find_cfunc "find(Q const&, Func)"
734 but \p pred is used for key comparing
735 \p Less has the interface like \p std::less.
736 \p pred must imply the same element order as the comparator used for building the set.
738 template <typename Q, typename Less, typename Func>
739 bool find_with( Q const& val, Less pred, Func f )
741 return find_with_( val, pred, f );
744 /// Find the key \p val
745 /** \anchor cds_intrusive_StripedSet_find_val
746 The function searches the item with key equal to \p val
747 and returns \p true if it is found, and \p false otherwise.
749 Note the hash functor specified for class \p Traits template parameter
750 should accept a parameter of type \p Q that can be not the same as \p value_type.
752 template <typename Q>
753 bool find( Q const& val )
755 return find( val, [](value_type&, Q const& ) {} );
758 /// Find the key \p val using \p pred predicate
760 The function is an analog of \ref cds_intrusive_StripedSet_find_val "find(Q const&)"
761 but \p pred is used for key comparing
762 \p Less has the interface like \p std::less.
763 \p pred must imply the same element order as the comparator used for building the set.
765 template <typename Q, typename Less>
766 bool find_with( Q const& val, Less pred )
768 return find_with( val, pred, [](value_type& , Q const& ) {} );
773 The function unlinks all items from the set.
777 // locks entire array
778 scoped_full_lock sl( m_MutexPolicy );
780 size_t nBucketCount = bucket_count();
781 bucket_type * pBucket = m_Buckets;
782 for ( size_t i = 0; i < nBucketCount; ++i, ++pBucket )
784 m_ItemCounter.reset();
787 /// Clears the set and calls \p disposer for each item
789 The function unlinks all items from the set calling \p disposer for each item.
790 \p Disposer functor interface is:
793 void operator()( value_type * p );
797 template <typename Disposer>
798 void clear_and_dispose( Disposer disposer )
800 // locks entire array
801 scoped_full_lock sl( m_MutexPolicy );
803 size_t nBucketCount = bucket_count();
804 bucket_type * pBucket = m_Buckets;
805 for ( size_t i = 0; i < nBucketCount; ++i, ++pBucket )
806 pBucket->clear( disposer );
807 m_ItemCounter.reset();
810 /// Checks if the set is empty
812 Emptiness is checked by item counting: if item count is zero then the set is empty.
819 /// Returns item count in the set
822 return m_ItemCounter;
825 /// Returns the size of hash table
827 The hash table size is non-constant and can be increased via resizing.
829 size_t bucket_count() const
831 return m_nBucketMask + 1;
834 /// Returns lock array size
835 size_t lock_count() const
837 return m_MutexPolicy.lock_count();
840 /// Returns resizing policy object
841 resizing_policy& get_resizing_policy()
843 return m_ResizingPolicy;
846 /// Returns resizing policy (const version)
847 resizing_policy const& get_resizing_policy() const
849 return m_ResizingPolicy;
852 }} // namespace cds::itrusive
854 #endif // #ifndef __CDS_INTRUSIVE_STRIPED_SET_H