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_MICHAEL_LIST_NOGC_H
32 #define CDSLIB_INTRUSIVE_MICHAEL_LIST_NOGC_H
34 #include <cds/intrusive/details/michael_list_base.h>
35 #include <cds/gc/nogc.h>
36 #include <cds/details/make_const_type.h>
38 namespace cds { namespace intrusive {
40 namespace michael_list {
44 - Tag - a tag used to distinguish between different implementation
46 template <typename Tag>
47 struct node<gc::nogc, Tag>
49 typedef gc::nogc gc ; ///< Garbage collector
50 typedef Tag tag ; ///< tag
52 typedef atomics::atomic< node * > atomic_ptr ; ///< atomic marked pointer
54 atomic_ptr m_pNext ; ///< pointer to the next node in the container
60 } // namespace michael_list
62 /// Michael's lock-free ordered single-linked list (template specialization for gc::nogc)
63 /** @ingroup cds_intrusive_list
64 \anchor cds_intrusive_MichaelList_nogc
66 This specialization is intended for so-called append-only usage when no item
67 reclamation may be performed. The class does not support item removal.
69 See \ref cds_intrusive_MichaelList_hp "MichaelList" for description of template parameters.
71 template < typename T,
72 #ifdef CDS_DOXYGEN_INVOKED
73 class Traits = michael_list::traits
78 class MichaelList<gc::nogc, T, Traits>
81 typedef gc::nogc gc; ///< Garbage collector
82 typedef T value_type; ///< type of value to be stored in the queue
83 typedef Traits traits; ///< List traits
85 typedef typename traits::hook hook; ///< hook type
86 typedef typename hook::node_type node_type; ///< node type
88 # ifdef CDS_DOXYGEN_INVOKED
89 typedef implementation_defined key_comparator ; ///< key comparison functor based on opt::compare and opt::less option setter.
91 typedef typename opt::details::make_comparator< value_type, traits >::type key_comparator;
94 typedef typename traits::disposer disposer; ///< disposer used
95 typedef typename get_node_traits< value_type, node_type, hook>::type node_traits ; ///< node traits
96 typedef typename michael_list::get_link_checker< node_type, traits::link_checker >::type link_checker; ///< link checker
98 typedef typename traits::back_off back_off; ///< back-off strategy
99 typedef typename traits::item_counter item_counter; ///< Item counting policy used
100 typedef typename traits::memory_model memory_model; ///< Memory ordering. See cds::opt::memory_model option
101 typedef typename traits::stat stat; ///< Internal statistics
104 static_assert((std::is_same< gc, typename node_type::gc >::value), "GC and node_type::gc must be the same type");
106 // Rebind traits (split-list support)
107 template <typename... Options>
108 struct rebind_traits {
112 , typename cds::opt::make_options< traits, Options...>::type
117 template <typename Stat>
118 using select_stat_wrapper = michael_list::select_stat_wrapper< Stat >;
122 typedef typename node_type::atomic_ptr atomic_node_ptr ; ///< Atomic node pointer
123 typedef atomic_node_ptr auxiliary_head ; ///< Auxiliary head type (for split-list support)
125 atomic_node_ptr m_pHead; ///< Head pointer
126 item_counter m_ItemCounter; ///< Item counter
127 stat m_Stat; ///< Internal statistics
130 /// Position pointer for item search
132 atomic_node_ptr * pPrev ; ///< Previous node
133 node_type * pCur ; ///< Current node
134 node_type * pNext ; ///< Next node
140 static void clear_links( node_type * pNode )
142 pNode->m_pNext.store( nullptr, memory_model::memory_order_release );
145 template <class Disposer>
146 static void dispose_node( node_type * pNode, Disposer disp )
148 clear_links( pNode );
149 disp( node_traits::to_value_ptr( *pNode ));
152 template <class Disposer>
153 static void dispose_value( value_type& val, Disposer disp )
155 dispose_node( node_traits::to_node_ptr( val ), disp );
158 static bool link_node( node_type * pNode, position& pos )
160 assert( pNode != nullptr );
161 link_checker::is_empty( pNode );
163 pNode->m_pNext.store( pos.pCur, memory_model::memory_order_relaxed );
164 if ( cds_likely( pos.pPrev->compare_exchange_strong( pos.pCur, pNode, memory_model::memory_order_release, atomics::memory_order_relaxed )))
167 pNode->m_pNext.store( nullptr, memory_model::memory_order_relaxed );
174 template <bool IsConst>
177 friend class MichaelList;
178 value_type * m_pNode;
183 node_type * pNode = node_traits::to_node_ptr( *m_pNode )->m_pNext.load(memory_model::memory_order_acquire);
185 m_pNode = node_traits::to_value_ptr( *pNode );
192 explicit iterator_type( node_type * pNode)
195 m_pNode = node_traits::to_value_ptr( *pNode );
199 explicit iterator_type( atomic_node_ptr const& refNode)
201 node_type * pNode = refNode.load(memory_model::memory_order_relaxed);
203 m_pNode = node_traits::to_value_ptr( *pNode );
209 typedef typename cds::details::make_const_type<value_type, IsConst>::pointer value_ptr;
210 typedef typename cds::details::make_const_type<value_type, IsConst>::reference value_ref;
216 iterator_type( const iterator_type& src )
217 : m_pNode( src.m_pNode )
220 value_ptr operator ->() const
225 value_ref operator *() const
227 assert( m_pNode != nullptr );
232 iterator_type& operator ++()
239 iterator_type operator ++(int)
241 iterator_type i(*this);
246 iterator_type& operator = (const iterator_type& src)
248 m_pNode = src.m_pNode;
253 bool operator ==(iterator_type<C> const& i ) const
255 return m_pNode == i.m_pNode;
258 bool operator !=(iterator_type<C> const& i ) const
260 return m_pNode != i.m_pNode;
267 typedef iterator_type<false> iterator;
268 /// Const forward iterator
269 typedef iterator_type<true> const_iterator;
271 /// Returns a forward iterator addressing the first element in a list
273 For empty list \code begin() == end() \endcode
277 return iterator(m_pHead.load(memory_model::memory_order_relaxed));
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.
283 Internally, <tt>end</tt> returning value equals to \p nullptr.
285 The returned value can be used only to control reaching the end of the list.
286 For empty list \code begin() == end() \endcode
293 /// Returns a forward const iterator addressing the first element in a list
294 const_iterator begin() const
296 return const_iterator(m_pHead.load(memory_model::memory_order_relaxed));
298 /// Returns a forward const iterator addressing the first element in a list
299 const_iterator cbegin() const
301 return const_iterator(m_pHead.load(memory_model::memory_order_relaxed));
304 /// Returns an const iterator that addresses the location succeeding the last element in a list
305 const_iterator end() const
307 return const_iterator();
309 /// Returns an const iterator that addresses the location succeeding the last element in a list
310 const_iterator cend() const
312 return const_iterator();
316 /// Default constructor initializes empty list
322 template <typename Stat, typename = std::enable_if<std::is_same<stat, michael_list::wrapped_stat<Stat>>::value >>
323 explicit MichaelList( Stat& st )
329 /// Destroys the list objects
337 The function inserts \p val in the list if the list does not contain
338 an item with key equal to \p val.
340 Returns \p true if \p val is linked into the list, \p false otherwise.
342 bool insert( value_type& val )
344 return insert_at( m_pHead, val );
349 The operation performs inserting or changing data with lock-free manner.
351 If the item \p val not found in the list, then \p val is inserted into the list
352 iff \p bAllowInsert is \p true.
353 Otherwise, the functor \p func is called with item found.
354 The functor signature is:
357 void operator()( bool bNew, value_type& item, value_type& val );
361 - \p bNew - \p true if the item has been inserted, \p false otherwise
362 - \p item - item of the list
363 - \p val - argument \p val passed into the \p update() function
364 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
365 refer to the same thing.
367 The functor may change non-key fields of the \p item; however, \p func must guarantee
368 that during changing no any other modifications could be made on this item by concurrent threads.
370 Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successful,
371 \p second is \p true if new item has been added or \p false if the item with \p key
372 already is in the list.
374 template <typename Func>
375 std::pair<bool, bool> update( value_type& val, Func func, bool bAllowInsert = true )
377 return update_at( m_pHead, val, func, bAllowInsert );
380 template <typename Func>
381 CDS_DEPRECATED("ensure() is deprecated, use update()")
382 std::pair<bool, bool> ensure( value_type& val, Func func )
384 return update( val, func );
388 /// Finds the key \p val
389 /** \anchor cds_intrusive_MichaelList_nogc_find_func
390 The function searches the item with key equal to \p key
391 and calls the functor \p f for item found.
392 The interface of \p Func functor is:
395 void operator()( value_type& item, Q& key );
398 where \p item is the item found, \p key is the <tt>find</tt> function argument.
400 The functor can change non-key fields of \p item.
401 The function \p find does not serialize simultaneous access to the list \p item. If such access is
402 possible you must provide your own synchronization schema to exclude unsafe item modifications.
404 The function returns \p true if \p val is found, \p false otherwise.
406 template <typename Q, typename Func>
407 bool find( Q& key, Func f )
409 return find_at( m_pHead, key, key_comparator(), f );
412 template <typename Q, typename Func>
413 bool find( Q const& key, Func f )
415 return find_at( m_pHead, key, key_comparator(), f );
419 /// Finds the key \p key using \p pred predicate for searching
421 The function is an analog of \ref cds_intrusive_MichaelList_nogc_find_func "find(Q&, Func)"
422 but \p pred is used for key comparing.
423 \p Less functor has the interface like \p std::less.
424 \p pred must imply the same element order as the comparator used for building the list.
426 template <typename Q, typename Less, typename Func>
427 bool find_with( Q& key, Less pred, Func f )
430 return find_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>(), f );
433 template <typename Q, typename Less, typename Func>
434 bool find_with( Q const& key, Less pred, Func f )
437 return find_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>(), f );
441 /// Checks whether the list contains \p key
443 The function searches the item with key equal to \p key
444 and returns \p true if it is found, and \p false otherwise.
446 template <typename Q>
447 value_type * contains( Q const& key )
449 return find_at( m_pHead, key, key_comparator());
452 template <typename Q>
453 CDS_DEPRECATED("deprecated, use contains()")
454 value_type * find( Q const& key )
456 return contains( key );
460 /// Checks whether the map contains \p key using \p pred predicate for searching
462 The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
463 \p Less functor has the interface like \p std::less.
464 \p Less must imply the same element order as the comparator used for building the list.
466 template <typename Q, typename Less>
467 value_type * contains( Q const& key, Less pred )
470 return find_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>());
473 template <typename Q, typename Less>
474 CDS_DEPRECATED("deprecated, use contains()")
475 value_type * find_with( Q const& key, Less pred )
477 return contains( key, pred );
483 The function unlink all items from the list.
485 For each unlinked item the item disposer \p disp is called after unlinking.
487 template <typename Disposer>
488 void clear( Disposer disp )
490 node_type * pHead = m_pHead.load(memory_model::memory_order_relaxed);
491 do {} while ( cds_unlikely( !m_pHead.compare_exchange_weak( pHead, nullptr, memory_model::memory_order_relaxed )));
494 node_type * p = pHead->m_pNext.load(memory_model::memory_order_relaxed);
495 dispose_node( pHead, disp );
501 /// Clears the list using default disposer
503 The function clears the list using default (provided in class template) disposer functor.
510 /// Checks if the list is empty
513 return m_pHead.load( memory_model::memory_order_relaxed ) == nullptr;
516 /// Returns list's item count
518 The value returned depends on item counter provided by \p Traits. For \p atomicity::empty_item_counter,
519 this function always returns 0.
521 @note Even if you use real item counter and it returns 0, this fact does not mean that the list
522 is empty. To check list emptyness use \p empty() method.
526 return m_ItemCounter.value();
529 /// Returns const reference to internal statistics
530 stat const& statistics() const
537 // split-list support
538 bool insert_aux_node( node_type * pNode )
540 return insert_aux_node( m_pHead, pNode );
543 // split-list support
544 bool insert_aux_node( atomic_node_ptr& refHead, node_type * pNode )
546 assert( pNode != nullptr );
548 // Hack: convert node_type to value_type.
549 // In principle, auxiliary node can be non-reducible to value_type
550 // We assume that comparator can correctly distinguish aux and regular node.
551 return insert_at( refHead, *node_traits::to_value_ptr( pNode ));
554 bool insert_at( atomic_node_ptr& refHead, value_type& val )
559 if ( search( refHead, val, key_comparator(), pos )) {
560 m_Stat.onInsertFailed();
564 if ( link_node( node_traits::to_node_ptr( val ), pos )) {
566 m_Stat.onInsertSuccess();
570 m_Stat.onInsertRetry();
574 iterator insert_at_( atomic_node_ptr& refHead, value_type& val )
576 if ( insert_at( refHead, val ))
577 return iterator( node_traits::to_node_ptr( val ));
581 template <typename Func>
582 std::pair<iterator, bool> update_at_( atomic_node_ptr& refHead, value_type& val, Func func, bool bAllowInsert )
587 if ( search( refHead, val, key_comparator(), pos )) {
588 assert( key_comparator()( val, *node_traits::to_value_ptr( *pos.pCur )) == 0 );
590 func( false, *node_traits::to_value_ptr( *pos.pCur ) , val );
591 m_Stat.onUpdateExisting();
592 return std::make_pair( iterator( pos.pCur ), false );
595 if ( !bAllowInsert ) {
596 m_Stat.onUpdateFailed();
597 return std::make_pair( end(), false );
600 if ( link_node( node_traits::to_node_ptr( val ), pos )) {
602 func( true, val , val );
603 m_Stat.onUpdateNew();
604 return std::make_pair( iterator( node_traits::to_node_ptr( val )), true );
608 m_Stat.onUpdateRetry();
612 template <typename Func>
613 std::pair<bool, bool> update_at( atomic_node_ptr& refHead, value_type& val, Func func, bool bAllowInsert )
615 std::pair<iterator, bool> ret = update_at_( refHead, val, func, bAllowInsert );
616 return std::make_pair( ret.first != end(), ret.second );
619 template <typename Q, typename Compare, typename Func>
620 bool find_at( atomic_node_ptr& refHead, Q& val, Compare cmp, Func f )
624 if ( search( refHead, val, cmp, pos )) {
625 assert( pos.pCur != nullptr );
626 f( *node_traits::to_value_ptr( *pos.pCur ), val );
627 m_Stat.onFindSuccess();
631 m_Stat.onFindFailed();
635 template <typename Q, typename Compare>
636 value_type * find_at( atomic_node_ptr& refHead, Q const& val, Compare cmp )
638 iterator it = find_at_( refHead, val, cmp );
640 m_Stat.onFindSuccess();
644 m_Stat.onFindFailed();
648 template <typename Q, typename Compare>
649 iterator find_at_( atomic_node_ptr& refHead, Q const& val, Compare cmp )
653 if ( search( refHead, val, cmp, pos )) {
654 assert( pos.pCur != nullptr );
655 m_Stat.onFindSuccess();
656 return iterator( pos.pCur );
659 m_Stat.onFindFailed();
668 template <typename Q, typename Compare >
669 bool search( atomic_node_ptr& refHead, const Q& val, Compare cmp, position& pos )
671 atomic_node_ptr * pPrev;
679 pCur = pPrev->load(memory_model::memory_order_acquire);
690 pNext = pCur->m_pNext.load(memory_model::memory_order_relaxed);
691 if ( cds_unlikely( pCur->m_pNext.load(memory_model::memory_order_acquire) != pNext )) {
696 if ( cds_unlikely( pPrev->load(memory_model::memory_order_acquire) != pCur )) {
701 assert( pCur != nullptr );
702 int nCmp = cmp( *node_traits::to_value_ptr( *pCur ), val );
709 pPrev = &( pCur->m_pNext );
715 template <typename Predicate>
716 void erase_for( Predicate pred )
718 node_type * pPred = nullptr;
719 node_type * pHead = m_pHead.load( memory_model::memory_order_relaxed );
721 node_type * p = pHead->m_pNext.load( memory_model::memory_order_relaxed );
722 if ( pred( *node_traits::to_value_ptr( pHead ))) {
723 assert( pPred != nullptr );
724 pPred->m_pNext.store( p, memory_model::memory_order_relaxed );
725 dispose_node( pHead, disposer());
735 }} // namespace cds::intrusive
737 #endif // #ifndef CDSLIB_INTRUSIVE_MICHAEL_LIST_NOGC_H