cds/container/skip_list_map_rcu.h

   1 //$$CDS-header$$
   2
   3 #ifndef __CDS_CONTAINER_SKIP_LIST_MAP_RCU_H
   4 #define __CDS_CONTAINER_SKIP_LIST_MAP_RCU_H
   5
   6 #include <cds/container/skip_list_base.h>
   7 #include <cds/intrusive/skip_list_rcu.h>
   8 #include <cds/container/details/make_skip_list_map.h>
   9 #include <cds/details/functor_wrapper.h>
  10
  11 namespace cds { namespace container {
  12
  13     /// Lock-free skip-list map (template specialization for \ref cds_urcu_desc "RCU")
  14     /** @ingroup cds_nonintrusive_map
  15         \anchor cds_nonintrusive_SkipListMap_rcu
  16
  17         The implementation of well-known probabilistic data structure called skip-list
  18         invented by W.Pugh in his papers:
  19             - [1989] W.Pugh Skip Lists: A Probabilistic Alternative to Balanced Trees
  20             - [1990] W.Pugh A Skip List Cookbook
  21
  22         A skip-list is a probabilistic data structure that provides expected logarithmic
  23         time search without the need of rebalance. The skip-list is a collection of sorted
  24         linked list. Nodes are ordered by key. Each node is linked into a subset of the lists.
  25         Each list has a level, ranging from 0 to 32. The bottom-level list contains
  26         all the nodes, and each higher-level list is a sublist of the lower-level lists.
  27         Each node is created with a random top level (with a random height), and belongs
  28         to all lists up to that level. The probability that a node has the height 1 is 1/2.
  29         The probability that a node has the height N is 1/2 ** N (more precisely,
  30         the distribution depends on an random generator provided, but our generators
  31         have this property).
  32
  33         The lock-free variant of skip-list is implemented according to book
  34             - [2008] M.Herlihy, N.Shavit "The Art of Multiprocessor Programming",
  35                 chapter 14.4 "A Lock-Free Concurrent Skiplist"
  36
  37         Template arguments:
  38         - \p RCU - one of \ref cds_urcu_gc "RCU type".
  39         - \p K - type of a key to be stored in the list.
  40         - \p T - type of a value to be stored in the list.
  41         - \p Traits - type traits. See skip_list::type_traits for explanation.
  42
  43         It is possible to declare option-based list with cds::container::skip_list::make_traits metafunction istead of \p Traits template
  44         argument.
  45         Template argument list \p Options of cds::container::skip_list::make_traits metafunction are:
  46         - opt::compare - key compare functor. No default functor is provided.
  47             If the option is not specified, the opt::less is used.
  48         - opt::less - specifies binary predicate used for key comparison. Default is \p std::less<K>.
  49         - opt::item_counter - the type of item counting feature. Default is \ref atomicity::empty_item_counter that is no item counting.
  50         - opt::memory_model - C++ memory ordering model. Can be opt::v::relaxed_ordering (relaxed memory model, the default)
  51             or opt::v::sequential_consistent (sequentially consisnent memory model).
  52         - skip_list::random_level_generator - random level generator. Can be skip_list::xorshift, skip_list::turbo_pascal or
  53             user-provided one. See skip_list::random_level_generator option description for explanation.
  54             Default is \p %skip_list::turbo_pascal.
  55         - opt::allocator - allocator for skip-list node. Default is \ref CDS_DEFAULT_ALLOCATOR.
  56         - opt::back_off - back-off strategy used. If the option is not specified, the cds::backoff::Default is used.
  57         - opt::stat - internal statistics. Available types: skip_list::stat, skip_list::empty_stat (the default)
  58         - opt::rcu_check_deadlock - a deadlock checking policy. Default is opt::v::rcu_throw_deadlock
  59
  60         Like STL map class, \p %SkipListMap stores its key-value pair as <tt>std:pair< K const, T></tt>.
  61
  62         @note Before including <tt><cds/container/skip_list_map_rcu.h></tt> you should include appropriate RCU header file,
  63         see \ref cds_urcu_gc "RCU type" for list of existing RCU class and corresponding header files.
  64
  65         <b>Iterators</b>
  66
  67         The class supports a forward iterator (\ref iterator and \ref const_iterator).
  68         The iteration is ordered.
  69         You may iterate over skip-list set items only under RCU lock.
  70         Only in this case the iterator is thread-safe since
  71         while RCU is locked any set's item cannot be reclaimed.
  72
  73         The requirement of RCU lock during iterating means that deletion of the elements (i.e. \ref erase)
  74         is not possible.
  75
  76         @warning The iterator object cannot be passed between threads
  77
  78         The iterator class supports the following minimalistic interface:
  79         \code
  80         struct iterator {
  81             // Default ctor
  82             iterator();
  83
  84             // Copy ctor
  85             iterator( iterator const& s);
  86
  87             value_type * operator ->() const;
  88             value_type& operator *() const;
  89
  90             // Pre-increment
  91             iterator& operator ++();
  92
  93             // Copy assignment
  94             iterator& operator = (const iterator& src);
  95
  96             bool operator ==(iterator const& i ) const;
  97             bool operator !=(iterator const& i ) const;
  98         };
  99         \endcode
 100         Note, the iterator object returned by \ref end, \p cend member functions points to \p nullptr and should not be dereferenced.
 101
 102     */
 103     template <
 104         typename RCU,
 105         typename Key,
 106         typename T,
 107 #ifdef CDS_DOXYGEN_INVOKED
 108         typename Traits = skip_list::type_traits
 109 #else
 110         typename Traits
 111 #endif
 112     >
 113     class SkipListMap< cds::urcu::gc< RCU >, Key, T, Traits >:
 114 #ifdef CDS_DOXYGEN_INVOKED
 115         protected intrusive::SkipListSet< cds::urcu::gc< RCU >, std::pair<Key const, T>, Traits >
 116 #else
 117         protected details::make_skip_list_map< cds::urcu::gc< RCU >, Key, T, Traits >::type
 118 #endif
 119     {
 120         //@cond
 121         typedef details::make_skip_list_map< cds::urcu::gc< RCU >, Key, T, Traits >    maker;
 122         typedef typename maker::type base_class;
 123         //@endcond
 124     public:
 125         typedef typename base_class::gc          gc  ; ///< Garbage collector used
 126         typedef Key     key_type    ;   ///< Key type
 127         typedef T       mapped_type ;   ///< Mapped type
 128 #   ifdef CDS_DOXYGEN_INVOKED
 129         typedef std::pair< K const, T> value_type   ;   ///< Value type stored in the map
 130 #   else
 131         typedef typename maker::value_type  value_type;
 132 #   endif
 133         typedef Traits  options     ;   ///< Options specified
 134
 135         typedef typename base_class::back_off       back_off        ;   ///< Back-off strategy used
 136         typedef typename options::allocator         allocator_type  ;   ///< Allocator type used for allocate/deallocate the skip-list nodes
 137         typedef typename base_class::item_counter   item_counter    ;   ///< Item counting policy used
 138         typedef typename maker::key_comparator      key_comparator  ;   ///< key comparison functor
 139         typedef typename base_class::memory_model   memory_model    ;   ///< Memory ordering. See cds::opt::memory_model option
 140         typedef typename options::random_level_generator random_level_generator ; ///< random level generator
 141         typedef typename options::stat              stat            ;   ///< internal statistics type
 142
 143     protected:
 144         //@cond
 145         typedef typename maker::node_type           node_type;
 146         typedef typename maker::node_allocator      node_allocator;
 147
 148         typedef std::unique_ptr< node_type, typename maker::node_deallocator >    scoped_node_ptr;
 149         //@endcond
 150
 151     public:
 152         typedef typename base_class::rcu_lock  rcu_lock;   ///< RCU scoped lock
 153         /// Group of \p extract_xxx functions do not require external locking
 154         static CDS_CONSTEXPR_CONST bool c_bExtractLockExternal = base_class::c_bExtractLockExternal;
 155
 156         /// pointer to extracted node
 157         typedef cds::urcu::exempt_ptr< gc, node_type, value_type, typename maker::intrusive_type_traits::disposer > exempt_ptr;
 158
 159     protected:
 160         //@cond
 161         unsigned int random_level()
 162         {
 163             return base_class::random_level();
 164         }
 165
 166         value_type * to_value_ptr( node_type * pNode ) const CDS_NOEXCEPT
 167         {
 168             return pNode ? &pNode->m_Value : nullptr;
 169         }
 170         //@endcond
 171
 172     protected:
 173         //@cond
 174 #   ifndef CDS_CXX11_LAMBDA_SUPPORT
 175         struct empty_insert_functor
 176         {
 177             void operator()( value_type& ) const
 178             {}
 179         };
 180
 181         template <typename Q>
 182         class insert_value_functor
 183         {
 184             Q const&    m_val;
 185         public:
 186             insert_value_functor( Q const& v)
 187                 : m_val(v)
 188             {}
 189
 190             void operator()( value_type& item )
 191             {
 192                 item.second = m_val;
 193             }
 194         };
 195
 196         template <typename Func>
 197         class insert_key_wrapper: protected cds::details::functor_wrapper<Func>
 198         {
 199             typedef cds::details::functor_wrapper<Func> base_class;
 200         public:
 201             insert_key_wrapper( Func f ): base_class(f) {}
 202
 203             void operator()( node_type& item )
 204             {
 205                 base_class::get()( item.m_Value );
 206             }
 207         };
 208
 209         template <typename Func>
 210         class ensure_wrapper: protected cds::details::functor_wrapper<Func>
 211         {
 212             typedef cds::details::functor_wrapper<Func> base_class;
 213         public:
 214             ensure_wrapper( Func f) : base_class(f) {}
 215
 216             void operator()( bool bNew, node_type& item, node_type const& )
 217             {
 218                 base_class::get()( bNew, item.m_Value );
 219             }
 220         };
 221
 222         template <typename Func>
 223         struct erase_functor
 224         {
 225             Func        m_func;
 226
 227             erase_functor( Func f )
 228                 : m_func(f)
 229             {}
 230
 231             void operator()( node_type& node )
 232             {
 233                 cds::unref(m_func)( node.m_Value );
 234             }
 235         };
 236
 237         template <typename Func>
 238         class find_wrapper: protected cds::details::functor_wrapper<Func>
 239         {
 240             typedef cds::details::functor_wrapper<Func> base_class;
 241         public:
 242             find_wrapper( Func f )
 243                 : base_class(f)
 244             {}
 245
 246             template <typename Q>
 247             void operator()( node_type& item, Q& val )
 248             {
 249                 base_class::get()( item.m_Value, val );
 250             }
 251         };
 252
 253         template <typename Func>
 254         struct extract_copy_wrapper
 255         {
 256             Func    m_func;
 257             extract_copy_wrapper( Func f )
 258                 : m_func(f)
 259             {}
 260
 261             template <typename Q>
 262             void operator()( Q& dest, node_type& src )
 263             {
 264                 cds::unref(m_func)(dest, src.m_Value);
 265             }
 266         };
 267
 268 #   endif  // #ifndef CDS_CXX11_LAMBDA_SUPPORT
 269         //@endcond
 270
 271     public:
 272         /// Default ctor
 273         SkipListMap()
 274             : base_class()
 275         {}
 276
 277         /// Destructor destroys the set object
 278         ~SkipListMap()
 279         {}
 280
 281     public:
 282         /// Iterator type
 283         typedef skip_list::details::iterator< typename base_class::iterator >  iterator;
 284
 285         /// Const iterator type
 286         typedef skip_list::details::iterator< typename base_class::const_iterator >   const_iterator;
 287
 288         /// Returns a forward iterator addressing the first element in a map
 289         iterator begin()
 290         {
 291             return iterator( base_class::begin() );
 292         }
 293
 294         /// Returns a forward const iterator addressing the first element in a map
 295         //@{
 296         const_iterator begin() const
 297         {
 298             return cbegin();
 299         }
 300         const_iterator cbegin()
 301         {
 302             return const_iterator( base_class::cbegin() );
 303         }
 304         //@}
 305
 306         /// Returns a forward iterator that addresses the location succeeding the last element in a map.
 307         iterator end()
 308         {
 309             return iterator( base_class::end() );
 310         }
 311
 312         /// Returns a forward const iterator that addresses the location succeeding the last element in a map.
 313         //@{
 314         const_iterator end() const
 315         {
 316             return cend();
 317         }
 318         const_iterator cend()
 319         {
 320             return const_iterator( base_class::cend() );
 321         }
 322         //@}
 323
 324     public:
 325         /// Inserts new node with key and default value
 326         /**
 327             The function creates a node with \p key and default value, and then inserts the node created into the map.
 328
 329             Preconditions:
 330             - The \ref key_type should be constructible from a value of type \p K.
 331                 In trivial case, \p K is equal to \ref key_type.
 332             - The \ref mapped_type should be default-constructible.
 333
 334             RCU \p synchronize method can be called. RCU should not be locked.
 335
 336             Returns \p true if inserting successful, \p false otherwise.
 337         */
 338         template <typename K>
 339         bool insert( K const& key )
 340         {
 341 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
 342             return insert_key( key, [](value_type&){} );
 343 #       else
 344             return insert_key( key, empty_insert_functor() );
 345 #       endif
 346         }
 347
 348         /// Inserts new node
 349         /**
 350             The function creates a node with copy of \p val value
 351             and then inserts the node created into the map.
 352
 353             Preconditions:
 354             - The \ref key_type should be constructible from \p key of type \p K.
 355             - The \ref value_type should be constructible from \p val of type \p V.
 356
 357             RCU \p synchronize method can be called. RCU should not be locked.
 358
 359             Returns \p true if \p val is inserted into the set, \p false otherwise.
 360         */
 361         template <typename K, typename V>
 362         bool insert( K const& key, V const& val )
 363         {
 364             /*
 365 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
 366             return insert_key( key, [&val](value_type& item) { item.second = val ; } );
 367 #       else
 368             insert_value_functor<V> f(val);
 369             return insert_key( key, cds::ref(f) );
 370 #       endif
 371             */
 372             scoped_node_ptr pNode( node_allocator().New( random_level(), key, val ));
 373             if ( base_class::insert( *pNode ))
 374             {
 375                 pNode.release();
 376                 return true;
 377             }
 378             return false;
 379         }
 380
 381         /// Inserts new node and initialize it by a functor
 382         /**
 383             This function inserts new node with key \p key and if inserting is successful then it calls
 384             \p func functor with signature
 385             \code
 386                 struct functor {
 387                     void operator()( value_type& item );
 388                 };
 389             \endcode
 390
 391             The argument \p item of user-defined functor \p func is the reference
 392             to the map's item inserted:
 393                 - <tt>item.first</tt> is a const reference to item's key that cannot be changed.
 394                 - <tt>item.second</tt> is a reference to item's value that may be changed.
 395
 396             The user-defined functor can be passed by reference using <tt>boost::ref</tt>
 397             and it is called only if inserting is successful.
 398
 399             The key_type should be constructible from value of type \p K.
 400
 401             The function allows to split creating of new item into two part:
 402             - create item from \p key;
 403             - insert new item into the map;
 404             - if inserting is successful, initialize the value of item by calling \p func functor
 405
 406             This can be useful if complete initialization of object of \p value_type is heavyweight and
 407             it is preferable that the initialization should be completed only if inserting is successful.
 408
 409             RCU \p synchronize method can be called. RCU should not be locked.
 410         */
 411         template <typename K, typename Func>
 412         bool insert_key( const K& key, Func func )
 413         {
 414             scoped_node_ptr pNode( node_allocator().New( random_level(), key ));
 415 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
 416             if ( base_class::insert( *pNode, [&func]( node_type& item ) { cds::unref(func)( item.m_Value ); } ))
 417 #       else
 418             insert_key_wrapper<Func> wrapper(func);
 419             if ( base_class::insert( *pNode, cds::ref(wrapper) ))
 420 #endif
 421             {
 422                 pNode.release();
 423                 return true;
 424             }
 425             return false;
 426         }
 427
 428         /// For key \p key inserts data of type \ref value_type constructed with <tt>std::forward<Args>(args)...</tt>
 429         /**
 430             Returns \p true if inserting successful, \p false otherwise.
 431
 432             RCU \p synchronize method can be called. RCU should not be locked.
 433         */
 434         template <typename K, typename... Args>
 435         bool emplace( K&& key, Args&&... args )
 436         {
 437             scoped_node_ptr pNode( node_allocator().New( random_level(), std::forward<K>(key), std::forward<Args>(args)... ));
 438             if ( base_class::insert( *pNode )) {
 439                 pNode.release();
 440                 return true;
 441             }
 442             return false;
 443         }
 444
 445         /// Ensures that the \p key exists in the map
 446         /**
 447             The operation performs inserting or changing data with lock-free manner.
 448
 449             If the \p key not found in the map, then the new item created from \p key
 450             is inserted into the map (note that in this case the \ref key_type should be
 451             constructible from type \p K).
 452             Otherwise, the functor \p func is called with item found.
 453             The functor \p Func may be a function with signature:
 454             \code
 455                 void func( bool bNew, value_type& item );
 456             \endcode
 457             or a functor:
 458             \code
 459                 struct my_functor {
 460                     void operator()( bool bNew, value_type& item );
 461                 };
 462             \endcode
 463
 464             with arguments:
 465             - \p bNew - \p true if the item has been inserted, \p false otherwise
 466             - \p item - item of the list
 467
 468             The functor may change any fields of the \p item.second that is \ref value_type.
 469
 470             You may pass \p func argument by reference using <tt>boost::ref</tt>.
 471
 472             RCU \p synchronize method can be called. RCU should not be locked.
 473
 474             Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
 475             \p second is true if new item has been added or \p false if the item with \p key
 476             already is in the list.
 477         */
 478         template <typename K, typename Func>
 479         std::pair<bool, bool> ensure( K const& key, Func func )
 480         {
 481             scoped_node_ptr pNode( node_allocator().New( random_level(), key ));
 482 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
 483             std::pair<bool, bool> res = base_class::ensure( *pNode,
 484                 [&func](bool bNew, node_type& item, node_type const& ){ cds::unref(func)( bNew, item.m_Value ); }
 485             );
 486 #       else
 487             ensure_wrapper<Func> wrapper( func );
 488             std::pair<bool, bool> res = base_class::ensure( *pNode, cds::ref(wrapper) );
 489 #       endif
 490             if ( res.first && res.second )
 491                 pNode.release();
 492             return res;
 493         }
 494
 495         /// Delete \p key from the map
 496         /**\anchor cds_nonintrusive_SkipListMap_rcu_erase_val
 497
 498             RCU \p synchronize method can be called. RCU should not be locked.
 499
 500             Return \p true if \p key is found and deleted, \p false otherwise
 501         */
 502         template <typename K>
 503         bool erase( K const& key )
 504         {
 505             return base_class::erase(key);
 506         }
 507
 508         /// Deletes the item from the map using \p pred predicate for searching
 509         /**
 510             The function is an analog of \ref cds_nonintrusive_SkipListMap_rcu_erase_val "erase(K const&)"
 511             but \p pred is used for key comparing.
 512             \p Less functor has the interface like \p std::less.
 513             \p Less must imply the same element order as the comparator used for building the map.
 514         */
 515         template <typename K, typename Less>
 516         bool erase_with( K const& key, Less pred )
 517         {
 518             return base_class::erase_with( key, cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor >());
 519         }
 520
 521         /// Delete \p key from the map
 522         /** \anchor cds_nonintrusive_SkipListMap_rcu_erase_func
 523
 524             The function searches an item with key \p key, calls \p f functor
 525             and deletes the item. If \p key is not found, the functor is not called.
 526
 527             The functor \p Func interface:
 528             \code
 529             struct extractor {
 530                 void operator()(value_type& item) { ... }
 531             };
 532             \endcode
 533             The functor may be passed by reference using <tt>boost:ref</tt>
 534
 535             RCU \p synchronize method can be called. RCU should not be locked.
 536
 537             Return \p true if key is found and deleted, \p false otherwise
 538         */
 539         template <typename K, typename Func>
 540         bool erase( K const& key, Func f )
 541         {
 542 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
 543             return base_class::erase( key, [&f]( node_type& node) { cds::unref(f)( node.m_Value ); } );
 544 #       else
 545             erase_functor<Func> wrapper(f);
 546             return base_class::erase( key, cds::ref(wrapper));
 547 #       endif
 548         }
 549
 550         /// Deletes the item from the map using \p pred predicate for searching
 551         /**
 552             The function is an analog of \ref cds_nonintrusive_SkipListMap_rcu_erase_func "erase(K const&, Func)"
 553             but \p pred is used for key comparing.
 554             \p Less functor has the interface like \p std::less.
 555             \p Less must imply the same element order as the comparator used for building the map.
 556         */
 557         template <typename K, typename Less, typename Func>
 558         bool erase_with( K const& key, Less pred, Func f )
 559         {
 560 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
 561             return base_class::erase_with( key, cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor >(),
 562                 [&f]( node_type& node) { cds::unref(f)( node.m_Value ); } );
 563 #       else
 564             erase_functor<Func> wrapper(f);
 565             return base_class::erase_with( key, cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor >(), cds::ref(wrapper));
 566 #       endif
 567         }
 568
 569         /// Extracts the item from the map with specified \p key
 570         /** \anchor cds_nonintrusive_SkipListMap_rcu_extract
 571             The function searches an item with key equal to \p key in the map,
 572             unlinks it from the set, and returns it in \p result parameter.
 573             If the item with key equal to \p key is not found the function returns \p false.
 574
 575             Note the compare functor from \p Traits class' template argument
 576             should accept a parameter of type \p K that can be not the same as \p key_type.
 577
 578             RCU \p synchronize method can be called. RCU should NOT be locked.
 579             The function does not free the item found.
 580             The item will be implicitly freed when \p result object is destroyed or when
 581             <tt>result.release()</tt> is called, see cds::urcu::exempt_ptr for explanation.
 582             @note Before reusing \p result object you should call its \p release() method.
 583         */
 584         template <typename K>
 585         bool extract( exempt_ptr& result, K const& key )
 586         {
 587             return base_class::do_extract( result, key );
 588         }
 589
 590         /// Extracts the item from the map with comparing functor \p pred
 591         /**
 592             The function is an analog of \ref cds_nonintrusive_SkipListMap_rcu_extract "extract(exempt_ptr&, K const&)"
 593             but \p pred predicate is used for key comparing.
 594             \p Less has the semantics like \p std::less.
 595             \p pred must imply the same element order as the comparator used for building the map.
 596         */
 597         template <typename K, typename Less>
 598         bool extract_with( exempt_ptr& result, K const& key, Less pred )
 599         {
 600             return base_class::do_extract_with( result, key, cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor >());
 601         }
 602
 603         /// Extracts an item with minimal key from the map
 604         /**
 605             The function searches an item with minimal key, unlinks it, and returns the item found in \p result parameter.
 606             If the skip-list is empty the function returns \p false.
 607
 608             RCU \p synchronize method can be called. RCU should NOT be locked.
 609             The function does not free the item found.
 610             The item will be implicitly freed when \p result object is destroyed or when
 611             <tt>result.release()</tt> is called, see cds::urcu::exempt_ptr for explanation.
 612             @note Before reusing \p result object you should call its \p release() method.
 613         */
 614         bool extract_min( exempt_ptr& result )
 615         {
 616             return base_class::do_extract_min(result);
 617         }
 618
 619         /// Extracts an item with maximal key from the map
 620         /**
 621             The function searches an item with maximal key, unlinks it from the set, and returns the item found
 622             in \p result parameter. If the skip-list is empty the function returns \p false.
 623
 624             RCU \p synchronize method can be called. RCU should NOT be locked.
 625             The function does not free the item found.
 626             The item will be implicitly freed when \p result object is destroyed or when
 627             <tt>result.release()</tt> is called, see cds::urcu::exempt_ptr for explanation.
 628             @note Before reusing \p result object you should call its \p release() method.
 629         */
 630         bool extract_max( exempt_ptr& result )
 631         {
 632             return base_class::do_extract_max(result);
 633         }
 634
 635         /// Find the key \p key
 636         /** \anchor cds_nonintrusive_SkipListMap_rcu_find_cfunc
 637
 638             The function searches the item with key equal to \p key and calls the functor \p f for item found.
 639             The interface of \p Func functor is:
 640             \code
 641             struct functor {
 642                 void operator()( value_type& item );
 643             };
 644             \endcode
 645             where \p item is the item found.
 646
 647             You can pass \p f argument by reference using <tt>boost::ref</tt> or cds::ref.
 648
 649             The functor may change \p item.second.
 650
 651             The function applies RCU lock internally.
 652
 653             The function returns \p true if \p key is found, \p false otherwise.
 654         */
 655         template <typename K, typename Func>
 656         bool find( K const& key, Func f )
 657         {
 658 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
 659             return base_class::find( key, [&f](node_type& item, K const& ) { cds::unref(f)( item.m_Value );});
 660 #       else
 661             find_wrapper<Func> wrapper(f);
 662             return base_class::find( key, cds::ref(wrapper) );
 663 #       endif
 664         }
 665
 666         /// Finds the key \p val using \p pred predicate for searching
 667         /**
 668             The function is an analog of \ref cds_nonintrusive_SkipListMap_rcu_find_cfunc "find(K const&, Func)"
 669             but \p pred is used for key comparing.
 670             \p Less functor has the interface like \p std::less.
 671             \p Less must imply the same element order as the comparator used for building the map.
 672         */
 673         template <typename K, typename Less, typename Func>
 674         bool find_with( K const& key, Less pred, Func f )
 675         {
 676 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
 677             return base_class::find_with( key, cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor >(),
 678                 [&f](node_type& item, K const& ) { cds::unref(f)( item.m_Value );});
 679 #       else
 680             find_wrapper<Func> wrapper(f);
 681             return base_class::find_with( key, cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor >(), cds::ref(wrapper) );
 682 #       endif
 683         }
 684
 685         /// Find the key \p key
 686         /** \anchor cds_nonintrusive_SkipListMap_rcu_find_val
 687
 688             The function searches the item with key equal to \p key
 689             and returns \p true if it is found, and \p false otherwise.
 690
 691             The function applies RCU lock internally.
 692         */
 693         template <typename K>
 694         bool find( K const& key )
 695         {
 696             return base_class::find( key );
 697         }
 698
 699         /// Finds the key \p val using \p pred predicate for searching
 700         /**
 701             The function is an analog of \ref cds_nonintrusive_SkipListMap_rcu_find_val "find(K const&)"
 702             but \p pred is used for key comparing.
 703             \p Less functor has the interface like \p std::less.
 704             \p Less must imply the same element order as the comparator used for building the map.
 705         */
 706         template <typename K, typename Less>
 707         bool find_with( K const& key, Less pred )
 708         {
 709             return base_class::find_with( key, cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor >() );
 710         }
 711
 712         /// Finds the key \p key and return the item found
 713         /** \anchor cds_nonintrusive_SkipListMap_rcu_get
 714             The function searches the item with key equal to \p key and returns the pointer to item found.
 715             If \p key is not found it returns \p nullptr.
 716
 717             Note the compare functor in \p Traits class' template argument
 718             should accept a parameter of type \p K that can be not the same as \p key_type.
 719
 720             RCU should be locked before call of this function.
 721             Returned item is valid only while RCU is locked:
 722             \code
 723             typedef cds::container::SkipListMap< cds::urcu::gc< cds::urcu::general_buffered<> >, int, foo, my_traits > skip_list;
 724             skip_list theList;
 725             // ...
 726             {
 727                 // Lock RCU
 728                 skip_list::rcu_lock lock;
 729
 730                 skip_list::value_type * pVal = theList.get( 5 );
 731                 // Deal with pVal
 732                 //...
 733
 734                 // Unlock RCU by rcu_lock destructor
 735                 // pVal can be freed at any time after RCU unlocking
 736             }
 737             \endcode
 738
 739             After RCU unlocking the \p %force_dispose member function can be called manually,
 740             see \ref force_dispose for explanation.
 741         */
 742         template <typename K>
 743         value_type * get( K const& key )
 744         {
 745             return to_value_ptr( base_class::get( key ));
 746         }
 747
 748         /// Finds the key \p key and return the item found
 749         /**
 750             The function is an analog of \ref cds_nonintrusive_SkipListMap_rcu_get "get(K const&)"
 751             but \p pred is used for comparing the keys.
 752
 753             \p Less functor has the semantics like \p std::less but should take arguments of type \ref key_type and \p K
 754             in any order.
 755             \p pred must imply the same element order as the comparator used for building the map.
 756         */
 757         template <typename K, typename Less>
 758         value_type * get_with( K const& key, Less pred )
 759         {
 760             return to_value_ptr( base_class::get_with( key, cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor >() ));
 761         }
 762
 763         /// Clears the map
 764         void clear()
 765         {
 766             base_class::clear();
 767         }
 768
 769         /// Checks if the map is empty
 770         /**
 771             Emptiness is checked by item counting: if item count is zero then the map is empty.
 772         */
 773         bool empty() const
 774         {
 775             return base_class::empty();
 776         }
 777
 778         /// Returns item count in the map
 779         size_t size() const
 780         {
 781             return base_class::size();
 782         }
 783
 784         /// Returns const reference to internal statistics
 785         stat const& statistics() const
 786         {
 787             return base_class::statistics();
 788         }
 789
 790         /// Clears internal list of ready-to-delete items passing them to RCU reclamation cycle
 791         /**
 792             See \ref cds_intrusive_SkipListSet_rcu_force_dispose "intrusive SkipListSet" for explanation
 793         */
 794         void force_dispose()
 795         {
 796             return base_class::force_dispose();
 797         }
 798     };
 799 }} // namespace cds::container
 800
 801 #endif // #ifndef __CDS_CONTAINER_SKIP_LIST_MAP_RCU_H