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_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> wrapped_ordered_list;
77 # ifdef CDS_DOXYGEN_INVOKED
78 typedef OrderedList ordered_list; ///< type of ordered list used as base for split-list
80 typedef typename wrapped_ordered_list::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 split_list::node_traits<typename ordered_list::node_traits> node_traits;
110 /// Bucket table implementation
111 typedef typename split_list::details::bucket_table_selector<
112 traits::dynamic_bucket_table
115 , opt::allocator< typename traits::allocator >
116 , opt::memory_model< memory_model >
117 >::type bucket_table;
119 typedef typename bucket_table::aux_node_type aux_node_type; ///< dummy node type
121 typedef typename ordered_list::iterator list_iterator;
122 typedef typename ordered_list::const_iterator list_const_iterator;
127 /// Ordered list wrapper to access protected members
128 class ordered_list_wrapper: public ordered_list
130 typedef ordered_list base_class;
131 typedef typename base_class::auxiliary_head bucket_head_type;
134 list_iterator insert_at_( aux_node_type * pHead, value_type& val )
136 assert( pHead != nullptr );
137 bucket_head_type h(static_cast<list_node_type *>(pHead));
138 return base_class::insert_at_( h, val );
141 template <typename Func>
142 std::pair<list_iterator, bool> update_at_( aux_node_type * pHead, value_type& val, Func func, bool bAllowInsert )
144 assert( pHead != nullptr );
145 bucket_head_type h(static_cast<list_node_type *>(pHead));
146 return base_class::update_at_( h, val, func, bAllowInsert );
149 template <typename Q, typename Compare, typename Func>
150 bool find_at( aux_node_type * pHead, split_list::details::search_value_type<Q>& val, Compare cmp, Func f )
152 assert( pHead != nullptr );
153 bucket_head_type h(static_cast<list_node_type *>(pHead));
154 return base_class::find_at( h, val, cmp, f );
157 template <typename Q, typename Compare>
158 list_iterator find_at_( aux_node_type * pHead, split_list::details::search_value_type<Q> const & val, Compare cmp )
160 assert( pHead != nullptr );
161 bucket_head_type h(static_cast<list_node_type *>(pHead));
162 return base_class::find_at_( h, val, cmp );
165 bool insert_aux_node( aux_node_type * pNode )
167 return base_class::insert_aux_node( pNode );
169 bool insert_aux_node( aux_node_type * pHead, aux_node_type * pNode )
171 bucket_head_type h(static_cast<list_node_type *>(pHead));
172 return base_class::insert_aux_node( h, pNode );
175 template <typename Predicate>
176 void erase_for( Predicate pred )
178 return base_class::erase_for( pred );
184 /// Initialize split-ordered list of default capacity
186 The default capacity is defined in bucket table constructor.
187 See split_list::expandable_bucket_table, split_list::static_ducket_table
188 which selects by split_list::dynamic_bucket_table option.
191 : m_nBucketCountLog2(1)
192 , m_nMaxItemCount( max_item_count(2, m_Buckets.load_factor()) )
197 /// Initialize split-ordered list
199 size_t nItemCount ///< estimate average of item count
200 , size_t nLoadFactor = 1 ///< load factor - average item count per bucket. Small integer up to 10, default is 1.
202 : m_Buckets( nItemCount, nLoadFactor )
203 , m_nBucketCountLog2(1)
204 , m_nMaxItemCount( max_item_count(2, m_Buckets.load_factor()) )
209 /// Destroys split-list
217 The function inserts \p val in the set if it does not contain
218 an item with key equal to \p val.
220 Returns \p true if \p val is placed into the set, \p false otherwise.
222 bool insert( value_type& val )
224 return insert_( val ) != end();
229 The operation performs inserting or changing data with lock-free manner.
231 If the item \p val is not found in the set, then \p val is inserted
232 iff \p bAllowInsert is \p true.
233 Otherwise, the functor \p func is called with item found.
234 The functor signature is:
236 void func( bool bNew, value_type& item, value_type& val );
239 - \p bNew - \p true if the item has been inserted, \p false otherwise
240 - \p item - item of the set
241 - \p val - argument \p val passed into the \p update() function
242 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
243 refers to the same thing.
245 The functor may change non-key fields of the \p item.
247 Returns std::pair<bool, bool> where \p first is \p true if operation is successful,
248 \p second is \p true if new item has been added or \p false if the item with \p key
249 already is in the list.
251 @warning For \ref cds_intrusive_MichaelList_hp "MichaelList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
252 \ref cds_intrusive_LazyList_hp "LazyList" provides exclusive access to inserted item and does not require any node-level
255 template <typename Func>
256 std::pair<bool, bool> update( value_type& val, Func func, bool bAllowInsert = true )
258 std::pair<iterator, bool> ret = update_( val, func, bAllowInsert );
259 return std::make_pair( ret.first != end(), ret.second );
262 template <typename Func>
263 CDS_DEPRECATED("ensure() is deprecated, use update()")
264 std::pair<bool, bool> ensure( value_type& val, Func func )
266 return update( val, func, true );
270 /// Checks whether the set contains \p key
272 The function searches the item with key equal to \p key
273 and returns \p true if it is found, and \p false otherwise.
275 Note the hash functor specified for class \p Traits template parameter
276 should accept a parameter of type \p Q that can be not the same as \p value_type.
277 Otherwise, you may use \p contains( Q const&, Less pred ) functions with explicit predicate for key comparing.
279 template <typename Q>
280 value_type * contains( Q const& key )
282 iterator it = find_( key );
288 template <typename Q>
289 CDS_DEPRECATED("deprecated, use contains()")
290 value_type * find( Q const& key )
292 return contains( key );
296 /// Checks whether the set contains \p key using \p pred predicate for searching
298 The function is similar to <tt>contains( key )</tt> but \p pred is used for key comparing.
299 \p Less functor has the interface like \p std::less.
300 \p Less must imply the same element order as the comparator used for building the list.
302 template <typename Q, typename Less>
303 value_type * contains( Q const& key, Less pred )
305 iterator it = find_with_( key, pred );
311 template <typename Q, typename Less>
312 CDS_DEPRECATED("deprecated, use contains()")
313 value_type * find_with( Q const& key, Less pred )
315 return contains( key, pred );
319 /// Finds the key \p key
320 /** \anchor cds_intrusive_SplitListSet_nogc_find_func
321 The function searches the item with key equal to \p key and calls the functor \p f for item found.
322 The interface of \p Func functor is:
325 void operator()( value_type& item, Q& key );
328 where \p item is the item found, \p key is the <tt>find</tt> function argument.
330 The functor can change non-key fields of \p item.
331 The functor does not serialize simultaneous access to the set \p item. If such access is
332 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
334 Note the hash functor specified for class \p Traits template parameter
335 should accept a parameter of type \p Q that can be not the same as \p value_type.
337 The function returns \p true if \p key is found, \p false otherwise.
339 template <typename Q, typename Func>
340 bool find( Q& key, Func f )
342 return find_( key, key_comparator(), f );
345 template <typename Q, typename Func>
346 bool find( Q const& key, Func f )
348 return find_( key, key_comparator(), f );
352 /// Finds the key \p key with \p pred predicate for comparing
354 The function is an analog of \ref cds_intrusive_SplitListSet_nogc_find_func "find(Q&, Func)"
355 but \p cmp is used for key compare.
356 \p Less has the interface like \p std::less.
357 \p cmp must imply the same element order as the comparator used for building the set.
359 template <typename Q, typename Less, typename Func>
360 bool find_with( Q& key, Less pred, Func f )
363 return find_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>(), f );
366 template <typename Q, typename Less, typename Func>
367 bool find_with( Q const& key, Less pred, Func f )
370 return find_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>(), f );
375 /// Clears the set (non-atomic, not thread-safe)
377 The function unlink all items from the set.
378 The function is not atomic. It cleans up each bucket and then resets the item counter to zero.
379 If there are a thread that performs insertion while \p %clear() is working the result is undefined in general case:
380 <tt> empty() </tt> may return \p true but the set may contain item(s).
381 Therefore, \p %clear() may be used only for debugging purposes.
383 For each item the \p disposer is called after unlinking.
387 m_List.erase_for( []( value_type const& val ) -> bool { return !node_traits::to_node_ptr( val )->is_dummy(); } );
388 m_ItemCounter.reset();
391 /// Checks if the set is empty
393 Emptiness is checked by item counting: if item count is zero then the set is empty.
394 Thus, the correct item counting feature is an important part of split-list implementation.
401 /// Returns item count in the set
404 return m_ItemCounter;
407 /// Returns internal statistics
408 stat const& statistics() const
415 template <bool IsConst>
417 : public split_list::details::iterator_type<node_traits, ordered_list, IsConst>
419 typedef split_list::details::iterator_type<node_traits, ordered_list, IsConst> iterator_base_class;
420 typedef typename iterator_base_class::list_iterator list_iterator;
423 : iterator_base_class()
426 iterator_type( iterator_type const& src )
427 : iterator_base_class( src )
430 // This ctor should be protected...
431 iterator_type( list_iterator itCur, list_iterator itEnd )
432 : iterator_base_class( itCur, itEnd )
438 ///@name Forward iterators
442 The forward iterator for a split-list has some features:
443 - it has no post-increment operator
444 - it depends on iterator of underlying \p OrderedList
446 typedef iterator_type<false> iterator;
448 /// Const forward iterator
450 For iterator's features and requirements see \ref iterator
452 typedef iterator_type<true> const_iterator;
454 /// Returns a forward iterator addressing the first element in a split-list
456 For empty list \code begin() == end() \endcode
460 return iterator( m_List.begin(), m_List.end() );
463 /// Returns an iterator that addresses the location succeeding the last element in a split-list
465 Do not use the value returned by <tt>end</tt> function to access any item.
467 The returned value can be used only to control reaching the end of the split-list.
468 For empty list \code begin() == end() \endcode
472 return iterator( m_List.end(), m_List.end() );
475 /// Returns a forward const iterator addressing the first element in a split-list
476 const_iterator begin() const
478 return const_iterator( m_List.begin(), m_List.end() );
481 /// Returns a forward const iterator addressing the first element in a split-list
482 const_iterator cbegin() const
484 return const_iterator( m_List.cbegin(), m_List.cend() );
487 /// Returns an const iterator that addresses the location succeeding the last element in a split-list
488 const_iterator end() const
490 return const_iterator( m_List.end(), m_List.end() );
493 /// Returns an const iterator that addresses the location succeeding the last element in a split-list
494 const_iterator cend() const
496 return const_iterator( m_List.cend(), m_List.cend() );
502 iterator insert_( value_type& val )
504 size_t nHash = hash_value( val );
505 aux_node_type * pHead = get_bucket( nHash );
506 assert( pHead != nullptr );
508 node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
510 list_iterator it = m_List.insert_at_( pHead, val );
511 if ( it != m_List.end() ) {
513 m_Stat.onInsertSuccess();
514 return iterator( it, m_List.end() );
516 m_Stat.onInsertFailed();
520 template <typename Func>
521 std::pair<iterator, bool> update_( value_type& val, Func func, bool bAllowInsert )
523 size_t nHash = hash_value( val );
524 aux_node_type * pHead = get_bucket( nHash );
525 assert( pHead != nullptr );
527 node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
529 std::pair<list_iterator, bool> ret = m_List.update_at_( pHead, val, func, bAllowInsert );
530 if ( ret.first != m_List.end() ) {
533 m_Stat.onUpdateNew();
536 m_Stat.onUpdateExist();
537 return std::make_pair( iterator(ret.first, m_List.end()), ret.second );
539 return std::make_pair( end(), ret.second );
542 template <typename Q, typename Less >
543 iterator find_with_( Q& val, Less pred )
546 size_t nHash = hash_value( val );
547 split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash( nHash ));
548 aux_node_type * pHead = get_bucket( nHash );
549 assert( pHead != nullptr );
551 auto it = m_List.find_at_( pHead, sv, typename wrapped_ordered_list::template make_compare_from_less<Less>() );
552 m_Stat.onFind( it != m_List.end() );
553 return iterator( it, m_List.end() );
556 template <typename Q>
557 iterator find_( Q const& val )
559 size_t nHash = hash_value( val );
560 split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash( nHash ));
561 aux_node_type * pHead = get_bucket( nHash );
562 assert( pHead != nullptr );
564 auto it = m_List.find_at_( pHead, sv, key_comparator() );
565 m_Stat.onFind( it != m_List.end() );
566 return iterator( it, m_List.end() );
569 template <typename Q, typename Compare, typename Func>
570 bool find_( Q& val, Compare cmp, Func f )
572 size_t nHash = hash_value( val );
573 split_list::details::search_value_type<Q> sv( val, split_list::regular_hash( nHash ));
574 aux_node_type * pHead = get_bucket( nHash );
575 assert( pHead != nullptr );
576 return m_Stat.onFind( m_List.find_at( pHead, sv, cmp,
577 [&f](value_type& item, split_list::details::search_value_type<Q>& val){ f(item, val.val ); }));
580 aux_node_type * alloc_aux_node( size_t nHash )
582 m_Stat.onHeadNodeAllocated();
583 aux_node_type* p = m_Buckets.alloc_aux_node();
589 void free_aux_node( aux_node_type * p )
591 m_Buckets.free_aux_node( p );
592 m_Stat.onHeadNodeFreed();
595 /// Calculates hash value of \p key
596 template <typename Q>
597 size_t hash_value( Q const& key ) const
599 return m_HashFunctor( key );
602 size_t bucket_no( size_t nHash ) const
604 return nHash & ((1 << m_nBucketCountLog2.load( memory_model::memory_order_relaxed )) - 1);
607 static size_t parent_bucket( size_t nBucket )
609 assert( nBucket > 0 );
610 return nBucket & ~(1 << bitop::MSBnz( nBucket ));
613 aux_node_type * init_bucket( size_t const nBucket )
615 assert( nBucket > 0 );
616 size_t nParent = parent_bucket( nBucket );
618 aux_node_type * pParentBucket = m_Buckets.bucket( nParent );
619 if ( pParentBucket == nullptr ) {
620 pParentBucket = init_bucket( nParent );
621 m_Stat.onRecursiveInitBucket();
624 assert( pParentBucket != nullptr );
626 // Allocate an aux node for new bucket
627 aux_node_type * pBucket = m_Buckets.bucket( nBucket );
630 for ( ;; pBucket = m_Buckets.bucket( nBucket ) ) {
634 pBucket = alloc_aux_node( split_list::dummy_hash( nBucket ) );
636 if ( m_List.insert_aux_node( pParentBucket, pBucket ) ) {
637 m_Buckets.bucket( nBucket, pBucket );
638 m_Stat.onNewBucket();
642 // Another thread set the bucket. Wait while it done
643 free_aux_node( pBucket );
644 m_Stat.onBucketInitContenton();
648 // There are no free buckets. It means that the bucket table is full
649 // Wait while another thread set the bucket or a free bucket will be available
650 m_Stat.onBucketsExhausted();
654 // Another thread set the bucket. Wait while it done
655 for ( pBucket = m_Buckets.bucket( nBucket ); pBucket == nullptr; pBucket = m_Buckets.bucket( nBucket ) ) {
657 m_Stat.onBusyWaitBucketInit();
663 aux_node_type * get_bucket( size_t nHash )
665 size_t nBucket = bucket_no( nHash );
667 aux_node_type * pHead = m_Buckets.bucket( nBucket );
668 if ( pHead == nullptr )
669 pHead = init_bucket( nBucket );
671 assert( pHead->is_dummy() );
678 // Initialize bucket 0
679 aux_node_type * pNode = alloc_aux_node( 0 /*split_list::dummy_hash(0)*/ );
681 // insert_aux_node cannot return false for empty list
682 CDS_VERIFY( m_List.insert_aux_node( pNode ) );
684 m_Buckets.bucket( 0, pNode );
687 static size_t max_item_count( size_t nBucketCount, size_t nLoadFactor )
689 return nBucketCount * nLoadFactor;
692 void inc_item_count()
694 size_t nMaxCount = m_nMaxItemCount.load( memory_model::memory_order_relaxed );
695 if ( ++m_ItemCounter <= nMaxCount )
698 size_t sz = m_nBucketCountLog2.load( memory_model::memory_order_relaxed );
699 const size_t nBucketCount = static_cast<size_t>(1) << sz;
700 if ( nBucketCount < m_Buckets.capacity() ) {
701 // we may grow the bucket table
702 const size_t nLoadFactor = m_Buckets.load_factor();
703 if ( nMaxCount < max_item_count( nBucketCount, nLoadFactor ) )
704 return; // someone already have updated m_nBucketCountLog2, so stop here
706 m_nMaxItemCount.compare_exchange_strong( nMaxCount, max_item_count( nBucketCount << 1, nLoadFactor ),
707 memory_model::memory_order_relaxed, atomics::memory_order_relaxed );
708 m_nBucketCountLog2.compare_exchange_strong( sz, sz + 1, memory_model::memory_order_relaxed, atomics::memory_order_relaxed );
711 m_nMaxItemCount.store( std::numeric_limits<size_t>::max(), memory_model::memory_order_relaxed );
717 static unsigned const c_padding = cds::opt::actual_padding< traits::padding >::value;
719 typedef typename cds::details::type_padding< bucket_table, c_padding >::type padded_bucket_table;
720 padded_bucket_table m_Buckets; ///< bucket table
722 typedef typename cds::details::type_padding< ordered_list_wrapper, c_padding >::type padded_ordered_list;
723 padded_ordered_list m_List; ///< Ordered list containing split-list items
725 atomics::atomic<size_t> m_nBucketCountLog2; ///< log2( current bucket count )
726 atomics::atomic<size_t> m_nMaxItemCount; ///< number of items container can hold, before we have to resize
727 item_counter m_ItemCounter; ///< Item counter
728 hash m_HashFunctor; ///< Hash functor
729 stat m_Stat; ///< Internal statistics
733 }} // namespace cds::intrusive
735 #endif // #ifndef CDSLIB_INTRUSIVE_SPLIT_LIST_NOGC_H