3 #ifndef CDSLIB_INTRUSIVE_LAZY_LIST_NOGC_H
4 #define CDSLIB_INTRUSIVE_LAZY_LIST_NOGC_H
6 #include <mutex> // unique_lock
7 #include <cds/intrusive/details/lazy_list_base.h>
8 #include <cds/gc/nogc.h>
10 namespace cds { namespace intrusive {
12 /// Lazy list node for \p gc::nogc
15 - Lock - lock type. Default is \p cds::sync::spin
16 - Tag - a \ref cds_intrusive_hook_tag "tag"
19 #ifdef CDS_DOXYGEN_INVOKED
20 typename Lock = cds::sync::spin,
21 typename Tag = opt::none
27 struct node<gc::nogc, Lock, Tag>
29 typedef gc::nogc gc; ///< Garbage collector
30 typedef Lock lock_type; ///< Lock type
31 typedef Tag tag; ///< tag
33 atomics::atomic<node *> m_pNext; ///< pointer to the next node in the list
34 mutable lock_type m_Lock; ///< Node lock
40 } // namespace lazy_list
43 /// Lazy single-linked list (template specialization for \p gc::nogc)
44 /** @ingroup cds_intrusive_list
45 \anchor cds_intrusive_LazyList_nogc
47 This specialization is append-only list when no item
48 reclamation may be performed. The class does not support deleting of list item.
50 The list can be ordered if \p Traits::sort is \p true that is default
51 or unordered otherwise. Unordered list can be maintained by \p equal_to
52 relationship (\p Traits::equal_to), but for the ordered list \p less
53 or \p compare relations should be specified in \p Traits.
55 See \ref cds_intrusive_LazyList_hp "LazyList" for description of template parameters.
59 #ifdef CDS_DOXYGEN_INVOKED
60 ,class Traits = lazy_list::traits
65 class LazyList<gc::nogc, T, Traits>
68 typedef gc::nogc gc; ///< Garbage collector
69 typedef T value_type; ///< type of value stored in the list
70 typedef Traits traits; ///< Traits template parameter
72 typedef typename traits::hook hook; ///< hook type
73 typedef typename hook::node_type node_type; ///< node type
74 static CDS_CONSTEXPR bool const c_bSort = traits::sort; ///< List type: ordered (\p true) or unordered (\p false)
76 # ifdef CDS_DOXYGEN_INVOKED
77 /// Key comparing functor
79 - for ordered list, the functor is based on \p traits::compare or \p traits::less
80 - for unordered list, the functor is based on \p traits::equal_to, \p traits::compare or \p traits::less
82 typedef implementation_defined key_comparator;
84 typedef typename std::conditional< c_bSort,
85 typename opt::details::make_comparator< value_type, traits >::type,
86 typename opt::details::make_equal_to< value_type, traits >::type
87 >::type key_comparator;
89 typedef typename traits::back_off back_off; ///< Back-off strategy
90 typedef typename traits::disposer disposer; ///< disposer
91 typedef typename get_node_traits< value_type, node_type, hook>::type node_traits; ///< node traits
92 typedef typename lazy_list::get_link_checker< node_type, traits::link_checker >::type link_checker; ///< link checker
94 typedef typename traits::item_counter item_counter; ///< Item counting policy used
95 typedef typename traits::memory_model memory_model; ///< C++ memory ordering (see lazy_list::traits::memory_model)
98 // Rebind traits (split-list support)
99 template <typename... Options>
100 struct rebind_traits {
104 , typename cds::opt::make_options< traits, Options...>::type
110 typedef node_type * auxiliary_head ; ///< Auxiliary head type (for split-list support)
113 node_type m_Head; ///< List head (dummy node)
114 node_type m_Tail; ///< List tail (dummy node)
115 item_counter m_ItemCounter; ///< Item counter
119 /// Position pointer for item search
121 node_type * pPred ; ///< Previous node
122 node_type * pCur ; ///< Current node
124 /// Locks nodes \p pPred and \p pCur
127 pPred->m_Lock.lock();
131 /// Unlocks nodes \p pPred and \p pCur
134 pCur->m_Lock.unlock();
135 pPred->m_Lock.unlock();
139 class auto_lock_position {
142 auto_lock_position( position& pos )
147 ~auto_lock_position()
156 void clear_links( node_type * pNode )
158 pNode->m_pNext.store( nullptr, memory_model::memory_order_relaxed );
161 template <class Disposer>
162 void dispose_node( node_type * pNode, Disposer disp )
164 clear_links( pNode );
165 disp( node_traits::to_value_ptr( *pNode ));
168 template <class Disposer>
169 void dispose_value( value_type& val, Disposer disp )
171 dispose_node( node_traits::to_node_ptr( val ), disp );
174 void link_node( node_type * pNode, node_type * pPred, node_type * pCur )
176 assert( pPred->m_pNext.load(memory_model::memory_order_relaxed) == pCur );
178 pNode->m_pNext.store( pCur, memory_model::memory_order_release );
179 pPred->m_pNext.store( pNode, memory_model::memory_order_release );
185 template <bool IsConst>
188 friend class LazyList;
191 value_type * m_pNode;
195 assert( m_pNode != nullptr );
197 node_type * pNode = node_traits::to_node_ptr( m_pNode );
198 node_type * pNext = pNode->m_pNext.load(memory_model::memory_order_relaxed);
199 if ( pNext != nullptr )
200 m_pNode = node_traits::to_value_ptr( pNext );
203 iterator_type( node_type * pNode )
205 m_pNode = node_traits::to_value_ptr( pNode );
209 typedef typename cds::details::make_const_type<value_type, IsConst>::pointer value_ptr;
210 typedef typename cds::details::make_const_type<value_type, IsConst>::reference value_ref;
216 iterator_type( const iterator_type& src )
217 : m_pNode( src.m_pNode )
220 value_ptr operator ->() const
225 value_ref operator *() const
227 assert( m_pNode != nullptr );
232 iterator_type& operator ++()
239 iterator_type operator ++(int)
241 iterator_type i(*this);
246 iterator_type& operator = (const iterator_type& src)
248 m_pNode = src.m_pNode;
253 bool operator ==(iterator_type<C> const& i ) const
255 return m_pNode == i.m_pNode;
258 bool operator !=(iterator_type<C> const& i ) const
260 return m_pNode != i.m_pNode;
267 typedef iterator_type<false> iterator;
268 /// Const forward iterator
269 typedef iterator_type<true> const_iterator;
271 /// Returns a forward iterator addressing the first element in a list
273 For empty list \code begin() == end() \endcode
277 iterator it( &m_Head );
278 ++it ; // skip dummy head
282 /// Returns an iterator that addresses the location succeeding the last element in a list
284 Do not use the value returned by <tt>end</tt> function to access any item.
286 The returned value can be used only to control reaching the end of the list.
287 For empty list \code begin() == end() \endcode
291 return iterator( &m_Tail );
294 /// Returns a forward const iterator addressing the first element in a list
295 const_iterator begin() const
299 /// Returns a forward const iterator addressing the first element in a list
300 const_iterator cbegin() const
302 const_iterator it( const_cast<node_type *>(&m_Head) );
303 ++it; // skip dummy head
307 /// Returns an const iterator that addresses the location succeeding the last element in a list
308 const_iterator end() const
312 /// Returns an const iterator that addresses the location succeeding the last element in a list
313 const_iterator cend() const
315 return const_iterator( const_cast<node_type *>(&m_Tail) );
319 /// Default constructor initializes empty list
322 static_assert( (std::is_same< gc, typename node_type::gc >::value), "GC and node_type::gc must be the same type" );
323 m_Head.m_pNext.store( &m_Tail, memory_model::memory_order_relaxed );
326 /// Destroys the list object
330 assert( m_Head.m_pNext.load(memory_model::memory_order_relaxed) == &m_Tail );
331 m_Head.m_pNext.store( nullptr, memory_model::memory_order_relaxed );
336 The function inserts \p val in the list if the list does not contain
337 an item with key equal to \p val.
339 Returns \p true if \p val is linked into the list, \p false otherwise.
341 bool insert( value_type& val )
343 return insert_at( &m_Head, val );
348 The operation performs inserting or changing data with lock-free manner.
350 If the item \p val not found in the list, then \p val is inserted into the list
351 iff \p bAllowInsert is \p true.
352 Otherwise, the functor \p func is called with item found.
353 The functor signature is:
356 void operator()( bool bNew, value_type& item, value_type& val );
360 - \p bNew - \p true if the item has been inserted, \p false otherwise
361 - \p item - item of the list
362 - \p val - argument \p val passed into the \p update() function
363 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
364 refer to the same thing.
366 The functor may change non-key fields of the \p item.
367 While the functor \p f is calling the item \p item is locked.
369 Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successfull,
370 \p second is \p true if new item has been added or \p false if the item with \p key
371 already is in the list.
373 template <typename Func>
374 std::pair<bool, bool> update( value_type& val, Func func, bool bAllowInsert = true )
376 return update_at( &m_Head, val, func, bAllowInsert );
379 template <typename Func>
380 CDS_DEPRECATED("ensure() is deprecated, use update()")
381 std::pair<bool, bool> ensure( value_type& val, Func func )
383 return update( val, func, true );
387 /// Finds the key \p key
388 /** \anchor cds_intrusive_LazyList_nogc_find_func
389 The function searches the item with key equal to \p key
390 and calls the functor \p f for item found.
391 The interface of \p Func functor is:
394 void operator()( value_type& item, Q& key );
397 where \p item is the item found, \p key is the <tt>find</tt> function argument.
399 The functor may change non-key fields of \p item.
400 While the functor \p f is calling the item found \p item is locked.
402 The function returns \p true if \p key is found, \p false otherwise.
404 template <typename Q, typename Func>
405 bool find( Q& key, Func f )
407 return find_at( &m_Head, key, key_comparator(), f );
410 template <typename Q, typename Func>
411 bool find( Q const& key, Func f )
413 return find_at( &m_Head, key, key_comparator(), f );
417 /// Finds the key \p key using \p less predicate for searching. Disabled for unordered lists.
419 The function is an analog of \ref cds_intrusive_LazyList_nogc_find_func "find(Q&, Func)"
420 but \p pred is used for key comparing.
421 \p Less functor has the interface like \p std::less.
422 \p pred must imply the same element order as the comparator used for building the list.
424 template <typename Q, typename Less, typename Func, bool Sort = c_bSort>
425 typename std::enable_if<Sort, bool>::type find_with( Q& key, Less less, Func f )
428 return find_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>(), f );
431 /// Finds the key \p key using \p equal predicate for searching. Disabled for ordered lists.
433 The function is an analog of \ref cds_intrusive_LazyList_nogc_find_func "find(Q&, Func)"
434 but \p equal is used for key comparing.
435 \p Equal functor has the interface like \p std::equal_to.
437 template <typename Q, typename Equal, typename Func, bool Sort = c_bSort>
438 typename std::enable_if<!Sort, bool>::type find_with( Q& key, Equal equal, Func f )
441 return find_at( &m_Head, key, equal, f );
444 template <typename Q, typename Less, typename Func, bool Sort = c_bSort>
445 typename std::enable_if<Sort, bool>::type find_with( Q const& key, Less pred, Func f )
448 return find_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>(), f );
451 template <typename Q, typename Equal, typename Func, bool Sort = c_bSort>
452 typename std::enable_if<!Sort, bool>::type find_with( Q const& key, Equal equal, Func f )
455 return find_at( &m_Head, key, equal, f );
459 /// Checks whether the list contains \p key
461 The function searches the item with key equal to \p key
462 and returns \p true if it is found, and \p false otherwise.
464 template <typename Q>
465 value_type * contains( Q const& key )
467 return find_at( &m_Head, key, key_comparator() );
470 template <typename Q>
471 CDS_DEPRECATED("deprecated, use contains()")
472 value_type * find( Q const& key )
474 return contains( key );
478 /// Checks whether the map contains \p key using \p pred predicate for searching (ordered list version)
480 The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
481 \p Less functor has the interface like \p std::less.
482 \p Less must imply the same element order as the comparator used for building the list.
484 template <typename Q, typename Less, bool Sort = c_bSort>
485 typename std::enable_if<Sort, value_type *>::type contains( Q const& key, Less pred )
488 return find_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>() );
491 template <typename Q, typename Less, bool Sort = c_bSort>
492 CDS_DEPRECATED("deprecated, use contains()")
493 typename std::enable_if<Sort, value_type *>::type find_with( Q const& key, Less pred )
495 return contains( key, pred );
499 /// Checks whether the map contains \p key using \p equal predicate for searching (unordered list version)
501 The function is an analog of <tt>contains( key )</tt> but \p equal is used for key comparing.
502 \p Equal functor has the interface like \p std::equal_to.
504 template <typename Q, typename Equal, bool Sort = c_bSort>
505 typename std::enable_if<!Sort, value_type *>::type contains( Q const& key, Equal equal )
507 return find_at( &m_Head, key, equal );
510 template <typename Q, typename Equal, bool Sort = c_bSort>
511 CDS_DEPRECATED("deprecated, use contains()")
512 typename std::enable_if<!Sort, value_type *>::type find_with( Q const& key, Equal equal )
514 return contains( key, equal );
520 The function unlink all items from the list.
521 For each unlinked item the item disposer \p disp is called after unlinking.
523 This function is not thread-safe.
525 template <typename Disposer>
526 void clear( Disposer disp )
528 node_type * pHead = m_Head.m_pNext.exchange( &m_Tail, memory_model::memory_order_release );
530 while ( pHead != &m_Tail ) {
531 node_type * p = pHead->m_pNext.load(memory_model::memory_order_relaxed);
532 dispose_node( pHead, disp );
537 /// Clears the list using default disposer
539 The function clears the list using default (provided in class template) disposer functor.
546 /// Checks if the list is empty
549 return m_Head.m_pNext.load(memory_model::memory_order_relaxed) == &m_Tail;
552 /// Returns list's item count
554 The value returned depends on opt::item_counter option. For atomicity::empty_item_counter,
555 this function always returns 0.
557 <b>Warning</b>: even if you use real item counter and it returns 0, this fact is not mean that the list
558 is empty. To check list emptyness use \ref empty() method.
562 return m_ItemCounter.value();
567 // split-list support
568 bool insert_aux_node( node_type * pNode )
570 return insert_aux_node( &m_Head, pNode );
573 // split-list support
574 bool insert_aux_node( node_type * pHead, node_type * pNode )
576 assert( pHead != nullptr );
577 assert( pNode != nullptr );
579 // Hack: convert node_type to value_type.
580 // In principle, auxiliary node can be non-reducible to value_type
581 // We assume that comparator can correctly distinguish aux and regular node.
582 return insert_at( pHead, *node_traits::to_value_ptr( pNode ) );
585 bool insert_at( node_type * pHead, value_type& val )
587 link_checker::is_empty( node_traits::to_node_ptr( val ) );
592 search( pHead, val, pos, pred );
594 auto_lock_position alp( pos );
595 if ( validate( pos.pPred, pos.pCur )) {
596 if ( pos.pCur != &m_Tail && equal( *node_traits::to_value_ptr( *pos.pCur ), val, pred ) ) {
597 // failed: key already in list
601 link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
610 iterator insert_at_( node_type * pHead, value_type& val )
612 if ( insert_at( pHead, val ))
613 return iterator( node_traits::to_node_ptr( val ));
618 template <typename Func>
619 std::pair<iterator, bool> update_at_( node_type * pHead, value_type& val, Func func, bool bAllowInsert )
625 search( pHead, val, pos, pred );
627 auto_lock_position alp( pos );
628 if ( validate( pos.pPred, pos.pCur )) {
629 if ( pos.pCur != &m_Tail && equal( *node_traits::to_value_ptr( *pos.pCur ), val, pred )) {
630 // key already in the list
632 func( false, *node_traits::to_value_ptr( *pos.pCur ) , val );
633 return std::make_pair( iterator( pos.pCur ), false );
638 return std::make_pair( end(), false );
640 link_checker::is_empty( node_traits::to_node_ptr( val ) );
642 link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
643 func( true, val, val );
645 return std::make_pair( iterator( node_traits::to_node_ptr( val )), true );
652 template <typename Func>
653 std::pair<bool, bool> update_at( node_type * pHead, value_type& val, Func func, bool bAllowInsert )
655 std::pair<iterator, bool> ret = update_at_( pHead, val, func, bAllowInsert );
656 return std::make_pair( ret.first != end(), ret.second );
659 template <typename Q, typename Pred, typename Func>
660 bool find_at( node_type * pHead, Q& val, Pred pred, Func f )
664 search( pHead, val, pos, pred );
665 if ( pos.pCur != &m_Tail ) {
666 std::unique_lock< typename node_type::lock_type> al( pos.pCur->m_Lock );
667 if ( equal( *node_traits::to_value_ptr( *pos.pCur ), val, pred ) )
669 f( *node_traits::to_value_ptr( *pos.pCur ), val );
676 template <typename Q, typename Pred>
677 value_type * find_at( node_type * pHead, Q& val, Pred pred)
679 iterator it = find_at_( pHead, val, pred );
685 template <typename Q, typename Pred>
686 iterator find_at_( node_type * pHead, Q& val, Pred pred)
690 search( pHead, val, pos, pred );
691 if ( pos.pCur != &m_Tail ) {
692 if ( equal( *node_traits::to_value_ptr( *pos.pCur ), val, pred ))
693 return iterator( pos.pCur );
702 template <typename Q, typename Equal, bool Sort = c_bSort>
703 typename std::enable_if<!Sort, void>::type search( node_type * pHead, const Q& key, position& pos, Equal eq )
705 const node_type * pTail = &m_Tail;
707 node_type * pCur = pHead;
708 node_type * pPrev = pHead;
710 while ( pCur != pTail && ( pCur == pHead || !equal( *node_traits::to_value_ptr( *pCur ), key, eq ) )) {
712 pCur = pCur->m_pNext.load(memory_model::memory_order_acquire);
719 template <typename Q, typename Compare, bool Sort = c_bSort>
720 typename std::enable_if<Sort, void>::type search( node_type * pHead, const Q& key, position& pos, Compare cmp )
722 const node_type * pTail = &m_Tail;
724 node_type * pCur = pHead;
725 node_type * pPrev = pHead;
727 while ( pCur != pTail && ( pCur == pHead || cmp( *node_traits::to_value_ptr( *pCur ), key ) < 0 )) {
729 pCur = pCur->m_pNext.load(memory_model::memory_order_acquire);
736 template <typename L, typename R, typename Equal, bool Sort = c_bSort>
737 static typename std::enable_if<!Sort, bool>::type equal( L const& l, R const& r, Equal eq )
742 template <typename L, typename R, typename Compare, bool Sort = c_bSort>
743 static typename std::enable_if<Sort, bool>::type equal( L const& l, R const& r, Compare cmp )
745 return cmp(l, r) == 0;
748 static bool validate( node_type * pPred, node_type * pCur )
750 return pPred->m_pNext.load(memory_model::memory_order_acquire) == pCur;
756 }} // namespace cds::intrusive
758 #endif // #ifndef CDSLIB_INTRUSIVE_LAZY_LIST_NOGC_H