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 = 2; ///< 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         //@endcond
 157
 158     protected:
 159         typedef atomics::atomic< node_type* > atomic_node_ptr;  ///< Atomic node pointer
 160         typedef atomic_node_ptr               auxiliary_head;   ///< Auxiliary head type (for split-list support)
 161
 162         atomic_node_ptr m_pHead;        ///< Head pointer
 163         item_counter    m_ItemCounter;  ///< Item counter
 164         mutable stat    m_Stat;         ///< Internal statistics
 165
 166         //@cond
 167         typedef cds::details::Allocator< node_type, node_allocator > cxx_node_allocator;
 168
 169         /// Position pointer for item search
 170         struct position {
 171             atomic_node_ptr * pHead; ///< Previous node (pointer to pPrev->next or to m_pHead)
 172             node_type *       pPrev;  ///< Previous node
 173             node_type *       pCur;   ///< Current node
 174
 175             value_type *      pFound; ///< Value of \p pCur->data, valid only if data found
 176             typename gc::Guard guard; ///< guard for \p pFound
 177         };
 178         //@endcond
 179
 180     protected:
 181         //@cond
 182         template <bool IsConst>
 183         class iterator_type
 184         {
 185             friend class IterableList;
 186
 187         protected:
 188             node_type*  m_pNode;
 189             value_type* m_pVal;
 190             typename gc::Guard  m_Guard; // for m_pVal
 191
 192             void next()
 193             {
 194                 while ( m_pNode ) {
 195                     m_pNode = m_pNode->next.load( memory_model::memory_order_relaxed );
 196                     if ( !m_pNode )
 197                         break;
 198                     m_pVal = m_Guard.protect( m_pNode->data );
 199                     if ( m_pVal )
 200                         break;
 201                 }
 202             }
 203
 204             explicit iterator_type( atomic_node_ptr const& pNode )
 205                 : m_pNode( pNode.load( memory_model::memory_order_relaxed ))
 206                 , m_pVal( nullptr )
 207             {
 208                 if ( m_pNode ) {
 209                     m_pVal = m_Guard.protect( m_pNode->data );
 210                     if ( !m_pVal )
 211                         next();
 212                 }
 213             }
 214
 215             iterator_type( node_type* pNode, value_type* pVal )
 216                 : m_pNode( pNode )
 217                 , m_pVal( pVal )
 218             {
 219                 if ( m_pNode ) {
 220                     assert( pVal != nullptr );
 221                     m_Guard.assign( pVal );
 222                 }
 223             }
 224
 225         public:
 226             typedef typename cds::details::make_const_type<value_type, IsConst>::pointer   value_ptr;
 227             typedef typename cds::details::make_const_type<value_type, IsConst>::reference value_ref;
 228
 229             iterator_type()
 230                 : m_pNode( nullptr )
 231                 , m_pVal( nullptr )
 232             {}
 233
 234             iterator_type( iterator_type const& src )
 235                 : m_pNode( src.m_pNode )
 236                 , m_pVal( src.m_pVal )
 237             {
 238                 m_Guard.assign( m_pVal );
 239             }
 240
 241             value_ptr operator ->() const
 242             {
 243                 return m_pVal;
 244             }
 245
 246             value_ref operator *() const
 247             {
 248                 assert( m_pVal != nullptr );
 249                 return *m_pVal;
 250             }
 251
 252             /// Pre-increment
 253             iterator_type& operator ++()
 254             {
 255                 next();
 256                 return *this;
 257             }
 258
 259             iterator_type& operator = (iterator_type const& src)
 260             {
 261                 m_pNode = src.m_pNode;
 262                 m_pVal = src.m_pVal;
 263                 m_Guard.assign( m_pVal );
 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 m_pNode != i.m_pNode;
 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: event 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_pHead );
 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();
 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_pHead );
 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_pHead );
 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();
 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();
 383         }
 384     //@}
 385
 386     public:
 387         /// Default constructor initializes empty list
 388         IterableList()
 389             : m_pHead( nullptr )
 390         {}
 391
 392         //@cond
 393         template <typename Stat, typename = std::enable_if<std::is_same<stat, iterable_list::wrapped_stat<Stat>>::value >>
 394         explicit IterableList( Stat& st )
 395             : m_pHead( nullptr )
 396             , m_Stat( st )
 397         {}
 398         //@endcond
 399
 400         /// Destroys the list object
 401         ~IterableList()
 402         {
 403             destroy();
 404         }
 405
 406         /// Inserts new node
 407         /**
 408             The function inserts \p val into the list if the list does not contain
 409             an item with key equal to \p val.
 410
 411             Returns \p true if \p val has been linked to the list, \p false otherwise.
 412         */
 413         bool insert( value_type& val )
 414         {
 415             return insert_at( m_pHead, val );
 416         }
 417
 418         /// Inserts new node
 419         /**
 420             This function is intended for derived non-intrusive containers.
 421
 422             The function allows to split new item creating into two part:
 423             - create item with key only
 424             - insert new item into the list
 425             - if inserting is success, calls  \p f functor to initialize value-field of \p val.
 426
 427             The functor signature is:
 428             \code
 429                 void func( value_type& val );
 430             \endcode
 431             where \p val is the item inserted. User-defined functor \p f should guarantee that during changing
 432             \p val no any other changes could be made on this list's item by concurrent threads.
 433             The user-defined functor is called only if the inserting is success.
 434
 435             @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
 436         */
 437         template <typename Func>
 438         bool insert( value_type& val, Func f )
 439         {
 440             return insert_at( m_pHead, val, f );
 441         }
 442
 443         /// Updates the node
 444         /**
 445             The operation performs inserting or changing data with lock-free manner.
 446
 447             If the item \p val is not found in the list, then \p val is inserted
 448             iff \p bInsert is \p true.
 449             Otherwise, the current element is changed to \p val, the element will be retired later
 450             by call \p Traits::disposer.
 451             The functor \p func is called after inserting or replacing, it signature is:
 452             \code
 453                 void func( value_type& val, value_type * old );
 454             \endcode
 455             where
 456             - \p val - argument \p val passed into the \p %update() function
 457             - \p old - old value that will be retired. If new item has been inserted then \p old is \p nullptr.
 458
 459             Returns std::pair<bool, bool> where \p first is \p true if operation is successful,
 460             \p second is \p true if \p val has been added or \p false if the item with that key
 461             already in the list.
 462         */
 463         template <typename Func>
 464         std::pair<bool, bool> update( value_type& val, Func func, bool bInsert = true )
 465         {
 466             return update_at( m_pHead, val, func, bInsert );
 467         }
 468
 469         /// Insert or update
 470         /**
 471             The operation performs inserting or updating data with lock-free manner.
 472
 473             If the item \p val is not found in the list, then \p val is inserted
 474             iff \p bInsert is \p true.
 475             Otherwise, the current element is changed to \p val, the old element will be retired later
 476             by call \p Traits::disposer.
 477
 478             Returns std::pair<bool, bool> where \p first is \p true if operation is successful,
 479             \p second is \p true if \p val has been added or \p false if the item with that key
 480             already in the list.
 481         */
 482         std::pair<bool, bool> upsert( value_type& val, bool bInsert = true )
 483         {
 484             return update_at( m_pHead, val, []( value_type&, value_type* ) {}, bInsert );
 485         }
 486
 487         /// Unlinks the item \p val from the list
 488         /**
 489             The function searches the item \p val in the list and unlinks it from the list
 490             if it is found and it is equal to \p val.
 491
 492             Difference between \p erase() and \p %unlink(): \p %erase() finds <i>a key</i>
 493             and deletes the item found. \p %unlink() finds an item by key and deletes it
 494             only if \p val is an item of the list, i.e. the pointer to item found
 495             is equal to <tt> &val </tt>.
 496
 497             \p disposer specified in \p Traits is called for deleted item.
 498
 499             The function returns \p true if success and \p false otherwise.
 500         */
 501         bool unlink( value_type& val )
 502         {
 503             return unlink_at( m_pHead, val );
 504         }
 505
 506         /// Deletes the item from the list
 507         /** \anchor cds_intrusive_IterableList_hp_erase_val
 508             The function searches an item with key equal to \p key in the list,
 509             unlinks it from the list, and returns \p true.
 510             If \p key is not found the function return \p false.
 511
 512             \p disposer specified in \p Traits is called for deleted item.
 513         */
 514         template <typename Q>
 515         bool erase( Q const& key )
 516         {
 517             return erase_at( m_pHead, key, key_comparator());
 518         }
 519
 520         /// Deletes the item from the list using \p pred predicate for searching
 521         /**
 522             The function is an analog of \ref cds_intrusive_IterableList_hp_erase_val "erase(Q const&)"
 523             but \p pred is used for key comparing.
 524             \p Less functor has the interface like \p std::less.
 525             \p pred must imply the same element order as the comparator used for building the list.
 526
 527             \p disposer specified in \p Traits is called for deleted item.
 528         */
 529         template <typename Q, typename Less>
 530         bool erase_with( Q const& key, Less pred )
 531         {
 532             CDS_UNUSED( pred );
 533             return erase_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>());
 534         }
 535
 536         /// Deletes the item from the list
 537         /** \anchor cds_intrusive_IterableList_hp_erase_func
 538             The function searches an item with key equal to \p key in the list,
 539             call \p func functor with item found, unlinks it from the list, and returns \p true.
 540             The \p Func interface is
 541             \code
 542             struct functor {
 543                 void operator()( value_type const& item );
 544             };
 545             \endcode
 546             If \p key is not found the function return \p false, \p func is not called.
 547
 548             \p disposer specified in \p Traits is called for deleted item.
 549         */
 550         template <typename Q, typename Func>
 551         bool erase( Q const& key, Func func )
 552         {
 553             return erase_at( m_pHead, key, key_comparator(), func );
 554         }
 555
 556         /// Deletes the item from the list using \p pred predicate for searching
 557         /**
 558             The function is an analog of \ref cds_intrusive_IterableList_hp_erase_func "erase(Q const&, Func)"
 559             but \p pred is used for key comparing.
 560             \p Less functor has the interface like \p std::less.
 561             \p pred must imply the same element order as the comparator used for building the list.
 562
 563             \p disposer specified in \p Traits is called for deleted item.
 564         */
 565         template <typename Q, typename Less, typename Func>
 566         bool erase_with( Q const& key, Less pred, Func f )
 567         {
 568             CDS_UNUSED( pred );
 569             return erase_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>(), f );
 570         }
 571
 572         /// Extracts the item from the list with specified \p key
 573         /** \anchor cds_intrusive_IterableList_hp_extract
 574             The function searches an item with key equal to \p key,
 575             unlinks it from the list, and returns it as \p guarded_ptr.
 576             If \p key is not found returns an empty guarded pointer.
 577
 578             Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
 579
 580             The \ref disposer specified in \p Traits class template parameter is called automatically
 581             by garbage collector \p GC when returned \ref guarded_ptr object will be destroyed or released.
 582             @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
 583
 584             Usage:
 585             \code
 586             typedef cds::intrusive::IterableList< cds::gc::HP, foo, my_traits >  ord_list;
 587             ord_list theList;
 588             // ...
 589             {
 590                 ord_list::guarded_ptr gp(theList.extract( 5 ));
 591                 if ( gp ) {
 592                     // Deal with gp
 593                     // ...
 594                 }
 595                 // Destructor of gp releases internal HP guard
 596             }
 597             \endcode
 598         */
 599         template <typename Q>
 600         guarded_ptr extract( Q const& key )
 601         {
 602             guarded_ptr gp;
 603             extract_at( m_pHead, gp.guard(), key, key_comparator());
 604             return gp;
 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             guarded_ptr gp;
 621             extract_at( m_pHead, gp.guard(), key, cds::opt::details::make_comparator_from_less<Less>());
 622             return gp;
 623         }
 624
 625         /// Finds \p key in the list
 626         /** \anchor cds_intrusive_IterableList_hp_find_func
 627             The function searches the item with key equal to \p key and calls the functor \p f for item found.
 628             The interface of \p Func functor is:
 629             \code
 630             struct functor {
 631                 void operator()( value_type& item, Q& key );
 632             };
 633             \endcode
 634             where \p item is the item found, \p key is the \p %find() function argument.
 635
 636             The functor may change non-key fields of \p item. Note that the function is only guarantee
 637             that \p item cannot be disposed during functor is executing.
 638             The function does not serialize simultaneous access to the \p item. If such access is
 639             possible you must provide your own synchronization schema to keep out unsafe item modifications.
 640
 641             The function returns \p true if \p val is found, \p false otherwise.
 642         */
 643         template <typename Q, typename Func>
 644         bool find( Q& key, Func f ) const
 645         {
 646             return find_at( m_pHead, key, key_comparator(), f );
 647         }
 648         //@cond
 649         template <typename Q, typename Func>
 650         bool find( Q const& key, Func f ) const
 651         {
 652             return find_at( m_pHead, key, key_comparator(), f );
 653         }
 654         //@endcond
 655
 656         /// Finds \p key in the list and returns iterator pointed to the item found
 657         /**
 658             If \p key is not found the function returns \p end().
 659         */
 660         template <typename Q>
 661         iterator find( Q& key ) const
 662         {
 663             return find_iterator_at( m_pHead, key, key_comparator());
 664         }
 665         //@cond
 666         template <typename Q>
 667         iterator find( Q const& key ) const
 668         {
 669             return find_iterator_at( m_pHead, key, key_comparator() );
 670         }
 671         //@endcond
 672
 673         /// Finds the \p key using \p pred predicate for searching
 674         /**
 675             The function is an analog of \ref cds_intrusive_IterableList_hp_find_func "find(Q&, Func)"
 676             but \p pred is used for key comparing.
 677             \p Less functor has the interface like \p std::less.
 678             \p pred must imply the same element order as the comparator used for building the list.
 679         */
 680         template <typename Q, typename Less, typename Func>
 681         bool find_with( Q& key, Less pred, Func f ) const
 682         {
 683             CDS_UNUSED( pred );
 684             return find_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>(), f );
 685         }
 686         //@cond
 687         template <typename Q, typename Less, typename Func>
 688         bool find_with( Q const& key, Less pred, Func f ) const
 689         {
 690             CDS_UNUSED( pred );
 691             return find_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>(), f );
 692         }
 693         //@endcond
 694
 695         /// Finds \p key in the list using \p pred predicate for searching and returns iterator pointed to the item found
 696         /**
 697             The function is an analog of \p find(Q&) but \p pred is used for key comparing.
 698             \p Less functor has the interface like \p std::less.
 699             \p pred must imply the same element order as the comparator used for building the list.
 700
 701             If \p key is not found the function returns \p end().
 702         */
 703         template <typename Q, typename Less>
 704         iterator find_with( Q& key, Less pred ) const
 705         {
 706             CDS_UNUSED( pred );
 707             return find_iterator_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>());
 708         }
 709         //@cond
 710         template <typename Q, typename Less>
 711         iterator find_with( Q const& key, Less pred ) const
 712         {
 713             CDS_UNUSED( pred );
 714             return find_iterator_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>());
 715         }
 716         //@endcond
 717
 718         /// Checks whether the list contains \p key
 719         /**
 720             The function searches the item with key equal to \p key
 721             and returns \p true if it is found, and \p false otherwise.
 722         */
 723         template <typename Q>
 724         bool contains( Q const& key ) const
 725         {
 726             return find_at( m_pHead, key, key_comparator());
 727         }
 728
 729         /// Checks whether the list contains \p key using \p pred predicate for searching
 730         /**
 731             The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
 732             \p Less functor has the interface like \p std::less.
 733             \p Less must imply the same element order as the comparator used for building the list.
 734         */
 735         template <typename Q, typename Less>
 736         bool contains( Q const& key, Less pred ) const
 737         {
 738             CDS_UNUSED( pred );
 739             return find_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>());
 740         }
 741
 742         /// Finds the \p key and return the item found
 743         /** \anchor cds_intrusive_IterableList_hp_get
 744             The function searches the item with key equal to \p key
 745             and returns it as \p guarded_ptr.
 746             If \p key is not found the function returns an empty guarded pointer.
 747
 748             The \ref disposer specified in \p Traits class template parameter is called
 749             by garbage collector \p GC automatically when returned \ref guarded_ptr object
 750             will be destroyed or released.
 751             @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
 752
 753             Usage:
 754             \code
 755             typedef cds::intrusive::IterableList< cds::gc::HP, foo, my_traits >  ord_list;
 756             ord_list theList;
 757             // ...
 758             {
 759                 ord_list::guarded_ptr gp(theList.get( 5 ));
 760                 if ( gp ) {
 761                     // Deal with gp
 762                     //...
 763                 }
 764                 // Destructor of guarded_ptr releases internal HP guard
 765             }
 766             \endcode
 767
 768             Note the compare functor specified for \p Traits template parameter
 769             should accept a parameter of type \p Q that can be not the same as \p value_type.
 770         */
 771         template <typename Q>
 772         guarded_ptr get( Q const& key ) const
 773         {
 774             guarded_ptr gp;
 775             get_at( m_pHead, gp.guard(), key, key_comparator());
 776             return gp;
 777         }
 778
 779         /// Finds the \p key and return the item found
 780         /**
 781             The function is an analog of \ref cds_intrusive_IterableList_hp_get "get( Q const&)"
 782             but \p pred is used for comparing the keys.
 783
 784             \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
 785             in any order.
 786             \p pred must imply the same element order as the comparator used for building the list.
 787         */
 788         template <typename Q, typename Less>
 789         guarded_ptr get_with( Q const& key, Less pred ) const
 790         {
 791             CDS_UNUSED( pred );
 792             guarded_ptr gp;
 793             get_at( m_pHead, gp.guard(), key, cds::opt::details::make_comparator_from_less<Less>());
 794             return gp;
 795         }
 796
 797         /// Clears the list (thread safe, not atomic)
 798         void clear()
 799         {
 800             position pos;
 801             for ( pos.pCur = m_pHead.load( memory_model::memory_order_relaxed ); pos.pCur; pos.pCur = pos.pCur->next.load( memory_model::memory_order_relaxed )) {
 802                 while ( true ) {
 803                     pos.pFound = pos.guard.protect( pos.pCur->data );
 804                     if ( !pos.pFound )
 805                         break;
 806                     if ( cds_likely( unlink_node( pos ))) {
 807                         --m_ItemCounter;
 808                         break;
 809                     }
 810                 }
 811             }
 812         }
 813
 814         /// Checks if the list is empty
 815         /**
 816             Emptiness is checked by item counting: if item count is zero then the set is empty.
 817             Thus, if you need to use \p %empty() you should provide appropriate (non-empty) \p iterable_list::traits::item_counter
 818             feature.
 819         */
 820         bool empty() const
 821         {
 822             return size() == 0;
 823         }
 824
 825         /// Returns list's item count
 826         /**
 827             The value returned depends on item counter provided by \p iterable_list::traits::item_counter. For \p atomicity::empty_item_counter,
 828             this function always returns 0.
 829         */
 830         size_t size() const
 831         {
 832             return m_ItemCounter.value();
 833         }
 834
 835         /// Returns const reference to internal statistics
 836         stat const& statistics() const
 837         {
 838             return m_Stat;
 839         }
 840
 841     protected:
 842         //@cond
 843 #if 0
 844         // split-list support
 845         bool insert_aux_node( node_type * pNode )
 846         {
 847             return insert_aux_node( m_pHead, pNode );
 848         }
 849
 850         // split-list support
 851         bool insert_aux_node( atomic_node_ptr& refHead, node_type * pNode )
 852         {
 853             assert( pNode != nullptr );
 854
 855             // Hack: convert node_type to value_type.
 856             // In principle, auxiliary node can be non-reducible to value_type
 857             // We assume that comparator can correctly distinguish aux and regular node.
 858             return insert_at( refHead, *node_traits::to_value_ptr( pNode ) );
 859         }
 860 #endif
 861
 862         bool insert_at( atomic_node_ptr& refHead, value_type& val )
 863         {
 864             position pos;
 865
 866             while ( true ) {
 867                 if ( search( refHead, val, pos, key_comparator() )) {
 868                     m_Stat.onInsertFailed();
 869                     return false;
 870                 }
 871
 872                 if ( link_node( &val, pos ) ) {
 873                     ++m_ItemCounter;
 874                     m_Stat.onInsertSuccess();
 875                     return true;
 876                 }
 877
 878                 m_Stat.onInsertRetry();
 879             }
 880         }
 881
 882         template <typename Func>
 883         bool insert_at( atomic_node_ptr& refHead, value_type& val, Func f )
 884         {
 885             position pos;
 886
 887             typename gc::Guard guard;
 888             guard.assign( &val );
 889
 890             while ( true ) {
 891                 if ( search( refHead, val, pos, key_comparator() ) ) {
 892                     m_Stat.onInsertFailed();
 893                     return false;
 894                 }
 895
 896                 if ( link_node( &val, pos ) ) {
 897                     f( val );
 898                     ++m_ItemCounter;
 899                     m_Stat.onInsertSuccess();
 900                     return true;
 901                 }
 902
 903                 m_Stat.onInsertRetry();
 904             }
 905         }
 906
 907         template <typename Func>
 908         std::pair<bool, bool> update_at( atomic_node_ptr& refHead, value_type& val, Func func, bool bInsert )
 909         {
 910             position pos;
 911
 912             typename gc::Guard guard;
 913             guard.assign( &val );
 914
 915             while ( true ) {
 916                 if ( search( refHead, val, pos, key_comparator() ) ) {
 917                     // try to replace pCur->data with val
 918                     assert( pos.pFound != nullptr );
 919                     assert( key_comparator()(*pos.pFound, val) == 0 );
 920
 921                     if ( cds_likely( pos.pCur->data.compare_exchange_strong( pos.pFound, &val, memory_model::memory_order_release, atomics::memory_order_relaxed ))) {
 922                         if ( pos.pFound != &val ) {
 923                             retire_data( pos.pFound );
 924                             func( val, pos.pFound );
 925                         }
 926                         m_Stat.onUpdateExisting();
 927                         return std::make_pair( true, false );
 928                     }
 929                 }
 930                 else {
 931                     if ( !bInsert ) {
 932                         m_Stat.onUpdateFailed();
 933                         return std::make_pair( false, false );
 934                     }
 935
 936                     if ( link_node( &val, pos )) {
 937                         func( val, static_cast<value_type*>( nullptr ));
 938                         ++m_ItemCounter;
 939                         m_Stat.onUpdateNew();
 940                         return std::make_pair( true, true );
 941                     }
 942                 }
 943
 944                 m_Stat.onUpdateRetry();
 945             }
 946         }
 947
 948         bool unlink_at( atomic_node_ptr& refHead, value_type& val )
 949         {
 950             position pos;
 951
 952             back_off bkoff;
 953             while ( search( refHead, val, pos, key_comparator())) {
 954                 if ( pos.pFound == &val ) {
 955                     if ( unlink_node( pos )) {
 956                         --m_ItemCounter;
 957                         m_Stat.onEraseSuccess();
 958                         return true;
 959                     }
 960                     else
 961                         bkoff();
 962                 }
 963                 else
 964                     break;
 965
 966                 m_Stat.onEraseRetry();
 967             }
 968
 969             m_Stat.onEraseFailed();
 970             return false;
 971         }
 972
 973         template <typename Q, typename Compare, typename Func>
 974         bool erase_at( atomic_node_ptr& refHead, const Q& val, Compare cmp, Func f, position& pos )
 975         {
 976             back_off bkoff;
 977             while ( search( refHead, val, pos, cmp )) {
 978                 if ( unlink_node( pos )) {
 979                     f( *pos.pFound );
 980                     --m_ItemCounter;
 981                     m_Stat.onEraseSuccess();
 982                     return true;
 983                 }
 984                 else
 985                     bkoff();
 986
 987                 m_Stat.onEraseRetry();
 988             }
 989
 990             m_Stat.onEraseFailed();
 991             return false;
 992         }
 993
 994         template <typename Q, typename Compare, typename Func>
 995         bool erase_at( atomic_node_ptr& refHead, const Q& val, Compare cmp, Func f )
 996         {
 997             position pos;
 998             return erase_at( refHead, val, cmp, f, pos );
 999         }
1000
1001         template <typename Q, typename Compare>
1002         bool erase_at( atomic_node_ptr& refHead, Q const& val, Compare cmp )
1003         {
1004             position pos;
1005             return erase_at( refHead, val, cmp, [](value_type const&){}, pos );
1006         }
1007
1008         template <typename Q, typename Compare>
1009         bool extract_at( atomic_node_ptr& refHead, typename guarded_ptr::native_guard& dest, Q const& val, Compare cmp )
1010         {
1011             position pos;
1012             back_off bkoff;
1013             while ( search( refHead, val, pos, cmp )) {
1014                 if ( unlink_node( pos )) {
1015                     dest.set( pos.pFound );
1016                     --m_ItemCounter;
1017                     m_Stat.onEraseSuccess();
1018                     return true;
1019                 }
1020                 else
1021                     bkoff();
1022
1023                 m_Stat.onEraseRetry();
1024             }
1025
1026             m_Stat.onEraseFailed();
1027             return false;
1028         }
1029
1030         template <typename Q, typename Compare>
1031         bool find_at( atomic_node_ptr const& refHead, Q const& val, Compare cmp ) const
1032         {
1033             position pos;
1034             if ( search( refHead, val, pos, cmp ) ) {
1035                 m_Stat.onFindSuccess();
1036                 return true;
1037             }
1038
1039             m_Stat.onFindFailed();
1040             return false;
1041         }
1042
1043         template <typename Q, typename Compare, typename Func>
1044         bool find_at( atomic_node_ptr const& refHead, Q& val, Compare cmp, Func f ) const
1045         {
1046             position pos;
1047             if ( search( refHead, val, pos, cmp )) {
1048                 assert( pos.pFound != nullptr );
1049                 f( *pos.pFound, val );
1050                 m_Stat.onFindSuccess();
1051                 return true;
1052             }
1053
1054             m_Stat.onFindFailed();
1055             return false;
1056         }
1057
1058         template <typename Q, typename Compare>
1059         iterator find_iterator_at( atomic_node_ptr const& refHead, Q const& val, Compare cmp ) const
1060         {
1061             position pos;
1062             if ( search( refHead, val, pos, cmp )) {
1063                 assert( pos.pCur != nullptr );
1064                 assert( pos.pFound != nullptr );
1065                 m_Stat.onFindSuccess();
1066                 return iterator( pos.pCur, pos.pFound );
1067             }
1068
1069             m_Stat.onFindFailed();
1070             return iterator{};
1071         }
1072
1073         template <typename Q, typename Compare>
1074         bool get_at( atomic_node_ptr const& refHead, typename guarded_ptr::native_guard& guard, Q const& val, Compare cmp ) const
1075         {
1076             position pos;
1077             if ( search( refHead, val, pos, cmp )) {
1078                 guard.set( pos.pFound );
1079                 m_Stat.onFindSuccess();
1080                 return true;
1081             }
1082
1083             m_Stat.onFindFailed();
1084             return false;
1085         }
1086         //@endcond
1087
1088     protected:
1089
1090         //@cond
1091         template <typename Q, typename Compare >
1092         bool search( atomic_node_ptr const& refHead, const Q& val, position& pos, Compare cmp ) const
1093         {
1094             atomic_node_ptr* pHead = const_cast<atomic_node_ptr*>( &refHead );
1095             node_type * pPrev = nullptr;
1096
1097             while ( true ) {
1098                 node_type * pCur = pHead->load( memory_model::memory_order_relaxed );
1099
1100                 if ( pCur == nullptr ) {
1101                     // end-of-list
1102                     pos.pHead = pHead;
1103                     pos.pPrev = pPrev;
1104                     pos.pCur = nullptr;
1105                     pos.pFound = nullptr;
1106                     return false;
1107                 }
1108
1109                 value_type * pVal = pos.guard.protect( pCur->data );
1110
1111                 if ( pVal ) {
1112                     int nCmp = cmp( *pVal, val );
1113                     if ( nCmp >= 0 ) {
1114                         pos.pHead = pHead;
1115                         pos.pPrev = pPrev;
1116                         pos.pCur = pCur;
1117                         pos.pFound = pVal;
1118                         return nCmp == 0;
1119                     }
1120                 }
1121
1122                 pPrev = pCur;
1123                 pHead = &( pCur->next );
1124             }
1125         }
1126         //@endcond
1127
1128     private:
1129         //@cond
1130         node_type * alloc_node( value_type * pVal )
1131         {
1132             m_Stat.onNodeCreated();
1133             return cxx_node_allocator().New( pVal );
1134         }
1135
1136         void delete_node( node_type * pNode )
1137         {
1138             m_Stat.onNodeRemoved();
1139             cxx_node_allocator().Delete( pNode );
1140         }
1141
1142         static void retire_data( value_type * pVal )
1143         {
1144             assert( pVal != nullptr );
1145             gc::template retire<disposer>( pVal );
1146         }
1147
1148         void destroy()
1149         {
1150             node_type * pNode = m_pHead.load( memory_model::memory_order_relaxed );
1151             while ( pNode ) {
1152                 value_type * pVal = pNode->data.load( memory_model::memory_order_relaxed );
1153                 if ( pVal )
1154                     retire_data( pVal );
1155                 node_type * pNext = pNode->next.load( memory_model::memory_order_relaxed );
1156                 delete_node( pNode );
1157                 pNode = pNext;
1158             }
1159         }
1160
1161         bool link_node( value_type * pVal, position& pos )
1162         {
1163             if ( pos.pPrev ) {
1164                 if ( pos.pPrev->data.load( memory_model::memory_order_relaxed ) == nullptr ) {
1165                     // reuse pPrev
1166                     value_type * p = nullptr;
1167                     return pos.pPrev->data.compare_exchange_strong( p, pVal, memory_model::memory_order_release, atomics::memory_order_relaxed );
1168                 }
1169                 else {
1170                     // insert new node between pos.pPrev and pos.pCur
1171                     node_type * pNode = alloc_node( pVal );
1172                     pNode->next.store( pos.pCur, memory_model::memory_order_relaxed );
1173
1174                     if ( cds_likely( pos.pPrev->next.compare_exchange_strong( pos.pCur, pNode, memory_model::memory_order_release, atomics::memory_order_relaxed )))
1175                         return true;
1176
1177                     delete_node( pNode );
1178                 }
1179             }
1180             else {
1181                 node_type * pNode = alloc_node( pVal );
1182                 pNode->next.store( pos.pCur, memory_model::memory_order_relaxed );
1183                 if ( cds_likely( pos.pHead->compare_exchange_strong( pos.pCur, pNode, memory_model::memory_order_release, atomics::memory_order_relaxed ) ) )
1184                     return true;
1185
1186                 delete_node( pNode );
1187             }
1188             return false;
1189         }
1190
1191         static bool unlink_node( position& pos )
1192         {
1193             assert( pos.pCur != nullptr );
1194             assert( pos.pFound != nullptr );
1195
1196             if ( pos.pCur->data.compare_exchange_strong( pos.pFound, nullptr, memory_model::memory_order_acquire, atomics::memory_order_relaxed ) ) {
1197                 retire_data( pos.pFound );
1198                 return true;
1199             }
1200             return false;
1201         }
1202
1203         //@endcond
1204     };
1205 }} // namespace cds::intrusive
1206
1207 #endif // #ifndef CDSLIB_INTRUSIVE_IMPL_ITERABLE_LIST_H