3 #ifndef __CDS_INTRUSIVE_STRIPED_SET_H
4 #define __CDS_INTRUSIVE_STRIPED_SET_H
6 #include <cds/intrusive/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;
309 # ifndef CDS_CXX11_LAMBDA_SUPPORT
310 struct empty_insert_functor {
311 void operator()( value_type& )
315 struct empty_erase_functor {
316 void operator()( value_type const& )
320 struct empty_find_functor {
321 template <typename Q>
322 void operator()( value_type& item, Q& val )
330 static size_t calc_init_capacity( size_t nCapacity )
332 nCapacity = cds::beans::ceil2( nCapacity );
333 return nCapacity < c_nMinimalCapacity ? c_nMinimalCapacity : nCapacity;
336 void alloc_bucket_table( size_t nSize )
338 assert( cds::beans::is_power2( nSize ));
339 m_nBucketMask = nSize - 1;
340 m_Buckets = bucket_allocator().NewArray( nSize );
343 static void free_bucket_table( bucket_type * pBuckets, size_t nSize )
345 bucket_allocator().Delete( pBuckets, nSize );
348 template <typename Q>
349 size_t hashing( Q const& v ) const
354 bucket_type * bucket( size_t nHash ) const CDS_NOEXCEPT
356 return m_Buckets + (nHash & m_nBucketMask);
359 template <typename Q, typename Func>
360 bool find_( Q& val, Func f )
362 size_t nHash = hashing( val );
364 scoped_cell_lock sl( m_MutexPolicy, nHash );
365 return bucket( nHash )->find( val, f );
368 template <typename Q, typename Less, typename Func>
369 bool find_with_( Q& val, Less pred, Func f )
371 size_t nHash = hashing( val );
372 scoped_cell_lock sl( m_MutexPolicy, nHash );
373 return bucket( nHash )->find( val, pred, f );
376 void internal_resize( size_t nNewCapacity )
378 // All locks are already locked!
379 m_MutexPolicy.resize( nNewCapacity );
381 size_t nOldCapacity = bucket_count();
382 bucket_type * pOldBuckets = m_Buckets;
384 alloc_bucket_table( nNewCapacity );
386 typedef typename bucket_type::iterator bucket_iterator;
387 bucket_type * pEnd = pOldBuckets + nOldCapacity;
388 for ( bucket_type * pCur = pOldBuckets; pCur != pEnd; ++pCur ) {
389 bucket_iterator itEnd = pCur->end();
390 bucket_iterator itNext;
391 for ( bucket_iterator it = pCur->begin(); it != itEnd; it = itNext ) {
394 bucket( m_Hash( *it ) )->move_item( *pCur, it );
399 free_bucket_table( pOldBuckets, nOldCapacity );
401 m_ResizingPolicy.reset();
406 size_t nOldCapacity = bucket_count();
407 size_t volatile& refBucketMask = m_nBucketMask;
409 scoped_resize_lock al( m_MutexPolicy );
410 if ( al.success() ) {
411 if ( nOldCapacity != refBucketMask + 1 ) {
412 // someone resized already
416 internal_resize( nOldCapacity * 2 );
423 /// Default ctor. The initial capacity is 16.
425 : m_Buckets( nullptr )
426 , m_nBucketMask( c_nMinimalCapacity - 1 )
427 , m_MutexPolicy( c_nMinimalCapacity )
429 alloc_bucket_table( m_nBucketMask + 1 );
432 /// Ctor with initial capacity specified
434 size_t nCapacity ///< Initial size of bucket table and lock array. Must be power of two, the minimum is 16.
436 : m_Buckets( nullptr )
437 , m_nBucketMask( calc_init_capacity(nCapacity) - 1 )
438 , m_MutexPolicy( m_nBucketMask + 1 )
440 alloc_bucket_table( m_nBucketMask + 1 );
443 /// Ctor with resizing policy (copy semantics)
445 This constructor initializes m_ResizingPolicy member with copy of \p resizingPolicy parameter
448 size_t nCapacity ///< Initial size of bucket table and lock array. Must be power of two, the minimum is 16.
449 ,resizing_policy const& resizingPolicy ///< Resizing policy
451 : m_Buckets( nullptr )
452 , m_nBucketMask( ( nCapacity ? calc_init_capacity(nCapacity) : c_nMinimalCapacity ) - 1 )
453 , m_MutexPolicy( m_nBucketMask + 1 )
454 , m_ResizingPolicy( resizingPolicy )
456 alloc_bucket_table( m_nBucketMask + 1 );
459 /// Ctor with resizing policy (move semantics)
461 This constructor initializes m_ResizingPolicy member moving \p resizingPolicy parameter
462 Move semantics is used.
465 size_t nCapacity ///< Initial size of bucket table and lock array. Must be power of two, the minimum is 16.
466 ,resizing_policy&& resizingPolicy ///< Resizing policy
468 : m_Buckets( nullptr )
469 , m_nBucketMask( ( nCapacity ? calc_init_capacity(nCapacity) : c_nMinimalCapacity ) - 1 )
470 , m_MutexPolicy( m_nBucketMask + 1 )
471 , m_ResizingPolicy( std::forward<resizing_policy>( resizingPolicy ) )
473 alloc_bucket_table( m_nBucketMask + 1 );
476 /// Destructor destroys internal data
479 free_bucket_table( m_Buckets, m_nBucketMask + 1 );
485 The function inserts \p val in the set if it does not contain
486 an item with key equal to \p val.
488 Returns \p true if \p val is placed into the set, \p false otherwise.
490 bool insert( value_type& val )
492 # ifdef CDS_CXX11_LAMBDA_SUPPORT
493 return insert( val, []( value_type& ) {} );
495 return insert( val, empty_insert_functor() );
501 The function allows to split creating of new item into two part:
502 - create item with key only
503 - insert new item into the set
504 - if inserting is success, calls \p f functor to initialize value-field of \p val.
506 The functor signature is:
508 void func( value_type& val );
510 where \p val is the item inserted.
512 The user-defined functor is called only if the inserting is success and can be passed by reference
513 using <tt>boost::ref</tt>
515 template <typename Func>
516 bool insert( value_type& val, Func f )
520 size_t nHash = hashing( val );
521 bucket_type * pBucket;
523 scoped_cell_lock sl( m_MutexPolicy, nHash );
524 pBucket = bucket( nHash );
525 bOk = pBucket->insert( val, f );
526 bResize = bOk && m_ResizingPolicy( ++m_ItemCounter, *this, *pBucket );
534 /// Ensures that the \p val exists in the set
536 The operation performs inserting or changing data with lock-free manner.
538 If the item \p val not found in the set, then \p val is inserted into the set.
539 Otherwise, the functor \p func is called with item found.
540 The functor signature is:
542 void func( bool bNew, value_type& item, value_type& val );
545 - \p bNew - \p true if the item has been inserted, \p false otherwise
546 - \p item - item of the set
547 - \p val - argument \p val passed into the \p ensure function
548 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
549 refers to the same thing.
551 The functor may change non-key fields of the \p item.
553 You may pass \p func argument by reference using <tt>boost::ref</tt> or cds::ref.
555 Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successful,
556 \p second is \p true if new item has been added or \p false if the item with \p key
557 already is in the set.
559 template <typename Func>
560 std::pair<bool, bool> ensure( value_type& val, Func func )
562 std::pair<bool, bool> result;
564 size_t nHash = hashing( val );
565 bucket_type * pBucket;
567 scoped_cell_lock sl( m_MutexPolicy, nHash );
568 pBucket = bucket( nHash );
570 result = pBucket->ensure( val, func );
571 bResize = result.first && result.second && m_ResizingPolicy( ++m_ItemCounter, *this, *pBucket );
579 /// Unlink the item \p val from the set
581 The function searches the item \p val in the set and unlink it
582 if it is found and is equal to \p val (here, the equality means that
583 \p val belongs to the set: if \p item is an item found then
584 unlink is successful iif <tt>&val == &item</tt>)
586 The function returns \p true if success and \p false otherwise.
588 bool unlink( value_type& val )
591 size_t nHash = hashing( val );
593 scoped_cell_lock sl( m_MutexPolicy, nHash );
594 bOk = bucket( nHash )->unlink( val );
602 /// Deletes the item from the set
603 /** \anchor cds_intrusive_StripedSet_erase
604 The function searches an item with key equal to \p val in the set,
605 unlinks it from the set, and returns a pointer to unlinked item.
607 If the item with key equal to \p val is not found the function return \p nullptr.
609 Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
611 template <typename Q>
612 value_type * erase( Q const& val )
614 # ifdef CDS_CXX11_LAMBDA_SUPPORT
615 return erase( val, [](value_type const&) {} );
617 return erase( val, empty_erase_functor() );
621 /// Deletes the item from the set using \p pred predicate for searching
623 The function is an analog of \ref cds_intrusive_StripedSet_erase "erase(Q const&)"
624 but \p pred is used for key comparing
625 \p Less has the interface like \p std::less.
626 \p pred must imply the same element order as the comparator used for building the set.
628 template <typename Q, typename Less>
629 value_type * erase_with( Q const& val, Less pred )
631 # ifdef CDS_CXX11_LAMBDA_SUPPORT
632 return erase_with( val, pred, [](value_type const&) {} );
634 return erase_with( val, pred, empty_erase_functor() );
638 /// Deletes the item from the set
639 /** \anchor cds_intrusive_StripedSet_erase_func
641 The function searches an item with key equal to \p val in the set,
642 call \p f functor with item found, unlinks it from the set, and returns a pointer to unlinked item.
644 The \p Func interface is
647 void operator()( value_type const& item );
650 The functor may be passed by reference with <tt>boost:ref</tt>
652 If the item with key equal to \p val is not found the function return \p false.
654 Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
656 template <typename Q, typename Func>
657 value_type * erase( Q const& val, Func f )
659 size_t nHash = hashing( val );
662 scoped_cell_lock sl( m_MutexPolicy, nHash );
663 pVal = bucket( nHash )->erase( val, f );
671 /// Deletes the item from the set using \p pred predicate for searching
673 The function is an analog of \ref cds_intrusive_StripedSet_erase_func "erase(Q const&, Func)"
674 but \p pred is used for key comparing
675 \p Less has the interface like \p std::less.
676 \p pred must imply the same element order as the comparator used for building the set.
678 template <typename Q, typename Less, typename Func>
679 value_type * erase_with( Q const& val, Less pred, Func f )
681 size_t nHash = hashing( val );
684 scoped_cell_lock sl( m_MutexPolicy, nHash );
685 pVal = bucket( nHash )->erase( val, pred, f );
693 /// Find the key \p val
694 /** \anchor cds_intrusive_StripedSet_find_func
695 The function searches the item with key equal to \p val and calls the functor \p f for item found.
696 The interface of \p Func functor is:
699 void operator()( value_type& item, Q& val );
702 where \p item is the item found, \p val is the <tt>find</tt> function argument.
704 You can pass \p f argument by reference using <tt>boost::ref</tt> or cds::ref.
706 The functor may change non-key fields of \p item.
708 The \p val argument is non-const since it can be used as \p f functor destination i.e., the functor
709 may modify both arguments.
711 Note the hash functor specified for class \p Traits template parameter
712 should accept a parameter of type \p Q that can be not the same as \p value_type.
714 The function returns \p true if \p val is found, \p false otherwise.
716 template <typename Q, typename Func>
717 bool find( Q& val, Func f )
719 return find_( val, f );
722 /// Find the key \p val using \p pred predicate
724 The function is an analog of \ref cds_intrusive_StripedSet_find_func "find(Q&, Func)"
725 but \p pred is used for key comparing
726 \p Less has the interface like \p std::less.
727 \p pred must imply the same element order as the comparator used for building the set.
729 template <typename Q, typename Less, typename Func>
730 bool find_with( Q& val, Less pred, Func f )
732 return find_with_( val, pred, f );
735 /// Find the key \p val
736 /** \anchor cds_intrusive_StripedSet_find_cfunc
737 The function searches the item with key equal to \p val and calls the functor \p f for item found.
738 The interface of \p Func functor is:
741 void operator()( value_type& item, Q const& val );
744 where \p item is the item found, \p val is the <tt>find</tt> function argument.
746 You can pass \p f argument by reference using <tt>boost::ref</tt> or cds::ref.
748 The functor may change non-key fields of \p item.
750 The \p val argument is non-const since it can be used as \p f functor destination i.e., the functor
751 may modify both arguments.
753 The function returns \p true if \p val is found, \p false otherwise.
755 template <typename Q, typename Func>
756 bool find( Q const& val, Func f )
758 return find_( val, f );
761 /// Find the key \p val using \p pred predicate
763 The function is an analog of \ref cds_intrusive_StripedSet_find_cfunc "find(Q const&, Func)"
764 but \p pred is used for key comparing
765 \p Less has the interface like \p std::less.
766 \p pred must imply the same element order as the comparator used for building the set.
768 template <typename Q, typename Less, typename Func>
769 bool find_with( Q const& val, Less pred, Func f )
771 return find_with_( val, pred, f );
774 /// Find the key \p val
775 /** \anchor cds_intrusive_StripedSet_find_val
776 The function searches the item with key equal to \p val
777 and returns \p true if it is found, and \p false otherwise.
779 Note the hash functor specified for class \p Traits template parameter
780 should accept a parameter of type \p Q that can be not the same as \p value_type.
782 template <typename Q>
783 bool find( Q const& val )
785 # ifdef CDS_CXX11_LAMBDA_SUPPORT
786 return find( val, [](value_type&, Q const& ) {} );
788 return find( val, empty_find_functor() );
792 /// Find the key \p val using \p pred predicate
794 The function is an analog of \ref cds_intrusive_StripedSet_find_val "find(Q const&)"
795 but \p pred is used for key comparing
796 \p Less has the interface like \p std::less.
797 \p pred must imply the same element order as the comparator used for building the set.
799 template <typename Q, typename Less>
800 bool find_with( Q const& val, Less pred )
802 # ifdef CDS_CXX11_LAMBDA_SUPPORT
803 return find_with( val, pred, [](value_type& , Q const& ) {} );
805 return find_with( val, pred, empty_find_functor() );
811 The function unlinks all items from the set.
815 // locks entire array
816 scoped_full_lock sl( m_MutexPolicy );
818 size_t nBucketCount = bucket_count();
819 bucket_type * pBucket = m_Buckets;
820 for ( size_t i = 0; i < nBucketCount; ++i, ++pBucket )
822 m_ItemCounter.reset();
825 /// Clears the set and calls \p disposer for each item
827 The function unlinks all items from the set calling \p disposer for each item.
828 \p Disposer functor interface is:
831 void operator()( value_type * p );
835 template <typename Disposer>
836 void clear_and_dispose( Disposer disposer )
838 // locks entire array
839 scoped_full_lock sl( m_MutexPolicy );
841 size_t nBucketCount = bucket_count();
842 bucket_type * pBucket = m_Buckets;
843 for ( size_t i = 0; i < nBucketCount; ++i, ++pBucket )
844 pBucket->clear( disposer );
845 m_ItemCounter.reset();
848 /// Checks if the set is empty
850 Emptiness is checked by item counting: if item count is zero then the set is empty.
857 /// Returns item count in the set
860 return m_ItemCounter;
863 /// Returns the size of hash table
865 The hash table size is non-constant and can be increased via resizing.
867 size_t bucket_count() const
869 return m_nBucketMask + 1;
872 /// Returns lock array size
873 size_t lock_count() const
875 return m_MutexPolicy.lock_count();
878 /// Returns resizing policy object
879 resizing_policy& get_resizing_policy()
881 return m_ResizingPolicy;
884 /// Returns resizing policy (const version)
885 resizing_policy const& get_resizing_policy() const
887 return m_ResizingPolicy;
890 }} // namespace cds::itrusive
892 #endif // #ifndef __CDS_INTRUSIVE_STRIPED_SET_H