2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017
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_SPLIT_LIST_NOGC_H
32 #define CDSLIB_INTRUSIVE_SPLIT_LIST_NOGC_H
36 #include <cds/intrusive/details/split_list_base.h>
37 #include <cds/gc/nogc.h>
38 #include <cds/details/type_padding.h>
40 namespace cds { namespace intrusive {
42 /// Split-ordered list (template specialization for gc::nogc)
43 /** @ingroup cds_intrusive_map
44 \anchor cds_intrusive_SplitListSet_nogc
46 This specialization is intended for so-called persistent usage when no item
47 reclamation may be performed. The class does not support deleting of list item.
49 See \ref cds_intrusive_SplitListSet_hp "SplitListSet" for description of template parameters.
50 The template parameter \p OrderedList should be any gc::nogc-derived ordered list, for example,
51 \ref cds_intrusive_MichaelList_nogc "persistent MichaelList",
52 \ref cds_intrusive_LazyList_nogc "persistent LazyList"
56 #ifdef CDS_DOXYGEN_INVOKED
57 class Traits = split_list::traits
62 class SplitListSet< cds::gc::nogc, OrderedList, Traits >
65 typedef cds::gc::nogc gc; ///< Garbage collector
66 typedef Traits traits; ///< Traits template parameters
68 /// Hash functor for \p value_type and all its derivatives that you use
69 typedef typename cds::opt::v::hash_selector< typename traits::hash >::type hash;
73 typedef split_list::details::rebind_list_traits<OrderedList, traits> ordered_list_adapter;
77 # ifdef CDS_DOXYGEN_INVOKED
78 typedef OrderedList ordered_list; ///< type of ordered list used as base for split-list
80 typedef typename ordered_list_adapter::result ordered_list;
82 typedef typename ordered_list::value_type value_type; ///< type of value stored in the split-list
83 typedef typename ordered_list::key_comparator key_comparator; ///< key comparison functor
84 typedef typename ordered_list::disposer disposer; ///< Node disposer functor
86 typedef typename traits::item_counter item_counter; ///< Item counter type
87 typedef typename traits::back_off back_off; ///< back-off strategy
88 typedef typename traits::memory_model memory_model; ///< Memory ordering. See cds::opt::memory_model option
89 typedef typename traits::stat stat; ///< Internal statistics, see \p spit_list::stat
91 // GC and OrderedList::gc must be the same
92 static_assert(std::is_same<gc, typename ordered_list::gc>::value, "GC and OrderedList::gc must be the same");
94 // atomicity::empty_item_counter is not allowed as a item counter
95 static_assert(!std::is_same<item_counter, cds::atomicity::empty_item_counter>::value,
96 "cds::atomicity::empty_item_counter is not allowed as a item counter");
100 typedef typename ordered_list::node_type list_node_type; ///< Node type as declared in ordered list
101 typedef split_list::node<list_node_type> node_type; ///< split-list node type
103 /// Split-list node traits
105 This traits is intended for converting between underlying ordered list node type \ref list_node_type
106 and split-list node type \ref node_type
108 typedef typename ordered_list_adapter::node_traits node_traits;
110 /// Bucket table implementation
111 typedef typename split_list::details::bucket_table_selector<
112 traits::dynamic_bucket_table
114 , typename ordered_list_adapter::aux_node
115 , opt::allocator< typename traits::allocator >
116 , opt::memory_model< memory_model >
117 , opt::free_list< typename traits::free_list >
118 >::type bucket_table;
120 typedef typename bucket_table::aux_node_type aux_node_type; ///< dummy node type
122 typedef typename ordered_list::iterator list_iterator;
123 typedef typename ordered_list::const_iterator list_const_iterator;
128 /// Ordered list wrapper to access protected members
129 class ordered_list_wrapper: public ordered_list
131 typedef ordered_list base_class;
132 typedef typename base_class::auxiliary_head bucket_head_type;
135 list_iterator insert_at_( aux_node_type * pHead, value_type& val )
137 assert( pHead != nullptr );
138 bucket_head_type h(static_cast<list_node_type *>(pHead));
139 return base_class::insert_at_( h, val );
142 template <typename Func>
143 std::pair<list_iterator, bool> update_at_( aux_node_type * pHead, value_type& val, Func func, bool bAllowInsert )
145 assert( pHead != nullptr );
146 bucket_head_type h(static_cast<list_node_type *>(pHead));
147 return base_class::update_at_( h, val, func, bAllowInsert );
150 template <typename Q, typename Compare, typename Func>
151 bool find_at( aux_node_type * pHead, split_list::details::search_value_type<Q>& val, Compare cmp, Func f )
153 assert( pHead != nullptr );
154 bucket_head_type h(static_cast<list_node_type *>(pHead));
155 return base_class::find_at( h, val, cmp, f );
158 template <typename Q, typename Compare>
159 list_iterator find_at_( aux_node_type * pHead, split_list::details::search_value_type<Q> const & val, Compare cmp )
161 assert( pHead != nullptr );
162 bucket_head_type h(static_cast<list_node_type *>(pHead));
163 return base_class::find_at_( h, val, cmp );
166 bool insert_aux_node( aux_node_type * pNode )
168 return base_class::insert_aux_node( pNode );
170 bool insert_aux_node( aux_node_type * pHead, aux_node_type * pNode )
172 bucket_head_type h(static_cast<list_node_type *>(pHead));
173 return base_class::insert_aux_node( h, pNode );
176 template <typename Predicate>
177 void erase_for( Predicate pred )
179 return base_class::erase_for( pred );
185 /// Initialize split-ordered list of default capacity
187 The default capacity is defined in bucket table constructor.
188 See split_list::expandable_bucket_table, split_list::static_ducket_table
189 which selects by split_list::dynamic_bucket_table option.
192 : m_nBucketCountLog2(1)
193 , m_nMaxItemCount( max_item_count(2, m_Buckets.load_factor()))
198 /// Initialize split-ordered list
200 size_t nItemCount ///< estimate average of item count
201 , size_t nLoadFactor = 1 ///< load factor - average item count per bucket. Small integer up to 10, default is 1.
203 : m_Buckets( nItemCount, nLoadFactor )
204 , m_nBucketCountLog2(1)
205 , m_nMaxItemCount( max_item_count(2, m_Buckets.load_factor()))
210 /// Destroys split-list
218 The function inserts \p val in the set if it does not contain
219 an item with key equal to \p val.
221 Returns \p true if \p val is placed into the set, \p false otherwise.
223 bool insert( value_type& val )
225 return insert_( val ) != end();
230 The operation performs inserting or changing data with lock-free manner.
232 If the item \p val is not found in the set, then \p val is inserted
233 iff \p bAllowInsert is \p true.
234 Otherwise, the functor \p func is called with item found.
235 The functor signature is:
237 void func( bool bNew, value_type& item, value_type& val );
240 - \p bNew - \p true if the item has been inserted, \p false otherwise
241 - \p item - item of the set
242 - \p val - argument \p val passed into the \p update() function
243 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
244 refers to the same thing.
246 The functor may change non-key fields of the \p item.
248 Returns std::pair<bool, bool> where \p first is \p true if operation is successful,
249 \p second is \p true if new item has been added or \p false if the item with \p key
250 already is in the list.
252 @warning For \ref cds_intrusive_MichaelList_hp "MichaelList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
253 \ref cds_intrusive_LazyList_hp "LazyList" provides exclusive access to inserted item and does not require any node-level
256 template <typename Func>
257 std::pair<bool, bool> update( value_type& val, Func func, bool bAllowInsert = true )
259 std::pair<iterator, bool> ret = update_( val, func, bAllowInsert );
260 return std::make_pair( ret.first != end(), ret.second );
263 template <typename Func>
264 CDS_DEPRECATED("ensure() is deprecated, use update()")
265 std::pair<bool, bool> ensure( value_type& val, Func func )
267 return update( val, func, true );
271 /// Checks whether the set contains \p key
273 The function searches the item with key equal to \p key
274 and returns \p true if it is found, and \p false otherwise.
276 Note the hash functor specified for class \p Traits template parameter
277 should accept a parameter of type \p Q that can be not the same as \p value_type.
278 Otherwise, you may use \p contains( Q const&, Less pred ) functions with explicit predicate for key comparing.
280 template <typename Q>
281 value_type * contains( Q const& key )
283 iterator it = find_( key );
289 template <typename Q>
290 CDS_DEPRECATED("deprecated, use contains()")
291 value_type * find( Q const& key )
293 return contains( key );
297 /// Checks whether the set contains \p key using \p pred predicate for searching
299 The function is similar to <tt>contains( key )</tt> but \p pred is used for key comparing.
300 \p Less functor has the interface like \p std::less.
301 \p Less must imply the same element order as the comparator used for building the list.
303 template <typename Q, typename Less>
304 value_type * contains( Q const& key, Less pred )
306 iterator it = find_with_( key, pred );
312 template <typename Q, typename Less>
313 CDS_DEPRECATED("deprecated, use contains()")
314 value_type * find_with( Q const& key, Less pred )
316 return contains( key, pred );
320 /// Finds the key \p key
321 /** \anchor cds_intrusive_SplitListSet_nogc_find_func
322 The function searches the item with key equal to \p key and calls the functor \p f for item found.
323 The interface of \p Func functor is:
326 void operator()( value_type& item, Q& key );
329 where \p item is the item found, \p key is the <tt>find</tt> function argument.
331 The functor can change non-key fields of \p item.
332 The functor does not serialize simultaneous access to the set \p item. If such access is
333 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
335 Note the hash functor specified for class \p Traits template parameter
336 should accept a parameter of type \p Q that can be not the same as \p value_type.
338 The function returns \p true if \p key is found, \p false otherwise.
340 template <typename Q, typename Func>
341 bool find( Q& key, Func f )
343 return find_( key, key_comparator(), f );
346 template <typename Q, typename Func>
347 bool find( Q const& key, Func f )
349 return find_( key, key_comparator(), f );
353 /// Finds the key \p key with \p pred predicate for comparing
355 The function is an analog of \ref cds_intrusive_SplitListSet_nogc_find_func "find(Q&, Func)"
356 but \p cmp is used for key compare.
357 \p Less has the interface like \p std::less.
358 \p cmp must imply the same element order as the comparator used for building the set.
360 template <typename Q, typename Less, typename Func>
361 bool find_with( Q& key, Less pred, Func f )
364 return find_( key, typename ordered_list_adapter::template make_compare_from_less<Less>(), f );
367 template <typename Q, typename Less, typename Func>
368 bool find_with( Q const& key, Less pred, Func f )
371 return find_( key, typename ordered_list_adapter::template make_compare_from_less<Less>(), f );
376 /// Clears the set (non-atomic, not thread-safe)
378 The function unlink all items from the set.
379 The function is not atomic. It cleans up each bucket and then resets the item counter to zero.
380 If there are a thread that performs insertion while \p %clear() is working the result is undefined in general case:
381 <tt> empty() </tt> may return \p true but the set may contain item(s).
382 Therefore, \p %clear() may be used only for debugging purposes.
384 For each item the \p disposer is called after unlinking.
388 m_List.erase_for( []( value_type const& val ) -> bool { return !node_traits::to_node_ptr( val )->is_dummy(); } );
389 m_ItemCounter.reset();
392 /// Checks if the set is empty
394 Emptiness is checked by item counting: if item count is zero then the set is empty.
395 Thus, the correct item counting feature is an important part of split-list implementation.
402 /// Returns item count in the set
405 return m_ItemCounter;
408 /// Returns internal statistics
409 stat const& statistics() const
414 /// Returns internal statistics for \p OrderedList
415 typename OrderedList::stat const& list_statistics() const
417 return m_List.statistics();
422 template <bool IsConst>
424 : public split_list::details::iterator_type<node_traits, ordered_list, IsConst>
426 typedef split_list::details::iterator_type<node_traits, ordered_list, IsConst> iterator_base_class;
427 typedef typename iterator_base_class::list_iterator list_iterator;
430 : iterator_base_class()
433 iterator_type( iterator_type const& src )
434 : iterator_base_class( src )
437 // This ctor should be protected...
438 iterator_type( list_iterator itCur, list_iterator itEnd )
439 : iterator_base_class( itCur, itEnd )
445 ///@name Forward iterators
449 The forward iterator for a split-list has some features:
450 - it has no post-increment operator
451 - it depends on iterator of underlying \p OrderedList
453 typedef iterator_type<false> iterator;
455 /// Const forward iterator
457 For iterator's features and requirements see \ref iterator
459 typedef iterator_type<true> const_iterator;
461 /// Returns a forward iterator addressing the first element in a split-list
463 For empty list \code begin() == end() \endcode
467 return iterator( m_List.begin(), m_List.end());
470 /// Returns an iterator that addresses the location succeeding the last element in a split-list
472 Do not use the value returned by <tt>end</tt> function to access any item.
474 The returned value can be used only to control reaching the end of the split-list.
475 For empty list \code begin() == end() \endcode
479 return iterator( m_List.end(), m_List.end());
482 /// Returns a forward const iterator addressing the first element in a split-list
483 const_iterator begin() const
485 return const_iterator( m_List.begin(), m_List.end());
488 /// Returns a forward const iterator addressing the first element in a split-list
489 const_iterator cbegin() const
491 return const_iterator( m_List.cbegin(), m_List.cend());
494 /// Returns an const iterator that addresses the location succeeding the last element in a split-list
495 const_iterator end() const
497 return const_iterator( m_List.end(), m_List.end());
500 /// Returns an const iterator that addresses the location succeeding the last element in a split-list
501 const_iterator cend() const
503 return const_iterator( m_List.cend(), m_List.cend());
509 iterator insert_( value_type& val )
511 size_t nHash = hash_value( val );
512 aux_node_type * pHead = get_bucket( nHash );
513 assert( pHead != nullptr );
515 node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
517 list_iterator it = m_List.insert_at_( pHead, val );
518 if ( it != m_List.end()) {
520 m_Stat.onInsertSuccess();
521 return iterator( it, m_List.end());
523 m_Stat.onInsertFailed();
527 template <typename Func>
528 std::pair<iterator, bool> update_( value_type& val, Func func, bool bAllowInsert )
530 size_t nHash = hash_value( val );
531 aux_node_type * pHead = get_bucket( nHash );
532 assert( pHead != nullptr );
534 node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
536 std::pair<list_iterator, bool> ret = m_List.update_at_( pHead, val, func, bAllowInsert );
537 if ( ret.first != m_List.end()) {
540 m_Stat.onUpdateNew();
543 m_Stat.onUpdateExist();
544 return std::make_pair( iterator(ret.first, m_List.end()), ret.second );
546 return std::make_pair( end(), ret.second );
549 template <typename Q, typename Less >
550 iterator find_with_( Q& val, Less pred )
553 size_t nHash = hash_value( val );
554 split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash( nHash ));
555 aux_node_type * pHead = get_bucket( nHash );
556 assert( pHead != nullptr );
558 auto it = m_List.find_at_( pHead, sv, typename ordered_list_adapter::template make_compare_from_less<Less>());
559 m_Stat.onFind( it != m_List.end());
560 return iterator( it, m_List.end());
563 template <typename Q>
564 iterator find_( Q const& val )
566 size_t nHash = hash_value( val );
567 split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash( nHash ));
568 aux_node_type * pHead = get_bucket( nHash );
569 assert( pHead != nullptr );
571 auto it = m_List.find_at_( pHead, sv, key_comparator());
572 m_Stat.onFind( it != m_List.end());
573 return iterator( it, m_List.end());
576 template <typename Q, typename Compare, typename Func>
577 bool find_( Q& val, Compare cmp, Func f )
579 size_t nHash = hash_value( val );
580 split_list::details::search_value_type<Q> sv( val, split_list::regular_hash( nHash ));
581 aux_node_type * pHead = get_bucket( nHash );
582 assert( pHead != nullptr );
583 return m_Stat.onFind( m_List.find_at( pHead, sv, cmp,
584 [&f](value_type& item, split_list::details::search_value_type<Q>& val){ f(item, val.val ); }));
587 aux_node_type * alloc_aux_node( size_t nHash )
589 m_Stat.onHeadNodeAllocated();
590 aux_node_type* p = m_Buckets.alloc_aux_node();
596 void free_aux_node( aux_node_type * p )
598 m_Buckets.free_aux_node( p );
599 m_Stat.onHeadNodeFreed();
602 /// Calculates hash value of \p key
603 template <typename Q>
604 size_t hash_value( Q const& key ) const
606 return m_HashFunctor( key );
609 size_t bucket_no( size_t nHash ) const
611 return nHash & ((1 << m_nBucketCountLog2.load( memory_model::memory_order_relaxed )) - 1);
614 static size_t parent_bucket( size_t nBucket )
616 assert( nBucket > 0 );
617 return nBucket & ~(1 << bitop::MSBnz( nBucket ));
620 aux_node_type * init_bucket( size_t const nBucket )
622 assert( nBucket > 0 );
623 size_t nParent = parent_bucket( nBucket );
625 aux_node_type * pParentBucket = m_Buckets.bucket( nParent );
626 if ( pParentBucket == nullptr ) {
627 pParentBucket = init_bucket( nParent );
628 m_Stat.onRecursiveInitBucket();
631 assert( pParentBucket != nullptr );
633 // Allocate an aux node for new bucket
634 aux_node_type * pBucket = m_Buckets.bucket( nBucket );
637 for ( ;; pBucket = m_Buckets.bucket( nBucket )) {
641 pBucket = alloc_aux_node( split_list::dummy_hash( nBucket ));
643 if ( m_List.insert_aux_node( pParentBucket, pBucket )) {
644 m_Buckets.bucket( nBucket, pBucket );
645 m_Stat.onNewBucket();
649 // Another thread set the bucket. Wait while it done
650 free_aux_node( pBucket );
651 m_Stat.onBucketInitContenton();
655 // There are no free buckets. It means that the bucket table is full
656 // Wait while another thread set the bucket or a free bucket will be available
657 m_Stat.onBucketsExhausted();
661 // Another thread set the bucket. Wait while it done
662 for ( pBucket = m_Buckets.bucket( nBucket ); pBucket == nullptr; pBucket = m_Buckets.bucket( nBucket )) {
664 m_Stat.onBusyWaitBucketInit();
670 aux_node_type * get_bucket( size_t nHash )
672 size_t nBucket = bucket_no( nHash );
674 aux_node_type * pHead = m_Buckets.bucket( nBucket );
675 if ( pHead == nullptr )
676 pHead = init_bucket( nBucket );
678 assert( pHead->is_dummy());
685 // Initialize bucket 0
686 aux_node_type * pNode = alloc_aux_node( 0 /*split_list::dummy_hash(0)*/ );
688 // insert_aux_node cannot return false for empty list
689 CDS_VERIFY( m_List.insert_aux_node( pNode ));
691 m_Buckets.bucket( 0, pNode );
694 static size_t max_item_count( size_t nBucketCount, size_t nLoadFactor )
696 return nBucketCount * nLoadFactor;
699 void inc_item_count()
701 size_t nMaxCount = m_nMaxItemCount.load( memory_model::memory_order_relaxed );
702 if ( ++m_ItemCounter <= nMaxCount )
705 size_t sz = m_nBucketCountLog2.load( memory_model::memory_order_relaxed );
706 const size_t nBucketCount = static_cast<size_t>(1) << sz;
707 if ( nBucketCount < m_Buckets.capacity()) {
708 // we may grow the bucket table
709 const size_t nLoadFactor = m_Buckets.load_factor();
710 if ( nMaxCount < max_item_count( nBucketCount, nLoadFactor ))
711 return; // someone already have updated m_nBucketCountLog2, so stop here
713 m_nMaxItemCount.compare_exchange_strong( nMaxCount, max_item_count( nBucketCount << 1, nLoadFactor ),
714 memory_model::memory_order_relaxed, atomics::memory_order_relaxed );
715 m_nBucketCountLog2.compare_exchange_strong( sz, sz + 1, memory_model::memory_order_relaxed, atomics::memory_order_relaxed );
718 m_nMaxItemCount.store( std::numeric_limits<size_t>::max(), memory_model::memory_order_relaxed );
724 static unsigned const c_padding = cds::opt::actual_padding< traits::padding >::value;
726 typedef typename cds::details::type_padding< bucket_table, c_padding >::type padded_bucket_table;
727 padded_bucket_table m_Buckets; ///< bucket table
729 typedef typename cds::details::type_padding< ordered_list_wrapper, c_padding >::type padded_ordered_list;
730 padded_ordered_list m_List; ///< Ordered list containing split-list items
732 atomics::atomic<size_t> m_nBucketCountLog2; ///< log2( current bucket count )
733 atomics::atomic<size_t> m_nMaxItemCount; ///< number of items container can hold, before we have to resize
734 item_counter m_ItemCounter; ///< Item counter
735 hash m_HashFunctor; ///< Hash functor
736 stat m_Stat; ///< Internal statistics
740 }} // namespace cds::intrusive
742 #endif // #ifndef CDSLIB_INTRUSIVE_SPLIT_LIST_NOGC_H