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