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