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 ) );
295 /// Ensures that the item \p val exists in the list
297 The operation inserts new item if the key \p val is not found in the list.
298 Otherwise, the function returns an iterator that points to item found.
300 Returns <tt> std::pair<iterator, bool> </tt> where \p first is an iterator pointing to
301 item found or inserted, \p second is true if new item has been added or \p false if the item
302 already is in the list.
304 template <typename Q>
305 std::pair<iterator, bool> ensure( const Q& val )
307 std::pair< node_type *, bool > ret = ensure_at( head(), val );
308 return std::make_pair( node_to_iterator( ret.first ), ret.second );
311 /// Inserts data of type \ref value_type constructed with <tt>std::forward<Args>(args)...</tt>
313 Return an iterator pointing to inserted item if success \ref end() otherwise
315 template <typename... Args>
316 iterator emplace( Args&&... args )
318 return node_to_iterator( emplace_at( head(), std::forward<Args>(args)... ));
321 /// Find the key \p key
322 /** \anchor cds_nonintrusive_MichaelList_nogc_find_val
323 The function searches the item with key equal to \p key
324 and returns an iterator pointed to item found if the key is found,
325 and \p end() otherwise
327 template <typename Q>
328 iterator find( Q const& key )
330 return node_to_iterator( find_at( head(), key, intrusive_key_comparator() ));
333 /// Finds the key \p key using \p pred predicate for searching
335 The function is an analog of \ref cds_nonintrusive_MichaelList_nogc_find_val "find(Q const&)"
336 but \p pred is used for key comparing.
337 \p Less functor has the interface like \p std::less.
338 \p pred must imply the same element order as the comparator used for building the list.
340 template <typename Q, typename Less>
341 iterator find_with( Q const& key, Less pred )
344 return node_to_iterator( find_at( head(), key, typename maker::template less_wrapper<Less>::type() ) );
347 /// Check if the list is empty
350 return base_class::empty();
353 /// Returns list's item count
355 The value returned depends on item counter provided by \p Traits. For \p atomicity::empty_item_counter,
356 this function always returns 0.
358 @note Even if you use real item counter and it returns 0, this fact does not mean that the list
359 is empty. To check list emptyness use \p empty() method.
363 return base_class::size();
374 node_type * insert_node_at( head_type& refHead, node_type * pNode )
376 assert( pNode != nullptr );
377 scoped_node_ptr p(pNode);
378 if ( base_class::insert_at( refHead, *pNode ))
384 template <typename Q>
385 node_type * insert_at( head_type& refHead, const Q& val )
387 return insert_node_at( refHead, alloc_node( val ));
390 template <typename Q>
391 std::pair< node_type *, bool > ensure_at( head_type& refHead, const Q& val )
393 scoped_node_ptr pNode( alloc_node( val ));
394 node_type * pItemFound = nullptr;
396 std::pair<bool, bool> ret = base_class::ensure_at( refHead, *pNode, [&pItemFound](bool, node_type& item, node_type&) { pItemFound = &item; });
397 assert( pItemFound != nullptr );
399 if ( ret.first && ret.second )
401 return std::make_pair( pItemFound, ret.second );
404 template <typename... Args>
405 node_type * emplace_at( head_type& refHead, Args&&... args )
407 return insert_node_at( refHead, alloc_node( std::forward<Args>(args)...));
410 template <typename Q, typename Compare>
411 node_type * find_at( head_type& refHead, Q const& key, Compare cmp )
413 return base_class::find_at( refHead, key, cmp );
418 }} // namespace cds::container
420 #endif // #ifndef CDSLIB_CONTAINER_MICHAEL_LIST_NOGC_H