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>
39 namespace cds { namespace intrusive {
41 namespace michael_list {
45 - Tag - a tag used to distinguish between different implementation
47 template <typename Tag>
48 struct node<gc::nogc, Tag>
50 typedef gc::nogc gc ; ///< Garbage collector
51 typedef Tag tag ; ///< tag
53 typedef atomics::atomic< node * > atomic_ptr ; ///< atomic marked pointer
55 atomic_ptr m_pNext ; ///< pointer to the next node in the container
61 } // namespace michael_list
63 /// Michael's lock-free ordered single-linked list (template specialization for gc::nogc)
64 /** @ingroup cds_intrusive_list
65 \anchor cds_intrusive_MichaelList_nogc
67 This specialization is intended for so-called append-only usage when no item
68 reclamation may be performed. The class does not support item removal.
70 See \ref cds_intrusive_MichaelList_hp "MichaelList" for description of template parameters.
72 template < typename T,
73 #ifdef CDS_DOXYGEN_INVOKED
74 class Traits = michael_list::traits
79 class MichaelList<gc::nogc, T, Traits>
82 typedef gc::nogc gc; ///< Garbage collector
83 typedef T value_type; ///< type of value to be stored in the queue
84 typedef Traits traits; ///< List traits
86 typedef typename traits::hook hook; ///< hook type
87 typedef typename hook::node_type node_type; ///< node type
89 # ifdef CDS_DOXYGEN_INVOKED
90 typedef implementation_defined key_comparator ; ///< key comparison functor based on opt::compare and opt::less option setter.
92 typedef typename opt::details::make_comparator< value_type, traits >::type key_comparator;
95 typedef typename traits::disposer disposer; ///< disposer used
96 typedef typename get_node_traits< value_type, node_type, hook>::type node_traits ; ///< node traits
97 typedef typename michael_list::get_link_checker< node_type, traits::link_checker >::type link_checker; ///< link checker
99 typedef typename traits::back_off back_off; ///< back-off strategy
100 typedef typename traits::item_counter item_counter; ///< Item counting policy used
101 typedef typename traits::memory_model memory_model; ///< Memory ordering. See cds::opt::memory_model option
104 // Rebind traits (split-list support)
105 template <typename... Options>
106 struct rebind_traits {
110 , typename cds::opt::make_options< traits, Options...>::type
116 typedef typename node_type::atomic_ptr atomic_node_ptr ; ///< Atomic node pointer
117 typedef atomic_node_ptr auxiliary_head ; ///< Auxiliary head type (for split-list support)
119 atomic_node_ptr m_pHead; ///< Head pointer
120 item_counter m_ItemCounter; ///< Item counter
123 /// Position pointer for item search
125 atomic_node_ptr * pPrev ; ///< Previous node
126 node_type * pCur ; ///< Current node
127 node_type * pNext ; ///< Next node
133 static void clear_links( node_type * pNode )
135 pNode->m_pNext.store( nullptr, memory_model::memory_order_release );
138 template <class Disposer>
139 static void dispose_node( node_type * pNode, Disposer disp )
141 clear_links( pNode );
142 disp( node_traits::to_value_ptr( *pNode ));
145 template <class Disposer>
146 static void dispose_value( value_type& val, Disposer disp )
148 dispose_node( node_traits::to_node_ptr( val ), disp );
151 static bool link_node( node_type * pNode, position& pos )
153 assert( pNode != nullptr );
154 link_checker::is_empty( pNode );
156 pNode->m_pNext.store( pos.pCur, memory_model::memory_order_relaxed );
157 if ( cds_likely( pos.pPrev->compare_exchange_strong( pos.pCur, pNode, memory_model::memory_order_release, atomics::memory_order_relaxed )))
160 pNode->m_pNext.store( nullptr, memory_model::memory_order_relaxed );
167 template <bool IsConst>
170 friend class MichaelList;
171 value_type * m_pNode;
176 node_type * pNode = node_traits::to_node_ptr( *m_pNode )->m_pNext.load(memory_model::memory_order_acquire);
178 m_pNode = node_traits::to_value_ptr( *pNode );
185 explicit iterator_type( node_type * pNode)
188 m_pNode = node_traits::to_value_ptr( *pNode );
192 explicit iterator_type( atomic_node_ptr const& refNode)
194 node_type * pNode = refNode.load(memory_model::memory_order_relaxed);
196 m_pNode = node_traits::to_value_ptr( *pNode );
202 typedef typename cds::details::make_const_type<value_type, IsConst>::pointer value_ptr;
203 typedef typename cds::details::make_const_type<value_type, IsConst>::reference value_ref;
209 iterator_type( const iterator_type& src )
210 : m_pNode( src.m_pNode )
213 value_ptr operator ->() const
218 value_ref operator *() const
220 assert( m_pNode != nullptr );
225 iterator_type& operator ++()
232 iterator_type operator ++(int)
234 iterator_type i(*this);
239 iterator_type& operator = (const iterator_type& src)
241 m_pNode = src.m_pNode;
246 bool operator ==(iterator_type<C> const& i ) const
248 return m_pNode == i.m_pNode;
251 bool operator !=(iterator_type<C> const& i ) const
253 return m_pNode != i.m_pNode;
260 typedef iterator_type<false> iterator;
261 /// Const forward iterator
262 typedef iterator_type<true> const_iterator;
264 /// Returns a forward iterator addressing the first element in a list
266 For empty list \code begin() == end() \endcode
270 return iterator(m_pHead.load(memory_model::memory_order_relaxed) );
273 /// Returns an iterator that addresses the location succeeding the last element in a list
275 Do not use the value returned by <tt>end</tt> function to access any item.
276 Internally, <tt>end</tt> returning value equals to \p nullptr.
278 The returned value can be used only to control reaching the end of the list.
279 For empty list \code begin() == end() \endcode
286 /// Returns a forward const iterator addressing the first element in a list
287 const_iterator begin() const
289 return const_iterator(m_pHead.load(memory_model::memory_order_relaxed) );
291 /// Returns a forward const iterator addressing the first element in a list
292 const_iterator cbegin() const
294 return const_iterator(m_pHead.load(memory_model::memory_order_relaxed) );
297 /// Returns an const iterator that addresses the location succeeding the last element in a list
298 const_iterator end() const
300 return const_iterator();
302 /// Returns an const iterator that addresses the location succeeding the last element in a list
303 const_iterator cend() const
305 return const_iterator();
309 /// Default constructor initializes empty list
313 static_assert( (std::is_same< gc, typename node_type::gc >::value), "GC and node_type::gc must be the same type" );
316 /// Destroys the list objects
324 The function inserts \p val in the list if the list does not contain
325 an item with key equal to \p val.
327 Returns \p true if \p val is linked into the list, \p false otherwise.
329 bool insert( value_type& val )
331 return insert_at( m_pHead, val );
336 The operation performs inserting or changing data with lock-free manner.
338 If the item \p val not found in the list, then \p val is inserted into the list
339 iff \p bAllowInsert is \p true.
340 Otherwise, the functor \p func is called with item found.
341 The functor signature is:
344 void operator()( bool bNew, value_type& item, value_type& val );
348 - \p bNew - \p true if the item has been inserted, \p false otherwise
349 - \p item - item of the list
350 - \p val - argument \p val passed into the \p update() function
351 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
352 refer to the same thing.
354 The functor may change non-key fields of the \p item; however, \p func must guarantee
355 that during changing no any other modifications could be made on this item by concurrent threads.
357 Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successful,
358 \p second is \p true if new item has been added or \p false if the item with \p key
359 already is in the list.
361 template <typename Func>
362 std::pair<bool, bool> update( value_type& val, Func func, bool bAllowInsert = true )
364 return update_at( m_pHead, val, func, bAllowInsert );
367 template <typename Func>
368 CDS_DEPRECATED("ensure() is deprecated, use update()")
369 std::pair<bool, bool> ensure( value_type& val, Func func )
371 return update( val, func );
375 /// Finds the key \p val
376 /** \anchor cds_intrusive_MichaelList_nogc_find_func
377 The function searches the item with key equal to \p key
378 and calls the functor \p f for item found.
379 The interface of \p Func functor is:
382 void operator()( value_type& item, Q& key );
385 where \p item is the item found, \p key is the <tt>find</tt> function argument.
387 The functor can change non-key fields of \p item.
388 The function \p find does not serialize simultaneous access to the list \p item. If such access is
389 possible you must provide your own synchronization schema to exclude unsafe item modifications.
391 The function returns \p true if \p val is found, \p false otherwise.
393 template <typename Q, typename Func>
394 bool find( Q& key, Func f )
396 return find_at( m_pHead, key, key_comparator(), f );
399 template <typename Q, typename Func>
400 bool find( Q const& key, Func f )
402 return find_at( m_pHead, key, key_comparator(), f );
406 /// Finds the key \p key using \p pred predicate for searching
408 The function is an analog of \ref cds_intrusive_MichaelList_nogc_find_func "find(Q&, Func)"
409 but \p pred is used for key comparing.
410 \p Less functor has the interface like \p std::less.
411 \p pred must imply the same element order as the comparator used for building the list.
413 template <typename Q, typename Less, typename Func>
414 bool find_with( Q& key, Less pred, Func f )
417 return find_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>(), f );
420 template <typename Q, typename Less, typename Func>
421 bool find_with( Q const& key, Less pred, Func f )
424 return find_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>(), f );
428 /// Checks whether the list contains \p key
430 The function searches the item with key equal to \p key
431 and returns \p true if it is found, and \p false otherwise.
433 template <typename Q>
434 value_type * contains( Q const& key )
436 return find_at( m_pHead, key, key_comparator() );
439 template <typename Q>
440 CDS_DEPRECATED("deprecated, use contains()")
441 value_type * find( Q const& key )
443 return contains( key );
447 /// Checks whether the map contains \p key using \p pred predicate for searching
449 The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
450 \p Less functor has the interface like \p std::less.
451 \p Less must imply the same element order as the comparator used for building the list.
453 template <typename Q, typename Less>
454 value_type * contains( Q const& key, Less pred )
457 return find_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>());
460 template <typename Q, typename Less>
461 CDS_DEPRECATED("deprecated, use contains()")
462 value_type * find_with( Q const& key, Less pred )
464 return contains( key, pred );
470 The function unlink all items from the list.
472 For each unlinked item the item disposer \p disp is called after unlinking.
474 template <typename Disposer>
475 void clear( Disposer disp )
477 node_type * pHead = m_pHead.load(memory_model::memory_order_relaxed);
478 do {} while ( cds_unlikely( !m_pHead.compare_exchange_weak( pHead, nullptr, memory_model::memory_order_relaxed )));
481 node_type * p = pHead->m_pNext.load(memory_model::memory_order_relaxed);
482 dispose_node( pHead, disp );
488 /// Clears the list using default disposer
490 The function clears the list using default (provided in class template) disposer functor.
497 /// Checks if the list is empty
500 return m_pHead.load( memory_model::memory_order_relaxed ) == nullptr;
503 /// Returns list's item count
505 The value returned depends on item counter provided by \p Traits. For \p atomicity::empty_item_counter,
506 this function always returns 0.
508 @note Even if you use real item counter and it returns 0, this fact does not mean that the list
509 is empty. To check list emptyness use \p empty() method.
513 return m_ItemCounter.value();
518 // split-list support
519 bool insert_aux_node( node_type * pNode )
521 return insert_aux_node( m_pHead, pNode );
524 // split-list support
525 bool insert_aux_node( atomic_node_ptr& refHead, node_type * pNode )
527 assert( pNode != nullptr );
529 // Hack: convert node_type to value_type.
530 // In principle, auxiliary node can be non-reducible to value_type
531 // We assume that comparator can correctly distinguish aux and regular node.
532 return insert_at( refHead, *node_traits::to_value_ptr( pNode ) );
535 bool insert_at( atomic_node_ptr& refHead, value_type& val )
540 if ( search( refHead, val, key_comparator(), pos ) )
543 if ( link_node( node_traits::to_node_ptr( val ), pos ) ) {
550 iterator insert_at_( atomic_node_ptr& refHead, value_type& val )
552 if ( insert_at( refHead, val ))
553 return iterator( node_traits::to_node_ptr( val ));
557 template <typename Func>
558 std::pair<iterator, bool> update_at_( atomic_node_ptr& refHead, value_type& val, Func func, bool bAllowInsert )
563 if ( search( refHead, val, key_comparator(), pos ) ) {
564 assert( key_comparator()( val, *node_traits::to_value_ptr( *pos.pCur ) ) == 0 );
566 func( false, *node_traits::to_value_ptr( *pos.pCur ) , val );
567 return std::make_pair( iterator( pos.pCur ), false );
571 return std::make_pair( end(), false );
573 if ( link_node( node_traits::to_node_ptr( val ), pos ) ) {
575 func( true, val , val );
576 return std::make_pair( iterator( node_traits::to_node_ptr( val )), true );
582 template <typename Func>
583 std::pair<bool, bool> update_at( atomic_node_ptr& refHead, value_type& val, Func func, bool bAllowInsert )
585 std::pair<iterator, bool> ret = update_at_( refHead, val, func, bAllowInsert );
586 return std::make_pair( ret.first != end(), ret.second );
589 template <typename Q, typename Compare, typename Func>
590 bool find_at( atomic_node_ptr& refHead, Q& val, Compare cmp, Func f )
594 if ( search( refHead, val, cmp, pos ) ) {
595 assert( pos.pCur != nullptr );
596 f( *node_traits::to_value_ptr( *pos.pCur ), val );
602 template <typename Q, typename Compare>
603 value_type * find_at( atomic_node_ptr& refHead, Q const& val, Compare cmp )
605 iterator it = find_at_( refHead, val, cmp );
611 template <typename Q, typename Compare>
612 iterator find_at_( atomic_node_ptr& refHead, Q const& val, Compare cmp )
616 if ( search( refHead, val, cmp, pos ) ) {
617 assert( pos.pCur != nullptr );
618 return iterator( pos.pCur );
628 template <typename Q, typename Compare >
629 bool search( atomic_node_ptr& refHead, const Q& val, Compare cmp, position& pos )
631 atomic_node_ptr * pPrev;
639 pCur = pPrev->load(memory_model::memory_order_acquire);
650 pNext = pCur->m_pNext.load(memory_model::memory_order_relaxed);
651 if ( cds_unlikely( pCur->m_pNext.load(memory_model::memory_order_acquire) != pNext )) {
656 if ( cds_unlikely( pPrev->load(memory_model::memory_order_acquire) != pCur )) {
661 assert( pCur != nullptr );
662 int nCmp = cmp( *node_traits::to_value_ptr( *pCur ), val );
669 pPrev = &( pCur->m_pNext );
675 template <typename Predicate>
676 void erase_for( Predicate pred )
678 node_type * pPred = nullptr;
679 node_type * pHead = m_pHead.load( memory_model::memory_order_relaxed );
681 node_type * p = pHead->m_pNext.load( memory_model::memory_order_relaxed );
682 if ( pred( *node_traits::to_value_ptr( pHead ))) {
683 assert( pPred != nullptr );
684 pPred->m_pNext.store( p, memory_model::memory_order_relaxed );
685 dispose_node( pHead, disposer());
695 }} // namespace cds::intrusive
697 #endif // #ifndef CDSLIB_INTRUSIVE_MICHAEL_LIST_NOGC_H