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_CONTAINER_MICHAEL_SET_RCU_H
32 #define CDSLIB_CONTAINER_MICHAEL_SET_RCU_H
34 #include <cds/container/details/michael_set_base.h>
35 #include <cds/details/allocator.h>
37 namespace cds { namespace container {
39 /// Michael's hash set (template specialization for \ref cds_urcu_desc "RCU")
40 /** @ingroup cds_nonintrusive_set
41 \anchor cds_nonintrusive_MichaelHashSet_rcu
44 - [2002] Maged Michael "High performance dynamic lock-free hash tables and list-based sets"
46 Michael's hash table algorithm is based on lock-free ordered list and it is very simple.
47 The main structure is an array \p T of size \p M. Each element in \p T is basically a pointer
48 to a hash bucket, implemented as a singly linked list. The array of buckets cannot be dynamically expanded.
49 However, each bucket may contain unbounded number of items.
51 Template parameters are:
52 - \p RCU - one of \ref cds_urcu_gc "RCU type"
53 - \p OrderedList - ordered list implementation used as the bucket for hash set, for example,
54 \ref cds_nonintrusive_MichaelList_rcu "MichaelList".
55 The ordered list implementation specifies the type \p T stored in the hash-set,
56 the comparison functor for the type \p T and other features specific for
58 - \p Traits - set traits, default is michael_set::traits.
59 Instead of defining \p Traits struct you may use option-based syntax with michael_set::make_traits metafunction.
61 About hash functor see \ref cds_nonintrusive_MichaelHashSet_hash_functor "MichaelSet hash functor".
65 Suppose, we have the following type \p Foo that we want to store in your \p %MichaelHashSet:
68 int nKey ; // key field
69 int nVal ; // value field
73 To use \p %MichaelHashSet for \p Foo values, you should first choose suitable ordered list class
74 that will be used as a bucket for the set. We will cds::urcu::general_buffered<> RCU type and
75 MichaelList as a bucket type.
76 You should include RCU-related header file (<tt>cds/urcu/general_buffered.h</tt> in this example)
77 before including <tt>cds/container/michael_set_rcu.h</tt>.
78 Also, for ordered list we should develop a comparator for our \p Foo struct.
80 #include <cds/urcu/general_buffered.h>
81 #include <cds/container/michael_list_rcu.h>
82 #include <cds/container/michael_set_rcu.h>
84 namespace cc = cds::container;
88 int operator ()(Foo const& v1, Foo const& v2 ) const
90 if ( std::less( v1.nKey, v2.nKey ))
92 return std::less(v2.nKey, v1.nKey) ? 1 : 0;
97 typedef cc::MichaelList< cds::urcu::gc< cds::urcu::general_buffered<> >, Foo,
98 typename cc::michael_list::make_traits<
99 cc::opt::compare< Foo_cmp > // item comparator option
103 // Hash functor for Foo
105 size_t operator ()( int i ) const
107 return std::hash( i );
109 size_t operator()( Foo const& i ) const
111 return std::hash( i.nKey );
116 // Note that \p RCU template parameter of ordered list must be equal \p RCU for the set.
117 typedef cc::MichaelHashSet< cds::urcu::gc< cds::urcu::general_buffered<> >, bucket_list,
118 cc::michael_set::make_traits<
119 cc::opt::hash< foo_hash >
129 #ifdef CDS_DOXYGEN_INVOKED
130 class Traits = michael_set::traits
135 class MichaelHashSet< cds::urcu::gc< RCU >, OrderedList, Traits >
138 typedef cds::urcu::gc< RCU > gc; ///< RCU used as garbage collector
139 typedef OrderedList ordered_list; ///< type of ordered list to be used as a bucket implementation
140 typedef Traits traits; ///< Set traits
142 typedef typename ordered_list::value_type value_type; ///< type of value to be stored in the list
143 typedef typename ordered_list::key_comparator key_comparator; ///< key comparing functor
144 typedef typename ordered_list::stat stat; ///< Internal statistics
146 /// Hash functor for \ref value_type and all its derivatives that you use
147 typedef typename cds::opt::v::hash_selector< typename traits::hash >::type hash;
148 typedef typename traits::item_counter item_counter; ///< Item counter type
149 typedef typename traits::allocator allocator; ///< Bucket table allocator
151 typedef typename ordered_list::rcu_lock rcu_lock; ///< RCU scoped lock
152 /// Group of \p extract_xxx functions require external locking if underlying ordered list requires that
153 static CDS_CONSTEXPR const bool c_bExtractLockExternal = ordered_list::c_bExtractLockExternal;
155 // GC and OrderedList::gc must be the same
156 static_assert(std::is_same<gc, typename ordered_list::gc>::value, "GC and OrderedList::gc must be the same");
158 static_assert(!std::is_same<item_counter, atomicity::empty_item_counter>::value,
159 "atomicity::empty_item_counter is not allowed as a item counter");
161 #ifdef CDS_DOXYGEN_INVOKED
162 /// Wrapped internal statistics for \p ordered_list
163 typedef implementatin_specific bucket_stat;
165 /// Internal bucket type - rebind \p ordered_list with empty item counter and wrapped internal statistics
166 typedef modified_ordered_list internal_bucket_type;
168 typedef typename ordered_list::template select_stat_wrapper< typename ordered_list::stat > bucket_stat;
170 typedef typename ordered_list::template rebind_traits<
171 cds::opt::item_counter< cds::atomicity::empty_item_counter >
172 , cds::opt::stat< typename bucket_stat::wrapped_stat >
173 >::type internal_bucket_type_;
175 class internal_bucket_type: public internal_bucket_type_
177 typedef internal_bucket_type_ base_class;
179 using base_class::base_class;
180 using base_class::node_type;
181 using base_class::alloc_node;
182 using base_class::insert_node;
183 using base_class::node_to_value;
187 typedef typename internal_bucket_type::exempt_ptr exempt_ptr; ///< pointer to extracted node
188 typedef typename internal_bucket_type::raw_ptr raw_ptr; ///< Return type of \p get() member function and its derivatives
192 /// Bucket table allocator
193 typedef typename allocator::template rebind< internal_bucket_type >::other bucket_table_allocator;
195 const size_t m_nHashBitmask;
196 item_counter m_ItemCounter; ///< Item counter
197 hash m_HashFunctor; ///< Hash functor
198 internal_bucket_type* m_Buckets; ///< bucket table
199 typename bucket_stat::stat m_Stat; ///< Internal statistics
203 ///@name Forward iterators (thread-safe under RCU lock)
207 The forward iterator for Michael's set is based on \p OrderedList forward iterator and has some features:
208 - it has no post-increment operator
209 - it iterates items in unordered fashion
211 You may safely use iterators in multi-threaded environment only under RCU lock.
212 Otherwise, a crash is possible if another thread deletes the element the iterator points to.
214 The iterator interface:
218 // Default constructor
222 iterator( iterator const& src );
224 // Dereference operator
225 value_type * operator ->() const;
227 // Dereference operator
228 value_type& operator *() const;
230 // Preincrement operator
231 iterator& operator ++();
233 // Assignment operator
234 iterator& operator = (iterator const& src);
236 // Equality operators
237 bool operator ==(iterator const& i ) const;
238 bool operator !=(iterator const& i ) const;
242 typedef michael_set::details::iterator< internal_bucket_type, false > iterator;
244 /// Const forward iterator
245 typedef michael_set::details::iterator< internal_bucket_type, true > const_iterator;
247 /// Returns a forward iterator addressing the first element in a set
249 For empty set \code begin() == end() \endcode
253 return iterator( m_Buckets[0].begin(), m_Buckets, m_Buckets + bucket_count() );
256 /// Returns an iterator that addresses the location succeeding the last element in a set
258 Do not use the value returned by <tt>end</tt> function to access any item.
259 The returned value can be used only to control reaching the end of the set.
260 For empty set \code begin() == end() \endcode
264 return iterator( m_Buckets[bucket_count() - 1].end(), m_Buckets + bucket_count() - 1, m_Buckets + bucket_count() );
267 /// Returns a forward const iterator addressing the first element in a set
268 const_iterator begin() const
270 return get_const_begin();
273 /// Returns a forward const iterator addressing the first element in a set
274 const_iterator cbegin() const
276 return get_const_begin();
279 /// Returns an const iterator that addresses the location succeeding the last element in a set
280 const_iterator end() const
282 return get_const_end();
285 /// Returns an const iterator that addresses the location succeeding the last element in a set
286 const_iterator cend() const
288 return get_const_end();
293 /// Initialize hash set
295 The Michael's hash set is non-expandable container. You should point the average count of items \p nMaxItemCount
296 when you create an object.
297 \p nLoadFactor parameter defines average count of items per bucket and it should be small number between 1 and 10.
298 Remember, since the bucket implementation is an ordered list, searching in the bucket is linear [<tt>O(nLoadFactor)</tt>].
300 The ctor defines hash table size as rounding <tt>nMaxItemCount / nLoadFactor</tt> up to nearest power of two.
303 size_t nMaxItemCount, ///< estimation of max item count in the hash set
304 size_t nLoadFactor ///< load factor: estimation of max number of items in the bucket
305 ) : m_nHashBitmask( michael_set::details::init_hash_bitmask( nMaxItemCount, nLoadFactor ))
306 , m_Buckets( bucket_table_allocator().allocate( bucket_count() ) )
308 for ( auto it = m_Buckets, itEnd = m_Buckets + bucket_count(); it != itEnd; ++it )
309 construct_bucket<bucket_stat>( it );
312 /// Clears hash set and destroys it
317 for ( auto it = m_Buckets, itEnd = m_Buckets + bucket_count(); it != itEnd; ++it )
318 it->~internal_bucket_type();
319 bucket_table_allocator().deallocate( m_Buckets, bucket_count() );
325 The function creates a node with copy of \p val value
326 and then inserts the node created into the set.
328 The type \p Q should contain as minimum the complete key for the node.
329 The object of \ref value_type should be constructible from a value of type \p Q.
330 In trivial case, \p Q is equal to \ref value_type.
332 The function applies RCU lock internally.
334 Returns \p true if \p val is inserted into the set, \p false otherwise.
336 template <typename Q>
337 bool insert( Q&& val )
339 const bool bRet = bucket( val ).insert( std::forward<Q>( val ));
347 The function allows to split creating of new item into two part:
348 - create item with key only
349 - insert new item into the set
350 - if inserting is success, calls \p f functor to initialize value-fields of \p val.
352 The functor signature is:
354 void func( value_type& val );
356 where \p val is the item inserted.
357 The user-defined functor is called only if the inserting is success.
359 The function applies RCU lock internally.
361 @warning For \ref cds_nonintrusive_MichaelList_rcu "MichaelList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
362 \ref cds_nonintrusive_LazyList_rcu "LazyList" provides exclusive access to inserted item and does not require any node-level
365 template <typename Q, typename Func>
366 bool insert( Q&& val, Func f )
368 const bool bRet = bucket( val ).insert( std::forward<Q>( val ), f );
374 /// Updates the element
376 The operation performs inserting or changing data with lock-free manner.
378 If the item \p val not found in the set, then \p val is inserted iff \p bAllowInsert is \p true.
379 Otherwise, the functor \p func is called with item found.
380 The functor signature is:
383 void operator()( bool bNew, value_type& item, Q const& val );
387 - \p bNew - \p true if the item has been inserted, \p false otherwise
388 - \p item - item of the set
389 - \p val - argument \p val passed into the \p %update() function
391 The functor may change non-key fields of the \p item.
393 The function applies RCU lock internally.
395 Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successful,
396 \p second is \p true if new item has been added or \p false if the item with \p key
397 already is in the set.
399 @warning For \ref cds_intrusive_MichaelList_hp "MichaelList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
400 \ref cds_intrusive_LazyList_hp "LazyList" provides exclusive access to inserted item and does not require any node-level
403 template <typename Q, typename Func>
404 std::pair<bool, bool> update( Q const& val, Func func, bool bAllowInsert = true )
406 std::pair<bool, bool> bRet = bucket( val ).update( val, func, bAllowInsert );
411 template <typename Q, typename Func>
412 CDS_DEPRECATED("ensure() is deprecated, use update()")
413 std::pair<bool, bool> ensure( const Q& val, Func func )
415 return update( val, func, true );
419 /// Inserts data of type \p value_type created from \p args
421 Returns \p true if inserting successful, \p false otherwise.
423 The function applies RCU lock internally.
425 template <typename... Args>
426 bool emplace( Args&&... args )
428 typename internal_bucket_type::node_type * pNode = internal_bucket_type::alloc_node( std::forward<Args>( args )... );
429 bool bRet = bucket( internal_bucket_type::node_to_value( *pNode ) ).insert_node( pNode );
435 /// Deletes \p key from the set
436 /** \anchor cds_nonintrusive_MichealSet_rcu_erase_val
438 Since the key of MichaelHashSet's item type \p value_type is not explicitly specified,
439 template parameter \p Q defines the key type searching in the list.
440 The set item comparator should be able to compare the type \p value_type
443 RCU \p synchronize method can be called. RCU should not be locked.
445 Return \p true if key is found and deleted, \p false otherwise
447 template <typename Q>
448 bool erase( Q const& key )
450 const bool bRet = bucket( key ).erase( key );
456 /// Deletes the item from the set using \p pred predicate for searching
458 The function is an analog of \ref cds_nonintrusive_MichealSet_rcu_erase_val "erase(Q const&)"
459 but \p pred is used for key comparing.
460 \p Less functor has the interface like \p std::less.
461 \p Less must imply the same element order as the comparator used for building the set.
463 template <typename Q, typename Less>
464 bool erase_with( Q const& key, Less pred )
466 const bool bRet = bucket( key ).erase_with( key, pred );
472 /// Deletes \p key from the set
473 /** \anchor cds_nonintrusive_MichealSet_rcu_erase_func
475 The function searches an item with key \p key, calls \p f functor
476 and deletes the item. If \p key is not found, the functor is not called.
478 The functor \p Func interface:
481 void operator()(value_type const& val);
485 Since the key of %MichaelHashSet's \p value_type is not explicitly specified,
486 template parameter \p Q defines the key type searching in the list.
487 The list item comparator should be able to compare the type \p T of list item
490 RCU \p synchronize method can be called. RCU should not be locked.
492 Return \p true if key is found and deleted, \p false otherwise
494 template <typename Q, typename Func>
495 bool erase( Q const& key, Func f )
497 const bool bRet = bucket( key ).erase( key, f );
503 /// Deletes the item from the set using \p pred predicate for searching
505 The function is an analog of \ref cds_nonintrusive_MichealSet_rcu_erase_func "erase(Q const&, Func)"
506 but \p pred is used for key comparing.
507 \p Less functor has the interface like \p std::less.
508 \p Less must imply the same element order as the comparator used for building the set.
510 template <typename Q, typename Less, typename Func>
511 bool erase_with( Q const& key, Less pred, Func f )
513 const bool bRet = bucket( key ).erase_with( key, pred, f );
519 /// Extracts an item from the set
520 /** \anchor cds_nonintrusive_MichaelHashSet_rcu_extract
521 The function searches an item with key equal to \p key in the set,
522 unlinks it from the set, and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the item found.
523 If the item with the key equal to \p key is not found the function return an empty \p exempt_ptr.
525 The function just excludes the item from the set and returns a pointer to item found.
526 Depends on \p ordered_list you should or should not lock RCU before calling of this function:
527 - for the set based on \ref cds_nonintrusive_MichaelList_rcu "MichaelList" RCU should not be locked
528 - for the set based on \ref cds_nonintrusive_LazyList_rcu "LazyList" RCU should be locked
529 See ordered list implementation for details.
532 #include <cds/urcu/general_buffered.h>
533 #include <cds/container/michael_list_rcu.h>
534 #include <cds/container/michael_set_rcu.h>
536 typedef cds::urcu::gc< general_buffered<> > rcu;
537 typedef cds::container::MichaelList< rcu, Foo > rcu_michael_list;
538 typedef cds::container::MichaelHashSet< rcu, rcu_michael_list, foo_traits > rcu_michael_set;
540 rcu_michael_set theSet;
543 typename rcu_michael_set::exempt_ptr p;
545 // For MichaelList we should not lock RCU
547 // Note that you must not delete the item found inside the RCU lock
548 p = theSet.extract( 10 );
550 // do something with p
554 // We may safely release p here
555 // release() passes the pointer to RCU reclamation cycle
559 template <typename Q>
560 exempt_ptr extract( Q const& key )
562 exempt_ptr p = bucket( key ).extract( key );
568 /// Extracts an item from the set using \p pred predicate for searching
570 The function is an analog of \p extract(Q const&) but \p pred is used for key comparing.
571 \p Less functor has the interface like \p std::less.
572 \p pred must imply the same element order as the comparator used for building the set.
574 template <typename Q, typename Less>
575 exempt_ptr extract_with( Q const& key, Less pred )
577 exempt_ptr p = bucket( key ).extract_with( key, pred );
583 /// Finds the key \p key
584 /** \anchor cds_nonintrusive_MichealSet_rcu_find_func
586 The function searches the item with key equal to \p key and calls the functor \p f for item found.
587 The interface of \p Func functor is:
590 void operator()( value_type& item, Q& key );
593 where \p item is the item found, \p key is the <tt>find</tt> function argument.
595 The functor may change non-key fields of \p item. Note that the functor is only guarantee
596 that \p item cannot be disposed during functor is executing.
597 The functor does not serialize simultaneous access to the set's \p item. If such access is
598 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
600 The \p key argument is non-const since it can be used as \p f functor destination i.e., the functor
601 can modify both arguments.
603 Note the hash functor specified for class \p Traits template parameter
604 should accept a parameter of type \p Q that may be not the same as \p value_type.
606 The function applies RCU lock internally.
608 The function returns \p true if \p key is found, \p false otherwise.
610 template <typename Q, typename Func>
611 bool find( Q& key, Func f )
613 return bucket( key ).find( key, f );
616 template <typename Q, typename Func>
617 bool find( Q const& key, Func f )
619 return bucket( key ).find( key, f );
623 /// Finds the key \p key using \p pred predicate for searching
625 The function is an analog of \ref cds_nonintrusive_MichealSet_rcu_find_func "find(Q&, Func)"
626 but \p pred is used for key comparing.
627 \p Less functor has the interface like \p std::less.
628 \p Less must imply the same element order as the comparator used for building the set.
630 template <typename Q, typename Less, typename Func>
631 bool find_with( Q& key, Less pred, Func f )
633 return bucket( key ).find_with( key, pred, f );
636 template <typename Q, typename Less, typename Func>
637 bool find_with( Q const& key, Less pred, Func f )
639 return bucket( key ).find_with( key, pred, f );
643 /// Checks whether the set contains \p key
646 The function searches the item with key equal to \p key
647 and returns \p true if the key is found, and \p false otherwise.
649 Note the hash functor specified for class \p Traits template parameter
650 should accept a parameter of type \p Q that can be not the same as \p value_type.
652 template <typename Q>
653 bool contains( Q const& key )
655 return bucket( key ).contains( key );
658 template <typename Q>
659 CDS_DEPRECATED("use contains()")
660 bool find( Q const& key )
662 return contains( key );
666 /// Checks whether the set contains \p key using \p pred predicate for searching
668 The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
669 \p Less functor has the interface like \p std::less.
670 \p Less must imply the same element order as the comparator used for building the set.
672 template <typename Q, typename Less>
673 bool contains( Q const& key, Less pred )
675 return bucket( key ).contains( key, pred );
678 template <typename Q, typename Less>
679 CDS_DEPRECATED("use contains()")
680 bool find_with( Q const& key, Less pred )
682 return contains( key, pred );
686 /// Finds the key \p key and return the item found
687 /** \anchor cds_nonintrusive_MichaelHashSet_rcu_get
688 The function searches the item with key equal to \p key and returns the pointer to item found.
689 If \p key is not found it returns \p nullptr.
690 Note the type of returned value depends on underlying \p ordered_list.
691 For details, see documentation of ordered list you use.
693 Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
695 RCU should be locked before call of this function.
696 Returned item is valid only while RCU is locked:
698 typedef cds::container::MichaelHashSet< your_template_parameters > hash_set;
700 typename hash_set::raw_ptr gp;
704 hash_set::rcu_lock lock;
706 gp = theSet.get( 5 );
711 // Unlock RCU by rcu_lock destructor
712 // gp can be reclaimed at any time after RCU has been unlocked
716 template <typename Q>
717 raw_ptr get( Q const& key )
719 return bucket( key ).get( key );
722 /// Finds the key \p key and return the item found
724 The function is an analog of \ref cds_nonintrusive_MichaelHashSet_rcu_get "get(Q const&)"
725 but \p pred is used for comparing the keys.
727 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
729 \p pred must imply the same element order as the comparator used for building the set.
731 template <typename Q, typename Less>
732 raw_ptr get_with( Q const& key, Less pred )
734 return bucket( key ).get_with( key, pred );
737 /// Clears the set (not atomic)
740 for ( size_t i = 0; i < bucket_count(); ++i )
741 m_Buckets[i].clear();
742 m_ItemCounter.reset();
745 /// Checks if the set is empty
747 Emptiness is checked by item counting: if item count is zero then the set is empty.
748 Thus, the correct item counting feature is an important part of Michael's set implementation.
755 /// Returns item count in the set
758 return m_ItemCounter;
761 /// Returns const reference to internal statistics
762 stat const& statistics() const
767 /// Returns the size of hash table
769 Since \p %MichaelHashSet cannot dynamically extend the hash table size,
770 the value returned is an constant depending on object initialization parameters;
771 see MichaelHashSet::MichaelHashSet for explanation.
773 size_t bucket_count() const
775 return m_nHashBitmask + 1;
780 /// Calculates hash value of \p key
781 template <typename Q>
782 size_t hash_value( Q const& key ) const
784 return m_HashFunctor( key ) & m_nHashBitmask;
787 /// Returns the bucket (ordered list) for \p key
788 template <typename Q>
789 internal_bucket_type& bucket( Q const& key )
791 return m_Buckets[hash_value( key )];
793 template <typename Q>
794 internal_bucket_type const& bucket( Q const& key ) const
796 return m_Buckets[hash_value( key )];
799 template <typename Stat>
800 typename std::enable_if< Stat::empty >::type construct_bucket( internal_bucket_type* bucket )
802 new (bucket) internal_bucket_type;
805 template <typename Stat>
806 typename std::enable_if< !Stat::empty >::type construct_bucket( internal_bucket_type* bucket )
808 new (bucket) internal_bucket_type( m_Stat );
811 const_iterator get_const_begin() const
813 return const_iterator( const_cast<internal_bucket_type const&>(m_Buckets[0]).begin(), m_Buckets, m_Buckets + bucket_count() );
815 const_iterator get_const_end() const
817 return const_iterator( const_cast<internal_bucket_type const&>(m_Buckets[bucket_count() - 1]).end(), m_Buckets + bucket_count() - 1, m_Buckets + bucket_count() );
822 }} // namespace cds::container
824 #endif // ifndef CDSLIB_CONTAINER_MICHAEL_SET_RCU_H