cds/container/lazy_list_impl.h

   1 //$$CDS-header$$
   2
   3 #ifndef __CDS_CONTAINER_LAZY_LIST_IMPL_H
   4 #define __CDS_CONTAINER_LAZY_LIST_IMPL_H
   5
   6 #include <memory>
   7 #include <cds/container/details/guarded_ptr_cast.h>
   8
   9 namespace cds { namespace container {
  10
  11     /// Lazy ordered list
  12     /** @ingroup cds_nonintrusive_list
  13         \anchor cds_nonintrusive_LazyList_gc
  14
  15         Usually, ordered single-linked list is used as a building block for the hash table implementation.
  16         The complexity of searching is <tt>O(N)</tt>.
  17
  18         Source:
  19         - [2005] Steve Heller, Maurice Herlihy, Victor Luchangco, Mark Moir, William N. Scherer III, and Nir Shavit
  20         "A Lazy Concurrent List-Based Set Algorithm"
  21
  22         The lazy list is based on an optimistic locking scheme for inserts and removes,
  23         eliminating the need to use the equivalent of an atomically markable
  24         reference. It also has a novel wait-free membership \p find operation
  25         that does not need to perform cleanup operations and is more efficient.
  26
  27         It is non-intrusive version of cds::intrusive::LazyList class
  28
  29         Template arguments:
  30         - \p GC - garbage collector used
  31         - \p T - type stored in the list. The type must be default- and copy-constructible.
  32         - \p Traits - type traits, default is lazy_list::type_traits
  33
  34         Unlike standard container, this implementation does not divide type \p T into key and value part and
  35         may be used as main building block for hash set algorithms.
  36
  37         The key is a function (or a part) of type \p T, and this function is specified by <tt> Traits::compare </tt> functor
  38         or <tt> Traits::less </tt> predicate
  39
  40         LazyKVList is a key-value version of lazy non-intrusive list that is closer to the C++ std library approach.
  41
  42         It is possible to declare option-based list with cds::container::lazy_list::make_traits metafunction istead of \p Traits template
  43         argument. For example, the following traits-based declaration of gc::HP lazy list
  44         \code
  45         #include <cds/container/lazy_list_hp.h>
  46         // Declare comparator for the item
  47         struct my_compare {
  48             int operator ()( int i1, int i2 )
  49             {
  50                 return i1 - i2;
  51             }
  52         };
  53
  54         // Declare type_traits
  55         struct my_traits: public cds::container::lazy_list::type_traits
  56         {
  57             typedef my_compare compare;
  58         };
  59
  60         // Declare traits-based list
  61         typedef cds::container::LazyList< cds::gc::HP, int, my_traits >     traits_based_list;
  62         \endcode
  63
  64         is equivalent for the following option-based list
  65         \code
  66         #include <cds/container/lazy_list_hp.h>
  67
  68         // my_compare is the same
  69
  70         // Declare option-based list
  71         typedef cds::container::LazyList< cds::gc::HP, int,
  72             typename cds::container::lazy_list::make_traits<
  73                 cds::container::opt::compare< my_compare >     // item comparator option
  74             >::type
  75         >     option_based_list;
  76         \endcode
  77
  78         Template argument list \p Options of cds::container::lazy_list::make_traits metafunction are:
  79         - opt::lock_type - lock type for per-node locking. Default is cds::lock::Spin. Note that <b>each</b> node
  80             of the list has member of type \p lock_type, therefore, heavy-weighted locking primitive is not
  81             acceptable as candidate for \p lock_type.
  82         - opt::compare - key compare functor. No default functor is provided.
  83             If the option is not specified, the opt::less is used.
  84         - opt::less - specifies binary predicate used for key compare. Default is \p std::less<T>.
  85         - opt::back_off - back-off strategy used. If the option is not specified, the cds::backoff::empty is used.
  86         - opt::item_counter - the type of item counting feature. Default is \ref atomicity::empty_item_counter that is no item counting.
  87         - opt::allocator - the allocator used for creating and freeing list's item. Default is \ref CDS_DEFAULT_ALLOCATOR macro.
  88         - opt::memory_model - C++ memory ordering model. Can be opt::v::relaxed_ordering (relaxed memory model, the default)
  89             or opt::v::sequential_consistent (sequentially consisnent memory model).
  90
  91         \par Usage
  92         There are different specializations of this template for each garbage collecting schema used.
  93         You should include appropriate .h-file depending on GC you are using:
  94         - for gc::HP: \code #include <cds/container/lazy_list_hp.h> \endcode
  95         - for gc::PTB: \code #include <cds/container/lazy_list_ptb.h> \endcode
  96         - for gc::HRC: \code #include <cds/container/lazy_list_hrc.h> \endcode
  97         - for \ref cds_urcu_desc "RCU": \code #include <cds/container/lazy_list_rcu.h> \endcode
  98         - for gc::nogc: \code #include <cds/container/lazy_list_nogc.h> \endcode
  99     */
 100     template <
 101         typename GC,
 102         typename T,
 103 #ifdef CDS_DOXYGEN_INVOKED
 104         typename Traits = lazy_list::type_traits
 105 #else
 106         typename Traits
 107 #endif
 108     >
 109     class LazyList:
 110 #ifdef CDS_DOXYGEN_INVOKED
 111         protected intrusive::LazyList< GC, T, Traits >
 112 #else
 113         protected details::make_lazy_list< GC, T, Traits >::type
 114 #endif
 115     {
 116         //@cond
 117         typedef details::make_lazy_list< GC, T, Traits > options;
 118         typedef typename options::type  base_class;
 119         //@endcond
 120
 121     public:
 122         typedef T                                   value_type      ;   ///< Type of value stored in the list
 123         typedef typename base_class::gc             gc              ;   ///< Garbage collector used
 124         typedef typename base_class::back_off       back_off        ;   ///< Back-off strategy used
 125         typedef typename options::allocator_type    allocator_type  ;   ///< Allocator type used for allocate/deallocate the nodes
 126         typedef typename base_class::item_counter   item_counter    ;   ///< Item counting policy used
 127         typedef typename options::key_comparator    key_comparator  ;   ///< key comparison functor
 128         typedef typename base_class::memory_model   memory_model    ;   ///< Memory ordering. See cds::opt::memory_model option
 129
 130     protected:
 131         //@cond
 132         typedef typename base_class::value_type     node_type;
 133         typedef typename options::cxx_allocator     cxx_allocator;
 134         typedef typename options::node_deallocator  node_deallocator;
 135         typedef typename options::type_traits::compare  intrusive_key_comparator;
 136
 137         typedef typename base_class::node_type      head_type;
 138 #   ifndef CDS_CXX11_LAMBDA_SUPPORT
 139         typedef typename base_class::empty_erase_functor    empty_erase_functor;
 140 #   endif
 141         //@endcond
 142
 143     public:
 144         /// Guarded pointer
 145         typedef cds::gc::guarded_ptr< gc, node_type, value_type, details::guarded_ptr_cast_set<node_type, value_type> > guarded_ptr;
 146
 147     private:
 148         //@cond
 149         static value_type& node_to_value( node_type& n )
 150         {
 151             return n.m_Value;
 152         }
 153         static value_type const& node_to_value( node_type const& n )
 154         {
 155             return n.m_Value;
 156         }
 157
 158 #   ifndef CDS_CXX11_LAMBDA_SUPPORT
 159         template <typename Func>
 160         struct insert_functor
 161         {
 162             Func        m_func;
 163
 164             insert_functor ( Func f )
 165                 : m_func(f)
 166             {}
 167
 168             void operator()( node_type& node )
 169             {
 170                 cds::unref(m_func)( node_to_value(node) );
 171             }
 172         };
 173
 174         template <typename Q, typename Func>
 175         struct ensure_functor
 176         {
 177             Func        m_func;
 178             const Q&    m_arg;
 179
 180             ensure_functor( const Q& arg, Func f )
 181                 : m_func(f)
 182                 , m_arg( arg )
 183             {}
 184
 185             void operator ()( bool bNew, node_type& node, node_type& )
 186             {
 187                 cds::unref(m_func)( bNew, node_to_value(node), m_arg );
 188             }
 189         };
 190
 191         template <typename Func>
 192         struct find_functor
 193         {
 194             Func    m_func;
 195
 196             find_functor( Func f )
 197                 : m_func(f)
 198             {}
 199
 200             template <typename Q>
 201             void operator ()( node_type& node, Q& val )
 202             {
 203                 cds::unref(m_func)( node_to_value(node), val );
 204             }
 205         };
 206
 207         template <typename Func>
 208         struct erase_functor
 209         {
 210             Func        m_func;
 211
 212             erase_functor( Func f )
 213                 : m_func(f)
 214             {}
 215
 216             void operator()( node_type const& node )
 217             {
 218                 cds::unref(m_func)( node_to_value(node) );
 219             }
 220         };
 221 #   endif   // ifndef CDS_CXX11_LAMBDA_SUPPORT
 222         //@endcond
 223
 224     protected:
 225         //@cond
 226         template <typename Q>
 227         static node_type * alloc_node( Q const& v )
 228         {
 229             return cxx_allocator().New( v );
 230         }
 231
 232 #   ifdef CDS_EMPLACE_SUPPORT
 233         template <typename... Args>
 234         static node_type * alloc_node( Args&&... args )
 235         {
 236             return cxx_allocator().MoveNew( std::forward<Args>(args)... );
 237         }
 238 #   endif
 239
 240         static void free_node( node_type * pNode )
 241         {
 242             cxx_allocator().Delete( pNode );
 243         }
 244
 245         struct node_disposer {
 246             void operator()( node_type * pNode )
 247             {
 248                 free_node( pNode );
 249             }
 250         };
 251         typedef std::unique_ptr< node_type, node_disposer >     scoped_node_ptr;
 252
 253         head_type& head()
 254         {
 255             return *base_class::head();
 256         }
 257
 258         head_type const& head() const
 259         {
 260             return *base_class::head();
 261         }
 262
 263         head_type& tail()
 264         {
 265             return *base_class::tail();
 266         }
 267
 268         head_type const&  tail() const
 269         {
 270             return *base_class::tail();
 271         }
 272         //@endcond
 273
 274     protected:
 275                 //@cond
 276         template <bool IsConst>
 277         class iterator_type: protected base_class::template iterator_type<IsConst>
 278         {
 279             typedef typename base_class::template iterator_type<IsConst>    iterator_base;
 280
 281             iterator_type( head_type const& pNode )
 282                 : iterator_base( const_cast<head_type *>( &pNode ))
 283             {}
 284
 285             iterator_type( head_type const * pNode )
 286                 : iterator_base( const_cast<head_type *>( pNode ))
 287             {}
 288
 289             friend class LazyList;
 290
 291         public:
 292             typedef typename cds::details::make_const_type<value_type, IsConst>::pointer   value_ptr;
 293             typedef typename cds::details::make_const_type<value_type, IsConst>::reference value_ref;
 294
 295             iterator_type()
 296             {}
 297
 298             iterator_type( const iterator_type& src )
 299                 : iterator_base( src )
 300             {}
 301
 302             value_ptr operator ->() const
 303             {
 304                 typename iterator_base::value_ptr p = iterator_base::operator ->();
 305                 return p ? &(p->m_Value) : nullptr;
 306             }
 307
 308             value_ref operator *() const
 309             {
 310                 return (iterator_base::operator *()).m_Value;
 311             }
 312
 313             /// Pre-increment
 314             iterator_type& operator ++()
 315             {
 316                 iterator_base::operator ++();
 317                 return *this;
 318             }
 319
 320             template <bool C>
 321             bool operator ==(iterator_type<C> const& i ) const
 322             {
 323                 return iterator_base::operator ==(i);
 324             }
 325             template <bool C>
 326             bool operator !=(iterator_type<C> const& i ) const
 327             {
 328                 return iterator_base::operator !=(i);
 329             }
 330         };
 331         //@endcond
 332
 333     public:
 334         /// Forward iterator
 335         /**
 336             The forward iterator for lazy list has some features:
 337             - it has no post-increment operator
 338             - to protect the value, the iterator contains a GC-specific guard + another guard is required locally for increment operator.
 339               For some GC (gc::HP, gc::HRC), a guard is limited resource per thread, so an exception (or assertion) "no free guard"
 340               may be thrown if a limit of guard count per thread is exceeded.
 341             - The iterator cannot be moved across thread boundary since it contains GC's guard that is thread-private GC data.
 342             - Iterator ensures thread-safety even if you delete the item that iterator points to. However, in case of concurrent
 343               deleting operations it is no guarantee that you iterate all item in the list.
 344
 345             Therefore, the use of iterators in concurrent environment is not good idea. Use the iterator on the concurrent container
 346             for debug purpose only.
 347         */
 348         typedef iterator_type<false>    iterator;
 349
 350         /// Const forward iterator
 351         /**
 352             For iterator's features and requirements see \ref iterator
 353         */
 354         typedef iterator_type<true>     const_iterator;
 355
 356         /// Returns a forward iterator addressing the first element in a list
 357         /**
 358             For empty list \code begin() == end() \endcode
 359         */
 360         iterator begin()
 361         {
 362             iterator it( head() );
 363             ++it        ;   // skip dummy head node
 364             return it;
 365         }
 366
 367         /// Returns an iterator that addresses the location succeeding the last element in a list
 368         /**
 369             Do not use the value returned by <tt>end</tt> function to access any item.
 370
 371             The returned value can be used only to control reaching the end of the list.
 372             For empty list \code begin() == end() \endcode
 373         */
 374         iterator end()
 375         {
 376             return iterator( tail() );
 377         }
 378
 379         /// Returns a forward const iterator addressing the first element in a list
 380         //@{
 381         const_iterator begin() const
 382         {
 383             const_iterator it( head() );
 384             ++it        ;   // skip dummy head node
 385             return it;
 386         }
 387         const_iterator cbegin()
 388         {
 389             const_iterator it( head() );
 390             ++it        ;   // skip dummy head node
 391             return it;
 392         }
 393         //@}
 394
 395         /// Returns an const iterator that addresses the location succeeding the last element in a list
 396         //@{
 397         const_iterator end() const
 398         {
 399             return const_iterator( tail() );
 400         }
 401         const_iterator cend()
 402         {
 403             return const_iterator( tail() );
 404         }
 405         //@}
 406
 407     public:
 408         /// Default constructor
 409         /**
 410             Initializes empty list
 411         */
 412         LazyList()
 413         {}
 414
 415         /// List desctructor
 416         /**
 417             Clears the list
 418         */
 419         ~LazyList()
 420         {
 421             clear();
 422         }
 423
 424         /// Inserts new node
 425         /**
 426             The function creates a node with copy of \p val value
 427             and then inserts the node created into the list.
 428
 429             The type \p Q should contain as minimum the complete key of the node.
 430             The object of \ref value_type should be constructible from \p val of type \p Q.
 431             In trivial case, \p Q is equal to \ref value_type.
 432
 433             Returns \p true if inserting successful, \p false otherwise.
 434         */
 435         template <typename Q>
 436         bool insert( Q const& val )
 437         {
 438             return insert_at( head(), val );
 439         }
 440
 441         /// Inserts new node
 442         /**
 443             This function inserts new node with default-constructed value and then it calls
 444             \p func functor with signature
 445             \code void func( value_type& itemValue ) ;\endcode
 446
 447             The argument \p itemValue of user-defined functor \p func is the reference
 448             to the list's item inserted. User-defined functor \p func should guarantee that during changing
 449             item's value no any other changes could be made on this list's item by concurrent threads.
 450             The user-defined functor can be passed by reference using <tt>boost::ref</tt>
 451             and it is called only if the inserting is success.
 452
 453             The type \p Q should contain the complete key of the node.
 454             The object of \ref value_type should be constructible from \p key of type \p Q.
 455
 456             The function allows to split creating of new item into two part:
 457             - create item from \p key with initializing key-fields only;
 458             - insert new item into the list;
 459             - if inserting is successful, initialize non-key fields of item by calling \p f functor
 460
 461             This can be useful if complete initialization of object of \p value_type is heavyweight and
 462             it is preferable that the initialization should be completed only if inserting is successful.
 463         */
 464         template <typename Q, typename Func>
 465         bool insert( Q const& key, Func func )
 466         {
 467             return insert_at( head(), key, func );
 468         }
 469
 470 #   ifdef CDS_EMPLACE_SUPPORT
 471         /// Inserts data of type \ref value_type constructed with <tt>std::forward<Args>(args)...</tt>
 472         /**
 473             Returns \p true if inserting successful, \p false otherwise.
 474
 475             This function is available only for compiler that supports
 476             variadic template and move semantics
 477         */
 478         template <typename... Args>
 479         bool emplace( Args&&... args )
 480         {
 481             return emplace_at( head(), std::forward<Args>(args)... );
 482         }
 483 #   endif
 484
 485         /// Ensures that the \p key exists in the list
 486         /**
 487             The operation performs inserting or changing data with lock-free manner.
 488
 489             If the \p key not found in the list, then the new item created from \p key
 490             is inserted into the list. Otherwise, the functor \p func is called with the item found.
 491             The functor \p Func should be a function with signature:
 492             \code
 493                 void func( bool bNew, value_type& item, const Q& val );
 494             \endcode
 495             or a functor:
 496             \code
 497                 struct my_functor {
 498                     void operator()( bool bNew, value_type& item, const Q& val );
 499                 };
 500             \endcode
 501
 502             with arguments:
 503             - \p bNew - \p true if the item has been inserted, \p false otherwise
 504             - \p item - item of the list
 505             - \p val - argument \p key passed into the \p ensure function
 506
 507             The functor may change non-key fields of the \p item; however, \p func must guarantee
 508             that during changing no any other modifications could be made on this item by concurrent threads.
 509
 510             You may pass \p func argument by reference using <tt>boost::ref</tt>.
 511
 512             Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
 513             \p second is true if new item has been added or \p false if the item with \p key
 514             already is in the list.
 515         */
 516         template <typename Q, typename Func>
 517         std::pair<bool, bool> ensure( Q const& key, Func f )
 518         {
 519             return ensure_at( head(), key, f );
 520         }
 521
 522         /// Deletes \p key from the list
 523         /** \anchor cds_nonintrusive_LazyList_hp_erase_val
 524             Since the key of LazyList's item type \p T is not explicitly specified,
 525             template parameter \p Q defines the key type searching in the list.
 526             The list item comparator should be able to compare the type \p T of list item
 527             and the type \p Q.
 528
 529             Return \p true if key is found and deleted, \p false otherwise
 530         */
 531         template <typename Q>
 532         bool erase( Q const& key )
 533         {
 534 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
 535             return erase_at( head(), key, intrusive_key_comparator(), [](value_type const&){} );
 536 #       else
 537             return erase_at( head(), key, intrusive_key_comparator(), empty_erase_functor() );
 538 #       endif
 539         }
 540
 541         /// Deletes the item from the list using \p pred predicate for searching
 542         /**
 543             The function is an analog of \ref cds_nonintrusive_LazyList_hp_erase_val "erase(Q const&)"
 544             but \p pred is used for key comparing.
 545             \p Less functor has the interface like \p std::less.
 546             \p pred must imply the same element order as the comparator used for building the list.
 547         */
 548         template <typename Q, typename Less>
 549         bool erase_with( Q const& key, Less pred )
 550         {
 551 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
 552             return erase_at( head(), key, typename options::template less_wrapper<Less>::type(), [](value_type const&){} );
 553 #       else
 554             return erase_at( head(), key, typename options::template less_wrapper<Less>::type(), empty_erase_functor() );
 555 #       endif
 556         }
 557
 558         /// Deletes \p key from the list
 559         /** \anchor cds_nonintrusive_LazyList_hp_erase_func
 560             The function searches an item with key \p key, calls \p f functor with item found
 561             and deletes the item. If \p key is not found, the functor is not called.
 562
 563             The functor \p Func interface:
 564             \code
 565             struct extractor {
 566                 void operator()(const value_type& val) { ... }
 567             };
 568             \endcode
 569             The functor may be passed by reference with <tt>boost:ref</tt>
 570
 571             Since the key of LazyList's item type \p T is not explicitly specified,
 572             template parameter \p Q defines the key type searching in the list.
 573             The list item comparator should be able to compare the type \p T of list item
 574             and the type \p Q.
 575
 576             Return \p true if key is found and deleted, \p false otherwise
 577
 578             See also: \ref erase
 579         */
 580         template <typename Q, typename Func>
 581         bool erase( Q const& key, Func f )
 582         {
 583             return erase_at( head(), key, intrusive_key_comparator(), f );
 584         }
 585
 586         /// Deletes the item from the list using \p pred predicate for searching
 587         /**
 588             The function is an analog of \ref cds_nonintrusive_LazyList_hp_erase_func "erase(Q const&, Func)"
 589             but \p pred is used for key comparing.
 590             \p Less functor has the interface like \p std::less.
 591             \p pred must imply the same element order as the comparator used for building the list.
 592         */
 593         template <typename Q, typename Less, typename Func>
 594         bool erase_with( Q const& key, Less pred, Func f )
 595         {
 596             return erase_at( head(), key, typename options::template less_wrapper<Less>::type(), f );
 597         }
 598
 599         /// Extracts the item from the list with specified \p key
 600         /** \anchor cds_nonintrusive_LazyList_hp_extract
 601             The function searches an item with key equal to \p key,
 602             unlinks it from the list, and returns it in \p dest parameter.
 603             If the item with key equal to \p key is not found the function returns \p false.
 604
 605             Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
 606
 607             @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
 608
 609             Usage:
 610             \code
 611             typedef cds::container::LazyList< cds::gc::HP, foo, my_traits >  ord_list;
 612             ord_list theList;
 613             // ...
 614             {
 615                 ord_list::guarded_ptr gp;
 616                 theList.extract( gp, 5 );
 617                 // Deal with gp
 618                 // ...
 619
 620                 // Destructor of gp releases internal HP guard and frees the item
 621             }
 622             \endcode
 623         */
 624         template <typename Q>
 625         bool extract( guarded_ptr& dest, Q const& key )
 626         {
 627             return extract_at( head(), dest.guard(), key, intrusive_key_comparator() );
 628         }
 629
 630         /// Extracts the item from the list with comparing functor \p pred
 631         /**
 632             The function is an analog of \ref cds_nonintrusive_LazyList_hp_extract "extract(guarded_ptr&, Q const&)"
 633             but \p pred predicate is used for key comparing.
 634
 635             \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
 636             in any order.
 637             \p pred must imply the same element order as the comparator used for building the list.
 638         */
 639         template <typename Q, typename Less>
 640         bool extract_with( guarded_ptr& dest, Q const& key, Less pred )
 641         {
 642             return extract_at( head(), dest.guard(), key, typename options::template less_wrapper<Less>::type() );
 643         }
 644
 645         /// Finds the key \p key
 646         /** \anchor cds_nonintrusive_LazyList_hp_find_val
 647             The function searches the item with key equal to \p key
 648             and returns \p true if it is found, and \p false otherwise
 649         */
 650         template <typename Q>
 651         bool find( Q const& key )
 652         {
 653             return find_at( head(), key, intrusive_key_comparator() );
 654         }
 655
 656         /// Finds the key \p val using \p pred predicate for searching
 657         /**
 658             The function is an analog of \ref cds_nonintrusive_LazyList_hp_find_val "find(Q const&)"
 659             but \p pred is used for key comparing.
 660             \p Less functor has the interface like \p std::less.
 661             \p pred must imply the same element order as the comparator used for building the list.
 662         */
 663         template <typename Q, typename Less>
 664         bool find_with( Q const& key, Less pred )
 665         {
 666             return find_at( head(), key, typename options::template less_wrapper<Less>::type() );
 667         }
 668
 669         /// Finds the key \p val and performs an action with it
 670         /** \anchor cds_nonintrusive_LazyList_hp_find_func
 671             The function searches an item with key equal to \p val and calls the functor \p f for the item found.
 672             The interface of \p Func functor is:
 673             \code
 674             struct functor {
 675                 void operator()( value_type& item, Q& val );
 676             };
 677             \endcode
 678             where \p item is the item found, \p val is the <tt>find</tt> function argument.
 679
 680             You may pass \p f argument by reference using <tt>boost::ref</tt> or cds::ref.
 681
 682             The functor may change non-key fields of \p item. Note that the function is only guarantee
 683             that \p item cannot be deleted during functor is executing.
 684             The function does not serialize simultaneous access to the list \p item. If such access is
 685             possible you must provide your own synchronization schema to exclude unsafe item modifications.
 686
 687             The \p val argument is non-const since it can be used as \p f functor destination i.e., the functor
 688             may modify both arguments.
 689
 690             The function returns \p true if \p val is found, \p false otherwise.
 691         */
 692         template <typename Q, typename Func>
 693         bool find( Q& val, Func f )
 694         {
 695             return find_at( head(), val, intrusive_key_comparator(), f );
 696         }
 697
 698         /// Finds the key \p val using \p pred predicate for searching
 699         /**
 700             The function is an analog of \ref cds_nonintrusive_LazyList_hp_find_func "find(Q&, Func)"
 701             but \p pred is used for key comparing.
 702             \p Less functor has the interface like \p std::less.
 703             \p pred must imply the same element order as the comparator used for building the list.
 704         */
 705         template <typename Q, typename Less, typename Func>
 706         bool find_with( Q& val, Less pred, Func f )
 707         {
 708             return find_at( head(), val, typename options::template less_wrapper<Less>::type(), f );
 709         }
 710
 711         /// Finds the key \p val and performs an action with it
 712         /** \anchor cds_nonintrusive_LazyList_hp_find_cfunc
 713             The function searches an item with key equal to \p val and calls the functor \p f for the item found.
 714             The interface of \p Func functor is:
 715             \code
 716             struct functor {
 717                 void operator()( value_type& item, Q const& val );
 718             };
 719             \endcode
 720             where \p item is the item found, \p val is the <tt>find</tt> function argument.
 721
 722             You may pass \p f argument by reference using <tt>boost::ref</tt> or cds::ref.
 723
 724             The function does not serialize simultaneous access to the list \p item. If such access is
 725             possible you must provide your own synchronization schema to exclude unsafe item modifications.
 726
 727             The function returns \p true if \p val is found, \p false otherwise.
 728         */
 729         template <typename Q, typename Func>
 730         bool find( Q const& val, Func f )
 731         {
 732             return find_at( head(), val, intrusive_key_comparator(), f );
 733         }
 734
 735         /// Finds the key \p val using \p pred predicate for searching
 736         /**
 737             The function is an analog of \ref cds_nonintrusive_LazyList_hp_find_cfunc "find(Q&, Func)"
 738             but \p pred is used for key comparing.
 739             \p Less functor has the interface like \p std::less.
 740             \p pred must imply the same element order as the comparator used for building the list.
 741         */
 742         template <typename Q, typename Less, typename Func>
 743         bool find_with( Q const& val, Less pred, Func f )
 744         {
 745             return find_at( head(), val, typename options::template less_wrapper<Less>::type(), f );
 746         }
 747
 748         /// Finds the key \p val and return the item found
 749         /** \anchor cds_nonintrusive_LazyList_hp_get
 750             The function searches the item with key equal to \p val
 751             and assigns the item found to guarded pointer \p ptr.
 752             The function returns \p true if \p val is found, and \p false otherwise.
 753             If \p val is not found the \p ptr parameter is not changed.
 754
 755             @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
 756
 757             Usage:
 758             \code
 759             typedef cds::container::LazyList< cds::gc::HP, foo, my_traits >  ord_list;
 760             ord_list theList;
 761             // ...
 762             {
 763                 ord_list::guarded_ptr gp;
 764                 if ( theList.get( gp, 5 )) {
 765                     // Deal with gp
 766                     //...
 767                 }
 768                 // Destructor of guarded_ptr releases internal HP guard and frees the item
 769             }
 770             \endcode
 771
 772             Note the compare functor specified for class \p Traits template parameter
 773             should accept a parameter of type \p Q that can be not the same as \p value_type.
 774         */
 775         template <typename Q>
 776         bool get( guarded_ptr& ptr, Q const& val )
 777         {
 778             return get_at( head(), ptr.guard(), val, intrusive_key_comparator() );
 779         }
 780
 781         /// Finds the key \p val and return the item found
 782         /**
 783             The function is an analog of \ref cds_nonintrusive_LazyList_hp_get "get( guarded_ptr& ptr, Q const&)"
 784             but \p pred is used for comparing the keys.
 785
 786             \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
 787             in any order.
 788             \p pred must imply the same element order as the comparator used for building the list.
 789         */
 790         template <typename Q, typename Less>
 791         bool get_with( guarded_ptr& ptr, Q const& val, Less pred )
 792         {
 793             return get_at( head(), ptr.guard(), val, typename options::template less_wrapper<Less>::type() );
 794         }
 795
 796         /// Checks if the list is empty
 797         bool empty() const
 798         {
 799             return base_class::empty();
 800         }
 801
 802         /// Returns list's item count
 803         /**
 804             The value returned depends on opt::item_counter option. For atomicity::empty_item_counter,
 805             this function always returns 0.
 806
 807             <b>Warning</b>: even if you use real item counter and it returns 0, this fact is not mean that the list
 808             is empty. To check list emptyness use \ref empty() method.
 809         */
 810         size_t size() const
 811         {
 812             return base_class::size();
 813         }
 814
 815         /// Clears the list
 816         /**
 817             Post-condition: the list is empty
 818         */
 819         void clear()
 820         {
 821             base_class::clear();
 822         }
 823
 824     protected:
 825         //@cond
 826         bool insert_node_at( head_type& refHead, node_type * pNode )
 827         {
 828             assert( pNode != nullptr );
 829             scoped_node_ptr p( pNode );
 830
 831             if ( base_class::insert_at( &refHead, *pNode )) {
 832                 p.release();
 833                 return true;
 834             }
 835
 836             return false;
 837         }
 838
 839         template <typename Q>
 840         bool insert_at( head_type& refHead, const Q& val )
 841         {
 842             return insert_node_at( refHead, alloc_node( val ));
 843         }
 844
 845 #   ifdef CDS_EMPLACE_SUPPORT
 846         template <typename... Args>
 847         bool emplace_at( head_type& refHead, Args&&... args )
 848         {
 849             return insert_node_at( refHead, alloc_node( std::forward<Args>(args)... ));
 850         }
 851 #   endif
 852
 853         template <typename Q, typename Func>
 854         bool insert_at( head_type& refHead, const Q& key, Func f )
 855         {
 856             scoped_node_ptr pNode( alloc_node( key ));
 857
 858 #   ifdef CDS_CXX11_LAMBDA_SUPPORT
 859 #       ifdef CDS_BUG_STATIC_MEMBER_IN_LAMBDA
 860             // GCC 4.5-4.7: node_to_value is unaccessible from lambda,
 861             // like as MichaelList::node_to_value that requires to capture *this* despite on node_to_value is static function
 862             value_type& (* n2v)( node_type& ) = node_to_value;
 863             if ( base_class::insert_at( &refHead, *pNode, [&f,n2v](node_type& node){ cds::unref(f)( n2v(node) ); } ))
 864 #       else
 865             if ( base_class::insert_at( &refHead, *pNode, [&f](node_type& node){ cds::unref(f)( node_to_value(node) ); } ))
 866 #       endif
 867 #   else
 868             insert_functor<Func>  wrapper( f );
 869             if ( base_class::insert_at( &refHead, *pNode, cds::ref(wrapper) ))
 870 #   endif
 871             {
 872                 pNode.release();
 873                 return true;
 874             }
 875             return false;
 876         }
 877
 878         template <typename Q, typename Compare, typename Func>
 879         bool erase_at( head_type& refHead, const Q& key, Compare cmp, Func f )
 880         {
 881 #   ifdef CDS_CXX11_LAMBDA_SUPPORT
 882 #       ifdef CDS_BUG_STATIC_MEMBER_IN_LAMBDA
 883             // GCC 4.5-4.7: node_to_value is unaccessible from lambda,
 884             // like as MichaelList::node_to_value that requires to capture *this* despite on node_to_value is static function
 885             value_type const& (* n2v)( node_type const& ) = node_to_value;
 886             return base_class::erase_at( &refHead, key, cmp, [&f,n2v](node_type const& node){ cds::unref(f)( n2v(node) ); } );
 887 #       else
 888             return base_class::erase_at( &refHead, key, cmp, [&f](node_type const& node){ cds::unref(f)( node_to_value(node) ); } );
 889 #       endif
 890 #   else
 891             erase_functor<Func> wrapper( f );
 892             return base_class::erase_at( &refHead, key, cmp, cds::ref(wrapper) );
 893 #   endif
 894         }
 895
 896         template <typename Q, typename Compare>
 897         bool extract_at( head_type& refHead, typename gc::Guard& dest, Q const& key, Compare cmp )
 898         {
 899             return base_class::extract_at( &refHead, dest, key, cmp );
 900         }
 901
 902         template <typename Q, typename Func>
 903         std::pair<bool, bool> ensure_at( head_type& refHead, const Q& key, Func f )
 904         {
 905             scoped_node_ptr pNode( alloc_node( key ));
 906
 907 #   ifdef CDS_CXX11_LAMBDA_SUPPORT
 908 #       ifdef CDS_BUG_STATIC_MEMBER_IN_LAMBDA
 909             // GCC 4.5-4.7: node_to_value is unaccessible from lambda,
 910             // like as MichaelList::node_to_value that requires to capture *this* despite on node_to_value is static function
 911             value_type& (* n2v)( node_type& ) = node_to_value;
 912             std::pair<bool, bool> ret = base_class::ensure_at( &refHead, *pNode,
 913                 [&f, &key, n2v](bool bNew, node_type& node, node_type&){cds::unref(f)( bNew, n2v(node), key ); });
 914 #       else
 915             std::pair<bool, bool> ret = base_class::ensure_at( &refHead, *pNode,
 916                 [&f, &key](bool bNew, node_type& node, node_type&){cds::unref(f)( bNew, node_to_value(node), key ); });
 917 #       endif
 918 #   else
 919             ensure_functor<Q, Func> wrapper( key, f );
 920             std::pair<bool, bool> ret = base_class::ensure_at( &refHead, *pNode, cds::ref(wrapper));
 921 #   endif
 922             if ( ret.first && ret.second )
 923                 pNode.release();
 924
 925             return ret;
 926         }
 927
 928         template <typename Q, typename Compare>
 929         bool find_at( head_type& refHead, Q const& key, Compare cmp )
 930         {
 931             return base_class::find_at( &refHead, key, cmp );
 932         }
 933
 934         template <typename Q, typename Compare, typename Func>
 935         bool find_at( head_type& refHead, Q& val, Compare cmp, Func f )
 936         {
 937 #   ifdef CDS_CXX11_LAMBDA_SUPPORT
 938 #       ifdef CDS_BUG_STATIC_MEMBER_IN_LAMBDA
 939             // GCC 4.5-4.7: node_to_value is unaccessible from lambda,
 940             // like as MichaelList::node_to_value that requires to capture *this* despite on node_to_value is static function
 941             value_type& (* n2v)( node_type& ) = node_to_value;
 942             return base_class::find_at( &refHead, val, cmp, [&f,n2v](node_type& node, Q& val){ cds::unref(f)( n2v(node), val ); });
 943 #       else
 944             return base_class::find_at( &refHead, val, cmp, [&f](node_type& node, Q& val){ cds::unref(f)( node_to_value(node), val ); });
 945 #       endif
 946 #   else
 947             find_functor<Func>  wrapper( f );
 948             return base_class::find_at( &refHead, val, cmp, cds::ref(wrapper) );
 949 #   endif
 950         }
 951
 952         template <typename Q, typename Compare>
 953         bool get_at( head_type& refHead, typename gc::Guard& guard, Q const& key, Compare cmp )
 954         {
 955             return base_class::get_at( &refHead, guard, key, cmp );
 956         }
 957
 958         //@endcond
 959     };
 960
 961 }} // namespace cds::container
 962
 963 #endif // #ifndef __CDS_CONTAINER_LAZY_LIST_IMPL_H