3 #ifndef __CDS_INTRUSIVE_LAZY_LIST_NOGC_H
4 #define __CDS_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 gc::nogc
15 - Tag - a tag used to distinguish between different implementation
17 template <typename Lock, typename Tag>
18 struct node<gc::nogc, Lock, Tag>
20 typedef gc::nogc gc ; ///< Garbage collector
21 typedef Lock lock_type ; ///< Lock type
22 typedef Tag tag ; ///< tag
24 atomics::atomic<node *> m_pNext ; ///< pointer to the next node in the list
25 mutable lock_type m_Lock ; ///< Node lock
31 } // namespace lazy_list
34 /// Lazy ordered single-linked list (template specialization for gc::nogc)
35 /** @ingroup cds_intrusive_list
36 \anchor cds_intrusive_LazyList_nogc
38 This specialization is intended for so-called persistent usage when no item
39 reclamation may be performed. The class does not support deleting of list item.
41 See \ref cds_intrusive_LazyList_hp "LazyList" for description of template parameters.
43 The interface of the specialization is a slightly different.
45 The gc::nogc specialization of LazyList accepts following template argument list
46 \p Options of cds::intrusive::lazy_list::make_traits metafunction:
47 - opt::hook - hook used. Possible values are: lazy_list::base_hook, lazy_list::member_hook, lazy_list::traits_hook.
48 If the option is not specified, <tt>lazy_list::base_hook<></tt> and gc::HP is used.
49 - opt::compare - key comparison functor. No default functor is provided.
50 If the option is not specified, the opt::less is used.
51 - opt::less - specifies binary predicate used for key comparison. Default is \p std::less<T>.
52 - opt::back_off - back-off strategy used. If the option is not specified, the cds::backoff::empty is used.
53 - opt::disposer - the functor used for dispose removed items. Default is opt::v::empty_disposer. The disposer
54 provided is used only in \ref clear() function.
55 - opt::link_checker - the type of node's link fields checking. Default is \ref opt::debug_check_link
56 - opt::item_counter - the type of item counting feature. Default is \ref atomicity::empty_item_counter that is no item counting.
57 - opt::memory_model - C++ memory ordering model. Can be opt::v::relaxed_ordering (relaxed memory model, the default)
58 or opt::v::sequential_consistent (sequentially consisnent memory model).
60 The opt::allocator and opt::back_off is not used for this specialization.
65 #ifdef CDS_DOXYGEN_INVOKED
66 ,class Traits = lazy_list::type_traits
71 class LazyList<gc::nogc, T, Traits>
74 typedef T value_type ; ///< type of value stored in the list
75 typedef Traits options ; ///< Traits template parameter
77 typedef typename options::hook hook ; ///< hook type
78 typedef typename hook::node_type node_type ; ///< node type
80 # ifdef CDS_DOXYGEN_INVOKED
81 typedef implementation_defined key_comparator ; ///< key comparison functor based on opt::compare and opt::less option setter.
83 typedef typename opt::details::make_comparator< value_type, options >::type key_comparator;
86 typedef typename options::disposer disposer ; ///< disposer used
87 typedef typename get_node_traits< value_type, node_type, hook>::type node_traits ; ///< node traits
88 typedef typename lazy_list::get_link_checker< node_type, options::link_checker >::type link_checker ; ///< link checker
90 typedef gc::nogc gc ; ///< Garbage collector
91 typedef typename options::back_off back_off ; ///< back-off strategy (not used)
92 typedef typename options::item_counter item_counter ; ///< Item counting policy used
93 typedef typename options::memory_model memory_model; ///< C++ memory ordering (see lazy_list::type_traits::memory_model)
96 // Rebind options (split-list support)
97 template <typename... Options>
98 struct rebind_options {
102 , typename cds::opt::make_options< options, Options...>::type
108 typedef node_type * auxiliary_head ; ///< Auxiliary head type (for split-list support)
111 node_type m_Head ; ///< List head (dummy node)
112 node_type m_Tail; ///< List tail (dummy node)
113 item_counter m_ItemCounter ; ///< Item counter
117 /// Position pointer for item search
119 node_type * pPred ; ///< Previous node
120 node_type * pCur ; ///< Current node
122 /// Locks nodes \p pPred and \p pCur
125 pPred->m_Lock.lock();
129 /// Unlocks nodes \p pPred and \p pCur
132 pCur->m_Lock.unlock();
133 pPred->m_Lock.unlock();
137 class auto_lock_position {
140 auto_lock_position( position& pos )
145 ~auto_lock_position()
154 void clear_links( node_type * pNode )
156 pNode->m_pNext.store( nullptr, memory_model::memory_order_relaxed );
159 template <class Disposer>
160 void dispose_node( node_type * pNode, Disposer disp )
162 clear_links( pNode );
163 disp( node_traits::to_value_ptr( *pNode ));
166 template <class Disposer>
167 void dispose_value( value_type& val, Disposer disp )
169 dispose_node( node_traits::to_node_ptr( val ), disp );
172 void link_node( node_type * pNode, node_type * pPred, node_type * pCur )
174 assert( pPred->m_pNext.load(memory_model::memory_order_relaxed) == pCur );
176 pNode->m_pNext.store( pCur, memory_model::memory_order_release );
177 pPred->m_pNext.store( pNode, memory_model::memory_order_release );
183 template <bool IsConst>
186 friend class LazyList;
189 value_type * m_pNode;
193 assert( m_pNode != nullptr );
195 node_type * pNode = node_traits::to_node_ptr( m_pNode );
196 node_type * pNext = pNode->m_pNext.load(memory_model::memory_order_relaxed);
197 if ( pNext != nullptr )
198 m_pNode = node_traits::to_value_ptr( pNext );
201 iterator_type( node_type * pNode )
203 m_pNode = node_traits::to_value_ptr( pNode );
207 typedef typename cds::details::make_const_type<value_type, IsConst>::pointer value_ptr;
208 typedef typename cds::details::make_const_type<value_type, IsConst>::reference value_ref;
214 iterator_type( const iterator_type& src )
215 : m_pNode( src.m_pNode )
218 value_ptr operator ->() const
223 value_ref operator *() const
225 assert( m_pNode != nullptr );
230 iterator_type& operator ++()
237 iterator_type operator ++(int)
239 iterator_type i(*this);
244 iterator_type& operator = (const iterator_type& src)
246 m_pNode = src.m_pNode;
251 bool operator ==(iterator_type<C> const& i ) const
253 return m_pNode == i.m_pNode;
256 bool operator !=(iterator_type<C> const& i ) const
258 return m_pNode != i.m_pNode;
265 typedef iterator_type<false> iterator;
266 /// Const forward iterator
267 typedef iterator_type<true> const_iterator;
269 /// Returns a forward iterator addressing the first element in a list
271 For empty list \code begin() == end() \endcode
275 iterator it( &m_Head );
276 ++it ; // skip dummy head
280 /// Returns an iterator that addresses the location succeeding the last element in a list
282 Do not use the value returned by <tt>end</tt> function to access any item.
284 The returned value can be used only to control reaching the end of the list.
285 For empty list \code begin() == end() \endcode
289 return iterator( &m_Tail );
292 /// Returns a forward const iterator addressing the first element in a list
293 const_iterator begin() const
295 const_iterator it( const_cast<node_type *>( &m_Head ));
296 ++it ; // skip dummy head
300 /// Returns an const iterator that addresses the location succeeding the last element in a list
301 const_iterator end() const
303 return const_iterator( const_cast<node_type *>( &m_Tail ));
307 /// Default constructor initializes empty list
310 static_assert( (std::is_same< gc, typename node_type::gc >::value), "GC and node_type::gc must be the same type" );
312 m_Head.m_pNext.store( &m_Tail, memory_model::memory_order_relaxed );
315 /// Destroys the list object
320 assert( m_Head.m_pNext.load(memory_model::memory_order_relaxed) == &m_Tail );
321 m_Head.m_pNext.store( nullptr, memory_model::memory_order_relaxed );
326 The function inserts \p val in the list if the list does not contain
327 an item with key equal to \p val.
329 Returns \p true if \p val is linked into the list, \p false otherwise.
331 bool insert( value_type& val )
333 return insert_at( &m_Head, val );
336 /// Ensures that the \p item exists in the list
338 The operation performs inserting or changing data with lock-free manner.
340 If the item \p val not found in the list, then \p val is inserted into the list.
341 Otherwise, the functor \p func is called with item found.
342 The functor signature is:
345 void operator()( bool bNew, value_type& item, value_type& val );
349 - \p bNew - \p true if the item has been inserted, \p false otherwise
350 - \p item - item of the list
351 - \p val - argument \p val passed into the \p ensure function
352 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
353 refers to the same thing.
355 The functor may change non-key fields of the \p item.
356 While the functor \p f is calling the item \p item is locked.
358 You may pass \p func argument by reference using \p std::ref.
360 Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
361 \p second is true if new item has been added or \p false if the item with \p key
362 already is in the list.
365 template <typename Func>
366 std::pair<bool, bool> ensure( value_type& val, Func func )
368 return ensure_at( &m_Head, val, func );
371 /// Finds the key \p val
372 /** \anchor cds_intrusive_LazyList_nogc_find_func
373 The function searches the item with key equal to \p val
374 and calls the functor \p f for item found.
375 The interface of \p Func functor is:
378 void operator()( value_type& item, Q& val );
381 where \p item is the item found, \p val is the <tt>find</tt> function argument.
383 You may pass \p f argument by reference using \p std::ref.
385 The functor may change non-key fields of \p item.
386 While the functor \p f is calling the item found \p item is locked.
388 The function returns \p true if \p val is found, \p false otherwise.
390 template <typename Q, typename Func>
391 bool find( Q& val, Func f )
393 return find_at( &m_Head, val, key_comparator(), f );
396 /// Finds the key \p val
397 /** \anchor cds_intrusive_LazyList_nogc_find_cfunc
398 The function searches the item with key equal to \p val
399 and calls the functor \p f for item found.
400 The interface of \p Func functor is:
403 void operator()( value_type& item, Q const& val );
406 where \p item is the item found, \p val is the <tt>find</tt> function argument.
408 You may pass \p f argument by reference using \p std::ref.
410 The functor may change non-key fields of \p item.
411 While the functor \p f is calling the item found \p item is locked.
413 The function returns \p true if \p val is found, \p false otherwise.
415 template <typename Q, typename Func>
416 bool find( Q const& val, Func f )
418 return find_at( &m_Head, val, key_comparator(), f );
421 /// Finds the key \p val using \p pred predicate for searching
423 The function is an analog of \ref cds_intrusive_LazyList_nogc_find_cfunc "find(Q const&, Func)"
424 but \p pred is used for key comparing.
425 \p Less functor has the interface like \p std::less.
426 \p pred must imply the same element order as the comparator used for building the list.
428 template <typename Q, typename Less, typename Func>
429 bool find_with( Q const& val, Less pred, Func f )
431 return find_at( &m_Head, val, cds::opt::details::make_comparator_from_less<Less>(), f );
434 /// Finds the key \p val using \p pred predicate for searching
436 The function is an analog of \ref cds_intrusive_LazyList_nogc_find_func "find(Q&, Func)"
437 but \p pred is used for key comparing.
438 \p Less functor has the interface like \p std::less.
439 \p pred must imply the same element order as the comparator used for building the list.
441 template <typename Q, typename Less, typename Func>
442 bool find_with( Q& val, Less pred, Func f )
444 return find_at( &m_Head, val, cds::opt::details::make_comparator_from_less<Less>(), f );
447 /// Finds the key \p val
448 /** \anchor cds_intrusive_LazyList_nogc_find_val
449 The function searches the item with key equal to \p val
450 and returns pointer to value found or \p nullptr.
452 template <typename Q>
453 value_type * find( Q const& val )
455 return find_at( &m_Head, val, key_comparator() );
458 /// Finds the key \p val using \p pred predicate for searching
460 The function is an analog of \ref cds_intrusive_LazyList_nogc_find_val "find(Q const&)"
461 but \p pred is used for key comparing.
462 \p Less functor has the interface like \p std::less.
463 \p pred must imply the same element order as the comparator used for building the list.
465 template <typename Q, typename Less>
466 value_type * find_with( Q const & val, Less pred )
468 return find_at( &m_Head, val, cds::opt::details::make_comparator_from_less<Less>() );
473 The function unlink all items from the list.
474 For each unlinked item the item disposer \p disp is called after unlinking.
476 This function is not thread-safe.
478 template <typename Disposer>
479 void clear( Disposer disp )
481 node_type * pHead = m_Head.m_pNext.exchange( &m_Tail, memory_model::memory_order_release );
483 while ( pHead != &m_Tail ) {
484 node_type * p = pHead->m_pNext.load(memory_model::memory_order_relaxed);
485 dispose_node( pHead, disp );
490 /// Clears the list using default disposer
492 The function clears the list using default (provided in class template) disposer functor.
499 /// Checks if the list is empty
502 return m_Head.m_pNext.load(memory_model::memory_order_relaxed) == &m_Tail;
505 /// Returns list's item count
507 The value returned depends on opt::item_counter option. For atomicity::empty_item_counter,
508 this function always returns 0.
510 <b>Warning</b>: even if you use real item counter and it returns 0, this fact is not mean that the list
511 is empty. To check list emptyness use \ref empty() method.
515 return m_ItemCounter.value();
520 // split-list support
521 bool insert_aux_node( node_type * pNode )
523 return insert_aux_node( &m_Head, pNode );
526 // split-list support
527 bool insert_aux_node( node_type * pHead, node_type * pNode )
529 assert( pHead != nullptr );
530 assert( pNode != nullptr );
532 // Hack: convert node_type to value_type.
533 // In principle, auxiliary node can be non-reducible to value_type
534 // We assume that comparator can correctly distinguish aux and regular node.
535 return insert_at( pHead, *node_traits::to_value_ptr( pNode ) );
538 bool insert_at( node_type * pHead, value_type& val )
540 link_checker::is_empty( node_traits::to_node_ptr( val ) );
545 search( pHead, val, pos, key_comparator() );
547 auto_lock_position alp( pos );
548 if ( validate( pos.pPred, pos.pCur )) {
549 if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
550 // failed: key already in list
554 link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
563 iterator insert_at_( node_type * pHead, value_type& val )
565 if ( insert_at( pHead, val ))
566 return iterator( node_traits::to_node_ptr( val ));
571 template <typename Func>
572 std::pair<iterator, bool> ensure_at_( node_type * pHead, value_type& val, Func func )
578 search( pHead, val, pos, key_comparator() );
580 auto_lock_position alp( pos );
581 if ( validate( pos.pPred, pos.pCur )) {
582 if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
583 // key already in the list
585 func( false, *node_traits::to_value_ptr( *pos.pCur ) , val );
586 return std::make_pair( iterator( pos.pCur ), false );
590 link_checker::is_empty( node_traits::to_node_ptr( val ) );
592 link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
593 func( true, val, val );
595 return std::make_pair( iterator( node_traits::to_node_ptr( val )), true );
602 template <typename Func>
603 std::pair<bool, bool> ensure_at( node_type * pHead, value_type& val, Func func )
605 std::pair<iterator, bool> ret = ensure_at_( pHead, val, func );
606 return std::make_pair( ret.first != end(), ret.second );
609 template <typename Q, typename Compare, typename Func>
610 bool find_at( node_type * pHead, Q& val, Compare cmp, Func f )
614 search( pHead, val, pos, cmp );
615 if ( pos.pCur != &m_Tail ) {
616 std::unique_lock< typename node_type::lock_type> al( pos.pCur->m_Lock );
617 if ( cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 )
619 f( *node_traits::to_value_ptr( *pos.pCur ), val );
626 template <typename Q, typename Compare>
627 value_type * find_at( node_type * pHead, Q& val, Compare cmp)
629 iterator it = find_at_( pHead, val, cmp );
635 template <typename Q, typename Compare>
636 iterator find_at_( node_type * pHead, Q& val, Compare cmp)
640 search( pHead, val, pos, cmp );
641 if ( pos.pCur != &m_Tail ) {
642 std::unique_lock< typename node_type::lock_type> al( pos.pCur->m_Lock );
643 if ( cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 )
645 return iterator( pos.pCur );
655 template <typename Q, typename Compare>
656 void search( node_type * pHead, const Q& key, position& pos, Compare cmp )
658 const node_type * pTail = &m_Tail;
660 node_type * pCur = pHead;
661 node_type * pPrev = pHead;
663 while ( pCur != pTail && ( pCur == pHead || cmp( *node_traits::to_value_ptr( *pCur ), key ) < 0 )) {
665 pCur = pCur->m_pNext.load(memory_model::memory_order_acquire);
672 static bool validate( node_type * pPred, node_type * pCur )
674 return pPred->m_pNext.load(memory_model::memory_order_acquire) == pCur;
680 }} // namespace cds::intrusive
682 #endif // #ifndef __CDS_INTRUSIVE_LAZY_LIST_NOGC_H