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 #   ifdef CDS_EMPLACE_SUPPORT
 429         /// For key \p key inserts data of type \ref value_type constructed with <tt>std::forward<Args>(args)...</tt>
 430         /**
 431             Returns \p true if inserting successful, \p false otherwise.
 432
 433             RCU \p synchronize method can be called. RCU should not be locked.
 434
 435             @note This function is available only for compiler that supports
 436             variadic template and move semantics
 437         */
 438         template <typename K, typename... Args>
 439         bool emplace( K&& key, Args&&... args )
 440         {
 441             scoped_node_ptr pNode( node_allocator().New( random_level(), std::forward<K>(key), std::forward<Args>(args)... ));
 442             if ( base_class::insert( *pNode )) {
 443                 pNode.release();
 444                 return true;
 445             }
 446             return false;
 447         }
 448 #   endif
 449
 450
 451         /// Ensures that the \p key exists in the map
 452         /**
 453             The operation performs inserting or changing data with lock-free manner.
 454
 455             If the \p key not found in the map, then the new item created from \p key
 456             is inserted into the map (note that in this case the \ref key_type should be
 457             constructible from type \p K).
 458             Otherwise, the functor \p func is called with item found.
 459             The functor \p Func may be a function with signature:
 460             \code
 461                 void func( bool bNew, value_type& item );
 462             \endcode
 463             or a functor:
 464             \code
 465                 struct my_functor {
 466                     void operator()( bool bNew, value_type& item );
 467                 };
 468             \endcode
 469
 470             with arguments:
 471             - \p bNew - \p true if the item has been inserted, \p false otherwise
 472             - \p item - item of the list
 473
 474             The functor may change any fields of the \p item.second that is \ref value_type.
 475
 476             You may pass \p func argument by reference using <tt>boost::ref</tt>.
 477
 478             RCU \p synchronize method can be called. RCU should not be locked.
 479
 480             Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
 481             \p second is true if new item has been added or \p false if the item with \p key
 482             already is in the list.
 483         */
 484         template <typename K, typename Func>
 485         std::pair<bool, bool> ensure( K const& key, Func func )
 486         {
 487             scoped_node_ptr pNode( node_allocator().New( random_level(), key ));
 488 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
 489             std::pair<bool, bool> res = base_class::ensure( *pNode,
 490                 [&func](bool bNew, node_type& item, node_type const& ){ cds::unref(func)( bNew, item.m_Value ); }
 491             );
 492 #       else
 493             ensure_wrapper<Func> wrapper( func );
 494             std::pair<bool, bool> res = base_class::ensure( *pNode, cds::ref(wrapper) );
 495 #       endif
 496             if ( res.first && res.second )
 497                 pNode.release();
 498             return res;
 499         }
 500
 501         /// Delete \p key from the map
 502         /**\anchor cds_nonintrusive_SkipListMap_rcu_erase_val
 503
 504             RCU \p synchronize method can be called. RCU should not be locked.
 505
 506             Return \p true if \p key is found and deleted, \p false otherwise
 507         */
 508         template <typename K>
 509         bool erase( K const& key )
 510         {
 511             return base_class::erase(key);
 512         }
 513
 514         /// Deletes the item from the map using \p pred predicate for searching
 515         /**
 516             The function is an analog of \ref cds_nonintrusive_SkipListMap_rcu_erase_val "erase(K const&)"
 517             but \p pred is used for key comparing.
 518             \p Less functor has the interface like \p std::less.
 519             \p Less must imply the same element order as the comparator used for building the map.
 520         */
 521         template <typename K, typename Less>
 522         bool erase_with( K const& key, Less pred )
 523         {
 524             return base_class::erase_with( key, cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor >());
 525         }
 526
 527         /// Delete \p key from the map
 528         /** \anchor cds_nonintrusive_SkipListMap_rcu_erase_func
 529
 530             The function searches an item with key \p key, calls \p f functor
 531             and deletes the item. If \p key is not found, the functor is not called.
 532
 533             The functor \p Func interface:
 534             \code
 535             struct extractor {
 536                 void operator()(value_type& item) { ... }
 537             };
 538             \endcode
 539             The functor may be passed by reference using <tt>boost:ref</tt>
 540
 541             RCU \p synchronize method can be called. RCU should not be locked.
 542
 543             Return \p true if key is found and deleted, \p false otherwise
 544         */
 545         template <typename K, typename Func>
 546         bool erase( K const& key, Func f )
 547         {
 548 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
 549             return base_class::erase( key, [&f]( node_type& node) { cds::unref(f)( node.m_Value ); } );
 550 #       else
 551             erase_functor<Func> wrapper(f);
 552             return base_class::erase( key, cds::ref(wrapper));
 553 #       endif
 554         }
 555
 556         /// Deletes the item from the map using \p pred predicate for searching
 557         /**
 558             The function is an analog of \ref cds_nonintrusive_SkipListMap_rcu_erase_func "erase(K const&, Func)"
 559             but \p pred is used for key comparing.
 560             \p Less functor has the interface like \p std::less.
 561             \p Less must imply the same element order as the comparator used for building the map.
 562         */
 563         template <typename K, typename Less, typename Func>
 564         bool erase_with( K const& key, Less pred, Func f )
 565         {
 566 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
 567             return base_class::erase_with( key, cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor >(),
 568                 [&f]( node_type& node) { cds::unref(f)( node.m_Value ); } );
 569 #       else
 570             erase_functor<Func> wrapper(f);
 571             return base_class::erase_with( key, cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor >(), cds::ref(wrapper));
 572 #       endif
 573         }
 574
 575         /// Extracts the item from the map with specified \p key
 576         /** \anchor cds_nonintrusive_SkipListMap_rcu_extract
 577             The function searches an item with key equal to \p key in the map,
 578             unlinks it from the set, and returns it in \p result parameter.
 579             If the item with key equal to \p key is not found the function returns \p false.
 580
 581             Note the compare functor from \p Traits class' template argument
 582             should accept a parameter of type \p K that can be not the same as \p key_type.
 583
 584             RCU \p synchronize method can be called. RCU should NOT be locked.
 585             The function does not free the item found.
 586             The item will be implicitly freed when \p result object is destroyed or when
 587             <tt>result.release()</tt> is called, see cds::urcu::exempt_ptr for explanation.
 588             @note Before reusing \p result object you should call its \p release() method.
 589         */
 590         template <typename K>
 591         bool extract( exempt_ptr& result, K const& key )
 592         {
 593             return base_class::do_extract( result, key );
 594         }
 595
 596         /// Extracts the item from the map with comparing functor \p pred
 597         /**
 598             The function is an analog of \ref cds_nonintrusive_SkipListMap_rcu_extract "extract(exempt_ptr&, K const&)"
 599             but \p pred predicate is used for key comparing.
 600             \p Less has the semantics like \p std::less.
 601             \p pred must imply the same element order as the comparator used for building the map.
 602         */
 603         template <typename K, typename Less>
 604         bool extract_with( exempt_ptr& result, K const& key, Less pred )
 605         {
 606             return base_class::do_extract_with( result, key, cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor >());
 607         }
 608
 609         /// Extracts an item with minimal key from the map
 610         /**
 611             The function searches an item with minimal key, unlinks it, and returns the item found in \p result parameter.
 612             If the skip-list is empty the function returns \p false.
 613
 614             RCU \p synchronize method can be called. RCU should NOT be locked.
 615             The function does not free the item found.
 616             The item will be implicitly freed when \p result object is destroyed or when
 617             <tt>result.release()</tt> is called, see cds::urcu::exempt_ptr for explanation.
 618             @note Before reusing \p result object you should call its \p release() method.
 619         */
 620         bool extract_min( exempt_ptr& result )
 621         {
 622             return base_class::do_extract_min(result);
 623         }
 624
 625         /// Extracts an item with maximal key from the map
 626         /**
 627             The function searches an item with maximal key, unlinks it from the set, and returns the item found
 628             in \p result parameter. If the skip-list is empty the function returns \p false.
 629
 630             RCU \p synchronize method can be called. RCU should NOT be locked.
 631             The function does not free the item found.
 632             The item will be implicitly freed when \p result object is destroyed or when
 633             <tt>result.release()</tt> is called, see cds::urcu::exempt_ptr for explanation.
 634             @note Before reusing \p result object you should call its \p release() method.
 635         */
 636         bool extract_max( exempt_ptr& result )
 637         {
 638             return base_class::do_extract_max(result);
 639         }
 640
 641         /// Find the key \p key
 642         /** \anchor cds_nonintrusive_SkipListMap_rcu_find_cfunc
 643
 644             The function searches the item with key equal to \p key and calls the functor \p f for item found.
 645             The interface of \p Func functor is:
 646             \code
 647             struct functor {
 648                 void operator()( value_type& item );
 649             };
 650             \endcode
 651             where \p item is the item found.
 652
 653             You can pass \p f argument by reference using <tt>boost::ref</tt> or cds::ref.
 654
 655             The functor may change \p item.second.
 656
 657             The function applies RCU lock internally.
 658
 659             The function returns \p true if \p key is found, \p false otherwise.
 660         */
 661         template <typename K, typename Func>
 662         bool find( K const& key, Func f )
 663         {
 664 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
 665             return base_class::find( key, [&f](node_type& item, K const& ) { cds::unref(f)( item.m_Value );});
 666 #       else
 667             find_wrapper<Func> wrapper(f);
 668             return base_class::find( key, cds::ref(wrapper) );
 669 #       endif
 670         }
 671
 672         /// Finds the key \p val using \p pred predicate for searching
 673         /**
 674             The function is an analog of \ref cds_nonintrusive_SkipListMap_rcu_find_cfunc "find(K const&, Func)"
 675             but \p pred is used for key comparing.
 676             \p Less functor has the interface like \p std::less.
 677             \p Less must imply the same element order as the comparator used for building the map.
 678         */
 679         template <typename K, typename Less, typename Func>
 680         bool find_with( K const& key, Less pred, Func f )
 681         {
 682 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
 683             return base_class::find_with( key, cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor >(),
 684                 [&f](node_type& item, K const& ) { cds::unref(f)( item.m_Value );});
 685 #       else
 686             find_wrapper<Func> wrapper(f);
 687             return base_class::find_with( key, cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor >(), cds::ref(wrapper) );
 688 #       endif
 689         }
 690
 691         /// Find the key \p key
 692         /** \anchor cds_nonintrusive_SkipListMap_rcu_find_val
 693
 694             The function searches the item with key equal to \p key
 695             and returns \p true if it is found, and \p false otherwise.
 696
 697             The function applies RCU lock internally.
 698         */
 699         template <typename K>
 700         bool find( K const& key )
 701         {
 702             return base_class::find( key );
 703         }
 704
 705         /// Finds the key \p val using \p pred predicate for searching
 706         /**
 707             The function is an analog of \ref cds_nonintrusive_SkipListMap_rcu_find_val "find(K const&)"
 708             but \p pred is used for key comparing.
 709             \p Less functor has the interface like \p std::less.
 710             \p Less must imply the same element order as the comparator used for building the map.
 711         */
 712         template <typename K, typename Less>
 713         bool find_with( K const& key, Less pred )
 714         {
 715             return base_class::find_with( key, cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor >() );
 716         }
 717
 718         /// Finds the key \p key and return the item found
 719         /** \anchor cds_nonintrusive_SkipListMap_rcu_get
 720             The function searches the item with key equal to \p key and returns the pointer to item found.
 721             If \p key is not found it returns \p nullptr.
 722
 723             Note the compare functor in \p Traits class' template argument
 724             should accept a parameter of type \p K that can be not the same as \p key_type.
 725
 726             RCU should be locked before call of this function.
 727             Returned item is valid only while RCU is locked:
 728             \code
 729             typedef cds::container::SkipListMap< cds::urcu::gc< cds::urcu::general_buffered<> >, int, foo, my_traits > skip_list;
 730             skip_list theList;
 731             // ...
 732             {
 733                 // Lock RCU
 734                 skip_list::rcu_lock lock;
 735
 736                 skip_list::value_type * pVal = theList.get( 5 );
 737                 // Deal with pVal
 738                 //...
 739
 740                 // Unlock RCU by rcu_lock destructor
 741                 // pVal can be freed at any time after RCU unlocking
 742             }
 743             \endcode
 744
 745             After RCU unlocking the \p %force_dispose member function can be called manually,
 746             see \ref force_dispose for explanation.
 747         */
 748         template <typename K>
 749         value_type * get( K const& key )
 750         {
 751             return to_value_ptr( base_class::get( key ));
 752         }
 753
 754         /// Finds the key \p key and return the item found
 755         /**
 756             The function is an analog of \ref cds_nonintrusive_SkipListMap_rcu_get "get(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 map.
 762         */
 763         template <typename K, typename Less>
 764         value_type * get_with( K const& key, Less pred )
 765         {
 766             return to_value_ptr( base_class::get_with( key, cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor >() ));
 767         }
 768
 769         /// Clears the map
 770         void clear()
 771         {
 772             base_class::clear();
 773         }
 774
 775         /// Checks if the map is empty
 776         /**
 777             Emptiness is checked by item counting: if item count is zero then the map is empty.
 778         */
 779         bool empty() const
 780         {
 781             return base_class::empty();
 782         }
 783
 784         /// Returns item count in the map
 785         size_t size() const
 786         {
 787             return base_class::size();
 788         }
 789
 790         /// Returns const reference to internal statistics
 791         stat const& statistics() const
 792         {
 793             return base_class::statistics();
 794         }
 795
 796         /// Clears internal list of ready-to-delete items passing them to RCU reclamation cycle
 797         /**
 798             See \ref cds_intrusive_SkipListSet_rcu_force_dispose "intrusive SkipListSet" for explanation
 799         */
 800         void force_dispose()
 801         {
 802             return base_class::force_dispose();
 803         }
 804     };
 805 }} // namespace cds::container
 806
 807 #endif // #ifndef __CDS_CONTAINER_SKIP_LIST_MAP_RCU_H