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_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
118 typedef typename node_type::atomic_ptr atomic_node_ptr ; ///< Atomic node pointer
119 typedef atomic_node_ptr auxiliary_head ; ///< Auxiliary head type (for split-list support)
121 atomic_node_ptr m_pHead; ///< Head pointer
122 item_counter m_ItemCounter; ///< Item counter
123 stat m_Stat; ///< Internal statistics
126 /// Position pointer for item search
128 atomic_node_ptr * pPrev ; ///< Previous node
129 node_type * pCur ; ///< Current node
130 node_type * pNext ; ///< Next node
136 static void clear_links( node_type * pNode )
138 pNode->m_pNext.store( nullptr, memory_model::memory_order_release );
141 template <class Disposer>
142 static void dispose_node( node_type * pNode, Disposer disp )
144 clear_links( pNode );
145 disp( node_traits::to_value_ptr( *pNode ));
148 template <class Disposer>
149 static void dispose_value( value_type& val, Disposer disp )
151 dispose_node( node_traits::to_node_ptr( val ), disp );
154 static bool link_node( node_type * pNode, position& pos )
156 assert( pNode != nullptr );
157 link_checker::is_empty( pNode );
159 pNode->m_pNext.store( pos.pCur, memory_model::memory_order_relaxed );
160 if ( cds_likely( pos.pPrev->compare_exchange_strong( pos.pCur, pNode, memory_model::memory_order_release, atomics::memory_order_relaxed )))
163 pNode->m_pNext.store( nullptr, memory_model::memory_order_relaxed );
170 template <bool IsConst>
173 friend class MichaelList;
174 value_type * m_pNode;
179 node_type * pNode = node_traits::to_node_ptr( *m_pNode )->m_pNext.load(memory_model::memory_order_acquire);
181 m_pNode = node_traits::to_value_ptr( *pNode );
188 explicit iterator_type( node_type * pNode)
191 m_pNode = node_traits::to_value_ptr( *pNode );
195 explicit iterator_type( atomic_node_ptr const& refNode)
197 node_type * pNode = refNode.load(memory_model::memory_order_relaxed);
199 m_pNode = node_traits::to_value_ptr( *pNode );
205 typedef typename cds::details::make_const_type<value_type, IsConst>::pointer value_ptr;
206 typedef typename cds::details::make_const_type<value_type, IsConst>::reference value_ref;
212 iterator_type( const iterator_type& src )
213 : m_pNode( src.m_pNode )
216 value_ptr operator ->() const
221 value_ref operator *() const
223 assert( m_pNode != nullptr );
228 iterator_type& operator ++()
235 iterator_type operator ++(int)
237 iterator_type i(*this);
242 iterator_type& operator = (const iterator_type& src)
244 m_pNode = src.m_pNode;
249 bool operator ==(iterator_type<C> const& i ) const
251 return m_pNode == i.m_pNode;
254 bool operator !=(iterator_type<C> const& i ) const
256 return m_pNode != i.m_pNode;
263 typedef iterator_type<false> iterator;
264 /// Const forward iterator
265 typedef iterator_type<true> const_iterator;
267 /// Returns a forward iterator addressing the first element in a list
269 For empty list \code begin() == end() \endcode
273 return iterator(m_pHead.load(memory_model::memory_order_relaxed) );
276 /// Returns an iterator that addresses the location succeeding the last element in a list
278 Do not use the value returned by <tt>end</tt> function to access any item.
279 Internally, <tt>end</tt> returning value equals to \p nullptr.
281 The returned value can be used only to control reaching the end of the list.
282 For empty list \code begin() == end() \endcode
289 /// Returns a forward const iterator addressing the first element in a list
290 const_iterator begin() const
292 return const_iterator(m_pHead.load(memory_model::memory_order_relaxed) );
294 /// Returns a forward const iterator addressing the first element in a list
295 const_iterator cbegin() const
297 return const_iterator(m_pHead.load(memory_model::memory_order_relaxed) );
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();
305 /// Returns an const iterator that addresses the location succeeding the last element in a list
306 const_iterator cend() const
308 return const_iterator();
312 /// Default constructor initializes empty list
318 template <typename Stat, typename = std::enable_if<std::is_same<stat, michael_list::wrapped_stat<Stat>>::value >>
319 explicit MichaelList( Stat& st )
325 /// Destroys the list objects
333 The function inserts \p val in the list if the list does not contain
334 an item with key equal to \p val.
336 Returns \p true if \p val is linked into the list, \p false otherwise.
338 bool insert( value_type& val )
340 return insert_at( m_pHead, val );
345 The operation performs inserting or changing data with lock-free manner.
347 If the item \p val not found in the list, then \p val is inserted into the list
348 iff \p bAllowInsert is \p true.
349 Otherwise, the functor \p func is called with item found.
350 The functor signature is:
353 void operator()( bool bNew, value_type& item, value_type& val );
357 - \p bNew - \p true if the item has been inserted, \p false otherwise
358 - \p item - item of the list
359 - \p val - argument \p val passed into the \p update() function
360 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
361 refer to the same thing.
363 The functor may change non-key fields of the \p item; however, \p func must guarantee
364 that during changing no any other modifications could be made on this item by concurrent threads.
366 Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successful,
367 \p second is \p true if new item has been added or \p false if the item with \p key
368 already is in the list.
370 template <typename Func>
371 std::pair<bool, bool> update( value_type& val, Func func, bool bAllowInsert = true )
373 return update_at( m_pHead, val, func, bAllowInsert );
376 template <typename Func>
377 CDS_DEPRECATED("ensure() is deprecated, use update()")
378 std::pair<bool, bool> ensure( value_type& val, Func func )
380 return update( val, func );
384 /// Finds the key \p val
385 /** \anchor cds_intrusive_MichaelList_nogc_find_func
386 The function searches the item with key equal to \p key
387 and calls the functor \p f for item found.
388 The interface of \p Func functor is:
391 void operator()( value_type& item, Q& key );
394 where \p item is the item found, \p key is the <tt>find</tt> function argument.
396 The functor can change non-key fields of \p item.
397 The function \p find does not serialize simultaneous access to the list \p item. If such access is
398 possible you must provide your own synchronization schema to exclude unsafe item modifications.
400 The function returns \p true if \p val is found, \p false otherwise.
402 template <typename Q, typename Func>
403 bool find( Q& key, Func f )
405 return find_at( m_pHead, key, key_comparator(), f );
408 template <typename Q, typename Func>
409 bool find( Q const& key, Func f )
411 return find_at( m_pHead, key, key_comparator(), f );
415 /// Finds the key \p key using \p pred predicate for searching
417 The function is an analog of \ref cds_intrusive_MichaelList_nogc_find_func "find(Q&, Func)"
418 but \p pred is used for key comparing.
419 \p Less functor has the interface like \p std::less.
420 \p pred must imply the same element order as the comparator used for building the list.
422 template <typename Q, typename Less, typename Func>
423 bool find_with( Q& key, Less pred, Func f )
426 return find_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>(), f );
429 template <typename Q, typename Less, typename Func>
430 bool find_with( Q const& key, Less pred, Func f )
433 return find_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>(), f );
437 /// Checks whether the list contains \p key
439 The function searches the item with key equal to \p key
440 and returns \p true if it is found, and \p false otherwise.
442 template <typename Q>
443 value_type * contains( Q const& key )
445 return find_at( m_pHead, key, key_comparator() );
448 template <typename Q>
449 CDS_DEPRECATED("deprecated, use contains()")
450 value_type * find( Q const& key )
452 return contains( key );
456 /// Checks whether the map contains \p key using \p pred predicate for searching
458 The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
459 \p Less functor has the interface like \p std::less.
460 \p Less must imply the same element order as the comparator used for building the list.
462 template <typename Q, typename Less>
463 value_type * contains( Q const& key, Less pred )
466 return find_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>());
469 template <typename Q, typename Less>
470 CDS_DEPRECATED("deprecated, use contains()")
471 value_type * find_with( Q const& key, Less pred )
473 return contains( key, pred );
479 The function unlink all items from the list.
481 For each unlinked item the item disposer \p disp is called after unlinking.
483 template <typename Disposer>
484 void clear( Disposer disp )
486 node_type * pHead = m_pHead.load(memory_model::memory_order_relaxed);
487 do {} while ( cds_unlikely( !m_pHead.compare_exchange_weak( pHead, nullptr, memory_model::memory_order_relaxed )));
490 node_type * p = pHead->m_pNext.load(memory_model::memory_order_relaxed);
491 dispose_node( pHead, disp );
497 /// Clears the list using default disposer
499 The function clears the list using default (provided in class template) disposer functor.
506 /// Checks if the list is empty
509 return m_pHead.load( memory_model::memory_order_relaxed ) == nullptr;
512 /// Returns list's item count
514 The value returned depends on item counter provided by \p Traits. For \p atomicity::empty_item_counter,
515 this function always returns 0.
517 @note Even if you use real item counter and it returns 0, this fact does not mean that the list
518 is empty. To check list emptyness use \p empty() method.
522 return m_ItemCounter.value();
525 /// Returns const reference to internal statistics
526 stat const& statistics() const
533 // split-list support
534 bool insert_aux_node( node_type * pNode )
536 return insert_aux_node( m_pHead, pNode );
539 // split-list support
540 bool insert_aux_node( atomic_node_ptr& refHead, node_type * pNode )
542 assert( pNode != nullptr );
544 // Hack: convert node_type to value_type.
545 // In principle, auxiliary node can be non-reducible to value_type
546 // We assume that comparator can correctly distinguish aux and regular node.
547 return insert_at( refHead, *node_traits::to_value_ptr( pNode ) );
550 bool insert_at( atomic_node_ptr& refHead, value_type& val )
555 if ( search( refHead, val, key_comparator(), pos )) {
556 m_Stat.onInsertFailed();
560 if ( link_node( node_traits::to_node_ptr( val ), pos ) ) {
562 m_Stat.onInsertSuccess();
566 m_Stat.onInsertRetry();
570 iterator insert_at_( atomic_node_ptr& refHead, value_type& val )
572 if ( insert_at( refHead, val ))
573 return iterator( node_traits::to_node_ptr( val ));
577 template <typename Func>
578 std::pair<iterator, bool> update_at_( atomic_node_ptr& refHead, value_type& val, Func func, bool bAllowInsert )
583 if ( search( refHead, val, key_comparator(), pos ) ) {
584 assert( key_comparator()( val, *node_traits::to_value_ptr( *pos.pCur ) ) == 0 );
586 func( false, *node_traits::to_value_ptr( *pos.pCur ) , val );
587 m_Stat.onUpdateExisting();
588 return std::make_pair( iterator( pos.pCur ), false );
591 if ( !bAllowInsert ) {
592 m_Stat.onUpdateFailed();
593 return std::make_pair( end(), false );
596 if ( link_node( node_traits::to_node_ptr( val ), pos ) ) {
598 func( true, val , val );
599 m_Stat.onUpdateNew();
600 return std::make_pair( iterator( node_traits::to_node_ptr( val )), true );
604 m_Stat.onUpdateRetry();
608 template <typename Func>
609 std::pair<bool, bool> update_at( atomic_node_ptr& refHead, value_type& val, Func func, bool bAllowInsert )
611 std::pair<iterator, bool> ret = update_at_( refHead, val, func, bAllowInsert );
612 return std::make_pair( ret.first != end(), ret.second );
615 template <typename Q, typename Compare, typename Func>
616 bool find_at( atomic_node_ptr& refHead, Q& val, Compare cmp, Func f )
620 if ( search( refHead, val, cmp, pos ) ) {
621 assert( pos.pCur != nullptr );
622 f( *node_traits::to_value_ptr( *pos.pCur ), val );
623 m_Stat.onFindSuccess();
627 m_Stat.onFindFailed();
631 template <typename Q, typename Compare>
632 value_type * find_at( atomic_node_ptr& refHead, Q const& val, Compare cmp )
634 iterator it = find_at_( refHead, val, cmp );
636 m_Stat.onFindSuccess();
640 m_Stat.onFindFailed();
644 template <typename Q, typename Compare>
645 iterator find_at_( atomic_node_ptr& refHead, Q const& val, Compare cmp )
649 if ( search( refHead, val, cmp, pos ) ) {
650 assert( pos.pCur != nullptr );
651 m_Stat.onFindSuccess();
652 return iterator( pos.pCur );
655 m_Stat.onFindFailed();
664 template <typename Q, typename Compare >
665 bool search( atomic_node_ptr& refHead, const Q& val, Compare cmp, position& pos )
667 atomic_node_ptr * pPrev;
675 pCur = pPrev->load(memory_model::memory_order_acquire);
686 pNext = pCur->m_pNext.load(memory_model::memory_order_relaxed);
687 if ( cds_unlikely( pCur->m_pNext.load(memory_model::memory_order_acquire) != pNext )) {
692 if ( cds_unlikely( pPrev->load(memory_model::memory_order_acquire) != pCur )) {
697 assert( pCur != nullptr );
698 int nCmp = cmp( *node_traits::to_value_ptr( *pCur ), val );
705 pPrev = &( pCur->m_pNext );
711 template <typename Predicate>
712 void erase_for( Predicate pred )
714 node_type * pPred = nullptr;
715 node_type * pHead = m_pHead.load( memory_model::memory_order_relaxed );
717 node_type * p = pHead->m_pNext.load( memory_model::memory_order_relaxed );
718 if ( pred( *node_traits::to_value_ptr( pHead ))) {
719 assert( pPred != nullptr );
720 pPred->m_pNext.store( p, memory_model::memory_order_relaxed );
721 dispose_node( pHead, disposer());
731 }} // namespace cds::intrusive
733 #endif // #ifndef CDSLIB_INTRUSIVE_MICHAEL_LIST_NOGC_H