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,
299 the function inserts a new item.
300 Otherwise, the function returns an iterator pointing to the item found.
302 Returns <tt> std::pair<iterator, bool> </tt> where \p first is an iterator pointing to
303 item found or inserted, \p second is true if new item has been added or \p false if the item
304 already is in the list.
306 template <typename Q>
307 std::pair<iterator, bool> update( const Q& key, bool bAllowInsert = true )
309 std::pair< node_type *, bool > ret = update_at( head(), key, bAllowInsert );
310 return std::make_pair( node_to_iterator( ret.first ), ret.second );
313 template <typename Q>
314 CDS_DEPRECATED("ensure() is deprecated, use update()")
315 std::pair<iterator, bool> ensure( const Q& val )
317 return update( val, true );
321 /// Inserts data of type \ref value_type constructed with <tt>std::forward<Args>(args)...</tt>
323 Return an iterator pointing to inserted item if success \ref end() otherwise
325 template <typename... Args>
326 iterator emplace( Args&&... args )
328 return node_to_iterator( emplace_at( head(), std::forward<Args>(args)... ));
331 /// Checks whether the list contains \p key
333 The function searches the item with key equal to \p key
334 and returns an iterator pointed to item found if the key is found,
335 and \ref end() otherwise
337 template <typename Q>
338 iterator contains( Q const& key )
340 return node_to_iterator( find_at( head(), key, intrusive_key_comparator() ));
343 template <typename Q>
344 CDS_DEPRECATED("deprecated, use contains()")
345 iterator find( Q const& key )
347 return contains( key );
351 /// Checks whether the map contains \p key using \p pred predicate for searching
353 The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
354 \p Less functor has the interface like \p std::less.
355 \p Less must imply the same element order as the comparator used for building the list.
357 template <typename Q, typename Less>
358 iterator contains( Q const& key, Less pred )
361 return node_to_iterator( find_at( head(), key, typename maker::template less_wrapper<Less>::type() ) );
364 template <typename Q, typename Less>
365 CDS_DEPRECATED("deprecated, use contains()")
366 iterator find_with( Q const& key, Less pred )
368 return contains( key, pred );
372 /// Check if the list is empty
375 return base_class::empty();
378 /// Returns list's item count
380 The value returned depends on item counter provided by \p Traits. For \p atomicity::empty_item_counter,
381 this function always returns 0.
383 @note Even if you use real item counter and it returns 0, this fact does not mean that the list
384 is empty. To check list emptyness use \p empty() method.
388 return base_class::size();
399 node_type * insert_node_at( head_type& refHead, node_type * pNode )
401 assert( pNode != nullptr );
402 scoped_node_ptr p(pNode);
403 if ( base_class::insert_at( refHead, *pNode ))
409 template <typename Q>
410 node_type * insert_at( head_type& refHead, const Q& val )
412 return insert_node_at( refHead, alloc_node( val ));
415 template <typename Q>
416 std::pair< node_type *, bool > update_at( head_type& refHead, const Q& val, bool bAllowInsert )
418 scoped_node_ptr pNode( alloc_node( val ));
419 node_type * pItemFound = nullptr;
421 std::pair<bool, bool> ret = base_class::update_at( refHead, *pNode,
422 [&pItemFound](bool, node_type& item, node_type&) { pItemFound = &item; },
427 return std::make_pair( pItemFound, ret.second );
430 template <typename... Args>
431 node_type * emplace_at( head_type& refHead, Args&&... args )
433 return insert_node_at( refHead, alloc_node( std::forward<Args>(args)...));
436 template <typename Q, typename Compare>
437 node_type * find_at( head_type& refHead, Q const& key, Compare cmp )
439 return base_class::find_at( refHead, key, cmp );
444 }} // namespace cds::container
446 #endif // #ifndef CDSLIB_CONTAINER_MICHAEL_LIST_NOGC_H