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;
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 size_t sz = m_nBucketCountLog2.load(memory_model::memory_order_relaxed);
271 const size_t nBucketCount = static_cast<size_t>(1) << sz;
272 if ( nBucketCount < m_Buckets.capacity() ) {
273 // we may grow the bucket table
274 const size_t nLoadFactor = m_Buckets.load_factor();
275 if ( nMaxCount < max_item_count( nBucketCount, nLoadFactor ))
276 return; // someone already have updated m_nBucketCountLog2, so stop here
278 m_nMaxItemCount.compare_exchange_strong( nMaxCount, max_item_count( nBucketCount << 1, nLoadFactor ),
279 memory_model::memory_order_relaxed, atomics::memory_order_relaxed );
280 m_nBucketCountLog2.compare_exchange_strong( sz, sz + 1, memory_model::memory_order_relaxed, atomics::memory_order_relaxed );
283 m_nMaxItemCount.store( std::numeric_limits<size_t>::max(), memory_model::memory_order_relaxed );
289 /// Initialize split-ordered list of default capacity
291 The default capacity is defined in bucket table constructor.
292 See split_list::expandable_bucket_table, split_list::static_ducket_table
293 which selects by split_list::dynamic_bucket_table option.
296 : m_nBucketCountLog2(1)
297 , m_nMaxItemCount( max_item_count(2, m_Buckets.load_factor()) )
302 /// Initialize split-ordered list
304 size_t nItemCount ///< estimate average of item count
305 , size_t nLoadFactor = 1 ///< load factor - average item count per bucket. Small integer up to 10, default is 1.
307 : m_Buckets( nItemCount, nLoadFactor )
308 , m_nBucketCountLog2(1)
309 , m_nMaxItemCount( max_item_count(2, m_Buckets.load_factor()) )
317 The function inserts \p val in the set if it does not contain
318 an item with key equal to \p val.
320 Returns \p true if \p val is placed into the set, \p false otherwise.
322 bool insert( value_type& val )
324 return insert_( val ) != end();
327 /// Ensures that the \p item exists in the set
329 The operation performs inserting or changing data with lock-free manner.
331 If the item \p val not found in the set, then \p val is inserted into the set.
332 Otherwise, the functor \p func is called with item found.
333 The functor signature is:
335 struct ensure_functor {
336 void operator()( bool bNew, value_type& item, value_type& val );
340 - \p bNew - \p true if the item has been inserted, \p false otherwise
341 - \p item - item of the set
342 - \p val - argument \p val passed into the \p ensure function
343 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
344 refers to the same thing.
346 The functor can change non-key fields of the \p item.
348 Returns std::pair<bool, bool> where \p first is \p true if operation is successfull,
349 \p second is \p true if new item has been added or \p false if the item with given key
350 already is in the set.
352 @warning For \ref cds_intrusive_MichaelList_nogc "MichaelList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
353 \ref cds_intrusive_LazyList_nogc "LazyList" provides exclusive access to inserted item and does not require any node-level
356 template <typename Func>
357 std::pair<bool, bool> ensure( value_type& val, Func func )
359 std::pair<iterator, bool> ret = ensure_( val, func );
360 return std::make_pair( ret.first != end(), ret.second );
363 /// Finds the key \p key
364 /** \anchor cds_intrusive_SplitListSet_nogc_find_val
365 The function searches the item with key equal to \p key
366 and returns pointer to item found or , and \p nullptr otherwise.
368 Note the hash functor specified for class \p Traits template parameter
369 should accept a parameter of type \p Q that can be not the same as \p value_type.
371 template <typename Q>
372 value_type * find( Q const& key )
374 iterator it = find_( key );
380 /// Finds the key \p key with \p pred predicate for comparing
382 The function is an analog of \ref cds_intrusive_SplitListSet_nogc_find_val "find(Q const&)"
383 but \p cmp is used for key compare.
384 \p Less has the interface like \p std::less.
385 \p cmp must imply the same element order as the comparator used for building the set.
387 template <typename Q, typename Less>
388 value_type * find_with( Q const& key, Less pred )
390 iterator it = find_with_( key, pred );
396 /// Finds the key \p key
397 /** \anchor cds_intrusive_SplitListSet_nogc_find_func
398 The function searches the item with key equal to \p key and calls the functor \p f for item found.
399 The interface of \p Func functor is:
402 void operator()( value_type& item, Q& key );
405 where \p item is the item found, \p key is the <tt>find</tt> function argument.
407 The functor can change non-key fields of \p item.
408 The functor does not serialize simultaneous access to the set \p item. If such access is
409 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
411 Note the hash functor specified for class \p Traits template parameter
412 should accept a parameter of type \p Q that can be not the same as \p value_type.
414 The function returns \p true if \p key is found, \p false otherwise.
416 template <typename Q, typename Func>
417 bool find( Q& key, Func f )
419 return find_( key, key_comparator(), f );
422 template <typename Q, typename Func>
423 bool find( Q const& key, Func f )
425 return find_( key, key_comparator(), f );
429 /// Finds the key \p key with \p pred predicate for comparing
431 The function is an analog of \ref cds_intrusive_SplitListSet_nogc_find_func "find(Q&, Func)"
432 but \p cmp is used for key compare.
433 \p Less has the interface like \p std::less.
434 \p cmp must imply the same element order as the comparator used for building the set.
436 template <typename Q, typename Less, typename Func>
437 bool find_with( Q& key, Less pred, Func f )
440 return find_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>(), f );
443 template <typename Q, typename Less, typename Func>
444 bool find_with( Q const& key, Less pred, Func f )
447 return find_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>(), f );
451 /// Checks if the set is empty
453 Emptiness is checked by item counting: if item count is zero then the set is empty.
454 Thus, the correct item counting feature is an important part of split-list implementation.
461 /// Returns item count in the set
464 return m_ItemCounter;
467 /// Returns internal statistics
468 stat const& statistics() const
475 template <bool IsConst>
477 : public split_list::details::iterator_type<node_traits, ordered_list, IsConst>
479 typedef split_list::details::iterator_type<node_traits, ordered_list, IsConst> iterator_base_class;
480 typedef typename iterator_base_class::list_iterator list_iterator;
483 : iterator_base_class()
486 iterator_type( iterator_type const& src )
487 : iterator_base_class( src )
490 // This ctor should be protected...
491 iterator_type( list_iterator itCur, list_iterator itEnd )
492 : iterator_base_class( itCur, itEnd )
500 The forward iterator for a split-list has some features:
501 - it has no post-increment operator
502 - it depends on iterator of underlying \p OrderedList
504 typedef iterator_type<false> iterator;
505 /// Const forward iterator
507 For iterator's features and requirements see \ref iterator
509 typedef iterator_type<true> const_iterator;
511 /// Returns a forward iterator addressing the first element in a split-list
513 For empty list \code begin() == end() \endcode
517 return iterator( m_List.begin(), m_List.end() );
520 /// Returns an iterator that addresses the location succeeding the last element in a split-list
522 Do not use the value returned by <tt>end</tt> function to access any item.
524 The returned value can be used only to control reaching the end of the split-list.
525 For empty list \code begin() == end() \endcode
529 return iterator( m_List.end(), m_List.end() );
532 /// Returns a forward const iterator addressing the first element in a split-list
534 const_iterator begin() const
536 return const_iterator( m_List.begin(), m_List.end() );
538 const_iterator cbegin() const
540 return const_iterator( m_List.cbegin(), m_List.cend() );
544 /// Returns an const iterator that addresses the location succeeding the last element in a split-list
546 const_iterator end() const
548 return const_iterator( m_List.end(), m_List.end() );
550 const_iterator cend() const
552 return const_iterator( m_List.cend(), m_List.cend() );
558 iterator insert_( value_type& val )
560 size_t nHash = hash_value( val );
561 dummy_node_type * pHead = get_bucket( nHash );
562 assert( pHead != nullptr );
564 node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
566 list_iterator it = m_List.insert_at_( pHead, val );
567 if ( it != m_List.end() ) {
569 m_Stat.onInsertSuccess();
570 return iterator( it, m_List.end() );
572 m_Stat.onInsertFailed();
576 template <typename Func>
577 std::pair<iterator, bool> ensure_( value_type& val, Func func )
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 std::pair<list_iterator, bool> ret = m_List.ensure_at_( pHead, val, func );
586 if ( ret.first != m_List.end() ) {
589 m_Stat.onEnsureNew();
592 m_Stat.onEnsureExist();
593 return std::make_pair( iterator(ret.first, m_List.end()), ret.second );
595 return std::make_pair( end(), ret.second );
598 template <typename Q, typename Less >
599 iterator find_with_( Q& val, Less pred )
602 size_t nHash = hash_value( val );
603 split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash( nHash ));
604 dummy_node_type * pHead = get_bucket( nHash );
605 assert( pHead != nullptr );
607 auto it = m_List.find_at_( pHead, sv, typename wrapped_ordered_list::template make_compare_from_less<Less>() );
608 m_Stat.onFind( it != m_List.end() );
609 return iterator( it, m_List.end() );
612 template <typename Q>
613 iterator find_( Q const& val )
615 size_t nHash = hash_value( val );
616 split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash( nHash ));
617 dummy_node_type * pHead = get_bucket( nHash );
618 assert( pHead != nullptr );
620 auto it = m_List.find_at_( pHead, sv, key_comparator() );
621 m_Stat.onFind( it != m_List.end() );
622 return iterator( it, m_List.end() );
625 template <typename Q, typename Compare, typename Func>
626 bool find_( Q& val, Compare cmp, Func f )
628 size_t nHash = hash_value( val );
629 split_list::details::search_value_type<Q> sv( val, split_list::regular_hash( nHash ));
630 dummy_node_type * pHead = get_bucket( nHash );
631 assert( pHead != nullptr );
632 return m_Stat.onFind( m_List.find_at( pHead, sv, cmp,
633 [&f](value_type& item, split_list::details::search_value_type<Q>& val){ f(item, val.val ); }));
639 }} // namespace cds::intrusive
641 #endif // #ifndef CDSLIB_INTRUSIVE_SPLIT_LIST_NOGC_H