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