2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
6 Source code repo: http://github.com/khizmax/libcds/
7 Download: http://sourceforge.net/projects/libcds/files/
9 Redistribution and use in source and binary forms, with or without
10 modification, are permitted provided that the following conditions are met:
12 * Redistributions of source code must retain the above copyright notice, this
13 list of conditions and the following disclaimer.
15 * Redistributions in binary form must reproduce the above copyright notice,
16 this list of conditions and the following disclaimer in the documentation
17 and/or other materials provided with the distribution.
19 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
20 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
22 DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
23 FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
25 SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
26 CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
27 OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31 #ifndef CDSLIB_INTRUSIVE_STRIPED_SET_H
32 #define CDSLIB_INTRUSIVE_STRIPED_SET_H
34 #include <cds/intrusive/details/base.h>
35 #include <cds/intrusive/striped_set/adapter.h>
36 #include <cds/intrusive/striped_set/striping_policy.h>
38 namespace cds { namespace intrusive {
39 /// StripedSet related definitions
40 namespace striped_set {
42 /** @defgroup cds_striped_resizing_policy Resizing policy for striped/refinable set/map
44 Resizing policy for \p intrusive::StripedSet, \p container::StripedSet and \p container::StripedMap.
47 } // namespace striped_set
50 /** @ingroup cds_intrusive_map
53 - [2008] Maurice Herlihy, Nir Shavit "The Art of Multiprocessor Programming"
55 Lock striping is very simple technique.
56 The set consists of the bucket table and the array of locks.
57 Initially, the capacity of lock array and bucket table is the same.
58 When set is resized, bucket table capacity will be doubled but lock array will not.
59 The lock \p i protects each bucket \p j, where <tt> j = i mod L </tt>,
60 where \p L - the size of lock array.
63 - \p Container - the container class that is used as bucket table entry. The \p Container class should support
64 an uniform interface described below.
65 - \p Options - options
67 The \p %StripedSet class does not exactly dictate the type of container that should be used as a \p Container bucket.
68 Instead, the class supports different intrusive container type for the bucket, for exampe,
69 \p boost::intrusive::list, \p boost::intrusive::set and others.
71 Remember that \p %StripedSet class algorithm ensures sequential blocking access to its bucket through the mutex type you specify
72 among \p Options template arguments.
75 - \p opt::mutex_policy - concurrent access policy.
76 Available policies: \p striped_set::striping, \p striped_set::refinable.
77 Default is \p %striped_set::striping.
78 - \p cds::opt::hash - hash functor. Default option value see <tt>opt::v::hash_selector <opt::none></tt>
79 which selects default hash functor for your compiler.
80 - \p cds::opt::compare - key comparison functor. No default functor is provided.
81 If the option is not specified, the \p opt::less is used.
82 - \p cds::opt::less - specifies binary predicate used for key comparison. Default is \p std::less<T>.
83 - \p cds::opt::item_counter - item counter type. Default is \p atomicity::item_counter since some operation on the counter is performed
84 without locks. Note that item counting is an essential part of the set algorithm, so dummy counter like \p atomicity::empty_item_counter
86 - \p cds::opt::allocator - the allocator type using for memory allocation of bucket table and lock array. Default is \ref CDS_DEFAULT_ALLOCATOR.
87 - \p cds::opt::resizing_policy - the resizing policy - a functor that decides when to resize the hash set.
88 Default option value depends on bucket container type:
89 for sequential containers like \p boost::intrusive::list the resizing policy is <tt>cds::container::striped_set::load_factor_resizing<4> </tt>;
90 for other type of containers like \p boost::intrusive::set the resizing policy is cds::container::striped_set::no_resizing.
91 See \ref cds_striped_resizing_policy "available resizing policy".
92 Note that the choose of resizing policy depends of \p Container type:
93 for sequential containers like \p boost::intrusive::list the right policy can significantly improve performance.
94 For other, non-sequential types of \p Container (like a \p boost::intrusive::set) the resizing policy is not so important.
95 - \p cds::opt::buffer - an initialized buffer type used only for \p boost::intrusive::unordered_set.
96 Default is <tt>cds::opt::v::initialized_static_buffer< cds::any_type, 256 > </tt>.
98 \p opt::compare or \p opt::less options are used in some \p Container class for ordering.
99 \p %opt::compare option has the highest priority: if \p %opt::compare is specified, \p %opt::less is not used.
101 You can pass other option that would be passed to \p adapt metafunction, see below.
103 <b>Internal details</b>
105 The \p %StripedSet class cannot utilize the \p Container specified directly, but only its adapted variant which
106 supports an unified interface. Internally, the adaptation is made via \p intrusive::striped_set::adapt metafunction that wraps bucket container
107 and provides the unified bucket interface suitable for \p %StripedSet. Such adaptation is completely transparent for you -
108 you don't need to call \p adapt metafunction directly, \p %StripedSet class's internal machinery itself invokes appropriate
109 \p adapt metafunction specialization to adjust your \p Container container class to \p %StripedSet bucket's internal interface.
110 All you need is to include a right header before <tt>striped_set.h</tt>.
112 By default, <tt>intrusive::striped_set::adapt<AnyContainer, OptionPack> </tt> metafunction does not make any wrapping to \p AnyContainer,
113 so, the result <tt>intrusive::striped_set::adapt<AnyContainer, OptionPack>::type </tt> is the same as \p AnyContainer.
114 However, there are a lot of specializations of \p %intrusive::striped_set::adapt for \p boost::intrusive containers, see table below.
115 Any of this specialization wraps corresponding container making it suitable for the set's bucket.
116 Remember, you should include the proper header file for \p adapt <b>before</b> including <tt>striped_set.h</tt>.
118 \note It is important to specify <tt>boost::intrusive::constant_time_size<true></tt> option
119 for all \p boost::intrusive container that supports this option. Fast item counting feature is essential part of
120 \p %StripedSet resizing algorithm.
125 <th>.h-file for \p adapt</th>
130 <td> \p boost::intrusive::list</td>
131 <td><tt><cds/intrusive/striped_set/boost_list.h></tt></td>
133 #include <cds/intrusive/striped_set/boost_list.h>
134 #include <cds/intrusive/striped_set.h>
135 typedef cds::intrusive::StripedSet<
136 boost::intrusive::list<T, boost::intrusive::constant_time_size<true> >,
137 cds::opt::less< std::less<T> >
143 Template argument pack \p Options <b>must</b> contain cds::opt::less or cds::opt::compare for type \p T stored in the list
147 <td> \p boost::intrusive::slist</td>
148 <td><tt><cds/intrusive/striped_set/boost_slist.h></tt></td>
150 #include <cds/intrusive/striped_set/boost_slist.h>
151 #include <cds/intrusive/striped_set.h>
152 typedef cds::intrusive::StripedSet<
153 boost::intrusive::slist<T, boost::intrusive::constant_time_size<true> >,
154 cds::opt::less< std::less<T> >
160 Template argument pack \p Options <b>must</b> contain \p cds::opt::less or \p cds::opt::compare for type \p T stored in the list
164 <td> \p boost::intrusive::set</td>
165 <td><tt><cds/intrusive/striped_set/boost_set.h></tt></td>
167 #include <cds/intrusive/striped_set/boost_set.h>
168 #include <cds/intrusive/striped_set.h>
169 typedef cds::intrusive::StripedSet<
170 boost::intrusive::set<T, boost::intrusive::constant_time_size<true> >
175 Note that \p boost::intrusive::compare option using in \p boost::intrusive::set
176 should support \p T type stored in the set and any type \p Q that you can use
177 in \p erase() and \p find() member functions.
181 <td> \p boost::intrusive::unordered_set</td>
182 <td><tt><cds/intrusive/striped_set/boost_unordered_set.h></tt></td>
184 #include <cds/intrusive/striped_set/boost_unordered_set.h>
185 #include <cds/intrusive/striped_set.h>
186 typedef cds::intrusive::StripedSet<
187 boost::intrusive::unordered_set<T
188 ,boost::intrusive::constant_time_size<true>
189 ,boost::intrusive::hash< user_provided_hash_functor >
195 You should provide two different hash function \p h1 and \p h2 - one for \p boost::intrusive::unordered_set
196 and other for \p %StripedSet. For the best result, \p h1 and \p h2 must be orthogonal i.e. <tt>h1(X) != h2(X)</tt> for any value \p X
198 The option \p opt::buffer is used for \p boost::intrusive::bucket_traits.
199 Default is <tt> cds::opt::v::initialized_static_buffer< cds::any_type, 256 > </tt>.
200 The resizing policy should correlate with the buffer capacity.
201 The default resizing policy is <tt>cds::container::striped_set::load_factor_resizing<256> </tt> what gives load factor 1 for
202 default bucket buffer that is the best for \p boost::intrusive::unordered_set.
206 <td> \p boost::intrusive::avl_set</td>
207 <td><tt><cds/intrusive/striped_set/boost_avl_set.h></tt></td>
209 #include <cds/intrusive/striped_set/boost_avl_set.h>
210 #include <cds/intrusive/striped_set.h>
211 typedef cds::intrusive::StripedSet<
212 boost::intrusive::avl_set<T, boost::intrusive::constant_time_size<true> >
217 Note that \p boost::intrusive::compare option using in \p boost::intrusive::avl_set
218 should support \p T type stored in the set and any type \p Q that you can use
219 in \p erase() and \p find() member functions.
223 <td> \p boost::intrusive::sg_set</td>
224 <td><tt><cds/intrusive/striped_set/boost_sg_set.h></tt></td>
226 #include <cds/intrusive/striped_set/boost_sg_set.h>
227 #include <cds/intrusive/striped_set.h>
228 typedef cds::intrusive::StripedSet<
229 boost::intrusive::sg_set<T, boost::intrusive::constant_time_size<true> >
234 Note that \p boost::intrusive::compare option using in \p boost::intrusive::sg_set
235 should support \p T type stored in the set and any type \p Q that you can use
236 in \p erase() and \p find() member functions.
240 <td> \p boost::intrusive::splay_set</td>
241 <td><tt><cds/intrusive/striped_set/boost_splay_set.h></tt></td>
243 #include <cds/intrusive/striped_set/boost_splay_set.h>
244 #include <cds/intrusive/striped_set.h>
245 typedef cds::intrusive::StripedSet<
246 boost::intrusive::splay_set<T, boost::intrusive::constant_time_size<true> >
251 Note that \p boost::intrusive::compare option using in \p boost::intrusive::splay_set
252 should support \p T type stored in the set and any type \p Q that you can use
253 in \p erase() and \p find() member functions.
257 <td> \p boost::intrusive::treap_set</td>
258 <td><tt><cds/intrusive/striped_set/boost_treap_set.h></tt></td>
260 #include <cds/intrusive/striped_set/boost_treap_set.h>
261 #include <cds/intrusive/striped_set.h>
262 typedef cds::intrusive::StripedSet<
263 boost::intrusive::treap_set<T, boost::intrusive::constant_time_size<true> >
268 Note that \p boost::intrusive::compare option using in \p boost::intrusive::treap_set
269 should support \p T type stored in the set and any type \p Q that you can use
270 in \p erase() and \p find() member functions.
275 You can use another intrusive container type as striped set's bucket.
276 Suppose, you have a container class \p MyBestContainer and you want to integrate it with \p StripedSet as bucket type.
277 There are two possibility:
278 - either your \p MyBestContainer class has native support of bucket's interface;
279 in this case, you can use default \p intrusive::striped_set::adapt metafunction;
280 - or your \p MyBestContainer class does not support bucket's interface, which means, that you should create a specialization of
281 <tt>cds::intrusive::striped_set::adapt<MyBestContainer> </tt> metafunction providing necessary interface.
283 The <tt>intrusive::striped_set::adapt< Container, OptionPack ></tt> metafunction has two template argument:
284 - \p Container is the class that should be used as the bucket, for example, <tt>boost::intrusive::list< T ></tt>.
285 - \p OptionPack is the packed options from \p %StripedSet declaration. The \p adapt metafunction can use
286 any option from \p OptionPack for its internal use. For example, a \p compare option can be passed to \p adapt
287 metafunction via \p OptionPack argument of \p %StripedSet declaration.
289 See \p intrusive::striped_set::adapt metafunction for the description of interface that the bucket container must provide
290 to be \p %StripedSet compatible.
292 template <class Container, typename... Options>
297 struct default_options {
298 typedef striped_set::striping<> mutex_policy;
299 typedef typename cds::opt::v::hash_selector< cds::opt::none >::type hash;
300 typedef cds::atomicity::item_counter item_counter;
301 typedef CDS_DEFAULT_ALLOCATOR allocator;
302 typedef cds::opt::none resizing_policy;
303 typedef cds::opt::none compare;
304 typedef cds::opt::none less;
307 typedef typename cds::opt::make_options<
308 typename cds::opt::find_type_traits< default_options, Options... >::type
313 typedef Container underlying_container_type ; ///< original intrusive container type for the bucket
314 typedef typename cds::intrusive::striped_set::adapt< underlying_container_type, Options... >::type bucket_type ; ///< container type adapted for hash set
315 typedef typename bucket_type::value_type value_type ; ///< value type stored in the set
317 typedef typename options::hash hash ; ///< Hash functor
318 typedef typename options::item_counter item_counter ; ///< Item counter
319 typedef typename cds::opt::select_default<
320 typename options::resizing_policy,
321 typename bucket_type::default_resizing_policy
322 >::type resizing_policy ; ///< Resizing policy
323 typedef typename options::allocator allocator_type ; ///< allocator type specified in options.
324 typedef typename options::mutex_policy mutex_policy ; ///< Mutex policy
326 typedef cds::details::Allocator< bucket_type, allocator_type > bucket_allocator; ///< bucket allocator type based on allocator_type
329 bucket_type * m_Buckets ; ///< Bucket table
330 size_t m_nBucketMask ; ///< Bucket table size - 1. m_nBucketMask + 1 should be power of two.
331 item_counter m_ItemCounter ; ///< Item counter
332 hash m_Hash ; ///< Hash functor
334 mutex_policy m_MutexPolicy ; ///< Mutex policy
335 resizing_policy m_ResizingPolicy; ///< Resizing policy
337 static const size_t c_nMinimalCapacity = 16 ; ///< Minimal capacity
341 typedef typename mutex_policy::scoped_cell_lock scoped_cell_lock;
342 typedef typename mutex_policy::scoped_full_lock scoped_full_lock;
343 typedef typename mutex_policy::scoped_resize_lock scoped_resize_lock;
348 static size_t calc_init_capacity( size_t nCapacity )
350 nCapacity = cds::beans::ceil2( nCapacity );
351 return nCapacity < c_nMinimalCapacity ? c_nMinimalCapacity : nCapacity;
354 void alloc_bucket_table( size_t nSize )
356 assert( cds::beans::is_power2( nSize ));
357 m_nBucketMask = nSize - 1;
358 m_Buckets = bucket_allocator().NewArray( nSize );
361 static void free_bucket_table( bucket_type * pBuckets, size_t nSize )
363 bucket_allocator().Delete( pBuckets, nSize );
366 template <typename Q>
367 size_t hashing( Q const& v ) const
372 bucket_type * bucket( size_t nHash ) const CDS_NOEXCEPT
374 return m_Buckets + (nHash & m_nBucketMask);
377 template <typename Q, typename Func>
378 bool find_( Q& val, Func f )
380 size_t nHash = hashing( val );
382 scoped_cell_lock sl( m_MutexPolicy, nHash );
383 return bucket( nHash )->find( val, f );
386 template <typename Q, typename Less, typename Func>
387 bool find_with_( Q& val, Less pred, Func f )
389 size_t nHash = hashing( val );
390 scoped_cell_lock sl( m_MutexPolicy, nHash );
391 return bucket( nHash )->find( val, pred, f );
394 void internal_resize( size_t nNewCapacity )
396 // All locks are already locked!
397 m_MutexPolicy.resize( nNewCapacity );
399 size_t nOldCapacity = bucket_count();
400 bucket_type * pOldBuckets = m_Buckets;
402 alloc_bucket_table( nNewCapacity );
404 typedef typename bucket_type::iterator bucket_iterator;
405 bucket_type * pEnd = pOldBuckets + nOldCapacity;
406 for ( bucket_type * pCur = pOldBuckets; pCur != pEnd; ++pCur ) {
407 bucket_iterator itEnd = pCur->end();
408 bucket_iterator itNext;
409 for ( bucket_iterator it = pCur->begin(); it != itEnd; it = itNext ) {
412 bucket( m_Hash( *it ) )->move_item( *pCur, it );
417 free_bucket_table( pOldBuckets, nOldCapacity );
419 m_ResizingPolicy.reset();
424 size_t nOldCapacity = bucket_count();
425 size_t volatile& refBucketMask = m_nBucketMask;
427 scoped_resize_lock al( m_MutexPolicy );
428 if ( al.success() ) {
429 if ( nOldCapacity != refBucketMask + 1 ) {
430 // someone resized already
434 internal_resize( nOldCapacity * 2 );
441 /// Default ctor. The initial capacity is 16.
443 : m_Buckets( nullptr )
444 , m_nBucketMask( c_nMinimalCapacity - 1 )
445 , m_MutexPolicy( c_nMinimalCapacity )
447 alloc_bucket_table( m_nBucketMask + 1 );
450 /// Ctor with initial capacity specified
452 size_t nCapacity ///< Initial size of bucket table and lock array. Must be power of two, the minimum is 16.
454 : m_Buckets( nullptr )
455 , m_nBucketMask( calc_init_capacity(nCapacity) - 1 )
456 , m_MutexPolicy( m_nBucketMask + 1 )
458 alloc_bucket_table( m_nBucketMask + 1 );
461 /// Ctor with resizing policy (copy semantics)
463 This constructor initializes m_ResizingPolicy member with copy of \p resizingPolicy parameter
466 size_t nCapacity ///< Initial size of bucket table and lock array. Must be power of two, the minimum is 16.
467 ,resizing_policy const& 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 );
477 /// Ctor with resizing policy (move semantics)
479 This constructor initializes m_ResizingPolicy member moving \p resizingPolicy parameter
480 Move semantics is used.
483 size_t nCapacity ///< Initial size of bucket table and lock array. Must be power of two, the minimum is 16.
484 ,resizing_policy&& resizingPolicy ///< Resizing policy
486 : m_Buckets( nullptr )
487 , m_nBucketMask( ( nCapacity ? calc_init_capacity(nCapacity) : c_nMinimalCapacity ) - 1 )
488 , m_MutexPolicy( m_nBucketMask + 1 )
489 , m_ResizingPolicy( std::forward<resizing_policy>( resizingPolicy ) )
491 alloc_bucket_table( m_nBucketMask + 1 );
494 /// Destructor destroys internal data
497 free_bucket_table( m_Buckets, m_nBucketMask + 1 );
503 The function inserts \p val in the set if it does not contain
504 an item with key equal to \p val.
506 Returns \p true if \p val is placed into the set, \p false otherwise.
508 bool insert( value_type& val )
510 return insert( val, []( value_type& ) {} );
515 The function allows to split creating of new item into two part:
516 - create item with key only
517 - insert new item into the set
518 - if inserting is success, calls \p f functor to initialize value-field of \p val.
520 The functor signature is:
522 void func( value_type& val );
524 where \p val is the item inserted.
526 template <typename Func>
527 bool insert( value_type& val, Func f )
531 size_t nHash = hashing( val );
532 bucket_type * pBucket;
534 scoped_cell_lock sl( m_MutexPolicy, nHash );
535 pBucket = bucket( nHash );
536 bOk = pBucket->insert( val, f );
537 bResize = bOk && m_ResizingPolicy( ++m_ItemCounter, *this, *pBucket );
547 The operation performs inserting or changing data with lock-free manner.
549 If the item \p val is not found in the set, then \p val is inserted
550 iff \p bAllowInsert is \p true.
551 Otherwise, the functor \p func is called with item found.
552 The functor signature is:
554 void func( bool bNew, value_type& item, value_type& val );
557 - \p bNew - \p true if the item has been inserted, \p false otherwise
558 - \p item - item of the set
559 - \p val - argument \p val passed into the \p update() function
560 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
561 refers to the same thing.
563 The functor may change non-key fields of the \p item.
565 Returns std::pair<bool, bool> where \p first is \p true if operation is successful,
566 \p second is \p true if new item has been added or \p false if the item with \p val
567 already is in the set.
569 template <typename Func>
570 std::pair<bool, bool> update( value_type& val, Func func, bool bAllowInsert = true )
572 std::pair<bool, bool> result;
574 size_t nHash = hashing( val );
575 bucket_type * pBucket;
577 scoped_cell_lock sl( m_MutexPolicy, nHash );
578 pBucket = bucket( nHash );
580 result = pBucket->update( val, func, bAllowInsert );
581 bResize = result.first && result.second && m_ResizingPolicy( ++m_ItemCounter, *this, *pBucket );
589 template <typename Func>
590 std::pair<bool, bool> ensure( value_type& val, Func func )
592 return update( val, func, true );
596 /// Unlink the item \p val from the set
598 The function searches the item \p val in the set and unlink it
599 if it is found and is equal to \p val (here, the equality means that
600 \p val belongs to the set: if \p item is an item found then
601 unlink is successful iif <tt>&val == &item</tt>)
603 The function returns \p true if success and \p false otherwise.
605 bool unlink( value_type& val )
608 size_t nHash = hashing( val );
610 scoped_cell_lock sl( m_MutexPolicy, nHash );
611 bOk = bucket( nHash )->unlink( val );
619 /// Deletes the item from the set
620 /** \anchor cds_intrusive_StripedSet_erase
621 The function searches an item with key equal to \p val in the set,
622 unlinks it from the set, and returns a pointer to unlinked item.
624 If the item with key equal to \p val is not found the function return \p nullptr.
626 Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
628 template <typename Q>
629 value_type * erase( Q const& val )
631 return erase( val, [](value_type const&) {} );
634 /// Deletes the item from the set using \p pred predicate for searching
636 The function is an analog of \ref cds_intrusive_StripedSet_erase "erase(Q const&)"
637 but \p pred is used for key comparing
638 \p Less has the interface like \p std::less.
639 \p pred must imply the same element order as the comparator used for building the set.
641 template <typename Q, typename Less>
642 value_type * erase_with( Q const& val, Less pred )
644 return erase_with( val, pred, [](value_type const&) {} );
647 /// Deletes the item from the set
648 /** \anchor cds_intrusive_StripedSet_erase_func
650 The function searches an item with key equal to \p val in the set,
651 call \p f functor with item found, unlinks it from the set, and returns a pointer to unlinked item.
653 The \p Func interface is
656 void operator()( value_type const& item );
660 If the item with key equal to \p val is not found the function return \p false.
662 Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
664 template <typename Q, typename Func>
665 value_type * erase( Q const& val, Func f )
667 size_t nHash = hashing( val );
670 scoped_cell_lock sl( m_MutexPolicy, nHash );
671 pVal = bucket( nHash )->erase( val, f );
679 /// Deletes the item from the set using \p pred predicate for searching
681 The function is an analog of \ref cds_intrusive_StripedSet_erase_func "erase(Q const&, Func)"
682 but \p pred is used for key comparing
683 \p Less has the interface like \p std::less.
684 \p pred must imply the same element order as the comparator used for building the set.
686 template <typename Q, typename Less, typename Func>
687 value_type * erase_with( Q const& val, Less pred, Func f )
689 size_t nHash = hashing( val );
692 scoped_cell_lock sl( m_MutexPolicy, nHash );
693 pVal = bucket( nHash )->erase( val, pred, f );
701 /// Find the key \p val
702 /** \anchor cds_intrusive_StripedSet_find_func
703 The function searches the item with key equal to \p val and calls the functor \p f for item found.
704 The interface of \p Func functor is:
707 void operator()( value_type& item, Q& val );
710 where \p item is the item found, \p val is the <tt>find</tt> function argument.
712 The functor may change non-key fields of \p item.
714 The \p val argument is non-const since it can be used as \p f functor destination i.e., the functor
715 may modify both arguments.
717 Note the hash functor specified for class \p Traits template parameter
718 should accept a parameter of type \p Q that can be not the same as \p value_type.
720 The function returns \p true if \p val is found, \p false otherwise.
722 template <typename Q, typename Func>
723 bool find( Q& val, Func f )
725 return find_( val, f );
728 /// Find the key \p val using \p pred predicate
730 The function is an analog of \ref cds_intrusive_StripedSet_find_func "find(Q&, Func)"
731 but \p pred is used for key comparing
732 \p Less has the interface like \p std::less.
733 \p pred must imply the same element order as the comparator used for building the set.
735 template <typename Q, typename Less, typename Func>
736 bool find_with( Q& val, Less pred, Func f )
738 return find_with_( val, pred, f );
741 /// Find the key \p val
742 /** \anchor cds_intrusive_StripedSet_find_cfunc
743 The function searches the item with key equal to \p val and calls the functor \p f for item found.
744 The interface of \p Func functor is:
747 void operator()( value_type& item, Q const& val );
750 where \p item is the item found, \p val is the <tt>find</tt> function argument.
752 The functor may change non-key fields of \p item.
754 The \p val argument is non-const since it can be used as \p f functor destination i.e., the functor
755 may modify both arguments.
757 The function returns \p true if \p val is found, \p false otherwise.
759 template <typename Q, typename Func>
760 bool find( Q const& val, Func f )
762 return find_( val, f );
765 /// Find the key \p val using \p pred predicate
767 The function is an analog of \ref cds_intrusive_StripedSet_find_cfunc "find(Q const&, Func)"
768 but \p pred is used for key comparing
769 \p Less has the interface like \p std::less.
770 \p pred must imply the same element order as the comparator used for building the set.
772 template <typename Q, typename Less, typename Func>
773 bool find_with( Q const& val, Less pred, Func f )
775 return find_with_( val, pred, f );
778 /// Checks whether the set contains \p key
780 The function searches the item with key equal to \p key
781 and returns \p true if it is found, and \p false otherwise.
783 Note the hash functor specified for class \p Traits template parameter
784 should accept a parameter of type \p Q that can be not the same as \p value_type.
785 Otherwise, you may use \p contains( Q const&, Less pred ) functions with explicit predicate for key comparing.
787 template <typename Q>
788 bool contains( Q const& key )
790 return find( key, [](value_type&, Q const& ) {} );
793 template <typename Q>
794 CDS_DEPRECATED("use contains()")
795 bool find( Q const& val )
797 return contains( val );
801 /// Checks whether the set contains \p key using \p pred predicate for searching
803 The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
804 \p Less functor has the interface like \p std::less.
805 \p Less must imply the same element order as the comparator used for building the set.
807 template <typename Q, typename Less>
808 bool contains( Q const& key, Less pred )
810 return find_with( key, pred, [](value_type& , Q const& ) {} );
813 template <typename Q, typename Less>
814 CDS_DEPRECATED("use contains()")
815 bool find_with( Q const& val, Less pred )
817 return contains( val, pred );
823 The function unlinks all items from the set.
827 // locks entire array
828 scoped_full_lock sl( m_MutexPolicy );
830 size_t nBucketCount = bucket_count();
831 bucket_type * pBucket = m_Buckets;
832 for ( size_t i = 0; i < nBucketCount; ++i, ++pBucket )
834 m_ItemCounter.reset();
837 /// Clears the set and calls \p disposer for each item
839 The function unlinks all items from the set calling \p disposer for each item.
840 \p Disposer functor interface is:
843 void operator()( value_type * p );
847 template <typename Disposer>
848 void clear_and_dispose( Disposer disposer )
850 // locks entire array
851 scoped_full_lock sl( m_MutexPolicy );
853 size_t nBucketCount = bucket_count();
854 bucket_type * pBucket = m_Buckets;
855 for ( size_t i = 0; i < nBucketCount; ++i, ++pBucket )
856 pBucket->clear( disposer );
857 m_ItemCounter.reset();
860 /// Checks if the set is empty
862 Emptiness is checked by item counting: if item count is zero then the set is empty.
869 /// Returns item count in the set
872 return m_ItemCounter;
875 /// Returns the size of hash table
877 The hash table size is non-constant and can be increased via resizing.
879 size_t bucket_count() const
881 return m_nBucketMask + 1;
884 /// Returns lock array size
885 size_t lock_count() const
887 return m_MutexPolicy.lock_count();
890 /// Returns resizing policy object
891 resizing_policy& get_resizing_policy()
893 return m_ResizingPolicy;
896 /// Returns resizing policy (const version)
897 resizing_policy const& get_resizing_policy() const
899 return m_ResizingPolicy;
902 }} // namespace cds::itrusive
904 #endif // #ifndef CDSLIB_INTRUSIVE_STRIPED_SET_H