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::PTB 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             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             return base_class::erase_with( key,
 394                 cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor >(),
 395                 [&f]( node_type& node) { f( node.m_Value ); } );
 396         }
 397
 398         /// Extracts the item from the map with specified \p key
 399         /** \anchor cds_nonintrusive_SkipListMap_hp_extract
 400             The function searches an item with key equal to \p key in the map,
 401             unlinks it from the map, and returns it in \p ptr parameter.
 402             If the item with key equal to \p key is not found the function returns \p false.
 403
 404             Note the compare functor should accept a parameter of type \p K that can be not the same as \p key_type.
 405
 406             The item extracted is freed automatically by garbage collector \p GC
 407             when returned \ref guarded_ptr object will be destroyed or released.
 408             @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
 409
 410             Usage:
 411             \code
 412             typedef cds::container::SkipListMap< cds::gc::HP, int, foo, my_traits >  skip_list;
 413             skip_list theList;
 414             // ...
 415             {
 416                 skip_list::guarded_ptr gp;
 417                 if ( theList.extract( gp, 5 ) ) {
 418                     // Deal with gp
 419                     // ...
 420                 }
 421                 // Destructor of gp releases internal HP guard and frees the pointer
 422             }
 423             \endcode
 424         */
 425         template <typename K>
 426         bool extract( guarded_ptr& ptr, K const& key )
 427         {
 428             return base_class::extract_( ptr.guard(), key, typename base_class::key_comparator() );
 429         }
 430
 431         /// Extracts the item from the map with comparing functor \p pred
 432         /**
 433             The function is an analog of \ref cds_nonintrusive_SkipListMap_hp_extract "extract(K const&)"
 434             but \p pred predicate is used for key comparing.
 435
 436             \p Less functor has the semantics like \p std::less but should take arguments of type \ref key_type and \p K
 437             in any order.
 438             \p pred must imply the same element order as the comparator used for building the map.
 439         */
 440         template <typename K, typename Less>
 441         bool extract_with( guarded_ptr& ptr, K const& key, Less pred )
 442         {
 443             typedef cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor >  wrapped_less;
 444             return base_class::extract_( ptr.guard(), key, cds::opt::details::make_comparator_from_less<wrapped_less>() );
 445         }
 446
 447         /// Extracts an item with minimal key from the map
 448         /**
 449             The function searches an item with minimal key, unlinks it, and returns the item found in \p ptr parameter.
 450             If the skip-list is empty the function returns \p false.
 451
 452             The item extracted is freed automatically by garbage collector \p GC
 453             when returned \ref guarded_ptr object will be destroyed or released.
 454             @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
 455
 456             Usage:
 457             \code
 458             typedef cds::continer::SkipListMap< cds::gc::HP, int, foo, my_traits >  skip_list;
 459             skip_list theList;
 460             // ...
 461             {
 462                 skip_list::guarded_ptr gp;
 463                 if ( theList.extract_min( gp )) {
 464                     // Deal with gp
 465                     //...
 466                 }
 467                 // Destructor of gp releases internal HP guard and then frees the pointer
 468             }
 469             \endcode
 470         */
 471         bool extract_min( guarded_ptr& ptr)
 472         {
 473             return base_class::extract_min_( ptr.guard() );
 474         }
 475
 476         /// Extracts an item with maximal key from the map
 477         /**
 478             The function searches an item with maximal key, unlinks it, and returns the pointer to item found in \p ptr parameter.
 479             If the skip-list is empty the function returns empty \p guarded_ptr.
 480
 481             The item found is freed by garbage collector \p GC automatically
 482             when returned \ref guarded_ptr object will be destroyed or released.
 483             @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
 484
 485             Usage:
 486             \code
 487             typedef cds::container::SkipListMap< cds::gc::HP, int, foo, my_traits >  skip_list;
 488             skip_list theList;
 489             // ...
 490             {
 491                 skip_list::guarded_ptr gp;
 492                 if ( theList.extract_max( gp )) {
 493                     // Deal with gp
 494                     //...
 495                 }
 496                 // Destructor of gp releases internal HP guard and then frees the pointer
 497             }
 498             \endcode
 499         */
 500         bool extract_max( guarded_ptr& dest )
 501         {
 502             return base_class::extract_max_( dest.guard() );
 503         }
 504
 505         /// Find the key \p key
 506         /** \anchor cds_nonintrusive_SkipListMap_find_cfunc
 507
 508             The function searches the item with key equal to \p key and calls the functor \p f for item found.
 509             The interface of \p Func functor is:
 510             \code
 511             struct functor {
 512                 void operator()( value_type& item );
 513             };
 514             \endcode
 515             where \p item is the item found.
 516
 517             The functor may change \p item.second.
 518
 519             The function returns \p true if \p key is found, \p false otherwise.
 520         */
 521         template <typename K, typename Func>
 522         bool find( K const& key, Func f )
 523         {
 524             return base_class::find( key, [&f](node_type& item, K const& ) { f( item.m_Value );});
 525         }
 526
 527         /// Finds the key \p val using \p pred predicate for searching
 528         /**
 529             The function is an analog of \ref cds_nonintrusive_SkipListMap_find_cfunc "find(K const&, Func)"
 530             but \p pred is used for key comparing.
 531             \p Less functor has the interface like \p std::less.
 532             \p Less must imply the same element order as the comparator used for building the map.
 533         */
 534         template <typename K, typename Less, typename Func>
 535         bool find_with( K const& key, Less pred, Func f )
 536         {
 537             return base_class::find_with( key,
 538                 cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor >(),
 539                 [&f](node_type& item, K const& ) { f( item.m_Value );});
 540         }
 541
 542         /// Find the key \p key
 543         /** \anchor cds_nonintrusive_SkipListMap_find_val
 544
 545             The function searches the item with key equal to \p key
 546             and returns \p true if it is found, and \p false otherwise.
 547         */
 548         template <typename K>
 549         bool find( K const& key )
 550         {
 551             return base_class::find( key );
 552         }
 553
 554         /// Finds the key \p val using \p pred predicate for searching
 555         /**
 556             The function is an analog of \ref cds_nonintrusive_SkipListMap_find_val "find(K const&)"
 557             but \p pred is used for key comparing.
 558             \p Less functor has the interface like \p std::less.
 559             \p Less must imply the same element order as the comparator used for building the map.
 560         */
 561         template <typename K, typename Less>
 562         bool find_with( K const& key, Less pred )
 563         {
 564             return base_class::find_with( key, cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor >() );
 565         }
 566
 567         /// Finds the key \p key and return the item found
 568         /** \anchor cds_nonintrusive_SkipListMap_hp_get
 569             The function searches the item with key equal to \p key
 570             and assigns the item found to guarded pointer \p ptr.
 571             The function returns \p true if \p key is found, and \p false otherwise.
 572             If \p key is not found the \p ptr parameter is not changed.
 573
 574             It is safe when a concurrent thread erases the item returned in \p ptr guarded pointer.
 575             In this case the item will be freed later by garbage collector \p GC automatically
 576             when \p guarded_ptr object will be destroyed or released.
 577             @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
 578
 579             Usage:
 580             \code
 581             typedef cds::container::SkipListMap< cds::gc::HP, int, foo, my_traits >  skip_list;
 582             skip_list theList;
 583             // ...
 584             {
 585                 skip_list::guarded_ptr gp;
 586                 if ( theList.get( gp, 5 ) ) {
 587                     // Deal with gp
 588                     //...
 589                 }
 590                 // Destructor of guarded_ptr releases internal HP guard
 591             }
 592             \endcode
 593
 594             Note the compare functor specified for class \p Traits template parameter
 595             should accept a parameter of type \p K that can be not the same as \p value_type.
 596         */
 597         template <typename K>
 598         bool get( guarded_ptr& ptr, K const& key )
 599         {
 600             return base_class::get_with_( ptr.guard(), key, typename base_class::key_comparator() );
 601         }
 602
 603         /// Finds the key \p key and return the item found
 604         /**
 605             The function is an analog of \ref cds_nonintrusive_SkipListMap_hp_get "get( guarded_ptr& ptr, K const&)"
 606             but \p pred is used for comparing the keys.
 607
 608             \p Less functor has the semantics like \p std::less but should take arguments of type \ref key_type and \p K
 609             in any order.
 610             \p pred must imply the same element order as the comparator used for building the map.
 611         */
 612         template <typename K, typename Less>
 613         bool get_with( guarded_ptr& ptr, K const& key, Less pred )
 614         {
 615             typedef cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor > wrapped_less;
 616             return base_class::get_with_( ptr.guard(), key, cds::opt::details::make_comparator_from_less< wrapped_less >());
 617         }
 618
 619         /// Clears the map
 620         void clear()
 621         {
 622             base_class::clear();
 623         }
 624
 625         /// Checks if the map is empty
 626         bool empty() const
 627         {
 628             return base_class::empty();
 629         }
 630
 631         /// Returns item count in the map
 632         size_t size() const
 633         {
 634             return base_class::size();
 635         }
 636
 637         /// Returns const reference to internal statistics
 638         stat const& statistics() const
 639         {
 640             return base_class::statistics();
 641         }
 642     };
 643 }} // namespace cds::container
 644
 645 #endif // #ifndef __CDS_CONTAINER_IMPL_SKIP_LIST_MAP_H