cds/container/impl/skip_list_map.h

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