3 #ifndef CDSLIB_INTRUSIVE_SPLIT_LIST_NOGC_H
4 #define CDSLIB_INTRUSIVE_SPLIT_LIST_NOGC_H
6 #include <cds/intrusive/details/split_list_base.h>
7 #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;
43 typedef cds::intrusive::split_list::implementation_tag implementation_tag;
48 typedef split_list::details::rebind_list_traits<OrderedList, traits> wrapped_ordered_list;
52 # ifdef CDS_DOXYGEN_INVOKED
53 typedef OrderedList ordered_list; ///< type of ordered list used as base for split-list
55 typedef typename wrapped_ordered_list::result ordered_list;
57 typedef typename ordered_list::value_type value_type; ///< type of value stored in the split-list
58 typedef typename ordered_list::key_comparator key_comparator; ///< key comparison functor
59 typedef typename ordered_list::disposer disposer; ///< Node disposer functor
61 typedef typename traits::item_counter item_counter; ///< Item counter type
62 typedef typename traits::back_off back_off; ///< back-off strategy
63 typedef typename traits::memory_model memory_model; ///< Memory ordering. See cds::opt::memory_model option
64 typedef typename traits::stat stat; ///< Internal statistics, see \p spit_list::stat
67 typedef typename ordered_list::node_type list_node_type; ///< Node type as declared in ordered list
68 typedef split_list::node<list_node_type> node_type; ///< split-list node type
69 typedef node_type dummy_node_type; ///< dummy node type
71 /// Split-list node traits
73 This traits is intended for converting between underlying ordered list node type \ref list_node_type
74 and split-list node type \ref node_type
76 typedef split_list::node_traits<typename ordered_list::node_traits> node_traits;
79 /// Bucket table implementation
80 typedef typename split_list::details::bucket_table_selector<
81 traits::dynamic_bucket_table
84 , opt::allocator< typename traits::allocator >
85 , opt::memory_model< memory_model >
88 typedef typename ordered_list::iterator list_iterator;
89 typedef typename ordered_list::const_iterator list_const_iterator;
94 /// Ordered list wrapper to access protected members
95 class ordered_list_wrapper: public ordered_list
97 typedef ordered_list base_class;
98 typedef typename base_class::auxiliary_head bucket_head_type;
101 list_iterator insert_at_( dummy_node_type * pHead, value_type& val )
103 assert( pHead != nullptr );
104 bucket_head_type h(static_cast<list_node_type *>(pHead));
105 return base_class::insert_at_( h, val );
108 template <typename Func>
109 std::pair<list_iterator, bool> ensure_at_( dummy_node_type * pHead, value_type& val, Func func )
111 assert( pHead != nullptr );
112 bucket_head_type h(static_cast<list_node_type *>(pHead));
113 return base_class::ensure_at_( h, val, func );
116 template <typename Q, typename Compare, typename Func>
117 bool find_at( dummy_node_type * pHead, split_list::details::search_value_type<Q>& val, Compare cmp, Func f )
119 assert( pHead != nullptr );
120 bucket_head_type h(static_cast<list_node_type *>(pHead));
121 return base_class::find_at( h, val, cmp, f );
124 template <typename Q, typename Compare>
125 list_iterator find_at_( dummy_node_type * pHead, split_list::details::search_value_type<Q> const & val, Compare cmp )
127 assert( pHead != nullptr );
128 bucket_head_type h(static_cast<list_node_type *>(pHead));
129 return base_class::find_at_( h, val, cmp );
132 bool insert_aux_node( dummy_node_type * pNode )
134 return base_class::insert_aux_node( pNode );
136 bool insert_aux_node( dummy_node_type * pHead, dummy_node_type * pNode )
138 bucket_head_type h(static_cast<list_node_type *>(pHead));
139 return base_class::insert_aux_node( h, pNode );
146 ordered_list_wrapper m_List; ///< Ordered list containing split-list items
147 bucket_table m_Buckets; ///< bucket table
148 atomics::atomic<size_t> m_nBucketCountLog2; ///< log2( current bucket count )
149 atomics::atomic<size_t> m_nMaxItemCount; ///< number of items container can hold, before we have to resize
150 item_counter m_ItemCounter; ///< Item counter
151 hash m_HashFunctor; ///< Hash functor
152 stat m_Stat; ///< Internal statistics
156 typedef cds::details::Allocator< dummy_node_type, typename traits::allocator > dummy_node_allocator;
158 dummy_node_type * alloc_dummy_node( size_t nHash )
160 m_Stat.onHeadNodeAllocated();
161 return dummy_node_allocator().New( nHash );
163 void free_dummy_node( dummy_node_type * p )
165 dummy_node_allocator().Delete( p );
166 m_Stat.onHeadNodeFreed();
169 /// Calculates hash value of \p key
170 template <typename Q>
171 size_t hash_value( Q const& key ) const
173 return m_HashFunctor( key );
176 size_t bucket_no( size_t nHash ) const
178 return nHash & ( (1 << m_nBucketCountLog2.load(memory_model::memory_order_relaxed)) - 1 );
181 static size_t parent_bucket( size_t nBucket )
183 assert( nBucket > 0 );
184 return nBucket & ~( 1 << bitop::MSBnz( nBucket ) );
187 dummy_node_type * init_bucket( size_t nBucket )
189 assert( nBucket > 0 );
190 size_t nParent = parent_bucket( nBucket );
192 dummy_node_type * pParentBucket = m_Buckets.bucket( nParent );
193 if ( pParentBucket == nullptr ) {
194 pParentBucket = init_bucket( nParent );
195 m_Stat.onRecursiveInitBucket();
198 assert( pParentBucket != nullptr );
200 // Allocate a dummy node for new bucket
202 dummy_node_type * pBucket = alloc_dummy_node( split_list::dummy_hash( nBucket ) );
203 if ( m_List.insert_aux_node( pParentBucket, pBucket ) ) {
204 m_Buckets.bucket( nBucket, pBucket );
205 m_Stat.onNewBucket();
208 free_dummy_node( pBucket );
211 // Another thread set the bucket. Wait while it done
213 // In this point, we must wait while nBucket is empty.
214 // The compiler can decide that waiting loop can be "optimized" (stripped)
215 // To prevent this situation, we use waiting on volatile bucket_head_ptr pointer.
217 m_Stat.onBucketInitContenton();
220 dummy_node_type volatile * p = m_Buckets.bucket( nBucket );
221 if ( p && p != nullptr )
222 return const_cast<dummy_node_type *>( p );
224 m_Stat.onBusyWaitBucketInit();
228 dummy_node_type * get_bucket( size_t nHash )
230 size_t nBucket = bucket_no( nHash );
232 dummy_node_type * pHead = m_Buckets.bucket( nBucket );
233 if ( pHead == nullptr )
234 pHead = init_bucket( nBucket );
236 assert( pHead->is_dummy() );
243 // GC and OrderedList::gc must be the same
244 static_assert( std::is_same<gc, typename ordered_list::gc>::value, "GC and OrderedList::gc must be the same");
246 // atomicity::empty_item_counter is not allowed as a item counter
247 static_assert( !std::is_same<item_counter, cds::atomicity::empty_item_counter>::value,
248 "cds::atomicity::empty_item_counter is not allowed as a item counter");
250 // Initialize bucket 0
251 dummy_node_type * pNode = alloc_dummy_node( 0 /*split_list::dummy_hash(0)*/ );
253 // insert_aux_node cannot return false for empty list
254 CDS_VERIFY( m_List.insert_aux_node( pNode ));
256 m_Buckets.bucket( 0, pNode );
259 static size_t max_item_count( size_t nBucketCount, size_t nLoadFactor )
261 return nBucketCount * nLoadFactor;
264 void inc_item_count()
266 size_t nMaxCount = m_nMaxItemCount.load(memory_model::memory_order_relaxed);
267 if ( ++m_ItemCounter <= nMaxCount )
270 const size_t nLoadFactor = m_Buckets.load_factor();
271 size_t sz = m_nBucketCountLog2.load(memory_model::memory_order_relaxed);
272 const size_t nBucketCount = static_cast<size_t>(1) << sz;
273 if ( nMaxCount < max_item_count( nBucketCount, nLoadFactor ))
274 return; // someone already have updated m_nBucketCountLog2, so stop here
276 const size_t nNewMaxCount = (nBucketCount < m_Buckets.capacity()) ? max_item_count( nBucketCount << 1, nLoadFactor )
277 : std::numeric_limits<size_t>::max();
278 m_nMaxItemCount.compare_exchange_strong( nMaxCount, nNewMaxCount, memory_model::memory_order_relaxed,
279 memory_model::memory_order_relaxed );
280 m_nBucketCountLog2.compare_exchange_strong( sz, sz + 1, memory_model::memory_order_relaxed, memory_model::memory_order_relaxed );
286 /// Initialize split-ordered list of default capacity
288 The default capacity is defined in bucket table constructor.
289 See split_list::expandable_bucket_table, split_list::static_ducket_table
290 which selects by split_list::dynamic_bucket_table option.
293 : m_nBucketCountLog2(1)
294 , m_nMaxItemCount( max_item_count(2, m_Buckets.load_factor()) )
299 /// Initialize split-ordered list
301 size_t nItemCount ///< estimate average of item count
302 , size_t nLoadFactor = 1 ///< load factor - average item count per bucket. Small integer up to 10, default is 1.
304 : m_Buckets( nItemCount, nLoadFactor )
305 , m_nBucketCountLog2(1)
306 , m_nMaxItemCount( max_item_count(2, m_Buckets.load_factor()) )
314 The function inserts \p val in the set if it does not contain
315 an item with key equal to \p val.
317 Returns \p true if \p val is placed into the set, \p false otherwise.
319 bool insert( value_type& val )
321 return insert_( val ) != end();
324 /// Ensures that the \p item exists in the set
326 The operation performs inserting or changing data with lock-free manner.
328 If the item \p val not found in the set, then \p val is inserted into the set.
329 Otherwise, the functor \p func is called with item found.
330 The functor signature is:
332 struct ensure_functor {
333 void operator()( bool bNew, value_type& item, value_type& val );
337 - \p bNew - \p true if the item has been inserted, \p false otherwise
338 - \p item - item of the set
339 - \p val - argument \p val passed into the \p ensure function
340 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
341 refers to the same thing.
343 The functor can change non-key fields of the \p item.
345 Returns std::pair<bool, bool> where \p first is \p true if operation is successfull,
346 \p second is \p true if new item has been added or \p false if the item with given key
347 already is in the set.
349 @warning For \ref cds_intrusive_MichaelList_nogc "MichaelList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
350 \ref cds_intrusive_LazyList_nogc "LazyList" provides exclusive access to inserted item and does not require any node-level
353 template <typename Func>
354 std::pair<bool, bool> ensure( value_type& val, Func func )
356 std::pair<iterator, bool> ret = ensure_( val, func );
357 return std::make_pair( ret.first != end(), ret.second );
360 /// Finds the key \p key
361 /** \anchor cds_intrusive_SplitListSet_nogc_find_val
362 The function searches the item with key equal to \p key
363 and returns pointer to item found or , and \p nullptr otherwise.
365 Note the hash functor specified for class \p Traits template parameter
366 should accept a parameter of type \p Q that can be not the same as \p value_type.
368 template <typename Q>
369 value_type * find( Q const& key )
371 iterator it = find_( key );
377 /// Finds the key \p key with \p pred predicate for comparing
379 The function is an analog of \ref cds_intrusive_SplitListSet_nogc_find_val "find(Q const&)"
380 but \p cmp is used for key compare.
381 \p Less has the interface like \p std::less.
382 \p cmp must imply the same element order as the comparator used for building the set.
384 template <typename Q, typename Less>
385 value_type * find_with( Q const& key, Less pred )
387 iterator it = find_with_( key, pred );
393 /// Finds the key \p key
394 /** \anchor cds_intrusive_SplitListSet_nogc_find_func
395 The function searches the item with key equal to \p key and calls the functor \p f for item found.
396 The interface of \p Func functor is:
399 void operator()( value_type& item, Q& key );
402 where \p item is the item found, \p key is the <tt>find</tt> function argument.
404 The functor can change non-key fields of \p item.
405 The functor does not serialize simultaneous access to the set \p item. If such access is
406 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
408 Note the hash functor specified for class \p Traits template parameter
409 should accept a parameter of type \p Q that can be not the same as \p value_type.
411 The function returns \p true if \p key is found, \p false otherwise.
413 template <typename Q, typename Func>
414 bool find( Q& key, Func f )
416 return find_( key, key_comparator(), f );
419 template <typename Q, typename Func>
420 bool find( Q const& key, Func f )
422 return find_( key, key_comparator(), f );
426 /// Finds the key \p key with \p pred predicate for comparing
428 The function is an analog of \ref cds_intrusive_SplitListSet_nogc_find_func "find(Q&, Func)"
429 but \p cmp is used for key compare.
430 \p Less has the interface like \p std::less.
431 \p cmp must imply the same element order as the comparator used for building the set.
433 template <typename Q, typename Less, typename Func>
434 bool find_with( Q& key, Less pred, Func f )
437 return find_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>(), f );
440 template <typename Q, typename Less, typename Func>
441 bool find_with( Q const& key, Less pred, Func f )
444 return find_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>(), f );
448 /// Checks if the set is empty
450 Emptiness is checked by item counting: if item count is zero then the set is empty.
451 Thus, the correct item counting feature is an important part of split-list implementation.
458 /// Returns item count in the set
461 return m_ItemCounter;
464 /// Returns internal statistics
465 stat const& statistics() const
472 template <bool IsConst>
474 : public split_list::details::iterator_type<node_traits, ordered_list, IsConst>
476 typedef split_list::details::iterator_type<node_traits, ordered_list, IsConst> iterator_base_class;
477 typedef typename iterator_base_class::list_iterator list_iterator;
480 : iterator_base_class()
483 iterator_type( iterator_type const& src )
484 : iterator_base_class( src )
487 // This ctor should be protected...
488 iterator_type( list_iterator itCur, list_iterator itEnd )
489 : iterator_base_class( itCur, itEnd )
497 The forward iterator for a split-list has some features:
498 - it has no post-increment operator
499 - it depends on iterator of underlying \p OrderedList
501 typedef iterator_type<false> iterator;
502 /// Const forward iterator
504 For iterator's features and requirements see \ref iterator
506 typedef iterator_type<true> const_iterator;
508 /// Returns a forward iterator addressing the first element in a split-list
510 For empty list \code begin() == end() \endcode
514 return iterator( m_List.begin(), m_List.end() );
517 /// Returns an iterator that addresses the location succeeding the last element in a split-list
519 Do not use the value returned by <tt>end</tt> function to access any item.
521 The returned value can be used only to control reaching the end of the split-list.
522 For empty list \code begin() == end() \endcode
526 return iterator( m_List.end(), m_List.end() );
529 /// Returns a forward const iterator addressing the first element in a split-list
531 const_iterator begin() const
533 return const_iterator( m_List.begin(), m_List.end() );
535 const_iterator cbegin() const
537 return const_iterator( m_List.cbegin(), m_List.cend() );
541 /// Returns an const iterator that addresses the location succeeding the last element in a split-list
543 const_iterator end() const
545 return const_iterator( m_List.end(), m_List.end() );
547 const_iterator cend() const
549 return const_iterator( m_List.cend(), m_List.cend() );
555 iterator insert_( value_type& val )
557 size_t nHash = hash_value( val );
558 dummy_node_type * pHead = get_bucket( nHash );
559 assert( pHead != nullptr );
561 node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
563 list_iterator it = m_List.insert_at_( pHead, val );
564 if ( it != m_List.end() ) {
566 m_Stat.onInsertSuccess();
567 return iterator( it, m_List.end() );
569 m_Stat.onInsertFailed();
573 template <typename Func>
574 std::pair<iterator, bool> ensure_( value_type& val, Func func )
576 size_t nHash = hash_value( val );
577 dummy_node_type * pHead = get_bucket( nHash );
578 assert( pHead != nullptr );
580 node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
582 std::pair<list_iterator, bool> ret = m_List.ensure_at_( pHead, val, func );
583 if ( ret.first != m_List.end() ) {
586 m_Stat.onEnsureNew();
589 m_Stat.onEnsureExist();
590 return std::make_pair( iterator(ret.first, m_List.end()), ret.second );
592 return std::make_pair( end(), ret.second );
595 template <typename Q, typename Less >
596 iterator find_with_( Q& val, Less pred )
599 size_t nHash = hash_value( val );
600 split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash( nHash ));
601 dummy_node_type * pHead = get_bucket( nHash );
602 assert( pHead != nullptr );
604 auto it = m_List.find_at_( pHead, sv, typename wrapped_ordered_list::template make_compare_from_less<Less>() );
605 m_Stat.onFind( it != m_List.end() );
606 return iterator( it, m_List.end() );
609 template <typename Q>
610 iterator find_( Q const& val )
612 size_t nHash = hash_value( val );
613 split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash( nHash ));
614 dummy_node_type * pHead = get_bucket( nHash );
615 assert( pHead != nullptr );
617 auto it = m_List.find_at_( pHead, sv, key_comparator() );
618 m_Stat.onFind( it != m_List.end() );
619 return iterator( it, m_List.end() );
622 template <typename Q, typename Compare, typename Func>
623 bool find_( Q& val, Compare cmp, Func f )
625 size_t nHash = hash_value( val );
626 split_list::details::search_value_type<Q> sv( val, split_list::regular_hash( nHash ));
627 dummy_node_type * pHead = get_bucket( nHash );
628 assert( pHead != nullptr );
629 return m_Stat.onFind( m_List.find_at( pHead, sv, cmp,
630 [&f](value_type& item, split_list::details::search_value_type<Q>& val){ f(item, val.val ); }));
636 }} // namespace cds::intrusive
638 #endif // #ifndef CDSLIB_INTRUSIVE_SPLIT_LIST_NOGC_H