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