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::bit_reversal bit_reversal; ///< Bit reversal algorithm, see \p split_list::traits::bit_reversal
87 typedef typename traits::item_counter item_counter; ///< Item counter type
88 typedef typename traits::back_off back_off; ///< back-off strategy
89 typedef typename traits::memory_model memory_model; ///< Memory ordering. See cds::opt::memory_model option
90 typedef typename traits::stat stat; ///< Internal statistics, see \p spit_list::stat
92 // GC and OrderedList::gc must be the same
93 static_assert(std::is_same<gc, typename ordered_list::gc>::value, "GC and OrderedList::gc must be the same");
95 // atomicity::empty_item_counter is not allowed as a item counter
96 static_assert(!std::is_same<item_counter, cds::atomicity::empty_item_counter>::value,
97 "cds::atomicity::empty_item_counter is not allowed as a item counter");
101 typedef typename ordered_list::node_type list_node_type; ///< Node type as declared in ordered list
102 typedef split_list::node<list_node_type> node_type; ///< split-list node type
104 /// Split-list node traits
106 This traits is intended for converting between underlying ordered list node type \ref list_node_type
107 and split-list node type \ref node_type
109 typedef typename ordered_list_adapter::node_traits node_traits;
111 /// Bucket table implementation
112 typedef typename split_list::details::bucket_table_selector<
113 traits::dynamic_bucket_table
115 , typename ordered_list_adapter::aux_node
116 , opt::allocator< typename traits::allocator >
117 , opt::memory_model< memory_model >
118 , opt::free_list< typename traits::free_list >
119 >::type bucket_table;
121 typedef typename bucket_table::aux_node_type aux_node_type; ///< dummy node type
123 typedef typename ordered_list::iterator list_iterator;
124 typedef typename ordered_list::const_iterator list_const_iterator;
129 /// Ordered list wrapper to access protected members
130 class ordered_list_wrapper: public ordered_list
132 typedef ordered_list base_class;
133 typedef typename base_class::auxiliary_head bucket_head_type;
136 list_iterator insert_at_( aux_node_type * pHead, value_type& val )
138 assert( pHead != nullptr );
139 bucket_head_type h(static_cast<list_node_type *>(pHead));
140 return base_class::insert_at_( h, val );
143 template <typename Func>
144 std::pair<list_iterator, bool> update_at_( aux_node_type * pHead, value_type& val, Func func, bool bAllowInsert )
146 assert( pHead != nullptr );
147 bucket_head_type h(static_cast<list_node_type *>(pHead));
148 return base_class::update_at_( h, val, func, bAllowInsert );
151 template <typename Q, typename Compare, typename Func>
152 bool find_at( aux_node_type * pHead, split_list::details::search_value_type<Q>& val, Compare cmp, Func f )
154 assert( pHead != nullptr );
155 bucket_head_type h(static_cast<list_node_type *>(pHead));
156 return base_class::find_at( h, val, cmp, f );
159 template <typename Q, typename Compare>
160 list_iterator find_at_( aux_node_type * pHead, split_list::details::search_value_type<Q> const & val, Compare cmp )
162 assert( pHead != nullptr );
163 bucket_head_type h(static_cast<list_node_type *>(pHead));
164 return base_class::find_at_( h, val, cmp );
167 bool insert_aux_node( aux_node_type * pNode )
169 return base_class::insert_aux_node( pNode );
171 bool insert_aux_node( aux_node_type * pHead, aux_node_type * pNode )
173 bucket_head_type h(static_cast<list_node_type *>(pHead));
174 return base_class::insert_aux_node( h, pNode );
177 template <typename Predicate>
178 void erase_for( Predicate pred )
180 return base_class::erase_for( pred );
186 /// Initialize split-ordered list of default capacity
188 The default capacity is defined in bucket table constructor.
189 See split_list::expandable_bucket_table, split_list::static_ducket_table
190 which selects by split_list::dynamic_bucket_table option.
193 : m_nBucketCountLog2(1)
194 , m_nMaxItemCount( max_item_count(2, m_Buckets.load_factor()))
199 /// Initialize split-ordered list
201 size_t nItemCount ///< estimate average of item count
202 , size_t nLoadFactor = 1 ///< load factor - average item count per bucket. Small integer up to 10, default is 1.
204 : m_Buckets( nItemCount, nLoadFactor )
205 , m_nBucketCountLog2(1)
206 , m_nMaxItemCount( max_item_count(2, m_Buckets.load_factor()))
211 /// Destroys split-list
219 The function inserts \p val in the set if it does not contain
220 an item with key equal to \p val.
222 Returns \p true if \p val is placed into the set, \p false otherwise.
224 bool insert( value_type& val )
226 return insert_( val ) != end();
231 The operation performs inserting or changing data with lock-free manner.
233 If the item \p val is not found in the set, then \p val is inserted
234 iff \p bAllowInsert is \p true.
235 Otherwise, the functor \p func is called with item found.
236 The functor signature is:
238 void func( bool bNew, value_type& item, value_type& val );
241 - \p bNew - \p true if the item has been inserted, \p false otherwise
242 - \p item - item of the set
243 - \p val - argument \p val passed into the \p update() function
244 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
245 refers to the same thing.
247 The functor may change non-key fields of the \p item.
249 Returns std::pair<bool, bool> where \p first is \p true if operation is successful,
250 \p second is \p true if new item has been added or \p false if the item with \p key
251 already is in the list.
253 @warning For \ref cds_intrusive_MichaelList_hp "MichaelList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
254 \ref cds_intrusive_LazyList_hp "LazyList" provides exclusive access to inserted item and does not require any node-level
257 template <typename Func>
258 std::pair<bool, bool> update( value_type& val, Func func, bool bAllowInsert = true )
260 std::pair<iterator, bool> ret = update_( val, func, bAllowInsert );
261 return std::make_pair( ret.first != end(), ret.second );
264 template <typename Func>
265 CDS_DEPRECATED("ensure() is deprecated, use update()")
266 std::pair<bool, bool> ensure( value_type& val, Func func )
268 return update( val, func, true );
272 /// Checks whether the set contains \p key
274 The function searches the item with key equal to \p key
275 and returns \p true if it is found, and \p false otherwise.
277 Note the hash functor specified for class \p Traits template parameter
278 should accept a parameter of type \p Q that can be not the same as \p value_type.
279 Otherwise, you may use \p contains( Q const&, Less pred ) functions with explicit predicate for key comparing.
281 template <typename Q>
282 value_type * contains( Q const& key )
284 iterator it = find_( key );
290 template <typename Q>
291 CDS_DEPRECATED("deprecated, use contains()")
292 value_type * find( Q const& key )
294 return contains( key );
298 /// Checks whether the set contains \p key using \p pred predicate for searching
300 The function is similar to <tt>contains( key )</tt> but \p pred is used for key comparing.
301 \p Less functor has the interface like \p std::less.
302 \p Less must imply the same element order as the comparator used for building the list.
304 template <typename Q, typename Less>
305 value_type * contains( Q const& key, Less pred )
307 iterator it = find_with_( key, pred );
313 template <typename Q, typename Less>
314 CDS_DEPRECATED("deprecated, use contains()")
315 value_type * find_with( Q const& key, Less pred )
317 return contains( key, pred );
321 /// Finds the key \p key
322 /** \anchor cds_intrusive_SplitListSet_nogc_find_func
323 The function searches the item with key equal to \p key and calls the functor \p f for item found.
324 The interface of \p Func functor is:
327 void operator()( value_type& item, Q& key );
330 where \p item is the item found, \p key is the <tt>find</tt> function argument.
332 The functor can change non-key fields of \p item.
333 The functor does not serialize simultaneous access to the set \p item. If such access is
334 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
336 Note the hash functor specified for class \p Traits template parameter
337 should accept a parameter of type \p Q that can be not the same as \p value_type.
339 The function returns \p true if \p key is found, \p false otherwise.
341 template <typename Q, typename Func>
342 bool find( Q& key, Func f )
344 return find_( key, key_comparator(), f );
347 template <typename Q, typename Func>
348 bool find( Q const& key, Func f )
350 return find_( key, key_comparator(), f );
354 /// Finds the key \p key with \p pred predicate for comparing
356 The function is an analog of \ref cds_intrusive_SplitListSet_nogc_find_func "find(Q&, Func)"
357 but \p cmp is used for key compare.
358 \p Less has the interface like \p std::less.
359 \p cmp must imply the same element order as the comparator used for building the set.
361 template <typename Q, typename Less, typename Func>
362 bool find_with( Q& key, Less pred, Func f )
365 return find_( key, typename ordered_list_adapter::template make_compare_from_less<Less>(), f );
368 template <typename Q, typename Less, typename Func>
369 bool find_with( Q const& key, Less pred, Func f )
372 return find_( key, typename ordered_list_adapter::template make_compare_from_less<Less>(), f );
377 /// Clears the set (non-atomic, not thread-safe)
379 The function unlink all items from the set.
380 The function is not atomic. It cleans up each bucket and then resets the item counter to zero.
381 If there are a thread that performs insertion while \p %clear() is working the result is undefined in general case:
382 <tt> empty() </tt> may return \p true but the set may contain item(s).
383 Therefore, \p %clear() may be used only for debugging purposes.
385 For each item the \p disposer is called after unlinking.
389 m_List.erase_for( []( value_type const& val ) -> bool { return !node_traits::to_node_ptr( val )->is_dummy(); } );
390 m_ItemCounter.reset();
393 /// Checks if the set is empty
395 Emptiness is checked by item counting: if item count is zero then the set is empty.
396 Thus, the correct item counting feature is an important part of split-list implementation.
403 /// Returns item count in the set
406 return m_ItemCounter;
409 /// Returns internal statistics
410 stat const& statistics() const
415 /// Returns internal statistics for \p OrderedList
416 typename OrderedList::stat const& list_statistics() const
418 return m_List.statistics();
423 template <bool IsConst>
425 : public split_list::details::iterator_type<node_traits, ordered_list, IsConst>
427 typedef split_list::details::iterator_type<node_traits, ordered_list, IsConst> iterator_base_class;
428 typedef typename iterator_base_class::list_iterator list_iterator;
431 : iterator_base_class()
434 iterator_type( iterator_type const& src )
435 : iterator_base_class( src )
438 // This ctor should be protected...
439 iterator_type( list_iterator itCur, list_iterator itEnd )
440 : iterator_base_class( itCur, itEnd )
446 ///@name Forward iterators
450 The forward iterator for a split-list has some features:
451 - it has no post-increment operator
452 - it depends on iterator of underlying \p OrderedList
454 typedef iterator_type<false> iterator;
456 /// Const forward iterator
458 For iterator's features and requirements see \ref iterator
460 typedef iterator_type<true> const_iterator;
462 /// Returns a forward iterator addressing the first element in a split-list
464 For empty list \code begin() == end() \endcode
468 return iterator( m_List.begin(), m_List.end());
471 /// Returns an iterator that addresses the location succeeding the last element in a split-list
473 Do not use the value returned by <tt>end</tt> function to access any item.
475 The returned value can be used only to control reaching the end of the split-list.
476 For empty list \code begin() == end() \endcode
480 return iterator( m_List.end(), m_List.end());
483 /// Returns a forward const iterator addressing the first element in a split-list
484 const_iterator begin() const
486 return const_iterator( m_List.begin(), m_List.end());
489 /// Returns a forward const iterator addressing the first element in a split-list
490 const_iterator cbegin() const
492 return const_iterator( m_List.cbegin(), m_List.cend());
495 /// Returns an const iterator that addresses the location succeeding the last element in a split-list
496 const_iterator end() const
498 return const_iterator( m_List.end(), m_List.end());
501 /// Returns an const iterator that addresses the location succeeding the last element in a split-list
502 const_iterator cend() const
504 return const_iterator( m_List.cend(), m_List.cend());
510 iterator insert_( value_type& val )
512 size_t nHash = hash_value( val );
513 aux_node_type * pHead = get_bucket( nHash );
514 assert( pHead != nullptr );
516 node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash<bit_reversal>( nHash );
518 list_iterator it = m_List.insert_at_( pHead, val );
519 if ( it != m_List.end()) {
521 m_Stat.onInsertSuccess();
522 return iterator( it, m_List.end());
524 m_Stat.onInsertFailed();
528 template <typename Func>
529 std::pair<iterator, bool> update_( value_type& val, Func func, bool bAllowInsert )
531 size_t nHash = hash_value( val );
532 aux_node_type * pHead = get_bucket( nHash );
533 assert( pHead != nullptr );
535 node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash<bit_reversal>( nHash );
537 std::pair<list_iterator, bool> ret = m_List.update_at_( pHead, val, func, bAllowInsert );
538 if ( ret.first != m_List.end()) {
541 m_Stat.onUpdateNew();
544 m_Stat.onUpdateExist();
545 return std::make_pair( iterator(ret.first, m_List.end()), ret.second );
547 return std::make_pair( end(), ret.second );
550 template <typename Q, typename Less >
551 iterator find_with_( Q& val, Less pred )
554 size_t nHash = hash_value( val );
555 split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash<bit_reversal>( nHash ));
556 aux_node_type * pHead = get_bucket( nHash );
557 assert( pHead != nullptr );
559 auto it = m_List.find_at_( pHead, sv, typename ordered_list_adapter::template make_compare_from_less<Less>());
560 m_Stat.onFind( it != m_List.end());
561 return iterator( it, m_List.end());
564 template <typename Q>
565 iterator find_( Q const& val )
567 size_t nHash = hash_value( val );
568 split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash<bit_reversal>( nHash ));
569 aux_node_type * pHead = get_bucket( nHash );
570 assert( pHead != nullptr );
572 auto it = m_List.find_at_( pHead, sv, key_comparator());
573 m_Stat.onFind( it != m_List.end());
574 return iterator( it, m_List.end());
577 template <typename Q, typename Compare, typename Func>
578 bool find_( Q& val, Compare cmp, Func f )
580 size_t nHash = hash_value( val );
581 split_list::details::search_value_type<Q> sv( val, split_list::regular_hash<bit_reversal>( nHash ));
582 aux_node_type * pHead = get_bucket( nHash );
583 assert( pHead != nullptr );
584 return m_Stat.onFind( m_List.find_at( pHead, sv, cmp,
585 [&f](value_type& item, split_list::details::search_value_type<Q>& v){ f(item, v.val ); }));
588 aux_node_type * alloc_aux_node( size_t nHash )
590 m_Stat.onHeadNodeAllocated();
591 aux_node_type* p = m_Buckets.alloc_aux_node();
597 void free_aux_node( aux_node_type * p )
599 m_Buckets.free_aux_node( p );
600 m_Stat.onHeadNodeFreed();
603 /// Calculates hash value of \p key
604 template <typename Q>
605 size_t hash_value( Q const& key ) const
607 return m_HashFunctor( key );
610 size_t bucket_no( size_t nHash ) const
612 return nHash & ((1 << m_nBucketCountLog2.load( memory_model::memory_order_relaxed )) - 1);
615 static size_t parent_bucket( size_t nBucket )
617 assert( nBucket > 0 );
618 return nBucket & ~(1 << bitop::MSBnz( nBucket ));
621 aux_node_type * init_bucket( size_t const nBucket )
623 assert( nBucket > 0 );
624 size_t nParent = parent_bucket( nBucket );
626 aux_node_type * pParentBucket = m_Buckets.bucket( nParent );
627 if ( pParentBucket == nullptr ) {
628 pParentBucket = init_bucket( nParent );
629 m_Stat.onRecursiveInitBucket();
632 assert( pParentBucket != nullptr );
634 // Allocate an aux node for new bucket
635 aux_node_type * pBucket = m_Buckets.bucket( nBucket );
638 for ( ;; pBucket = m_Buckets.bucket( nBucket )) {
642 pBucket = alloc_aux_node( split_list::dummy_hash<bit_reversal>( nBucket ));
644 if ( m_List.insert_aux_node( pParentBucket, pBucket )) {
645 m_Buckets.bucket( nBucket, pBucket );
646 m_Stat.onNewBucket();
650 // Another thread set the bucket. Wait while it done
651 free_aux_node( pBucket );
652 m_Stat.onBucketInitContenton();
656 // There are no free buckets. It means that the bucket table is full
657 // Wait while another thread set the bucket or a free bucket will be available
658 m_Stat.onBucketsExhausted();
662 // Another thread set the bucket. Wait while it done
663 for ( pBucket = m_Buckets.bucket( nBucket ); pBucket == nullptr; pBucket = m_Buckets.bucket( nBucket )) {
665 m_Stat.onBusyWaitBucketInit();
671 aux_node_type * get_bucket( size_t nHash )
673 size_t nBucket = bucket_no( nHash );
675 aux_node_type * pHead = m_Buckets.bucket( nBucket );
676 if ( pHead == nullptr )
677 pHead = init_bucket( nBucket );
679 assert( pHead->is_dummy());
686 // Initialize bucket 0
687 aux_node_type * pNode = alloc_aux_node( 0 /*split_list::dummy_hash<bit_reversal>(0)*/ );
689 // insert_aux_node cannot return false for empty list
690 CDS_VERIFY( m_List.insert_aux_node( pNode ));
692 m_Buckets.bucket( 0, pNode );
695 static size_t max_item_count( size_t nBucketCount, size_t nLoadFactor )
697 return nBucketCount * nLoadFactor;
700 void inc_item_count()
702 size_t nMaxCount = m_nMaxItemCount.load( memory_model::memory_order_relaxed );
703 if ( ++m_ItemCounter <= nMaxCount )
706 size_t sz = m_nBucketCountLog2.load( memory_model::memory_order_relaxed );
707 const size_t nBucketCount = static_cast<size_t>(1) << sz;
708 if ( nBucketCount < m_Buckets.capacity()) {
709 // we may grow the bucket table
710 const size_t nLoadFactor = m_Buckets.load_factor();
711 if ( nMaxCount < max_item_count( nBucketCount, nLoadFactor ))
712 return; // someone already have updated m_nBucketCountLog2, so stop here
714 m_nMaxItemCount.compare_exchange_strong( nMaxCount, max_item_count( nBucketCount << 1, nLoadFactor ),
715 memory_model::memory_order_relaxed, atomics::memory_order_relaxed );
716 m_nBucketCountLog2.compare_exchange_strong( sz, sz + 1, memory_model::memory_order_relaxed, atomics::memory_order_relaxed );
719 m_nMaxItemCount.store( std::numeric_limits<size_t>::max(), memory_model::memory_order_relaxed );
725 static unsigned const c_padding = cds::opt::actual_padding< traits::padding >::value;
727 typedef typename cds::details::type_padding< bucket_table, c_padding >::type padded_bucket_table;
728 padded_bucket_table m_Buckets; ///< bucket table
730 typedef typename cds::details::type_padding< ordered_list_wrapper, c_padding >::type padded_ordered_list;
731 padded_ordered_list m_List; ///< Ordered list containing split-list items
733 atomics::atomic<size_t> m_nBucketCountLog2; ///< log2( current bucket count )
734 atomics::atomic<size_t> m_nMaxItemCount; ///< number of items container can hold, before we have to resize
735 hash m_HashFunctor; ///< Hash functor
736 item_counter m_ItemCounter; ///< Item counter
737 stat m_Stat; ///< Internal statistics
741 }} // namespace cds::intrusive
743 #endif // #ifndef CDSLIB_INTRUSIVE_SPLIT_LIST_NOGC_H