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         //@cond
 138         typedef cds::container::skip_list::implementation_tag implementation_tag;
 139         //@endcond
 140
 141     protected:
 142         //@cond
 143         typedef typename maker::node_type           node_type;
 144         typedef typename maker::node_allocator      node_allocator;
 145
 146         typedef std::unique_ptr< node_type, typename maker::node_deallocator >    scoped_node_ptr;
 147         //@endcond
 148
 149     public:
 150         /// Guarded pointer
 151         typedef typename gc::template guarded_ptr< node_type, value_type, details::guarded_ptr_cast_set<node_type, value_type> > guarded_ptr;
 152
 153     protected:
 154         //@cond
 155         unsigned int random_level()
 156         {
 157             return base_class::random_level();
 158         }
 159         //@endcond
 160
 161     public:
 162         /// Default ctor
 163         SkipListMap()
 164             : base_class()
 165         {}
 166
 167         /// Destructor destroys the set object
 168         ~SkipListMap()
 169         {}
 170
 171     public:
 172         /// Iterator type
 173         typedef skip_list::details::iterator< typename base_class::iterator >  iterator;
 174
 175         /// Const iterator type
 176         typedef skip_list::details::iterator< typename base_class::const_iterator >   const_iterator;
 177
 178         /// Returns a forward iterator addressing the first element in a map
 179         iterator begin()
 180         {
 181             return iterator( base_class::begin() );
 182         }
 183
 184         /// Returns a forward const iterator addressing the first element in a map
 185         const_iterator begin() const
 186         {
 187             return cbegin();
 188         }
 189         /// Returns a forward const iterator addressing the first element in a map
 190         const_iterator cbegin() const
 191         {
 192             return const_iterator( base_class::cbegin() );
 193         }
 194
 195         /// Returns a forward iterator that addresses the location succeeding the last element in a map.
 196         iterator end()
 197         {
 198             return iterator( base_class::end() );
 199         }
 200
 201         /// Returns a forward const iterator that addresses the location succeeding the last element in a map.
 202         const_iterator end() const
 203         {
 204             return cend();
 205         }
 206         /// Returns a forward const iterator that addresses the location succeeding the last element in a map.
 207         const_iterator cend() const
 208         {
 209             return const_iterator( base_class::cend() );
 210         }
 211
 212     public:
 213         /// Inserts new node with key and default value
 214         /**
 215             The function creates a node with \p key and default value, and then inserts the node created into the map.
 216
 217             Preconditions:
 218             - The \p key_type should be constructible from a value of type \p K.
 219                 In trivial case, \p K is equal to \p key_type.
 220             - The \p mapped_type should be default-constructible.
 221
 222             Returns \p true if inserting successful, \p false otherwise.
 223         */
 224         template <typename K>
 225         bool insert( K const& key )
 226         {
 227             return insert_with( key, [](value_type&){} );
 228         }
 229
 230         /// Inserts new node
 231         /**
 232             The function creates a node with copy of \p val value
 233             and then inserts the node created into the map.
 234
 235             Preconditions:
 236             - The \p key_type should be constructible from \p key of type \p K.
 237             - The \p value_type should be constructible from \p val of type \p V.
 238
 239             Returns \p true if \p val is inserted into the set, \p false otherwise.
 240         */
 241         template <typename K, typename V>
 242         bool insert( K const& key, V const& val )
 243         {
 244             return insert_with( key, [&val](value_type& item) { item.second = val ; } );
 245         }
 246
 247         /// Inserts new node and initialize it by a functor
 248         /**
 249             This function inserts new node with key \p key and if inserting is successful then it calls
 250             \p func functor with signature
 251             \code
 252                 struct functor {
 253                     void operator()( value_type& item );
 254                 };
 255             \endcode
 256
 257             The argument \p item of user-defined functor \p func is the reference
 258             to the map's item inserted:
 259                 - <tt>item.first</tt> is a const reference to item's key that cannot be changed.
 260                 - <tt>item.second</tt> is a reference to item's value that may be changed.
 261
 262             \p key_type should be constructible from value of type \p K.
 263
 264             The function allows to split creating of new item into two part:
 265             - create item from \p key;
 266             - insert new item into the map;
 267             - if inserting is successful, initialize the value of item by calling \p func functor
 268
 269             This can be useful if complete initialization of object of \p value_type is heavyweight and
 270             it is preferable that the initialization should be completed only if inserting is successful.
 271         */
 272         template <typename K, typename Func>
 273         bool insert_with( K const& key, Func func )
 274         {
 275             scoped_node_ptr pNode( node_allocator().New( random_level(), key ));
 276             if ( base_class::insert( *pNode, [&func]( node_type& item ) { func( item.m_Value ); } )) {
 277                 pNode.release();
 278                 return true;
 279             }
 280             return false;
 281         }
 282
 283         /// For key \p key inserts data of type \p value_type created in-place from <tt>std::forward<Args>(args)...</tt>
 284         /**
 285             Returns \p true if inserting successful, \p false otherwise.
 286         */
 287         template <typename K, typename... Args>
 288         bool emplace( K&& key, Args&&... args )
 289         {
 290             scoped_node_ptr pNode( node_allocator().New( random_level(), std::forward<K>(key), std::forward<Args>(args)... ));
 291             if ( base_class::insert( *pNode )) {
 292                 pNode.release();
 293                 return true;
 294             }
 295             return false;
 296         }
 297
 298         /// Updates data by \p key
 299         /**
 300             The operation performs inserting or changing data with lock-free manner.
 301
 302             If the \p key not found in the map, then the new item created from \p key
 303             will be inserted into the map iff \p bInsert is \p true
 304             (note that in this case the \ref key_type should be constructible from type \p K).
 305             Otherwise, if \p key is found, the functor \p func is called with item found.
 306             The functor \p Func signature:
 307             \code
 308                 struct my_functor {
 309                     void operator()( bool bNew, value_type& item );
 310                 };
 311             \endcode
 312             where:
 313             - \p bNew - \p true if the item has been inserted, \p false otherwise
 314             - \p item - item of the map
 315
 316             The functor may change any fields of the \p item.second that is \ref value_type.
 317
 318             Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successfull,
 319             \p second is \p true if new item has been added or \p false if \p key already exists.
 320
 321             @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
 322         */
 323         template <typename K, typename Func>
 324         std::pair<bool, bool> update( K const& key, Func func, bool bInsert = true )
 325         {
 326             scoped_node_ptr pNode( node_allocator().New( random_level(), key ));
 327             std::pair<bool, bool> res = base_class::update( *pNode,
 328                 [&func](bool bNew, node_type& item, node_type const& ){ func( bNew, item.m_Value );},
 329                 bInsert
 330             );
 331             if ( res.first && res.second )
 332                 pNode.release();
 333             return res;
 334         }
 335
 336         //@cond
 337         // Deprecated, use update()
 338         template <typename K, typename Func>
 339         std::pair<bool, bool> ensure( K const& key, Func func )
 340         {
 341             return update( key, func, true );
 342         }
 343         //@endcond
 344
 345         /// Delete \p key from the map
 346         /** \anchor cds_nonintrusive_SkipListMap_erase_val
 347
 348             Return \p true if \p key is found and deleted, \p false otherwise
 349         */
 350         template <typename K>
 351         bool erase( K const& key )
 352         {
 353             return base_class::erase(key);
 354         }
 355
 356         /// Deletes the item from the map using \p pred predicate for searching
 357         /**
 358             The function is an analog of \ref cds_nonintrusive_SkipListMap_erase_val "erase(K const&)"
 359             but \p pred is used for key comparing.
 360             \p Less functor has the interface like \p std::less.
 361             \p Less must imply the same element order as the comparator used for building the map.
 362         */
 363         template <typename K, typename Less>
 364         bool erase_with( K const& key, Less pred )
 365         {
 366             CDS_UNUSED( pred );
 367             return base_class::erase_with( key, cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor >());
 368         }
 369
 370         /// Delete \p key from the map
 371         /** \anchor cds_nonintrusive_SkipListMap_erase_func
 372
 373             The function searches an item with key \p key, calls \p f functor
 374             and deletes the item. If \p key is not found, the functor is not called.
 375
 376             The functor \p Func interface:
 377             \code
 378             struct extractor {
 379                 void operator()(value_type& item) { ... }
 380             };
 381             \endcode
 382
 383             Return \p true if key is found and deleted, \p false otherwise
 384         */
 385         template <typename K, typename Func>
 386         bool erase( K const& key, Func f )
 387         {
 388             return base_class::erase( key, [&f]( node_type& node) { f( node.m_Value ); } );
 389         }
 390
 391         /// Deletes the item from the map using \p pred predicate for searching
 392         /**
 393             The function is an analog of \ref cds_nonintrusive_SkipListMap_erase_func "erase(K const&, Func)"
 394             but \p pred is used for key comparing.
 395             \p Less functor has the interface like \p std::less.
 396             \p Less must imply the same element order as the comparator used for building the map.
 397         */
 398         template <typename K, typename Less, typename Func>
 399         bool erase_with( K const& key, Less pred, Func f )
 400         {
 401             CDS_UNUSED( pred );
 402             return base_class::erase_with( key,
 403                 cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor >(),
 404                 [&f]( node_type& node) { f( node.m_Value ); } );
 405         }
 406
 407         /// Extracts the item from the map with specified \p key
 408         /** \anchor cds_nonintrusive_SkipListMap_hp_extract
 409             The function searches an item with key equal to \p key in the map,
 410             unlinks it from the map, and returns a guarded pointer to the item found.
 411             If \p key is not found the function returns an empty guarded pointer.
 412
 413             Note the compare functor should accept a parameter of type \p K that can be not the same as \p key_type.
 414
 415             The item extracted is freed automatically by garbage collector \p GC
 416             when returned \p guarded_ptr object will be destroyed or released.
 417             @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
 418
 419             Usage:
 420             \code
 421             typedef cds::container::SkipListMap< cds::gc::HP, int, foo, my_traits >  skip_list;
 422             skip_list theList;
 423             // ...
 424             {
 425                 skip_list::guarded_ptr gp( theList.extract( 5 ));
 426                 if ( gp ) {
 427                     // Deal with gp
 428                     // ...
 429                 }
 430                 // Destructor of gp releases internal HP guard and frees the pointer
 431             }
 432             \endcode
 433         */
 434         template <typename K>
 435         guarded_ptr extract( K const& key )
 436         {
 437             guarded_ptr gp;
 438             base_class::extract_( gp.guard(), key, typename base_class::key_comparator() );
 439             return gp;
 440         }
 441
 442         /// Extracts the item from the map with comparing functor \p pred
 443         /**
 444             The function is an analog of \ref cds_nonintrusive_SkipListMap_hp_extract "extract(K const&)"
 445             but \p pred predicate is used for key comparing.
 446
 447             \p Less functor has the semantics like \p std::less but should take arguments of type \ref key_type and \p K
 448             in any order.
 449             \p pred must imply the same element order as the comparator used for building the map.
 450         */
 451         template <typename K, typename Less>
 452         guarded_ptr extract_with( K const& key, Less pred )
 453         {
 454             CDS_UNUSED( pred );
 455             typedef cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor >  wrapped_less;
 456             guarded_ptr gp;
 457             base_class::extract_( gp.guard(), key, cds::opt::details::make_comparator_from_less<wrapped_less>() );
 458             return gp;
 459         }
 460
 461         /// Extracts an item with minimal key from the map
 462         /**
 463             The function searches an item with minimal key, unlinks it, and returns an guarded pointer to the item found.
 464             If the skip-list is empty the function returns an empty guarded pointer.
 465
 466             The item extracted is freed automatically by garbage collector \p GC
 467             when returned \p guarded_ptr object will be destroyed or released.
 468             @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
 469
 470             Usage:
 471             \code
 472             typedef cds::continer::SkipListMap< cds::gc::HP, int, foo, my_traits >  skip_list;
 473             skip_list theList;
 474             // ...
 475             {
 476                 skip_list::guarded_ptr gp( theList.extract_min());
 477                 if ( gp ) {
 478                     // Deal with gp
 479                     //...
 480                 }
 481                 // Destructor of gp releases internal HP guard and then frees the pointer
 482             }
 483             \endcode
 484         */
 485         guarded_ptr extract_min()
 486         {
 487             guarded_ptr gp;
 488             base_class::extract_min_( gp.guard() );
 489             return gp;
 490         }
 491
 492         /// Extracts an item with maximal key from the map
 493         /**
 494             The function searches an item with maximal key, unlinks it, and returns a guarded pointer to item found.
 495             If the skip-list is empty the function returns an empty \p guarded_ptr.
 496
 497             The item found is freed by garbage collector \p GC automatically
 498             when returned \p guarded_ptr object will be destroyed or released.
 499             @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
 500
 501             Usage:
 502             \code
 503             typedef cds::container::SkipListMap< cds::gc::HP, int, foo, my_traits >  skip_list;
 504             skip_list theList;
 505             // ...
 506             {
 507                 skip_list::guarded_ptr gp( theList.extract_max());
 508                 if ( gp ) {
 509                     // Deal with gp
 510                     //...
 511                 }
 512                 // Destructor of gp releases internal HP guard and then frees the pointer
 513             }
 514             \endcode
 515         */
 516         guarded_ptr extract_max()
 517         {
 518             guarded_ptr gp;
 519             base_class::extract_max_( gp.guard() );
 520             return gp;
 521         }
 522
 523         /// Find the key \p key
 524         /** \anchor cds_nonintrusive_SkipListMap_find_cfunc
 525
 526             The function searches the item with key equal to \p key and calls the functor \p f for item found.
 527             The interface of \p Func functor is:
 528             \code
 529             struct functor {
 530                 void operator()( value_type& item );
 531             };
 532             \endcode
 533             where \p item is the item found.
 534
 535             The functor may change \p item.second.
 536
 537             The function returns \p true if \p key is found, \p false otherwise.
 538         */
 539         template <typename K, typename Func>
 540         bool find( K const& key, Func f )
 541         {
 542             return base_class::find( key, [&f](node_type& item, K const& ) { f( item.m_Value );});
 543         }
 544
 545         /// Finds the key \p val using \p pred predicate for searching
 546         /**
 547             The function is an analog of \ref cds_nonintrusive_SkipListMap_find_cfunc "find(K const&, Func)"
 548             but \p pred is used for key comparing.
 549             \p Less functor has the interface like \p std::less.
 550             \p Less must imply the same element order as the comparator used for building the map.
 551         */
 552         template <typename K, typename Less, typename Func>
 553         bool find_with( K const& key, Less pred, Func f )
 554         {
 555             CDS_UNUSED( pred );
 556             return base_class::find_with( key,
 557                 cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor >(),
 558                 [&f](node_type& item, K const& ) { f( item.m_Value );});
 559         }
 560
 561         /// Find the key \p key
 562         /** \anchor cds_nonintrusive_SkipListMap_find_val
 563
 564             The function searches the item with key equal to \p key
 565             and returns \p true if it is found, and \p false otherwise.
 566         */
 567         template <typename K>
 568         bool find( K const& key )
 569         {
 570             return base_class::find( key );
 571         }
 572
 573         /// Finds the key \p val using \p pred predicate for searching
 574         /**
 575             The function is an analog of \ref cds_nonintrusive_SkipListMap_find_val "find(K const&)"
 576             but \p pred is used for key comparing.
 577             \p Less functor has the interface like \p std::less.
 578             \p Less must imply the same element order as the comparator used for building the map.
 579         */
 580         template <typename K, typename Less>
 581         bool find_with( K const& key, Less pred )
 582         {
 583             CDS_UNUSED( pred );
 584             return base_class::find_with( key, cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor >() );
 585         }
 586
 587         /// Finds the key \p key and return the item found
 588         /** \anchor cds_nonintrusive_SkipListMap_hp_get
 589             The function searches the item with key equal to \p key
 590             and returns an guarded pointer to the item found.
 591             If \p key is not found the function returns an empty guarded pointer.
 592
 593             It is safe when a concurrent thread erases the item returned as \p guarded_ptr.
 594             In this case the item will be freed later by garbage collector \p GC automatically
 595             when \p guarded_ptr object will be destroyed or released.
 596             @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
 597
 598             Usage:
 599             \code
 600             typedef cds::container::SkipListMap< cds::gc::HP, int, foo, my_traits >  skip_list;
 601             skip_list theList;
 602             // ...
 603             {
 604                 skip_list::guarded_ptr gp( theList.get( 5 ));
 605                 if ( gp ) {
 606                     // Deal with gp
 607                     //...
 608                 }
 609                 // Destructor of guarded_ptr releases internal HP guard
 610             }
 611             \endcode
 612
 613             Note the compare functor specified for class \p Traits template parameter
 614             should accept a parameter of type \p K that can be not the same as \p value_type.
 615         */
 616         template <typename K>
 617         guarded_ptr get( K const& key )
 618         {
 619             guarded_ptr gp;
 620             base_class::get_with_( gp.guard(), key, typename base_class::key_comparator() );
 621             return gp;
 622         }
 623
 624         /// Finds the key \p key and return the item found
 625         /**
 626             The function is an analog of \ref cds_nonintrusive_SkipListMap_hp_get "get( K const&)"
 627             but \p pred is used for comparing the keys.
 628
 629             \p Less functor has the semantics like \p std::less but should take arguments of type \ref key_type and \p K
 630             in any order.
 631             \p pred must imply the same element order as the comparator used for building the map.
 632         */
 633         template <typename K, typename Less>
 634         guarded_ptr get_with( K const& key, Less pred )
 635         {
 636             CDS_UNUSED( pred );
 637             typedef cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor > wrapped_less;
 638             guarded_ptr gp;
 639             base_class::get_with_( gp.guard(), key, cds::opt::details::make_comparator_from_less< wrapped_less >());
 640             return gp;
 641         }
 642
 643         /// Clears the map
 644         void clear()
 645         {
 646             base_class::clear();
 647         }
 648
 649         /// Checks if the map is empty
 650         bool empty() const
 651         {
 652             return base_class::empty();
 653         }
 654
 655         /// Returns item count in the map
 656         size_t size() const
 657         {
 658             return base_class::size();
 659         }
 660
 661         /// Returns const reference to internal statistics
 662         stat const& statistics() const
 663         {
 664             return base_class::statistics();
 665         }
 666     };
 667 }} // namespace cds::container
 668
 669 #endif // #ifndef CDSLIB_CONTAINER_IMPL_SKIP_LIST_MAP_H