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, CDS_DECL_OPTIONS9>
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, CDS_OPTIONS9 >::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, CDS_OPTIONS9 >::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 );
477 /// Destructor destroys internal data
480 free_bucket_table( m_Buckets, m_nBucketMask + 1 );
486 The function inserts \p val in the set if it does not contain
487 an item with key equal to \p val.
489 Returns \p true if \p val is placed into the set, \p false otherwise.
491 bool insert( value_type& val )
493 # ifdef CDS_CXX11_LAMBDA_SUPPORT
494 return insert( val, []( value_type& ) {} );
496 return insert( val, empty_insert_functor() );
502 The function allows to split creating of new item into two part:
503 - create item with key only
504 - insert new item into the set
505 - if inserting is success, calls \p f functor to initialize value-field of \p val.
507 The functor signature is:
509 void func( value_type& val );
511 where \p val is the item inserted.
513 The user-defined functor is called only if the inserting is success and can be passed by reference
514 using <tt>boost::ref</tt>
516 template <typename Func>
517 bool insert( value_type& val, Func f )
521 size_t nHash = hashing( val );
522 bucket_type * pBucket;
524 scoped_cell_lock sl( m_MutexPolicy, nHash );
525 pBucket = bucket( nHash );
526 bOk = pBucket->insert( val, f );
527 bResize = bOk && m_ResizingPolicy( ++m_ItemCounter, *this, *pBucket );
535 /// Ensures that the \p val exists in the set
537 The operation performs inserting or changing data with lock-free manner.
539 If the item \p val not found in the set, then \p val is inserted into the set.
540 Otherwise, the functor \p func is called with item found.
541 The functor signature is:
543 void func( bool bNew, value_type& item, value_type& val );
546 - \p bNew - \p true if the item has been inserted, \p false otherwise
547 - \p item - item of the set
548 - \p val - argument \p val passed into the \p ensure function
549 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
550 refers to the same thing.
552 The functor may change non-key fields of the \p item.
554 You may pass \p func argument by reference using <tt>boost::ref</tt> or cds::ref.
556 Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successful,
557 \p second is \p true if new item has been added or \p false if the item with \p key
558 already is in the set.
560 template <typename Func>
561 std::pair<bool, bool> ensure( value_type& val, Func func )
563 std::pair<bool, bool> result;
565 size_t nHash = hashing( val );
566 bucket_type * pBucket;
568 scoped_cell_lock sl( m_MutexPolicy, nHash );
569 pBucket = bucket( nHash );
571 result = pBucket->ensure( val, func );
572 bResize = result.first && result.second && m_ResizingPolicy( ++m_ItemCounter, *this, *pBucket );
580 /// Unlink the item \p val from the set
582 The function searches the item \p val in the set and unlink it
583 if it is found and is equal to \p val (here, the equality means that
584 \p val belongs to the set: if \p item is an item found then
585 unlink is successful iif <tt>&val == &item</tt>)
587 The function returns \p true if success and \p false otherwise.
589 bool unlink( value_type& val )
592 size_t nHash = hashing( val );
594 scoped_cell_lock sl( m_MutexPolicy, nHash );
595 bOk = bucket( nHash )->unlink( val );
603 /// Deletes the item from the set
604 /** \anchor cds_intrusive_StripedSet_erase
605 The function searches an item with key equal to \p val in the set,
606 unlinks it from the set, and returns a pointer to unlinked item.
608 If the item with key equal to \p val is not found the function return \p nullptr.
610 Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
612 template <typename Q>
613 value_type * erase( Q const& val )
615 # ifdef CDS_CXX11_LAMBDA_SUPPORT
616 return erase( val, [](value_type const&) {} );
618 return erase( val, empty_erase_functor() );
622 /// Deletes the item from the set using \p pred predicate for searching
624 The function is an analog of \ref cds_intrusive_StripedSet_erase "erase(Q const&)"
625 but \p pred is used for key comparing
626 \p Less has the interface like \p std::less.
627 \p pred must imply the same element order as the comparator used for building the set.
629 template <typename Q, typename Less>
630 value_type * erase_with( Q const& val, Less pred )
632 # ifdef CDS_CXX11_LAMBDA_SUPPORT
633 return erase_with( val, pred, [](value_type const&) {} );
635 return erase_with( val, pred, empty_erase_functor() );
639 /// Deletes the item from the set
640 /** \anchor cds_intrusive_StripedSet_erase_func
642 The function searches an item with key equal to \p val in the set,
643 call \p f functor with item found, unlinks it from the set, and returns a pointer to unlinked item.
645 The \p Func interface is
648 void operator()( value_type const& item );
651 The functor may be passed by reference with <tt>boost:ref</tt>
653 If the item with key equal to \p val is not found the function return \p false.
655 Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
657 template <typename Q, typename Func>
658 value_type * erase( Q const& val, Func f )
660 size_t nHash = hashing( val );
663 scoped_cell_lock sl( m_MutexPolicy, nHash );
664 pVal = bucket( nHash )->erase( val, f );
672 /// Deletes the item from the set using \p pred predicate for searching
674 The function is an analog of \ref cds_intrusive_StripedSet_erase_func "erase(Q const&, Func)"
675 but \p pred is used for key comparing
676 \p Less has the interface like \p std::less.
677 \p pred must imply the same element order as the comparator used for building the set.
679 template <typename Q, typename Less, typename Func>
680 value_type * erase_with( Q const& val, Less pred, Func f )
682 size_t nHash = hashing( val );
685 scoped_cell_lock sl( m_MutexPolicy, nHash );
686 pVal = bucket( nHash )->erase( val, pred, f );
694 /// Find the key \p val
695 /** \anchor cds_intrusive_StripedSet_find_func
696 The function searches the item with key equal to \p val and calls the functor \p f for item found.
697 The interface of \p Func functor is:
700 void operator()( value_type& item, Q& val );
703 where \p item is the item found, \p val is the <tt>find</tt> function argument.
705 You can pass \p f argument by reference using <tt>boost::ref</tt> or cds::ref.
707 The functor may change non-key fields of \p item.
709 The \p val argument is non-const since it can be used as \p f functor destination i.e., the functor
710 may modify both arguments.
712 Note the hash functor specified for class \p Traits template parameter
713 should accept a parameter of type \p Q that can be not the same as \p value_type.
715 The function returns \p true if \p val is found, \p false otherwise.
717 template <typename Q, typename Func>
718 bool find( Q& val, Func f )
720 return find_( val, f );
723 /// Find the key \p val using \p pred predicate
725 The function is an analog of \ref cds_intrusive_StripedSet_find_func "find(Q&, Func)"
726 but \p pred is used for key comparing
727 \p Less has the interface like \p std::less.
728 \p pred must imply the same element order as the comparator used for building the set.
730 template <typename Q, typename Less, typename Func>
731 bool find_with( Q& val, Less pred, Func f )
733 return find_with_( val, pred, f );
736 /// Find the key \p val
737 /** \anchor cds_intrusive_StripedSet_find_cfunc
738 The function searches the item with key equal to \p val and calls the functor \p f for item found.
739 The interface of \p Func functor is:
742 void operator()( value_type& item, Q const& val );
745 where \p item is the item found, \p val is the <tt>find</tt> function argument.
747 You can pass \p f argument by reference using <tt>boost::ref</tt> or cds::ref.
749 The functor may change non-key fields of \p item.
751 The \p val argument is non-const since it can be used as \p f functor destination i.e., the functor
752 may modify both arguments.
754 The function returns \p true if \p val is found, \p false otherwise.
756 template <typename Q, typename Func>
757 bool find( Q const& val, Func f )
759 return find_( val, f );
762 /// Find the key \p val using \p pred predicate
764 The function is an analog of \ref cds_intrusive_StripedSet_find_cfunc "find(Q const&, Func)"
765 but \p pred is used for key comparing
766 \p Less has the interface like \p std::less.
767 \p pred must imply the same element order as the comparator used for building the set.
769 template <typename Q, typename Less, typename Func>
770 bool find_with( Q const& val, Less pred, Func f )
772 return find_with_( val, pred, f );
775 /// Find the key \p val
776 /** \anchor cds_intrusive_StripedSet_find_val
777 The function searches the item with key equal to \p val
778 and returns \p true if it is found, and \p false otherwise.
780 Note the hash functor specified for class \p Traits template parameter
781 should accept a parameter of type \p Q that can be not the same as \p value_type.
783 template <typename Q>
784 bool find( Q const& val )
786 # ifdef CDS_CXX11_LAMBDA_SUPPORT
787 return find( val, [](value_type&, Q const& ) {} );
789 return find( val, empty_find_functor() );
793 /// Find the key \p val using \p pred predicate
795 The function is an analog of \ref cds_intrusive_StripedSet_find_val "find(Q const&)"
796 but \p pred is used for key comparing
797 \p Less has the interface like \p std::less.
798 \p pred must imply the same element order as the comparator used for building the set.
800 template <typename Q, typename Less>
801 bool find_with( Q const& val, Less pred )
803 # ifdef CDS_CXX11_LAMBDA_SUPPORT
804 return find_with( val, pred, [](value_type& , Q const& ) {} );
806 return find_with( val, pred, empty_find_functor() );
812 The function unlinks all items from the set.
816 // locks entire array
817 scoped_full_lock sl( m_MutexPolicy );
819 size_t nBucketCount = bucket_count();
820 bucket_type * pBucket = m_Buckets;
821 for ( size_t i = 0; i < nBucketCount; ++i, ++pBucket )
823 m_ItemCounter.reset();
826 /// Clears the set and calls \p disposer for each item
828 The function unlinks all items from the set calling \p disposer for each item.
829 \p Disposer functor interface is:
832 void operator()( value_type * p );
836 template <typename Disposer>
837 void clear_and_dispose( Disposer disposer )
839 // locks entire array
840 scoped_full_lock sl( m_MutexPolicy );
842 size_t nBucketCount = bucket_count();
843 bucket_type * pBucket = m_Buckets;
844 for ( size_t i = 0; i < nBucketCount; ++i, ++pBucket )
845 pBucket->clear( disposer );
846 m_ItemCounter.reset();
849 /// Checks if the set is empty
851 Emptiness is checked by item counting: if item count is zero then the set is empty.
858 /// Returns item count in the set
861 return m_ItemCounter;
864 /// Returns the size of hash table
866 The hash table size is non-constant and can be increased via resizing.
868 size_t bucket_count() const
870 return m_nBucketMask + 1;
873 /// Returns lock array size
874 size_t lock_count() const
876 return m_MutexPolicy.lock_count();
879 /// Returns resizing policy object
880 resizing_policy& get_resizing_policy()
882 return m_ResizingPolicy;
885 /// Returns resizing policy (const version)
886 resizing_policy const& get_resizing_policy() const
888 return m_ResizingPolicy;
891 }} // namespace cds::itrusive
893 #endif // #ifndef __CDS_INTRUSIVE_STRIPED_SET_H