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> 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
416 template <bool IsConst>
418 : public split_list::details::iterator_type<node_traits, ordered_list, IsConst>
420 typedef split_list::details::iterator_type<node_traits, ordered_list, IsConst> iterator_base_class;
421 typedef typename iterator_base_class::list_iterator list_iterator;
424 : iterator_base_class()
427 iterator_type( iterator_type const& src )
428 : iterator_base_class( src )
431 // This ctor should be protected...
432 iterator_type( list_iterator itCur, list_iterator itEnd )
433 : iterator_base_class( itCur, itEnd )
439 ///@name Forward iterators
443 The forward iterator for a split-list has some features:
444 - it has no post-increment operator
445 - it depends on iterator of underlying \p OrderedList
447 typedef iterator_type<false> iterator;
449 /// Const forward iterator
451 For iterator's features and requirements see \ref iterator
453 typedef iterator_type<true> const_iterator;
455 /// Returns a forward iterator addressing the first element in a split-list
457 For empty list \code begin() == end() \endcode
461 return iterator( m_List.begin(), m_List.end() );
464 /// Returns an iterator that addresses the location succeeding the last element in a split-list
466 Do not use the value returned by <tt>end</tt> function to access any item.
468 The returned value can be used only to control reaching the end of the split-list.
469 For empty list \code begin() == end() \endcode
473 return iterator( m_List.end(), m_List.end() );
476 /// Returns a forward const iterator addressing the first element in a split-list
477 const_iterator begin() const
479 return const_iterator( m_List.begin(), m_List.end() );
482 /// Returns a forward const iterator addressing the first element in a split-list
483 const_iterator cbegin() const
485 return const_iterator( m_List.cbegin(), m_List.cend() );
488 /// Returns an const iterator that addresses the location succeeding the last element in a split-list
489 const_iterator end() const
491 return const_iterator( m_List.end(), m_List.end() );
494 /// Returns an const iterator that addresses the location succeeding the last element in a split-list
495 const_iterator cend() const
497 return const_iterator( m_List.cend(), m_List.cend() );
503 iterator insert_( value_type& val )
505 size_t nHash = hash_value( val );
506 aux_node_type * pHead = get_bucket( nHash );
507 assert( pHead != nullptr );
509 node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
511 list_iterator it = m_List.insert_at_( pHead, val );
512 if ( it != m_List.end() ) {
514 m_Stat.onInsertSuccess();
515 return iterator( it, m_List.end() );
517 m_Stat.onInsertFailed();
521 template <typename Func>
522 std::pair<iterator, bool> update_( value_type& val, Func func, bool bAllowInsert )
524 size_t nHash = hash_value( val );
525 aux_node_type * pHead = get_bucket( nHash );
526 assert( pHead != nullptr );
528 node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
530 std::pair<list_iterator, bool> ret = m_List.update_at_( pHead, val, func, bAllowInsert );
531 if ( ret.first != m_List.end() ) {
534 m_Stat.onUpdateNew();
537 m_Stat.onUpdateExist();
538 return std::make_pair( iterator(ret.first, m_List.end()), ret.second );
540 return std::make_pair( end(), ret.second );
543 template <typename Q, typename Less >
544 iterator find_with_( Q& val, Less pred )
547 size_t nHash = hash_value( val );
548 split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash( nHash ));
549 aux_node_type * pHead = get_bucket( nHash );
550 assert( pHead != nullptr );
552 auto it = m_List.find_at_( pHead, sv, typename ordered_list_adapter::template make_compare_from_less<Less>() );
553 m_Stat.onFind( it != m_List.end() );
554 return iterator( it, m_List.end() );
557 template <typename Q>
558 iterator find_( Q const& val )
560 size_t nHash = hash_value( val );
561 split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash( nHash ));
562 aux_node_type * pHead = get_bucket( nHash );
563 assert( pHead != nullptr );
565 auto it = m_List.find_at_( pHead, sv, key_comparator() );
566 m_Stat.onFind( it != m_List.end() );
567 return iterator( it, m_List.end() );
570 template <typename Q, typename Compare, typename Func>
571 bool find_( Q& val, Compare cmp, Func f )
573 size_t nHash = hash_value( val );
574 split_list::details::search_value_type<Q> sv( val, split_list::regular_hash( nHash ));
575 aux_node_type * pHead = get_bucket( nHash );
576 assert( pHead != nullptr );
577 return m_Stat.onFind( m_List.find_at( pHead, sv, cmp,
578 [&f](value_type& item, split_list::details::search_value_type<Q>& val){ f(item, val.val ); }));
581 aux_node_type * alloc_aux_node( size_t nHash )
583 m_Stat.onHeadNodeAllocated();
584 aux_node_type* p = m_Buckets.alloc_aux_node();
590 void free_aux_node( aux_node_type * p )
592 m_Buckets.free_aux_node( p );
593 m_Stat.onHeadNodeFreed();
596 /// Calculates hash value of \p key
597 template <typename Q>
598 size_t hash_value( Q const& key ) const
600 return m_HashFunctor( key );
603 size_t bucket_no( size_t nHash ) const
605 return nHash & ((1 << m_nBucketCountLog2.load( memory_model::memory_order_relaxed )) - 1);
608 static size_t parent_bucket( size_t nBucket )
610 assert( nBucket > 0 );
611 return nBucket & ~(1 << bitop::MSBnz( nBucket ));
614 aux_node_type * init_bucket( size_t const nBucket )
616 assert( nBucket > 0 );
617 size_t nParent = parent_bucket( nBucket );
619 aux_node_type * pParentBucket = m_Buckets.bucket( nParent );
620 if ( pParentBucket == nullptr ) {
621 pParentBucket = init_bucket( nParent );
622 m_Stat.onRecursiveInitBucket();
625 assert( pParentBucket != nullptr );
627 // Allocate an aux node for new bucket
628 aux_node_type * pBucket = m_Buckets.bucket( nBucket );
631 for ( ;; pBucket = m_Buckets.bucket( nBucket ) ) {
635 pBucket = alloc_aux_node( split_list::dummy_hash( nBucket ) );
637 if ( m_List.insert_aux_node( pParentBucket, pBucket ) ) {
638 m_Buckets.bucket( nBucket, pBucket );
639 m_Stat.onNewBucket();
643 // Another thread set the bucket. Wait while it done
644 free_aux_node( pBucket );
645 m_Stat.onBucketInitContenton();
649 // There are no free buckets. It means that the bucket table is full
650 // Wait while another thread set the bucket or a free bucket will be available
651 m_Stat.onBucketsExhausted();
655 // Another thread set the bucket. Wait while it done
656 for ( pBucket = m_Buckets.bucket( nBucket ); pBucket == nullptr; pBucket = m_Buckets.bucket( nBucket ) ) {
658 m_Stat.onBusyWaitBucketInit();
664 aux_node_type * get_bucket( size_t nHash )
666 size_t nBucket = bucket_no( nHash );
668 aux_node_type * pHead = m_Buckets.bucket( nBucket );
669 if ( pHead == nullptr )
670 pHead = init_bucket( nBucket );
672 assert( pHead->is_dummy() );
679 // Initialize bucket 0
680 aux_node_type * pNode = alloc_aux_node( 0 /*split_list::dummy_hash(0)*/ );
682 // insert_aux_node cannot return false for empty list
683 CDS_VERIFY( m_List.insert_aux_node( pNode ) );
685 m_Buckets.bucket( 0, pNode );
688 static size_t max_item_count( size_t nBucketCount, size_t nLoadFactor )
690 return nBucketCount * nLoadFactor;
693 void inc_item_count()
695 size_t nMaxCount = m_nMaxItemCount.load( memory_model::memory_order_relaxed );
696 if ( ++m_ItemCounter <= nMaxCount )
699 size_t sz = m_nBucketCountLog2.load( memory_model::memory_order_relaxed );
700 const size_t nBucketCount = static_cast<size_t>(1) << sz;
701 if ( nBucketCount < m_Buckets.capacity() ) {
702 // we may grow the bucket table
703 const size_t nLoadFactor = m_Buckets.load_factor();
704 if ( nMaxCount < max_item_count( nBucketCount, nLoadFactor ) )
705 return; // someone already have updated m_nBucketCountLog2, so stop here
707 m_nMaxItemCount.compare_exchange_strong( nMaxCount, max_item_count( nBucketCount << 1, nLoadFactor ),
708 memory_model::memory_order_relaxed, atomics::memory_order_relaxed );
709 m_nBucketCountLog2.compare_exchange_strong( sz, sz + 1, memory_model::memory_order_relaxed, atomics::memory_order_relaxed );
712 m_nMaxItemCount.store( std::numeric_limits<size_t>::max(), memory_model::memory_order_relaxed );
718 static unsigned const c_padding = cds::opt::actual_padding< traits::padding >::value;
720 typedef typename cds::details::type_padding< bucket_table, c_padding >::type padded_bucket_table;
721 padded_bucket_table m_Buckets; ///< bucket table
723 typedef typename cds::details::type_padding< ordered_list_wrapper, c_padding >::type padded_ordered_list;
724 padded_ordered_list m_List; ///< Ordered list containing split-list items
726 atomics::atomic<size_t> m_nBucketCountLog2; ///< log2( current bucket count )
727 atomics::atomic<size_t> m_nMaxItemCount; ///< number of items container can hold, before we have to resize
728 item_counter m_ItemCounter; ///< Item counter
729 hash m_HashFunctor; ///< Hash functor
730 stat m_Stat; ///< Internal statistics
734 }} // namespace cds::intrusive
736 #endif // #ifndef CDSLIB_INTRUSIVE_SPLIT_LIST_NOGC_H