3 #ifndef CDSLIB_CONTAINER_MICHAEL_LIST_NOGC_H
4 #define CDSLIB_CONTAINER_MICHAEL_LIST_NOGC_H
7 #include <cds/container/details/michael_list_base.h>
8 #include <cds/intrusive/michael_list_nogc.h>
9 #include <cds/container/details/make_michael_list.h>
11 namespace cds { namespace container {
16 template <typename T, class Traits>
17 struct make_michael_list_nogc: public make_michael_list<gc::nogc, T, Traits>
19 typedef make_michael_list<cds::gc::nogc, T, Traits> base_maker;
20 typedef typename base_maker::node_type node_type;
22 struct intrusive_traits: public base_maker::intrusive_traits
24 typedef typename base_maker::node_deallocator disposer;
27 typedef intrusive::MichaelList<cds::gc::nogc, node_type, intrusive_traits> type;
30 } // namespace details
33 /// Michael's lock-free ordered single-linked list (template specialization for \p gc::nogc)
34 /** @ingroup cds_nonintrusive_list
35 \anchor cds_nonintrusive_MichaelList_nogc
37 This specialization is intended for so-called append-only usage when no item
38 reclamation may be performed. The class does not support deleting of list item.
39 Usually, ordered single-linked list is used as a building block for the hash table implementation.
40 The complexity of searching is <tt>O(N)</tt>.
42 See \ref cds_nonintrusive_MichaelList_gc "MichaelList" for description of template parameters.
45 #ifdef CDS_DOXYGEN_INVOKED
46 class Traits = michael_list::traits
51 class MichaelList<gc::nogc, T, Traits>:
52 #ifdef CDS_DOXYGEN_INVOKED
53 protected intrusive::MichaelList< gc::nogc, T, Traits >
55 protected details::make_michael_list_nogc< T, Traits >::type
59 typedef details::make_michael_list_nogc< T, Traits > maker;
60 typedef typename maker::type base_class;
64 typedef cds::gc::nogc gc; ///< Garbage collector used
65 typedef T value_type; ///< Type of value stored in the list
66 typedef Traits traits; ///< List traits
68 typedef typename base_class::back_off back_off; ///< Back-off strategy used
69 typedef typename maker::allocator_type allocator_type; ///< Allocator type used for allocate/deallocate the nodes
70 typedef typename base_class::item_counter item_counter; ///< Item counting policy used
71 typedef typename maker::key_comparator key_comparator; ///< key comparison functor
72 typedef typename base_class::memory_model memory_model; ///< Memory ordering. See cds::opt::memory_model option
76 typedef typename base_class::value_type node_type;
77 typedef typename maker::cxx_allocator cxx_allocator;
78 typedef typename maker::node_deallocator node_deallocator;
79 typedef typename maker::intrusive_traits::compare intrusive_key_comparator;
81 typedef typename base_class::atomic_node_ptr head_type;
86 static node_type * alloc_node()
88 return cxx_allocator().New();
91 static node_type * alloc_node( value_type const& v )
93 return cxx_allocator().New( v );
96 template <typename... Args>
97 static node_type * alloc_node( Args&&... args )
99 return cxx_allocator().MoveNew( std::forward<Args>(args)... );
102 static void free_node( node_type * pNode )
104 cxx_allocator().Delete( pNode );
107 struct node_disposer {
108 void operator()( node_type * pNode )
113 typedef std::unique_ptr< node_type, node_disposer > scoped_node_ptr;
117 return base_class::m_pHead;
120 head_type const& head() const
122 return base_class::m_pHead;
128 template <bool IsConst>
129 class iterator_type: protected base_class::template iterator_type<IsConst>
131 typedef typename base_class::template iterator_type<IsConst> iterator_base;
133 iterator_type( head_type const& pNode )
134 : iterator_base( pNode )
137 explicit iterator_type( const iterator_base& it )
138 : iterator_base( it )
141 friend class MichaelList;
144 explicit iterator_type( node_type& pNode )
145 : iterator_base( &pNode )
149 typedef typename cds::details::make_const_type<value_type, IsConst>::pointer value_ptr;
150 typedef typename cds::details::make_const_type<value_type, IsConst>::reference value_ref;
155 iterator_type( const iterator_type& src )
156 : iterator_base( src )
159 value_ptr operator ->() const
161 typename iterator_base::value_ptr p = iterator_base::operator ->();
162 return p ? &(p->m_Value) : nullptr;
165 value_ref operator *() const
167 return (iterator_base::operator *()).m_Value;
171 iterator_type& operator ++()
173 iterator_base::operator ++();
178 iterator_type operator ++(int)
180 return iterator_base::operator ++(0);
184 bool operator ==(iterator_type<C> const& i ) const
186 return iterator_base::operator ==(i);
189 bool operator !=(iterator_type<C> const& i ) const
191 return iterator_base::operator !=(i);
197 /// Returns a forward iterator addressing the first element in a list
199 For empty list \code begin() == end() \endcode
201 typedef iterator_type<false> iterator;
203 /// Const forward iterator
205 For iterator's features and requirements see \ref iterator
207 typedef iterator_type<true> const_iterator;
209 /// Returns a forward iterator addressing the first element in a list
211 For empty list \code begin() == end() \endcode
215 return iterator( head() );
218 /// Returns an iterator that addresses the location succeeding the last element in a list
220 Do not use the value returned by <tt>end</tt> function to access any item.
221 Internally, <tt>end</tt> returning value equals to \p nullptr.
223 The returned value can be used only to control reaching the end of the list.
224 For empty list \code begin() == end() \endcode
231 /// Returns a forward const iterator addressing the first element in a list
233 const_iterator begin() const
235 return const_iterator( head() );
237 const_iterator cbegin() const
239 return const_iterator( head() );
243 /// Returns an const iterator that addresses the location succeeding the last element in a list
245 const_iterator end() const
247 return const_iterator();
249 const_iterator cend() const
251 return const_iterator();
257 iterator node_to_iterator( node_type * pNode )
260 return iterator( *pNode );
266 /// Default constructor
268 Initialize empty list
284 The function inserts \p val in the list if the list does not contain
285 an item with key equal to \p val.
287 Return an iterator pointing to inserted item if success \ref end() otherwise
289 template <typename Q>
290 iterator insert( const Q& val )
292 return node_to_iterator( insert_at( head(), val ) );
297 If \p key is not in the list and \p bAllowInsert is \p true,
298 the function inserts a new item.
299 Otherwise, the function returns an iterator pointing to the item found.
301 Returns <tt> std::pair<iterator, bool> </tt> where \p first is an iterator pointing to
302 item found or inserted, \p second is true if new item has been added or \p false if the item
303 already is in the list.
305 template <typename Q>
306 std::pair<iterator, bool> update( const Q& key, bool bAllowInsert = true )
308 std::pair< node_type *, bool > ret = update_at( head(), key, bAllowInsert );
309 return std::make_pair( node_to_iterator( ret.first ), ret.second );
312 template <typename Q>
313 CDS_DEPRECATED("ensure() is deprecated, use update()")
314 std::pair<iterator, bool> ensure( const Q& val )
316 return update( val, true );
320 /// Inserts data of type \ref value_type constructed with <tt>std::forward<Args>(args)...</tt>
322 Return an iterator pointing to inserted item if success \ref end() otherwise
324 template <typename... Args>
325 iterator emplace( Args&&... args )
327 return node_to_iterator( emplace_at( head(), std::forward<Args>(args)... ));
330 /// Checks whether the list contains \p key
332 The function searches the item with key equal to \p key
333 and returns an iterator pointed to item found if the key is found,
334 and \ref end() otherwise
336 template <typename Q>
337 iterator contains( Q const& key )
339 return node_to_iterator( find_at( head(), key, intrusive_key_comparator() ));
342 template <typename Q>
343 CDS_DEPRECATED("deprecated, use contains()")
344 iterator find( Q const& key )
346 return contains( key );
350 /// Checks whether the map contains \p key using \p pred predicate for searching
352 The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
353 \p Less functor has the interface like \p std::less.
354 \p Less must imply the same element order as the comparator used for building the list.
356 template <typename Q, typename Less>
357 iterator contains( Q const& key, Less pred )
360 return node_to_iterator( find_at( head(), key, typename maker::template less_wrapper<Less>::type() ) );
363 template <typename Q, typename Less>
364 CDS_DEPRECATED("deprecated, use contains()")
365 iterator find_with( Q const& key, Less pred )
367 return contains( key, pred );
371 /// Check if the list is empty
374 return base_class::empty();
377 /// Returns list's item count
379 The value returned depends on item counter provided by \p Traits. For \p atomicity::empty_item_counter,
380 this function always returns 0.
382 @note Even if you use real item counter and it returns 0, this fact does not mean that the list
383 is empty. To check list emptyness use \p empty() method.
387 return base_class::size();
398 node_type * insert_node_at( head_type& refHead, node_type * pNode )
400 assert( pNode != nullptr );
401 scoped_node_ptr p(pNode);
402 if ( base_class::insert_at( refHead, *pNode ))
408 template <typename Q>
409 node_type * insert_at( head_type& refHead, const Q& val )
411 return insert_node_at( refHead, alloc_node( val ));
414 template <typename Q>
415 std::pair< node_type *, bool > update_at( head_type& refHead, const Q& val, bool bAllowInsert )
417 scoped_node_ptr pNode( alloc_node( val ));
418 node_type * pItemFound = nullptr;
420 std::pair<bool, bool> ret = base_class::update_at( refHead, *pNode,
421 [&pItemFound](bool, node_type& item, node_type&) { pItemFound = &item; },
426 return std::make_pair( pItemFound, ret.second );
429 template <typename... Args>
430 node_type * emplace_at( head_type& refHead, Args&&... args )
432 return insert_node_at( refHead, alloc_node( std::forward<Args>(args)...));
435 template <typename Q, typename Compare>
436 node_type * find_at( head_type& refHead, Q const& key, Compare cmp )
438 return base_class::find_at( refHead, key, cmp );
443 }} // namespace cds::container
445 #endif // #ifndef CDSLIB_CONTAINER_MICHAEL_LIST_NOGC_H