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>
9 namespace cds { namespace intrusive {
11 /// Split-ordered list (template specialization for gc::nogc)
12 /** @ingroup cds_intrusive_map
13 \anchor cds_intrusive_SplitListSet_nogc
15 This specialization is intended for so-called persistent usage when no item
16 reclamation may be performed. The class does not support deleting of list item.
18 See \ref cds_intrusive_SplitListSet_hp "SplitListSet" for description of template parameters.
19 The template parameter \p OrderedList should be any gc::nogc-derived ordered list, for example,
20 \ref cds_intrusive_MichaelList_nogc "persistent MichaelList",
21 \ref cds_intrusive_LazyList_nogc "persistent LazyList"
25 #ifdef CDS_DOXYGEN_INVOKED
26 class Traits = split_list::traits
31 class SplitListSet< cds::gc::nogc, OrderedList, Traits >
34 typedef cds::gc::nogc gc; ///< Garbage collector
35 typedef Traits traits; ///< Traits template parameters
37 /// Hash functor for \p value_type and all its derivatives that you use
38 typedef typename cds::opt::v::hash_selector< typename traits::hash >::type hash;
42 typedef split_list::details::rebind_list_traits<OrderedList, traits> wrapped_ordered_list;
46 # ifdef CDS_DOXYGEN_INVOKED
47 typedef OrderedList ordered_list; ///< type of ordered list used as base for split-list
49 typedef typename wrapped_ordered_list::result ordered_list;
51 typedef typename ordered_list::value_type value_type; ///< type of value stored in the split-list
52 typedef typename ordered_list::key_comparator key_comparator; ///< key comparison functor
53 typedef typename ordered_list::disposer disposer; ///< Node disposer functor
55 typedef typename traits::item_counter item_counter; ///< Item counter type
56 typedef typename traits::back_off back_off; ///< back-off strategy
57 typedef typename traits::memory_model memory_model; ///< Memory ordering. See cds::opt::memory_model option
58 typedef typename traits::stat stat; ///< Internal statistics, see \p spit_list::stat
61 typedef typename ordered_list::node_type list_node_type; ///< Node type as declared in ordered list
62 typedef split_list::node<list_node_type> node_type; ///< split-list node type
63 typedef node_type dummy_node_type; ///< dummy node type
65 /// Split-list node traits
67 This traits is intended for converting between underlying ordered list node type \ref list_node_type
68 and split-list node type \ref node_type
70 typedef split_list::node_traits<typename ordered_list::node_traits> node_traits;
73 /// Bucket table implementation
74 typedef typename split_list::details::bucket_table_selector<
75 traits::dynamic_bucket_table
78 , opt::allocator< typename traits::allocator >
79 , opt::memory_model< memory_model >
82 typedef typename ordered_list::iterator list_iterator;
83 typedef typename ordered_list::const_iterator list_const_iterator;
88 /// Ordered list wrapper to access protected members
89 class ordered_list_wrapper: public ordered_list
91 typedef ordered_list base_class;
92 typedef typename base_class::auxiliary_head bucket_head_type;
95 list_iterator insert_at_( dummy_node_type * pHead, value_type& val )
97 assert( pHead != nullptr );
98 bucket_head_type h(static_cast<list_node_type *>(pHead));
99 return base_class::insert_at_( h, val );
102 template <typename Func>
103 std::pair<list_iterator, bool> ensure_at_( dummy_node_type * pHead, value_type& val, Func func )
105 assert( pHead != nullptr );
106 bucket_head_type h(static_cast<list_node_type *>(pHead));
107 return base_class::ensure_at_( h, val, func );
110 template <typename Q, typename Compare, typename Func>
111 bool find_at( dummy_node_type * pHead, split_list::details::search_value_type<Q>& val, Compare cmp, Func f )
113 assert( pHead != nullptr );
114 bucket_head_type h(static_cast<list_node_type *>(pHead));
115 return base_class::find_at( h, val, cmp, f );
118 template <typename Q, typename Compare>
119 list_iterator find_at_( dummy_node_type * pHead, split_list::details::search_value_type<Q> const & val, Compare cmp )
121 assert( pHead != nullptr );
122 bucket_head_type h(static_cast<list_node_type *>(pHead));
123 return base_class::find_at_( h, val, cmp );
126 bool insert_aux_node( dummy_node_type * pNode )
128 return base_class::insert_aux_node( pNode );
130 bool insert_aux_node( dummy_node_type * pHead, dummy_node_type * pNode )
132 bucket_head_type h(static_cast<list_node_type *>(pHead));
133 return base_class::insert_aux_node( h, pNode );
140 ordered_list_wrapper m_List; ///< Ordered list containing split-list items
141 bucket_table m_Buckets; ///< bucket table
142 atomics::atomic<size_t> m_nBucketCountLog2; ///< log2( current bucket count )
143 item_counter m_ItemCounter; ///< Item counter
144 hash m_HashFunctor; ///< Hash functor
145 stat m_Stat; ///< Internal statistics
149 typedef cds::details::Allocator< dummy_node_type, typename traits::allocator > dummy_node_allocator;
151 dummy_node_type * alloc_dummy_node( size_t nHash )
153 m_Stat.onHeadNodeAllocated();
154 return dummy_node_allocator().New( nHash );
156 void free_dummy_node( dummy_node_type * p )
158 dummy_node_allocator().Delete( p );
159 m_Stat.onHeadNodeFreed();
162 /// Calculates hash value of \p key
163 template <typename Q>
164 size_t hash_value( Q const& key ) const
166 return m_HashFunctor( key );
169 size_t bucket_no( size_t nHash ) const
171 return nHash & ( (1 << m_nBucketCountLog2.load(atomics::memory_order_relaxed)) - 1 );
174 static size_t parent_bucket( size_t nBucket )
176 assert( nBucket > 0 );
177 return nBucket & ~( 1 << bitop::MSBnz( nBucket ) );
180 dummy_node_type * init_bucket( size_t nBucket )
182 assert( nBucket > 0 );
183 size_t nParent = parent_bucket( nBucket );
185 dummy_node_type * pParentBucket = m_Buckets.bucket( nParent );
186 if ( pParentBucket == nullptr ) {
187 pParentBucket = init_bucket( nParent );
188 m_Stat.onRecursiveInitBucket();
191 assert( pParentBucket != nullptr );
193 // Allocate a dummy node for new bucket
195 dummy_node_type * pBucket = alloc_dummy_node( split_list::dummy_hash( nBucket ) );
196 if ( m_List.insert_aux_node( pParentBucket, pBucket ) ) {
197 m_Buckets.bucket( nBucket, pBucket );
198 m_Stat.onNewBucket();
201 free_dummy_node( pBucket );
204 // Another thread set the bucket. Wait while it done
206 // In this point, we must wait while nBucket is empty.
207 // The compiler can decide that waiting loop can be "optimized" (stripped)
208 // To prevent this situation, we use waiting on volatile bucket_head_ptr pointer.
210 m_Stat.onBucketInitContenton();
213 dummy_node_type volatile * p = m_Buckets.bucket( nBucket );
214 if ( p && p != nullptr )
215 return const_cast<dummy_node_type *>( p );
217 m_Stat.onBusyWaitBucketInit();
221 dummy_node_type * get_bucket( size_t nHash )
223 size_t nBucket = bucket_no( nHash );
225 dummy_node_type * pHead = m_Buckets.bucket( nBucket );
226 if ( pHead == nullptr )
227 pHead = init_bucket( nBucket );
229 assert( pHead->is_dummy() );
236 // GC and OrderedList::gc must be the same
237 static_assert( std::is_same<gc, typename ordered_list::gc>::value, "GC and OrderedList::gc must be the same");
239 // atomicity::empty_item_counter is not allowed as a item counter
240 static_assert( !std::is_same<item_counter, cds::atomicity::empty_item_counter>::value,
241 "cds::atomicity::empty_item_counter is not allowed as a item counter");
243 // Initialize bucket 0
244 dummy_node_type * pNode = alloc_dummy_node( 0 /*split_list::dummy_hash(0)*/ );
246 // insert_aux_node cannot return false for empty list
247 CDS_VERIFY( m_List.insert_aux_node( pNode ));
249 m_Buckets.bucket( 0, pNode );
252 void inc_item_count()
254 size_t sz = m_nBucketCountLog2.load(atomics::memory_order_relaxed);
255 if ( ( ++m_ItemCounter >> sz ) > m_Buckets.load_factor() && ((size_t)(1 << sz )) < m_Buckets.capacity() )
257 m_nBucketCountLog2.compare_exchange_strong( sz, sz + 1, atomics::memory_order_seq_cst, atomics::memory_order_relaxed );
264 /// Initialize split-ordered list of default capacity
266 The default capacity is defined in bucket table constructor.
267 See split_list::expandable_bucket_table, split_list::static_ducket_table
268 which selects by split_list::dynamic_bucket_table option.
271 : m_nBucketCountLog2(1)
276 /// Initialize split-ordered list
278 size_t nItemCount ///< estimate average of item count
279 , size_t nLoadFactor = 1 ///< load factor - average item count per bucket. Small integer up to 10, default is 1.
281 : m_Buckets( nItemCount, nLoadFactor )
282 , m_nBucketCountLog2(1)
290 The function inserts \p val in the set if it does not contain
291 an item with key equal to \p val.
293 Returns \p true if \p val is placed into the set, \p false otherwise.
295 bool insert( value_type& val )
297 return insert_( val ) != end();
300 /// Ensures that the \p item exists in the set
302 The operation performs inserting or changing data with lock-free manner.
304 If the item \p val not found in the set, then \p val is inserted into the set.
305 Otherwise, the functor \p func is called with item found.
306 The functor signature is:
308 struct ensure_functor {
309 void operator()( bool bNew, value_type& item, value_type& val );
313 - \p bNew - \p true if the item has been inserted, \p false otherwise
314 - \p item - item of the set
315 - \p val - argument \p val passed into the \p ensure function
316 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
317 refers to the same thing.
319 The functor can change non-key fields of the \p item.
321 Returns std::pair<bool, bool> where \p first is \p true if operation is successfull,
322 \p second is \p true if new item has been added or \p false if the item with given key
323 already is in the set.
325 @warning For \ref cds_intrusive_MichaelList_nogc "MichaelList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
326 \ref cds_intrusive_LazyList_nogc "LazyList" provides exclusive access to inserted item and does not require any node-level
329 template <typename Func>
330 std::pair<bool, bool> ensure( value_type& val, Func func )
332 std::pair<iterator, bool> ret = ensure_( val, func );
333 return std::make_pair( ret.first != end(), ret.second );
336 /// Finds the key \p key
337 /** \anchor cds_intrusive_SplitListSet_nogc_find_val
338 The function searches the item with key equal to \p key
339 and returns pointer to item found or , and \p nullptr otherwise.
341 Note the hash functor specified for class \p Traits template parameter
342 should accept a parameter of type \p Q that can be not the same as \p value_type.
344 template <typename Q>
345 value_type * find( Q const& key )
347 iterator it = find_( key );
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_val "find(Q const&)"
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>
361 value_type * find_with( Q const& key, Less pred )
363 iterator it = find_with_( key, pred );
369 /// Finds the key \p key
370 /** \anchor cds_intrusive_SplitListSet_nogc_find_func
371 The function searches the item with key equal to \p key and calls the functor \p f for item found.
372 The interface of \p Func functor is:
375 void operator()( value_type& item, Q& key );
378 where \p item is the item found, \p key is the <tt>find</tt> function argument.
380 The functor can change non-key fields of \p item.
381 The functor does not serialize simultaneous access to the set \p item. If such access is
382 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
384 Note the hash functor specified for class \p Traits template parameter
385 should accept a parameter of type \p Q that can be not the same as \p value_type.
387 The function returns \p true if \p key is found, \p false otherwise.
389 template <typename Q, typename Func>
390 bool find( Q& key, Func f )
392 return find_( key, key_comparator(), f );
395 template <typename Q, typename Func>
396 bool find( Q const& key, Func f )
398 return find_( key, key_comparator(), f );
402 /// Finds the key \p key with \p pred predicate for comparing
404 The function is an analog of \ref cds_intrusive_SplitListSet_nogc_find_func "find(Q&, Func)"
405 but \p cmp is used for key compare.
406 \p Less has the interface like \p std::less.
407 \p cmp must imply the same element order as the comparator used for building the set.
409 template <typename Q, typename Less, typename Func>
410 bool find_with( Q& key, Less pred, Func f )
413 return find_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>(), f );
416 template <typename Q, typename Less, typename Func>
417 bool find_with( Q const& key, Less pred, Func f )
420 return find_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>(), f );
424 /// Checks if the set is empty
426 Emptiness is checked by item counting: if item count is zero then the set is empty.
427 Thus, the correct item counting feature is an important part of split-list implementation.
434 /// Returns item count in the set
437 return m_ItemCounter;
440 /// Returns internal statistics
441 stat const& statistics() const
448 template <bool IsConst>
450 : public split_list::details::iterator_type<node_traits, ordered_list, IsConst>
452 typedef split_list::details::iterator_type<node_traits, ordered_list, IsConst> iterator_base_class;
453 typedef typename iterator_base_class::list_iterator list_iterator;
456 : iterator_base_class()
459 iterator_type( iterator_type const& src )
460 : iterator_base_class( src )
463 // This ctor should be protected...
464 iterator_type( list_iterator itCur, list_iterator itEnd )
465 : iterator_base_class( itCur, itEnd )
473 The forward iterator for a split-list has some features:
474 - it has no post-increment operator
475 - it depends on iterator of underlying \p OrderedList
477 typedef iterator_type<false> iterator;
478 /// Const forward iterator
480 For iterator's features and requirements see \ref iterator
482 typedef iterator_type<true> const_iterator;
484 /// Returns a forward iterator addressing the first element in a split-list
486 For empty list \code begin() == end() \endcode
490 return iterator( m_List.begin(), m_List.end() );
493 /// Returns an iterator that addresses the location succeeding the last element in a split-list
495 Do not use the value returned by <tt>end</tt> function to access any item.
497 The returned value can be used only to control reaching the end of the split-list.
498 For empty list \code begin() == end() \endcode
502 return iterator( m_List.end(), m_List.end() );
505 /// Returns a forward const iterator addressing the first element in a split-list
507 const_iterator begin() const
509 return const_iterator( m_List.begin(), m_List.end() );
511 const_iterator cbegin() const
513 return const_iterator( m_List.cbegin(), m_List.cend() );
517 /// Returns an const iterator that addresses the location succeeding the last element in a split-list
519 const_iterator end() const
521 return const_iterator( m_List.end(), m_List.end() );
523 const_iterator cend() const
525 return const_iterator( m_List.cend(), m_List.cend() );
531 iterator insert_( value_type& val )
533 size_t nHash = hash_value( val );
534 dummy_node_type * pHead = get_bucket( nHash );
535 assert( pHead != nullptr );
537 node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
539 list_iterator it = m_List.insert_at_( pHead, val );
540 if ( it != m_List.end() ) {
542 m_Stat.onInsertSuccess();
543 return iterator( it, m_List.end() );
545 m_Stat.onInsertFailed();
549 template <typename Func>
550 std::pair<iterator, bool> ensure_( value_type& val, Func func )
552 size_t nHash = hash_value( val );
553 dummy_node_type * pHead = get_bucket( nHash );
554 assert( pHead != nullptr );
556 node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
558 std::pair<list_iterator, bool> ret = m_List.ensure_at_( pHead, val, func );
559 if ( ret.first != m_List.end() ) {
562 m_Stat.onEnsureNew();
565 m_Stat.onEnsureExist();
566 return std::make_pair( iterator(ret.first, m_List.end()), ret.second );
568 return std::make_pair( end(), ret.second );
571 template <typename Q, typename Less >
572 iterator find_with_( Q& val, Less pred )
575 size_t nHash = hash_value( val );
576 split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash( nHash ));
577 dummy_node_type * pHead = get_bucket( nHash );
578 assert( pHead != nullptr );
580 auto it = m_List.find_at_( pHead, sv, typename wrapped_ordered_list::template make_compare_from_less<Less>() );
581 m_Stat.onFind( it != m_List.end() );
582 return iterator( it, m_List.end() );
585 template <typename Q>
586 iterator find_( Q const& val )
588 size_t nHash = hash_value( val );
589 split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash( nHash ));
590 dummy_node_type * pHead = get_bucket( nHash );
591 assert( pHead != nullptr );
593 auto it = m_List.find_at_( pHead, sv, key_comparator() );
594 m_Stat.onFind( it != m_List.end() );
595 return iterator( it, m_List.end() );
598 template <typename Q, typename Compare, typename Func>
599 bool find_( Q& val, Compare cmp, Func f )
601 size_t nHash = hash_value( val );
602 split_list::details::search_value_type<Q> sv( val, split_list::regular_hash( nHash ));
603 dummy_node_type * pHead = get_bucket( nHash );
604 assert( pHead != nullptr );
605 return m_Stat.onFind( m_List.find_at( pHead, sv, cmp,
606 [&f](value_type& item, split_list::details::search_value_type<Q>& val){ f(item, val.val ); }));
612 }} // namespace cds::intrusive
614 #endif // #ifndef CDSLIB_INTRUSIVE_SPLIT_LIST_NOGC_H