3 #ifndef __CDS_CONTAINER_MICHAEL_LIST_NOGC_H
4 #define __CDS_CONTAINER_MICHAEL_LIST_NOGC_H
6 #include <cds/container/michael_list_base.h>
7 #include <cds/intrusive/michael_list_nogc.h>
8 #include <cds/container/details/make_michael_list.h>
9 #include <cds/details/std/memory.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 type_traits: public base_maker::type_traits
24 typedef typename base_maker::node_deallocator disposer;
27 typedef intrusive::MichaelList<cds::gc::nogc, node_type, type_traits> type;
30 } // namespace details
33 /// Michael's lock-free ordered single-linked list (template specialization for gc::nogc)
34 /** @ingroup cds_nonintrusive_list
35 \anchor cds_nonintrusive_MichaelList_nogc
37 This specialization is intended for so-called persistent 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.
44 The interface of the specialization is a little different.
46 template <typename T, typename Traits>
47 class MichaelList<gc::nogc, T, Traits>:
48 #ifdef CDS_DOXYGEN_INVOKED
49 protected intrusive::MichaelList< gc::nogc, T, Traits >
51 protected details::make_michael_list_nogc< T, Traits >::type
55 typedef details::make_michael_list_nogc< T, Traits > options;
56 typedef typename options::type base_class;
60 typedef T value_type ; ///< Type of value stored in the list
61 typedef typename base_class::gc gc ; ///< Garbage collector used
62 typedef typename base_class::back_off back_off ; ///< Back-off strategy used
63 typedef typename options::allocator_type allocator_type ; ///< Allocator type used for allocate/deallocate the nodes
64 typedef typename base_class::item_counter item_counter ; ///< Item counting policy used
65 typedef typename options::key_comparator key_comparator ; ///< key comparison functor
66 typedef typename base_class::memory_model memory_model ; ///< Memory ordering. See cds::opt::memory_model option
70 typedef typename base_class::value_type node_type;
71 typedef typename options::cxx_allocator cxx_allocator;
72 typedef typename options::node_deallocator node_deallocator;
73 typedef typename options::type_traits::compare intrusive_key_comparator;
75 typedef typename base_class::atomic_node_ptr head_type;
80 # ifndef CDS_CXX11_LAMBDA_SUPPORT
83 node_type * m_pItemFound;
86 : m_pItemFound( NULL )
89 void operator ()(bool, node_type& item, node_type& )
99 static node_type * alloc_node()
101 return cxx_allocator().New();
104 static node_type * alloc_node( value_type const& v )
106 return cxx_allocator().New( v );
109 # ifdef CDS_EMPLACE_SUPPORT
110 template <typename... Args>
111 static node_type * alloc_node( Args&&... args )
113 return cxx_allocator().MoveNew( std::forward<Args>(args)... );
117 static void free_node( node_type * pNode )
119 cxx_allocator().Delete( pNode );
122 struct node_disposer {
123 void operator()( node_type * pNode )
128 typedef std::unique_ptr< node_type, node_disposer > scoped_node_ptr;
132 return base_class::m_pHead;
135 head_type const& head() const
137 return base_class::m_pHead;
143 template <bool IsConst>
144 class iterator_type: protected base_class::template iterator_type<IsConst>
146 typedef typename base_class::template iterator_type<IsConst> iterator_base;
148 iterator_type( head_type const& pNode )
149 : iterator_base( pNode )
152 explicit iterator_type( const iterator_base& it )
153 : iterator_base( it )
156 friend class MichaelList;
159 explicit iterator_type( node_type& pNode )
160 : iterator_base( &pNode )
164 typedef typename cds::details::make_const_type<value_type, IsConst>::pointer value_ptr;
165 typedef typename cds::details::make_const_type<value_type, IsConst>::reference value_ref;
170 iterator_type( const iterator_type& src )
171 : iterator_base( src )
174 value_ptr operator ->() const
176 typename iterator_base::value_ptr p = iterator_base::operator ->();
177 return p ? &(p->m_Value) : reinterpret_cast<value_ptr>(NULL);
180 value_ref operator *() const
182 return (iterator_base::operator *()).m_Value;
186 iterator_type& operator ++()
188 iterator_base::operator ++();
193 iterator_type operator ++(int)
195 return iterator_base::operator ++(0);
199 bool operator ==(iterator_type<C> const& i ) const
201 return iterator_base::operator ==(i);
204 bool operator !=(iterator_type<C> const& i ) const
206 return iterator_base::operator !=(i);
212 /// Returns a forward iterator addressing the first element in a list
214 For empty list \code begin() == end() \endcode
216 typedef iterator_type<false> iterator;
218 /// Const forward iterator
220 For iterator's features and requirements see \ref iterator
222 typedef iterator_type<true> const_iterator;
224 /// Returns a forward iterator addressing the first element in a list
226 For empty list \code begin() == end() \endcode
230 return iterator( head() );
233 /// Returns an iterator that addresses the location succeeding the last element in a list
235 Do not use the value returned by <tt>end</tt> function to access any item.
236 Internally, <tt>end</tt> returning value equals to <tt>NULL</tt>.
238 The returned value can be used only to control reaching the end of the list.
239 For empty list \code begin() == end() \endcode
246 /// Returns a forward const iterator addressing the first element in a list
248 const_iterator begin() const
250 return const_iterator( head() );
252 const_iterator cbegin()
254 return const_iterator( head() );
258 /// Returns an const iterator that addresses the location succeeding the last element in a list
260 const_iterator end() const
262 return const_iterator();
264 const_iterator cend()
266 return const_iterator();
272 iterator node_to_iterator( node_type * pNode )
275 return iterator( *pNode );
281 /// Default constructor
283 Initialize empty list
299 The function inserts \p val in the list if the list does not contain
300 an item with key equal to \p val.
302 Return an iterator pointing to inserted item if success \ref end() otherwise
304 template <typename Q>
305 iterator insert( const Q& val )
307 return node_to_iterator( insert_at( head(), val ) );
310 /// Ensures that the item \p val exists in the list
312 The operation inserts new item if the key \p val is not found in the list.
313 Otherwise, the function returns an iterator that points to item found.
315 Returns <tt> std::pair<iterator, bool> </tt> where \p first is an iterator pointing to
316 item found or inserted, \p second is true if new item has been added or \p false if the item
317 already is in the list.
319 template <typename Q>
320 std::pair<iterator, bool> ensure( const Q& val )
322 std::pair< node_type *, bool > ret = ensure_at( head(), val );
323 return std::make_pair( node_to_iterator( ret.first ), ret.second );
326 # ifdef CDS_EMPLACE_SUPPORT
327 /// Inserts data of type \ref value_type constructed with <tt>std::forward<Args>(args)...</tt>
329 Return an iterator pointing to inserted item if success \ref end() otherwise
331 This function is available only for compiler that supports
332 variadic template and move semantics
334 template <typename... Args>
335 iterator emplace( Args&&... args )
337 return node_to_iterator( emplace_at( head(), std::forward<Args>(args)... ));
341 /// Find the key \p val
342 /** \anchor cds_nonintrusive_MichaelList_nogc_find_val
343 The function searches the item with key equal to \p val
344 and returns an iterator pointed to item found if the key is found,
345 and \ref end() otherwise
347 template <typename Q>
348 iterator find( Q const& key )
350 return node_to_iterator( find_at( head(), key, intrusive_key_comparator() ));
353 /// Finds the key \p val using \p pred predicate for searching
355 The function is an analog of \ref cds_nonintrusive_MichaelList_nogc_find_val "find(Q const&)"
356 but \p pred is used for key comparing.
357 \p Less functor has the interface like \p std::less.
358 \p pred must imply the same element order as the comparator used for building the list.
360 template <typename Q, typename Less>
361 iterator find_with( Q const& key, Less pred )
363 return node_to_iterator( find_at( head(), key, typename options::template less_wrapper<Less>::type() ));
366 /// Check if the list is empty
369 return base_class::empty();
372 /// Returns list's item count
374 The value returned depends on opt::item_counter option. For atomics::empty_item_counter,
375 this function always returns 0.
377 <b>Warning</b>: even if you use real item counter and it returns 0, this fact is not mean that the list
378 is empty. To check list emptyness use \ref empty() method.
382 return base_class::size();
387 Post-condition: the list is empty
396 node_type * insert_node_at( head_type& refHead, node_type * pNode )
398 assert( pNode != nullptr );
399 scoped_node_ptr p(pNode);
400 if ( base_class::insert_at( refHead, *pNode ))
406 template <typename Q>
407 node_type * insert_at( head_type& refHead, const Q& val )
409 return insert_node_at( refHead, alloc_node( val ));
412 template <typename Q>
413 std::pair< node_type *, bool > ensure_at( head_type& refHead, const Q& val )
415 scoped_node_ptr pNode( alloc_node( val ));
416 node_type * pItemFound = nullptr;
418 # ifdef CDS_CXX11_LAMBDA_SUPPORT
419 std::pair<bool, bool> ret = base_class::ensure_at( refHead, *pNode, [&pItemFound](bool, node_type& item, node_type&) { pItemFound = &item; });
422 std::pair<bool, bool> ret = base_class::ensure_at( refHead, *pNode, boost::ref(func) );
423 pItemFound = func.m_pItemFound;
425 assert( pItemFound != nullptr );
427 if ( ret.first && ret.second )
429 return std::make_pair( pItemFound, ret.second );
432 # ifdef CDS_EMPLACE_SUPPORT
433 template <typename... Args>
434 node_type * emplace_at( head_type& refHead, Args&&... args )
436 return insert_node_at( refHead, alloc_node( std::forward<Args>(args)...));
440 template <typename Q, typename Compare>
441 node_type * find_at( head_type& refHead, Q const& key, Compare cmp )
443 return base_class::find_at( refHead, key, cmp );
448 }} // namespace cds::container
450 #endif // #ifndef __CDS_CONTAINER_MICHAEL_LIST_NOGC_H