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 ordered 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 See \ref cds_intrusive_LazyList_hp "LazyList" for description of template parameters.
54 #ifdef CDS_DOXYGEN_INVOKED
55 ,class Traits = lazy_list::traits
60 class LazyList<gc::nogc, T, Traits>
63 typedef gc::nogc gc; ///< Garbage collector
64 typedef T value_type; ///< type of value stored in the list
65 typedef Traits traits; ///< Traits template parameter
67 typedef typename traits::hook hook; ///< hook type
68 typedef typename hook::node_type node_type; ///< node type
70 # ifdef CDS_DOXYGEN_INVOKED
71 typedef implementation_defined key_comparator ; ///< key comparison functor based on opt::compare and opt::less option setter.
73 typedef typename opt::details::make_comparator< value_type, traits >::type key_comparator;
75 typedef typename traits::back_off back_off; ///< Back-off strategy
76 typedef typename traits::disposer disposer; ///< disposer
77 typedef typename get_node_traits< value_type, node_type, hook>::type node_traits; ///< node traits
78 typedef typename lazy_list::get_link_checker< node_type, traits::link_checker >::type link_checker; ///< link checker
80 typedef typename traits::item_counter item_counter; ///< Item counting policy used
81 typedef typename traits::memory_model memory_model; ///< C++ memory ordering (see lazy_list::traits::memory_model)
84 // Rebind traits (split-list support)
85 template <typename... Options>
86 struct rebind_traits {
90 , typename cds::opt::make_options< traits, Options...>::type
96 typedef node_type * auxiliary_head ; ///< Auxiliary head type (for split-list support)
99 node_type m_Head; ///< List head (dummy node)
100 node_type m_Tail; ///< List tail (dummy node)
101 item_counter m_ItemCounter; ///< Item counter
105 /// Position pointer for item search
107 node_type * pPred ; ///< Previous node
108 node_type * pCur ; ///< Current node
110 /// Locks nodes \p pPred and \p pCur
113 pPred->m_Lock.lock();
117 /// Unlocks nodes \p pPred and \p pCur
120 pCur->m_Lock.unlock();
121 pPred->m_Lock.unlock();
125 class auto_lock_position {
128 auto_lock_position( position& pos )
133 ~auto_lock_position()
142 void clear_links( node_type * pNode )
144 pNode->m_pNext.store( nullptr, memory_model::memory_order_relaxed );
147 template <class Disposer>
148 void dispose_node( node_type * pNode, Disposer disp )
150 clear_links( pNode );
151 disp( node_traits::to_value_ptr( *pNode ));
154 template <class Disposer>
155 void dispose_value( value_type& val, Disposer disp )
157 dispose_node( node_traits::to_node_ptr( val ), disp );
160 void link_node( node_type * pNode, node_type * pPred, node_type * pCur )
162 assert( pPred->m_pNext.load(memory_model::memory_order_relaxed) == pCur );
164 pNode->m_pNext.store( pCur, memory_model::memory_order_release );
165 pPred->m_pNext.store( pNode, memory_model::memory_order_release );
171 template <bool IsConst>
174 friend class LazyList;
177 value_type * m_pNode;
181 assert( m_pNode != nullptr );
183 node_type * pNode = node_traits::to_node_ptr( m_pNode );
184 node_type * pNext = pNode->m_pNext.load(memory_model::memory_order_relaxed);
185 if ( pNext != nullptr )
186 m_pNode = node_traits::to_value_ptr( pNext );
189 iterator_type( node_type * pNode )
191 m_pNode = node_traits::to_value_ptr( pNode );
195 typedef typename cds::details::make_const_type<value_type, IsConst>::pointer value_ptr;
196 typedef typename cds::details::make_const_type<value_type, IsConst>::reference value_ref;
202 iterator_type( const iterator_type& src )
203 : m_pNode( src.m_pNode )
206 value_ptr operator ->() const
211 value_ref operator *() const
213 assert( m_pNode != nullptr );
218 iterator_type& operator ++()
225 iterator_type operator ++(int)
227 iterator_type i(*this);
232 iterator_type& operator = (const iterator_type& src)
234 m_pNode = src.m_pNode;
239 bool operator ==(iterator_type<C> const& i ) const
241 return m_pNode == i.m_pNode;
244 bool operator !=(iterator_type<C> const& i ) const
246 return m_pNode != i.m_pNode;
253 typedef iterator_type<false> iterator;
254 /// Const forward iterator
255 typedef iterator_type<true> const_iterator;
257 /// Returns a forward iterator addressing the first element in a list
259 For empty list \code begin() == end() \endcode
263 iterator it( &m_Head );
264 ++it ; // skip dummy head
268 /// Returns an iterator that addresses the location succeeding the last element in a list
270 Do not use the value returned by <tt>end</tt> function to access any item.
272 The returned value can be used only to control reaching the end of the list.
273 For empty list \code begin() == end() \endcode
277 return iterator( &m_Tail );
280 /// Returns a forward const iterator addressing the first element in a list
281 const_iterator begin() const
285 /// Returns a forward const iterator addressing the first element in a list
286 const_iterator cbegin() const
288 const_iterator it( const_cast<node_type *>(&m_Head) );
289 ++it; // skip dummy head
293 /// Returns an const iterator that addresses the location succeeding the last element in a list
294 const_iterator end() const
298 /// Returns an const iterator that addresses the location succeeding the last element in a list
299 const_iterator cend() const
301 return const_iterator( const_cast<node_type *>(&m_Tail) );
305 /// Default constructor initializes empty list
308 static_assert( (std::is_same< gc, typename node_type::gc >::value), "GC and node_type::gc must be the same type" );
309 m_Head.m_pNext.store( &m_Tail, memory_model::memory_order_relaxed );
312 /// Destroys the list object
316 assert( m_Head.m_pNext.load(memory_model::memory_order_relaxed) == &m_Tail );
317 m_Head.m_pNext.store( nullptr, memory_model::memory_order_relaxed );
322 The function inserts \p val in the list if the list does not contain
323 an item with key equal to \p val.
325 Returns \p true if \p val is linked into the list, \p false otherwise.
327 bool insert( value_type& val )
329 return insert_at( &m_Head, val );
332 /// Ensures that the \p item exists in the list
334 The operation performs inserting or changing data with lock-free manner.
336 If the item \p val not found in the list, then \p val is inserted into the list.
337 Otherwise, the functor \p func is called with item found.
338 The functor signature is:
341 void operator()( bool bNew, value_type& item, value_type& val );
345 - \p bNew - \p true if the item has been inserted, \p false otherwise
346 - \p item - item of the list
347 - \p val - argument \p val passed into the \p ensure function
348 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
349 refers to the same thing.
351 The functor may change non-key fields of the \p item.
352 While the functor \p f is calling the item \p item is locked.
354 Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
355 \p second is true if new item has been added or \p false if the item with \p key
356 already is in the list.
359 template <typename Func>
360 std::pair<bool, bool> ensure( value_type& val, Func func )
362 return ensure_at( &m_Head, val, func );
365 /// Finds the key \p key
366 /** \anchor cds_intrusive_LazyList_nogc_find_func
367 The function searches the item with key equal to \p key
368 and calls the functor \p f for item found.
369 The interface of \p Func functor is:
372 void operator()( value_type& item, Q& key );
375 where \p item is the item found, \p key is the <tt>find</tt> function argument.
377 The functor may change non-key fields of \p item.
378 While the functor \p f is calling the item found \p item is locked.
380 The function returns \p true if \p key is found, \p false otherwise.
382 template <typename Q, typename Func>
383 bool find( Q& key, Func f )
385 return find_at( &m_Head, key, key_comparator(), f );
388 template <typename Q, typename Func>
389 bool find( Q const& key, Func f )
391 return find_at( &m_Head, key, key_comparator(), f );
395 /// Finds the key \p key using \p pred predicate for searching
397 The function is an analog of \ref cds_intrusive_LazyList_nogc_find_func "find(Q&, Func)"
398 but \p pred is used for key comparing.
399 \p Less functor has the interface like \p std::less.
400 \p pred must imply the same element order as the comparator used for building the list.
402 template <typename Q, typename Less, typename Func>
403 bool find_with( Q& key, Less pred, Func f )
406 return find_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>(), f );
409 template <typename Q, typename Less, typename Func>
410 bool find_with( Q const& key, Less pred, Func f )
413 return find_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>(), f );
417 /// Finds the key \p key
418 /** \anchor cds_intrusive_LazyList_nogc_find_val
419 The function searches the item with key equal to \p key
420 and returns pointer to value found or \p nullptr.
422 template <typename Q>
423 value_type * find( Q const& key )
425 return find_at( &m_Head, key, key_comparator() );
428 /// Finds the key \p key using \p pred predicate for searching
430 The function is an analog of \ref cds_intrusive_LazyList_nogc_find_val "find(Q const&)"
431 but \p pred is used for key comparing.
432 \p Less functor has the interface like \p std::less.
433 \p pred must imply the same element order as the comparator used for building the list.
435 template <typename Q, typename Less>
436 value_type * find_with( Q const& key, Less pred )
439 return find_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>() );
444 The function unlink all items from the list.
445 For each unlinked item the item disposer \p disp is called after unlinking.
447 This function is not thread-safe.
449 template <typename Disposer>
450 void clear( Disposer disp )
452 node_type * pHead = m_Head.m_pNext.exchange( &m_Tail, memory_model::memory_order_release );
454 while ( pHead != &m_Tail ) {
455 node_type * p = pHead->m_pNext.load(memory_model::memory_order_relaxed);
456 dispose_node( pHead, disp );
461 /// Clears the list using default disposer
463 The function clears the list using default (provided in class template) disposer functor.
470 /// Checks if the list is empty
473 return m_Head.m_pNext.load(memory_model::memory_order_relaxed) == &m_Tail;
476 /// Returns list's item count
478 The value returned depends on opt::item_counter option. For atomicity::empty_item_counter,
479 this function always returns 0.
481 <b>Warning</b>: even if you use real item counter and it returns 0, this fact is not mean that the list
482 is empty. To check list emptyness use \ref empty() method.
486 return m_ItemCounter.value();
491 // split-list support
492 bool insert_aux_node( node_type * pNode )
494 return insert_aux_node( &m_Head, pNode );
497 // split-list support
498 bool insert_aux_node( node_type * pHead, node_type * pNode )
500 assert( pHead != nullptr );
501 assert( pNode != nullptr );
503 // Hack: convert node_type to value_type.
504 // In principle, auxiliary node can be non-reducible to value_type
505 // We assume that comparator can correctly distinguish aux and regular node.
506 return insert_at( pHead, *node_traits::to_value_ptr( pNode ) );
509 bool insert_at( node_type * pHead, value_type& val )
511 link_checker::is_empty( node_traits::to_node_ptr( val ) );
516 search( pHead, val, pos, key_comparator() );
518 auto_lock_position alp( pos );
519 if ( validate( pos.pPred, pos.pCur )) {
520 if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
521 // failed: key already in list
525 link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
534 iterator insert_at_( node_type * pHead, value_type& val )
536 if ( insert_at( pHead, val ))
537 return iterator( node_traits::to_node_ptr( val ));
542 template <typename Func>
543 std::pair<iterator, bool> ensure_at_( node_type * pHead, value_type& val, Func func )
549 search( pHead, val, pos, key_comparator() );
551 auto_lock_position alp( pos );
552 if ( validate( pos.pPred, pos.pCur )) {
553 if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
554 // key already in the list
556 func( false, *node_traits::to_value_ptr( *pos.pCur ) , val );
557 return std::make_pair( iterator( pos.pCur ), false );
561 link_checker::is_empty( node_traits::to_node_ptr( val ) );
563 link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
564 func( true, val, val );
566 return std::make_pair( iterator( node_traits::to_node_ptr( val )), true );
573 template <typename Func>
574 std::pair<bool, bool> ensure_at( node_type * pHead, value_type& val, Func func )
576 std::pair<iterator, bool> ret = ensure_at_( pHead, val, func );
577 return std::make_pair( ret.first != end(), ret.second );
580 template <typename Q, typename Compare, typename Func>
581 bool find_at( node_type * pHead, Q& val, Compare cmp, Func f )
585 search( pHead, val, pos, cmp );
586 if ( pos.pCur != &m_Tail ) {
587 std::unique_lock< typename node_type::lock_type> al( pos.pCur->m_Lock );
588 if ( cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 )
590 f( *node_traits::to_value_ptr( *pos.pCur ), val );
597 template <typename Q, typename Compare>
598 value_type * find_at( node_type * pHead, Q& val, Compare cmp)
600 iterator it = find_at_( pHead, val, cmp );
606 template <typename Q, typename Compare>
607 iterator find_at_( node_type * pHead, Q& val, Compare cmp)
611 search( pHead, val, pos, cmp );
612 if ( pos.pCur != &m_Tail ) {
613 std::unique_lock< typename node_type::lock_type> al( pos.pCur->m_Lock );
614 if ( cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 )
616 return iterator( pos.pCur );
626 template <typename Q, typename Compare>
627 void search( node_type * pHead, const Q& key, position& pos, Compare cmp )
629 const node_type * pTail = &m_Tail;
631 node_type * pCur = pHead;
632 node_type * pPrev = pHead;
634 while ( pCur != pTail && ( pCur == pHead || cmp( *node_traits::to_value_ptr( *pCur ), key ) < 0 )) {
636 pCur = pCur->m_pNext.load(memory_model::memory_order_acquire);
643 static bool validate( node_type * pPred, node_type * pCur )
645 return pPred->m_pNext.load(memory_model::memory_order_acquire) == pCur;
651 }} // namespace cds::intrusive
653 #endif // #ifndef CDSLIB_INTRUSIVE_LAZY_LIST_NOGC_H