2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
6 Source code repo: http://github.com/khizmax/libcds/
7 Download: http://sourceforge.net/projects/libcds/files/
9 Redistribution and use in source and binary forms, with or without
10 modification, are permitted provided that the following conditions are met:
12 * Redistributions of source code must retain the above copyright notice, this
13 list of conditions and the following disclaimer.
15 * Redistributions in binary form must reproduce the above copyright notice,
16 this list of conditions and the following disclaimer in the documentation
17 and/or other materials provided with the distribution.
19 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
20 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
22 DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
23 FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
25 SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
26 CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
27 OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31 #ifndef CDSLIB_INTRUSIVE_LAZY_LIST_NOGC_H
32 #define CDSLIB_INTRUSIVE_LAZY_LIST_NOGC_H
34 #include <mutex> // unique_lock
35 #include <cds/intrusive/details/lazy_list_base.h>
36 #include <cds/gc/nogc.h>
38 namespace cds { namespace intrusive {
40 /// Lazy list node for \p gc::nogc
43 - Lock - lock type. Default is \p cds::sync::spin
44 - Tag - a \ref cds_intrusive_hook_tag "tag"
47 #ifdef CDS_DOXYGEN_INVOKED
48 typename Lock = cds::sync::spin,
49 typename Tag = opt::none
55 struct node<gc::nogc, Lock, Tag>
57 typedef gc::nogc gc; ///< Garbage collector
58 typedef Lock lock_type; ///< Lock type
59 typedef Tag tag; ///< tag
61 atomics::atomic<node *> m_pNext; ///< pointer to the next node in the list
62 mutable lock_type m_Lock; ///< Node lock
68 } // namespace lazy_list
71 /// Lazy single-linked list (template specialization for \p gc::nogc)
72 /** @ingroup cds_intrusive_list
73 \anchor cds_intrusive_LazyList_nogc
75 This specialization is append-only list when no item
76 reclamation may be performed. The class does not support deleting of list item.
78 The list can be ordered if \p Traits::sort is \p true that is default
79 or unordered otherwise. Unordered list can be maintained by \p equal_to
80 relationship (\p Traits::equal_to), but for the ordered list \p less
81 or \p compare relations should be specified in \p Traits.
83 See \ref cds_intrusive_LazyList_hp "LazyList" for description of template parameters.
87 #ifdef CDS_DOXYGEN_INVOKED
88 ,class Traits = lazy_list::traits
93 class LazyList<gc::nogc, T, Traits>
96 typedef gc::nogc gc; ///< Garbage collector
97 typedef T value_type; ///< type of value stored in the list
98 typedef Traits traits; ///< Traits template parameter
100 typedef typename traits::hook hook; ///< hook type
101 typedef typename hook::node_type node_type; ///< node type
102 static CDS_CONSTEXPR bool const c_bSort = traits::sort; ///< List type: ordered (\p true) or unordered (\p false)
104 # ifdef CDS_DOXYGEN_INVOKED
105 /// Key comparing functor
107 - for ordered list, the functor is based on \p traits::compare or \p traits::less
108 - for unordered list, the functor is based on \p traits::equal_to, \p traits::compare or \p traits::less
110 typedef implementation_defined key_comparator;
112 typedef typename std::conditional< c_bSort,
113 typename opt::details::make_comparator< value_type, traits >::type,
114 typename opt::details::make_equal_to< value_type, traits >::type
115 >::type key_comparator;
117 typedef typename traits::back_off back_off; ///< Back-off strategy
118 typedef typename traits::disposer disposer; ///< disposer
119 typedef typename get_node_traits< value_type, node_type, hook>::type node_traits; ///< node traits
120 typedef typename lazy_list::get_link_checker< node_type, traits::link_checker >::type link_checker; ///< link checker
122 typedef typename traits::item_counter item_counter; ///< Item counting policy used
123 typedef typename traits::memory_model memory_model; ///< C++ memory ordering (see \p lazy_list::traits::memory_model)
124 typedef typename traits::stat stat; ///< Internal statistics
127 static_assert((std::is_same< gc, typename node_type::gc >::value), "GC and node_type::gc must be the same type");
129 // Rebind traits (split-list support)
130 template <typename... Options>
131 struct rebind_traits {
135 , typename cds::opt::make_options< traits, Options...>::type
141 typedef node_type * auxiliary_head ; ///< Auxiliary head type (for split-list support)
144 node_type m_Head; ///< List head (dummy node)
145 node_type m_Tail; ///< List tail (dummy node)
146 item_counter m_ItemCounter; ///< Item counter
147 mutable stat m_Stat; ///< Internal statistics
151 /// Position pointer for item search
153 node_type * pPred ; ///< Previous node
154 node_type * pCur ; ///< Current node
156 /// Locks nodes \p pPred and \p pCur
159 pPred->m_Lock.lock();
163 /// Unlocks nodes \p pPred and \p pCur
166 pCur->m_Lock.unlock();
167 pPred->m_Lock.unlock();
171 class auto_lock_position {
174 auto_lock_position( position& pos )
179 ~auto_lock_position()
188 void clear_links( node_type * pNode )
190 pNode->m_pNext.store( nullptr, memory_model::memory_order_relaxed );
193 template <class Disposer>
194 void dispose_node( node_type * pNode, Disposer disp )
196 clear_links( pNode );
197 disp( node_traits::to_value_ptr( *pNode ));
200 template <class Disposer>
201 void dispose_value( value_type& val, Disposer disp )
203 dispose_node( node_traits::to_node_ptr( val ), disp );
206 void link_node( node_type * pNode, node_type * pPred, node_type * pCur )
208 link_checker::is_empty( pNode );
209 assert( pPred->m_pNext.load(memory_model::memory_order_relaxed) == pCur );
211 pNode->m_pNext.store( pCur, memory_model::memory_order_release );
212 pPred->m_pNext.store( pNode, memory_model::memory_order_release );
218 template <bool IsConst>
221 friend class LazyList;
224 value_type * m_pNode;
228 assert( m_pNode != nullptr );
230 node_type * pNode = node_traits::to_node_ptr( m_pNode );
231 node_type * pNext = pNode->m_pNext.load(memory_model::memory_order_relaxed);
232 if ( pNext != nullptr )
233 m_pNode = node_traits::to_value_ptr( pNext );
236 iterator_type( node_type * pNode )
238 m_pNode = node_traits::to_value_ptr( pNode );
242 typedef typename cds::details::make_const_type<value_type, IsConst>::pointer value_ptr;
243 typedef typename cds::details::make_const_type<value_type, IsConst>::reference value_ref;
249 iterator_type( const iterator_type& src )
250 : m_pNode( src.m_pNode )
253 value_ptr operator ->() const
258 value_ref operator *() const
260 assert( m_pNode != nullptr );
265 iterator_type& operator ++()
272 iterator_type operator ++(int)
274 iterator_type i(*this);
279 iterator_type& operator = (const iterator_type& src)
281 m_pNode = src.m_pNode;
286 bool operator ==(iterator_type<C> const& i ) const
288 return m_pNode == i.m_pNode;
291 bool operator !=(iterator_type<C> const& i ) const
293 return m_pNode != i.m_pNode;
300 typedef iterator_type<false> iterator;
301 /// Const forward iterator
302 typedef iterator_type<true> const_iterator;
304 /// Returns a forward iterator addressing the first element in a list
306 For empty list \code begin() == end() \endcode
310 iterator it( &m_Head );
311 ++it ; // skip dummy head
315 /// Returns an iterator that addresses the location succeeding the last element in a list
317 Do not use the value returned by <tt>end</tt> function to access any item.
319 The returned value can be used only to control reaching the end of the list.
320 For empty list \code begin() == end() \endcode
324 return iterator( &m_Tail );
327 /// Returns a forward const iterator addressing the first element in a list
328 const_iterator begin() const
332 /// Returns a forward const iterator addressing the first element in a list
333 const_iterator cbegin() const
335 const_iterator it( const_cast<node_type *>(&m_Head) );
336 ++it; // skip dummy head
340 /// Returns an const iterator that addresses the location succeeding the last element in a list
341 const_iterator end() const
345 /// Returns an const iterator that addresses the location succeeding the last element in a list
346 const_iterator cend() const
348 return const_iterator( const_cast<node_type *>(&m_Tail) );
352 /// Default constructor initializes empty list
355 m_Head.m_pNext.store( &m_Tail, memory_model::memory_order_relaxed );
359 template <typename Stat, typename = std::enable_if<std::is_same<stat, lazy_list::wrapped_stat<Stat>>::value >>
360 explicit LazyList( Stat& st )
363 m_Head.m_pNext.store( &m_Tail, memory_model::memory_order_relaxed );
367 /// Destroys the list object
371 assert( m_Head.m_pNext.load(memory_model::memory_order_relaxed) == &m_Tail );
372 m_Head.m_pNext.store( nullptr, memory_model::memory_order_relaxed );
377 The function inserts \p val in the list if the list does not contain
378 an item with key equal to \p val.
380 Returns \p true if \p val is linked into the list, \p false otherwise.
382 bool insert( value_type& val )
384 return insert_at( &m_Head, val );
389 The operation performs inserting or changing data with lock-free manner.
391 If the item \p val not found in the list, then \p val is inserted into the list
392 iff \p bAllowInsert is \p true.
393 Otherwise, the functor \p func is called with item found.
394 The functor signature is:
397 void operator()( bool bNew, value_type& item, value_type& val );
401 - \p bNew - \p true if the item has been inserted, \p false otherwise
402 - \p item - item of the list
403 - \p val - argument \p val passed into the \p update() function
404 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
405 refer to the same thing.
407 The functor may change non-key fields of the \p item.
408 While the functor \p f is calling the item \p item is locked.
410 Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successful,
411 \p second is \p true if new item has been added or \p false if the item with \p key
412 already is in the list.
414 template <typename Func>
415 std::pair<bool, bool> update( value_type& val, Func func, bool bAllowInsert = true )
417 return update_at( &m_Head, val, func, bAllowInsert );
420 template <typename Func>
421 CDS_DEPRECATED("ensure() is deprecated, use update()")
422 std::pair<bool, bool> ensure( value_type& val, Func func )
424 return update( val, func, true );
428 /// Finds the key \p key
429 /** \anchor cds_intrusive_LazyList_nogc_find_func
430 The function searches the item with key equal to \p key
431 and calls the functor \p f for item found.
432 The interface of \p Func functor is:
435 void operator()( value_type& item, Q& key );
438 where \p item is the item found, \p key is the <tt>find</tt> function argument.
440 The functor may change non-key fields of \p item.
441 While the functor \p f is calling the item found \p item is locked.
443 The function returns \p true if \p key is found, \p false otherwise.
445 template <typename Q, typename Func>
446 bool find( Q& key, Func f )
448 return find_at( &m_Head, key, key_comparator(), f );
451 template <typename Q, typename Func>
452 bool find( Q const& key, Func f )
454 return find_at( &m_Head, key, key_comparator(), f );
458 /// Finds the key \p key using \p less predicate for searching. Disabled for unordered lists.
460 The function is an analog of \ref cds_intrusive_LazyList_nogc_find_func "find(Q&, Func)"
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, typename Func, bool Sort = c_bSort>
466 typename std::enable_if<Sort, bool>::type find_with( Q& key, Less less, Func f )
469 return find_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>(), f );
472 /// Finds the key \p key using \p equal predicate for searching. Disabled for ordered lists.
474 The function is an analog of \ref cds_intrusive_LazyList_nogc_find_func "find(Q&, Func)"
475 but \p equal is used for key comparing.
476 \p Equal functor has the interface like \p std::equal_to.
478 template <typename Q, typename Equal, typename Func, bool Sort = c_bSort>
479 typename std::enable_if<!Sort, bool>::type find_with( Q& key, Equal equal, Func f )
482 return find_at( &m_Head, key, equal, f );
485 template <typename Q, typename Less, typename Func, bool Sort = c_bSort>
486 typename std::enable_if<Sort, bool>::type find_with( Q const& key, Less pred, Func f )
489 return find_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>(), f );
492 template <typename Q, typename Equal, typename Func, bool Sort = c_bSort>
493 typename std::enable_if<!Sort, bool>::type find_with( Q const& key, Equal equal, Func f )
496 return find_at( &m_Head, key, equal, f );
500 /// Checks whether the list contains \p key
502 The function searches the item with key equal to \p key
503 and returns \p true if it is found, and \p false otherwise.
505 template <typename Q>
506 value_type * contains( Q const& key )
508 return find_at( &m_Head, key, key_comparator() );
511 template <typename Q>
512 CDS_DEPRECATED("deprecated, use contains()")
513 value_type * find( Q const& key )
515 return contains( key );
519 /// Checks whether the map contains \p key using \p pred predicate for searching (ordered list version)
521 The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
522 \p Less functor has the interface like \p std::less.
523 \p Less must imply the same element order as the comparator used for building the list.
525 template <typename Q, typename Less, bool Sort = c_bSort>
526 typename std::enable_if<Sort, value_type *>::type contains( Q const& key, Less pred )
529 return find_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>() );
532 template <typename Q, typename Less, bool Sort = c_bSort>
533 CDS_DEPRECATED("deprecated, use contains()")
534 typename std::enable_if<Sort, value_type *>::type find_with( Q const& key, Less pred )
536 return contains( key, pred );
540 /// Checks whether the map contains \p key using \p equal predicate for searching (unordered list version)
542 The function is an analog of <tt>contains( key )</tt> but \p equal is used for key comparing.
543 \p Equal functor has the interface like \p std::equal_to.
545 template <typename Q, typename Equal, bool Sort = c_bSort>
546 typename std::enable_if<!Sort, value_type *>::type contains( Q const& key, Equal equal )
548 return find_at( &m_Head, key, equal );
551 template <typename Q, typename Equal, bool Sort = c_bSort>
552 CDS_DEPRECATED("deprecated, use contains()")
553 typename std::enable_if<!Sort, value_type *>::type find_with( Q const& key, Equal equal )
555 return contains( key, equal );
561 The function unlink all items from the list.
562 For each unlinked item the item disposer \p disp is called after unlinking.
564 This function is not thread-safe.
566 template <typename Disposer>
567 void clear( Disposer disp )
569 node_type * pHead = m_Head.m_pNext.exchange( &m_Tail, memory_model::memory_order_release );
571 while ( pHead != &m_Tail ) {
572 node_type * p = pHead->m_pNext.load(memory_model::memory_order_relaxed);
573 dispose_node( pHead, disp );
579 /// Clears the list using default disposer
581 The function clears the list using default (provided in class template) disposer functor.
588 /// Checks if the list is empty
591 return m_Head.m_pNext.load(memory_model::memory_order_relaxed) == &m_Tail;
594 /// Returns list's item count
596 The value returned depends on opt::item_counter option. For atomicity::empty_item_counter,
597 this function always returns 0.
599 <b>Warning</b>: even if you use real item counter and it returns 0, this fact is not mean that the list
600 is empty. To check list emptyness use \ref empty() method.
604 return m_ItemCounter.value();
607 /// Returns const reference to internal statistics
608 stat const& statistics() const
615 // split-list support
616 bool insert_aux_node( node_type * pNode )
618 return insert_aux_node( &m_Head, pNode );
621 // split-list support
622 bool insert_aux_node( node_type * pHead, node_type * pNode )
624 assert( pHead != nullptr );
625 assert( pNode != nullptr );
627 // Hack: convert node_type to value_type.
628 // In principle, auxiliary node can be non-reducible to value_type
629 // We assume that comparator can correctly distinguish aux and regular node.
630 return insert_at( pHead, *node_traits::to_value_ptr( pNode ) );
633 bool insert_at( node_type * pHead, value_type& val )
639 search( pHead, val, pos, pred );
641 auto_lock_position alp( pos );
642 if ( validate( pos.pPred, pos.pCur )) {
643 if ( pos.pCur != &m_Tail && equal( *node_traits::to_value_ptr( *pos.pCur ), val, pred ) ) {
644 // failed: key already in list
645 m_Stat.onInsertFailed();
649 link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
655 m_Stat.onInsertRetry();
659 m_Stat.onInsertSuccess();
663 iterator insert_at_( node_type * pHead, value_type& val )
665 if ( insert_at( pHead, val ))
666 return iterator( node_traits::to_node_ptr( val ));
671 template <typename Func>
672 std::pair<iterator, bool> update_at_( node_type * pHead, value_type& val, Func func, bool bAllowInsert )
678 search( pHead, val, pos, pred );
680 auto_lock_position alp( pos );
681 if ( validate( pos.pPred, pos.pCur )) {
682 if ( pos.pCur != &m_Tail && equal( *node_traits::to_value_ptr( *pos.pCur ), val, pred )) {
683 // key already in the list
685 func( false, *node_traits::to_value_ptr( *pos.pCur ) , val );
686 m_Stat.onUpdateExisting();
687 return std::make_pair( iterator( pos.pCur ), false );
691 if ( !bAllowInsert ) {
692 m_Stat.onUpdateFailed();
693 return std::make_pair( end(), false );
696 link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
697 func( true, val, val );
702 m_Stat.onUpdateRetry();
707 m_Stat.onUpdateNew();
708 return std::make_pair( iterator( node_traits::to_node_ptr( val ) ), true );
711 template <typename Func>
712 std::pair<bool, bool> update_at( node_type * pHead, value_type& val, Func func, bool bAllowInsert )
714 std::pair<iterator, bool> ret = update_at_( pHead, val, func, bAllowInsert );
715 return std::make_pair( ret.first != end(), ret.second );
718 template <typename Q, typename Pred, typename Func>
719 bool find_at( node_type * pHead, Q& val, Pred pred, Func f )
723 search( pHead, val, pos, pred );
724 if ( pos.pCur != &m_Tail ) {
725 std::unique_lock< typename node_type::lock_type> al( pos.pCur->m_Lock );
726 if ( equal( *node_traits::to_value_ptr( *pos.pCur ), val, pred ) )
728 f( *node_traits::to_value_ptr( *pos.pCur ), val );
729 m_Stat.onFindSuccess();
734 m_Stat.onFindFailed();
738 template <typename Q, typename Pred>
739 value_type * find_at( node_type * pHead, Q& val, Pred pred)
741 iterator it = find_at_( pHead, val, pred );
747 template <typename Q, typename Pred>
748 iterator find_at_( node_type * pHead, Q& val, Pred pred)
752 search( pHead, val, pos, pred );
753 if ( pos.pCur != &m_Tail ) {
754 if ( equal( *node_traits::to_value_ptr( *pos.pCur ), val, pred )) {
755 m_Stat.onFindSuccess();
756 return iterator( pos.pCur );
760 m_Stat.onFindFailed();
768 template <typename Q, typename Equal, bool Sort = c_bSort>
769 typename std::enable_if<!Sort, void>::type search( node_type * pHead, const Q& key, position& pos, Equal eq )
771 const node_type * pTail = &m_Tail;
773 node_type * pCur = pHead;
774 node_type * pPrev = pHead;
776 while ( pCur != pTail && ( pCur == pHead || !equal( *node_traits::to_value_ptr( *pCur ), key, eq ) )) {
778 pCur = pCur->m_pNext.load(memory_model::memory_order_acquire);
785 template <typename Q, typename Compare, bool Sort = c_bSort>
786 typename std::enable_if<Sort, void>::type search( node_type * pHead, const Q& key, position& pos, Compare cmp )
788 const node_type * pTail = &m_Tail;
790 node_type * pCur = pHead;
791 node_type * pPrev = pHead;
793 while ( pCur != pTail && ( pCur == pHead || cmp( *node_traits::to_value_ptr( *pCur ), key ) < 0 )) {
795 pCur = pCur->m_pNext.load(memory_model::memory_order_acquire);
802 template <typename L, typename R, typename Equal, bool Sort = c_bSort>
803 static typename std::enable_if<!Sort, bool>::type equal( L const& l, R const& r, Equal eq )
808 template <typename L, typename R, typename Compare, bool Sort = c_bSort>
809 static typename std::enable_if<Sort, bool>::type equal( L const& l, R const& r, Compare cmp )
811 return cmp(l, r) == 0;
814 bool validate( node_type * pPred, node_type * pCur )
816 if ( pPred->m_pNext.load(memory_model::memory_order_acquire) == pCur ) {
817 m_Stat.onValidationSuccess();
821 m_Stat.onValidationFailed();
826 template <typename Predicate>
827 void erase_for( Predicate pred )
829 node_type * pPred = nullptr;
830 node_type * pHead = m_Head.m_pNext.load( memory_model::memory_order_relaxed );
832 while ( pHead != &m_Tail ) {
833 node_type * p = pHead->m_pNext.load( memory_model::memory_order_relaxed );
834 if ( pred( *node_traits::to_value_ptr( pHead ))) {
835 assert( pPred != nullptr );
836 pPred->m_pNext.store( p, memory_model::memory_order_relaxed );
837 dispose_node( pHead, disposer() );
847 }} // namespace cds::intrusive
849 #endif // #ifndef CDSLIB_INTRUSIVE_LAZY_LIST_NOGC_H