cds/container/impl/skip_list_map.h

   1 //$$CDS-header$$
   2
   3 #ifndef CDSLIB_CONTAINER_IMPL_SKIP_LIST_MAP_H
   4 #define CDSLIB_CONTAINER_IMPL_SKIP_LIST_MAP_H
   5
   6 #include <cds/container/details/guarded_ptr_cast.h>
   7
   8 namespace cds { namespace container {
   9
  10     /// Lock-free skip-list map
  11     /** @ingroup cds_nonintrusive_map
  12         \anchor cds_nonintrusive_SkipListMap_hp
  13
  14         The implementation of well-known probabilistic data structure called skip-list
  15         invented by W.Pugh in his papers:
  16             - [1989] W.Pugh Skip Lists: A Probabilistic Alternative to Balanced Trees
  17             - [1990] W.Pugh A Skip List Cookbook
  18
  19         A skip-list is a probabilistic data structure that provides expected logarithmic
  20         time search without the need of rebalance. The skip-list is a collection of sorted
  21         linked list. Nodes are ordered by key. Each node is linked into a subset of the lists.
  22         Each list has a level, ranging from 0 to 32. The bottom-level list contains
  23         all the nodes, and each higher-level list is a sublist of the lower-level lists.
  24         Each node is created with a random top level (with a random height), and belongs
  25         to all lists up to that level. The probability that a node has the height 1 is 1/2.
  26         The probability that a node has the height N is 1/2 ** N (more precisely,
  27         the distribution depends on an random generator provided, but our generators
  28         have this property).
  29
  30         The lock-free variant of skip-list is implemented according to book
  31             - [2008] M.Herlihy, N.Shavit "The Art of Multiprocessor Programming",
  32                 chapter 14.4 "A Lock-Free Concurrent Skiplist"
  33
  34         Template arguments:
  35         - \p GC - Garbage collector used.
  36         - \p K - type of a key to be stored in the list.
  37         - \p T - type of a value to be stored in the list.
  38         - \p Traits - map traits, default is \p skip_list::traits
  39             It is possible to declare option-based list with \p cds::container::skip_list::make_traits metafunction
  40             istead of \p Traits template argument.
  41
  42         Like STL map class, \p %SkipListMap stores the key-value pair as <tt>std:pair< K const, T></tt>.
  43
  44         @warning The skip-list requires up to 67 hazard pointers that may be critical for some GCs for which
  45             the guard count is limited (like \p gc::HP). Those GCs should be explicitly initialized with
  46             hazard pointer enough: \code cds::gc::HP myhp( 67 ) \endcode. Otherwise an run-time exception may be raised
  47             when you try to create skip-list object.
  48
  49         @note There are several specializations of \p %SkipListMap for each \p GC. You should include:
  50         - <tt><cds/container/skip_list_map_hp.h></tt> for \p gc::HP garbage collector
  51         - <tt><cds/container/skip_list_map_dhp.h></tt> for \p gc::DHP garbage collector
  52         - <tt><cds/container/skip_list_map_rcu.h></tt> for \ref cds_nonintrusive_SkipListMap_rcu "RCU type"
  53         - <tt><cds/container/skip_list_map_nogc.h></tt> for \ref cds_nonintrusive_SkipListMap_nogc "non-deletable SkipListMap"
  54
  55         <b>Iterators</b>
  56
  57         The class supports a forward iterator (\ref iterator and \ref const_iterator).
  58         The iteration is ordered.
  59         The iterator object is thread-safe: the element pointed by the iterator object is guarded,
  60         so, the element cannot be reclaimed while the iterator object is alive.
  61         However, passing an iterator object between threads is dangerous.
  62
  63         \warning Due to concurrent nature of skip-list map it is not guarantee that you can iterate
  64         all elements in the map: any concurrent deletion can exclude the element
  65         pointed by the iterator from the map, and your iteration can be terminated
  66         before end of the map. Therefore, such iteration is more suitable for debugging purpose only
  67
  68         Remember, each iterator object requires 2 additional hazard pointers, that may be
  69         a limited resource for \p GC like \p gc::HP (for gc::DHP the count of
  70         guards is unlimited).
  71
  72         The iterator class supports the following minimalistic interface:
  73         \code
  74         struct iterator {
  75             // Default ctor
  76             iterator();
  77
  78             // Copy ctor
  79             iterator( iterator const& s);
  80
  81             value_type * operator ->() const;
  82             value_type& operator *() const;
  83
  84             // Pre-increment
  85             iterator& operator ++();
  86
  87             // Copy assignment
  88             iterator& operator = (const iterator& src);
  89
  90             bool operator ==(iterator const& i ) const;
  91             bool operator !=(iterator const& i ) const;
  92         };
  93         \endcode
  94         Note, the iterator object returned by \ref end, \ cend member functions points to \p nullptr and should not be dereferenced.
  95
  96     */
  97     template <
  98         typename GC,
  99         typename Key,
 100         typename T,
 101 #ifdef CDS_DOXYGEN_INVOKED
 102         typename Traits = skip_list::traits
 103 #else
 104         typename Traits
 105 #endif
 106     >
 107     class SkipListMap:
 108 #ifdef CDS_DOXYGEN_INVOKED
 109         protected intrusive::SkipListSet< GC, std::pair<Key const, T>, Traits >
 110 #else
 111         protected details::make_skip_list_map< GC, Key, T, Traits >::type
 112 #endif
 113     {
 114         //@cond
 115         typedef details::make_skip_list_map< GC, Key, T, Traits > maker;
 116         typedef typename maker::type base_class;
 117         //@endcond
 118     public:
 119         typedef GC      gc;          ///< Garbage collector
 120         typedef Key     key_type;    ///< Key type
 121         typedef T       mapped_type; ///< Mapped type
 122         typedef Traits  traits;      ///< Map traits
 123 #   ifdef CDS_DOXYGEN_INVOKED
 124         typedef std::pair< Key const, T> value_type;   ///< Key-value pair to be stored in the map
 125 #   else
 126         typedef typename maker::value_type  value_type;
 127 #   endif
 128
 129         typedef typename base_class::back_off      back_off;       ///< Back-off strategy
 130         typedef typename traits::allocator         allocator_type; ///< Allocator type used for allocate/deallocate the skip-list nodes
 131         typedef typename base_class::item_counter  item_counter;   ///< Item counting policy used
 132         typedef typename maker::key_comparator     key_comparator; ///< key comparison functor
 133         typedef typename base_class::memory_model  memory_model;   ///< Memory ordering, see \p cds::opt::memory_model
 134         typedef typename traits::random_level_generator random_level_generator ; ///< random level generator
 135         typedef typename traits::stat              stat;           ///< internal statistics type
 136
 137     protected:
 138         //@cond
 139         typedef typename maker::node_type           node_type;
 140         typedef typename maker::node_allocator      node_allocator;
 141
 142         typedef std::unique_ptr< node_type, typename maker::node_deallocator >    scoped_node_ptr;
 143         //@endcond
 144
 145     public:
 146         /// Guarded pointer
 147         typedef typename gc::template guarded_ptr< node_type, value_type, details::guarded_ptr_cast_set<node_type, value_type> > guarded_ptr;
 148
 149     protected:
 150         //@cond
 151         unsigned int random_level()
 152         {
 153             return base_class::random_level();
 154         }
 155         //@endcond
 156
 157     public:
 158         /// Default ctor
 159         SkipListMap()
 160             : base_class()
 161         {}
 162
 163         /// Destructor destroys the set object
 164         ~SkipListMap()
 165         {}
 166
 167     public:
 168         /// Iterator type
 169         typedef skip_list::details::iterator< typename base_class::iterator >  iterator;
 170
 171         /// Const iterator type
 172         typedef skip_list::details::iterator< typename base_class::const_iterator >   const_iterator;
 173
 174         /// Returns a forward iterator addressing the first element in a map
 175         iterator begin()
 176         {
 177             return iterator( base_class::begin() );
 178         }
 179
 180         /// Returns a forward const iterator addressing the first element in a map
 181         const_iterator begin() const
 182         {
 183             return cbegin();
 184         }
 185         /// Returns a forward const iterator addressing the first element in a map
 186         const_iterator cbegin() const
 187         {
 188             return const_iterator( base_class::cbegin() );
 189         }
 190
 191         /// Returns a forward iterator that addresses the location succeeding the last element in a map.
 192         iterator end()
 193         {
 194             return iterator( base_class::end() );
 195         }
 196
 197         /// Returns a forward const iterator that addresses the location succeeding the last element in a map.
 198         const_iterator end() const
 199         {
 200             return cend();
 201         }
 202         /// Returns a forward const iterator that addresses the location succeeding the last element in a map.
 203         const_iterator cend() const
 204         {
 205             return const_iterator( base_class::cend() );
 206         }
 207
 208     public:
 209         /// Inserts new node with key and default value
 210         /**
 211             The function creates a node with \p key and default value, and then inserts the node created into the map.
 212
 213             Preconditions:
 214             - The \p key_type should be constructible from a value of type \p K.
 215                 In trivial case, \p K is equal to \p key_type.
 216             - The \p mapped_type should be default-constructible.
 217
 218             Returns \p true if inserting successful, \p false otherwise.
 219         */
 220         template <typename K>
 221         bool insert( K const& key )
 222         {
 223             return insert_with( key, [](value_type&){} );
 224         }
 225
 226         /// Inserts new node
 227         /**
 228             The function creates a node with copy of \p val value
 229             and then inserts the node created into the map.
 230
 231             Preconditions:
 232             - The \p key_type should be constructible from \p key of type \p K.
 233             - The \p value_type should be constructible from \p val of type \p V.
 234
 235             Returns \p true if \p val is inserted into the set, \p false otherwise.
 236         */
 237         template <typename K, typename V>
 238         bool insert( K const& key, V const& val )
 239         {
 240             return insert_with( key, [&val](value_type& item) { item.second = val ; } );
 241         }
 242
 243         /// Inserts new node and initialize it by a functor
 244         /**
 245             This function inserts new node with key \p key and if inserting is successful then it calls
 246             \p func functor with signature
 247             \code
 248                 struct functor {
 249                     void operator()( value_type& item );
 250                 };
 251             \endcode
 252
 253             The argument \p item of user-defined functor \p func is the reference
 254             to the map's item inserted:
 255                 - <tt>item.first</tt> is a const reference to item's key that cannot be changed.
 256                 - <tt>item.second</tt> is a reference to item's value that may be changed.
 257
 258             \p key_type should be constructible from value of type \p K.
 259
 260             The function allows to split creating of new item into two part:
 261             - create item from \p key;
 262             - insert new item into the map;
 263             - if inserting is successful, initialize the value of item by calling \p func functor
 264
 265             This can be useful if complete initialization of object of \p value_type is heavyweight and
 266             it is preferable that the initialization should be completed only if inserting is successful.
 267         */
 268         template <typename K, typename Func>
 269         bool insert_with( K const& key, Func func )
 270         {
 271             scoped_node_ptr pNode( node_allocator().New( random_level(), key ));
 272             if ( base_class::insert( *pNode, [&func]( node_type& item ) { func( item.m_Value ); } )) {
 273                 pNode.release();
 274                 return true;
 275             }
 276             return false;
 277         }
 278
 279         /// For key \p key inserts data of type \p value_type created in-place from <tt>std::forward<Args>(args)...</tt>
 280         /**
 281             Returns \p true if inserting successful, \p false otherwise.
 282         */
 283         template <typename K, typename... Args>
 284         bool emplace( K&& key, Args&&... args )
 285         {
 286             scoped_node_ptr pNode( node_allocator().New( random_level(), std::forward<K>(key), std::forward<Args>(args)... ));
 287             if ( base_class::insert( *pNode )) {
 288                 pNode.release();
 289                 return true;
 290             }
 291             return false;
 292         }
 293
 294         /// Updates data by \p key
 295         /**
 296             The operation performs inserting or changing data with lock-free manner.
 297
 298             If the \p key not found in the map, then the new item created from \p key
 299             will be inserted into the map iff \p bInsert is \p true
 300             (note that in this case the \ref key_type should be constructible from type \p K).
 301             Otherwise, if \p key is found, the functor \p func is called with item found.
 302             The functor \p Func signature:
 303             \code
 304                 struct my_functor {
 305                     void operator()( bool bNew, value_type& item );
 306                 };
 307             \endcode
 308             where:
 309             - \p bNew - \p true if the item has been inserted, \p false otherwise
 310             - \p item - item of the map
 311
 312             The functor may change any fields of the \p item.second that is \ref value_type.
 313
 314             Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successfull,
 315             \p second is \p true if new item has been added or \p false if \p key already exists.
 316
 317             @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
 318         */
 319         template <typename K, typename Func>
 320         std::pair<bool, bool> update( K const& key, Func func, bool bInsert = true )
 321         {
 322             scoped_node_ptr pNode( node_allocator().New( random_level(), key ));
 323             std::pair<bool, bool> res = base_class::update( *pNode,
 324                 [&func](bool bNew, node_type& item, node_type const& ){ func( bNew, item.m_Value );},
 325                 bInsert
 326             );
 327             if ( res.first && res.second )
 328                 pNode.release();
 329             return res;
 330         }
 331         //@cond
 332         template <typename K, typename Func>
 333         CDS_DEPRECATED("ensure() is deprecated, use update()")
 334         std::pair<bool, bool> ensure( K const& key, Func func )
 335         {
 336             return update( key, func, true );
 337         }
 338         //@endcond
 339
 340         /// Delete \p key from the map
 341         /** \anchor cds_nonintrusive_SkipListMap_erase_val
 342
 343             Return \p true if \p key is found and deleted, \p false otherwise
 344         */
 345         template <typename K>
 346         bool erase( K const& key )
 347         {
 348             return base_class::erase(key);
 349         }
 350
 351         /// Deletes the item from the map using \p pred predicate for searching
 352         /**
 353             The function is an analog of \ref cds_nonintrusive_SkipListMap_erase_val "erase(K const&)"
 354             but \p pred is used for key comparing.
 355             \p Less functor has the interface like \p std::less.
 356             \p Less must imply the same element order as the comparator used for building the map.
 357         */
 358         template <typename K, typename Less>
 359         bool erase_with( K const& key, Less pred )
 360         {
 361             CDS_UNUSED( pred );
 362             return base_class::erase_with( key, cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor >());
 363         }
 364
 365         /// Delete \p key from the map
 366         /** \anchor cds_nonintrusive_SkipListMap_erase_func
 367
 368             The function searches an item with key \p key, calls \p f functor
 369             and deletes the item. If \p key is not found, the functor is not called.
 370
 371             The functor \p Func interface:
 372             \code
 373             struct extractor {
 374                 void operator()(value_type& item) { ... }
 375             };
 376             \endcode
 377
 378             Return \p true if key is found and deleted, \p false otherwise
 379         */
 380         template <typename K, typename Func>
 381         bool erase( K const& key, Func f )
 382         {
 383             return base_class::erase( key, [&f]( node_type& node) { f( node.m_Value ); } );
 384         }
 385
 386         /// Deletes the item from the map using \p pred predicate for searching
 387         /**
 388             The function is an analog of \ref cds_nonintrusive_SkipListMap_erase_func "erase(K const&, Func)"
 389             but \p pred is used for key comparing.
 390             \p Less functor has the interface like \p std::less.
 391             \p Less must imply the same element order as the comparator used for building the map.
 392         */
 393         template <typename K, typename Less, typename Func>
 394         bool erase_with( K const& key, Less pred, Func f )
 395         {
 396             CDS_UNUSED( pred );
 397             return base_class::erase_with( key,
 398                 cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor >(),
 399                 [&f]( node_type& node) { f( node.m_Value ); } );
 400         }
 401
 402         /// Extracts the item from the map with specified \p key
 403         /** \anchor cds_nonintrusive_SkipListMap_hp_extract
 404             The function searches an item with key equal to \p key in the map,
 405             unlinks it from the map, and returns a guarded pointer to the item found.
 406             If \p key is not found the function returns an empty guarded pointer.
 407
 408             Note the compare functor should accept a parameter of type \p K that can be not the same as \p key_type.
 409
 410             The item extracted is freed automatically by garbage collector \p GC
 411             when returned \p guarded_ptr object will be destroyed or released.
 412             @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
 413
 414             Usage:
 415             \code
 416             typedef cds::container::SkipListMap< cds::gc::HP, int, foo, my_traits >  skip_list;
 417             skip_list theList;
 418             // ...
 419             {
 420                 skip_list::guarded_ptr gp( theList.extract( 5 ));
 421                 if ( gp ) {
 422                     // Deal with gp
 423                     // ...
 424                 }
 425                 // Destructor of gp releases internal HP guard and frees the pointer
 426             }
 427             \endcode
 428         */
 429         template <typename K>
 430         guarded_ptr extract( K const& key )
 431         {
 432             guarded_ptr gp;
 433             base_class::extract_( gp.guard(), key, typename base_class::key_comparator() );
 434             return gp;
 435         }
 436
 437         /// Extracts the item from the map with comparing functor \p pred
 438         /**
 439             The function is an analog of \ref cds_nonintrusive_SkipListMap_hp_extract "extract(K const&)"
 440             but \p pred predicate is used for key comparing.
 441
 442             \p Less functor has the semantics like \p std::less but should take arguments of type \ref key_type and \p K
 443             in any order.
 444             \p pred must imply the same element order as the comparator used for building the map.
 445         */
 446         template <typename K, typename Less>
 447         guarded_ptr extract_with( K const& key, Less pred )
 448         {
 449             CDS_UNUSED( pred );
 450             typedef cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor >  wrapped_less;
 451             guarded_ptr gp;
 452             base_class::extract_( gp.guard(), key, cds::opt::details::make_comparator_from_less<wrapped_less>() );
 453             return gp;
 454         }
 455
 456         /// Extracts an item with minimal key from the map
 457         /**
 458             The function searches an item with minimal key, unlinks it, and returns an guarded pointer to the item found.
 459             If the skip-list is empty the function returns an empty guarded pointer.
 460
 461             The item extracted is freed automatically by garbage collector \p GC
 462             when returned \p guarded_ptr object will be destroyed or released.
 463             @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
 464
 465             Usage:
 466             \code
 467             typedef cds::continer::SkipListMap< cds::gc::HP, int, foo, my_traits >  skip_list;
 468             skip_list theList;
 469             // ...
 470             {
 471                 skip_list::guarded_ptr gp( theList.extract_min());
 472                 if ( gp ) {
 473                     // Deal with gp
 474                     //...
 475                 }
 476                 // Destructor of gp releases internal HP guard and then frees the pointer
 477             }
 478             \endcode
 479         */
 480         guarded_ptr extract_min()
 481         {
 482             guarded_ptr gp;
 483             base_class::extract_min_( gp.guard() );
 484             return gp;
 485         }
 486
 487         /// Extracts an item with maximal key from the map
 488         /**
 489             The function searches an item with maximal key, unlinks it, and returns a guarded pointer to item found.
 490             If the skip-list is empty the function returns an empty \p guarded_ptr.
 491
 492             The item found is freed by garbage collector \p GC automatically
 493             when returned \p guarded_ptr object will be destroyed or released.
 494             @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
 495
 496             Usage:
 497             \code
 498             typedef cds::container::SkipListMap< cds::gc::HP, int, foo, my_traits >  skip_list;
 499             skip_list theList;
 500             // ...
 501             {
 502                 skip_list::guarded_ptr gp( theList.extract_max());
 503                 if ( gp ) {
 504                     // Deal with gp
 505                     //...
 506                 }
 507                 // Destructor of gp releases internal HP guard and then frees the pointer
 508             }
 509             \endcode
 510         */
 511         guarded_ptr extract_max()
 512         {
 513             guarded_ptr gp;
 514             base_class::extract_max_( gp.guard() );
 515             return gp;
 516         }
 517
 518         /// Find the key \p key
 519         /** \anchor cds_nonintrusive_SkipListMap_find_cfunc
 520
 521             The function searches the item with key equal to \p key and calls the functor \p f for item found.
 522             The interface of \p Func functor is:
 523             \code
 524             struct functor {
 525                 void operator()( value_type& item );
 526             };
 527             \endcode
 528             where \p item is the item found.
 529
 530             The functor may change \p item.second.
 531
 532             The function returns \p true if \p key is found, \p false otherwise.
 533         */
 534         template <typename K, typename Func>
 535         bool find( K const& key, Func f )
 536         {
 537             return base_class::find( key, [&f](node_type& item, K const& ) { f( item.m_Value );});
 538         }
 539
 540         /// Finds the key \p val using \p pred predicate for searching
 541         /**
 542             The function is an analog of \ref cds_nonintrusive_SkipListMap_find_cfunc "find(K const&, Func)"
 543             but \p pred is used for key comparing.
 544             \p Less functor has the interface like \p std::less.
 545             \p Less must imply the same element order as the comparator used for building the map.
 546         */
 547         template <typename K, typename Less, typename Func>
 548         bool find_with( K const& key, Less pred, Func f )
 549         {
 550             CDS_UNUSED( pred );
 551             return base_class::find_with( key,
 552                 cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor >(),
 553                 [&f](node_type& item, K const& ) { f( item.m_Value );});
 554         }
 555
 556         /// Checks whether the map contains \p key
 557         /**
 558             The function searches the item with key equal to \p key
 559             and returns \p true if it is found, and \p false otherwise.
 560         */
 561         template <typename K>
 562         bool contains( K const& key )
 563         {
 564             return base_class::contains( key );
 565         }
 566         //@cond
 567         template <typename K>
 568         CDS_DEPRECATED("deprecated, use contains()")
 569         bool find( K const& key )
 570         {
 571             return contains( key );
 572         }
 573         //@endcond
 574
 575         /// Checks whether the set contains \p key using \p pred predicate for searching
 576         /**
 577             The function is similar to <tt>contains( key )</tt> but \p pred is used for key comparing.
 578             \p Less functor has the interface like \p std::less.
 579             \p Less must imply the same element order as the comparator used for building the set.
 580         */
 581         template <typename K, typename Less>
 582         bool contains( K const& key, Less pred )
 583         {
 584             CDS_UNUSED( pred );
 585             return base_class::contains( key, cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor >() );
 586         }
 587         //@cond
 588         template <typename K, typename Less>
 589         CDS_DEPRECATED("deprecated, use contains()")
 590         bool find_with( K const& key, Less pred )
 591         {
 592             return contains( key, pred );
 593         }
 594         //@endcond
 595
 596         /// Finds the key \p key and return the item found
 597         /** \anchor cds_nonintrusive_SkipListMap_hp_get
 598             The function searches the item with key equal to \p key
 599             and returns a guarded pointer to the item found.
 600             If \p key is not found the function returns an empty guarded pointer.
 601
 602             It is safe when a concurrent thread erases the item returned as \p guarded_ptr.
 603             In this case the item will be freed later by garbage collector \p GC automatically
 604             when \p guarded_ptr object will be destroyed or released.
 605             @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
 606
 607             Usage:
 608             \code
 609             typedef cds::container::SkipListMap< cds::gc::HP, int, foo, my_traits >  skip_list;
 610             skip_list theList;
 611             // ...
 612             {
 613                 skip_list::guarded_ptr gp( theList.get( 5 ));
 614                 if ( gp ) {
 615                     // Deal with gp
 616                     //...
 617                 }
 618                 // Destructor of guarded_ptr releases internal HP guard
 619             }
 620             \endcode
 621
 622             Note the compare functor specified for class \p Traits template parameter
 623             should accept a parameter of type \p K that can be not the same as \p value_type.
 624         */
 625         template <typename K>
 626         guarded_ptr get( K const& key )
 627         {
 628             guarded_ptr gp;
 629             base_class::get_with_( gp.guard(), key, typename base_class::key_comparator() );
 630             return gp;
 631         }
 632
 633         /// Finds the key \p key and return the item found
 634         /**
 635             The function is an analog of \ref cds_nonintrusive_SkipListMap_hp_get "get( K const&)"
 636             but \p pred is used for comparing the keys.
 637
 638             \p Less functor has the semantics like \p std::less but should take arguments of type \ref key_type and \p K
 639             in any order.
 640             \p pred must imply the same element order as the comparator used for building the map.
 641         */
 642         template <typename K, typename Less>
 643         guarded_ptr get_with( K const& key, Less pred )
 644         {
 645             CDS_UNUSED( pred );
 646             typedef cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor > wrapped_less;
 647             guarded_ptr gp;
 648             base_class::get_with_( gp.guard(), key, cds::opt::details::make_comparator_from_less< wrapped_less >());
 649             return gp;
 650         }
 651
 652         /// Clears the map
 653         void clear()
 654         {
 655             base_class::clear();
 656         }
 657
 658         /// Checks if the map is empty
 659         bool empty() const
 660         {
 661             return base_class::empty();
 662         }
 663
 664         /// Returns item count in the map
 665         size_t size() const
 666         {
 667             return base_class::size();
 668         }
 669
 670         /// Returns const reference to internal statistics
 671         stat const& statistics() const
 672         {
 673             return base_class::statistics();
 674         }
 675     };
 676 }} // namespace cds::container
 677
 678 #endif // #ifndef CDSLIB_CONTAINER_IMPL_SKIP_LIST_MAP_H