3 #ifndef __CDS_INTRUSIVE_SPLIT_LIST_NOGC_H
4 #define __CDS_INTRUSIVE_SPLIT_LIST_NOGC_H
6 #include <cds/intrusive/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"
23 The interface of the specialization is a slightly different.
27 #ifdef CDS_DOXYGEN_INVOKED
28 class Traits = split_list::type_traits
33 class SplitListSet< gc::nogc, OrderedList, Traits >
36 typedef Traits options ; ///< Traits template parameters
37 typedef gc::nogc gc ; ///< Garbage collector
39 /// Hash functor for \ref value_type and all its derivatives that you use
40 typedef typename cds::opt::v::hash_selector< typename options::hash >::type hash;
44 typedef split_list::details::rebind_list_options<OrderedList, options> 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 options::item_counter item_counter ; ///< Item counter type
58 typedef typename options::back_off back_off ; ///< back-off strategy for spinning
59 typedef typename options::memory_model memory_model ; ///< Memory ordering. See cds::opt::memory_model option
62 typedef typename ordered_list::node_type list_node_type ; ///< Node type as declared in ordered list
63 typedef split_list::node<list_node_type> node_type ; ///< split-list node type
64 typedef node_type dummy_node_type ; ///< dummy node type
66 /// Split-list node traits
68 This traits is intended for converting between underlying ordered list node type \ref list_node_type
69 and split-list node type \ref node_type
71 typedef split_list::node_traits<typename ordered_list::node_traits> node_traits;
74 /// Bucket table implementation
75 typedef typename split_list::details::bucket_table_selector<
76 options::dynamic_bucket_table
79 , opt::allocator< typename options::allocator >
80 , opt::memory_model< memory_model >
83 typedef typename ordered_list::iterator list_iterator;
84 typedef typename ordered_list::const_iterator list_const_iterator;
89 /// Ordered list wrapper to access protected members
90 class ordered_list_wrapper: public ordered_list
92 typedef ordered_list base_class;
93 typedef typename base_class::auxiliary_head bucket_head_type;
96 list_iterator insert_at_( dummy_node_type * pHead, value_type& val )
98 assert( pHead != nullptr );
99 bucket_head_type h(static_cast<list_node_type *>(pHead));
100 return base_class::insert_at_( h, val );
103 template <typename Func>
104 std::pair<list_iterator, bool> ensure_at_( dummy_node_type * pHead, value_type& val, Func func )
106 assert( pHead != nullptr );
107 bucket_head_type h(static_cast<list_node_type *>(pHead));
108 return base_class::ensure_at_( h, val, func );
111 template <typename Q, typename Compare, typename Func>
112 bool find_at( dummy_node_type * pHead, split_list::details::search_value_type<Q>& val, Compare cmp, Func f )
114 assert( pHead != nullptr );
115 bucket_head_type h(static_cast<list_node_type *>(pHead));
116 return base_class::find_at( h, val, cmp, f );
119 template <typename Q, typename Compare>
120 list_iterator find_at_( dummy_node_type * pHead, split_list::details::search_value_type<Q> const & val, Compare cmp )
122 assert( pHead != nullptr );
123 bucket_head_type h(static_cast<list_node_type *>(pHead));
124 return base_class::find_at_( h, val, cmp );
127 bool insert_aux_node( dummy_node_type * pNode )
129 return base_class::insert_aux_node( pNode );
131 bool insert_aux_node( dummy_node_type * pHead, dummy_node_type * pNode )
133 bucket_head_type h(static_cast<list_node_type *>(pHead));
134 return base_class::insert_aux_node( h, pNode );
141 ordered_list_wrapper m_List ; ///< Ordered list containing split-list items
142 bucket_table m_Buckets ; ///< bucket table
143 atomics::atomic<size_t> m_nBucketCountLog2 ; ///< log2( current bucket count )
144 item_counter m_ItemCounter ; ///< Item counter
145 hash m_HashFunctor ; ///< Hash functor
149 typedef cds::details::Allocator< dummy_node_type, typename options::allocator > dummy_node_allocator;
150 static dummy_node_type * alloc_dummy_node( size_t nHash )
152 return dummy_node_allocator().New( nHash );
154 static void free_dummy_node( dummy_node_type * p )
156 dummy_node_allocator().Delete( p );
159 /// Calculates hash value of \p key
160 template <typename Q>
161 size_t hash_value( Q const& key ) const
163 return m_HashFunctor( key );
166 size_t bucket_no( size_t nHash ) const
168 return nHash & ( (1 << m_nBucketCountLog2.load(atomics::memory_order_relaxed)) - 1 );
171 static size_t parent_bucket( size_t nBucket )
173 assert( nBucket > 0 );
174 return nBucket & ~( 1 << bitop::MSBnz( nBucket ) );
177 dummy_node_type * init_bucket( size_t nBucket )
179 assert( nBucket > 0 );
180 size_t nParent = parent_bucket( nBucket );
182 dummy_node_type * pParentBucket = m_Buckets.bucket( nParent );
183 if ( pParentBucket == nullptr ) {
184 pParentBucket = init_bucket( nParent );
187 assert( pParentBucket != nullptr );
189 // Allocate a dummy node for new bucket
191 dummy_node_type * pBucket = alloc_dummy_node( split_list::dummy_hash( nBucket ) );
192 if ( m_List.insert_aux_node( pParentBucket, pBucket ) ) {
193 m_Buckets.bucket( nBucket, pBucket );
196 free_dummy_node( pBucket );
199 // Another thread set the bucket. Wait while it done
201 // In this point, we must wait while nBucket is empty.
202 // The compiler can decide that waiting loop can be "optimized" (stripped)
203 // To prevent this situation, we use waiting on volatile bucket_head_ptr pointer.
207 dummy_node_type volatile * p = m_Buckets.bucket( nBucket );
208 if ( p && p != nullptr )
209 return const_cast<dummy_node_type *>( p );
214 dummy_node_type * get_bucket( size_t nHash )
216 size_t nBucket = bucket_no( nHash );
218 dummy_node_type * pHead = m_Buckets.bucket( nBucket );
219 if ( pHead == nullptr )
220 pHead = init_bucket( nBucket );
222 assert( pHead->is_dummy() );
229 // GC and OrderedList::gc must be the same
230 static_assert(( std::is_same<gc, typename ordered_list::gc>::value ), "GC and OrderedList::gc must be the same");
232 // atomicity::empty_item_counter is not allowed as a item counter
233 static_assert(( !std::is_same<item_counter, atomicity::empty_item_counter>::value ), "atomicity::empty_item_counter is not allowed as a item counter");
235 // Initialize bucket 0
236 dummy_node_type * pNode = alloc_dummy_node( 0 /*split_list::dummy_hash(0)*/ );
238 // insert_aux_node cannot return false for empty list
239 CDS_VERIFY( m_List.insert_aux_node( pNode ));
241 m_Buckets.bucket( 0, pNode );
244 void inc_item_count()
246 size_t sz = m_nBucketCountLog2.load(atomics::memory_order_relaxed);
247 if ( ( ++m_ItemCounter >> sz ) > m_Buckets.load_factor() && ((size_t)(1 << sz )) < m_Buckets.capacity() )
249 m_nBucketCountLog2.compare_exchange_strong( sz, sz + 1, atomics::memory_order_seq_cst, atomics::memory_order_relaxed );
256 /// Initialize split-ordered list of default capacity
258 The default capacity is defined in bucket table constructor.
259 See split_list::expandable_bucket_table, split_list::static_ducket_table
260 which selects by split_list::dynamic_bucket_table option.
263 : m_nBucketCountLog2(1)
268 /// Initialize split-ordered list
270 size_t nItemCount ///< estimate average of item count
271 , size_t nLoadFactor = 1 ///< load factor - average item count per bucket. Small integer up to 10, default is 1.
273 : m_Buckets( nItemCount, nLoadFactor )
274 , m_nBucketCountLog2(1)
282 The function inserts \p val in the set if it does not contain
283 an item with key equal to \p val.
285 Returns \p true if \p val is placed into the set, \p false otherwise.
287 bool insert( value_type& val )
289 return insert_( val ) != end();
292 /// Ensures that the \p item exists in the set
294 The operation performs inserting or changing data with lock-free manner.
296 If the item \p val not found in the set, then \p val is inserted into the set.
297 Otherwise, the functor \p func is called with item found.
298 The functor signature is:
300 struct ensure_functor {
301 void operator()( bool bNew, value_type& item, value_type& val );
305 - \p bNew - \p true if the item has been inserted, \p false otherwise
306 - \p item - item of the set
307 - \p val - argument \p val passed into the \p ensure function
308 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
309 refers to the same thing.
311 The functor can change non-key fields of the \p item; however, \p func must guarantee
312 that during changing no any other modifications could be made on this item by concurrent threads.
314 You can pass \p func argument by value by reference using <tt>boost::ref</tt> or cds::ref.
316 Returns std::pair<bool, bool> where \p first is \p true if operation is successfull,
317 \p second is \p true if new item has been added or \p false if the item with given key
318 already is in the set.
320 template <typename Func>
321 std::pair<bool, bool> ensure( value_type& val, Func func )
323 std::pair<iterator, bool> ret = ensure_( val, func );
324 return std::make_pair( ret.first != end(), ret.second );
327 /// Finds the key \p val
328 /** \anchor cds_intrusive_SplitListSet_nogc_find_val
329 The function searches the item with key equal to \p val
330 and returns pointer to item found or , and \p nullptr otherwise.
332 Note the hash functor specified for class \p Traits template parameter
333 should accept a parameter of type \p Q that can be not the same as \p value_type.
335 template <typename Q>
336 value_type * find( Q const & val )
338 iterator it = find_( val );
344 /// Finds the key \p val with \p pred predicate for comparing
346 The function is an analog of \ref cds_intrusive_SplitListSet_nogc_find_val "find(Q const&)"
347 but \p cmp is used for key compare.
348 \p Less has the interface like \p std::less.
349 \p cmp must imply the same element order as the comparator used for building the set.
351 template <typename Q, typename Less>
352 value_type * find_with( Q const& val, Less pred )
354 iterator it = find_with_( val, pred );
360 /// Finds the key \p val
361 /** \anchor cds_intrusive_SplitListSet_nogc_find_func
362 The function searches the item with key equal to \p val and calls the functor \p f for item found.
363 The interface of \p Func functor is:
366 void operator()( value_type& item, Q& val );
369 where \p item is the item found, \p val is the <tt>find</tt> function argument.
371 You can pass \p f argument by value or by reference using <tt>boost::ref</tt> or cds::ref.
373 The functor can change non-key fields of \p item.
374 The functor does not serialize simultaneous access to the set \p item. If such access is
375 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
377 The \p val argument is non-const since it can be used as \p f functor destination i.e., the functor
378 may modify both arguments.
380 Note the hash functor specified for class \p Traits template parameter
381 should accept a parameter of type \p Q that can be not the same as \p value_type.
383 The function returns \p true if \p val is found, \p false otherwise.
385 template <typename Q, typename Func>
386 bool find( Q& val, Func f )
388 return find_( val, key_comparator(), f );
391 /// Finds the key \p val with \p pred predicate for comparing
393 The function is an analog of \ref cds_intrusive_SplitListSet_nogc_find_func "find(Q&, Func)"
394 but \p cmp is used for key compare.
395 \p Less has the interface like \p std::less.
396 \p cmp must imply the same element order as the comparator used for building the set.
398 template <typename Q, typename Less, typename Func>
399 bool find_with( Q& val, Less pred, Func f )
401 return find_( val, typename wrapped_ordered_list::template make_compare_from_less<Less>(), f );
404 /// Find the key \p val
405 /** \anchor cds_intrusive_SplitListSet_nogc_find_cfunc
406 The function searches the item with key equal to \p val and calls the functor \p f for item found.
407 The interface of \p Func functor is:
410 void operator()( value_type& item, Q const& val );
413 where \p item is the item found, \p val is the <tt>find</tt> function argument.
415 You can pass \p f argument by value or by reference using <tt>boost::ref</tt> or cds::ref.
417 The functor can change non-key fields of \p item.
418 The functor does not serialize simultaneous access to the set \p item. If such access is
419 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
421 Note the hash functor specified for class \p Traits template parameter
422 should accept a parameter of type \p Q that can be not the same as \p value_type.
424 The function returns \p true if \p val is found, \p false otherwise.
426 template <typename Q, typename Func>
427 bool find( Q const& val, Func f )
429 return find_( val, key_comparator(), f );
432 /// Finds the key \p val with \p pred predicate for comparing
434 The function is an analog of \ref cds_intrusive_SplitListSet_nogc_find_cfunc "find(Q const&, Func)"
435 but \p cmp is used for key compare.
436 \p Less has the interface like \p std::less.
437 \p cmp must imply the same element order as the comparator used for building the set.
439 template <typename Q, typename Less, typename Func>
440 bool find_with( Q const& val, Less pred, Func f )
442 return find_( val, typename wrapped_ordered_list::template make_compare_from_less<Less>(), f );
445 /// Checks if the set is empty
447 Emptiness is checked by item counting: if item count is zero then the set is empty.
448 Thus, the correct item counting feature is an important part of split-list implementation.
455 /// Returns item count in the set
458 return m_ItemCounter;
463 template <bool IsConst>
465 :public split_list::details::iterator_type<node_traits, ordered_list, IsConst>
467 typedef split_list::details::iterator_type<node_traits, ordered_list, IsConst> iterator_base_class;
468 typedef typename iterator_base_class::list_iterator list_iterator;
471 : iterator_base_class()
474 iterator_type( iterator_type const& src )
475 : iterator_base_class( src )
478 // This ctor should be protected...
479 iterator_type( list_iterator itCur, list_iterator itEnd )
480 : iterator_base_class( itCur, itEnd )
488 The forward iterator for a split-list has some features:
489 - it has no post-increment operator
490 - it depends on iterator of underlying \p OrderedList
492 typedef iterator_type<false> iterator;
493 /// Const forward iterator
495 For iterator's features and requirements see \ref iterator
497 typedef iterator_type<true> const_iterator;
499 /// Returns a forward iterator addressing the first element in a split-list
501 For empty list \code begin() == end() \endcode
505 return iterator( m_List.begin(), m_List.end() );
508 /// Returns an iterator that addresses the location succeeding the last element in a split-list
510 Do not use the value returned by <tt>end</tt> function to access any item.
512 The returned value can be used only to control reaching the end of the split-list.
513 For empty list \code begin() == end() \endcode
517 return iterator( m_List.end(), m_List.end() );
520 /// Returns a forward const iterator addressing the first element in a split-list
522 const_iterator begin() const
524 return const_iterator( m_List.begin(), m_List.end() );
526 const_iterator cbegin()
528 return const_iterator( m_List.cbegin(), m_List.cend() );
532 /// Returns an const iterator that addresses the location succeeding the last element in a split-list
534 const_iterator end() const
536 return const_iterator( m_List.end(), m_List.end() );
538 const_iterator cend()
540 return const_iterator( m_List.cend(), m_List.cend() );
546 iterator insert_( value_type& val )
548 size_t nHash = hash_value( val );
549 dummy_node_type * pHead = get_bucket( nHash );
550 assert( pHead != nullptr );
552 node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
554 list_iterator it = m_List.insert_at_( pHead, val );
555 if ( it != m_List.end() ) {
557 return iterator( it, m_List.end() );
562 template <typename Func>
563 std::pair<iterator, bool> ensure_( value_type& val, Func func )
565 size_t nHash = hash_value( val );
566 dummy_node_type * pHead = get_bucket( nHash );
567 assert( pHead != nullptr );
569 node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
571 std::pair<list_iterator, bool> ret = m_List.ensure_at_( pHead, val, func );
572 if ( ret.first != m_List.end() ) {
575 return std::make_pair( iterator(ret.first, m_List.end()), ret.second );
577 return std::make_pair( end(), ret.second );
580 template <typename Q, typename Less >
581 iterator find_with_( Q const& val, Less pred )
583 size_t nHash = hash_value( val );
584 split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash( nHash ));
585 dummy_node_type * pHead = get_bucket( nHash );
586 assert( pHead != nullptr );
588 return iterator( m_List.find_at_( pHead, sv, typename wrapped_ordered_list::template make_compare_from_less<Less>() ), m_List.end() );
591 template <typename Q>
592 iterator find_( Q const& val )
594 size_t nHash = hash_value( val );
595 split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash( nHash ));
596 dummy_node_type * pHead = get_bucket( nHash );
597 assert( pHead != nullptr );
599 return iterator( m_List.find_at_( pHead, sv, key_comparator() ), m_List.end() );
603 template <typename Q, typename Compare, typename Func>
604 bool find_( Q& val, Compare cmp, Func f )
606 size_t nHash = hash_value( val );
607 split_list::details::search_value_type<Q> sv( val, split_list::regular_hash( nHash ));
608 dummy_node_type * pHead = get_bucket( nHash );
609 assert( pHead != nullptr );
610 # ifdef CDS_CXX11_LAMBDA_SUPPORT
611 return m_List.find_at( pHead, sv, cmp,
612 [&f](value_type& item, split_list::details::search_value_type<Q>& val){ cds::unref(f)(item, val.val ); });
614 split_list::details::find_functor_wrapper<Func> ffw( f );
615 return m_List.find_at( pHead, sv, cmp, cds::ref(ffw) );
622 }} // namespace cds::intrusive
624 #endif // #ifndef __CDS_INTRUSIVE_SPLIT_LIST_NOGC_H