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>
39 namespace cds { namespace intrusive {
41 /// Split-ordered list (template specialization for gc::nogc)
42 /** @ingroup cds_intrusive_map
43 \anchor cds_intrusive_SplitListSet_nogc
45 This specialization is intended for so-called persistent usage when no item
46 reclamation may be performed. The class does not support deleting of list item.
48 See \ref cds_intrusive_SplitListSet_hp "SplitListSet" for description of template parameters.
49 The template parameter \p OrderedList should be any gc::nogc-derived ordered list, for example,
50 \ref cds_intrusive_MichaelList_nogc "persistent MichaelList",
51 \ref cds_intrusive_LazyList_nogc "persistent LazyList"
55 #ifdef CDS_DOXYGEN_INVOKED
56 class Traits = split_list::traits
61 class SplitListSet< cds::gc::nogc, OrderedList, Traits >
64 typedef cds::gc::nogc gc; ///< Garbage collector
65 typedef Traits traits; ///< Traits template parameters
67 /// Hash functor for \p value_type and all its derivatives that you use
68 typedef typename cds::opt::v::hash_selector< typename traits::hash >::type hash;
72 typedef split_list::details::rebind_list_traits<OrderedList, traits> wrapped_ordered_list;
76 # ifdef CDS_DOXYGEN_INVOKED
77 typedef OrderedList ordered_list; ///< type of ordered list used as base for split-list
79 typedef typename wrapped_ordered_list::result ordered_list;
81 typedef typename ordered_list::value_type value_type; ///< type of value stored in the split-list
82 typedef typename ordered_list::key_comparator key_comparator; ///< key comparison functor
83 typedef typename ordered_list::disposer disposer; ///< Node disposer functor
85 typedef typename traits::item_counter item_counter; ///< Item counter type
86 typedef typename traits::back_off back_off; ///< back-off strategy
87 typedef typename traits::memory_model memory_model; ///< Memory ordering. See cds::opt::memory_model option
88 typedef typename traits::stat stat; ///< Internal statistics, see \p spit_list::stat
91 typedef typename ordered_list::node_type list_node_type; ///< Node type as declared in ordered list
92 typedef split_list::node<list_node_type> node_type; ///< split-list node type
93 typedef node_type dummy_node_type; ///< dummy node type
95 /// Split-list node traits
97 This traits is intended for converting between underlying ordered list node type \ref list_node_type
98 and split-list node type \ref node_type
100 typedef split_list::node_traits<typename ordered_list::node_traits> node_traits;
103 /// Bucket table implementation
104 typedef typename split_list::details::bucket_table_selector<
105 traits::dynamic_bucket_table
108 , opt::allocator< typename traits::allocator >
109 , opt::memory_model< memory_model >
110 >::type bucket_table;
112 typedef typename ordered_list::iterator list_iterator;
113 typedef typename ordered_list::const_iterator list_const_iterator;
118 /// Ordered list wrapper to access protected members
119 class ordered_list_wrapper: public ordered_list
121 typedef ordered_list base_class;
122 typedef typename base_class::auxiliary_head bucket_head_type;
125 list_iterator insert_at_( dummy_node_type * pHead, value_type& val )
127 assert( pHead != nullptr );
128 bucket_head_type h(static_cast<list_node_type *>(pHead));
129 return base_class::insert_at_( h, val );
132 template <typename Func>
133 std::pair<list_iterator, bool> update_at_( dummy_node_type * pHead, value_type& val, Func func, bool bAllowInsert )
135 assert( pHead != nullptr );
136 bucket_head_type h(static_cast<list_node_type *>(pHead));
137 return base_class::update_at_( h, val, func, bAllowInsert );
140 template <typename Q, typename Compare, typename Func>
141 bool find_at( dummy_node_type * pHead, split_list::details::search_value_type<Q>& val, Compare cmp, Func f )
143 assert( pHead != nullptr );
144 bucket_head_type h(static_cast<list_node_type *>(pHead));
145 return base_class::find_at( h, val, cmp, f );
148 template <typename Q, typename Compare>
149 list_iterator find_at_( dummy_node_type * pHead, split_list::details::search_value_type<Q> const & val, Compare cmp )
151 assert( pHead != nullptr );
152 bucket_head_type h(static_cast<list_node_type *>(pHead));
153 return base_class::find_at_( h, val, cmp );
156 bool insert_aux_node( dummy_node_type * pNode )
158 return base_class::insert_aux_node( pNode );
160 bool insert_aux_node( dummy_node_type * pHead, dummy_node_type * pNode )
162 bucket_head_type h(static_cast<list_node_type *>(pHead));
163 return base_class::insert_aux_node( h, pNode );
166 template <typename Predicate>
167 void erase_for( Predicate pred )
169 return base_class::erase_for( pred );
176 ordered_list_wrapper m_List; ///< Ordered list containing split-list items
177 bucket_table m_Buckets; ///< bucket table
178 atomics::atomic<size_t> m_nBucketCountLog2; ///< log2( current bucket count )
179 atomics::atomic<size_t> m_nMaxItemCount; ///< number of items container can hold, before we have to resize
180 item_counter m_ItemCounter; ///< Item counter
181 hash m_HashFunctor; ///< Hash functor
182 stat m_Stat; ///< Internal statistics
186 typedef cds::details::Allocator< dummy_node_type, typename traits::allocator > dummy_node_allocator;
188 dummy_node_type * alloc_dummy_node( size_t nHash )
190 m_Stat.onHeadNodeAllocated();
191 return dummy_node_allocator().New( nHash );
193 void free_dummy_node( dummy_node_type * p )
195 dummy_node_allocator().Delete( p );
196 m_Stat.onHeadNodeFreed();
199 /// Calculates hash value of \p key
200 template <typename Q>
201 size_t hash_value( Q const& key ) const
203 return m_HashFunctor( key );
206 size_t bucket_no( size_t nHash ) const
208 return nHash & ( (1 << m_nBucketCountLog2.load(memory_model::memory_order_relaxed)) - 1 );
211 static size_t parent_bucket( size_t nBucket )
213 assert( nBucket > 0 );
214 return nBucket & ~( 1 << bitop::MSBnz( nBucket ) );
217 dummy_node_type * init_bucket( size_t nBucket )
219 assert( nBucket > 0 );
220 size_t nParent = parent_bucket( nBucket );
222 dummy_node_type * pParentBucket = m_Buckets.bucket( nParent );
223 if ( pParentBucket == nullptr ) {
224 pParentBucket = init_bucket( nParent );
225 m_Stat.onRecursiveInitBucket();
228 assert( pParentBucket != nullptr );
230 // Allocate a dummy node for new bucket
232 dummy_node_type * pBucket = alloc_dummy_node( split_list::dummy_hash( nBucket ) );
233 if ( m_List.insert_aux_node( pParentBucket, pBucket ) ) {
234 m_Buckets.bucket( nBucket, pBucket );
235 m_Stat.onNewBucket();
238 free_dummy_node( pBucket );
241 // Another thread set the bucket. Wait while it done
243 // In this point, we must wait while nBucket is empty.
244 // The compiler can decide that waiting loop can be "optimized" (stripped)
245 // To prevent this situation, we use waiting on volatile bucket_head_ptr pointer.
247 m_Stat.onBucketInitContenton();
250 dummy_node_type volatile * p = m_Buckets.bucket( nBucket );
251 if ( p && p != nullptr )
252 return const_cast<dummy_node_type *>( p );
254 m_Stat.onBusyWaitBucketInit();
258 dummy_node_type * get_bucket( size_t nHash )
260 size_t nBucket = bucket_no( nHash );
262 dummy_node_type * pHead = m_Buckets.bucket( nBucket );
263 if ( pHead == nullptr )
264 pHead = init_bucket( nBucket );
266 assert( pHead->is_dummy() );
273 // GC and OrderedList::gc must be the same
274 static_assert( std::is_same<gc, typename ordered_list::gc>::value, "GC and OrderedList::gc must be the same");
276 // atomicity::empty_item_counter is not allowed as a item counter
277 static_assert( !std::is_same<item_counter, cds::atomicity::empty_item_counter>::value,
278 "cds::atomicity::empty_item_counter is not allowed as a item counter");
280 // Initialize bucket 0
281 dummy_node_type * pNode = alloc_dummy_node( 0 /*split_list::dummy_hash(0)*/ );
283 // insert_aux_node cannot return false for empty list
284 CDS_VERIFY( m_List.insert_aux_node( pNode ));
286 m_Buckets.bucket( 0, pNode );
289 static size_t max_item_count( size_t nBucketCount, size_t nLoadFactor )
291 return nBucketCount * nLoadFactor;
294 void inc_item_count()
296 size_t nMaxCount = m_nMaxItemCount.load(memory_model::memory_order_relaxed);
297 if ( ++m_ItemCounter <= nMaxCount )
300 size_t sz = m_nBucketCountLog2.load(memory_model::memory_order_relaxed);
301 const size_t nBucketCount = static_cast<size_t>(1) << sz;
302 if ( nBucketCount < m_Buckets.capacity() ) {
303 // we may grow the bucket table
304 const size_t nLoadFactor = m_Buckets.load_factor();
305 if ( nMaxCount < max_item_count( nBucketCount, nLoadFactor ))
306 return; // someone already have updated m_nBucketCountLog2, so stop here
308 m_nMaxItemCount.compare_exchange_strong( nMaxCount, max_item_count( nBucketCount << 1, nLoadFactor ),
309 memory_model::memory_order_relaxed, atomics::memory_order_relaxed );
310 m_nBucketCountLog2.compare_exchange_strong( sz, sz + 1, memory_model::memory_order_relaxed, atomics::memory_order_relaxed );
313 m_nMaxItemCount.store( std::numeric_limits<size_t>::max(), memory_model::memory_order_relaxed );
319 /// Initialize split-ordered list of default capacity
321 The default capacity is defined in bucket table constructor.
322 See split_list::expandable_bucket_table, split_list::static_ducket_table
323 which selects by split_list::dynamic_bucket_table option.
326 : m_nBucketCountLog2(1)
327 , m_nMaxItemCount( max_item_count(2, m_Buckets.load_factor()) )
332 /// Initialize split-ordered list
334 size_t nItemCount ///< estimate average of item count
335 , size_t nLoadFactor = 1 ///< load factor - average item count per bucket. Small integer up to 10, default is 1.
337 : m_Buckets( nItemCount, nLoadFactor )
338 , m_nBucketCountLog2(1)
339 , m_nMaxItemCount( max_item_count(2, m_Buckets.load_factor()) )
347 The function inserts \p val in the set if it does not contain
348 an item with key equal to \p val.
350 Returns \p true if \p val is placed into the set, \p false otherwise.
352 bool insert( value_type& val )
354 return insert_( val ) != end();
359 The operation performs inserting or changing data with lock-free manner.
361 If the item \p val is not found in the set, then \p val is inserted
362 iff \p bAllowInsert is \p true.
363 Otherwise, the functor \p func is called with item found.
364 The functor signature is:
366 void func( bool bNew, value_type& item, value_type& val );
369 - \p bNew - \p true if the item has been inserted, \p false otherwise
370 - \p item - item of the set
371 - \p val - argument \p val passed into the \p update() function
372 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
373 refers to the same thing.
375 The functor may change non-key fields of the \p item.
377 Returns std::pair<bool, bool> where \p first is \p true if operation is successful,
378 \p second is \p true if new item has been added or \p false if the item with \p key
379 already is in the list.
381 @warning For \ref cds_intrusive_MichaelList_hp "MichaelList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
382 \ref cds_intrusive_LazyList_hp "LazyList" provides exclusive access to inserted item and does not require any node-level
385 template <typename Func>
386 std::pair<bool, bool> update( value_type& val, Func func, bool bAllowInsert = true )
388 std::pair<iterator, bool> ret = update_( val, func, bAllowInsert );
389 return std::make_pair( ret.first != end(), ret.second );
392 template <typename Func>
393 CDS_DEPRECATED("ensure() is deprecated, use update()")
394 std::pair<bool, bool> ensure( value_type& val, Func func )
396 return update( val, func, true );
400 /// Checks whether the set contains \p key
402 The function searches the item with key equal to \p key
403 and returns \p true if it is found, and \p false otherwise.
405 Note the hash functor specified for class \p Traits template parameter
406 should accept a parameter of type \p Q that can be not the same as \p value_type.
407 Otherwise, you may use \p contains( Q const&, Less pred ) functions with explicit predicate for key comparing.
409 template <typename Q>
410 value_type * contains( Q const& key )
412 iterator it = find_( key );
418 template <typename Q>
419 CDS_DEPRECATED("deprecated, use contains()")
420 value_type * find( Q const& key )
422 return contains( key );
426 /// Checks whether the set contains \p key using \p pred predicate for searching
428 The function is similar to <tt>contains( key )</tt> but \p pred is used for key comparing.
429 \p Less functor has the interface like \p std::less.
430 \p Less must imply the same element order as the comparator used for building the list.
432 template <typename Q, typename Less>
433 value_type * contains( Q const& key, Less pred )
435 iterator it = find_with_( key, pred );
441 template <typename Q, typename Less>
442 CDS_DEPRECATED("deprecated, use contains()")
443 value_type * find_with( Q const& key, Less pred )
445 return contains( key, pred );
449 /// Finds the key \p key
450 /** \anchor cds_intrusive_SplitListSet_nogc_find_func
451 The function searches the item with key equal to \p key and calls the functor \p f for item found.
452 The interface of \p Func functor is:
455 void operator()( value_type& item, Q& key );
458 where \p item is the item found, \p key is the <tt>find</tt> function argument.
460 The functor can change non-key fields of \p item.
461 The functor does not serialize simultaneous access to the set \p item. If such access is
462 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
464 Note the hash functor specified for class \p Traits template parameter
465 should accept a parameter of type \p Q that can be not the same as \p value_type.
467 The function returns \p true if \p key is found, \p false otherwise.
469 template <typename Q, typename Func>
470 bool find( Q& key, Func f )
472 return find_( key, key_comparator(), f );
475 template <typename Q, typename Func>
476 bool find( Q const& key, Func f )
478 return find_( key, key_comparator(), f );
482 /// Finds the key \p key with \p pred predicate for comparing
484 The function is an analog of \ref cds_intrusive_SplitListSet_nogc_find_func "find(Q&, Func)"
485 but \p cmp is used for key compare.
486 \p Less has the interface like \p std::less.
487 \p cmp must imply the same element order as the comparator used for building the set.
489 template <typename Q, typename Less, typename Func>
490 bool find_with( Q& key, Less pred, Func f )
493 return find_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>(), f );
496 template <typename Q, typename Less, typename Func>
497 bool find_with( Q const& key, Less pred, Func f )
500 return find_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>(), f );
505 /// Clears the set (non-atomic, not thread-safe)
507 The function unlink all items from the set.
508 The function is not atomic. It cleans up each bucket and then resets the item counter to zero.
509 If there are a thread that performs insertion while \p %clear() is working the result is undefined in general case:
510 <tt> empty() </tt> may return \p true but the set may contain item(s).
511 Therefore, \p %clear() may be used only for debugging purposes.
513 For each item the \p disposer is called after unlinking.
517 m_List.erase_for( []( value_type const& val ) -> bool { return !node_traits::to_node_ptr( val )->is_dummy(); } );
518 m_ItemCounter.reset();
521 /// Checks if the set is empty
523 Emptiness is checked by item counting: if item count is zero then the set is empty.
524 Thus, the correct item counting feature is an important part of split-list implementation.
531 /// Returns item count in the set
534 return m_ItemCounter;
537 /// Returns internal statistics
538 stat const& statistics() const
545 template <bool IsConst>
547 : public split_list::details::iterator_type<node_traits, ordered_list, IsConst>
549 typedef split_list::details::iterator_type<node_traits, ordered_list, IsConst> iterator_base_class;
550 typedef typename iterator_base_class::list_iterator list_iterator;
553 : iterator_base_class()
556 iterator_type( iterator_type const& src )
557 : iterator_base_class( src )
560 // This ctor should be protected...
561 iterator_type( list_iterator itCur, list_iterator itEnd )
562 : iterator_base_class( itCur, itEnd )
568 ///@name Forward iterators
572 The forward iterator for a split-list has some features:
573 - it has no post-increment operator
574 - it depends on iterator of underlying \p OrderedList
576 typedef iterator_type<false> iterator;
578 /// Const forward iterator
580 For iterator's features and requirements see \ref iterator
582 typedef iterator_type<true> const_iterator;
584 /// Returns a forward iterator addressing the first element in a split-list
586 For empty list \code begin() == end() \endcode
590 return iterator( m_List.begin(), m_List.end() );
593 /// Returns an iterator that addresses the location succeeding the last element in a split-list
595 Do not use the value returned by <tt>end</tt> function to access any item.
597 The returned value can be used only to control reaching the end of the split-list.
598 For empty list \code begin() == end() \endcode
602 return iterator( m_List.end(), m_List.end() );
605 /// Returns a forward const iterator addressing the first element in a split-list
606 const_iterator begin() const
608 return const_iterator( m_List.begin(), m_List.end() );
611 /// Returns a forward const iterator addressing the first element in a split-list
612 const_iterator cbegin() const
614 return const_iterator( m_List.cbegin(), m_List.cend() );
617 /// Returns an const iterator that addresses the location succeeding the last element in a split-list
618 const_iterator end() const
620 return const_iterator( m_List.end(), m_List.end() );
623 /// Returns an const iterator that addresses the location succeeding the last element in a split-list
624 const_iterator cend() const
626 return const_iterator( m_List.cend(), m_List.cend() );
632 iterator insert_( value_type& val )
634 size_t nHash = hash_value( val );
635 dummy_node_type * pHead = get_bucket( nHash );
636 assert( pHead != nullptr );
638 node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
640 list_iterator it = m_List.insert_at_( pHead, val );
641 if ( it != m_List.end() ) {
643 m_Stat.onInsertSuccess();
644 return iterator( it, m_List.end() );
646 m_Stat.onInsertFailed();
650 template <typename Func>
651 std::pair<iterator, bool> update_( value_type& val, Func func, bool bAllowInsert )
653 size_t nHash = hash_value( val );
654 dummy_node_type * pHead = get_bucket( nHash );
655 assert( pHead != nullptr );
657 node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
659 std::pair<list_iterator, bool> ret = m_List.update_at_( pHead, val, func, bAllowInsert );
660 if ( ret.first != m_List.end() ) {
663 m_Stat.onUpdateNew();
666 m_Stat.onUpdateExist();
667 return std::make_pair( iterator(ret.first, m_List.end()), ret.second );
669 return std::make_pair( end(), ret.second );
672 template <typename Q, typename Less >
673 iterator find_with_( Q& val, Less pred )
676 size_t nHash = hash_value( val );
677 split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash( nHash ));
678 dummy_node_type * pHead = get_bucket( nHash );
679 assert( pHead != nullptr );
681 auto it = m_List.find_at_( pHead, sv, typename wrapped_ordered_list::template make_compare_from_less<Less>() );
682 m_Stat.onFind( it != m_List.end() );
683 return iterator( it, m_List.end() );
686 template <typename Q>
687 iterator find_( Q const& val )
689 size_t nHash = hash_value( val );
690 split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash( nHash ));
691 dummy_node_type * pHead = get_bucket( nHash );
692 assert( pHead != nullptr );
694 auto it = m_List.find_at_( pHead, sv, key_comparator() );
695 m_Stat.onFind( it != m_List.end() );
696 return iterator( it, m_List.end() );
699 template <typename Q, typename Compare, typename Func>
700 bool find_( Q& val, Compare cmp, Func f )
702 size_t nHash = hash_value( val );
703 split_list::details::search_value_type<Q> sv( val, split_list::regular_hash( nHash ));
704 dummy_node_type * pHead = get_bucket( nHash );
705 assert( pHead != nullptr );
706 return m_Stat.onFind( m_List.find_at( pHead, sv, cmp,
707 [&f](value_type& item, split_list::details::search_value_type<Q>& val){ f(item, val.val ); }));
713 }} // namespace cds::intrusive
715 #endif // #ifndef CDSLIB_INTRUSIVE_SPLIT_LIST_NOGC_H