3 #ifndef CDSLIB_INTRUSIVE_SPLIT_LIST_NOGC_H
4 #define CDSLIB_INTRUSIVE_SPLIT_LIST_NOGC_H
8 #include <cds/intrusive/details/split_list_base.h>
9 #include <cds/gc/nogc.h>
11 namespace cds { namespace intrusive {
13 /// Split-ordered list (template specialization for gc::nogc)
14 /** @ingroup cds_intrusive_map
15 \anchor cds_intrusive_SplitListSet_nogc
17 This specialization is intended for so-called persistent usage when no item
18 reclamation may be performed. The class does not support deleting of list item.
20 See \ref cds_intrusive_SplitListSet_hp "SplitListSet" for description of template parameters.
21 The template parameter \p OrderedList should be any gc::nogc-derived ordered list, for example,
22 \ref cds_intrusive_MichaelList_nogc "persistent MichaelList",
23 \ref cds_intrusive_LazyList_nogc "persistent LazyList"
27 #ifdef CDS_DOXYGEN_INVOKED
28 class Traits = split_list::traits
33 class SplitListSet< cds::gc::nogc, OrderedList, Traits >
36 typedef cds::gc::nogc gc; ///< Garbage collector
37 typedef Traits traits; ///< Traits template parameters
39 /// Hash functor for \p value_type and all its derivatives that you use
40 typedef typename cds::opt::v::hash_selector< typename traits::hash >::type hash;
44 typedef split_list::details::rebind_list_traits<OrderedList, traits> wrapped_ordered_list;
48 # ifdef CDS_DOXYGEN_INVOKED
49 typedef OrderedList ordered_list; ///< type of ordered list used as base for split-list
51 typedef typename wrapped_ordered_list::result ordered_list;
53 typedef typename ordered_list::value_type value_type; ///< type of value stored in the split-list
54 typedef typename ordered_list::key_comparator key_comparator; ///< key comparison functor
55 typedef typename ordered_list::disposer disposer; ///< Node disposer functor
57 typedef typename traits::item_counter item_counter; ///< Item counter type
58 typedef typename traits::back_off back_off; ///< back-off strategy
59 typedef typename traits::memory_model memory_model; ///< Memory ordering. See cds::opt::memory_model option
60 typedef typename traits::stat stat; ///< Internal statistics, see \p spit_list::stat
63 typedef typename ordered_list::node_type list_node_type; ///< Node type as declared in ordered list
64 typedef split_list::node<list_node_type> node_type; ///< split-list node type
65 typedef node_type dummy_node_type; ///< dummy node type
67 /// Split-list node traits
69 This traits is intended for converting between underlying ordered list node type \ref list_node_type
70 and split-list node type \ref node_type
72 typedef split_list::node_traits<typename ordered_list::node_traits> node_traits;
75 /// Bucket table implementation
76 typedef typename split_list::details::bucket_table_selector<
77 traits::dynamic_bucket_table
80 , opt::allocator< typename traits::allocator >
81 , opt::memory_model< memory_model >
84 typedef typename ordered_list::iterator list_iterator;
85 typedef typename ordered_list::const_iterator list_const_iterator;
90 /// Ordered list wrapper to access protected members
91 class ordered_list_wrapper: public ordered_list
93 typedef ordered_list base_class;
94 typedef typename base_class::auxiliary_head bucket_head_type;
97 list_iterator insert_at_( dummy_node_type * pHead, value_type& val )
99 assert( pHead != nullptr );
100 bucket_head_type h(static_cast<list_node_type *>(pHead));
101 return base_class::insert_at_( h, val );
104 template <typename Func>
105 std::pair<list_iterator, bool> update_at_( dummy_node_type * pHead, value_type& val, Func func, bool bAllowInsert )
107 assert( pHead != nullptr );
108 bucket_head_type h(static_cast<list_node_type *>(pHead));
109 return base_class::update_at_( h, val, func, bAllowInsert );
112 template <typename Q, typename Compare, typename Func>
113 bool find_at( dummy_node_type * pHead, split_list::details::search_value_type<Q>& val, Compare cmp, Func f )
115 assert( pHead != nullptr );
116 bucket_head_type h(static_cast<list_node_type *>(pHead));
117 return base_class::find_at( h, val, cmp, f );
120 template <typename Q, typename Compare>
121 list_iterator find_at_( dummy_node_type * pHead, split_list::details::search_value_type<Q> const & val, Compare cmp )
123 assert( pHead != nullptr );
124 bucket_head_type h(static_cast<list_node_type *>(pHead));
125 return base_class::find_at_( h, val, cmp );
128 bool insert_aux_node( dummy_node_type * pNode )
130 return base_class::insert_aux_node( pNode );
132 bool insert_aux_node( dummy_node_type * pHead, dummy_node_type * pNode )
134 bucket_head_type h(static_cast<list_node_type *>(pHead));
135 return base_class::insert_aux_node( h, pNode );
142 ordered_list_wrapper m_List; ///< Ordered list containing split-list items
143 bucket_table m_Buckets; ///< bucket table
144 atomics::atomic<size_t> m_nBucketCountLog2; ///< log2( current bucket count )
145 atomics::atomic<size_t> m_nMaxItemCount; ///< number of items container can hold, before we have to resize
146 item_counter m_ItemCounter; ///< Item counter
147 hash m_HashFunctor; ///< Hash functor
148 stat m_Stat; ///< Internal statistics
152 typedef cds::details::Allocator< dummy_node_type, typename traits::allocator > dummy_node_allocator;
154 dummy_node_type * alloc_dummy_node( size_t nHash )
156 m_Stat.onHeadNodeAllocated();
157 return dummy_node_allocator().New( nHash );
159 void free_dummy_node( dummy_node_type * p )
161 dummy_node_allocator().Delete( p );
162 m_Stat.onHeadNodeFreed();
165 /// Calculates hash value of \p key
166 template <typename Q>
167 size_t hash_value( Q const& key ) const
169 return m_HashFunctor( key );
172 size_t bucket_no( size_t nHash ) const
174 return nHash & ( (1 << m_nBucketCountLog2.load(memory_model::memory_order_relaxed)) - 1 );
177 static size_t parent_bucket( size_t nBucket )
179 assert( nBucket > 0 );
180 return nBucket & ~( 1 << bitop::MSBnz( nBucket ) );
183 dummy_node_type * init_bucket( size_t nBucket )
185 assert( nBucket > 0 );
186 size_t nParent = parent_bucket( nBucket );
188 dummy_node_type * pParentBucket = m_Buckets.bucket( nParent );
189 if ( pParentBucket == nullptr ) {
190 pParentBucket = init_bucket( nParent );
191 m_Stat.onRecursiveInitBucket();
194 assert( pParentBucket != nullptr );
196 // Allocate a dummy node for new bucket
198 dummy_node_type * pBucket = alloc_dummy_node( split_list::dummy_hash( nBucket ) );
199 if ( m_List.insert_aux_node( pParentBucket, pBucket ) ) {
200 m_Buckets.bucket( nBucket, pBucket );
201 m_Stat.onNewBucket();
204 free_dummy_node( pBucket );
207 // Another thread set the bucket. Wait while it done
209 // In this point, we must wait while nBucket is empty.
210 // The compiler can decide that waiting loop can be "optimized" (stripped)
211 // To prevent this situation, we use waiting on volatile bucket_head_ptr pointer.
213 m_Stat.onBucketInitContenton();
216 dummy_node_type volatile * p = m_Buckets.bucket( nBucket );
217 if ( p && p != nullptr )
218 return const_cast<dummy_node_type *>( p );
220 m_Stat.onBusyWaitBucketInit();
224 dummy_node_type * get_bucket( size_t nHash )
226 size_t nBucket = bucket_no( nHash );
228 dummy_node_type * pHead = m_Buckets.bucket( nBucket );
229 if ( pHead == nullptr )
230 pHead = init_bucket( nBucket );
232 assert( pHead->is_dummy() );
239 // GC and OrderedList::gc must be the same
240 static_assert( std::is_same<gc, typename ordered_list::gc>::value, "GC and OrderedList::gc must be the same");
242 // atomicity::empty_item_counter is not allowed as a item counter
243 static_assert( !std::is_same<item_counter, cds::atomicity::empty_item_counter>::value,
244 "cds::atomicity::empty_item_counter is not allowed as a item counter");
246 // Initialize bucket 0
247 dummy_node_type * pNode = alloc_dummy_node( 0 /*split_list::dummy_hash(0)*/ );
249 // insert_aux_node cannot return false for empty list
250 CDS_VERIFY( m_List.insert_aux_node( pNode ));
252 m_Buckets.bucket( 0, pNode );
255 static size_t max_item_count( size_t nBucketCount, size_t nLoadFactor )
257 return nBucketCount * nLoadFactor;
260 void inc_item_count()
262 size_t nMaxCount = m_nMaxItemCount.load(memory_model::memory_order_relaxed);
263 if ( ++m_ItemCounter <= nMaxCount )
266 size_t sz = m_nBucketCountLog2.load(memory_model::memory_order_relaxed);
267 const size_t nBucketCount = static_cast<size_t>(1) << sz;
268 if ( nBucketCount < m_Buckets.capacity() ) {
269 // we may grow the bucket table
270 const size_t nLoadFactor = m_Buckets.load_factor();
271 if ( nMaxCount < max_item_count( nBucketCount, nLoadFactor ))
272 return; // someone already have updated m_nBucketCountLog2, so stop here
274 m_nMaxItemCount.compare_exchange_strong( nMaxCount, max_item_count( nBucketCount << 1, nLoadFactor ),
275 memory_model::memory_order_relaxed, atomics::memory_order_relaxed );
276 m_nBucketCountLog2.compare_exchange_strong( sz, sz + 1, memory_model::memory_order_relaxed, atomics::memory_order_relaxed );
279 m_nMaxItemCount.store( std::numeric_limits<size_t>::max(), memory_model::memory_order_relaxed );
285 /// Initialize split-ordered list of default capacity
287 The default capacity is defined in bucket table constructor.
288 See split_list::expandable_bucket_table, split_list::static_ducket_table
289 which selects by split_list::dynamic_bucket_table option.
292 : m_nBucketCountLog2(1)
293 , m_nMaxItemCount( max_item_count(2, m_Buckets.load_factor()) )
298 /// Initialize split-ordered list
300 size_t nItemCount ///< estimate average of item count
301 , size_t nLoadFactor = 1 ///< load factor - average item count per bucket. Small integer up to 10, default is 1.
303 : m_Buckets( nItemCount, nLoadFactor )
304 , m_nBucketCountLog2(1)
305 , m_nMaxItemCount( max_item_count(2, m_Buckets.load_factor()) )
313 The function inserts \p val in the set if it does not contain
314 an item with key equal to \p val.
316 Returns \p true if \p val is placed into the set, \p false otherwise.
318 bool insert( value_type& val )
320 return insert_( val ) != end();
325 The operation performs inserting or changing data with lock-free manner.
327 If the item \p val is not found in the set, then \p val is inserted
328 iff \p bAllowInsert is \p true.
329 Otherwise, the functor \p func is called with item found.
330 The functor signature is:
332 void func( bool bNew, value_type& item, value_type& val );
335 - \p bNew - \p true if the item has been inserted, \p false otherwise
336 - \p item - item of the set
337 - \p val - argument \p val passed into the \p update() function
338 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
339 refers to the same thing.
341 The functor may change non-key fields of the \p item.
343 Returns std::pair<bool, bool> where \p first is \p true if operation is successfull,
344 \p second is \p true if new item has been added or \p false if the item with \p key
345 already is in the list.
347 @warning For \ref cds_intrusive_MichaelList_hp "MichaelList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
348 \ref cds_intrusive_LazyList_hp "LazyList" provides exclusive access to inserted item and does not require any node-level
351 template <typename Func>
352 std::pair<bool, bool> update( value_type& val, Func func, bool bAllowInsert = true )
354 std::pair<iterator, bool> ret = update_( val, func, bAllowInsert );
355 return std::make_pair( ret.first != end(), ret.second );
358 template <typename Func>
359 CDS_DEPRECATED("ensure() is deprecated, use update()")
360 std::pair<bool, bool> ensure( value_type& val, Func func )
362 return update( val, func, true );
366 /// Checks whether the set contains \p key
368 The function searches the item with key equal to \p key
369 and returns \p true if it is found, and \p false otherwise.
371 Note the hash functor specified for class \p Traits template parameter
372 should accept a parameter of type \p Q that can be not the same as \p value_type.
373 Otherwise, you may use \p contains( Q const&, Less pred ) functions with explicit predicate for key comparing.
375 template <typename Q>
376 value_type * contains( Q const& key )
378 iterator it = find_( key );
384 template <typename Q>
385 CDS_DEPRECATED("deprecated, use contains()")
386 value_type * find( Q const& key )
388 return contains( key );
392 /// Checks whether the set contains \p key using \p pred predicate for searching
394 The function is similar to <tt>contains( key )</tt> but \p pred is used for key comparing.
395 \p Less functor has the interface like \p std::less.
396 \p Less must imply the same element order as the comparator used for building the list.
398 template <typename Q, typename Less>
399 value_type * contains( Q const& key, Less pred )
401 iterator it = find_with_( key, pred );
407 template <typename Q, typename Less>
408 CDS_DEPRECATED("deprecated, use contains()")
409 value_type * find_with( Q const& key, Less pred )
411 return contains( key, pred );
415 /// Finds the key \p key
416 /** \anchor cds_intrusive_SplitListSet_nogc_find_func
417 The function searches the item with key equal to \p key and calls the functor \p f for item found.
418 The interface of \p Func functor is:
421 void operator()( value_type& item, Q& key );
424 where \p item is the item found, \p key is the <tt>find</tt> function argument.
426 The functor can change non-key fields of \p item.
427 The functor does not serialize simultaneous access to the set \p item. If such access is
428 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
430 Note the hash functor specified for class \p Traits template parameter
431 should accept a parameter of type \p Q that can be not the same as \p value_type.
433 The function returns \p true if \p key is found, \p false otherwise.
435 template <typename Q, typename Func>
436 bool find( Q& key, Func f )
438 return find_( key, key_comparator(), f );
441 template <typename Q, typename Func>
442 bool find( Q const& key, Func f )
444 return find_( key, key_comparator(), f );
448 /// Finds the key \p key with \p pred predicate for comparing
450 The function is an analog of \ref cds_intrusive_SplitListSet_nogc_find_func "find(Q&, Func)"
451 but \p cmp is used for key compare.
452 \p Less has the interface like \p std::less.
453 \p cmp must imply the same element order as the comparator used for building the set.
455 template <typename Q, typename Less, typename Func>
456 bool find_with( Q& key, Less pred, Func f )
459 return find_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>(), f );
462 template <typename Q, typename Less, typename Func>
463 bool find_with( Q const& key, Less pred, Func f )
466 return find_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>(), f );
470 /// Checks if the set is empty
472 Emptiness is checked by item counting: if item count is zero then the set is empty.
473 Thus, the correct item counting feature is an important part of split-list implementation.
480 /// Returns item count in the set
483 return m_ItemCounter;
486 /// Returns internal statistics
487 stat const& statistics() const
494 template <bool IsConst>
496 : public split_list::details::iterator_type<node_traits, ordered_list, IsConst>
498 typedef split_list::details::iterator_type<node_traits, ordered_list, IsConst> iterator_base_class;
499 typedef typename iterator_base_class::list_iterator list_iterator;
502 : iterator_base_class()
505 iterator_type( iterator_type const& src )
506 : iterator_base_class( src )
509 // This ctor should be protected...
510 iterator_type( list_iterator itCur, list_iterator itEnd )
511 : iterator_base_class( itCur, itEnd )
519 The forward iterator for a split-list has some features:
520 - it has no post-increment operator
521 - it depends on iterator of underlying \p OrderedList
523 typedef iterator_type<false> iterator;
524 /// Const forward iterator
526 For iterator's features and requirements see \ref iterator
528 typedef iterator_type<true> const_iterator;
530 /// Returns a forward iterator addressing the first element in a split-list
532 For empty list \code begin() == end() \endcode
536 return iterator( m_List.begin(), m_List.end() );
539 /// Returns an iterator that addresses the location succeeding the last element in a split-list
541 Do not use the value returned by <tt>end</tt> function to access any item.
543 The returned value can be used only to control reaching the end of the split-list.
544 For empty list \code begin() == end() \endcode
548 return iterator( m_List.end(), m_List.end() );
551 /// Returns a forward const iterator addressing the first element in a split-list
553 const_iterator begin() const
555 return const_iterator( m_List.begin(), m_List.end() );
557 const_iterator cbegin() const
559 return const_iterator( m_List.cbegin(), m_List.cend() );
563 /// Returns an const iterator that addresses the location succeeding the last element in a split-list
565 const_iterator end() const
567 return const_iterator( m_List.end(), m_List.end() );
569 const_iterator cend() const
571 return const_iterator( m_List.cend(), m_List.cend() );
577 iterator insert_( value_type& val )
579 size_t nHash = hash_value( val );
580 dummy_node_type * pHead = get_bucket( nHash );
581 assert( pHead != nullptr );
583 node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
585 list_iterator it = m_List.insert_at_( pHead, val );
586 if ( it != m_List.end() ) {
588 m_Stat.onInsertSuccess();
589 return iterator( it, m_List.end() );
591 m_Stat.onInsertFailed();
595 template <typename Func>
596 std::pair<iterator, bool> update_( value_type& val, Func func, bool bAllowInsert )
598 size_t nHash = hash_value( val );
599 dummy_node_type * pHead = get_bucket( nHash );
600 assert( pHead != nullptr );
602 node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
604 std::pair<list_iterator, bool> ret = m_List.update_at_( pHead, val, func, bAllowInsert );
605 if ( ret.first != m_List.end() ) {
608 m_Stat.onEnsureNew();
611 m_Stat.onEnsureExist();
612 return std::make_pair( iterator(ret.first, m_List.end()), ret.second );
614 return std::make_pair( end(), ret.second );
617 template <typename Q, typename Less >
618 iterator find_with_( Q& val, Less pred )
621 size_t nHash = hash_value( val );
622 split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash( nHash ));
623 dummy_node_type * pHead = get_bucket( nHash );
624 assert( pHead != nullptr );
626 auto it = m_List.find_at_( pHead, sv, typename wrapped_ordered_list::template make_compare_from_less<Less>() );
627 m_Stat.onFind( it != m_List.end() );
628 return iterator( it, m_List.end() );
631 template <typename Q>
632 iterator find_( Q const& val )
634 size_t nHash = hash_value( val );
635 split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash( nHash ));
636 dummy_node_type * pHead = get_bucket( nHash );
637 assert( pHead != nullptr );
639 auto it = m_List.find_at_( pHead, sv, key_comparator() );
640 m_Stat.onFind( it != m_List.end() );
641 return iterator( it, m_List.end() );
644 template <typename Q, typename Compare, typename Func>
645 bool find_( Q& val, Compare cmp, Func f )
647 size_t nHash = hash_value( val );
648 split_list::details::search_value_type<Q> sv( val, split_list::regular_hash( nHash ));
649 dummy_node_type * pHead = get_bucket( nHash );
650 assert( pHead != nullptr );
651 return m_Stat.onFind( m_List.find_at( pHead, sv, cmp,
652 [&f](value_type& item, split_list::details::search_value_type<Q>& val){ f(item, val.val ); }));
658 }} // namespace cds::intrusive
660 #endif // #ifndef CDSLIB_INTRUSIVE_SPLIT_LIST_NOGC_H