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 );
170 ordered_list_wrapper m_List; ///< Ordered list containing split-list items
171 bucket_table m_Buckets; ///< bucket table
172 atomics::atomic<size_t> m_nBucketCountLog2; ///< log2( current bucket count )
173 atomics::atomic<size_t> m_nMaxItemCount; ///< number of items container can hold, before we have to resize
174 item_counter m_ItemCounter; ///< Item counter
175 hash m_HashFunctor; ///< Hash functor
176 stat m_Stat; ///< Internal statistics
180 typedef cds::details::Allocator< dummy_node_type, typename traits::allocator > dummy_node_allocator;
182 dummy_node_type * alloc_dummy_node( size_t nHash )
184 m_Stat.onHeadNodeAllocated();
185 return dummy_node_allocator().New( nHash );
187 void free_dummy_node( dummy_node_type * p )
189 dummy_node_allocator().Delete( p );
190 m_Stat.onHeadNodeFreed();
193 /// Calculates hash value of \p key
194 template <typename Q>
195 size_t hash_value( Q const& key ) const
197 return m_HashFunctor( key );
200 size_t bucket_no( size_t nHash ) const
202 return nHash & ( (1 << m_nBucketCountLog2.load(memory_model::memory_order_relaxed)) - 1 );
205 static size_t parent_bucket( size_t nBucket )
207 assert( nBucket > 0 );
208 return nBucket & ~( 1 << bitop::MSBnz( nBucket ) );
211 dummy_node_type * init_bucket( size_t nBucket )
213 assert( nBucket > 0 );
214 size_t nParent = parent_bucket( nBucket );
216 dummy_node_type * pParentBucket = m_Buckets.bucket( nParent );
217 if ( pParentBucket == nullptr ) {
218 pParentBucket = init_bucket( nParent );
219 m_Stat.onRecursiveInitBucket();
222 assert( pParentBucket != nullptr );
224 // Allocate a dummy node for new bucket
226 dummy_node_type * pBucket = alloc_dummy_node( split_list::dummy_hash( nBucket ) );
227 if ( m_List.insert_aux_node( pParentBucket, pBucket ) ) {
228 m_Buckets.bucket( nBucket, pBucket );
229 m_Stat.onNewBucket();
232 free_dummy_node( pBucket );
235 // Another thread set the bucket. Wait while it done
237 // In this point, we must wait while nBucket is empty.
238 // The compiler can decide that waiting loop can be "optimized" (stripped)
239 // To prevent this situation, we use waiting on volatile bucket_head_ptr pointer.
241 m_Stat.onBucketInitContenton();
244 dummy_node_type volatile * p = m_Buckets.bucket( nBucket );
245 if ( p && p != nullptr )
246 return const_cast<dummy_node_type *>( p );
248 m_Stat.onBusyWaitBucketInit();
252 dummy_node_type * get_bucket( size_t nHash )
254 size_t nBucket = bucket_no( nHash );
256 dummy_node_type * pHead = m_Buckets.bucket( nBucket );
257 if ( pHead == nullptr )
258 pHead = init_bucket( nBucket );
260 assert( pHead->is_dummy() );
267 // GC and OrderedList::gc must be the same
268 static_assert( std::is_same<gc, typename ordered_list::gc>::value, "GC and OrderedList::gc must be the same");
270 // atomicity::empty_item_counter is not allowed as a item counter
271 static_assert( !std::is_same<item_counter, cds::atomicity::empty_item_counter>::value,
272 "cds::atomicity::empty_item_counter is not allowed as a item counter");
274 // Initialize bucket 0
275 dummy_node_type * pNode = alloc_dummy_node( 0 /*split_list::dummy_hash(0)*/ );
277 // insert_aux_node cannot return false for empty list
278 CDS_VERIFY( m_List.insert_aux_node( pNode ));
280 m_Buckets.bucket( 0, pNode );
283 static size_t max_item_count( size_t nBucketCount, size_t nLoadFactor )
285 return nBucketCount * nLoadFactor;
288 void inc_item_count()
290 size_t nMaxCount = m_nMaxItemCount.load(memory_model::memory_order_relaxed);
291 if ( ++m_ItemCounter <= nMaxCount )
294 size_t sz = m_nBucketCountLog2.load(memory_model::memory_order_relaxed);
295 const size_t nBucketCount = static_cast<size_t>(1) << sz;
296 if ( nBucketCount < m_Buckets.capacity() ) {
297 // we may grow the bucket table
298 const size_t nLoadFactor = m_Buckets.load_factor();
299 if ( nMaxCount < max_item_count( nBucketCount, nLoadFactor ))
300 return; // someone already have updated m_nBucketCountLog2, so stop here
302 m_nMaxItemCount.compare_exchange_strong( nMaxCount, max_item_count( nBucketCount << 1, nLoadFactor ),
303 memory_model::memory_order_relaxed, atomics::memory_order_relaxed );
304 m_nBucketCountLog2.compare_exchange_strong( sz, sz + 1, memory_model::memory_order_relaxed, atomics::memory_order_relaxed );
307 m_nMaxItemCount.store( std::numeric_limits<size_t>::max(), memory_model::memory_order_relaxed );
313 /// Initialize split-ordered list of default capacity
315 The default capacity is defined in bucket table constructor.
316 See split_list::expandable_bucket_table, split_list::static_ducket_table
317 which selects by split_list::dynamic_bucket_table option.
320 : m_nBucketCountLog2(1)
321 , m_nMaxItemCount( max_item_count(2, m_Buckets.load_factor()) )
326 /// Initialize split-ordered list
328 size_t nItemCount ///< estimate average of item count
329 , size_t nLoadFactor = 1 ///< load factor - average item count per bucket. Small integer up to 10, default is 1.
331 : m_Buckets( nItemCount, nLoadFactor )
332 , m_nBucketCountLog2(1)
333 , m_nMaxItemCount( max_item_count(2, m_Buckets.load_factor()) )
341 The function inserts \p val in the set if it does not contain
342 an item with key equal to \p val.
344 Returns \p true if \p val is placed into the set, \p false otherwise.
346 bool insert( value_type& val )
348 return insert_( val ) != end();
353 The operation performs inserting or changing data with lock-free manner.
355 If the item \p val is not found in the set, then \p val is inserted
356 iff \p bAllowInsert is \p true.
357 Otherwise, the functor \p func is called with item found.
358 The functor signature is:
360 void func( bool bNew, value_type& item, value_type& val );
363 - \p bNew - \p true if the item has been inserted, \p false otherwise
364 - \p item - item of the set
365 - \p val - argument \p val passed into the \p update() function
366 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
367 refers to the same thing.
369 The functor may change non-key fields of the \p item.
371 Returns std::pair<bool, bool> where \p first is \p true if operation is successfull,
372 \p second is \p true if new item has been added or \p false if the item with \p key
373 already is in the list.
375 @warning For \ref cds_intrusive_MichaelList_hp "MichaelList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
376 \ref cds_intrusive_LazyList_hp "LazyList" provides exclusive access to inserted item and does not require any node-level
379 template <typename Func>
380 std::pair<bool, bool> update( value_type& val, Func func, bool bAllowInsert = true )
382 std::pair<iterator, bool> ret = update_( val, func, bAllowInsert );
383 return std::make_pair( ret.first != end(), ret.second );
386 template <typename Func>
387 CDS_DEPRECATED("ensure() is deprecated, use update()")
388 std::pair<bool, bool> ensure( value_type& val, Func func )
390 return update( val, func, true );
394 /// Checks whether the set contains \p key
396 The function searches the item with key equal to \p key
397 and returns \p true if it is found, and \p false otherwise.
399 Note the hash functor specified for class \p Traits template parameter
400 should accept a parameter of type \p Q that can be not the same as \p value_type.
401 Otherwise, you may use \p contains( Q const&, Less pred ) functions with explicit predicate for key comparing.
403 template <typename Q>
404 value_type * contains( Q const& key )
406 iterator it = find_( key );
412 template <typename Q>
413 CDS_DEPRECATED("deprecated, use contains()")
414 value_type * find( Q const& key )
416 return contains( key );
420 /// Checks whether the set contains \p key using \p pred predicate for searching
422 The function is similar to <tt>contains( key )</tt> but \p pred is used for key comparing.
423 \p Less functor has the interface like \p std::less.
424 \p Less must imply the same element order as the comparator used for building the list.
426 template <typename Q, typename Less>
427 value_type * contains( Q const& key, Less pred )
429 iterator it = find_with_( key, pred );
435 template <typename Q, typename Less>
436 CDS_DEPRECATED("deprecated, use contains()")
437 value_type * find_with( Q const& key, Less pred )
439 return contains( key, pred );
443 /// Finds the key \p key
444 /** \anchor cds_intrusive_SplitListSet_nogc_find_func
445 The function searches the item with key equal to \p key and calls the functor \p f for item found.
446 The interface of \p Func functor is:
449 void operator()( value_type& item, Q& key );
452 where \p item is the item found, \p key is the <tt>find</tt> function argument.
454 The functor can change non-key fields of \p item.
455 The functor does not serialize simultaneous access to the set \p item. If such access is
456 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
458 Note the hash functor specified for class \p Traits template parameter
459 should accept a parameter of type \p Q that can be not the same as \p value_type.
461 The function returns \p true if \p key is found, \p false otherwise.
463 template <typename Q, typename Func>
464 bool find( Q& key, Func f )
466 return find_( key, key_comparator(), f );
469 template <typename Q, typename Func>
470 bool find( Q const& key, Func f )
472 return find_( key, key_comparator(), f );
476 /// Finds the key \p key with \p pred predicate for comparing
478 The function is an analog of \ref cds_intrusive_SplitListSet_nogc_find_func "find(Q&, Func)"
479 but \p cmp is used for key compare.
480 \p Less has the interface like \p std::less.
481 \p cmp must imply the same element order as the comparator used for building the set.
483 template <typename Q, typename Less, typename Func>
484 bool find_with( Q& key, Less pred, Func f )
487 return find_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>(), f );
490 template <typename Q, typename Less, typename Func>
491 bool find_with( Q const& key, Less pred, Func f )
494 return find_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>(), f );
498 /// Checks if the set is empty
500 Emptiness is checked by item counting: if item count is zero then the set is empty.
501 Thus, the correct item counting feature is an important part of split-list implementation.
508 /// Returns item count in the set
511 return m_ItemCounter;
514 /// Returns internal statistics
515 stat const& statistics() const
522 template <bool IsConst>
524 : public split_list::details::iterator_type<node_traits, ordered_list, IsConst>
526 typedef split_list::details::iterator_type<node_traits, ordered_list, IsConst> iterator_base_class;
527 typedef typename iterator_base_class::list_iterator list_iterator;
530 : iterator_base_class()
533 iterator_type( iterator_type const& src )
534 : iterator_base_class( src )
537 // This ctor should be protected...
538 iterator_type( list_iterator itCur, list_iterator itEnd )
539 : iterator_base_class( itCur, itEnd )
547 The forward iterator for a split-list has some features:
548 - it has no post-increment operator
549 - it depends on iterator of underlying \p OrderedList
551 typedef iterator_type<false> iterator;
552 /// Const forward iterator
554 For iterator's features and requirements see \ref iterator
556 typedef iterator_type<true> const_iterator;
558 /// Returns a forward iterator addressing the first element in a split-list
560 For empty list \code begin() == end() \endcode
564 return iterator( m_List.begin(), m_List.end() );
567 /// Returns an iterator that addresses the location succeeding the last element in a split-list
569 Do not use the value returned by <tt>end</tt> function to access any item.
571 The returned value can be used only to control reaching the end of the split-list.
572 For empty list \code begin() == end() \endcode
576 return iterator( m_List.end(), m_List.end() );
579 /// Returns a forward const iterator addressing the first element in a split-list
581 const_iterator begin() const
583 return const_iterator( m_List.begin(), m_List.end() );
585 const_iterator cbegin() const
587 return const_iterator( m_List.cbegin(), m_List.cend() );
591 /// Returns an const iterator that addresses the location succeeding the last element in a split-list
593 const_iterator end() const
595 return const_iterator( m_List.end(), m_List.end() );
597 const_iterator cend() const
599 return const_iterator( m_List.cend(), m_List.cend() );
605 iterator insert_( value_type& val )
607 size_t nHash = hash_value( val );
608 dummy_node_type * pHead = get_bucket( nHash );
609 assert( pHead != nullptr );
611 node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
613 list_iterator it = m_List.insert_at_( pHead, val );
614 if ( it != m_List.end() ) {
616 m_Stat.onInsertSuccess();
617 return iterator( it, m_List.end() );
619 m_Stat.onInsertFailed();
623 template <typename Func>
624 std::pair<iterator, bool> update_( value_type& val, Func func, bool bAllowInsert )
626 size_t nHash = hash_value( val );
627 dummy_node_type * pHead = get_bucket( nHash );
628 assert( pHead != nullptr );
630 node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
632 std::pair<list_iterator, bool> ret = m_List.update_at_( pHead, val, func, bAllowInsert );
633 if ( ret.first != m_List.end() ) {
636 m_Stat.onEnsureNew();
639 m_Stat.onEnsureExist();
640 return std::make_pair( iterator(ret.first, m_List.end()), ret.second );
642 return std::make_pair( end(), ret.second );
645 template <typename Q, typename Less >
646 iterator find_with_( Q& val, Less pred )
649 size_t nHash = hash_value( val );
650 split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash( nHash ));
651 dummy_node_type * pHead = get_bucket( nHash );
652 assert( pHead != nullptr );
654 auto it = m_List.find_at_( pHead, sv, typename wrapped_ordered_list::template make_compare_from_less<Less>() );
655 m_Stat.onFind( it != m_List.end() );
656 return iterator( it, m_List.end() );
659 template <typename Q>
660 iterator find_( Q const& val )
662 size_t nHash = hash_value( val );
663 split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash( nHash ));
664 dummy_node_type * pHead = get_bucket( nHash );
665 assert( pHead != nullptr );
667 auto it = m_List.find_at_( pHead, sv, key_comparator() );
668 m_Stat.onFind( it != m_List.end() );
669 return iterator( it, m_List.end() );
672 template <typename Q, typename Compare, typename Func>
673 bool find_( Q& val, Compare cmp, Func f )
675 size_t nHash = hash_value( val );
676 split_list::details::search_value_type<Q> sv( val, split_list::regular_hash( nHash ));
677 dummy_node_type * pHead = get_bucket( nHash );
678 assert( pHead != nullptr );
679 return m_Stat.onFind( m_List.find_at( pHead, sv, cmp,
680 [&f](value_type& item, split_list::details::search_value_type<Q>& val){ f(item, val.val ); }));
686 }} // namespace cds::intrusive
688 #endif // #ifndef CDSLIB_INTRUSIVE_SPLIT_LIST_NOGC_H