cds/intrusive/impl/iterable_list.h

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