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 #ifdef CDS_RVALUE_SUPPORT
460 /// Ctor with resizing policy (move semantics)
462 This constructor initializes m_ResizingPolicy member moving \p resizingPolicy parameter
463 Move semantics is used. Available only for the compilers that supports C++11 rvalue reference.
466 size_t nCapacity ///< Initial size of bucket table and lock array. Must be power of two, the minimum is 16.
467 ,resizing_policy&& resizingPolicy ///< Resizing policy
469 : m_Buckets( nullptr )
470 , m_nBucketMask( ( nCapacity ? calc_init_capacity(nCapacity) : c_nMinimalCapacity ) - 1 )
471 , m_MutexPolicy( m_nBucketMask + 1 )
472 , m_ResizingPolicy( resizingPolicy )
474 alloc_bucket_table( m_nBucketMask + 1 );
478 /// Destructor destroys internal data
481 free_bucket_table( m_Buckets, m_nBucketMask + 1 );
487 The function inserts \p val in the set if it does not contain
488 an item with key equal to \p val.
490 Returns \p true if \p val is placed into the set, \p false otherwise.
492 bool insert( value_type& val )
494 # ifdef CDS_CXX11_LAMBDA_SUPPORT
495 return insert( val, []( value_type& ) {} );
497 return insert( val, empty_insert_functor() );
503 The function allows to split creating of new item into two part:
504 - create item with key only
505 - insert new item into the set
506 - if inserting is success, calls \p f functor to initialize value-field of \p val.
508 The functor signature is:
510 void func( value_type& val );
512 where \p val is the item inserted.
514 The user-defined functor is called only if the inserting is success and can be passed by reference
515 using <tt>boost::ref</tt>
517 template <typename Func>
518 bool insert( value_type& val, Func f )
522 size_t nHash = hashing( val );
523 bucket_type * pBucket;
525 scoped_cell_lock sl( m_MutexPolicy, nHash );
526 pBucket = bucket( nHash );
527 bOk = pBucket->insert( val, f );
528 bResize = bOk && m_ResizingPolicy( ++m_ItemCounter, *this, *pBucket );
536 /// Ensures that the \p val exists in the set
538 The operation performs inserting or changing data with lock-free manner.
540 If the item \p val not found in the set, then \p val is inserted into the set.
541 Otherwise, the functor \p func is called with item found.
542 The functor signature is:
544 void func( bool bNew, value_type& item, value_type& val );
547 - \p bNew - \p true if the item has been inserted, \p false otherwise
548 - \p item - item of the set
549 - \p val - argument \p val passed into the \p ensure function
550 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
551 refers to the same thing.
553 The functor may change non-key fields of the \p item.
555 You may pass \p func argument by reference using <tt>boost::ref</tt> or cds::ref.
557 Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successful,
558 \p second is \p true if new item has been added or \p false if the item with \p key
559 already is in the set.
561 template <typename Func>
562 std::pair<bool, bool> ensure( value_type& val, Func func )
564 std::pair<bool, bool> result;
566 size_t nHash = hashing( val );
567 bucket_type * pBucket;
569 scoped_cell_lock sl( m_MutexPolicy, nHash );
570 pBucket = bucket( nHash );
572 result = pBucket->ensure( val, func );
573 bResize = result.first && result.second && m_ResizingPolicy( ++m_ItemCounter, *this, *pBucket );
581 /// Unlink the item \p val from the set
583 The function searches the item \p val in the set and unlink it
584 if it is found and is equal to \p val (here, the equality means that
585 \p val belongs to the set: if \p item is an item found then
586 unlink is successful iif <tt>&val == &item</tt>)
588 The function returns \p true if success and \p false otherwise.
590 bool unlink( value_type& val )
593 size_t nHash = hashing( val );
595 scoped_cell_lock sl( m_MutexPolicy, nHash );
596 bOk = bucket( nHash )->unlink( val );
604 /// Deletes the item from the set
605 /** \anchor cds_intrusive_StripedSet_erase
606 The function searches an item with key equal to \p val in the set,
607 unlinks it from the set, and returns a pointer to unlinked item.
609 If the item with key equal to \p val is not found the function return \p NULL.
611 Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
613 template <typename Q>
614 value_type * erase( Q const& val )
616 # ifdef CDS_CXX11_LAMBDA_SUPPORT
617 return erase( val, [](value_type const&) {} );
619 return erase( val, empty_erase_functor() );
623 /// Deletes the item from the set using \p pred predicate for searching
625 The function is an analog of \ref cds_intrusive_StripedSet_erase "erase(Q const&)"
626 but \p pred is used for key comparing
627 \p Less has the interface like \p std::less.
628 \p pred must imply the same element order as the comparator used for building the set.
630 template <typename Q, typename Less>
631 value_type * erase_with( Q const& val, Less pred )
633 # ifdef CDS_CXX11_LAMBDA_SUPPORT
634 return erase_with( val, pred, [](value_type const&) {} );
636 return erase_with( val, pred, empty_erase_functor() );
640 /// Deletes the item from the set
641 /** \anchor cds_intrusive_StripedSet_erase_func
643 The function searches an item with key equal to \p val in the set,
644 call \p f functor with item found, unlinks it from the set, and returns a pointer to unlinked item.
646 The \p Func interface is
649 void operator()( value_type const& item );
652 The functor may be passed by reference with <tt>boost:ref</tt>
654 If the item with key equal to \p val is not found the function return \p false.
656 Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
658 template <typename Q, typename Func>
659 value_type * erase( Q const& val, Func f )
661 size_t nHash = hashing( val );
664 scoped_cell_lock sl( m_MutexPolicy, nHash );
665 pVal = bucket( nHash )->erase( val, f );
673 /// Deletes the item from the set using \p pred predicate for searching
675 The function is an analog of \ref cds_intrusive_StripedSet_erase_func "erase(Q const&, Func)"
676 but \p pred is used for key comparing
677 \p Less has the interface like \p std::less.
678 \p pred must imply the same element order as the comparator used for building the set.
680 template <typename Q, typename Less, typename Func>
681 value_type * erase_with( Q const& val, Less pred, Func f )
683 size_t nHash = hashing( val );
686 scoped_cell_lock sl( m_MutexPolicy, nHash );
687 pVal = bucket( nHash )->erase( val, pred, f );
695 /// Find the key \p val
696 /** \anchor cds_intrusive_StripedSet_find_func
697 The function searches the item with key equal to \p val and calls the functor \p f for item found.
698 The interface of \p Func functor is:
701 void operator()( value_type& item, Q& val );
704 where \p item is the item found, \p val is the <tt>find</tt> function argument.
706 You can pass \p f argument by reference using <tt>boost::ref</tt> or cds::ref.
708 The functor may change non-key fields of \p item.
710 The \p val argument is non-const since it can be used as \p f functor destination i.e., the functor
711 may modify both arguments.
713 Note the hash functor specified for class \p Traits template parameter
714 should accept a parameter of type \p Q that can be not the same as \p value_type.
716 The function returns \p true if \p val is found, \p false otherwise.
718 template <typename Q, typename Func>
719 bool find( Q& val, Func f )
721 return find_( val, f );
724 /// Find the key \p val using \p pred predicate
726 The function is an analog of \ref cds_intrusive_StripedSet_find_func "find(Q&, Func)"
727 but \p pred is used for key comparing
728 \p Less has the interface like \p std::less.
729 \p pred must imply the same element order as the comparator used for building the set.
731 template <typename Q, typename Less, typename Func>
732 bool find_with( Q& val, Less pred, Func f )
734 return find_with_( val, pred, f );
737 /// Find the key \p val
738 /** \anchor cds_intrusive_StripedSet_find_cfunc
739 The function searches the item with key equal to \p val and calls the functor \p f for item found.
740 The interface of \p Func functor is:
743 void operator()( value_type& item, Q const& val );
746 where \p item is the item found, \p val is the <tt>find</tt> function argument.
748 You can pass \p f argument by reference using <tt>boost::ref</tt> or cds::ref.
750 The functor may change non-key fields of \p item.
752 The \p val argument is non-const since it can be used as \p f functor destination i.e., the functor
753 may modify both arguments.
755 The function returns \p true if \p val is found, \p false otherwise.
757 template <typename Q, typename Func>
758 bool find( Q const& val, Func f )
760 return find_( val, f );
763 /// Find the key \p val using \p pred predicate
765 The function is an analog of \ref cds_intrusive_StripedSet_find_cfunc "find(Q const&, Func)"
766 but \p pred is used for key comparing
767 \p Less has the interface like \p std::less.
768 \p pred must imply the same element order as the comparator used for building the set.
770 template <typename Q, typename Less, typename Func>
771 bool find_with( Q const& val, Less pred, Func f )
773 return find_with_( val, pred, f );
776 /// Find the key \p val
777 /** \anchor cds_intrusive_StripedSet_find_val
778 The function searches the item with key equal to \p val
779 and returns \p true if it is found, and \p false otherwise.
781 Note the hash functor specified for class \p Traits template parameter
782 should accept a parameter of type \p Q that can be not the same as \p value_type.
784 template <typename Q>
785 bool find( Q const& val )
787 # ifdef CDS_CXX11_LAMBDA_SUPPORT
788 return find( val, [](value_type&, Q const& ) {} );
790 return find( val, empty_find_functor() );
794 /// Find the key \p val using \p pred predicate
796 The function is an analog of \ref cds_intrusive_StripedSet_find_val "find(Q const&)"
797 but \p pred is used for key comparing
798 \p Less has the interface like \p std::less.
799 \p pred must imply the same element order as the comparator used for building the set.
801 template <typename Q, typename Less>
802 bool find_with( Q const& val, Less pred )
804 # ifdef CDS_CXX11_LAMBDA_SUPPORT
805 return find_with( val, pred, [](value_type& , Q const& ) {} );
807 return find_with( val, pred, empty_find_functor() );
813 The function unlinks all items from the set.
817 // locks entire array
818 scoped_full_lock sl( m_MutexPolicy );
820 size_t nBucketCount = bucket_count();
821 bucket_type * pBucket = m_Buckets;
822 for ( size_t i = 0; i < nBucketCount; ++i, ++pBucket )
824 m_ItemCounter.reset();
827 /// Clears the set and calls \p disposer for each item
829 The function unlinks all items from the set calling \p disposer for each item.
830 \p Disposer functor interface is:
833 void operator()( value_type * p );
837 template <typename Disposer>
838 void clear_and_dispose( Disposer disposer )
840 // locks entire array
841 scoped_full_lock sl( m_MutexPolicy );
843 size_t nBucketCount = bucket_count();
844 bucket_type * pBucket = m_Buckets;
845 for ( size_t i = 0; i < nBucketCount; ++i, ++pBucket )
846 pBucket->clear( disposer );
847 m_ItemCounter.reset();
850 /// Checks if the set is empty
852 Emptiness is checked by item counting: if item count is zero then the set is empty.
859 /// Returns item count in the set
862 return m_ItemCounter;
865 /// Returns the size of hash table
867 The hash table size is non-constant and can be increased via resizing.
869 size_t bucket_count() const
871 return m_nBucketMask + 1;
874 /// Returns lock array size
875 size_t lock_count() const
877 return m_MutexPolicy.lock_count();
880 /// Returns resizing policy object
881 resizing_policy& get_resizing_policy()
883 return m_ResizingPolicy;
886 /// Returns resizing policy (const version)
887 resizing_policy const& get_resizing_policy() const
889 return m_ResizingPolicy;
892 }} // namespace cds::itrusive
894 #endif // #ifndef __CDS_INTRUSIVE_STRIPED_SET_H