cds/intrusive/impl/iterable_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_ITERABLE_LIST_H
  32 #define CDSLIB_INTRUSIVE_IMPL_ITERABLE_LIST_H
  33
  34 #include <cds/intrusive/details/iterable_list_base.h>
  35 #include <cds/details/make_const_type.h>
  36
  37 namespace cds { namespace intrusive {
  38
  39     /// Iterable lock-free ordered single-linked list
  40     /** @ingroup cds_intrusive_list
  41         \anchor cds_intrusive_IterableList_hp
  42
  43         This non-blocking list implementation supports thread-safe iterators;
  44         searching and removing are lock-free, inserting is non-blocking because it
  45         uses a light-weight synchronization based on marked pointers.
  46
  47         Unlike \p cds::intrusive::MichaelList the iterable list does not require
  48         any hook in \p T to be stored in the list.
  49
  50         Usually, ordered single-linked list is used as a building block for the hash table implementation.
  51         Iterable list is suitable for almost append-only hash table because the list doesn't delete
  52         its internal node when erasing a key but it is marked them as empty to be reused in the future.
  53         However, plenty of empty nodes degrades performance.
  54         Separation of internal nodes and user data implies the need for an allocator for internal node
  55         so the iterable list is not fully intrusive. Nevertheless, if you need thread-safe iterator,
  56         the iterable list is good choice.
  57
  58         The complexity of searching is <tt>O(N)</tt>.
  59
  60         Template arguments:
  61         - \p GC - Garbage collector used.
  62         - \p T - type to be stored in the list.
  63         - \p Traits - type traits, default is \p iterable_list::traits. It is possible to declare option-based
  64              list with \p cds::intrusive::iterable_list::make_traits metafunction:
  65             For example, the following traits-based declaration of \p gc::HP iterable list
  66             \code
  67             #include <cds/intrusive/iterable_list_hp.h>
  68             // Declare item stored in your list
  69             struct foo
  70             {
  71                 int nKey;
  72                 // .... other data
  73             };
  74
  75             // Declare comparator for the item
  76             struct my_compare {
  77                 int operator()( foo const& i1, foo const& i2 ) const
  78                 {
  79                     return i1.nKey - i2.nKey;
  80                 }
  81             };
  82
  83             // Declare traits
  84             struct my_traits: public cds::intrusive::iterable_list::traits
  85             {
  86                 typedef my_compare compare;
  87             };
  88
  89             // Declare list
  90             typedef cds::intrusive::IterableList< cds::gc::HP, foo, my_traits > list_type;
  91             \endcode
  92             is equivalent for the following option-based list
  93             \code
  94             #include <cds/intrusive/iterable_list_hp.h>
  95
  96             // foo struct and my_compare are the same
  97
  98             // Declare option-based list
  99             typedef cds::intrusive::IterableList< cds::gc::HP, foo,
 100                 typename cds::intrusive::iterable_list::make_traits<
 101                     cds::intrusive::opt::compare< my_compare >     // item comparator option
 102                 >::type
 103             > option_list_type;
 104             \endcode
 105
 106         \par Usage
 107         There are different specializations of this template for each garbage collecting schema.
 108         You should select GC you want and include appropriate .h-file:
 109         - for \p gc::HP: <tt> <cds/intrusive/iterable_list_hp.h> </tt>
 110         - for \p gc::DHP: <tt> <cds/intrusive/iterable_list_dhp.h> </tt>
 111         - for \ref cds_urcu_gc "RCU type" - see \ref cds_intrusive_IterableList_rcu "RCU-based IterableList"
 112     */
 113     template <
 114         class GC
 115         ,typename T
 116 #ifdef CDS_DOXYGEN_INVOKED
 117         ,class Traits = iterable_list::traits
 118 #else
 119         ,class Traits
 120 #endif
 121     >
 122     class IterableList
 123     {
 124     public:
 125         typedef T       value_type; ///< type of value stored in the list
 126         typedef Traits  traits;     ///< Traits template parameter
 127
 128         typedef iterable_list::node< value_type > node_type; ///< node type
 129
 130 #   ifdef CDS_DOXYGEN_INVOKED
 131         typedef implementation_defined key_comparator  ;    ///< key comparison functor based on opt::compare and opt::less option setter.
 132 #   else
 133         typedef typename opt::details::make_comparator< value_type, traits >::type key_comparator;
 134 #   endif
 135
 136         typedef typename traits::disposer  disposer; ///< disposer for \p value_type
 137
 138         typedef GC  gc;   ///< Garbage collector
 139         typedef typename traits::back_off       back_off;       ///< back-off strategy
 140         typedef typename traits::item_counter   item_counter;   ///< Item counting policy used
 141         typedef typename traits::memory_model   memory_model;   ///< Memory ordering. See \p cds::opt::memory_model option
 142         typedef typename traits::node_allocator node_allocator; ///< Node allocator
 143         typedef typename traits::stat           stat;           ///< Internal statistics
 144
 145         typedef typename gc::template guarded_ptr< value_type > guarded_ptr; ///< Guarded pointer
 146
 147         static CDS_CONSTEXPR const size_t c_nHazardPtrCount = 3; ///< Count of hazard pointer required for the algorithm
 148
 149         //@cond
 150         // Rebind traits (split-list support)
 151         template <typename... Options>
 152         struct rebind_traits {
 153             typedef IterableList<
 154                 gc
 155                 , value_type
 156                 , typename cds::opt::make_options< traits, Options...>::type
 157             > type;
 158         };
 159
 160         // Stat selector
 161         template <typename Stat>
 162         using select_stat_wrapper = iterable_list::select_stat_wrapper< Stat >;
 163         //@endcond
 164
 165     protected:
 166         //@cond
 167         typedef atomics::atomic< node_type* > atomic_node_ptr;  ///< Atomic node pointer
 168         typedef atomic_node_ptr               auxiliary_head;   ///< Auxiliary head type (for split-list support)
 169         typedef typename node_type::marked_data_ptr marked_data_ptr;
 170
 171         node_type       m_Head;
 172         node_type       m_Tail;
 173
 174         item_counter    m_ItemCounter;  ///< Item counter
 175         mutable stat    m_Stat;         ///< Internal statistics
 176
 177         typedef cds::details::Allocator< node_type, node_allocator > cxx_node_allocator;
 178
 179         /// Position pointer for item search
 180         struct position {
 181             node_type const*  pHead;
 182             node_type *       pPrev;  ///< Previous node
 183             node_type *       pCur;   ///< Current node
 184
 185             value_type *      pFound;       ///< Value of \p pCur->data, valid only if data found
 186
 187             typename gc::Guard guard;       ///< guard for \p pFound
 188         };
 189
 190         struct insert_position: public position
 191         {
 192             value_type *        pPrevVal;     ///< Value of \p pPrev->data, can be \p nullptr
 193             typename gc::Guard  prevGuard;   ///< guard for \p pPrevVal
 194         };
 195         //@endcond
 196
 197     protected:
 198         //@cond
 199         template <bool IsConst>
 200         class iterator_type
 201         {
 202             friend class IterableList;
 203
 204         protected:
 205             node_type const*          m_pNode;
 206             typename gc::Guard  m_Guard; // data guard
 207
 208             void next()
 209             {
 210                 for ( node_type* p = m_pNode->next.load( memory_model::memory_order_relaxed ); p != m_pNode; p = p->next.load( memory_model::memory_order_relaxed ))
 211                 {
 212                     m_pNode = p;
 213                     if ( m_Guard.protect( p->data, []( marked_data_ptr p ) { return p.ptr(); }).ptr())
 214                         return;
 215                 }
 216                 m_Guard.clear();
 217             }
 218
 219             explicit iterator_type( node_type const* pNode )
 220                 : m_pNode( pNode )
 221             {
 222                 if ( !m_Guard.protect( pNode->data, []( marked_data_ptr p ) { return p.ptr(); }).ptr())
 223                     next();
 224             }
 225
 226             iterator_type( node_type const* pNode, value_type* pVal )
 227                 : m_pNode( pNode )
 228             {
 229                 if ( m_pNode ) {
 230                     assert( pVal != nullptr );
 231                     m_Guard.assign( pVal );
 232                 }
 233             }
 234
 235         public:
 236             typedef typename cds::details::make_const_type<value_type, IsConst>::pointer   value_ptr;
 237             typedef typename cds::details::make_const_type<value_type, IsConst>::reference value_ref;
 238
 239             iterator_type()
 240                 : m_pNode( nullptr )
 241             {}
 242
 243             iterator_type( iterator_type const& src )
 244                 : m_pNode( src.m_pNode )
 245             {
 246                 m_Guard.copy( src.m_Guard );
 247             }
 248
 249             value_ptr operator ->() const
 250             {
 251                 return m_Guard.template get<value_type>();
 252             }
 253
 254             value_ref operator *() const
 255             {
 256                 assert( m_Guard.get_native() != nullptr );
 257                 return *m_Guard.template get<value_type>();
 258             }
 259
 260             /// Pre-increment
 261             iterator_type& operator ++()
 262             {
 263                 next();
 264                 return *this;
 265             }
 266
 267             iterator_type& operator = (iterator_type const& src)
 268             {
 269                 m_pNode = src.m_pNode;
 270                 m_Guard.copy( src.m_Guard );
 271                 return *this;
 272             }
 273
 274             template <bool C>
 275             bool operator ==(iterator_type<C> const& i ) const
 276             {
 277                 return m_pNode == i.m_pNode;
 278             }
 279             template <bool C>
 280             bool operator !=(iterator_type<C> const& i ) const
 281             {
 282                 return !( *this == i );
 283             }
 284         };
 285         //@endcond
 286
 287     public:
 288     ///@name Thread-safe forward iterators
 289     //@{
 290         /// Forward iterator
 291         /**
 292             The forward iterator for iterable list has some features:
 293             - it has no post-increment operator
 294             - to protect the value, the iterator contains a GC-specific guard.
 295               For some GC (like as \p gc::HP), a guard is a limited resource per thread, so an exception (or assertion) "no free guard"
 296               may be thrown if the limit of guard count per thread is exceeded.
 297             - The iterator cannot be moved across thread boundary since it contains thread-private GC's guard.
 298             - Iterator is thread-safe: even if the element the iterator points to is removed, the iterator stays valid because
 299               it contains the guard keeping the value from to be recycled.
 300
 301             The iterator interface:
 302             \code
 303             class iterator {
 304             public:
 305                 // Default constructor
 306                 iterator();
 307
 308                 // Copy construtor
 309                 iterator( iterator const& src );
 310
 311                 // Dereference operator
 312                 value_type * operator ->() const;
 313
 314                 // Dereference operator
 315                 value_type& operator *() const;
 316
 317                 // Preincrement operator
 318                 iterator& operator ++();
 319
 320                 // Assignment operator
 321                 iterator& operator = (iterator const& src);
 322
 323                 // Equality operators
 324                 bool operator ==(iterator const& i ) const;
 325                 bool operator !=(iterator const& i ) const;
 326             };
 327             \endcode
 328
 329             @note For two iterators pointed to the same element the value can be different;
 330             this code
 331             \code
 332                 if ( it1 == it2 )
 333                     assert( &(*it1) == &(*it2) );
 334             \endcode
 335             can throw assertion. The point is that the iterator stores the value of element which can be modified later by other thread.
 336             The guard inside the iterator prevents recycling that value so the iterator's value remains valid even after such changing.
 337             Other iterator can observe modified value of the element.
 338         */
 339         typedef iterator_type<false>    iterator;
 340         /// Const forward iterator
 341         /**
 342             For iterator's features and requirements see \ref iterator
 343         */
 344         typedef iterator_type<true>     const_iterator;
 345
 346         /// Returns a forward iterator addressing the first element in a list
 347         /**
 348             For empty list \code begin() == end() \endcode
 349         */
 350         iterator begin()
 351         {
 352             return iterator( &m_Head );
 353         }
 354
 355         /// Returns an iterator that addresses the location succeeding the last element in a list
 356         /**
 357             Do not use the value returned by <tt>end</tt> function to access any item.
 358             Internally, <tt>end</tt> returning value equals to \p nullptr.
 359
 360             The returned value can be used only to control reaching the end of the list.
 361             For empty list <tt>begin() == end()</tt>
 362         */
 363         iterator end()
 364         {
 365             return iterator( &m_Tail );
 366         }
 367
 368         /// Returns a forward const iterator addressing the first element in a list
 369         const_iterator cbegin() const
 370         {
 371             return const_iterator( &m_Head );
 372         }
 373
 374         /// Returns a forward const iterator addressing the first element in a list
 375         const_iterator begin() const
 376         {
 377             return const_iterator( &m_Head );
 378         }
 379
 380         /// Returns an const iterator that addresses the location succeeding the last element in a list
 381         const_iterator end() const
 382         {
 383             return const_iterator( &m_Tail );
 384         }
 385
 386         /// Returns an const iterator that addresses the location succeeding the last element in a list
 387         const_iterator cend() const
 388         {
 389             return const_iterator( &m_Tail );
 390         }
 391     //@}
 392
 393     public:
 394         /// Default constructor initializes empty list
 395         IterableList()
 396         {
 397             init_list();
 398         }
 399
 400         //@cond
 401         template <typename Stat, typename = std::enable_if<std::is_same<stat, iterable_list::wrapped_stat<Stat>>::value >>
 402         explicit IterableList( Stat& st )
 403             : m_Stat( st )
 404         {
 405             init_list();
 406         }
 407         //@endcond
 408
 409         /// Destroys the list object
 410         ~IterableList()
 411         {
 412             destroy();
 413         }
 414
 415         /// Inserts new node
 416         /**
 417             The function inserts \p val into the list if the list does not contain
 418             an item with key equal to \p val.
 419
 420             Returns \p true if \p val has been linked to the list, \p false otherwise.
 421         */
 422         bool insert( value_type& val )
 423         {
 424             return insert_at( &m_Head, val );
 425         }
 426
 427         /// Inserts new node
 428         /**
 429             This function is intended for derived non-intrusive containers.
 430
 431             The function allows to split new item creating into two part:
 432             - create item with key only
 433             - insert new item into the list
 434             - if inserting is success, calls  \p f functor to initialize value-field of \p val.
 435
 436             The functor signature is:
 437             \code
 438                 void func( value_type& val );
 439             \endcode
 440             where \p val is the item inserted. User-defined functor \p f should guarantee that during changing
 441             \p val no any other changes could be made on this list's item by concurrent threads.
 442             The user-defined functor is called only if the inserting is success.
 443
 444             @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
 445         */
 446         template <typename Func>
 447         bool insert( value_type& val, Func f )
 448         {
 449             return insert_at( &m_Head, val, f );
 450         }
 451
 452         /// Updates the node
 453         /**
 454             The operation performs inserting or changing data with lock-free manner.
 455
 456             If the item \p val is not found in the list, then \p val is inserted
 457             iff \p bInsert is \p true.
 458             Otherwise, the current element is changed to \p val, the element will be retired later
 459             by call \p Traits::disposer.
 460             The functor \p func is called after inserting or replacing, it signature is:
 461             \code
 462                 void func( value_type& val, value_type * old );
 463             \endcode
 464             where
 465             - \p val - argument \p val passed into the \p %update() function
 466             - \p old - old value that will be retired. If new item has been inserted then \p old is \p nullptr.
 467
 468             Returns std::pair<bool, bool> where \p first is \p true if operation is successful,
 469             \p second is \p true if \p val has been added or \p false if the item with that key
 470             already in the list.
 471         */
 472         template <typename Func>
 473         std::pair<bool, bool> update( value_type& val, Func func, bool bInsert = true )
 474         {
 475             return update_at( &m_Head, val, func, bInsert );
 476         }
 477
 478         /// Insert or update
 479         /**
 480             The operation performs inserting or updating data with lock-free manner.
 481
 482             If the item \p val is not found in the list, then \p val is inserted
 483             iff \p bInsert is \p true.
 484             Otherwise, the current element is changed to \p val, the old element will be retired later
 485             by call \p Traits::disposer.
 486
 487             Returns std::pair<bool, bool> where \p first is \p true if operation is successful,
 488             \p second is \p true if \p val has been added or \p false if the item with that key
 489             already in the list.
 490         */
 491         std::pair<bool, bool> upsert( value_type& val, bool bInsert = true )
 492         {
 493             return upsert_at( &m_Head, val, bInsert );
 494         }
 495
 496         /// Unlinks the item \p val from the list
 497         /**
 498             The function searches the item \p val in the list and unlinks it from the list
 499             if it is found and it is equal to \p val.
 500
 501             Difference between \p erase() and \p %unlink(): \p %erase() finds <i>a key</i>
 502             and deletes the item found. \p %unlink() finds an item by key and deletes it
 503             only if \p val is an item of the list, i.e. the pointer to item found
 504             is equal to <tt> &val </tt>.
 505
 506             \p disposer specified in \p Traits is called for deleted item.
 507
 508             The function returns \p true if success and \p false otherwise.
 509         */
 510         bool unlink( value_type& val )
 511         {
 512             return unlink_at( &m_Head, val );
 513         }
 514
 515         /// Deletes the item from the list
 516         /** \anchor cds_intrusive_IterableList_hp_erase_val
 517             The function searches an item with key equal to \p key in the list,
 518             unlinks it from the list, and returns \p true.
 519             If \p key is not found the function return \p false.
 520
 521             \p disposer specified in \p Traits is called for deleted item.
 522         */
 523         template <typename Q>
 524         bool erase( Q const& key )
 525         {
 526             return erase_at( &m_Head, key, key_comparator());
 527         }
 528
 529         /// Deletes the item from the list using \p pred predicate for searching
 530         /**
 531             The function is an analog of \ref cds_intrusive_IterableList_hp_erase_val "erase(Q const&)"
 532             but \p pred is used for key comparing.
 533             \p Less functor has the interface like \p std::less.
 534             \p pred must imply the same element order as the comparator used for building the list.
 535
 536             \p disposer specified in \p Traits is called for deleted item.
 537         */
 538         template <typename Q, typename Less>
 539         bool erase_with( Q const& key, Less pred )
 540         {
 541             CDS_UNUSED( pred );
 542             return erase_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>());
 543         }
 544
 545         /// Deletes the item from the list
 546         /** \anchor cds_intrusive_IterableList_hp_erase_func
 547             The function searches an item with key equal to \p key in the list,
 548             call \p func functor with item found, unlinks it from the list, and returns \p true.
 549             The \p Func interface is
 550             \code
 551             struct functor {
 552                 void operator()( value_type const& item );
 553             };
 554             \endcode
 555             If \p key is not found the function return \p false, \p func is not called.
 556
 557             \p disposer specified in \p Traits is called for deleted item.
 558         */
 559         template <typename Q, typename Func>
 560         bool erase( Q const& key, Func func )
 561         {
 562             return erase_at( &m_Head, key, key_comparator(), func );
 563         }
 564
 565         /// Deletes the item from the list using \p pred predicate for searching
 566         /**
 567             The function is an analog of \ref cds_intrusive_IterableList_hp_erase_func "erase(Q const&, Func)"
 568             but \p pred is used for key comparing.
 569             \p Less functor has the interface like \p std::less.
 570             \p pred must imply the same element order as the comparator used for building the list.
 571
 572             \p disposer specified in \p Traits is called for deleted item.
 573         */
 574         template <typename Q, typename Less, typename Func>
 575         bool erase_with( Q const& key, Less pred, Func f )
 576         {
 577             CDS_UNUSED( pred );
 578             return erase_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>(), f );
 579         }
 580
 581         /// Extracts the item from the list with specified \p key
 582         /** \anchor cds_intrusive_IterableList_hp_extract
 583             The function searches an item with key equal to \p key,
 584             unlinks it from the list, and returns it as \p guarded_ptr.
 585             If \p key is not found returns an empty guarded pointer.
 586
 587             Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
 588
 589             The \ref disposer specified in \p Traits class template parameter is called automatically
 590             by garbage collector \p GC when returned \ref guarded_ptr object will be destroyed or released.
 591             @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
 592
 593             Usage:
 594             \code
 595             typedef cds::intrusive::IterableList< cds::gc::HP, foo, my_traits >  ord_list;
 596             ord_list theList;
 597             // ...
 598             {
 599                 ord_list::guarded_ptr gp( theList.extract( 5 ));
 600                 if ( gp ) {
 601                     // Deal with gp
 602                     // ...
 603                 }
 604                 // Destructor of gp releases internal HP guard
 605             }
 606             \endcode
 607         */
 608         template <typename Q>
 609         guarded_ptr extract( Q const& key )
 610         {
 611             return extract_at( &m_Head, key, key_comparator());
 612         }
 613
 614         /// Extracts the item using compare functor \p pred
 615         /**
 616             The function is an analog of \ref cds_intrusive_IterableList_hp_extract "extract(Q const&)"
 617             but \p pred predicate is used for key comparing.
 618
 619             \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
 620             in any order.
 621             \p pred must imply the same element order as the comparator used for building the list.
 622         */
 623         template <typename Q, typename Less>
 624         guarded_ptr extract_with( Q const& key, Less pred )
 625         {
 626             CDS_UNUSED( pred );
 627             return extract_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>());
 628         }
 629
 630         /// Finds \p key in the list
 631         /** \anchor cds_intrusive_IterableList_hp_find_func
 632             The function searches the item with key equal to \p key and calls the functor \p f for item found.
 633             The interface of \p Func functor is:
 634             \code
 635             struct functor {
 636                 void operator()( value_type& item, Q& key );
 637             };
 638             \endcode
 639             where \p item is the item found, \p key is the \p %find() function argument.
 640
 641             The functor may change non-key fields of \p item. Note that the function is only guarantee
 642             that \p item cannot be disposed during functor is executing.
 643             The function does not serialize simultaneous access to the \p item. If such access is
 644             possible you must provide your own synchronization schema to keep out unsafe item modifications.
 645
 646             The function returns \p true if \p val is found, \p false otherwise.
 647         */
 648         template <typename Q, typename Func>
 649         bool find( Q& key, Func f ) const
 650         {
 651             return find_at( &m_Head, key, key_comparator(), f );
 652         }
 653         //@cond
 654         template <typename Q, typename Func>
 655         bool find( Q const& key, Func f ) const
 656         {
 657             return find_at( &m_Head, key, key_comparator(), f );
 658         }
 659         //@endcond
 660
 661         /// Finds \p key in the list and returns iterator pointed to the item found
 662         /**
 663             If \p key is not found the function returns \p end().
 664         */
 665         template <typename Q>
 666         iterator find( Q const& key ) const
 667         {
 668             return find_iterator_at( &m_Head, key, key_comparator());
 669         }
 670
 671         /// Finds the \p key using \p pred predicate for searching
 672         /**
 673             The function is an analog of \ref cds_intrusive_IterableList_hp_find_func "find(Q&, Func)"
 674             but \p pred is used for key comparing.
 675             \p Less functor has the interface like \p std::less.
 676             \p pred must imply the same element order as the comparator used for building the list.
 677         */
 678         template <typename Q, typename Less, typename Func>
 679         bool find_with( Q& key, Less pred, Func f ) const
 680         {
 681             CDS_UNUSED( pred );
 682             return find_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>(), f );
 683         }
 684         //@cond
 685         template <typename Q, typename Less, typename Func>
 686         bool find_with( Q const& key, Less pred, Func f ) const
 687         {
 688             CDS_UNUSED( pred );
 689             return find_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>(), f );
 690         }
 691         //@endcond
 692
 693         /// Finds \p key in the list using \p pred predicate for searching and returns iterator pointed to the item found
 694         /**
 695             The function is an analog of \p find(Q&) but \p pred is used for key comparing.
 696             \p Less functor has the interface like \p std::less.
 697             \p pred must imply the same element order as the comparator used for building the list.
 698
 699             If \p key is not found the function returns \p end().
 700         */
 701         template <typename Q, typename Less>
 702         iterator find_with( Q const& key, Less pred ) const
 703         {
 704             CDS_UNUSED( pred );
 705             return find_iterator_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>());
 706         }
 707
 708         /// Checks whether the list contains \p key
 709         /**
 710             The function searches the item with key equal to \p key
 711             and returns \p true if it is found, and \p false otherwise.
 712         */
 713         template <typename Q>
 714         bool contains( Q const& key ) const
 715         {
 716             return find_at( &m_Head, key, key_comparator());
 717         }
 718
 719         /// Checks whether the list contains \p key using \p pred predicate for searching
 720         /**
 721             The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
 722             \p Less functor has the interface like \p std::less.
 723             \p Less must imply the same element order as the comparator used for building the list.
 724         */
 725         template <typename Q, typename Less>
 726         bool contains( Q const& key, Less pred ) const
 727         {
 728             CDS_UNUSED( pred );
 729             return find_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>());
 730         }
 731
 732         /// Finds the \p key and return the item found
 733         /** \anchor cds_intrusive_IterableList_hp_get
 734             The function searches the item with key equal to \p key
 735             and returns it as \p guarded_ptr.
 736             If \p key is not found the function returns an empty guarded pointer.
 737
 738             The \ref disposer specified in \p Traits class template parameter is called
 739             by garbage collector \p GC automatically when returned \ref guarded_ptr object
 740             will be destroyed or released.
 741             @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
 742
 743             Usage:
 744             \code
 745             typedef cds::intrusive::IterableList< cds::gc::HP, foo, my_traits >  ord_list;
 746             ord_list theList;
 747             // ...
 748             {
 749                 ord_list::guarded_ptr gp(theList.get( 5 ));
 750                 if ( gp ) {
 751                     // Deal with gp
 752                     //...
 753                 }
 754                 // Destructor of guarded_ptr releases internal HP guard
 755             }
 756             \endcode
 757
 758             Note the compare functor specified for \p Traits template parameter
 759             should accept a parameter of type \p Q that can be not the same as \p value_type.
 760         */
 761         template <typename Q>
 762         guarded_ptr get( Q const& key ) const
 763         {
 764             return get_at( &m_Head, key, key_comparator());
 765         }
 766
 767         /// Finds the \p key and return the item found
 768         /**
 769             The function is an analog of \ref cds_intrusive_IterableList_hp_get "get( Q const&)"
 770             but \p pred is used for comparing the keys.
 771
 772             \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
 773             in any order.
 774             \p pred must imply the same element order as the comparator used for building the list.
 775         */
 776         template <typename Q, typename Less>
 777         guarded_ptr get_with( Q const& key, Less pred ) const
 778         {
 779             CDS_UNUSED( pred );
 780             return get_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>());
 781         }
 782
 783         /// Clears the list (thread safe, not atomic)
 784         void clear()
 785         {
 786             position pos;
 787             pos.pPrev = nullptr;
 788             for ( pos.pCur = m_Head.next.load( memory_model::memory_order_relaxed ); pos.pCur != pos.pPrev; pos.pCur = pos.pCur->next.load( memory_model::memory_order_relaxed )) {
 789                 while ( true ) {
 790                     pos.pFound = pos.guard.protect( pos.pCur->data, []( marked_data_ptr p ) { return p.ptr(); }).ptr();
 791                     if ( !pos.pFound )
 792                         break;
 793                     if ( cds_likely( unlink_data( pos ))) {
 794                         --m_ItemCounter;
 795                         break;
 796                     }
 797                 }
 798                 pos.pPrev = pos.pCur;
 799             }
 800         }
 801
 802         /// Checks if the list is empty
 803         /**
 804             Emptiness is checked by item counting: if item count is zero then the set is empty.
 805             Thus, if you need to use \p %empty() you should provide appropriate (non-empty) \p iterable_list::traits::item_counter
 806             feature.
 807         */
 808         bool empty() const
 809         {
 810             return size() == 0;
 811         }
 812
 813         /// Returns list's item count
 814         /**
 815             The value returned depends on item counter provided by \p iterable_list::traits::item_counter. For \p atomicity::empty_item_counter,
 816             this function always returns 0.
 817         */
 818         size_t size() const
 819         {
 820             return m_ItemCounter.value();
 821         }
 822
 823         /// Returns const reference to internal statistics
 824         stat const& statistics() const
 825         {
 826             return m_Stat;
 827         }
 828
 829     protected:
 830         //@cond
 831
 832         // split-list support
 833         bool insert_aux_node( node_type * pNode )
 834         {
 835             return insert_aux_node( &m_Head, pNode );
 836         }
 837
 838         // split-list support
 839         bool insert_aux_node( node_type* pHead, node_type * pNode )
 840         {
 841             assert( pNode != nullptr );
 842             assert( pNode->data.load( memory_model::memory_order_relaxed ) != nullptr );
 843
 844             insert_position pos;
 845
 846             while ( true ) {
 847                 if ( inserting_search( pHead, *pNode->data.load(memory_model::memory_order_relaxed).ptr(), pos, key_comparator() ) ) {
 848                     m_Stat.onInsertFailed();
 849                     return false;
 850                 }
 851
 852                 if ( link_aux_node( pNode, pos ) ) {
 853                     ++m_ItemCounter;
 854                     m_Stat.onInsertSuccess();
 855                     return true;
 856                 }
 857
 858                 m_Stat.onInsertRetry();
 859             }
 860         }
 861
 862         bool insert_at( node_type* pHead, value_type& val )
 863         {
 864             insert_position pos;
 865
 866             while ( true ) {
 867                 if ( inserting_search( pHead, val, pos, key_comparator() )) {
 868                     m_Stat.onInsertFailed();
 869                     return false;
 870                 }
 871
 872                 if ( link_data( &val, pos ) ) {
 873                     ++m_ItemCounter;
 874                     m_Stat.onInsertSuccess();
 875                     return true;
 876                 }
 877
 878                 m_Stat.onInsertRetry();
 879             }
 880         }
 881
 882         template <typename Func>
 883         bool insert_at( node_type* pHead, value_type& val, Func f )
 884         {
 885             insert_position pos;
 886
 887             typename gc::Guard guard;
 888             guard.assign( &val );
 889
 890             while ( true ) {
 891                 if ( inserting_search( pHead, val, pos, key_comparator() ) ) {
 892                     m_Stat.onInsertFailed();
 893                     return false;
 894                 }
 895
 896                 if ( link_data( &val, pos ) ) {
 897                     f( val );
 898                     ++m_ItemCounter;
 899                     m_Stat.onInsertSuccess();
 900                     return true;
 901                 }
 902
 903                 m_Stat.onInsertRetry();
 904             }
 905         }
 906
 907         template <typename Func>
 908         std::pair<bool, bool> update_at( node_type* pHead, value_type& val, Func func, bool bInsert )
 909         {
 910             insert_position pos;
 911
 912             typename gc::Guard guard;
 913             guard.assign( &val );
 914
 915             while ( true ) {
 916                 if ( inserting_search( pHead, val, pos, key_comparator() ) ) {
 917                     // try to replace pCur->data with val
 918                     assert( pos.pFound != nullptr );
 919                     assert( key_comparator()(*pos.pFound, val) == 0 );
 920
 921                     marked_data_ptr pFound( pos.pFound );
 922                     if ( cds_likely( pos.pCur->data.compare_exchange_strong( pFound, marked_data_ptr( &val ),
 923                             memory_model::memory_order_release, atomics::memory_order_relaxed )))
 924                     {
 925                         if ( pos.pFound != &val ) {
 926                             retire_data( pos.pFound );
 927                             func( val, pos.pFound );
 928                         }
 929                         m_Stat.onUpdateExisting();
 930                         return std::make_pair( true, false );
 931                     }
 932                 }
 933                 else {
 934                     if ( !bInsert ) {
 935                         m_Stat.onUpdateFailed();
 936                         return std::make_pair( false, false );
 937                     }
 938
 939                     if ( link_data( &val, pos )) {
 940                         func( val, static_cast<value_type*>( nullptr ));
 941                         ++m_ItemCounter;
 942                         m_Stat.onUpdateNew();
 943                         return std::make_pair( true, true );
 944                     }
 945                 }
 946
 947                 m_Stat.onUpdateRetry();
 948             }
 949         }
 950
 951         std::pair<bool, bool> upsert_at( node_type* pHead, value_type& val, bool bInsert )
 952         {
 953             return update_at( pHead, val, []( value_type&, value_type* ) {}, bInsert );
 954         }
 955
 956         bool unlink_at( node_type* pHead, value_type& val )
 957         {
 958             position pos;
 959
 960             back_off bkoff;
 961             while ( search( pHead, val, pos, key_comparator())) {
 962                 if ( pos.pFound == &val ) {
 963                     if ( unlink_data( pos )) {
 964                         --m_ItemCounter;
 965                         m_Stat.onEraseSuccess();
 966                         return true;
 967                     }
 968                     else
 969                         bkoff();
 970                 }
 971                 else
 972                     break;
 973
 974                 m_Stat.onEraseRetry();
 975             }
 976
 977             m_Stat.onEraseFailed();
 978             return false;
 979         }
 980
 981         template <typename Q, typename Compare, typename Func>
 982         bool erase_at( node_type* pHead, const Q& val, Compare cmp, Func f, position& pos )
 983         {
 984             back_off bkoff;
 985             while ( search( pHead, val, pos, cmp )) {
 986                 if ( unlink_data( pos )) {
 987                     f( *pos.pFound );
 988                     --m_ItemCounter;
 989                     m_Stat.onEraseSuccess();
 990                     return true;
 991                 }
 992                 else
 993                     bkoff();
 994
 995                 m_Stat.onEraseRetry();
 996             }
 997
 998             m_Stat.onEraseFailed();
 999             return false;
1000         }
1001
1002         template <typename Q, typename Compare, typename Func>
1003         bool erase_at( node_type* pHead, const Q& val, Compare cmp, Func f )
1004         {
1005             position pos;
1006             return erase_at( pHead, val, cmp, f, pos );
1007         }
1008
1009         template <typename Q, typename Compare>
1010         bool erase_at( node_type* pHead, Q const& val, Compare cmp )
1011         {
1012             position pos;
1013             return erase_at( pHead, val, cmp, [](value_type const&){}, pos );
1014         }
1015
1016         template <typename Q, typename Compare>
1017         guarded_ptr extract_at( node_type* pHead, Q const& val, Compare cmp )
1018         {
1019             position pos;
1020             back_off bkoff;
1021             while ( search( pHead, val, pos, cmp )) {
1022                 if ( unlink_data( pos )) {
1023                     --m_ItemCounter;
1024                     m_Stat.onEraseSuccess();
1025                     assert( pos.pFound != nullptr );
1026                     return guarded_ptr( std::move( pos.guard ));
1027                 }
1028                 else
1029                     bkoff();
1030
1031                 m_Stat.onEraseRetry();
1032             }
1033
1034             m_Stat.onEraseFailed();
1035             return guarded_ptr();
1036         }
1037
1038         template <typename Q, typename Compare>
1039         bool find_at( node_type const* pHead, Q const& val, Compare cmp ) const
1040         {
1041             position pos;
1042             if ( search( pHead, val, pos, cmp ) ) {
1043                 m_Stat.onFindSuccess();
1044                 return true;
1045             }
1046
1047             m_Stat.onFindFailed();
1048             return false;
1049         }
1050
1051         template <typename Q, typename Compare, typename Func>
1052         bool find_at( node_type const* pHead, Q& val, Compare cmp, Func f ) const
1053         {
1054             position pos;
1055             if ( search( pHead, val, pos, cmp )) {
1056                 assert( pos.pFound != nullptr );
1057                 f( *pos.pFound, val );
1058                 m_Stat.onFindSuccess();
1059                 return true;
1060             }
1061
1062             m_Stat.onFindFailed();
1063             return false;
1064         }
1065
1066         template <typename Q, typename Compare>
1067         iterator find_iterator_at( node_type const* pHead, Q const& val, Compare cmp ) const
1068         {
1069             position pos;
1070             if ( search( pHead, val, pos, cmp )) {
1071                 assert( pos.pCur != nullptr );
1072                 assert( pos.pFound != nullptr );
1073                 m_Stat.onFindSuccess();
1074                 return iterator( pos.pCur, pos.pFound );
1075             }
1076
1077             m_Stat.onFindFailed();
1078             return iterator( &m_Tail );
1079         }
1080
1081         template <typename Q, typename Compare>
1082         guarded_ptr get_at( node_type const* pHead, Q const& val, Compare cmp ) const
1083         {
1084             position pos;
1085             if ( search( pHead, val, pos, cmp )) {
1086                 m_Stat.onFindSuccess();
1087                 return guarded_ptr( std::move( pos.guard ));
1088             }
1089
1090             m_Stat.onFindFailed();
1091             return guarded_ptr();
1092         }
1093
1094         node_type* head()
1095         {
1096             return &m_Head;
1097         }
1098
1099         node_type const* head() const
1100         {
1101             return &m_Head;
1102         }
1103         //@endcond
1104
1105     protected:
1106         //@cond
1107         template <typename Q, typename Compare >
1108         bool search( node_type const* pHead, Q const& val, position& pos, Compare cmp ) const
1109         {
1110             pos.pHead = pHead;
1111             node_type*  pPrev = const_cast<node_type*>( pHead );
1112
1113             while ( true ) {
1114                 node_type * pCur = pPrev->next.load( memory_model::memory_order_relaxed );
1115
1116                 if ( pCur == pCur->next.load( memory_model::memory_order_acquire )) {
1117                     // end-of-list
1118                     pos.pPrev = pPrev;
1119                     pos.pCur = pCur;
1120                     pos.pFound = nullptr;
1121                     return false;
1122                 }
1123
1124                 value_type * pVal = pos.guard.protect( pCur->data,
1125                     []( marked_data_ptr p ) -> value_type*
1126                     {
1127                         return p.ptr();
1128                     }).ptr();
1129
1130                 if ( pVal ) {
1131                     int const nCmp = cmp( *pVal, val );
1132                     if ( nCmp >= 0 ) {
1133                         pos.pPrev = pPrev;
1134                         pos.pCur = pCur;
1135                         pos.pFound = pVal;
1136                         return nCmp == 0;
1137                     }
1138                 }
1139
1140                 pPrev = pCur;
1141             }
1142         }
1143
1144         template <typename Q, typename Compare >
1145         bool inserting_search( node_type const* pHead, Q const& val, insert_position& pos, Compare cmp ) const
1146         {
1147             pos.pHead = pHead;
1148             node_type*  pPrev = const_cast<node_type*>(pHead);
1149             value_type* pPrevVal = pPrev->data.load( memory_model::memory_order_relaxed ).ptr();
1150
1151             while ( true ) {
1152                 node_type * pCur = pPrev->next.load( memory_model::memory_order_relaxed );
1153
1154                 if ( pCur == pCur->next.load( memory_model::memory_order_acquire )) {
1155                     // end-of-list
1156                     pos.pPrev = pPrev;
1157                     pos.pCur = pCur;
1158                     pos.pFound = nullptr;
1159                     pos.pPrevVal = pPrevVal;
1160                     return false;
1161                 }
1162
1163                 value_type * pVal = pos.guard.protect( pCur->data,
1164                     []( marked_data_ptr p ) -> value_type*
1165                 {
1166                     return p.ptr();
1167                 } ).ptr();
1168
1169                 if ( pVal ) {
1170                     int const nCmp = cmp( *pVal, val );
1171                     if ( nCmp >= 0 ) {
1172                         pos.pPrev = pPrev;
1173                         pos.pCur = pCur;
1174                         pos.pFound = pVal;
1175                         pos.pPrevVal = pPrevVal;
1176                         return nCmp == 0;
1177                     }
1178                 }
1179
1180                 pPrev = pCur;
1181                 pPrevVal = pVal;
1182                 pos.prevGuard.copy( pos.guard );
1183             }
1184         }
1185
1186         // split-list support
1187         template <typename Predicate>
1188         void destroy( Predicate pred )
1189         {
1190             node_type * pNode = m_Head.next.load( memory_model::memory_order_relaxed );
1191             while ( pNode != pNode->next.load( memory_model::memory_order_relaxed ) ) {
1192                 value_type * pVal = pNode->data.load( memory_model::memory_order_relaxed ).ptr();
1193                 node_type * pNext = pNode->next.load( memory_model::memory_order_relaxed );
1194                 bool const is_regular_node = !pVal || pred( pVal );
1195                 if ( is_regular_node ) {
1196                     if ( pVal )
1197                         retire_data( pVal );
1198                     delete_node( pNode );
1199                 }
1200                 pNode = pNext;
1201             }
1202
1203             m_Head.next.store( &m_Tail, memory_model::memory_order_relaxed );
1204         }
1205         //@endcond
1206
1207     private:
1208         //@cond
1209         void init_list()
1210         {
1211             m_Head.next.store( &m_Tail, memory_model::memory_order_relaxed );
1212             // end-of-list mark: node.next == node
1213             m_Tail.next.store( &m_Tail, memory_model::memory_order_release );
1214         }
1215
1216         node_type * alloc_node( value_type * pVal )
1217         {
1218             m_Stat.onNodeCreated();
1219             return cxx_node_allocator().New( pVal );
1220         }
1221
1222         void delete_node( node_type * pNode )
1223         {
1224             m_Stat.onNodeRemoved();
1225             cxx_node_allocator().Delete( pNode );
1226         }
1227
1228         static void retire_data( value_type * pVal )
1229         {
1230             assert( pVal != nullptr );
1231             gc::template retire<disposer>( pVal );
1232         }
1233
1234         void destroy()
1235         {
1236             node_type * pNode = m_Head.next.load( memory_model::memory_order_relaxed );
1237             while ( pNode != pNode->next.load( memory_model::memory_order_relaxed )) {
1238                 value_type * pVal = pNode->data.load( memory_model::memory_order_relaxed ).ptr();
1239                 if ( pVal )
1240                     retire_data( pVal );
1241                 node_type * pNext = pNode->next.load( memory_model::memory_order_relaxed );
1242                 delete_node( pNode );
1243                 pNode = pNext;
1244             }
1245         }
1246
1247         bool link_data( value_type * pVal, insert_position& pos )
1248         {
1249             assert( pos.pPrev != nullptr );
1250             assert( pos.pCur != nullptr );
1251
1252             // We need pos.pCur data should be unchanged, otherwise ordering violation can be possible
1253             // if current thread will be preempted and another thread will delete pos.pCur data
1254             // and then set it to another.
1255             // To prevent this we mark pos.pCur data as undeletable by setting LSB
1256             marked_data_ptr valCur( pos.pFound );
1257             if ( !pos.pCur->data.compare_exchange_strong( valCur, valCur | 1, memory_model::memory_order_acquire, atomics::memory_order_relaxed ) ) {
1258                 // oops, pos.pCur data has been changed or another thread is setting pos.pPrev data
1259                 m_Stat.onNodeMarkFailed();
1260                 return false;
1261             }
1262
1263             marked_data_ptr valPrev( pos.pPrevVal );
1264             if ( !pos.pPrev->data.compare_exchange_strong( valPrev, valPrev | 1, memory_model::memory_order_acquire, atomics::memory_order_relaxed ) ) {
1265                 pos.pCur->data.store( valCur, memory_model::memory_order_relaxed );
1266                 m_Stat.onNodeMarkFailed();
1267                 return false;
1268             }
1269
1270             // checks if link pPrev -> pCur is broken
1271             if ( pos.pPrev->next.load( memory_model::memory_order_acquire ) != pos.pCur ) {
1272                 // sequence pPrev - pCur is broken
1273                 pos.pPrev->data.store( valPrev, memory_model::memory_order_relaxed );
1274                 pos.pCur->data.store( valCur, memory_model::memory_order_relaxed );
1275                 m_Stat.onNodeSeqBreak();
1276                 return false;
1277             }
1278
1279             if ( pos.pPrev != pos.pHead && pos.pPrevVal == nullptr )
1280             {
1281                 // reuse pPrev
1282
1283                 // Set pos.pPrev data if it is null
1284                 valPrev |= 1;
1285                 bool result = pos.pPrev->data.compare_exchange_strong( valPrev, marked_data_ptr( pVal ),
1286                     memory_model::memory_order_release, atomics::memory_order_relaxed );
1287
1288                 // Clears data marks
1289                 pos.pCur->data.store( valCur, memory_model::memory_order_relaxed );
1290
1291                 if ( result ) {
1292                     m_Stat.onReuseNode();
1293                     return result;
1294                 }
1295             }
1296             else {
1297                 // insert new node between pos.pPrev and pos.pCur
1298                 node_type * pNode = alloc_node( pVal );
1299                 pNode->next.store( pos.pCur, memory_model::memory_order_relaxed );
1300
1301                 bool result = pos.pPrev->next.compare_exchange_strong( pos.pCur, pNode, memory_model::memory_order_release, atomics::memory_order_relaxed );
1302
1303                 // Clears data marks
1304                 pos.pPrev->data.store( valPrev, memory_model::memory_order_relaxed );
1305                 pos.pCur->data.store( valCur, memory_model::memory_order_relaxed );
1306
1307                 if ( result ) {
1308                     m_Stat.onNewNodeCreated();
1309                     return result;
1310                 }
1311
1312                 delete_node( pNode );
1313             }
1314
1315             return false;
1316         }
1317
1318         // split-list support
1319         bool link_aux_node( node_type * pNode, insert_position& pos )
1320         {
1321             assert( pos.pPrev != nullptr );
1322             assert( pos.pCur != nullptr );
1323
1324             // We need pos.pCur data should be unchanged, otherwise ordering violation can be possible
1325             // if current thread will be preempted and another thread will delete pos.pCur data
1326             // and then set it to another.
1327             // To prevent this we mark pos.pCur data as undeletable by setting LSB
1328             marked_data_ptr valCur( pos.pFound );
1329             if ( !pos.pCur->data.compare_exchange_strong( valCur, valCur | 1, memory_model::memory_order_acquire, atomics::memory_order_relaxed ) ) {
1330                 // oops, pos.pCur data has been changed or another thread is setting pos.pPrev data
1331                 m_Stat.onNodeMarkFailed();
1332                 return false;
1333             }
1334
1335             marked_data_ptr valPrev( pos.pPrevVal );
1336             if ( !pos.pPrev->data.compare_exchange_strong( valPrev, valPrev | 1, memory_model::memory_order_acquire, atomics::memory_order_relaxed ) ) {
1337                 pos.pCur->data.store( valCur, memory_model::memory_order_relaxed );
1338                 m_Stat.onNodeMarkFailed();
1339                 return false;
1340             }
1341
1342             // checks if link pPrev -> pCur is broken
1343             if ( pos.pPrev->next.load( memory_model::memory_order_acquire ) != pos.pCur ) {
1344                 // sequence pPrev - pCur is broken
1345                 pos.pPrev->data.store( valPrev, memory_model::memory_order_relaxed );
1346                 pos.pCur->data.store( valCur, memory_model::memory_order_relaxed );
1347                 m_Stat.onNodeSeqBreak();
1348                 return false;
1349             }
1350
1351             // insert new node between pos.pPrev and pos.pCur
1352             pNode->next.store( pos.pCur, memory_model::memory_order_relaxed );
1353
1354             bool result = pos.pPrev->next.compare_exchange_strong( pos.pCur, pNode, memory_model::memory_order_release, atomics::memory_order_relaxed );
1355
1356             // Clears data marks
1357             pos.pPrev->data.store( valPrev, memory_model::memory_order_relaxed );
1358             pos.pCur->data.store( valCur, memory_model::memory_order_relaxed );
1359
1360             return result;
1361         }
1362
1363         static bool unlink_data( position& pos )
1364         {
1365             assert( pos.pCur != nullptr );
1366             assert( pos.pFound != nullptr );
1367
1368             marked_data_ptr val( pos.pFound );
1369             if ( pos.pCur->data.compare_exchange_strong( val, marked_data_ptr(), memory_model::memory_order_acquire, atomics::memory_order_relaxed ) ) {
1370                 retire_data( pos.pFound );
1371                 return true;
1372             }
1373             return false;
1374         }
1375         //@endcond
1376     };
1377 }} // namespace cds::intrusive
1378
1379 #endif // #ifndef CDSLIB_INTRUSIVE_IMPL_ITERABLE_LIST_H