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 lazy_list::traits::memory_model)
126 // Rebind traits (split-list support)
127 template <typename... Options>
128 struct rebind_traits {
132 , typename cds::opt::make_options< traits, Options...>::type
138 typedef node_type * auxiliary_head ; ///< Auxiliary head type (for split-list support)
141 node_type m_Head; ///< List head (dummy node)
142 node_type m_Tail; ///< List tail (dummy node)
143 item_counter m_ItemCounter; ///< Item counter
147 /// Position pointer for item search
149 node_type * pPred ; ///< Previous node
150 node_type * pCur ; ///< Current node
152 /// Locks nodes \p pPred and \p pCur
155 pPred->m_Lock.lock();
159 /// Unlocks nodes \p pPred and \p pCur
162 pCur->m_Lock.unlock();
163 pPred->m_Lock.unlock();
167 class auto_lock_position {
170 auto_lock_position( position& pos )
175 ~auto_lock_position()
184 void clear_links( node_type * pNode )
186 pNode->m_pNext.store( nullptr, memory_model::memory_order_relaxed );
189 template <class Disposer>
190 void dispose_node( node_type * pNode, Disposer disp )
192 clear_links( pNode );
193 disp( node_traits::to_value_ptr( *pNode ));
196 template <class Disposer>
197 void dispose_value( value_type& val, Disposer disp )
199 dispose_node( node_traits::to_node_ptr( val ), disp );
202 void link_node( node_type * pNode, node_type * pPred, node_type * pCur )
204 link_checker::is_empty( pNode );
205 assert( pPred->m_pNext.load(memory_model::memory_order_relaxed) == pCur );
207 pNode->m_pNext.store( pCur, memory_model::memory_order_release );
208 pPred->m_pNext.store( pNode, memory_model::memory_order_release );
214 template <bool IsConst>
217 friend class LazyList;
220 value_type * m_pNode;
224 assert( m_pNode != nullptr );
226 node_type * pNode = node_traits::to_node_ptr( m_pNode );
227 node_type * pNext = pNode->m_pNext.load(memory_model::memory_order_relaxed);
228 if ( pNext != nullptr )
229 m_pNode = node_traits::to_value_ptr( pNext );
232 iterator_type( node_type * pNode )
234 m_pNode = node_traits::to_value_ptr( pNode );
238 typedef typename cds::details::make_const_type<value_type, IsConst>::pointer value_ptr;
239 typedef typename cds::details::make_const_type<value_type, IsConst>::reference value_ref;
245 iterator_type( const iterator_type& src )
246 : m_pNode( src.m_pNode )
249 value_ptr operator ->() const
254 value_ref operator *() const
256 assert( m_pNode != nullptr );
261 iterator_type& operator ++()
268 iterator_type operator ++(int)
270 iterator_type i(*this);
275 iterator_type& operator = (const iterator_type& src)
277 m_pNode = src.m_pNode;
282 bool operator ==(iterator_type<C> const& i ) const
284 return m_pNode == i.m_pNode;
287 bool operator !=(iterator_type<C> const& i ) const
289 return m_pNode != i.m_pNode;
296 typedef iterator_type<false> iterator;
297 /// Const forward iterator
298 typedef iterator_type<true> const_iterator;
300 /// Returns a forward iterator addressing the first element in a list
302 For empty list \code begin() == end() \endcode
306 iterator it( &m_Head );
307 ++it ; // skip dummy head
311 /// Returns an iterator that addresses the location succeeding the last element in a list
313 Do not use the value returned by <tt>end</tt> function to access any item.
315 The returned value can be used only to control reaching the end of the list.
316 For empty list \code begin() == end() \endcode
320 return iterator( &m_Tail );
323 /// Returns a forward const iterator addressing the first element in a list
324 const_iterator begin() const
328 /// Returns a forward const iterator addressing the first element in a list
329 const_iterator cbegin() const
331 const_iterator it( const_cast<node_type *>(&m_Head) );
332 ++it; // skip dummy head
336 /// Returns an const iterator that addresses the location succeeding the last element in a list
337 const_iterator end() const
341 /// Returns an const iterator that addresses the location succeeding the last element in a list
342 const_iterator cend() const
344 return const_iterator( const_cast<node_type *>(&m_Tail) );
348 /// Default constructor initializes empty list
351 static_assert( (std::is_same< gc, typename node_type::gc >::value), "GC and node_type::gc must be the same type" );
352 m_Head.m_pNext.store( &m_Tail, memory_model::memory_order_relaxed );
355 /// Destroys the list object
359 assert( m_Head.m_pNext.load(memory_model::memory_order_relaxed) == &m_Tail );
360 m_Head.m_pNext.store( nullptr, memory_model::memory_order_relaxed );
365 The function inserts \p val in the list if the list does not contain
366 an item with key equal to \p val.
368 Returns \p true if \p val is linked into the list, \p false otherwise.
370 bool insert( value_type& val )
372 return insert_at( &m_Head, val );
377 The operation performs inserting or changing data with lock-free manner.
379 If the item \p val not found in the list, then \p val is inserted into the list
380 iff \p bAllowInsert is \p true.
381 Otherwise, the functor \p func is called with item found.
382 The functor signature is:
385 void operator()( bool bNew, value_type& item, value_type& val );
389 - \p bNew - \p true if the item has been inserted, \p false otherwise
390 - \p item - item of the list
391 - \p val - argument \p val passed into the \p update() function
392 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
393 refer to the same thing.
395 The functor may change non-key fields of the \p item.
396 While the functor \p f is calling the item \p item is locked.
398 Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successfull,
399 \p second is \p true if new item has been added or \p false if the item with \p key
400 already is in the list.
402 template <typename Func>
403 std::pair<bool, bool> update( value_type& val, Func func, bool bAllowInsert = true )
405 return update_at( &m_Head, val, func, bAllowInsert );
408 template <typename Func>
409 CDS_DEPRECATED("ensure() is deprecated, use update()")
410 std::pair<bool, bool> ensure( value_type& val, Func func )
412 return update( val, func, true );
416 /// Finds the key \p key
417 /** \anchor cds_intrusive_LazyList_nogc_find_func
418 The function searches the item with key equal to \p key
419 and calls the functor \p f for item found.
420 The interface of \p Func functor is:
423 void operator()( value_type& item, Q& key );
426 where \p item is the item found, \p key is the <tt>find</tt> function argument.
428 The functor may change non-key fields of \p item.
429 While the functor \p f is calling the item found \p item is locked.
431 The function returns \p true if \p key is found, \p false otherwise.
433 template <typename Q, typename Func>
434 bool find( Q& key, Func f )
436 return find_at( &m_Head, key, key_comparator(), f );
439 template <typename Q, typename Func>
440 bool find( Q const& key, Func f )
442 return find_at( &m_Head, key, key_comparator(), f );
446 /// Finds the key \p key using \p less predicate for searching. Disabled for unordered lists.
448 The function is an analog of \ref cds_intrusive_LazyList_nogc_find_func "find(Q&, Func)"
449 but \p pred is used for key comparing.
450 \p Less functor has the interface like \p std::less.
451 \p pred must imply the same element order as the comparator used for building the list.
453 template <typename Q, typename Less, typename Func, bool Sort = c_bSort>
454 typename std::enable_if<Sort, bool>::type find_with( Q& key, Less less, Func f )
457 return find_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>(), f );
460 /// Finds the key \p key using \p equal predicate for searching. Disabled for ordered lists.
462 The function is an analog of \ref cds_intrusive_LazyList_nogc_find_func "find(Q&, Func)"
463 but \p equal is used for key comparing.
464 \p Equal functor has the interface like \p std::equal_to.
466 template <typename Q, typename Equal, typename Func, bool Sort = c_bSort>
467 typename std::enable_if<!Sort, bool>::type find_with( Q& key, Equal equal, Func f )
470 return find_at( &m_Head, key, equal, f );
473 template <typename Q, typename Less, typename Func, bool Sort = c_bSort>
474 typename std::enable_if<Sort, bool>::type find_with( Q const& key, Less pred, Func f )
477 return find_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>(), f );
480 template <typename Q, typename Equal, typename Func, bool Sort = c_bSort>
481 typename std::enable_if<!Sort, bool>::type find_with( Q const& key, Equal equal, Func f )
484 return find_at( &m_Head, key, equal, f );
488 /// Checks whether the list contains \p key
490 The function searches the item with key equal to \p key
491 and returns \p true if it is found, and \p false otherwise.
493 template <typename Q>
494 value_type * contains( Q const& key )
496 return find_at( &m_Head, key, key_comparator() );
499 template <typename Q>
500 CDS_DEPRECATED("deprecated, use contains()")
501 value_type * find( Q const& key )
503 return contains( key );
507 /// Checks whether the map contains \p key using \p pred predicate for searching (ordered list version)
509 The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
510 \p Less functor has the interface like \p std::less.
511 \p Less must imply the same element order as the comparator used for building the list.
513 template <typename Q, typename Less, bool Sort = c_bSort>
514 typename std::enable_if<Sort, value_type *>::type contains( Q const& key, Less pred )
517 return find_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>() );
520 template <typename Q, typename Less, bool Sort = c_bSort>
521 CDS_DEPRECATED("deprecated, use contains()")
522 typename std::enable_if<Sort, value_type *>::type find_with( Q const& key, Less pred )
524 return contains( key, pred );
528 /// Checks whether the map contains \p key using \p equal predicate for searching (unordered list version)
530 The function is an analog of <tt>contains( key )</tt> but \p equal is used for key comparing.
531 \p Equal functor has the interface like \p std::equal_to.
533 template <typename Q, typename Equal, bool Sort = c_bSort>
534 typename std::enable_if<!Sort, value_type *>::type contains( Q const& key, Equal equal )
536 return find_at( &m_Head, key, equal );
539 template <typename Q, typename Equal, bool Sort = c_bSort>
540 CDS_DEPRECATED("deprecated, use contains()")
541 typename std::enable_if<!Sort, value_type *>::type find_with( Q const& key, Equal equal )
543 return contains( key, equal );
549 The function unlink all items from the list.
550 For each unlinked item the item disposer \p disp is called after unlinking.
552 This function is not thread-safe.
554 template <typename Disposer>
555 void clear( Disposer disp )
557 node_type * pHead = m_Head.m_pNext.exchange( &m_Tail, memory_model::memory_order_release );
559 while ( pHead != &m_Tail ) {
560 node_type * p = pHead->m_pNext.load(memory_model::memory_order_relaxed);
561 dispose_node( pHead, disp );
567 /// Clears the list using default disposer
569 The function clears the list using default (provided in class template) disposer functor.
576 /// Checks if the list is empty
579 return m_Head.m_pNext.load(memory_model::memory_order_relaxed) == &m_Tail;
582 /// Returns list's item count
584 The value returned depends on opt::item_counter option. For atomicity::empty_item_counter,
585 this function always returns 0.
587 <b>Warning</b>: even if you use real item counter and it returns 0, this fact is not mean that the list
588 is empty. To check list emptyness use \ref empty() method.
592 return m_ItemCounter.value();
597 // split-list support
598 bool insert_aux_node( node_type * pNode )
600 return insert_aux_node( &m_Head, pNode );
603 // split-list support
604 bool insert_aux_node( node_type * pHead, node_type * pNode )
606 assert( pHead != nullptr );
607 assert( pNode != nullptr );
609 // Hack: convert node_type to value_type.
610 // In principle, auxiliary node can be non-reducible to value_type
611 // We assume that comparator can correctly distinguish aux and regular node.
612 return insert_at( pHead, *node_traits::to_value_ptr( pNode ) );
615 bool insert_at( node_type * pHead, value_type& val )
621 search( pHead, val, pos, pred );
623 auto_lock_position alp( pos );
624 if ( validate( pos.pPred, pos.pCur )) {
625 if ( pos.pCur != &m_Tail && equal( *node_traits::to_value_ptr( *pos.pCur ), val, pred ) ) {
626 // failed: key already in list
630 link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
639 iterator insert_at_( node_type * pHead, value_type& val )
641 if ( insert_at( pHead, val ))
642 return iterator( node_traits::to_node_ptr( val ));
647 template <typename Func>
648 std::pair<iterator, bool> update_at_( node_type * pHead, value_type& val, Func func, bool bAllowInsert )
654 search( pHead, val, pos, pred );
656 auto_lock_position alp( pos );
657 if ( validate( pos.pPred, pos.pCur )) {
658 if ( pos.pCur != &m_Tail && equal( *node_traits::to_value_ptr( *pos.pCur ), val, pred )) {
659 // key already in the list
661 func( false, *node_traits::to_value_ptr( *pos.pCur ) , val );
662 return std::make_pair( iterator( pos.pCur ), false );
667 return std::make_pair( end(), false );
669 link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
670 func( true, val, val );
672 return std::make_pair( iterator( node_traits::to_node_ptr( val )), true );
679 template <typename Func>
680 std::pair<bool, bool> update_at( node_type * pHead, value_type& val, Func func, bool bAllowInsert )
682 std::pair<iterator, bool> ret = update_at_( pHead, val, func, bAllowInsert );
683 return std::make_pair( ret.first != end(), ret.second );
686 template <typename Q, typename Pred, typename Func>
687 bool find_at( node_type * pHead, Q& val, Pred pred, Func f )
691 search( pHead, val, pos, pred );
692 if ( pos.pCur != &m_Tail ) {
693 std::unique_lock< typename node_type::lock_type> al( pos.pCur->m_Lock );
694 if ( equal( *node_traits::to_value_ptr( *pos.pCur ), val, pred ) )
696 f( *node_traits::to_value_ptr( *pos.pCur ), val );
703 template <typename Q, typename Pred>
704 value_type * find_at( node_type * pHead, Q& val, Pred pred)
706 iterator it = find_at_( pHead, val, pred );
712 template <typename Q, typename Pred>
713 iterator find_at_( node_type * pHead, Q& val, Pred pred)
717 search( pHead, val, pos, pred );
718 if ( pos.pCur != &m_Tail ) {
719 if ( equal( *node_traits::to_value_ptr( *pos.pCur ), val, pred ))
720 return iterator( pos.pCur );
729 template <typename Q, typename Equal, bool Sort = c_bSort>
730 typename std::enable_if<!Sort, void>::type search( node_type * pHead, const Q& key, position& pos, Equal eq )
732 const node_type * pTail = &m_Tail;
734 node_type * pCur = pHead;
735 node_type * pPrev = pHead;
737 while ( pCur != pTail && ( pCur == pHead || !equal( *node_traits::to_value_ptr( *pCur ), key, eq ) )) {
739 pCur = pCur->m_pNext.load(memory_model::memory_order_acquire);
746 template <typename Q, typename Compare, bool Sort = c_bSort>
747 typename std::enable_if<Sort, void>::type search( node_type * pHead, const Q& key, position& pos, Compare cmp )
749 const node_type * pTail = &m_Tail;
751 node_type * pCur = pHead;
752 node_type * pPrev = pHead;
754 while ( pCur != pTail && ( pCur == pHead || cmp( *node_traits::to_value_ptr( *pCur ), key ) < 0 )) {
756 pCur = pCur->m_pNext.load(memory_model::memory_order_acquire);
763 template <typename L, typename R, typename Equal, bool Sort = c_bSort>
764 static typename std::enable_if<!Sort, bool>::type equal( L const& l, R const& r, Equal eq )
769 template <typename L, typename R, typename Compare, bool Sort = c_bSort>
770 static typename std::enable_if<Sort, bool>::type equal( L const& l, R const& r, Compare cmp )
772 return cmp(l, r) == 0;
775 static bool validate( node_type * pPred, node_type * pCur )
777 return pPred->m_pNext.load(memory_model::memory_order_acquire) == pCur;
781 template <typename Predicate>
782 void erase_for( Predicate pred )
784 node_type * pPred = nullptr;
785 node_type * pHead = m_Head.m_pNext.load( memory_model::memory_order_relaxed );
787 while ( pHead != &m_Tail ) {
788 node_type * p = pHead->m_pNext.load( memory_model::memory_order_relaxed );
789 if ( pred( *node_traits::to_value_ptr( pHead ))) {
790 assert( pPred != nullptr );
791 pPred->m_pNext.store( p, memory_model::memory_order_relaxed );
792 dispose_node( pHead, disposer() );
802 }} // namespace cds::intrusive
804 #endif // #ifndef CDSLIB_INTRUSIVE_LAZY_LIST_NOGC_H