3 #ifndef __CDS_INTRUSIVE_LAZY_LIST_NOGC_H
4 #define __CDS_INTRUSIVE_LAZY_LIST_NOGC_H
6 #include <cds/intrusive/lazy_list_base.h>
7 #include <cds/gc/nogc.h>
9 namespace cds { namespace intrusive {
11 /// Lazy list node for gc::nogc
14 - Tag - a tag used to distinguish between different implementation
16 template <typename Lock, typename Tag>
17 struct node<gc::nogc, Lock, Tag>
19 typedef gc::nogc gc ; ///< Garbage collector
20 typedef Lock lock_type ; ///< Lock type
21 typedef Tag tag ; ///< tag
23 atomics::atomic<node *> m_pNext ; ///< pointer to the next node in the list
24 mutable lock_type m_Lock ; ///< Node lock
30 } // namespace lazy_list
33 /// Lazy ordered single-linked list (template specialization for gc::nogc)
34 /** @ingroup cds_intrusive_list
35 \anchor cds_intrusive_LazyList_nogc
37 This specialization is intended for so-called persistent usage when no item
38 reclamation may be performed. The class does not support deleting of list item.
40 See \ref cds_intrusive_LazyList_hp "LazyList" for description of template parameters.
42 The interface of the specialization is a slightly different.
44 The gc::nogc specialization of LazyList accepts following template argument list
45 \p Options of cds::intrusive::lazy_list::make_traits metafunction:
46 - opt::hook - hook used. Possible values are: lazy_list::base_hook, lazy_list::member_hook, lazy_list::traits_hook.
47 If the option is not specified, <tt>lazy_list::base_hook<></tt> and gc::HP is used.
48 - opt::compare - key comparison functor. No default functor is provided.
49 If the option is not specified, the opt::less is used.
50 - opt::less - specifies binary predicate used for key comparison. Default is \p std::less<T>.
51 - opt::back_off - back-off strategy used. If the option is not specified, the cds::backoff::empty is used.
52 - opt::disposer - the functor used for dispose removed items. Default is opt::v::empty_disposer. The disposer
53 provided is used only in \ref clear() function.
54 - opt::link_checker - the type of node's link fields checking. Default is \ref opt::debug_check_link
55 - opt::item_counter - the type of item counting feature. Default is \ref atomicity::empty_item_counter that is no item counting.
56 - opt::memory_model - C++ memory ordering model. Can be opt::v::relaxed_ordering (relaxed memory model, the default)
57 or opt::v::sequential_consistent (sequentially consisnent memory model).
59 The opt::allocator and opt::back_off is not used for this specialization.
64 #ifdef CDS_DOXYGEN_INVOKED
65 ,class Traits = lazy_list::type_traits
70 class LazyList<gc::nogc, T, Traits>
73 typedef T value_type ; ///< type of value stored in the list
74 typedef Traits options ; ///< Traits template parameter
76 typedef typename options::hook hook ; ///< hook type
77 typedef typename hook::node_type node_type ; ///< node type
79 # ifdef CDS_DOXYGEN_INVOKED
80 typedef implementation_defined key_comparator ; ///< key comparison functor based on opt::compare and opt::less option setter.
82 typedef typename opt::details::make_comparator< value_type, options >::type key_comparator;
85 typedef typename options::disposer disposer ; ///< disposer used
86 typedef typename get_node_traits< value_type, node_type, hook>::type node_traits ; ///< node traits
87 typedef typename lazy_list::get_link_checker< node_type, options::link_checker >::type link_checker ; ///< link checker
89 typedef gc::nogc gc ; ///< Garbage collector
90 typedef typename options::back_off back_off ; ///< back-off strategy (not used)
91 typedef typename options::item_counter item_counter ; ///< Item counting policy used
92 typedef typename options::memory_model memory_model; ///< C++ memory ordering (see lazy_list::type_traits::memory_model)
95 // Rebind options (split-list support)
96 template <CDS_DECL_OPTIONS8>
97 struct rebind_options {
101 , typename cds::opt::make_options< options, CDS_OPTIONS8>::type
107 typedef node_type * auxiliary_head ; ///< Auxiliary head type (for split-list support)
110 node_type m_Head ; ///< List head (dummy node)
111 node_type m_Tail; ///< List tail (dummy node)
112 item_counter m_ItemCounter ; ///< Item counter
116 /// Position pointer for item search
118 node_type * pPred ; ///< Previous node
119 node_type * pCur ; ///< Current node
121 /// Locks nodes \p pPred and \p pCur
124 pPred->m_Lock.lock();
128 /// Unlocks nodes \p pPred and \p pCur
131 pCur->m_Lock.unlock();
132 pPred->m_Lock.unlock();
136 class auto_lock_position {
139 auto_lock_position( position& pos )
144 ~auto_lock_position()
153 void clear_links( node_type * pNode )
155 pNode->m_pNext.store( nullptr, memory_model::memory_order_relaxed );
158 template <class Disposer>
159 void dispose_node( node_type * pNode, Disposer disp )
161 clear_links( pNode );
162 cds::unref(disp)( node_traits::to_value_ptr( *pNode ));
165 template <class Disposer>
166 void dispose_value( value_type& val, Disposer disp )
168 dispose_node( node_traits::to_node_ptr( val ), disp );
171 void link_node( node_type * pNode, node_type * pPred, node_type * pCur )
173 assert( pPred->m_pNext.load(memory_model::memory_order_relaxed) == pCur );
175 pNode->m_pNext.store( pCur, memory_model::memory_order_release );
176 pPred->m_pNext.store( pNode, memory_model::memory_order_release );
182 template <bool IsConst>
185 friend class LazyList;
188 value_type * m_pNode;
192 assert( m_pNode != nullptr );
194 node_type * pNode = node_traits::to_node_ptr( m_pNode );
195 node_type * pNext = pNode->m_pNext.load(memory_model::memory_order_relaxed);
196 if ( pNext != nullptr )
197 m_pNode = node_traits::to_value_ptr( pNext );
200 iterator_type( node_type * pNode )
202 m_pNode = node_traits::to_value_ptr( pNode );
206 typedef typename cds::details::make_const_type<value_type, IsConst>::pointer value_ptr;
207 typedef typename cds::details::make_const_type<value_type, IsConst>::reference value_ref;
213 iterator_type( const iterator_type& src )
214 : m_pNode( src.m_pNode )
217 value_ptr operator ->() const
222 value_ref operator *() const
224 assert( m_pNode != nullptr );
229 iterator_type& operator ++()
236 iterator_type operator ++(int)
238 iterator_type i(*this);
243 iterator_type& operator = (const iterator_type& src)
245 m_pNode = src.m_pNode;
250 bool operator ==(iterator_type<C> const& i ) const
252 return m_pNode == i.m_pNode;
255 bool operator !=(iterator_type<C> const& i ) const
257 return m_pNode != i.m_pNode;
264 typedef iterator_type<false> iterator;
265 /// Const forward iterator
266 typedef iterator_type<true> const_iterator;
268 /// Returns a forward iterator addressing the first element in a list
270 For empty list \code begin() == end() \endcode
274 iterator it( &m_Head );
275 ++it ; // skip dummy head
279 /// Returns an iterator that addresses the location succeeding the last element in a list
281 Do not use the value returned by <tt>end</tt> function to access any item.
283 The returned value can be used only to control reaching the end of the list.
284 For empty list \code begin() == end() \endcode
288 return iterator( &m_Tail );
291 /// Returns a forward const iterator addressing the first element in a list
292 const_iterator begin() const
294 const_iterator it( const_cast<node_type *>( &m_Head ));
295 ++it ; // skip dummy head
299 /// Returns an const iterator that addresses the location succeeding the last element in a list
300 const_iterator end() const
302 return const_iterator( const_cast<node_type *>( &m_Tail ));
306 /// Default constructor initializes empty list
309 static_assert( (std::is_same< gc, typename node_type::gc >::value), "GC and node_type::gc must be the same type" );
311 m_Head.m_pNext.store( &m_Tail, memory_model::memory_order_relaxed );
314 /// Destroys the list object
319 assert( m_Head.m_pNext.load(memory_model::memory_order_relaxed) == &m_Tail );
320 m_Head.m_pNext.store( nullptr, memory_model::memory_order_relaxed );
325 The function inserts \p val in the list if the list does not contain
326 an item with key equal to \p val.
328 Returns \p true if \p val is linked into the list, \p false otherwise.
330 bool insert( value_type& val )
332 return insert_at( &m_Head, val );
335 /// Ensures that the \p item exists in the list
337 The operation performs inserting or changing data with lock-free manner.
339 If the item \p val not found in the list, then \p val is inserted into the list.
340 Otherwise, the functor \p func is called with item found.
341 The functor signature is:
344 void operator()( bool bNew, value_type& item, value_type& val );
348 - \p bNew - \p true if the item has been inserted, \p false otherwise
349 - \p item - item of the list
350 - \p val - argument \p val passed into the \p ensure function
351 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
352 refers to the same thing.
354 The functor may change non-key fields of the \p item.
355 While the functor \p f is calling the item \p item is locked.
357 You may pass \p func argument by reference using <tt>boost::ref</tt> or cds::ref.
359 Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
360 \p second is true if new item has been added or \p false if the item with \p key
361 already is in the list.
364 template <typename Func>
365 std::pair<bool, bool> ensure( value_type& val, Func func )
367 return ensure_at( &m_Head, val, func );
370 /// Finds the key \p val
371 /** \anchor cds_intrusive_LazyList_nogc_find_func
372 The function searches the item with key equal to \p val
373 and calls the functor \p f for item found.
374 The interface of \p Func functor is:
377 void operator()( value_type& item, Q& val );
380 where \p item is the item found, \p val is the <tt>find</tt> function argument.
382 You may pass \p f argument by reference using <tt>boost::ref</tt> or cds::ref.
384 The functor may change non-key fields of \p item.
385 While the functor \p f is calling the item found \p item is locked.
387 The function returns \p true if \p val is found, \p false otherwise.
389 template <typename Q, typename Func>
390 bool find( Q& val, Func f )
392 return find_at( &m_Head, val, key_comparator(), f );
395 /// Finds the key \p val
396 /** \anchor cds_intrusive_LazyList_nogc_find_cfunc
397 The function searches the item with key equal to \p val
398 and calls the functor \p f for item found.
399 The interface of \p Func functor is:
402 void operator()( value_type& item, Q const& val );
405 where \p item is the item found, \p val is the <tt>find</tt> function argument.
407 You may pass \p f argument by reference using <tt>boost::ref</tt> or cds::ref.
409 The functor may change non-key fields of \p item.
410 While the functor \p f is calling the item found \p item is locked.
412 The function returns \p true if \p val is found, \p false otherwise.
414 template <typename Q, typename Func>
415 bool find( Q const& val, Func f )
417 return find_at( &m_Head, val, key_comparator(), f );
420 /// Finds the key \p val using \p pred predicate for searching
422 The function is an analog of \ref cds_intrusive_LazyList_nogc_find_cfunc "find(Q const&, Func)"
423 but \p pred is used for key comparing.
424 \p Less functor has the interface like \p std::less.
425 \p pred must imply the same element order as the comparator used for building the list.
427 template <typename Q, typename Less, typename Func>
428 bool find_with( Q const& val, Less pred, Func f )
430 return find_at( &m_Head, val, cds::opt::details::make_comparator_from_less<Less>(), f );
433 /// Finds the key \p val using \p pred predicate for searching
435 The function is an analog of \ref cds_intrusive_LazyList_nogc_find_func "find(Q&, Func)"
436 but \p pred is used for key comparing.
437 \p Less functor has the interface like \p std::less.
438 \p pred must imply the same element order as the comparator used for building the list.
440 template <typename Q, typename Less, typename Func>
441 bool find_with( Q& val, Less pred, Func f )
443 return find_at( &m_Head, val, cds::opt::details::make_comparator_from_less<Less>(), f );
446 /// Finds the key \p val
447 /** \anchor cds_intrusive_LazyList_nogc_find_val
448 The function searches the item with key equal to \p val
449 and returns pointer to value found or \p nullptr.
451 template <typename Q>
452 value_type * find( Q const& val )
454 return find_at( &m_Head, val, key_comparator() );
457 /// Finds the key \p val using \p pred predicate for searching
459 The function is an analog of \ref cds_intrusive_LazyList_nogc_find_val "find(Q const&)"
460 but \p pred is used for key comparing.
461 \p Less functor has the interface like \p std::less.
462 \p pred must imply the same element order as the comparator used for building the list.
464 template <typename Q, typename Less>
465 value_type * find_with( Q const & val, Less pred )
467 return find_at( &m_Head, val, cds::opt::details::make_comparator_from_less<Less>() );
472 The function unlink all items from the list.
473 For each unlinked item the item disposer \p disp is called after unlinking.
475 This function is not thread-safe.
477 template <typename Disposer>
478 void clear( Disposer disp )
480 node_type * pHead = m_Head.m_pNext.exchange( &m_Tail, memory_model::memory_order_release );
482 while ( pHead != &m_Tail ) {
483 node_type * p = pHead->m_pNext.load(memory_model::memory_order_relaxed);
484 dispose_node( pHead, disp );
489 /// Clears the list using default disposer
491 The function clears the list using default (provided in class template) disposer functor.
498 /// Checks if the list is empty
501 return m_Head.m_pNext.load(memory_model::memory_order_relaxed) == &m_Tail;
504 /// Returns list's item count
506 The value returned depends on opt::item_counter option. For atomicity::empty_item_counter,
507 this function always returns 0.
509 <b>Warning</b>: even if you use real item counter and it returns 0, this fact is not mean that the list
510 is empty. To check list emptyness use \ref empty() method.
514 return m_ItemCounter.value();
519 // split-list support
520 bool insert_aux_node( node_type * pNode )
522 return insert_aux_node( &m_Head, pNode );
525 // split-list support
526 bool insert_aux_node( node_type * pHead, node_type * pNode )
528 assert( pHead != nullptr );
529 assert( pNode != nullptr );
531 // Hack: convert node_type to value_type.
532 // In principle, auxiliary node can be non-reducible to value_type
533 // We assume that comparator can correctly distinguish aux and regular node.
534 return insert_at( pHead, *node_traits::to_value_ptr( pNode ) );
537 bool insert_at( node_type * pHead, value_type& val )
539 link_checker::is_empty( node_traits::to_node_ptr( val ) );
544 search( pHead, val, pos, key_comparator() );
546 auto_lock_position alp( pos );
547 if ( validate( pos.pPred, pos.pCur )) {
548 if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
549 // failed: key already in list
553 link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
562 iterator insert_at_( node_type * pHead, value_type& val )
564 if ( insert_at( pHead, val ))
565 return iterator( node_traits::to_node_ptr( val ));
570 template <typename Func>
571 std::pair<iterator, bool> ensure_at_( node_type * pHead, value_type& val, Func func )
577 search( pHead, val, pos, key_comparator() );
579 auto_lock_position alp( pos );
580 if ( validate( pos.pPred, pos.pCur )) {
581 if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
582 // key already in the list
584 cds::unref(func)( false, *node_traits::to_value_ptr( *pos.pCur ) , val );
585 return std::make_pair( iterator( pos.pCur ), false );
589 link_checker::is_empty( node_traits::to_node_ptr( val ) );
591 link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
592 cds::unref(func)( true, val, val );
594 return std::make_pair( iterator( node_traits::to_node_ptr( val )), true );
601 template <typename Func>
602 std::pair<bool, bool> ensure_at( node_type * pHead, value_type& val, Func func )
604 std::pair<iterator, bool> ret = ensure_at_( pHead, val, func );
605 return std::make_pair( ret.first != end(), ret.second );
608 template <typename Q, typename Compare, typename Func>
609 bool find_at( node_type * pHead, Q& val, Compare cmp, Func f )
613 search( pHead, val, pos, cmp );
614 if ( pos.pCur != &m_Tail ) {
615 cds::lock::scoped_lock< typename node_type::lock_type> al( pos.pCur->m_Lock );
616 if ( cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 )
618 cds::unref(f)( *node_traits::to_value_ptr( *pos.pCur ), val );
625 template <typename Q, typename Compare>
626 value_type * find_at( node_type * pHead, Q& val, Compare cmp)
628 iterator it = find_at_( pHead, val, cmp );
634 template <typename Q, typename Compare>
635 iterator find_at_( node_type * pHead, Q& val, Compare cmp)
639 search( pHead, val, pos, cmp );
640 if ( pos.pCur != &m_Tail ) {
641 cds::lock::scoped_lock< typename node_type::lock_type> al( pos.pCur->m_Lock );
642 if ( cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 )
644 return iterator( pos.pCur );
654 template <typename Q, typename Compare>
655 void search( node_type * pHead, const Q& key, position& pos, Compare cmp )
657 const node_type * pTail = &m_Tail;
659 node_type * pCur = pHead;
660 node_type * pPrev = pHead;
662 while ( pCur != pTail && ( pCur == pHead || cmp( *node_traits::to_value_ptr( *pCur ), key ) < 0 )) {
664 pCur = pCur->m_pNext.load(memory_model::memory_order_acquire);
671 static bool validate( node_type * pPred, node_type * pCur )
673 return pPred->m_pNext.load(memory_model::memory_order_acquire) == pCur;
679 }} // namespace cds::intrusive
681 #endif // #ifndef __CDS_INTRUSIVE_LAZY_LIST_NOGC_H