2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017
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
140 template <typename Stat>
141 using select_stat_wrapper = lazy_list::select_stat_wrapper< Stat >;
145 typedef node_type * auxiliary_head ; ///< Auxiliary head type (for split-list support)
148 node_type m_Head; ///< List head (dummy node)
149 node_type m_Tail; ///< List tail (dummy node)
150 item_counter m_ItemCounter; ///< Item counter
151 mutable stat m_Stat; ///< Internal statistics
155 /// Position pointer for item search
157 node_type * pPred ; ///< Previous node
158 node_type * pCur ; ///< Current node
160 /// Locks nodes \p pPred and \p pCur
163 pPred->m_Lock.lock();
167 /// Unlocks nodes \p pPred and \p pCur
170 pCur->m_Lock.unlock();
171 pPred->m_Lock.unlock();
175 class auto_lock_position {
178 auto_lock_position( position& pos )
183 ~auto_lock_position()
192 void clear_links( node_type * pNode )
194 pNode->m_pNext.store( nullptr, memory_model::memory_order_relaxed );
197 template <class Disposer>
198 void dispose_node( node_type * pNode, Disposer disp )
200 clear_links( pNode );
201 disp( node_traits::to_value_ptr( *pNode ));
204 template <class Disposer>
205 void dispose_value( value_type& val, Disposer disp )
207 dispose_node( node_traits::to_node_ptr( val ), disp );
210 void link_node( node_type * pNode, node_type * pPred, node_type * pCur )
212 link_checker::is_empty( pNode );
213 assert( pPred->m_pNext.load(memory_model::memory_order_relaxed) == pCur );
215 pNode->m_pNext.store( pCur, memory_model::memory_order_release );
216 pPred->m_pNext.store( pNode, memory_model::memory_order_release );
222 template <bool IsConst>
225 friend class LazyList;
228 value_type * m_pNode;
232 assert( m_pNode != nullptr );
234 node_type * pNode = node_traits::to_node_ptr( m_pNode );
235 node_type * pNext = pNode->m_pNext.load(memory_model::memory_order_relaxed);
236 if ( pNext != nullptr )
237 m_pNode = node_traits::to_value_ptr( pNext );
240 iterator_type( node_type * pNode )
242 m_pNode = node_traits::to_value_ptr( pNode );
246 typedef typename cds::details::make_const_type<value_type, IsConst>::pointer value_ptr;
247 typedef typename cds::details::make_const_type<value_type, IsConst>::reference value_ref;
253 iterator_type( const iterator_type& src )
254 : m_pNode( src.m_pNode )
257 value_ptr operator ->() const
262 value_ref operator *() const
264 assert( m_pNode != nullptr );
269 iterator_type& operator ++()
276 iterator_type operator ++(int)
278 iterator_type i(*this);
283 iterator_type& operator = (const iterator_type& src)
285 m_pNode = src.m_pNode;
290 bool operator ==(iterator_type<C> const& i ) const
292 return m_pNode == i.m_pNode;
295 bool operator !=(iterator_type<C> const& i ) const
297 return m_pNode != i.m_pNode;
304 typedef iterator_type<false> iterator;
305 /// Const forward iterator
306 typedef iterator_type<true> const_iterator;
308 /// Returns a forward iterator addressing the first element in a list
310 For empty list \code begin() == end() \endcode
314 iterator it( &m_Head );
315 ++it ; // skip dummy head
319 /// Returns an iterator that addresses the location succeeding the last element in a list
321 Do not use the value returned by <tt>end</tt> function to access any item.
323 The returned value can be used only to control reaching the end of the list.
324 For empty list \code begin() == end() \endcode
328 return iterator( &m_Tail );
331 /// Returns a forward const iterator addressing the first element in a list
332 const_iterator begin() const
336 /// Returns a forward const iterator addressing the first element in a list
337 const_iterator cbegin() const
339 const_iterator it( const_cast<node_type *>(&m_Head));
340 ++it; // skip dummy head
344 /// Returns an const iterator that addresses the location succeeding the last element in a list
345 const_iterator end() const
349 /// Returns an const iterator that addresses the location succeeding the last element in a list
350 const_iterator cend() const
352 return const_iterator( const_cast<node_type *>(&m_Tail));
356 /// Default constructor initializes empty list
359 m_Head.m_pNext.store( &m_Tail, memory_model::memory_order_relaxed );
363 template <typename Stat, typename = std::enable_if<std::is_same<stat, lazy_list::wrapped_stat<Stat>>::value >>
364 explicit LazyList( Stat& st )
367 m_Head.m_pNext.store( &m_Tail, memory_model::memory_order_relaxed );
371 /// Destroys the list object
375 assert( m_Head.m_pNext.load(memory_model::memory_order_relaxed) == &m_Tail );
376 m_Head.m_pNext.store( nullptr, memory_model::memory_order_relaxed );
381 The function inserts \p val in the list if the list does not contain
382 an item with key equal to \p val.
384 Returns \p true if \p val is linked into the list, \p false otherwise.
386 bool insert( value_type& val )
388 return insert_at( &m_Head, val );
393 The operation performs inserting or changing data with lock-free manner.
395 If the item \p val not found in the list, then \p val is inserted into the list
396 iff \p bAllowInsert is \p true.
397 Otherwise, the functor \p func is called with item found.
398 The functor signature is:
401 void operator()( bool bNew, value_type& item, value_type& val );
405 - \p bNew - \p true if the item has been inserted, \p false otherwise
406 - \p item - item of the list
407 - \p val - argument \p val passed into the \p update() function
408 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
409 refer to the same thing.
411 The functor may change non-key fields of the \p item.
412 While the functor \p f is calling the item \p item is locked.
414 Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successful,
415 \p second is \p true if new item has been added or \p false if the item with \p key
416 already is in the list.
418 template <typename Func>
419 std::pair<bool, bool> update( value_type& val, Func func, bool bAllowInsert = true )
421 return update_at( &m_Head, val, func, bAllowInsert );
424 template <typename Func>
425 CDS_DEPRECATED("ensure() is deprecated, use update()")
426 std::pair<bool, bool> ensure( value_type& val, Func func )
428 return update( val, func, true );
432 /// Finds the key \p key
433 /** \anchor cds_intrusive_LazyList_nogc_find_func
434 The function searches the item with key equal to \p key
435 and calls the functor \p f for item found.
436 The interface of \p Func functor is:
439 void operator()( value_type& item, Q& key );
442 where \p item is the item found, \p key is the <tt>find</tt> function argument.
444 The functor may change non-key fields of \p item.
445 While the functor \p f is calling the item found \p item is locked.
447 The function returns \p true if \p key is found, \p false otherwise.
449 template <typename Q, typename Func>
450 bool find( Q& key, Func f )
452 return find_at( &m_Head, key, key_comparator(), f );
455 template <typename Q, typename Func>
456 bool find( Q const& key, Func f )
458 return find_at( &m_Head, key, key_comparator(), f );
462 /// Finds the key \p key using \p less predicate for searching. Disabled for unordered lists.
464 The function is an analog of \ref cds_intrusive_LazyList_nogc_find_func "find(Q&, Func)"
465 but \p pred is used for key comparing.
466 \p Less functor has the interface like \p std::less.
467 \p pred must imply the same element order as the comparator used for building the list.
469 template <typename Q, typename Less, typename Func, bool Sort = c_bSort>
470 typename std::enable_if<Sort, bool>::type find_with( Q& key, Less less, Func f )
473 return find_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>(), f );
476 /// Finds the key \p key using \p equal predicate for searching. Disabled for ordered lists.
478 The function is an analog of \ref cds_intrusive_LazyList_nogc_find_func "find(Q&, Func)"
479 but \p equal is used for key comparing.
480 \p Equal functor has the interface like \p std::equal_to.
482 template <typename Q, typename Equal, typename Func, bool Sort = c_bSort>
483 typename std::enable_if<!Sort, bool>::type find_with( Q& key, Equal eq, Func f )
486 return find_at( &m_Head, key, eq, f );
489 template <typename Q, typename Less, typename Func, bool Sort = c_bSort>
490 typename std::enable_if<Sort, bool>::type find_with( Q const& key, Less pred, Func f )
493 return find_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>(), f );
496 template <typename Q, typename Equal, typename Func, bool Sort = c_bSort>
497 typename std::enable_if<!Sort, bool>::type find_with( Q const& key, Equal eq, Func f )
500 return find_at( &m_Head, key, eq, f );
504 /// Checks whether the list contains \p key
506 The function searches the item with key equal to \p key
507 and returns \p true if it is found, and \p false otherwise.
509 template <typename Q>
510 value_type * contains( Q const& key )
512 return find_at( &m_Head, key, key_comparator());
515 template <typename Q>
516 CDS_DEPRECATED("deprecated, use contains()")
517 value_type * find( Q const& key )
519 return contains( key );
523 /// Checks whether the map contains \p key using \p pred predicate for searching (ordered list version)
525 The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
526 \p Less functor has the interface like \p std::less.
527 \p Less must imply the same element order as the comparator used for building the list.
529 template <typename Q, typename Less, bool Sort = c_bSort>
530 typename std::enable_if<Sort, value_type *>::type contains( Q const& key, Less pred )
533 return find_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>());
536 template <typename Q, typename Less, bool Sort = c_bSort>
537 CDS_DEPRECATED("deprecated, use contains()")
538 typename std::enable_if<Sort, value_type *>::type find_with( Q const& key, Less pred )
540 return contains( key, pred );
544 /// Checks whether the map contains \p key using \p equal predicate for searching (unordered list version)
546 The function is an analog of <tt>contains( key )</tt> but \p equal is used for key comparing.
547 \p Equal functor has the interface like \p std::equal_to.
549 template <typename Q, typename Equal, bool Sort = c_bSort>
550 typename std::enable_if<!Sort, value_type *>::type contains( Q const& key, Equal eq )
552 return find_at( &m_Head, key, eq );
555 template <typename Q, typename Equal, bool Sort = c_bSort>
556 CDS_DEPRECATED("deprecated, use contains()")
557 typename std::enable_if<!Sort, value_type *>::type find_with( Q const& key, Equal eq )
559 return contains( key, eq );
565 The function unlink all items from the list.
566 For each unlinked item the item disposer \p disp is called after unlinking.
568 This function is not thread-safe.
570 template <typename Disposer>
571 void clear( Disposer disp )
573 node_type * pHead = m_Head.m_pNext.exchange( &m_Tail, memory_model::memory_order_release );
575 while ( pHead != &m_Tail ) {
576 node_type * p = pHead->m_pNext.load(memory_model::memory_order_relaxed);
577 dispose_node( pHead, disp );
583 /// Clears the list using default disposer
585 The function clears the list using default (provided in class template) disposer functor.
592 /// Checks if the list is empty
595 return m_Head.m_pNext.load(memory_model::memory_order_relaxed) == &m_Tail;
598 /// Returns list's item count
600 The value returned depends on opt::item_counter option. For atomicity::empty_item_counter,
601 this function always returns 0.
603 <b>Warning</b>: even if you use real item counter and it returns 0, this fact is not mean that the list
604 is empty. To check list emptyness use \ref empty() method.
608 return m_ItemCounter.value();
611 /// Returns const reference to internal statistics
612 stat const& statistics() const
619 // split-list support
620 bool insert_aux_node( node_type * pNode )
622 return insert_aux_node( &m_Head, pNode );
625 // split-list support
626 bool insert_aux_node( node_type * pHead, node_type * pNode )
628 assert( pHead != nullptr );
629 assert( pNode != nullptr );
631 // Hack: convert node_type to value_type.
632 // In principle, auxiliary node can be non-reducible to value_type
633 // We assume that comparator can correctly distinguish aux and regular node.
634 return insert_at( pHead, *node_traits::to_value_ptr( pNode ));
637 bool insert_at( node_type * pHead, value_type& val )
643 search( pHead, val, pos, pred );
645 auto_lock_position alp( pos );
646 if ( validate( pos.pPred, pos.pCur )) {
647 if ( pos.pCur != &m_Tail && equal( *node_traits::to_value_ptr( *pos.pCur ), val, pred )) {
648 // failed: key already in list
649 m_Stat.onInsertFailed();
653 link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
659 m_Stat.onInsertRetry();
663 m_Stat.onInsertSuccess();
667 iterator insert_at_( node_type * pHead, value_type& val )
669 if ( insert_at( pHead, val ))
670 return iterator( node_traits::to_node_ptr( val ));
675 template <typename Func>
676 std::pair<iterator, bool> update_at_( node_type * pHead, value_type& val, Func func, bool bAllowInsert )
682 search( pHead, val, pos, pred );
684 auto_lock_position alp( pos );
685 if ( validate( pos.pPred, pos.pCur )) {
686 if ( pos.pCur != &m_Tail && equal( *node_traits::to_value_ptr( *pos.pCur ), val, pred )) {
687 // key already in the list
689 func( false, *node_traits::to_value_ptr( *pos.pCur ) , val );
690 m_Stat.onUpdateExisting();
691 return std::make_pair( iterator( pos.pCur ), false );
695 if ( !bAllowInsert ) {
696 m_Stat.onUpdateFailed();
697 return std::make_pair( end(), false );
700 link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
701 func( true, val, val );
706 m_Stat.onUpdateRetry();
711 m_Stat.onUpdateNew();
712 return std::make_pair( iterator( node_traits::to_node_ptr( val )), true );
715 template <typename Func>
716 std::pair<bool, bool> update_at( node_type * pHead, value_type& val, Func func, bool bAllowInsert )
718 std::pair<iterator, bool> ret = update_at_( pHead, val, func, bAllowInsert );
719 return std::make_pair( ret.first != end(), ret.second );
722 template <typename Q, typename Pred, typename Func>
723 bool find_at( node_type * pHead, Q& val, Pred pred, Func f )
727 search( pHead, val, pos, pred );
728 if ( pos.pCur != &m_Tail ) {
729 std::unique_lock< typename node_type::lock_type> al( pos.pCur->m_Lock );
730 if ( equal( *node_traits::to_value_ptr( *pos.pCur ), val, pred ))
732 f( *node_traits::to_value_ptr( *pos.pCur ), val );
733 m_Stat.onFindSuccess();
738 m_Stat.onFindFailed();
742 template <typename Q, typename Pred>
743 value_type * find_at( node_type * pHead, Q& val, Pred pred)
745 iterator it = find_at_( pHead, val, pred );
751 template <typename Q, typename Pred>
752 iterator find_at_( node_type * pHead, Q& val, Pred pred)
756 search( pHead, val, pos, pred );
757 if ( pos.pCur != &m_Tail ) {
758 if ( equal( *node_traits::to_value_ptr( *pos.pCur ), val, pred )) {
759 m_Stat.onFindSuccess();
760 return iterator( pos.pCur );
764 m_Stat.onFindFailed();
772 template <typename Q, typename Equal, bool Sort = c_bSort>
773 typename std::enable_if<!Sort, void>::type search( node_type * pHead, const Q& key, position& pos, Equal eq )
775 const node_type * pTail = &m_Tail;
777 node_type * pCur = pHead;
778 node_type * pPrev = pHead;
780 while ( pCur != pTail && ( pCur == pHead || !equal( *node_traits::to_value_ptr( *pCur ), key, eq ))) {
782 pCur = pCur->m_pNext.load(memory_model::memory_order_acquire);
789 template <typename Q, typename Compare, bool Sort = c_bSort>
790 typename std::enable_if<Sort, void>::type search( node_type * pHead, const Q& key, position& pos, Compare cmp )
792 const node_type * pTail = &m_Tail;
794 node_type * pCur = pHead;
795 node_type * pPrev = pHead;
797 while ( pCur != pTail && ( pCur == pHead || cmp( *node_traits::to_value_ptr( *pCur ), key ) < 0 )) {
799 pCur = pCur->m_pNext.load(memory_model::memory_order_acquire);
806 template <typename L, typename R, typename Equal, bool Sort = c_bSort>
807 static typename std::enable_if<!Sort, bool>::type equal( L const& l, R const& r, Equal eq )
812 template <typename L, typename R, typename Compare, bool Sort = c_bSort>
813 static typename std::enable_if<Sort, bool>::type equal( L const& l, R const& r, Compare cmp )
815 return cmp(l, r) == 0;
818 bool validate( node_type * pPred, node_type * pCur )
820 if ( pPred->m_pNext.load(memory_model::memory_order_acquire) == pCur ) {
821 m_Stat.onValidationSuccess();
825 m_Stat.onValidationFailed();
830 template <typename Predicate>
831 void erase_for( Predicate pred )
833 node_type * pPred = nullptr;
834 node_type * pHead = m_Head.m_pNext.load( memory_model::memory_order_relaxed );
836 while ( pHead != &m_Tail ) {
837 node_type * p = pHead->m_pNext.load( memory_model::memory_order_relaxed );
838 if ( pred( *node_traits::to_value_ptr( pHead ))) {
839 assert( pPred != nullptr );
840 pPred->m_pNext.store( p, memory_model::memory_order_relaxed );
841 dispose_node( pHead, disposer());
851 }} // namespace cds::intrusive
853 #endif // #ifndef CDSLIB_INTRUSIVE_LAZY_LIST_NOGC_H