Fixed UBsan warning "call to function through pointer to incorrect function type"
[libcds.git] / cds / intrusive / impl / skip_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-2017
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_SKIP_LIST_H
32 #define CDSLIB_INTRUSIVE_IMPL_SKIP_LIST_H
33
34 #include <type_traits>
35 #include <memory>
36 #include <functional>   // ref
37 #include <cds/intrusive/details/skip_list_base.h>
38 #include <cds/opt/compare.h>
39 #include <cds/details/binary_functor_wrapper.h>
40
41 namespace cds { namespace intrusive {
42
43     //@cond
44     namespace skip_list { namespace details {
45
46         template <class GC, typename NodeTraits, typename BackOff, bool IsConst>
47         class iterator {
48         public:
49             typedef GC                                  gc;
50             typedef NodeTraits                          node_traits;
51             typedef BackOff                             back_off;
52             typedef typename node_traits::node_type     node_type;
53             typedef typename node_traits::value_type    value_type;
54             static CDS_CONSTEXPR bool const c_isConst = IsConst;
55
56             typedef typename std::conditional< c_isConst, value_type const&, value_type&>::type   value_ref;
57
58         protected:
59             typedef typename node_type::marked_ptr          marked_ptr;
60             typedef typename node_type::atomic_marked_ptr   atomic_marked_ptr;
61
62             typename gc::Guard      m_guard;
63             node_type *             m_pNode;
64
65         protected:
66             static value_type * gc_protect( marked_ptr p )
67             {
68                 return node_traits::to_value_ptr( p.ptr());
69             }
70
71             void next()
72             {
73                 typename gc::Guard g;
74                 g.copy( m_guard );
75                 back_off bkoff;
76
77                 for (;;) {
78                     if ( m_pNode->next( m_pNode->height() - 1 ).load( atomics::memory_order_acquire ).bits()) {
79                         // Current node is marked as deleted. So, its next pointer can point to anything
80                         // In this case we interrupt our iteration and returns end() iterator.
81                         *this = iterator();
82                         return;
83                     }
84
85                     marked_ptr p = m_guard.protect( (*m_pNode)[0], gc_protect );
86                     node_type * pp = p.ptr();
87                     if ( p.bits()) {
88                         // p is marked as deleted. Spin waiting for physical removal
89                         bkoff();
90                         continue;
91                     }
92                     else if ( pp && pp->next( pp->height() - 1 ).load( atomics::memory_order_relaxed ).bits()) {
93                         // p is marked as deleted. Spin waiting for physical removal
94                         bkoff();
95                         continue;
96                     }
97
98                     m_pNode = pp;
99                     break;
100                 }
101             }
102
103         public: // for internal use only!!!
104             iterator( node_type& refHead )
105                 : m_pNode( nullptr )
106             {
107                 back_off bkoff;
108
109                 for (;;) {
110                     marked_ptr p = m_guard.protect( refHead[0], gc_protect );
111                     if ( !p.ptr()) {
112                         // empty skip-list
113                         m_guard.clear();
114                         break;
115                     }
116
117                     node_type * pp = p.ptr();
118                     // Logically deleted node is marked from highest level
119                     if ( !pp->next( pp->height() - 1 ).load( atomics::memory_order_acquire ).bits()) {
120                         m_pNode = pp;
121                         break;
122                     }
123
124                     bkoff();
125                 }
126             }
127
128         public:
129             iterator()
130                 : m_pNode( nullptr )
131             {}
132
133             iterator( iterator const& s)
134                 : m_pNode( s.m_pNode )
135             {
136                 m_guard.assign( node_traits::to_value_ptr(m_pNode));
137             }
138
139             value_type * operator ->() const
140             {
141                 assert( m_pNode != nullptr );
142                 assert( node_traits::to_value_ptr( m_pNode ) != nullptr );
143
144                 return node_traits::to_value_ptr( m_pNode );
145             }
146
147             value_ref operator *() const
148             {
149                 assert( m_pNode != nullptr );
150                 assert( node_traits::to_value_ptr( m_pNode ) != nullptr );
151
152                 return *node_traits::to_value_ptr( m_pNode );
153             }
154
155             /// Pre-increment
156             iterator& operator ++()
157             {
158                 next();
159                 return *this;
160             }
161
162             iterator& operator =(const iterator& src)
163             {
164                 m_pNode = src.m_pNode;
165                 m_guard.copy( src.m_guard );
166                 return *this;
167             }
168
169             template <typename Bkoff, bool C>
170             bool operator ==(iterator<gc, node_traits, Bkoff, C> const& i ) const
171             {
172                 return m_pNode == i.m_pNode;
173             }
174             template <typename Bkoff, bool C>
175             bool operator !=(iterator<gc, node_traits, Bkoff, C> const& i ) const
176             {
177                 return !( *this == i );
178             }
179         };
180     }}  // namespace skip_list::details
181     //@endcond
182
183     /// Lock-free skip-list set
184     /** @ingroup cds_intrusive_map
185         @anchor cds_intrusive_SkipListSet_hp
186
187         The implementation of well-known probabilistic data structure called skip-list
188         invented by W.Pugh in his papers:
189             - [1989] W.Pugh Skip Lists: A Probabilistic Alternative to Balanced Trees
190             - [1990] W.Pugh A Skip List Cookbook
191
192         A skip-list is a probabilistic data structure that provides expected logarithmic
193         time search without the need of rebalance. The skip-list is a collection of sorted
194         linked list. Nodes are ordered by key. Each node is linked into a subset of the lists.
195         Each list has a level, ranging from 0 to 32. The bottom-level list contains
196         all the nodes, and each higher-level list is a sublist of the lower-level lists.
197         Each node is created with a random top level (with a random height), and belongs
198         to all lists up to that level. The probability that a node has the height 1 is 1/2.
199         The probability that a node has the height N is 1/2 ** N (more precisely,
200         the distribution depends on an random generator provided, but our generators
201         have this property).
202
203         The lock-free variant of skip-list is implemented according to book
204             - [2008] M.Herlihy, N.Shavit "The Art of Multiprocessor Programming",
205                 chapter 14.4 "A Lock-Free Concurrent Skiplist".
206
207         <b>Template arguments</b>:
208             - \p GC - Garbage collector used. Note the \p GC must be the same as the GC used for item type \p T, see \p skip_list::node.
209             - \p T - type to be stored in the list. The type must be based on \p skip_list::node (for \p skip_list::base_hook)
210                 or it must have a member of type \p skip_list::node (for \p skip_list::member_hook).
211             - \p Traits - skip-list traits, default is \p skip_list::traits.
212                 It is possible to declare option-based list with \p cds::intrusive::skip_list::make_traits metafunction istead of \p Traits
213                 template argument.
214
215         @warning The skip-list requires up to 67 hazard pointers that may be critical for some GCs for which
216             the guard count is limited (like as \p gc::HP). Those GCs should be explicitly initialized with
217             hazard pointer enough: \code cds::gc::HP myhp( 67 ) \endcode. Otherwise an run-time exception may be raised
218             when you try to create skip-list object.
219
220         There are several specializations of \p %SkipListSet for each \p GC. You should include:
221         - <tt><cds/intrusive/skip_list_hp.h></tt> for \p gc::HP garbage collector
222         - <tt><cds/intrusive/skip_list_dhp.h></tt> for \p gc::DHP garbage collector
223         - <tt><cds/intrusive/skip_list_nogc.h></tt> for \ref cds_intrusive_SkipListSet_nogc for append-only set
224         - <tt><cds/intrusive/skip_list_rcu.h></tt> for \ref cds_intrusive_SkipListSet_rcu "RCU type"
225
226         <b>Iterators</b>
227
228         The class supports a forward iterator (\ref iterator and \ref const_iterator).
229         The iteration is ordered.
230         The iterator object is thread-safe: the element pointed by the iterator object is guarded,
231         so, the element cannot be reclaimed while the iterator object is alive.
232         However, passing an iterator object between threads is dangerous.
233
234         @warning Due to concurrent nature of skip-list set it is not guarantee that you can iterate
235         all elements in the set: any concurrent deletion can exclude the element
236         pointed by the iterator from the set, and your iteration can be terminated
237         before end of the set. Therefore, such iteration is more suitable for debugging purpose only
238
239         Remember, each iterator object requires 2 additional hazard pointers, that may be
240         a limited resource for \p GC like as \p gc::HP (for \p gc::DHP the count of
241         guards is unlimited).
242
243         The iterator class supports the following minimalistic interface:
244         \code
245         struct iterator {
246             // Default ctor
247             iterator();
248
249             // Copy ctor
250             iterator( iterator const& s);
251
252             value_type * operator ->() const;
253             value_type& operator *() const;
254
255             // Pre-increment
256             iterator& operator ++();
257
258             // Copy assignment
259             iterator& operator = (const iterator& src);
260
261             bool operator ==(iterator const& i ) const;
262             bool operator !=(iterator const& i ) const;
263         };
264         \endcode
265         Note, the iterator object returned by \p end(), \p cend() member functions points to \p nullptr and should not be dereferenced.
266
267         <b>How to use</b>
268
269         You should incorporate \p skip_list::node into your struct \p T and provide
270         appropriate \p skip_list::traits::hook in your \p Traits template parameters. Usually, for \p Traits you
271         define a struct based on \p skip_list::traits.
272
273         Example for \p gc::HP and base hook:
274         \code
275         // Include GC-related skip-list specialization
276         #include <cds/intrusive/skip_list_hp.h>
277
278         // Data stored in skip list
279         struct my_data: public cds::intrusive::skip_list::node< cds::gc::HP >
280         {
281             // key field
282             std::string     strKey;
283
284             // other data
285             // ...
286         };
287
288         // my_data compare functor
289         struct my_data_cmp {
290             int operator()( const my_data& d1, const my_data& d2 )
291             {
292                 return d1.strKey.compare( d2.strKey );
293             }
294
295             int operator()( const my_data& d, const std::string& s )
296             {
297                 return d.strKey.compare(s);
298             }
299
300             int operator()( const std::string& s, const my_data& d )
301             {
302                 return s.compare( d.strKey );
303             }
304         };
305
306
307         // Declare your traits
308         struct my_traits: public cds::intrusive::skip_list::traits
309         {
310             typedef cds::intrusive::skip_list::base_hook< cds::opt::gc< cds::gc::HP > >   hook;
311             typedef my_data_cmp compare;
312         };
313
314         // Declare skip-list set type
315         typedef cds::intrusive::SkipListSet< cds::gc::HP, my_data, my_traits >     traits_based_set;
316         \endcode
317
318         Equivalent option-based code:
319         \code
320         // GC-related specialization
321         #include <cds/intrusive/skip_list_hp.h>
322
323         struct my_data {
324             // see above
325         };
326         struct compare {
327             // see above
328         };
329
330         // Declare option-based skip-list set
331         typedef cds::intrusive::SkipListSet< cds::gc::HP
332             ,my_data
333             , typename cds::intrusive::skip_list::make_traits<
334                 cds::intrusive::opt::hook< cds::intrusive::skip_list::base_hook< cds::opt::gc< cds::gc::HP > > >
335                 ,cds::intrusive::opt::compare< my_data_cmp >
336             >::type
337         > option_based_set;
338
339         \endcode
340     */
341     template <
342         class GC
343        ,typename T
344 #ifdef CDS_DOXYGEN_INVOKED
345        ,typename Traits = skip_list::traits
346 #else
347        ,typename Traits
348 #endif
349     >
350     class SkipListSet
351     {
352     public:
353         typedef GC      gc;         ///< Garbage collector
354         typedef T       value_type; ///< type of value stored in the skip-list
355         typedef Traits  traits;     ///< Traits template parameter
356
357         typedef typename traits::hook    hook;      ///< hook type
358         typedef typename hook::node_type node_type; ///< node type
359
360 #   ifdef CDS_DOXYGEN_INVOKED
361         typedef implementation_defined key_comparator  ;    ///< key comparison functor based on opt::compare and opt::less option setter.
362 #   else
363         typedef typename opt::details::make_comparator< value_type, traits >::type key_comparator;
364 #   endif
365
366         typedef typename traits::disposer  disposer;   ///< item disposer
367         typedef typename get_node_traits< value_type, node_type, hook>::type node_traits; ///< node traits
368
369         typedef typename traits::item_counter  item_counter;   ///< Item counting policy
370         typedef typename traits::memory_model  memory_model;   ///< Memory ordering, see \p cds::opt::memory_model option
371         typedef typename traits::random_level_generator random_level_generator; ///< random level generator
372         typedef typename traits::allocator     allocator_type;   ///< allocator for maintaining array of next pointers of the node
373         typedef typename traits::back_off      back_off;   ///< Back-off strategy
374         typedef typename traits::stat          stat;       ///< internal statistics type
375
376     public:
377         typedef typename gc::template guarded_ptr< value_type > guarded_ptr; ///< Guarded pointer
378
379         /// Max node height. The actual node height should be in range <tt>[0 .. c_nMaxHeight)</tt>
380         /**
381             The max height is specified by \ref skip_list::random_level_generator "random level generator" constant \p m_nUpperBound
382             but it should be no more than 32 (\p skip_list::c_nHeightLimit).
383         */
384         static unsigned int const c_nMaxHeight = std::conditional<
385             (random_level_generator::c_nUpperBound <= skip_list::c_nHeightLimit),
386             std::integral_constant< unsigned int, random_level_generator::c_nUpperBound >,
387             std::integral_constant< unsigned int, skip_list::c_nHeightLimit >
388         >::type::value;
389
390         //@cond
391         static unsigned int const c_nMinHeight = 5;
392         //@endcond
393
394         // c_nMaxHeight * 2 - pPred/pSucc guards
395         // + 1 - for erase, unlink
396         // + 1 - for clear
397         // + 1 - for help_remove()
398         static size_t const c_nHazardPtrCount = c_nMaxHeight * 2 + 3; ///< Count of hazard pointer required for the skip-list
399
400     protected:
401         typedef typename node_type::atomic_marked_ptr   atomic_node_ptr;   ///< Atomic marked node pointer
402         typedef typename node_type::marked_ptr          marked_node_ptr;   ///< Node marked pointer
403
404     protected:
405         //@cond
406         typedef skip_list::details::intrusive_node_builder< node_type, atomic_node_ptr, allocator_type > intrusive_node_builder;
407
408         typedef typename std::conditional<
409             std::is_same< typename traits::internal_node_builder, cds::opt::none >::value
410             ,intrusive_node_builder
411             ,typename traits::internal_node_builder
412         >::type node_builder;
413
414         typedef std::unique_ptr< node_type, typename node_builder::node_disposer > scoped_node_ptr;
415
416         struct position {
417             node_type *   pPrev[ c_nMaxHeight ];
418             node_type *   pSucc[ c_nMaxHeight ];
419
420             typename gc::template GuardArray< c_nMaxHeight * 2 > guards;   ///< Guards array for pPrev/pSucc
421             node_type *   pCur;   // guarded by one of guards
422         };
423         //@endcond
424
425     public:
426         /// Default constructor
427         /**
428             The constructor checks whether the count of guards is enough
429             for skip-list and may raise an exception if not.
430         */
431         SkipListSet()
432             : m_Head( c_nMaxHeight )
433             , m_nHeight( c_nMinHeight )
434         {
435             static_assert( (std::is_same< gc, typename node_type::gc >::value), "GC and node_type::gc must be the same type" );
436
437             gc::check_available_guards( c_nHazardPtrCount );
438
439             // Barrier for head node
440             atomics::atomic_thread_fence( memory_model::memory_order_release );
441         }
442
443         /// Clears and destructs the skip-list
444         ~SkipListSet()
445         {
446             destroy();
447         }
448
449     public:
450     ///@name Forward iterators (only for debugging purpose)
451     //@{
452         /// Iterator type
453         /**
454             The forward iterator has some features:
455             - it has no post-increment operator
456             - to protect the value, the iterator contains a GC-specific guard + another guard is required locally for increment operator.
457               For some GC (like as \p gc::HP), a guard is a limited resource per thread, so an exception (or assertion) "no free guard"
458               may be thrown if the limit of guard count per thread is exceeded.
459             - The iterator cannot be moved across thread boundary because it contains thread-private GC's guard.
460             - Iterator ensures thread-safety even if you delete the item the iterator points to. However, in case of concurrent
461               deleting operations there is no guarantee that you iterate all item in the list.
462               Moreover, a crash is possible when you try to iterate the next element that has been deleted by concurrent thread.
463
464             @warning Use this iterator on the concurrent container for debugging purpose only.
465
466             The iterator interface:
467             \code
468             class iterator {
469             public:
470                 // Default constructor
471                 iterator();
472
473                 // Copy construtor
474                 iterator( iterator const& src );
475
476                 // Dereference operator
477                 value_type * operator ->() const;
478
479                 // Dereference operator
480                 value_type& operator *() const;
481
482                 // Preincrement operator
483                 iterator& operator ++();
484
485                 // Assignment operator
486                 iterator& operator = (iterator const& src);
487
488                 // Equality operators
489                 bool operator ==(iterator const& i ) const;
490                 bool operator !=(iterator const& i ) const;
491             };
492             \endcode
493         */
494         typedef skip_list::details::iterator< gc, node_traits, back_off, false >  iterator;
495
496         /// Const iterator type
497         typedef skip_list::details::iterator< gc, node_traits, back_off, true >   const_iterator;
498
499         /// Returns a forward iterator addressing the first element in a set
500         iterator begin()
501         {
502             return iterator( *m_Head.head());
503         }
504
505         /// Returns a forward const iterator addressing the first element in a set
506         const_iterator begin() const
507         {
508             return const_iterator( *m_Head.head());
509         }
510         /// Returns a forward const iterator addressing the first element in a set
511         const_iterator cbegin() const
512         {
513             return const_iterator( *m_Head.head());
514         }
515
516         /// Returns a forward iterator that addresses the location succeeding the last element in a set.
517         iterator end()
518         {
519             return iterator();
520         }
521
522         /// Returns a forward const iterator that addresses the location succeeding the last element in a set.
523         const_iterator end() const
524         {
525             return const_iterator();
526         }
527         /// Returns a forward const iterator that addresses the location succeeding the last element in a set.
528         const_iterator cend() const
529         {
530             return const_iterator();
531         }
532     //@}
533
534     public:
535         /// Inserts new node
536         /**
537             The function inserts \p val in the set if it does not contain
538             an item with key equal to \p val.
539
540             Returns \p true if \p val is placed into the set, \p false otherwise.
541         */
542         bool insert( value_type& val )
543         {
544             return insert( val, []( value_type& ) {} );
545         }
546
547         /// Inserts new node
548         /**
549             This function is intended for derived non-intrusive containers.
550
551             The function allows to split creating of new item into two part:
552             - create item with key only
553             - insert new item into the set
554             - if inserting is success, calls  \p f functor to initialize value-field of \p val.
555
556             The functor signature is:
557             \code
558                 void func( value_type& val );
559             \endcode
560             where \p val is the item inserted. User-defined functor \p f should guarantee that during changing
561             \p val no any other changes could be made on this set's item by concurrent threads.
562             The user-defined functor is called only if the inserting is success.
563         */
564         template <typename Func>
565         bool insert( value_type& val, Func f )
566         {
567             typename gc::Guard gNew;
568             gNew.assign( &val );
569
570             node_type * pNode = node_traits::to_node_ptr( val );
571             scoped_node_ptr scp( pNode );
572             unsigned int nHeight = pNode->height();
573             bool bTowerOk = pNode->has_tower(); // nHeight > 1 && pNode->get_tower() != nullptr;
574             bool bTowerMade = false;
575
576             position pos;
577             while ( true )
578             {
579                 if ( find_position( val, pos, key_comparator(), true )) {
580                     // scoped_node_ptr deletes the node tower if we create it
581                     if ( !bTowerMade )
582                         scp.release();
583
584                     m_Stat.onInsertFailed();
585                     return false;
586                 }
587
588                 if ( !bTowerOk ) {
589                     build_node( pNode );
590                     nHeight = pNode->height();
591                     bTowerMade = pNode->has_tower();
592                     bTowerOk = true;
593                 }
594
595                 if ( !insert_at_position( val, pNode, pos, f )) {
596                     m_Stat.onInsertRetry();
597                     continue;
598                 }
599
600                 increase_height( nHeight );
601                 ++m_ItemCounter;
602                 m_Stat.onAddNode( nHeight );
603                 m_Stat.onInsertSuccess();
604                 scp.release();
605                 return true;
606             }
607         }
608
609         /// Updates the node
610         /**
611             The operation performs inserting or changing data with lock-free manner.
612
613             If the item \p val is not found in the set, then \p val is inserted into the set
614             iff \p bInsert is \p true.
615             Otherwise, the functor \p func is called with item found.
616             The functor \p func signature is:
617             \code
618                 void func( bool bNew, value_type& item, value_type& val );
619             \endcode
620             with arguments:
621             - \p bNew - \p true if the item has been inserted, \p false otherwise
622             - \p item - item of the set
623             - \p val - argument \p val passed into the \p %update() function
624             If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
625             refer to the same thing.
626
627             Returns std::pair<bool, bool> where \p first is \p true if operation is successful,
628             i.e. the node has been inserted or updated,
629             \p second is \p true if new item has been added or \p false if the item with \p key
630             already exists.
631
632             @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
633         */
634         template <typename Func>
635         std::pair<bool, bool> update( value_type& val, Func func, bool bInsert = true )
636         {
637             typename gc::Guard gNew;
638             gNew.assign( &val );
639
640             node_type * pNode = node_traits::to_node_ptr( val );
641             scoped_node_ptr scp( pNode );
642             unsigned int nHeight = pNode->height();
643             bool bTowerOk = pNode->has_tower();
644             bool bTowerMade = false;
645
646             position pos;
647             while ( true )
648             {
649                 bool bFound = find_position( val, pos, key_comparator(), true );
650                 if ( bFound ) {
651                     // scoped_node_ptr deletes the node tower if we create it before
652                     if ( !bTowerMade )
653                         scp.release();
654
655                     func( false, *node_traits::to_value_ptr(pos.pCur), val );
656                     m_Stat.onUpdateExist();
657                     return std::make_pair( true, false );
658                 }
659
660                 if ( !bInsert ) {
661                     scp.release();
662                     return std::make_pair( false, false );
663                 }
664
665                 if ( !bTowerOk ) {
666                     build_node( pNode );
667                     nHeight = pNode->height();
668                     bTowerMade = pNode->has_tower();
669                     bTowerOk = true;
670                 }
671
672                 if ( !insert_at_position( val, pNode, pos, [&func]( value_type& item ) { func( true, item, item ); })) {
673                     m_Stat.onInsertRetry();
674                     continue;
675                 }
676
677                 increase_height( nHeight );
678                 ++m_ItemCounter;
679                 scp.release();
680                 m_Stat.onAddNode( nHeight );
681                 m_Stat.onUpdateNew();
682                 return std::make_pair( true, true );
683             }
684         }
685         //@cond
686         template <typename Func>
687         CDS_DEPRECATED("ensure() is deprecated, use update()")
688         std::pair<bool, bool> ensure( value_type& val, Func func )
689         {
690             return update( val, func, true );
691         }
692         //@endcond
693
694         /// Unlinks the item \p val from the set
695         /**
696             The function searches the item \p val in the set and unlink it from the set
697             if it is found and is equal to \p val.
698
699             Difference between \p erase() and \p %unlink() functions: \p %erase() finds <i>a key</i>
700             and deletes the item found. \p %unlink() finds an item by key and deletes it
701             only if \p val is an item of that set, i.e. the pointer to item found
702             is equal to <tt> &val </tt>.
703
704             The \p disposer specified in \p Traits class template parameter is called
705             by garbage collector \p GC asynchronously.
706
707             The function returns \p true if success and \p false otherwise.
708         */
709         bool unlink( value_type& val )
710         {
711             position pos;
712
713             if ( !find_position( val, pos, key_comparator(), false )) {
714                 m_Stat.onUnlinkFailed();
715                 return false;
716             }
717
718             node_type * pDel = pos.pCur;
719             assert( key_comparator()( *node_traits::to_value_ptr( pDel ), val ) == 0 );
720
721             unsigned int nHeight = pDel->height();
722             typename gc::Guard gDel;
723             gDel.assign( node_traits::to_value_ptr(pDel));
724
725             if ( node_traits::to_value_ptr( pDel ) == &val && try_remove_at( pDel, pos, [](value_type const&) {} )) {
726                 --m_ItemCounter;
727                 m_Stat.onRemoveNode( nHeight );
728                 m_Stat.onUnlinkSuccess();
729                 return true;
730             }
731
732             m_Stat.onUnlinkFailed();
733             return false;
734         }
735
736         /// Extracts the item from the set with specified \p key
737         /** \anchor cds_intrusive_SkipListSet_hp_extract
738             The function searches an item with key equal to \p key in the set,
739             unlinks it from the set, and returns it as \p guarded_ptr object.
740             If \p key is not found the function returns an empty guarded pointer.
741
742             Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
743
744             The \p disposer specified in \p Traits class template parameter is called automatically
745             by garbage collector \p GC specified in class' template parameters when returned \p guarded_ptr object
746             will be destroyed or released.
747             @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
748
749             Usage:
750             \code
751             typedef cds::intrusive::SkipListSet< cds::gc::HP, foo, my_traits >  skip_list;
752             skip_list theList;
753             // ...
754             {
755                 skip_list::guarded_ptr gp(theList.extract( 5 ));
756                 if ( gp ) {
757                     // Deal with gp
758                     // ...
759                 }
760                 // Destructor of gp releases internal HP guard
761             }
762             \endcode
763         */
764         template <typename Q>
765         guarded_ptr extract( Q const& key )
766         {
767             return extract_( key, key_comparator());
768         }
769
770         /// Extracts the item from the set with comparing functor \p pred
771         /**
772             The function is an analog of \ref cds_intrusive_SkipListSet_hp_extract "extract(Q const&)"
773             but \p pred predicate is used for key comparing.
774
775             \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
776             in any order.
777             \p pred must imply the same element order as the comparator used for building the set.
778         */
779         template <typename Q, typename Less>
780         guarded_ptr extract_with( Q const& key, Less pred )
781         {
782             CDS_UNUSED( pred );
783             return extract_( key, cds::opt::details::make_comparator_from_less<Less>());
784         }
785
786         /// Extracts an item with minimal key from the list
787         /**
788             The function searches an item with minimal key, unlinks it, and returns it as \p guarded_ptr object.
789             If the skip-list is empty the function returns an empty guarded pointer.
790
791             @note Due the concurrent nature of the list, the function extracts <i>nearly</i> minimum key.
792             It means that the function gets leftmost item and tries to unlink it.
793             During unlinking, a concurrent thread may insert an item with key less than leftmost item's key.
794             So, the function returns the item with minimum key at the moment of list traversing.
795
796             The \p disposer specified in \p Traits class template parameter is called
797             by garbage collector \p GC automatically when returned \p guarded_ptr object
798             will be destroyed or released.
799             @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
800
801             Usage:
802             \code
803             typedef cds::intrusive::SkipListSet< cds::gc::HP, foo, my_traits >  skip_list;
804             skip_list theList;
805             // ...
806             {
807                 skip_list::guarded_ptr gp(theList.extract_min());
808                 if ( gp ) {
809                     // Deal with gp
810                     //...
811                 }
812                 // Destructor of gp releases internal HP guard
813             }
814             \endcode
815         */
816         guarded_ptr extract_min()
817         {
818             return extract_min_();
819         }
820
821         /// Extracts an item with maximal key from the list
822         /**
823             The function searches an item with maximal key, unlinks it, and returns the pointer to item
824             as \p guarded_ptr object.
825             If the skip-list is empty the function returns an empty \p guarded_ptr.
826
827             @note Due the concurrent nature of the list, the function extracts <i>nearly</i> maximal key.
828             It means that the function gets rightmost item and tries to unlink it.
829             During unlinking, a concurrent thread may insert an item with key greater than rightmost item's key.
830             So, the function returns the item with maximum key at the moment of list traversing.
831
832             The \p disposer specified in \p Traits class template parameter is called
833             by garbage collector \p GC asynchronously when returned \ref guarded_ptr object
834             will be destroyed or released.
835             @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
836
837             Usage:
838             \code
839             typedef cds::intrusive::SkipListSet< cds::gc::HP, foo, my_traits > skip_list;
840             skip_list theList;
841             // ...
842             {
843                 skip_list::guarded_ptr gp( theList.extract_max( gp ));
844                 if ( gp ) {
845                     // Deal with gp
846                     //...
847                 }
848                 // Destructor of gp releases internal HP guard
849             }
850             \endcode
851         */
852         guarded_ptr extract_max()
853         {
854             return extract_max_();
855         }
856
857         /// Deletes the item from the set
858         /** \anchor cds_intrusive_SkipListSet_hp_erase
859             The function searches an item with key equal to \p key in the set,
860             unlinks it from the set, and returns \p true.
861             If the item with key equal to \p key is not found the function return \p false.
862
863             Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
864         */
865         template <typename Q>
866         bool erase( Q const& key )
867         {
868             return erase_( key, key_comparator(), [](value_type const&) {} );
869         }
870
871         /// Deletes the item from the set with comparing functor \p pred
872         /**
873             The function is an analog of \ref cds_intrusive_SkipListSet_hp_erase "erase(Q const&)"
874             but \p pred predicate is used for key comparing.
875
876             \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
877             in any order.
878             \p pred must imply the same element order as the comparator used for building the set.
879         */
880         template <typename Q, typename Less>
881         bool erase_with( Q const& key, Less pred )
882         {
883             CDS_UNUSED( pred );
884             return erase_( key, cds::opt::details::make_comparator_from_less<Less>(), [](value_type const&) {} );
885         }
886
887         /// Deletes the item from the set
888         /** \anchor cds_intrusive_SkipListSet_hp_erase_func
889             The function searches an item with key equal to \p key in the set,
890             call \p f functor with item found, unlinks it from the set, and returns \p true.
891             The \ref disposer specified in \p Traits class template parameter is called
892             by garbage collector \p GC asynchronously.
893
894             The \p Func interface is
895             \code
896             struct functor {
897                 void operator()( value_type const& item );
898             };
899             \endcode
900
901             If the item with key equal to \p key is not found the function return \p false.
902
903             Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
904         */
905         template <typename Q, typename Func>
906         bool erase( Q const& key, Func f )
907         {
908             return erase_( key, key_comparator(), f );
909         }
910
911         /// Deletes the item from the set with comparing functor \p pred
912         /**
913             The function is an analog of \ref cds_intrusive_SkipListSet_hp_erase_func "erase(Q const&, Func)"
914             but \p pred predicate is used for key comparing.
915
916             \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
917             in any order.
918             \p pred must imply the same element order as the comparator used for building the set.
919         */
920         template <typename Q, typename Less, typename Func>
921         bool erase_with( Q const& key, Less pred, Func f )
922         {
923             CDS_UNUSED( pred );
924             return erase_( key, cds::opt::details::make_comparator_from_less<Less>(), f );
925         }
926
927         /// Finds \p key
928         /** \anchor cds_intrusive_SkipListSet_hp_find_func
929             The function searches the item with key equal to \p key and calls the functor \p f for item found.
930             The interface of \p Func functor is:
931             \code
932             struct functor {
933                 void operator()( value_type& item, Q& key );
934             };
935             \endcode
936             where \p item is the item found, \p key is the <tt>find</tt> function argument.
937
938             The functor can change non-key fields of \p item. Note that the functor is only guarantee
939             that \p item cannot be disposed during functor is executing.
940             The functor does not serialize simultaneous access to the set \p item. If such access is
941             possible you must provide your own synchronization on item level to exclude unsafe item modifications.
942
943             Note the compare functor specified for class \p Traits template parameter
944             should accept a parameter of type \p Q that can be not the same as \p value_type.
945
946             The function returns \p true if \p key is found, \p false otherwise.
947         */
948         template <typename Q, typename Func>
949         bool find( Q& key, Func f )
950         {
951             return find_with_( key, key_comparator(), f );
952         }
953         //@cond
954         template <typename Q, typename Func>
955         bool find( Q const& key, Func f )
956         {
957             return find_with_( key, key_comparator(), f );
958         }
959         //@endcond
960
961         /// Finds the key \p key with \p pred predicate for comparing
962         /**
963             The function is an analog of \ref cds_intrusive_SkipListSet_hp_find_func "find(Q&, Func)"
964             but \p pred is used for key compare.
965
966             \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
967             in any order.
968             \p pred must imply the same element order as the comparator used for building the set.
969         */
970         template <typename Q, typename Less, typename Func>
971         bool find_with( Q& key, Less pred, Func f )
972         {
973             CDS_UNUSED( pred );
974             return find_with_( key, cds::opt::details::make_comparator_from_less<Less>(), f );
975         }
976         //@cond
977         template <typename Q, typename Less, typename Func>
978         bool find_with( Q const& key, Less pred, Func f )
979         {
980             CDS_UNUSED( pred );
981             return find_with_( key, cds::opt::details::make_comparator_from_less<Less>(), f );
982         }
983         //@endcond
984
985         /// Checks whether the set contains \p key
986         /**
987             The function searches the item with key equal to \p key
988             and returns \p true if it is found, and \p false otherwise.
989         */
990         template <typename Q>
991         bool contains( Q const& key )
992         {
993             return find_with_( key, key_comparator(), [](value_type& , Q const& ) {} );
994         }
995         //@cond
996         template <typename Q>
997         CDS_DEPRECATED("deprecated, use contains()")
998         bool find( Q const& key )
999         {
1000             return contains( key );
1001         }
1002         //@endcond
1003
1004         /// Checks whether the set contains \p key using \p pred predicate for searching
1005         /**
1006             The function is similar to <tt>contains( key )</tt> but \p pred is used for key comparing.
1007             \p Less functor has the interface like \p std::less.
1008             \p Less must imply the same element order as the comparator used for building the set.
1009         */
1010         template <typename Q, typename Less>
1011         bool contains( Q const& key, Less pred )
1012         {
1013             CDS_UNUSED( pred );
1014             return find_with_( key, cds::opt::details::make_comparator_from_less<Less>(), [](value_type& , Q const& ) {} );
1015         }
1016         //@cond
1017         template <typename Q, typename Less>
1018         CDS_DEPRECATED("deprecated, use contains()")
1019         bool find_with( Q const& key, Less pred )
1020         {
1021             return contains( key, pred );
1022         }
1023         //@endcond
1024
1025         /// Finds \p key and return the item found
1026         /** \anchor cds_intrusive_SkipListSet_hp_get
1027             The function searches the item with key equal to \p key
1028             and returns the pointer to the item found as \p guarded_ptr.
1029             If \p key is not found the function returns an empt guarded pointer.
1030
1031             The \p disposer specified in \p Traits class template parameter is called
1032             by garbage collector \p GC asynchronously when returned \ref guarded_ptr object
1033             will be destroyed or released.
1034             @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
1035
1036             Usage:
1037             \code
1038             typedef cds::intrusive::SkipListSet< cds::gc::HP, foo, my_traits >  skip_list;
1039             skip_list theList;
1040             // ...
1041             {
1042                 skip_list::guarded_ptr gp(theList.get( 5 ));
1043                 if ( gp ) {
1044                     // Deal with gp
1045                     //...
1046                 }
1047                 // Destructor of guarded_ptr releases internal HP guard
1048             }
1049             \endcode
1050
1051             Note the compare functor specified for class \p Traits template parameter
1052             should accept a parameter of type \p Q that can be not the same as \p value_type.
1053         */
1054         template <typename Q>
1055         guarded_ptr get( Q const& key )
1056         {
1057             return get_with_( key, key_comparator());
1058         }
1059
1060         /// Finds \p key and return the item found
1061         /**
1062             The function is an analog of \ref cds_intrusive_SkipListSet_hp_get "get( Q const&)"
1063             but \p pred is used for comparing the keys.
1064
1065             \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
1066             in any order.
1067             \p pred must imply the same element order as the comparator used for building the set.
1068         */
1069         template <typename Q, typename Less>
1070         guarded_ptr get_with( Q const& key, Less pred )
1071         {
1072             CDS_UNUSED( pred );
1073             return get_with_( key, cds::opt::details::make_comparator_from_less<Less>());
1074         }
1075
1076         /// Returns item count in the set
1077         /**
1078             The value returned depends on item counter type provided by \p Traits template parameter.
1079             If it is \p atomicity::empty_item_counter this function always returns 0.
1080             Therefore, the function is not suitable for checking the set emptiness, use \p empty()
1081             for this purpose.
1082         */
1083         size_t size() const
1084         {
1085             return m_ItemCounter;
1086         }
1087
1088         /// Checks if the set is empty
1089         bool empty() const
1090         {
1091             return m_Head.head()->next( 0 ).load( memory_model::memory_order_relaxed ) == nullptr;
1092         }
1093
1094         /// Clears the set (not atomic)
1095         /**
1096             The function unlink all items from the set.
1097             The function is not atomic, i.e., in multi-threaded environment with parallel insertions
1098             this sequence
1099             \code
1100             set.clear();
1101             assert( set.empty());
1102             \endcode
1103             the assertion could be raised.
1104
1105             For each item the \ref disposer will be called after unlinking.
1106         */
1107         void clear()
1108         {
1109             while ( extract_min_());
1110         }
1111
1112         /// Returns maximum height of skip-list. The max height is a constant for each object and does not exceed 32.
1113         static CDS_CONSTEXPR unsigned int max_height() CDS_NOEXCEPT
1114         {
1115             return c_nMaxHeight;
1116         }
1117
1118         /// Returns const reference to internal statistics
1119         stat const& statistics() const
1120         {
1121             return m_Stat;
1122         }
1123
1124     protected:
1125         //@cond
1126         unsigned int random_level()
1127         {
1128             // Random generator produces a number from range [0..31]
1129             // We need a number from range [1..32]
1130             return m_RandomLevelGen() + 1;
1131         }
1132
1133         template <typename Q>
1134         node_type * build_node( Q v )
1135         {
1136             return node_builder::make_tower( v, m_RandomLevelGen );
1137         }
1138
1139         static value_type * gc_protect( marked_node_ptr p )
1140         {
1141             return node_traits::to_value_ptr( p.ptr());
1142         }
1143
1144         static void dispose_node( void* p )
1145         {
1146             assert( p != nullptr );
1147             value_type* pVal = reinterpret_cast<value_type*>( p );
1148             typename node_builder::node_disposer()( node_traits::to_node_ptr( pVal ));
1149             disposer()( pVal );
1150         }
1151
1152         void help_remove( int nLevel, node_type* pPred, marked_node_ptr pCur )
1153         {
1154             if ( pCur->is_upper_level( nLevel )) {
1155                 marked_node_ptr p( pCur.ptr());
1156                 typename gc::Guard hp;
1157                 marked_node_ptr pSucc = hp.protect( pCur->next( nLevel ), gc_protect );
1158
1159                 if ( pSucc.bits() &&
1160                      pPred->next( nLevel ).compare_exchange_strong( p, marked_node_ptr( pSucc.ptr()),
1161                         memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
1162                 {
1163                     if ( pCur->level_unlinked()) {
1164                         gc::retire( node_traits::to_value_ptr( pCur.ptr()), dispose_node );
1165                         m_Stat.onEraseWhileFind();
1166                     }
1167                 }
1168             }
1169         }
1170
1171         template <typename Q, typename Compare >
1172         bool find_position( Q const& val, position& pos, Compare cmp, bool bStopIfFound )
1173         {
1174             node_type * pPred;
1175             marked_node_ptr pSucc;
1176             marked_node_ptr pCur;
1177
1178             // Hazard pointer array:
1179             //  pPred: [nLevel * 2]
1180             //  pSucc: [nLevel * 2 + 1]
1181
1182         retry:
1183             pPred = m_Head.head();
1184             int nCmp = 1;
1185
1186             for ( int nLevel = static_cast<int>( c_nMaxHeight - 1 ); nLevel >= 0; --nLevel ) {
1187                 pos.guards.assign( nLevel * 2, node_traits::to_value_ptr( pPred ));
1188                 while ( true ) {
1189                     pCur = pos.guards.protect( nLevel * 2 + 1, pPred->next( nLevel ), gc_protect );
1190                     if ( pCur.bits()) {
1191                         // pCur.bits() means that pPred is logically deleted
1192                         goto retry;
1193                     }
1194
1195                     if ( pCur.ptr() == nullptr ) {
1196                         // end of list at level nLevel - goto next level
1197                         break;
1198                     }
1199
1200                     // pSucc contains deletion mark for pCur
1201                     pSucc = pCur->next( nLevel ).load( memory_model::memory_order_acquire );
1202
1203                     if ( pPred->next( nLevel ).load( memory_model::memory_order_acquire ).all() != pCur.ptr())
1204                         goto retry;
1205
1206                     if ( pSucc.bits()) {
1207                         // pCur is marked, i.e. logically deleted
1208                         // try to help deleting pCur
1209                         help_remove( nLevel, pPred, pCur );
1210                         goto retry;
1211                     }
1212                     else {
1213                         nCmp = cmp( *node_traits::to_value_ptr( pCur.ptr()), val );
1214                         if ( nCmp < 0 ) {
1215                             pPred = pCur.ptr();
1216                             pos.guards.copy( nLevel * 2, nLevel * 2 + 1 );   // pPrev guard := cur guard
1217                         }
1218                         else if ( nCmp == 0 && bStopIfFound )
1219                             goto found;
1220                         else
1221                             break;
1222                     }
1223                 }
1224
1225                 // Next level
1226                 pos.pPrev[nLevel] = pPred;
1227                 pos.pSucc[nLevel] = pCur.ptr();
1228             }
1229
1230             if ( nCmp != 0 )
1231                 return false;
1232
1233         found:
1234             pos.pCur = pCur.ptr();
1235             return pCur.ptr() && nCmp == 0;
1236         }
1237
1238         bool find_min_position( position& pos )
1239         {
1240             node_type * pPred;
1241             marked_node_ptr pSucc;
1242             marked_node_ptr pCur;
1243
1244             // Hazard pointer array:
1245             //  pPred: [nLevel * 2]
1246             //  pSucc: [nLevel * 2 + 1]
1247
1248         retry:
1249             pPred = m_Head.head();
1250
1251             for ( int nLevel = static_cast<int>( c_nMaxHeight - 1 ); nLevel >= 0; --nLevel ) {
1252                 pos.guards.assign( nLevel * 2, node_traits::to_value_ptr( pPred ));
1253                 pCur = pos.guards.protect( nLevel * 2 + 1, pPred->next( nLevel ), gc_protect );
1254
1255                 // pCur.bits() means that pPred is logically deleted
1256                 // head cannot be deleted
1257                 assert( pCur.bits() == 0 );
1258
1259                 if ( pCur.ptr()) {
1260
1261                     // pSucc contains deletion mark for pCur
1262                     pSucc = pCur->next( nLevel ).load( memory_model::memory_order_acquire );
1263
1264                     if ( pPred->next( nLevel ).load( memory_model::memory_order_acquire ).all() != pCur.ptr())
1265                         goto retry;
1266
1267                     if ( pSucc.bits()) {
1268                         // pCur is marked, i.e. logically deleted.
1269                         // try to help deleting pCur
1270                         help_remove( nLevel, pPred, pCur );
1271                         goto retry;
1272                     }
1273                 }
1274
1275                 // Next level
1276                 pos.pPrev[nLevel] = pPred;
1277                 pos.pSucc[nLevel] = pCur.ptr();
1278             }
1279
1280             return ( pos.pCur = pCur.ptr()) != nullptr;
1281         }
1282
1283         bool find_max_position( position& pos )
1284         {
1285             node_type * pPred;
1286             marked_node_ptr pSucc;
1287             marked_node_ptr pCur;
1288
1289             // Hazard pointer array:
1290             //  pPred: [nLevel * 2]
1291             //  pSucc: [nLevel * 2 + 1]
1292
1293         retry:
1294             pPred = m_Head.head();
1295
1296             for ( int nLevel = static_cast<int>( c_nMaxHeight - 1 ); nLevel >= 0; --nLevel ) {
1297                 pos.guards.assign( nLevel * 2, node_traits::to_value_ptr( pPred ));
1298                 while ( true ) {
1299                     pCur = pos.guards.protect( nLevel * 2 + 1, pPred->next( nLevel ), gc_protect );
1300                     if ( pCur.bits()) {
1301                         // pCur.bits() means that pPred is logically deleted
1302                         goto retry;
1303                     }
1304
1305                     if ( pCur.ptr() == nullptr ) {
1306                         // end of the list at level nLevel - goto next level
1307                         break;
1308                     }
1309
1310                     // pSucc contains deletion mark for pCur
1311                     pSucc = pCur->next( nLevel ).load( memory_model::memory_order_acquire );
1312
1313                     if ( pPred->next( nLevel ).load( memory_model::memory_order_acquire ).all() != pCur.ptr())
1314                         goto retry;
1315
1316                     if ( pSucc.bits()) {
1317                         // pCur is marked, i.e. logically deleted.
1318                         // try to help deleting pCur
1319                         help_remove( nLevel, pPred, pCur );
1320                         goto retry;
1321                     }
1322                     else {
1323                         if ( !pSucc.ptr())
1324                             break;
1325
1326                         pPred = pCur.ptr();
1327                         pos.guards.copy( nLevel * 2, nLevel * 2 + 1 );
1328                     }
1329                 }
1330
1331                 // Next level
1332                 pos.pPrev[nLevel] = pPred;
1333                 pos.pSucc[nLevel] = pCur.ptr();
1334             }
1335
1336             return ( pos.pCur = pCur.ptr()) != nullptr;
1337         }
1338
1339         bool renew_insert_position( value_type& val, node_type * pNode, position& pos )
1340         {
1341             node_type * pPred;
1342             marked_node_ptr pSucc;
1343             marked_node_ptr pCur;
1344             key_comparator cmp;
1345
1346             // Hazard pointer array:
1347             //  pPred: [nLevel * 2]
1348             //  pSucc: [nLevel * 2 + 1]
1349
1350         retry:
1351             pPred = m_Head.head();
1352             int nCmp = 1;
1353
1354             for ( int nLevel = static_cast<int>( c_nMaxHeight - 1 ); nLevel >= 0; --nLevel ) {
1355                 pos.guards.assign( nLevel * 2, node_traits::to_value_ptr( pPred ));
1356                 while ( true ) {
1357                     pCur = pos.guards.protect( nLevel * 2 + 1, pPred->next( nLevel ), gc_protect );
1358                     if ( pCur.bits()) {
1359                         // pCur.bits() means that pPred is logically deleted
1360                         goto retry;
1361                     }
1362
1363                     if ( pCur.ptr() == nullptr ) {
1364                         // end of list at level nLevel - goto next level
1365                         break;
1366                     }
1367
1368                     // pSucc contains deletion mark for pCur
1369                     pSucc = pCur->next( nLevel ).load( memory_model::memory_order_acquire );
1370
1371                     if ( pPred->next( nLevel ).load( memory_model::memory_order_acquire ).all() != pCur.ptr())
1372                         goto retry;
1373
1374                     if ( pSucc.bits()) {
1375                         // pCur is marked, i.e. logically deleted
1376                         if ( pCur.ptr() == pNode ) {
1377                             // Node is removing while we are inserting it
1378                             return false;
1379                         }
1380                         // try to help deleting pCur
1381                         help_remove( nLevel, pPred, pCur );
1382                         goto retry;
1383                     }
1384                     else {
1385                         nCmp = cmp( *node_traits::to_value_ptr( pCur.ptr()), val );
1386                         if ( nCmp < 0 ) {
1387                             pPred = pCur.ptr();
1388                             pos.guards.copy( nLevel * 2, nLevel * 2 + 1 );   // pPrev guard := cur guard
1389                         }
1390                         else
1391                             break;
1392                     }
1393                 }
1394
1395                 // Next level
1396                 pos.pPrev[nLevel] = pPred;
1397                 pos.pSucc[nLevel] = pCur.ptr();
1398             }
1399
1400             return nCmp == 0;
1401         }
1402
1403         template <typename Func>
1404         bool insert_at_position( value_type& val, node_type * pNode, position& pos, Func f )
1405         {
1406             unsigned int const nHeight = pNode->height();
1407
1408             for ( unsigned int nLevel = 1; nLevel < nHeight; ++nLevel )
1409                 pNode->next( nLevel ).store( marked_node_ptr(), memory_model::memory_order_relaxed );
1410
1411             // Insert at level 0
1412             {
1413                 marked_node_ptr p( pos.pSucc[0] );
1414                 pNode->next( 0 ).store( p, memory_model::memory_order_relaxed );
1415                 if ( !pos.pPrev[0]->next( 0 ).compare_exchange_strong( p, marked_node_ptr( pNode ), memory_model::memory_order_release, atomics::memory_order_relaxed ))
1416                     return false;
1417
1418                 f( val );
1419             }
1420
1421             // Insert at level 1..max
1422             for ( unsigned int nLevel = 1; nLevel < nHeight; ++nLevel ) {
1423                 marked_node_ptr p;
1424                 while ( true ) {
1425                     marked_node_ptr pSucc( pos.pSucc[nLevel] );
1426
1427                     // Set pNode->next
1428                     // pNode->next can have "logical deleted" flag if another thread is removing pNode right now
1429                     if ( !pNode->next( nLevel ).compare_exchange_strong( p, pSucc,
1430                         memory_model::memory_order_acq_rel, atomics::memory_order_acquire ))
1431                     {
1432                         // pNode has been marked as removed while we are inserting it
1433                         // Stop inserting
1434                         assert( p.bits() != 0 );
1435
1436                         // Here pNode is linked at least level 0 so level_unlinked() cannot returns true
1437                         CDS_VERIFY_FALSE( pNode->level_unlinked( nHeight - nLevel ));
1438
1439                         // pNode is linked up to nLevel - 1
1440                         // Remove it via find_position()
1441                         find_position( val, pos, key_comparator(), false );
1442
1443                         m_Stat.onLogicDeleteWhileInsert();
1444                         return true;
1445                     }
1446                     p = pSucc;
1447
1448                     // Link pNode into the list at nLevel
1449                     if ( pos.pPrev[nLevel]->next( nLevel ).compare_exchange_strong( pSucc, marked_node_ptr( pNode ),
1450                         memory_model::memory_order_release, atomics::memory_order_relaxed ))
1451                     {
1452                         // go to next level
1453                         break;
1454                     }
1455
1456                     // Renew insert position
1457                     m_Stat.onRenewInsertPosition();
1458
1459                     if ( !renew_insert_position( val, pNode, pos )) {
1460                         // The node has been deleted while we are inserting it
1461                         // Update current height for concurent removing
1462                         CDS_VERIFY_FALSE( pNode->level_unlinked( nHeight - nLevel ));
1463
1464                         m_Stat.onRemoveWhileInsert();
1465
1466                         // help to removing val
1467                         find_position( val, pos, key_comparator(), false );
1468                         return true;
1469                     }
1470                 }
1471             }
1472             return true;
1473         }
1474
1475         template <typename Func>
1476         bool try_remove_at( node_type * pDel, position& pos, Func f )
1477         {
1478             assert( pDel != nullptr );
1479
1480             marked_node_ptr pSucc;
1481             back_off bkoff;
1482
1483             // logical deletion (marking)
1484             for ( unsigned int nLevel = pDel->height() - 1; nLevel > 0; --nLevel ) {
1485                 pSucc = pDel->next( nLevel ).load( memory_model::memory_order_relaxed );
1486                 if ( pSucc.bits() == 0 ) {
1487                     bkoff.reset();
1488                     while ( !( pDel->next( nLevel ).compare_exchange_weak( pSucc, pSucc | 1,
1489                         memory_model::memory_order_release, atomics::memory_order_acquire )
1490                         || pSucc.bits() != 0 ))
1491                     {
1492                         bkoff();
1493                         m_Stat.onMarkFailed();
1494                     }
1495                 }
1496             }
1497
1498             marked_node_ptr p( pDel->next( 0 ).load( memory_model::memory_order_relaxed ).ptr());
1499             while ( true ) {
1500                 if ( pDel->next( 0 ).compare_exchange_strong( p, p | 1, memory_model::memory_order_release, atomics::memory_order_acquire ))
1501                 {
1502                     f( *node_traits::to_value_ptr( pDel ));
1503
1504                     // Physical deletion
1505                     // try fast erase
1506                     p = pDel;
1507
1508                     for ( int nLevel = static_cast<int>( pDel->height() - 1 ); nLevel >= 0; --nLevel ) {
1509
1510                         pSucc = pDel->next( nLevel ).load( memory_model::memory_order_acquire );
1511                         if ( pos.pPrev[nLevel]->next( nLevel ).compare_exchange_strong( p, marked_node_ptr( pSucc.ptr()),
1512                             memory_model::memory_order_acq_rel, atomics::memory_order_relaxed ))
1513                         {
1514                             pDel->level_unlinked();
1515                         }
1516                         else {
1517                             // Make slow erase
1518 #       ifdef CDS_DEBUG
1519                             if ( find_position( *node_traits::to_value_ptr( pDel ), pos, key_comparator(), false ))
1520                                 assert( pDel != pos.pCur );
1521 #       else
1522                             find_position( *node_traits::to_value_ptr( pDel ), pos, key_comparator(), false );
1523 #       endif
1524                             m_Stat.onSlowErase();
1525                             return true;
1526                         }
1527                     }
1528
1529                     // Fast erasing success
1530                     gc::retire( node_traits::to_value_ptr( pDel ), dispose_node );
1531                     m_Stat.onFastErase();
1532                     return true;
1533                 }
1534                 else if ( p.bits()) {
1535                     // Another thread is deleting pDel right now
1536                     m_Stat.onEraseContention();
1537                     return false;
1538                 }
1539                 m_Stat.onEraseRetry();
1540                 bkoff();
1541             }
1542         }
1543
1544         enum finsd_fastpath_result {
1545             find_fastpath_found,
1546             find_fastpath_not_found,
1547             find_fastpath_abort
1548         };
1549         template <typename Q, typename Compare, typename Func>
1550         finsd_fastpath_result find_fastpath( Q& val, Compare cmp, Func f )
1551         {
1552             node_type * pPred;
1553             marked_node_ptr pCur;
1554             marked_node_ptr pNull;
1555
1556             // guard array:
1557             // 0 - pPred on level N
1558             // 1 - pCur on level N
1559             typename gc::template GuardArray<2> guards;
1560             back_off bkoff;
1561             unsigned attempt = 0;
1562
1563         try_again:
1564             pPred = m_Head.head();
1565             for ( int nLevel = static_cast<int>( m_nHeight.load( memory_model::memory_order_relaxed ) - 1 ); nLevel >= 0; --nLevel ) {
1566                 pCur = guards.protect( 1, pPred->next( nLevel ), gc_protect );
1567
1568                 while ( pCur != pNull ) {
1569                     if ( pCur.bits()) {
1570                         // pPred is being removed
1571                         if ( ++attempt < 4 ) {
1572                             bkoff();
1573                             goto try_again;
1574                         }
1575
1576                         return find_fastpath_abort;
1577                     }
1578
1579                     if ( pCur.ptr()) {
1580                         int nCmp = cmp( *node_traits::to_value_ptr( pCur.ptr()), val );
1581                         if ( nCmp < 0 ) {
1582                             guards.copy( 0, 1 );
1583                             pPred = pCur.ptr();
1584                             pCur = guards.protect( 1, pCur->next( nLevel ), gc_protect );
1585                         }
1586                         else if ( nCmp == 0 ) {
1587                             // found
1588                             f( *node_traits::to_value_ptr( pCur.ptr()), val );
1589                             return find_fastpath_found;
1590                         }
1591                         else {
1592                             // pCur > val - go down
1593                             break;
1594                         }
1595                     }
1596                 }
1597             }
1598
1599             return find_fastpath_not_found;
1600         }
1601
1602         template <typename Q, typename Compare, typename Func>
1603         bool find_slowpath( Q& val, Compare cmp, Func f )
1604         {
1605             position pos;
1606             if ( find_position( val, pos, cmp, true )) {
1607                 assert( cmp( *node_traits::to_value_ptr( pos.pCur ), val ) == 0 );
1608
1609                 f( *node_traits::to_value_ptr( pos.pCur ), val );
1610                 return true;
1611             }
1612             else
1613                 return false;
1614         }
1615
1616         template <typename Q, typename Compare, typename Func>
1617         bool find_with_( Q& val, Compare cmp, Func f )
1618         {
1619             switch ( find_fastpath( val, cmp, f )) {
1620             case find_fastpath_found:
1621                 m_Stat.onFindFastSuccess();
1622                 return true;
1623             case find_fastpath_not_found:
1624                 m_Stat.onFindFastFailed();
1625                 return false;
1626             default:
1627                 break;
1628             }
1629
1630             if ( find_slowpath( val, cmp, f )) {
1631                 m_Stat.onFindSlowSuccess();
1632                 return true;
1633             }
1634
1635             m_Stat.onFindSlowFailed();
1636             return false;
1637         }
1638
1639         template <typename Q, typename Compare>
1640         guarded_ptr get_with_( Q const& val, Compare cmp )
1641         {
1642             guarded_ptr gp;
1643             if ( find_with_( val, cmp, [&gp]( value_type& found, Q const& ) { gp.reset( &found ); } ))
1644                 return gp;
1645             return guarded_ptr();
1646         }
1647
1648         template <typename Q, typename Compare, typename Func>
1649         bool erase_( Q const& val, Compare cmp, Func f )
1650         {
1651             position pos;
1652
1653             if ( !find_position( val, pos, cmp, false )) {
1654                 m_Stat.onEraseFailed();
1655                 return false;
1656             }
1657
1658             node_type * pDel = pos.pCur;
1659             typename gc::Guard gDel;
1660             gDel.assign( node_traits::to_value_ptr( pDel ));
1661             assert( cmp( *node_traits::to_value_ptr( pDel ), val ) == 0 );
1662
1663             unsigned int nHeight = pDel->height();
1664             if ( try_remove_at( pDel, pos, f )) {
1665                 --m_ItemCounter;
1666                 m_Stat.onRemoveNode( nHeight );
1667                 m_Stat.onEraseSuccess();
1668                 return true;
1669             }
1670
1671             m_Stat.onEraseFailed();
1672             return false;
1673         }
1674
1675         template <typename Q, typename Compare>
1676         guarded_ptr extract_( Q const& val, Compare cmp )
1677         {
1678             position pos;
1679
1680             guarded_ptr gp;
1681             for (;;) {
1682                 if ( !find_position( val, pos, cmp, false )) {
1683                     m_Stat.onExtractFailed();
1684                     return guarded_ptr();
1685                 }
1686
1687                 node_type * pDel = pos.pCur;
1688                 gp.reset( node_traits::to_value_ptr( pDel ));
1689                 assert( cmp( *node_traits::to_value_ptr( pDel ), val ) == 0 );
1690
1691                 unsigned int nHeight = pDel->height();
1692                 if ( try_remove_at( pDel, pos, []( value_type const& ) {} )) {
1693                     --m_ItemCounter;
1694                     m_Stat.onRemoveNode( nHeight );
1695                     m_Stat.onExtractSuccess();
1696                     return gp;
1697                 }
1698                 m_Stat.onExtractRetry();
1699             }
1700         }
1701
1702         guarded_ptr extract_min_()
1703         {
1704             position pos;
1705
1706             guarded_ptr gp;
1707             for ( ;;) {
1708                 if ( !find_min_position( pos )) {
1709                     // The list is empty
1710                     m_Stat.onExtractMinFailed();
1711                     return guarded_ptr();
1712                 }
1713
1714                 node_type * pDel = pos.pCur;
1715
1716                 unsigned int nHeight = pDel->height();
1717                 gp.reset( node_traits::to_value_ptr( pDel ));
1718
1719                 if ( try_remove_at( pDel, pos, []( value_type const& ) {} )) {
1720                     --m_ItemCounter;
1721                     m_Stat.onRemoveNode( nHeight );
1722                     m_Stat.onExtractMinSuccess();
1723                     return gp;
1724                 }
1725
1726                 m_Stat.onExtractMinRetry();
1727             }
1728         }
1729
1730         guarded_ptr extract_max_()
1731         {
1732             position pos;
1733
1734             guarded_ptr gp;
1735             for ( ;;) {
1736                 if ( !find_max_position( pos )) {
1737                     // The list is empty
1738                     m_Stat.onExtractMaxFailed();
1739                     return guarded_ptr();
1740                 }
1741
1742                 node_type * pDel = pos.pCur;
1743
1744                 unsigned int nHeight = pDel->height();
1745                 gp.reset( node_traits::to_value_ptr( pDel ));
1746
1747                 if ( try_remove_at( pDel, pos, []( value_type const& ) {} )) {
1748                     --m_ItemCounter;
1749                     m_Stat.onRemoveNode( nHeight );
1750                     m_Stat.onExtractMaxSuccess();
1751                     return gp;
1752                 }
1753
1754                 m_Stat.onExtractMaxRetry();
1755             }
1756         }
1757
1758         void increase_height( unsigned int nHeight )
1759         {
1760             unsigned int nCur = m_nHeight.load( memory_model::memory_order_relaxed );
1761             if ( nCur < nHeight )
1762                 m_nHeight.compare_exchange_strong( nCur, nHeight, memory_model::memory_order_relaxed, atomics::memory_order_relaxed );
1763         }
1764
1765         void destroy()
1766         {
1767             node_type* p = m_Head.head()->next( 0 ).load( atomics::memory_order_relaxed ).ptr();
1768             while ( p ) {
1769                 node_type* pNext = p->next( 0 ).load( atomics::memory_order_relaxed ).ptr();
1770                 dispose_node( node_traits::to_value_ptr( p ));
1771                 p = pNext;
1772             }
1773         }
1774
1775         //@endcond
1776
1777     private:
1778         //@cond
1779         skip_list::details::head_node< node_type > m_Head;   ///< head tower (max height)
1780
1781         item_counter                m_ItemCounter;    ///< item counter
1782         random_level_generator      m_RandomLevelGen; ///< random level generator instance
1783         atomics::atomic<unsigned int> m_nHeight;      ///< estimated high level
1784         mutable stat                m_Stat;           ///< internal statistics
1785         //@endcond
1786     };
1787
1788 }} // namespace cds::intrusive
1789
1790
1791 #endif // #ifndef CDSLIB_INTRUSIVE_IMPL_SKIP_LIST_H