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/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< K 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( const K& 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         /// Ensures that the \p key exists in the map
 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             is inserted into the map (note that in this case the \ref key_type should be
 300             constructible from type \p K).
 301             Otherwise, the functor \p func is called with item found.
 302             The functor \p Func may be a function with signature:
 303             \code
 304                 void func( bool bNew, value_type& item );
 305             \endcode
 306             or a functor:
 307             \code
 308                 struct my_functor {
 309                     void operator()( bool bNew, value_type& item );
 310                 };
 311             \endcode
 312
 313             with arguments:
 314             - \p bNew - \p true if the item has been inserted, \p false otherwise
 315             - \p item - item of the list
 316
 317             The functor may change any fields of the \p item.second that is \ref value_type.
 318
 319             Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
 320             \p second is true if new item has been added or \p false if the item with \p key
 321             already is in the list.
 322
 323             @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
 324         */
 325         template <typename K, typename Func>
 326         std::pair<bool, bool> ensure( K const& key, Func func )
 327         {
 328             scoped_node_ptr pNode( node_allocator().New( random_level(), key ));
 329             std::pair<bool, bool> res = base_class::ensure( *pNode,
 330                 [&func](bool bNew, node_type& item, node_type const& ){ func( bNew, item.m_Value ); }
 331             );
 332             if ( res.first && res.second )
 333                 pNode.release();
 334             return res;
 335         }
 336
 337         /// Delete \p key from the map
 338         /** \anchor cds_nonintrusive_SkipListMap_erase_val
 339
 340             Return \p true if \p key is found and deleted, \p false otherwise
 341         */
 342         template <typename K>
 343         bool erase( K const& key )
 344         {
 345             return base_class::erase(key);
 346         }
 347
 348         /// Deletes the item from the map using \p pred predicate for searching
 349         /**
 350             The function is an analog of \ref cds_nonintrusive_SkipListMap_erase_val "erase(K const&)"
 351             but \p pred is used for key comparing.
 352             \p Less functor has the interface like \p std::less.
 353             \p Less must imply the same element order as the comparator used for building the map.
 354         */
 355         template <typename K, typename Less>
 356         bool erase_with( K const& key, Less pred )
 357         {
 358             CDS_UNUSED( pred );
 359             return base_class::erase_with( key, cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor >());
 360         }
 361
 362         /// Delete \p key from the map
 363         /** \anchor cds_nonintrusive_SkipListMap_erase_func
 364
 365             The function searches an item with key \p key, calls \p f functor
 366             and deletes the item. If \p key is not found, the functor is not called.
 367
 368             The functor \p Func interface:
 369             \code
 370             struct extractor {
 371                 void operator()(value_type& item) { ... }
 372             };
 373             \endcode
 374
 375             Return \p true if key is found and deleted, \p false otherwise
 376         */
 377         template <typename K, typename Func>
 378         bool erase( K const& key, Func f )
 379         {
 380             return base_class::erase( key, [&f]( node_type& node) { f( node.m_Value ); } );
 381         }
 382
 383         /// Deletes the item from the map using \p pred predicate for searching
 384         /**
 385             The function is an analog of \ref cds_nonintrusive_SkipListMap_erase_func "erase(K const&, Func)"
 386             but \p pred is used for key comparing.
 387             \p Less functor has the interface like \p std::less.
 388             \p Less must imply the same element order as the comparator used for building the map.
 389         */
 390         template <typename K, typename Less, typename Func>
 391         bool erase_with( K const& key, Less pred, Func f )
 392         {
 393             CDS_UNUSED( pred );
 394             return base_class::erase_with( key,
 395                 cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor >(),
 396                 [&f]( node_type& node) { f( node.m_Value ); } );
 397         }
 398
 399         /// Extracts the item from the map with specified \p key
 400         /** \anchor cds_nonintrusive_SkipListMap_hp_extract
 401             The function searches an item with key equal to \p key in the map,
 402             unlinks it from the map, and returns a guarded pointer to the item found.
 403             If \p key is not found the function returns an empty guarded pointer.
 404
 405             Note the compare functor should accept a parameter of type \p K that can be not the same as \p key_type.
 406
 407             The item extracted is freed automatically by garbage collector \p GC
 408             when returned \p guarded_ptr object will be destroyed or released.
 409             @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
 410
 411             Usage:
 412             \code
 413             typedef cds::container::SkipListMap< cds::gc::HP, int, foo, my_traits >  skip_list;
 414             skip_list theList;
 415             // ...
 416             {
 417                 skip_list::guarded_ptr gp( theList.extract( 5 ));
 418                 if ( gp ) {
 419                     // Deal with gp
 420                     // ...
 421                 }
 422                 // Destructor of gp releases internal HP guard and frees the pointer
 423             }
 424             \endcode
 425         */
 426         template <typename K>
 427         guarded_ptr extract( K const& key )
 428         {
 429             guarded_ptr gp;
 430             base_class::extract_( gp.guard(), key, typename base_class::key_comparator() );
 431             return gp;
 432         }
 433
 434         /// Extracts the item from the map with comparing functor \p pred
 435         /**
 436             The function is an analog of \ref cds_nonintrusive_SkipListMap_hp_extract "extract(K const&)"
 437             but \p pred predicate is used for key comparing.
 438
 439             \p Less functor has the semantics like \p std::less but should take arguments of type \ref key_type and \p K
 440             in any order.
 441             \p pred must imply the same element order as the comparator used for building the map.
 442         */
 443         template <typename K, typename Less>
 444         guarded_ptr extract_with( K const& key, Less pred )
 445         {
 446             CDS_UNUSED( pred );
 447             typedef cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor >  wrapped_less;
 448             guarded_ptr gp;
 449             base_class::extract_( gp.guard(), key, cds::opt::details::make_comparator_from_less<wrapped_less>() );
 450             return gp;
 451         }
 452
 453         /// Extracts an item with minimal key from the map
 454         /**
 455             The function searches an item with minimal key, unlinks it, and returns an guarded pointer to the item found.
 456             If the skip-list is empty the function returns an empty guarded pointer.
 457
 458             The item extracted is freed automatically by garbage collector \p GC
 459             when returned \p guarded_ptr object will be destroyed or released.
 460             @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
 461
 462             Usage:
 463             \code
 464             typedef cds::continer::SkipListMap< cds::gc::HP, int, foo, my_traits >  skip_list;
 465             skip_list theList;
 466             // ...
 467             {
 468                 skip_list::guarded_ptr gp( theList.extract_min());
 469                 if ( gp ) {
 470                     // Deal with gp
 471                     //...
 472                 }
 473                 // Destructor of gp releases internal HP guard and then frees the pointer
 474             }
 475             \endcode
 476         */
 477         guarded_ptr extract_min()
 478         {
 479             guarded_ptr gp;
 480             base_class::extract_min_( gp.guard() );
 481             return gp;
 482         }
 483
 484         /// Extracts an item with maximal key from the map
 485         /**
 486             The function searches an item with maximal key, unlinks it, and returns a guarded pointer to item found.
 487             If the skip-list is empty the function returns an empty \p guarded_ptr.
 488
 489             The item found is freed by garbage collector \p GC automatically
 490             when returned \p guarded_ptr object will be destroyed or released.
 491             @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
 492
 493             Usage:
 494             \code
 495             typedef cds::container::SkipListMap< cds::gc::HP, int, foo, my_traits >  skip_list;
 496             skip_list theList;
 497             // ...
 498             {
 499                 skip_list::guarded_ptr gp( theList.extract_max());
 500                 if ( gp ) {
 501                     // Deal with gp
 502                     //...
 503                 }
 504                 // Destructor of gp releases internal HP guard and then frees the pointer
 505             }
 506             \endcode
 507         */
 508         guarded_ptr extract_max()
 509         {
 510             guarded_ptr gp;
 511             base_class::extract_max_( gp.guard() );
 512             return gp;
 513         }
 514
 515         /// Find the key \p key
 516         /** \anchor cds_nonintrusive_SkipListMap_find_cfunc
 517
 518             The function searches the item with key equal to \p key and calls the functor \p f for item found.
 519             The interface of \p Func functor is:
 520             \code
 521             struct functor {
 522                 void operator()( value_type& item );
 523             };
 524             \endcode
 525             where \p item is the item found.
 526
 527             The functor may change \p item.second.
 528
 529             The function returns \p true if \p key is found, \p false otherwise.
 530         */
 531         template <typename K, typename Func>
 532         bool find( K const& key, Func f )
 533         {
 534             return base_class::find( key, [&f](node_type& item, K const& ) { f( item.m_Value );});
 535         }
 536
 537         /// Finds the key \p val using \p pred predicate for searching
 538         /**
 539             The function is an analog of \ref cds_nonintrusive_SkipListMap_find_cfunc "find(K const&, Func)"
 540             but \p pred is used for key comparing.
 541             \p Less functor has the interface like \p std::less.
 542             \p Less must imply the same element order as the comparator used for building the map.
 543         */
 544         template <typename K, typename Less, typename Func>
 545         bool find_with( K const& key, Less pred, Func f )
 546         {
 547             CDS_UNUSED( pred );
 548             return base_class::find_with( key,
 549                 cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor >(),
 550                 [&f](node_type& item, K const& ) { f( item.m_Value );});
 551         }
 552
 553         /// Find the key \p key
 554         /** \anchor cds_nonintrusive_SkipListMap_find_val
 555
 556             The function searches the item with key equal to \p key
 557             and returns \p true if it is found, and \p false otherwise.
 558         */
 559         template <typename K>
 560         bool find( K const& key )
 561         {
 562             return base_class::find( key );
 563         }
 564
 565         /// Finds the key \p val using \p pred predicate for searching
 566         /**
 567             The function is an analog of \ref cds_nonintrusive_SkipListMap_find_val "find(K const&)"
 568             but \p pred is used for key comparing.
 569             \p Less functor has the interface like \p std::less.
 570             \p Less must imply the same element order as the comparator used for building the map.
 571         */
 572         template <typename K, typename Less>
 573         bool find_with( K const& key, Less pred )
 574         {
 575             CDS_UNUSED( pred );
 576             return base_class::find_with( key, cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor >() );
 577         }
 578
 579         /// Finds the key \p key and return the item found
 580         /** \anchor cds_nonintrusive_SkipListMap_hp_get
 581             The function searches the item with key equal to \p key
 582             and returns an guarded pointer to the item found.
 583             If \p key is not found the function returns an empty guarded pointer.
 584
 585             It is safe when a concurrent thread erases the item returned as \p guarded_ptr.
 586             In this case the item will be freed later by garbage collector \p GC automatically
 587             when \p guarded_ptr object will be destroyed or released.
 588             @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
 589
 590             Usage:
 591             \code
 592             typedef cds::container::SkipListMap< cds::gc::HP, int, foo, my_traits >  skip_list;
 593             skip_list theList;
 594             // ...
 595             {
 596                 skip_list::guarded_ptr gp( theList.get( 5 ));
 597                 if ( gp ) {
 598                     // Deal with gp
 599                     //...
 600                 }
 601                 // Destructor of guarded_ptr releases internal HP guard
 602             }
 603             \endcode
 604
 605             Note the compare functor specified for class \p Traits template parameter
 606             should accept a parameter of type \p K that can be not the same as \p value_type.
 607         */
 608         template <typename K>
 609         guarded_ptr get( K const& key )
 610         {
 611             guarded_ptr gp;
 612             base_class::get_with_( gp.guard(), key, typename base_class::key_comparator() );
 613             return gp;
 614         }
 615
 616         /// Finds the key \p key and return the item found
 617         /**
 618             The function is an analog of \ref cds_nonintrusive_SkipListMap_hp_get "get( K const&)"
 619             but \p pred is used for comparing the keys.
 620
 621             \p Less functor has the semantics like \p std::less but should take arguments of type \ref key_type and \p K
 622             in any order.
 623             \p pred must imply the same element order as the comparator used for building the map.
 624         */
 625         template <typename K, typename Less>
 626         guarded_ptr get_with( K const& key, Less pred )
 627         {
 628             CDS_UNUSED( pred );
 629             typedef cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor > wrapped_less;
 630             guarded_ptr gp;
 631             base_class::get_with_( gp.guard(), key, cds::opt::details::make_comparator_from_less< wrapped_less >());
 632             return gp;
 633         }
 634
 635         /// Clears the map
 636         void clear()
 637         {
 638             base_class::clear();
 639         }
 640
 641         /// Checks if the map is empty
 642         bool empty() const
 643         {
 644             return base_class::empty();
 645         }
 646
 647         /// Returns item count in the map
 648         size_t size() const
 649         {
 650             return base_class::size();
 651         }
 652
 653         /// Returns const reference to internal statistics
 654         stat const& statistics() const
 655         {
 656             return base_class::statistics();
 657         }
 658     };
 659 }} // namespace cds::container
 660
 661 #endif // #ifndef __CDS_CONTAINER_IMPL_SKIP_LIST_MAP_H