cds/container/lazy_kvlist_impl.h

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