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;
41 typedef cds::intrusive::split_list::implementation_tag implementation_tag;
46 typedef split_list::details::rebind_list_traits<OrderedList, traits> wrapped_ordered_list;
50 # ifdef CDS_DOXYGEN_INVOKED
51 typedef OrderedList ordered_list; ///< type of ordered list used as base for split-list
53 typedef typename wrapped_ordered_list::result ordered_list;
55 typedef typename ordered_list::value_type value_type; ///< type of value stored in the split-list
56 typedef typename ordered_list::key_comparator key_comparator; ///< key comparison functor
57 typedef typename ordered_list::disposer disposer; ///< Node disposer functor
59 typedef typename traits::item_counter item_counter; ///< Item counter type
60 typedef typename traits::back_off back_off; ///< back-off strategy
61 typedef typename traits::memory_model memory_model; ///< Memory ordering. See cds::opt::memory_model option
62 typedef typename traits::stat stat; ///< Internal statistics, see \p spit_list::stat
65 typedef typename ordered_list::node_type list_node_type; ///< Node type as declared in ordered list
66 typedef split_list::node<list_node_type> node_type; ///< split-list node type
67 typedef node_type dummy_node_type; ///< dummy node type
69 /// Split-list node traits
71 This traits is intended for converting between underlying ordered list node type \ref list_node_type
72 and split-list node type \ref node_type
74 typedef split_list::node_traits<typename ordered_list::node_traits> node_traits;
77 /// Bucket table implementation
78 typedef typename split_list::details::bucket_table_selector<
79 traits::dynamic_bucket_table
82 , opt::allocator< typename traits::allocator >
83 , opt::memory_model< memory_model >
86 typedef typename ordered_list::iterator list_iterator;
87 typedef typename ordered_list::const_iterator list_const_iterator;
92 /// Ordered list wrapper to access protected members
93 class ordered_list_wrapper: public ordered_list
95 typedef ordered_list base_class;
96 typedef typename base_class::auxiliary_head bucket_head_type;
99 list_iterator insert_at_( dummy_node_type * pHead, value_type& val )
101 assert( pHead != nullptr );
102 bucket_head_type h(static_cast<list_node_type *>(pHead));
103 return base_class::insert_at_( h, val );
106 template <typename Func>
107 std::pair<list_iterator, bool> ensure_at_( dummy_node_type * pHead, value_type& val, Func func )
109 assert( pHead != nullptr );
110 bucket_head_type h(static_cast<list_node_type *>(pHead));
111 return base_class::ensure_at_( h, val, func );
114 template <typename Q, typename Compare, typename Func>
115 bool find_at( dummy_node_type * pHead, split_list::details::search_value_type<Q>& val, Compare cmp, Func f )
117 assert( pHead != nullptr );
118 bucket_head_type h(static_cast<list_node_type *>(pHead));
119 return base_class::find_at( h, val, cmp, f );
122 template <typename Q, typename Compare>
123 list_iterator find_at_( dummy_node_type * pHead, split_list::details::search_value_type<Q> const & val, Compare cmp )
125 assert( pHead != nullptr );
126 bucket_head_type h(static_cast<list_node_type *>(pHead));
127 return base_class::find_at_( h, val, cmp );
130 bool insert_aux_node( dummy_node_type * pNode )
132 return base_class::insert_aux_node( pNode );
134 bool insert_aux_node( dummy_node_type * pHead, dummy_node_type * pNode )
136 bucket_head_type h(static_cast<list_node_type *>(pHead));
137 return base_class::insert_aux_node( h, pNode );
144 ordered_list_wrapper m_List; ///< Ordered list containing split-list items
145 bucket_table m_Buckets; ///< bucket table
146 atomics::atomic<size_t> m_nBucketCountLog2; ///< log2( current bucket count )
147 item_counter m_ItemCounter; ///< Item counter
148 hash m_HashFunctor; ///< Hash functor
149 stat m_Stat; ///< Internal statistics
153 typedef cds::details::Allocator< dummy_node_type, typename traits::allocator > dummy_node_allocator;
155 dummy_node_type * alloc_dummy_node( size_t nHash )
157 m_Stat.onHeadNodeAllocated();
158 return dummy_node_allocator().New( nHash );
160 void free_dummy_node( dummy_node_type * p )
162 dummy_node_allocator().Delete( p );
163 m_Stat.onHeadNodeFreed();
166 /// Calculates hash value of \p key
167 template <typename Q>
168 size_t hash_value( Q const& key ) const
170 return m_HashFunctor( key );
173 size_t bucket_no( size_t nHash ) const
175 return nHash & ( (1 << m_nBucketCountLog2.load(memory_model::memory_order_relaxed)) - 1 );
178 static size_t parent_bucket( size_t nBucket )
180 assert( nBucket > 0 );
181 return nBucket & ~( 1 << bitop::MSBnz( nBucket ) );
184 dummy_node_type * init_bucket( size_t nBucket )
186 assert( nBucket > 0 );
187 size_t nParent = parent_bucket( nBucket );
189 dummy_node_type * pParentBucket = m_Buckets.bucket( nParent );
190 if ( pParentBucket == nullptr ) {
191 pParentBucket = init_bucket( nParent );
192 m_Stat.onRecursiveInitBucket();
195 assert( pParentBucket != nullptr );
197 // Allocate a dummy node for new bucket
199 dummy_node_type * pBucket = alloc_dummy_node( split_list::dummy_hash( nBucket ) );
200 if ( m_List.insert_aux_node( pParentBucket, pBucket ) ) {
201 m_Buckets.bucket( nBucket, pBucket );
202 m_Stat.onNewBucket();
205 free_dummy_node( pBucket );
208 // Another thread set the bucket. Wait while it done
210 // In this point, we must wait while nBucket is empty.
211 // The compiler can decide that waiting loop can be "optimized" (stripped)
212 // To prevent this situation, we use waiting on volatile bucket_head_ptr pointer.
214 m_Stat.onBucketInitContenton();
217 dummy_node_type volatile * p = m_Buckets.bucket( nBucket );
218 if ( p && p != nullptr )
219 return const_cast<dummy_node_type *>( p );
221 m_Stat.onBusyWaitBucketInit();
225 dummy_node_type * get_bucket( size_t nHash )
227 size_t nBucket = bucket_no( nHash );
229 dummy_node_type * pHead = m_Buckets.bucket( nBucket );
230 if ( pHead == nullptr )
231 pHead = init_bucket( nBucket );
233 assert( pHead->is_dummy() );
240 // GC and OrderedList::gc must be the same
241 static_assert( std::is_same<gc, typename ordered_list::gc>::value, "GC and OrderedList::gc must be the same");
243 // atomicity::empty_item_counter is not allowed as a item counter
244 static_assert( !std::is_same<item_counter, cds::atomicity::empty_item_counter>::value,
245 "cds::atomicity::empty_item_counter is not allowed as a item counter");
247 // Initialize bucket 0
248 dummy_node_type * pNode = alloc_dummy_node( 0 /*split_list::dummy_hash(0)*/ );
250 // insert_aux_node cannot return false for empty list
251 CDS_VERIFY( m_List.insert_aux_node( pNode ));
253 m_Buckets.bucket( 0, pNode );
256 void inc_item_count()
258 size_t sz = m_nBucketCountLog2.load(memory_model::memory_order_relaxed);
259 if ( ( ++m_ItemCounter >> sz ) > m_Buckets.load_factor() && ((size_t)(1 << sz )) < m_Buckets.capacity() )
261 m_nBucketCountLog2.compare_exchange_strong( sz, sz + 1, memory_model::memory_order_relaxed, atomics::memory_order_relaxed );
268 /// Initialize split-ordered list of default capacity
270 The default capacity is defined in bucket table constructor.
271 See split_list::expandable_bucket_table, split_list::static_ducket_table
272 which selects by split_list::dynamic_bucket_table option.
275 : m_nBucketCountLog2(1)
280 /// Initialize split-ordered list
282 size_t nItemCount ///< estimate average of item count
283 , size_t nLoadFactor = 1 ///< load factor - average item count per bucket. Small integer up to 10, default is 1.
285 : m_Buckets( nItemCount, nLoadFactor )
286 , m_nBucketCountLog2(1)
294 The function inserts \p val in the set if it does not contain
295 an item with key equal to \p val.
297 Returns \p true if \p val is placed into the set, \p false otherwise.
299 bool insert( value_type& val )
301 return insert_( val ) != end();
304 /// Ensures that the \p item exists in the set
306 The operation performs inserting or changing data with lock-free manner.
308 If the item \p val not found in the set, then \p val is inserted into the set.
309 Otherwise, the functor \p func is called with item found.
310 The functor signature is:
312 struct ensure_functor {
313 void operator()( bool bNew, value_type& item, value_type& val );
317 - \p bNew - \p true if the item has been inserted, \p false otherwise
318 - \p item - item of the set
319 - \p val - argument \p val passed into the \p ensure function
320 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
321 refers to the same thing.
323 The functor can change non-key fields of the \p item.
325 Returns std::pair<bool, bool> where \p first is \p true if operation is successfull,
326 \p second is \p true if new item has been added or \p false if the item with given key
327 already is in the set.
329 @warning For \ref cds_intrusive_MichaelList_nogc "MichaelList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
330 \ref cds_intrusive_LazyList_nogc "LazyList" provides exclusive access to inserted item and does not require any node-level
333 template <typename Func>
334 std::pair<bool, bool> ensure( value_type& val, Func func )
336 std::pair<iterator, bool> ret = ensure_( val, func );
337 return std::make_pair( ret.first != end(), ret.second );
340 /// Finds the key \p key
341 /** \anchor cds_intrusive_SplitListSet_nogc_find_val
342 The function searches the item with key equal to \p key
343 and returns pointer to item found or , and \p nullptr otherwise.
345 Note the hash functor specified for class \p Traits template parameter
346 should accept a parameter of type \p Q that can be not the same as \p value_type.
348 template <typename Q>
349 value_type * find( Q const& key )
351 iterator it = find_( key );
357 /// Finds the key \p key with \p pred predicate for comparing
359 The function is an analog of \ref cds_intrusive_SplitListSet_nogc_find_val "find(Q const&)"
360 but \p cmp is used for key compare.
361 \p Less has the interface like \p std::less.
362 \p cmp must imply the same element order as the comparator used for building the set.
364 template <typename Q, typename Less>
365 value_type * find_with( Q const& key, Less pred )
367 iterator it = find_with_( key, pred );
373 /// Finds the key \p key
374 /** \anchor cds_intrusive_SplitListSet_nogc_find_func
375 The function searches the item with key equal to \p key and calls the functor \p f for item found.
376 The interface of \p Func functor is:
379 void operator()( value_type& item, Q& key );
382 where \p item is the item found, \p key is the <tt>find</tt> function argument.
384 The functor can change non-key fields of \p item.
385 The functor does not serialize simultaneous access to the set \p item. If such access is
386 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
388 Note the hash functor specified for class \p Traits template parameter
389 should accept a parameter of type \p Q that can be not the same as \p value_type.
391 The function returns \p true if \p key is found, \p false otherwise.
393 template <typename Q, typename Func>
394 bool find( Q& key, Func f )
396 return find_( key, key_comparator(), f );
399 template <typename Q, typename Func>
400 bool find( Q const& key, Func f )
402 return find_( key, key_comparator(), f );
406 /// Finds the key \p key with \p pred predicate for comparing
408 The function is an analog of \ref cds_intrusive_SplitListSet_nogc_find_func "find(Q&, Func)"
409 but \p cmp is used for key compare.
410 \p Less has the interface like \p std::less.
411 \p cmp must imply the same element order as the comparator used for building the set.
413 template <typename Q, typename Less, typename Func>
414 bool find_with( Q& key, Less pred, Func f )
417 return find_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>(), f );
420 template <typename Q, typename Less, typename Func>
421 bool find_with( Q const& key, Less pred, Func f )
424 return find_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>(), f );
428 /// Checks if the set is empty
430 Emptiness is checked by item counting: if item count is zero then the set is empty.
431 Thus, the correct item counting feature is an important part of split-list implementation.
438 /// Returns item count in the set
441 return m_ItemCounter;
444 /// Returns internal statistics
445 stat const& statistics() const
452 template <bool IsConst>
454 : public split_list::details::iterator_type<node_traits, ordered_list, IsConst>
456 typedef split_list::details::iterator_type<node_traits, ordered_list, IsConst> iterator_base_class;
457 typedef typename iterator_base_class::list_iterator list_iterator;
460 : iterator_base_class()
463 iterator_type( iterator_type const& src )
464 : iterator_base_class( src )
467 // This ctor should be protected...
468 iterator_type( list_iterator itCur, list_iterator itEnd )
469 : iterator_base_class( itCur, itEnd )
477 The forward iterator for a split-list has some features:
478 - it has no post-increment operator
479 - it depends on iterator of underlying \p OrderedList
481 typedef iterator_type<false> iterator;
482 /// Const forward iterator
484 For iterator's features and requirements see \ref iterator
486 typedef iterator_type<true> const_iterator;
488 /// Returns a forward iterator addressing the first element in a split-list
490 For empty list \code begin() == end() \endcode
494 return iterator( m_List.begin(), m_List.end() );
497 /// Returns an iterator that addresses the location succeeding the last element in a split-list
499 Do not use the value returned by <tt>end</tt> function to access any item.
501 The returned value can be used only to control reaching the end of the split-list.
502 For empty list \code begin() == end() \endcode
506 return iterator( m_List.end(), m_List.end() );
509 /// Returns a forward const iterator addressing the first element in a split-list
511 const_iterator begin() const
513 return const_iterator( m_List.begin(), m_List.end() );
515 const_iterator cbegin() const
517 return const_iterator( m_List.cbegin(), m_List.cend() );
521 /// Returns an const iterator that addresses the location succeeding the last element in a split-list
523 const_iterator end() const
525 return const_iterator( m_List.end(), m_List.end() );
527 const_iterator cend() const
529 return const_iterator( m_List.cend(), m_List.cend() );
535 iterator insert_( value_type& val )
537 size_t nHash = hash_value( val );
538 dummy_node_type * pHead = get_bucket( nHash );
539 assert( pHead != nullptr );
541 node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
543 list_iterator it = m_List.insert_at_( pHead, val );
544 if ( it != m_List.end() ) {
546 m_Stat.onInsertSuccess();
547 return iterator( it, m_List.end() );
549 m_Stat.onInsertFailed();
553 template <typename Func>
554 std::pair<iterator, bool> ensure_( value_type& val, Func func )
556 size_t nHash = hash_value( val );
557 dummy_node_type * pHead = get_bucket( nHash );
558 assert( pHead != nullptr );
560 node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
562 std::pair<list_iterator, bool> ret = m_List.ensure_at_( pHead, val, func );
563 if ( ret.first != m_List.end() ) {
566 m_Stat.onEnsureNew();
569 m_Stat.onEnsureExist();
570 return std::make_pair( iterator(ret.first, m_List.end()), ret.second );
572 return std::make_pair( end(), ret.second );
575 template <typename Q, typename Less >
576 iterator find_with_( Q& val, Less pred )
579 size_t nHash = hash_value( val );
580 split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash( nHash ));
581 dummy_node_type * pHead = get_bucket( nHash );
582 assert( pHead != nullptr );
584 auto it = m_List.find_at_( pHead, sv, typename wrapped_ordered_list::template make_compare_from_less<Less>() );
585 m_Stat.onFind( it != m_List.end() );
586 return iterator( it, m_List.end() );
589 template <typename Q>
590 iterator find_( Q const& val )
592 size_t nHash = hash_value( val );
593 split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash( nHash ));
594 dummy_node_type * pHead = get_bucket( nHash );
595 assert( pHead != nullptr );
597 auto it = m_List.find_at_( pHead, sv, key_comparator() );
598 m_Stat.onFind( it != m_List.end() );
599 return iterator( it, m_List.end() );
602 template <typename Q, typename Compare, typename Func>
603 bool find_( Q& val, Compare cmp, Func f )
605 size_t nHash = hash_value( val );
606 split_list::details::search_value_type<Q> sv( val, split_list::regular_hash( nHash ));
607 dummy_node_type * pHead = get_bucket( nHash );
608 assert( pHead != nullptr );
609 return m_Stat.onFind( m_List.find_at( pHead, sv, cmp,
610 [&f](value_type& item, split_list::details::search_value_type<Q>& val){ f(item, val.val ); }));
616 }} // namespace cds::intrusive
618 #endif // #ifndef CDSLIB_INTRUSIVE_SPLIT_LIST_NOGC_H