Extending intrusive MichaelSet<HP> to IterableList
[libcds.git] / cds / intrusive / impl / lazy_list.h
1 /*
2     This file is a part of libcds - Concurrent Data Structures library
3
4     (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
5
6     Source code repo: http://github.com/khizmax/libcds/
7     Download: http://sourceforge.net/projects/libcds/files/
8     
9     Redistribution and use in source and binary forms, with or without
10     modification, are permitted provided that the following conditions are met:
11
12     * Redistributions of source code must retain the above copyright notice, this
13       list of conditions and the following disclaimer.
14
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.
18
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.
29 */
30
31 #ifndef CDSLIB_INTRUSIVE_IMPL_LAZY_LIST_H
32 #define CDSLIB_INTRUSIVE_IMPL_LAZY_LIST_H
33
34 #include <mutex>        // unique_lock
35 #include <cds/intrusive/details/lazy_list_base.h>
36
37 namespace cds { namespace intrusive {
38
39     /// Lazy ordered single-linked list
40     /** @ingroup cds_intrusive_list
41         \anchor cds_intrusive_LazyList_hp
42
43         Usually, ordered single-linked list is used as a building block for the hash table implementation.
44         The complexity of searching is <tt>O(N)</tt>.
45
46         Source:
47             - [2005] Steve Heller, Maurice Herlihy, Victor Luchangco, Mark Moir, William N. Scherer III, and Nir Shavit
48               "A Lazy Concurrent List-Based Set Algorithm"
49
50         The lazy list is based on an optimistic locking scheme for inserts and removes,
51         eliminating the need to use the equivalent of an atomically markable
52         reference. It also has a novel wait-free membership \p find operation
53         that does not need to perform cleanup operations and is more efficient.
54
55         Template arguments:
56         - \p GC - Garbage collector used. Note the \p GC must be the same as the GC used for item type \p T (see lazy_list::node).
57         - \p T - type to be stored in the list. The type must be based on lazy_list::node (for lazy_list::base_hook)
58             or it must have a member of type lazy_list::node (for lazy_list::member_hook).
59         - \p Traits - type traits. See lazy_list::traits for explanation.
60             It is possible to declare option-based list with cds::intrusive::lazy_list::make_traits metafunction instead of \p Traits template
61             argument. For example, the following traits-based declaration of \p gc::HP lazy list
62             \code
63             #include <cds/intrusive/lazy_list_hp.h>
64             // Declare item stored in your list
65             struct item: public cds::intrusive::lazy_list::node< cds::gc::HP >
66             { ... };
67
68             // Declare comparator for the item
69             struct my_compare { ... }
70
71             // Declare traits
72             struct my_traits: public cds::intrusive::lazy_list::traits
73             {
74                 typedef cds::intrusive::lazy_list::base_hook< cds::opt::gc< cds::gc::HP > >   hook;
75                 typedef my_compare compare;
76             };
77
78             // Declare traits-based list
79             typedef cds::intrusive::LazyList< cds::gc::HP, item, my_traits >     traits_based_list;
80             \endcode
81             is equivalent for the following option-based list
82             \code
83             #include <cds/intrusive/lazy_list_hp.h>
84
85             // item struct and my_compare are the same
86
87             // Declare option-based list
88             typedef cds::intrusive::LazyList< cds::gc::HP, item,
89                 typename cds::intrusive::lazy_list::make_traits<
90                     cds::intrusive::opt::hook< cds::intrusive::lazy_list::base_hook< cds::opt::gc< cds::gc::HP > > >    // hook option
91                     ,cds::intrusive::opt::compare< my_compare >     // item comparator option
92                 >::type
93             >     option_based_list;
94             \endcode
95
96         \par Usage
97         There are different specializations of this template for each garbage collecting schema used.
98         You should select GC needed and include appropriate .h-file:
99         - for gc::HP: \code #include <cds/intrusive/lazy_list_hp.h> \endcode
100         - for gc::DHP: \code #include <cds/intrusive/lazy_list_dhp.h> \endcode
101         - for gc::nogc: \code #include <cds/intrusive/lazy_list_nogc.h> \endcode
102         - for \ref cds_urcu_type "RCU" - see \ref cds_intrusive_LazyList_rcu "LazyList RCU specialization"
103
104         Then, you should incorporate lazy_list::node into your struct \p T and provide
105         appropriate \p lazy_list::traits::hook in your \p Traits template parameters. Usually, for \p Traits
106         a struct based on \p lazy_list::traits should be defined.
107
108         Example for gc::DHP and base hook:
109         \code
110         // Include GC-related lazy list specialization
111         #include <cds/intrusive/lazy_list_dhp.h>
112
113         // Data stored in lazy list
114         struct my_data: public cds::intrusive::lazy_list::node< cds::gc::DHP >
115         {
116             // key field
117             std::string     strKey;
118
119             // other data
120             // ...
121         };
122
123         // my_data comparing functor
124         struct compare {
125             int operator()( const my_data& d1, const my_data& d2 )
126             {
127                 return d1.strKey.compare( d2.strKey );
128             }
129
130             int operator()( const my_data& d, const std::string& s )
131             {
132                 return d.strKey.compare(s);
133             }
134
135             int operator()( const std::string& s, const my_data& d )
136             {
137                 return s.compare( d.strKey );
138             }
139         };
140
141         // Declare traits
142         struct my_traits: public cds::intrusive::lazy_list::traits
143         {
144             typedef cds::intrusive::lazy_list::base_hook< cds::opt::gc< cds::gc::DHP > >   hook;
145             typedef my_data_cmp compare;
146         };
147
148         // Declare list type
149         typedef cds::intrusive::LazyList< cds::gc::DHP, my_data, my_traits >     traits_based_list;
150         \endcode
151
152         Equivalent option-based code:
153         \code
154         // GC-related specialization
155         #include <cds/intrusive/lazy_list_dhp.h>
156
157         struct my_data {
158             // see above
159         };
160         struct compare {
161             // see above
162         };
163
164         // Declare option-based list
165         typedef cds::intrusive::LazyList< cds::gc::DHP
166             ,my_data
167             , typename cds::intrusive::lazy_list::make_traits<
168                 cds::intrusive::opt::hook< cds::intrusive::lazy_list::base_hook< cds::opt::gc< cds::gc::DHP > > >
169                 ,cds::intrusive::opt::compare< my_data_cmp >
170             >::type
171         > option_based_list;
172
173         \endcode
174     */
175     template <
176         class GC
177         ,typename T
178 #ifdef CDS_DOXYGEN_INVOKED
179         ,class Traits = lazy_list::traits
180 #else
181         ,class Traits
182 #endif
183     >
184     class LazyList
185     {
186     public:
187         typedef GC     gc;   ///< Garbage collector
188         typedef T      value_type; ///< type of value stored in the list
189         typedef Traits traits;     ///< Traits template parameter
190
191         typedef typename traits::hook    hook;      ///< hook type
192         typedef typename hook::node_type node_type; ///< node type
193
194 #   ifdef CDS_DOXYGEN_INVOKED
195         typedef implementation_defined key_comparator;    ///< key comparison functor based on opt::compare and opt::less option setter.
196 #   else
197         typedef typename opt::details::make_comparator< value_type, traits >::type key_comparator;
198 #   endif
199
200         typedef typename traits::disposer  disposer;   ///< disposer
201         typedef typename get_node_traits< value_type, node_type, hook>::type node_traits; ///< node traits
202         typedef typename lazy_list::get_link_checker< node_type, traits::link_checker >::type link_checker; ///< link checker
203
204         typedef typename traits::back_off     back_off;      ///< back-off strategy
205         typedef typename traits::item_counter item_counter;  ///< Item counting policy used
206         typedef typename traits::memory_model memory_model;  ///< C++ memory ordering (see \p lazy_list::traits::memory_model)
207         typedef typename traits::stat         stat;          ///< Internal statistics
208
209         static_assert((std::is_same< gc, typename node_type::gc >::value), "GC and node_type::gc must be the same type");
210
211         typedef typename gc::template guarded_ptr< value_type > guarded_ptr; ///< Guarded pointer
212
213         static CDS_CONSTEXPR const size_t c_nHazardPtrCount = 4; ///< Count of hazard pointer required for the algorithm
214
215         //@cond
216         // Rebind traits (split-list support)
217         template <typename... Options>
218         struct rebind_traits {
219             typedef LazyList<
220                 gc
221                 , value_type
222                 , typename cds::opt::make_options< traits, Options...>::type
223             > type;
224         };
225
226         // Stat selector
227         template <typename Stat>
228         using select_stat_wrapper = lazy_list::select_stat_wrapper< Stat >;
229         //@endcond
230
231     protected:
232         typedef typename node_type::marked_ptr marked_node_ptr;   ///< Node marked pointer
233         typedef node_type *     auxiliary_head;   ///< Auxiliary head type (for split-list support)
234
235     protected:
236         //@cond
237         node_type   m_Head;
238         node_type   m_Tail;
239
240         item_counter    m_ItemCounter;
241         stat            m_Stat; ///< Internal statistics
242
243         struct clean_disposer {
244             void operator()( value_type * p )
245             {
246                 lazy_list::node_cleaner<gc, node_type, memory_model>()( node_traits::to_node_ptr( p ));
247                 disposer()( p );
248             }
249         };
250
251         /// Position pointer for item search
252         struct position {
253             node_type *     pPred; ///< Previous node
254             node_type *     pCur;  ///< Current node
255
256             typename gc::template GuardArray<2> guards; ///< Guards array
257
258             enum {
259                 guard_prev_item,
260                 guard_current_item
261             };
262
263             /// Locks nodes \p pPred and \p pCur
264             void lock()
265             {
266                 pPred->m_Lock.lock();
267                 pCur->m_Lock.lock();
268             }
269
270             /// Unlocks nodes \p pPred and \p pCur
271             void unlock()
272             {
273                 pCur->m_Lock.unlock();
274                 pPred->m_Lock.unlock();
275             }
276         };
277
278         typedef std::unique_lock< position > scoped_position_lock;
279         //@endcond
280
281     protected:
282         //@cond
283         void link_node( node_type * pNode, node_type * pPred, node_type * pCur )
284         {
285             assert( pPred->m_pNext.load(memory_model::memory_order_relaxed).ptr() == pCur );
286             link_checker::is_empty( pNode );
287
288             pNode->m_pNext.store( marked_node_ptr(pCur), memory_model::memory_order_release );
289             pPred->m_pNext.store( marked_node_ptr(pNode), memory_model::memory_order_release );
290         }
291
292         void unlink_node( node_type * pPred, node_type * pCur, node_type * pHead )
293         {
294             assert( pPred->m_pNext.load(memory_model::memory_order_relaxed).ptr() == pCur );
295
296             node_type * pNext = pCur->m_pNext.load(memory_model::memory_order_relaxed).ptr();
297             pCur->m_pNext.store( marked_node_ptr( pHead, 1 ), memory_model::memory_order_release ); // logical removal + back-link for search
298             pPred->m_pNext.store( marked_node_ptr( pNext ), memory_model::memory_order_release); // physically deleting
299         }
300
301         void retire_node( node_type * pNode )
302         {
303             assert( pNode != nullptr );
304             gc::template retire<clean_disposer>( node_traits::to_value_ptr( *pNode ));
305         }
306         //@endcond
307
308     protected:
309         //@cond
310         template <bool IsConst>
311         class iterator_type
312         {
313             friend class LazyList;
314
315         protected:
316             value_type * m_pNode;
317             typename gc::Guard  m_Guard;
318
319             void next()
320             {
321                 assert( m_pNode != nullptr );
322
323                 if ( m_pNode ) {
324                     typename gc::Guard g;
325                     node_type * pCur = node_traits::to_node_ptr( m_pNode );
326                     if ( pCur->m_pNext.load( memory_model::memory_order_relaxed ).ptr() != nullptr ) {      // if pCur is not tail node
327                         node_type * pNext;
328                         do {
329                             pNext = pCur->m_pNext.load(memory_model::memory_order_relaxed).ptr();
330                             g.assign( node_traits::to_value_ptr( pNext ));
331                         } while ( pNext != pCur->m_pNext.load(memory_model::memory_order_relaxed).ptr());
332
333                         m_pNode = m_Guard.assign( g.template get<value_type>());
334                     }
335                 }
336             }
337
338             void skip_deleted()
339             {
340                 if ( m_pNode != nullptr ) {
341                     typename gc::Guard g;
342                     node_type * pNode = node_traits::to_node_ptr( m_pNode );
343
344                     // Dummy tail node could not be marked
345                     while ( pNode->is_marked()) {
346                         node_type * p = pNode->m_pNext.load(memory_model::memory_order_relaxed).ptr();
347                         g.assign( node_traits::to_value_ptr( p ));
348                         if ( p == pNode->m_pNext.load(memory_model::memory_order_relaxed).ptr())
349                             pNode = p;
350                     }
351                     if ( pNode != node_traits::to_node_ptr( m_pNode ))
352                         m_pNode = m_Guard.assign( g.template get<value_type>());
353                 }
354             }
355
356             iterator_type( node_type * pNode )
357             {
358                 m_pNode = m_Guard.assign( node_traits::to_value_ptr( pNode ));
359                 skip_deleted();
360             }
361
362         public:
363             typedef typename cds::details::make_const_type<value_type, IsConst>::pointer   value_ptr;
364             typedef typename cds::details::make_const_type<value_type, IsConst>::reference value_ref;
365
366             iterator_type()
367                 : m_pNode( nullptr )
368             {}
369
370             iterator_type( iterator_type const& src )
371             {
372                 if ( src.m_pNode ) {
373                     m_pNode = m_Guard.assign( src.m_pNode );
374                 }
375                 else
376                     m_pNode = nullptr;
377             }
378
379             value_ptr operator ->() const
380             {
381                 return m_pNode;
382             }
383
384             value_ref operator *() const
385             {
386                 assert( m_pNode != nullptr );
387                 return *m_pNode;
388             }
389
390             /// Pre-increment
391             iterator_type& operator ++()
392             {
393                 next();
394                 skip_deleted();
395                 return *this;
396             }
397
398             iterator_type& operator = (iterator_type const& src)
399             {
400                 m_pNode = src.m_pNode;
401                 m_Guard.assign( m_pNode );
402                 return *this;
403             }
404
405             template <bool C>
406             bool operator ==(iterator_type<C> const& i ) const
407             {
408                 return m_pNode == i.m_pNode;
409             }
410             template <bool C>
411             bool operator !=(iterator_type<C> const& i ) const
412             {
413                 return m_pNode != i.m_pNode;
414             }
415         };
416         //@endcond
417
418     public:
419     ///@name Forward iterators (only for debugging purpose)
420     //@{
421         /// Forward iterator
422         /**
423             The forward iterator for lazy list has some features:
424             - it has no post-increment operator
425             - to protect the value, the iterator contains a GC-specific guard + another guard is required locally for increment operator.
426               For some GC (\p gc::HP), a guard is limited resource per thread, so an exception (or assertion) "no free guard"
427               may be thrown if a limit of guard count per thread is exceeded.
428             - The iterator cannot be moved across thread boundary since it contains GC's guard that is thread-private GC data.
429             - Iterator ensures thread-safety even if you delete the item that iterator points to. However, in case of concurrent
430               deleting operations it is no guarantee that you iterate all item in the list.
431               Moreover, a crash is possible when you try to iterate the next element that has been deleted by concurrent thread.
432
433             @warning Use this iterator on the concurrent container for debugging purpose only.
434         */
435         typedef iterator_type<false>    iterator;
436         /// Const forward iterator
437         /**
438             For iterator's features and requirements see \ref iterator
439         */
440         typedef iterator_type<true>     const_iterator;
441
442         /// Returns a forward iterator addressing the first element in a list
443         /**
444             For empty list \code begin() == end() \endcode
445         */
446         iterator begin()
447         {
448             iterator it( &m_Head );
449             ++it        ;   // skip dummy head
450             return it;
451         }
452
453         /// Returns an iterator that addresses the location succeeding the last element in a list
454         /**
455             Do not use the value returned by <tt>end</tt> function to access any item.
456
457             The returned value can be used only to control reaching the end of the list.
458             For empty list \code begin() == end() \endcode
459         */
460         iterator end()
461         {
462             return iterator( &m_Tail );
463         }
464
465         /// Returns a forward const iterator addressing the first element in a list
466         const_iterator begin() const
467         {
468             return get_const_begin();
469         }
470
471         /// Returns a forward const iterator addressing the first element in a list
472         const_iterator cbegin() const
473         {
474             return get_const_begin();
475         }
476
477         /// Returns an const iterator that addresses the location succeeding the last element in a list
478         const_iterator end() const
479         {
480             return get_const_end();
481         }
482
483         /// Returns an const iterator that addresses the location succeeding the last element in a list
484         const_iterator cend() const
485         {
486             return get_const_end();
487         }
488     //@}
489
490     private:
491         //@cond
492         const_iterator get_const_begin() const
493         {
494             const_iterator it( const_cast<node_type *>( &m_Head ));
495             ++it        ;   // skip dummy head
496             return it;
497         }
498         const_iterator get_const_end() const
499         {
500             return const_iterator( const_cast<node_type *>(&m_Tail));
501         }
502         //@endcond
503
504     public:
505         /// Default constructor initializes empty list
506         LazyList()
507         {
508             m_Head.m_pNext.store( marked_node_ptr( &m_Tail ), memory_model::memory_order_relaxed );
509         }
510
511         //@cond
512         template <typename Stat, typename = std::enable_if<std::is_same<stat, lazy_list::wrapped_stat<Stat>>::value >>
513         explicit LazyList( Stat& st )
514             : m_Stat( st )
515         {
516             m_Head.m_pNext.store( marked_node_ptr( &m_Tail ), memory_model::memory_order_relaxed );
517         }
518         //@endcond
519
520         /// Destroys the list object
521         ~LazyList()
522         {
523             clear();
524             assert( m_Head.m_pNext.load( memory_model::memory_order_relaxed ).ptr() == &m_Tail );
525             m_Head.m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
526         }
527
528         /// Inserts new node
529         /**
530             The function inserts \p val in the list if the list does not contain
531             an item with key equal to \p val.
532
533             Returns \p true if \p val is linked into the list, \p false otherwise.
534         */
535         bool insert( value_type& val )
536         {
537             return insert_at( &m_Head, val );
538         }
539
540         /// Inserts new node
541         /**
542             This function is intended for derived non-intrusive containers.
543
544             The function allows to split new item creating into two part:
545             - create item with key only
546             - insert new item into the list
547             - if inserting is success, calls  \p f functor to initialize value-field of \p val.
548
549             The functor signature is:
550             \code
551                 void func( value_type& val );
552             \endcode
553             where \p val is the item inserted.
554             While the functor \p f is called the item \p val is locked so
555             the functor has an exclusive access to the item.
556             The user-defined functor is called only if the inserting is success.
557         */
558         template <typename Func>
559         bool insert( value_type& val, Func f )
560         {
561             return insert_at( &m_Head, val, f );
562         }
563
564         /// Updates the item
565         /**
566             The operation performs inserting or changing data with lock-free manner.
567
568             If the item \p val not found in the list, then \p val is inserted into the list
569             iff \p bAllowInsert is \p true.
570             Otherwise, the functor \p func is called with item found.
571             The functor signature is:
572             \code
573             struct functor {
574                 void operator()( bool bNew, value_type& item, value_type& val );
575             };
576             \endcode
577             with arguments:
578             - \p bNew - \p true if the item has been inserted, \p false otherwise
579             - \p item - item of the list
580             - \p val - argument \p val passed into the \p update() function
581             If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
582             refer to the same thing.
583
584             The functor may change non-key fields of the \p item.
585             While the functor \p f is working the item \p item is locked,
586             so \p func has exclusive access to the item.
587
588             Returns <tt> std::pair<bool, bool>  </tt> where \p first is \p true if operation is successful,
589             \p second is \p true if new item has been added or \p false if the item with \p key
590             already is in the list.
591
592             The function makes RCU lock internally.
593         */
594         template <typename Func>
595         std::pair<bool, bool> update( value_type& val, Func func, bool bAllowInsert = true )
596         {
597             return update_at( &m_Head, val, func, bAllowInsert );
598         }
599         //@cond
600         template <typename Func>
601         CDS_DEPRECATED("ensure() is deprecated, use update()")
602         std::pair<bool, bool> ensure( value_type& val, Func func )
603         {
604             return update( val, func, true );
605         }
606         //@endcond
607
608         /// Unlinks the item \p val from the list
609         /**
610             The function searches the item \p val in the list and unlink it from the list
611             if it is found and it is equal to \p val.
612
613             Difference between \ref erase and \p unlink functions: \p erase finds <i>a key</i>
614             and deletes the item found. \p unlink finds an item by key and deletes it
615             only if \p val is an item of that list, i.e. the pointer to item found
616             is equal to <tt> &val </tt>.
617
618             The function returns \p true if success and \p false otherwise.
619
620             \p disposer specified in \p Traits is called for unlinked item.
621         */
622         bool unlink( value_type& val )
623         {
624             return unlink_at( &m_Head, val );
625         }
626
627         /// Deletes the item from the list
628         /** \anchor cds_intrusive_LazyList_hp_erase_val
629             The function searches an item with key equal to \p key in the list,
630             unlinks it from the list, and returns \p true.
631             If the item with the key equal to \p key is not found the function return \p false.
632
633             \p disposer specified in \p Traits is called for deleted item.
634         */
635         template <typename Q>
636         bool erase( Q const& key )
637         {
638             return erase_at( &m_Head, key, key_comparator());
639         }
640
641         /// Deletes the item from the list using \p pred predicate for searching
642         /**
643             The function is an analog of \ref cds_intrusive_LazyList_hp_erase_val "erase(Q const&)"
644             but \p pred is used for key comparing.
645             \p Less functor has the interface like \p std::less.
646             \p pred must imply the same element order as the comparator used for building the list.
647
648             \p disposer specified in \p Traits is called for deleted item.
649         */
650         template <typename Q, typename Less>
651         bool erase_with( Q const& key, Less pred )
652         {
653             CDS_UNUSED( pred );
654             return erase_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>());
655         }
656
657         /// Deletes the item from the list
658         /** \anchor cds_intrusive_LazyList_hp_erase_func
659             The function searches an item with key equal to \p key in the list,
660             call \p func functor with item found, unlinks it from the list, and returns \p true.
661             The \p Func interface is
662             \code
663             struct functor {
664                 void operator()( value_type const& item );
665             };
666             \endcode
667
668             If \p key is not found the function return \p false.
669
670             \p disposer specified in \p Traits is called for deleted item.
671         */
672         template <typename Q, typename Func>
673         bool erase( const Q& key, Func func )
674         {
675             return erase_at( &m_Head, key, key_comparator(), func );
676         }
677
678         /// Deletes the item from the list using \p pred predicate for searching
679         /**
680             The function is an analog of \ref cds_intrusive_LazyList_hp_erase_func "erase(Q const&, Func)"
681             but \p pred is used for key comparing.
682             \p Less functor has the interface like \p std::less.
683             \p pred must imply the same element order as the comparator used for building the list.
684
685             \p disposer specified in \p Traits is called for deleted item.
686         */
687         template <typename Q, typename Less, typename Func>
688         bool erase_with( const Q& key, Less pred, Func func )
689         {
690             CDS_UNUSED( pred );
691             return erase_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>(), func );
692         }
693
694         /// Extracts the item from the list with specified \p key
695         /** \anchor cds_intrusive_LazyList_hp_extract
696             The function searches an item with key equal to \p key,
697             unlinks it from the list, and returns it as \p guarded_ptr.
698             If \p key is not found the function returns an empty guarded pointer.
699
700             Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
701
702             The \ref disposer specified in \p Traits class template parameter is called automatically
703             by garbage collector \p GC specified in class' template parameters when returned \p guarded_ptr object
704             will be destroyed or released.
705             @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
706
707             Usage:
708             \code
709             typedef cds::intrusive::LazyList< cds::gc::HP, foo, my_traits >  ord_list;
710             ord_list theList;
711             // ...
712             {
713                 ord_list::guarded_ptr gp( theList.extract( 5 ));
714                 // Deal with gp
715                 // ...
716
717                 // Destructor of gp releases internal HP guard
718             }
719             \endcode
720         */
721         template <typename Q>
722         guarded_ptr extract( Q const& key )
723         {
724             guarded_ptr gp;
725             extract_at( &m_Head, gp.guard(), key, key_comparator());
726             return gp;
727         }
728
729         /// Extracts the item from the list with comparing functor \p pred
730         /**
731             The function is an analog of \ref cds_intrusive_LazyList_hp_extract "extract(Q const&)"
732             but \p pred predicate is used for key comparing.
733
734             \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
735             in any order.
736             \p pred must imply the same element order as the comparator used for building the list.
737         */
738         template <typename Q, typename Less>
739         guarded_ptr extract_with( Q const& key, Less pred )
740         {
741             CDS_UNUSED( pred );
742             guarded_ptr gp;
743             extract_at( &m_Head, gp.guard(), key, cds::opt::details::make_comparator_from_less<Less>());
744             return gp;
745         }
746
747         /// Finds the key \p key
748         /** \anchor cds_intrusive_LazyList_hp_find
749             The function searches the item with key equal to \p key and calls the functor \p f for item found.
750             The interface of \p Func functor is:
751             \code
752             struct functor {
753                 void operator()( value_type& item, Q& key );
754             };
755             \endcode
756             where \p item is the item found, \p key is the <tt>find</tt> function argument.
757
758             The functor may change non-key fields of \p item.
759             While the functor \p f is calling the item \p item is locked.
760
761             The function returns \p true if \p key is found, \p false otherwise.
762         */
763         template <typename Q, typename Func>
764         bool find( Q& key, Func f )
765         {
766             return find_at( &m_Head, key, key_comparator(), f );
767         }
768         //@cond
769         template <typename Q, typename Func>
770         bool find( Q const& key, Func f )
771         {
772             return find_at( &m_Head, key, key_comparator(), f );
773         }
774         //@endcond
775
776         /// Finds the key \p key using \p pred predicate for searching
777         /**
778             The function is an analog of \ref cds_intrusive_LazyList_hp_find "find(Q&, Func)"
779             but \p pred is used for key comparing.
780             \p Less functor has the interface like \p std::less.
781             \p pred must imply the same element order as the comparator used for building the list.
782         */
783         template <typename Q, typename Less, typename Func>
784         bool find_with( Q& key, Less pred, Func f )
785         {
786             CDS_UNUSED( pred );
787             return find_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>(), f );
788         }
789         //@cond
790         template <typename Q, typename Less, typename Func>
791         bool find_with( Q const& key, Less pred, Func f )
792         {
793             CDS_UNUSED( pred );
794             return find_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>(), f );
795         }
796         //@endcond
797
798         /// Checks whether the list contains \p key
799         /**
800             The function searches the item with key equal to \p key
801             and returns \p true if it is found, and \p false otherwise.
802         */
803         template <typename Q>
804         bool contains( Q const& key )
805         {
806             return find_at( &m_Head, key, key_comparator());
807         }
808         //@cond
809         template <typename Q>
810         CDS_DEPRECATED("deprecated, use contains()")
811         bool find( Q const& key )
812         {
813             return contains( key );
814         }
815         //@cond
816
817         /// Checks whether the map contains \p key using \p pred predicate for searching
818         /**
819             The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
820             \p Less functor has the interface like \p std::less.
821             \p Less must imply the same element order as the comparator used for building the list.
822         */
823         template <typename Q, typename Less>
824         bool contains( Q const& key, Less pred )
825         {
826             CDS_UNUSED( pred );
827             return find_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>());
828         }
829         //@cond
830         template <typename Q, typename Less>
831         CDS_DEPRECATED("deprecated, use contains()")
832         bool find_with( Q const& key, Less pred )
833         {
834             return contains( key, pred );
835         }
836         //@endcond
837
838         /// Finds \p key and return the item found
839         /** \anchor cds_intrusive_LazyList_hp_get
840             The function searches the item with key equal to \p key
841             and returns an guarded pointer to it.
842             If \p key is not found the function returns an empty guarded pointer.
843
844             The \ref disposer specified in \p Traits class template parameter is called
845             by garbage collector \p GC automatically when returned \p guarded_ptr object
846             will be destroyed or released.
847             @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
848
849             Usage:
850             \code
851             typedef cds::intrusive::LazyList< cds::gc::HP, foo, my_traits >  ord_list;
852             ord_list theList;
853             // ...
854             {
855                 ord_list::guarded_ptr gp(theList.get( 5 ));
856                 if ( gp ) {
857                     // Deal with gp
858                     //...
859                 }
860                 // Destructor of guarded_ptr releases internal HP guard
861             }
862             \endcode
863
864             Note the compare functor specified for class \p Traits template parameter
865             should accept a parameter of type \p Q that can be not the same as \p value_type.
866         */
867         template <typename Q>
868         guarded_ptr get( Q const& key )
869         {
870             guarded_ptr gp;
871             get_at( &m_Head, gp.guard(), key, key_comparator());
872             return gp;
873         }
874
875         /// Finds \p key and return the item found
876         /**
877             The function is an analog of \ref cds_intrusive_LazyList_hp_get "get( Q const&)"
878             but \p pred is used for comparing the keys.
879
880             \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
881             in any order.
882             \p pred must imply the same element order as the comparator used for building the list.
883         */
884         template <typename Q, typename Less>
885         guarded_ptr get_with( Q const& key, Less pred )
886         {
887             CDS_UNUSED( pred );
888             guarded_ptr gp;
889             get_at( &m_Head, gp.guard(), key, cds::opt::details::make_comparator_from_less<Less>());
890             return gp;
891         }
892
893         /// Clears the list
894         void clear()
895         {
896             typename gc::Guard guard;
897             marked_node_ptr h;
898             while ( !empty()) {
899                 h = m_Head.m_pNext.load( memory_model::memory_order_relaxed );
900                 guard.assign( node_traits::to_value_ptr( h.ptr()));
901                 if ( m_Head.m_pNext.load(memory_model::memory_order_acquire) == h ) {
902                     m_Head.m_Lock.lock();
903                     h->m_Lock.lock();
904
905                     unlink_node( &m_Head, h.ptr(), &m_Head );
906                     --m_ItemCounter;
907
908                     h->m_Lock.unlock();
909                     m_Head.m_Lock.unlock();
910
911                     retire_node( h.ptr()) ; // free node
912                 }
913             }
914         }
915
916         /// Checks if the list is empty
917         bool empty() const
918         {
919             return m_Head.m_pNext.load( memory_model::memory_order_relaxed ).ptr() == &m_Tail;
920         }
921
922         /// Returns list's item count
923         /**
924             The value returned depends on item counter provided by \p Traits. For \p atomicity::empty_item_counter,
925             this function always returns 0.
926
927             @note Even if you use real item counter and it returns 0, this fact does not mean that the list
928             is empty. To check list emptiness use \p empty() method.
929         */
930         size_t size() const
931         {
932             return m_ItemCounter.value();
933         }
934
935         /// Returns const reference to internal statistics
936         stat const& statistics() const
937         {
938             return m_Stat;
939         }
940
941     protected:
942         //@cond
943         // split-list support
944         bool insert_aux_node( node_type * pNode )
945         {
946             return insert_aux_node( &m_Head, pNode );
947         }
948
949         // split-list support
950         bool insert_aux_node( node_type * pHead, node_type * pNode )
951         {
952             assert( pNode != nullptr );
953
954             // Hack: convert node_type to value_type.
955             // In principle, auxiliary node cannot be reducible to value_type
956             // We assume that internal comparator can correctly distinguish aux and regular node.
957             return insert_at( pHead, *node_traits::to_value_ptr( pNode ));
958         }
959
960         bool insert_at( node_type * pHead, value_type& val )
961         {
962             position pos;
963             key_comparator  cmp;
964
965             while ( true ) {
966                 search( pHead, val, pos, key_comparator());
967                 {
968                     scoped_position_lock alp( pos );
969                     if ( validate( pos.pPred, pos.pCur )) {
970                         if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
971                             // failed: key already in list
972                             m_Stat.onInsertFailed();
973                             return false;
974                         }
975                         else {
976                             link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
977                             break;
978                         }
979                     }
980                 }
981
982                 m_Stat.onInsertRetry();
983             }
984
985             ++m_ItemCounter;
986             m_Stat.onInsertSuccess();
987             return true;
988         }
989
990         template <typename Func>
991         bool insert_at( node_type * pHead, value_type& val, Func f )
992         {
993             position pos;
994             key_comparator  cmp;
995
996             while ( true ) {
997                 search( pHead, val, pos, key_comparator());
998                 {
999                     scoped_position_lock alp( pos );
1000                     if ( validate( pos.pPred, pos.pCur )) {
1001                         if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
1002                             // failed: key already in list
1003                             m_Stat.onInsertFailed();
1004                             return false;
1005                         }
1006                         else {
1007                             link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
1008                             f( val );
1009                             break;
1010                         }
1011                     }
1012                 }
1013
1014                 m_Stat.onInsertRetry();
1015             }
1016
1017             ++m_ItemCounter;
1018             m_Stat.onInsertSuccess();
1019             return true;
1020         }
1021
1022         template <typename Func>
1023         std::pair<bool, bool> update_at( node_type * pHead, value_type& val, Func func, bool bAllowInsert )
1024         {
1025             position pos;
1026             key_comparator  cmp;
1027
1028             while ( true ) {
1029                 search( pHead, val, pos, key_comparator());
1030                 {
1031                     scoped_position_lock alp( pos );
1032                     if ( validate( pos.pPred, pos.pCur )) {
1033                         if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
1034                             // key already in the list
1035
1036                             func( false, *node_traits::to_value_ptr( *pos.pCur ) , val );
1037                             m_Stat.onUpdateExisting();
1038                             return std::make_pair( true, false );
1039                         }
1040                         else {
1041                             // new key
1042                             if ( !bAllowInsert ) {
1043                                 m_Stat.onUpdateFailed();
1044                                 return std::make_pair( false, false );
1045                             }
1046
1047                             link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
1048                             func( true, val, val );
1049                             break;
1050                         }
1051                     }
1052                 }
1053
1054                 m_Stat.onUpdateRetry();
1055             }
1056
1057             ++m_ItemCounter;
1058             m_Stat.onUpdateNew();
1059             return std::make_pair( true, true );
1060         }
1061
1062         bool unlink_at( node_type * pHead, value_type& val )
1063         {
1064             position pos;
1065             key_comparator  cmp;
1066
1067             while ( true ) {
1068                 search( pHead, val, pos, key_comparator());
1069                 {
1070                     int nResult = 0;
1071                     {
1072                         scoped_position_lock alp( pos );
1073                         if ( validate( pos.pPred, pos.pCur )) {
1074                             if ( pos.pCur != &m_Tail
1075                                 && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0
1076                                 && node_traits::to_value_ptr( pos.pCur ) == &val )
1077                             {
1078                                 // item found
1079                                 unlink_node( pos.pPred, pos.pCur, pHead );
1080                                 nResult = 1;
1081                             }
1082                             else
1083                                 nResult = -1;
1084                         }
1085                     }
1086
1087                     if ( nResult ) {
1088                         if ( nResult > 0 ) {
1089                             --m_ItemCounter;
1090                             retire_node( pos.pCur );
1091                             m_Stat.onEraseSuccess();
1092                             return true;
1093                         }
1094
1095                         m_Stat.onEraseFailed();
1096                         return false;
1097                     }
1098                 }
1099
1100                 m_Stat.onEraseRetry();
1101             }
1102         }
1103
1104         template <typename Q, typename Compare, typename Func>
1105         bool erase_at( node_type * pHead, const Q& val, Compare cmp, Func f, position& pos )
1106         {
1107             while ( true ) {
1108                 search( pHead, val, pos, cmp );
1109                 {
1110                     int nResult = 0;
1111                     {
1112                         scoped_position_lock alp( pos );
1113                         if ( validate( pos.pPred, pos.pCur )) {
1114                             if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
1115                                 // key found
1116                                 unlink_node( pos.pPred, pos.pCur, pHead );
1117                                 f( *node_traits::to_value_ptr( *pos.pCur ));
1118                                 nResult = 1;
1119                             }
1120                             else {
1121                                 nResult = -1;
1122                             }
1123                         }
1124                     }
1125                     if ( nResult ) {
1126                         if ( nResult > 0 ) {
1127                             --m_ItemCounter;
1128                             retire_node( pos.pCur );
1129                             m_Stat.onEraseSuccess();
1130                             return true;
1131                         }
1132
1133                         m_Stat.onEraseFailed();
1134                         return false;
1135                     }
1136                 }
1137
1138                 m_Stat.onEraseRetry();
1139             }
1140         }
1141
1142         template <typename Q, typename Compare, typename Func>
1143         bool erase_at( node_type * pHead, const Q& val, Compare cmp, Func f )
1144         {
1145             position pos;
1146             return erase_at( pHead, val, cmp, f, pos );
1147         }
1148
1149         template <typename Q, typename Compare>
1150         bool erase_at( node_type * pHead, const Q& val, Compare cmp )
1151         {
1152             position pos;
1153             return erase_at( pHead, val, cmp, [](value_type const &){}, pos );
1154         }
1155
1156         template <typename Q, typename Compare>
1157         bool extract_at( node_type * pHead, typename guarded_ptr::native_guard& gp, const Q& val, Compare cmp )
1158         {
1159             position pos;
1160             if ( erase_at( pHead, val, cmp, [](value_type const &){}, pos )) {
1161                 gp.set( pos.guards.template get<value_type>(position::guard_current_item));
1162                 return true;
1163             }
1164             return false;
1165         }
1166
1167         template <typename Q, typename Compare, typename Func>
1168         bool find_at( node_type * pHead, Q& val, Compare cmp, Func f )
1169         {
1170             position pos;
1171
1172             search( pHead, val, pos, cmp );
1173             if ( pos.pCur != &m_Tail ) {
1174                 std::unique_lock< typename node_type::lock_type> al( pos.pCur->m_Lock );
1175                 if ( !pos.pCur->is_marked()
1176                     && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 )
1177                 {
1178                     f( *node_traits::to_value_ptr( *pos.pCur ), val );
1179                     m_Stat.onFindSuccess();
1180                     return true;
1181                 }
1182             }
1183
1184             m_Stat.onFindFailed();
1185             return false;
1186         }
1187
1188         template <typename Q, typename Compare>
1189         bool find_at( node_type * pHead, Q const& val, Compare cmp )
1190         {
1191             position pos;
1192
1193             search( pHead, val, pos, cmp );
1194             if ( pos.pCur != &m_Tail && !pos.pCur->is_marked() && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
1195                 m_Stat.onFindSuccess();
1196                 return true;
1197             }
1198
1199             m_Stat.onFindFailed();
1200             return false;
1201         }
1202
1203         template <typename Q, typename Compare>
1204         bool get_at( node_type * pHead, typename guarded_ptr::native_guard& gp, Q const& val, Compare cmp )
1205         {
1206             position pos;
1207
1208             search( pHead, val, pos, cmp );
1209             if ( pos.pCur != &m_Tail
1210                 && !pos.pCur->is_marked()
1211                 && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 )
1212             {
1213                 gp.set( pos.guards.template get<value_type>( position::guard_current_item ));
1214                 m_Stat.onFindSuccess();
1215                 return true;
1216             }
1217
1218             m_Stat.onFindFailed();
1219             return false;
1220         }
1221
1222         //@endcond
1223
1224     protected:
1225         //@cond
1226         template <typename Q, typename Compare>
1227         void search( node_type * pHead, const Q& key, position& pos, Compare cmp )
1228         {
1229             node_type const* pTail = &m_Tail;
1230
1231             marked_node_ptr pCur( pHead );
1232             marked_node_ptr pPrev( pHead );
1233
1234             while ( pCur.ptr() != pTail ) {
1235                 if ( pCur.ptr() != pHead ) {
1236                     if ( cmp( *node_traits::to_value_ptr( *pCur.ptr()), key ) >= 0 )
1237                         break;
1238                 }
1239
1240                 pos.guards.copy( position::guard_prev_item, position::guard_current_item );
1241                 pPrev = pCur;
1242
1243                 pCur = pos.guards.protect( position::guard_current_item, pPrev->m_pNext,
1244                     []( marked_node_ptr p ) { return node_traits::to_value_ptr( p.ptr()); }
1245                 );
1246                 assert( pCur.ptr() != nullptr );
1247                 if ( pCur.bits())
1248                     pPrev = pCur = pHead;
1249             }
1250
1251             pos.pCur = pCur.ptr();
1252             pos.pPred = pPrev.ptr();
1253         }
1254
1255         bool validate( node_type * pPred, node_type * pCur ) CDS_NOEXCEPT
1256         {
1257             if ( validate_link( pPred, pCur )) {
1258                 m_Stat.onValidationSuccess();
1259                 return true;
1260             }
1261
1262             m_Stat.onValidationFailed();
1263             return true;
1264         }
1265
1266         static bool validate_link( node_type * pPred, node_type * pCur ) CDS_NOEXCEPT
1267         {
1268             return !pPred->is_marked()
1269                 && !pCur->is_marked()
1270                 && pPred->m_pNext.load(memory_model::memory_order_relaxed) == pCur;
1271         }
1272
1273         //@endcond
1274     };
1275 }}  // namespace cds::intrusive
1276
1277 #endif // CDSLIB_INTRUSIVE_IMPL_LAZY_LIST_H