cds/container/multilevel_hashmap_rcu.h

   1 //$$CDS-header$$
   2
   3 #ifndef CDSLIB_CONTAINER_MULTILEVEL_HASHMAP_RCU_H
   4 #define CDSLIB_CONTAINER_MULTILEVEL_HASHMAP_RCU_H
   5
   6 #include <cds/intrusive/multilevel_hashset_rcu.h>
   7 #include <cds/container/details/multilevel_hashmap_base.h>
   8
   9 namespace cds { namespace container {
  10
  11     /// Hash map based on multi-level array
  12     /** @ingroup cds_nonintrusive_map
  13         @anchor cds_container_MultilevelHashMap_rcu
  14
  15         Source:
  16         - [2013] Steven Feldman, Pierre LaBorde, Damian Dechev "Concurrent Multi-level Arrays:
  17                  Wait-free Extensible Hash Maps"
  18
  19         See algorithm short description @ref cds_container_MultilevelHashMap_hp "here"
  20
  21         @note Two important things you should keep in mind when you're using \p %MultiLevelHashMap:
  22         - all keys is converted to fixed-size bit-string by hash functor provided.
  23           You can use variable-length keys, for example, \p std::string as a key for \p %MultiLevelHashMap,
  24           but real key in the map will be fixed-size hash values of your keys.
  25           For the strings you may use well-known hashing algorithms like <a href="https://en.wikipedia.org/wiki/Secure_Hash_Algorithm">SHA1, SHA2</a>,
  26           <a href="https://en.wikipedia.org/wiki/MurmurHash">MurmurHash</a>, <a href="https://en.wikipedia.org/wiki/CityHash">CityHash</a>
  27           or its successor <a href="https://code.google.com/p/farmhash/">FarmHash</a> and so on, which
  28           converts variable-length strings to fixed-length bit-strings, and such hash values will be the keys in \p %MultiLevelHashMap.
  29         - \p %MultiLevelHashMap uses a perfect hashing. It means that if two different keys, for example, of type \p std::string,
  30           have identical hash then you cannot insert both that keys in the map. \p %MultiLevelHashMap does not maintain the key,
  31           it maintains its fixed-size hash value.
  32
  33         The map supports @ref cds_container_MultilevelHashMap_rcu_iterators "bidirectional thread-safe iterators".
  34
  35         Template parameters:
  36         - \p RCU - one of \ref cds_urcu_gc "RCU type"
  37         - \p Key - a key type to be stored in the map
  38         - \p T - a value type to be stored in the map
  39         - \p Traits - type traits, the structure based on \p multilevel_hashmap::traits or result of \p multilevel_hashmap::make_traits metafunction.
  40
  41         @note Before including <tt><cds/intrusive/multilevel_hashset_rcu.h></tt> you should include appropriate RCU header file,
  42         see \ref cds_urcu_gc "RCU type" for list of existing RCU class and corresponding header files.
  43     */
  44     template <
  45         class RCU
  46         ,typename Key
  47         ,typename T
  48 #ifdef CDS_DOXYGEN_INVOKED
  49         ,class Traits = multilevel_hashmap::traits
  50 #else
  51         ,class Traits
  52 #endif
  53     >
  54     class MultiLevelHashMap< cds::urcu::gc< RCU >, Key, T, Traits >
  55 #ifdef CDS_DOXYGEN_INVOKED
  56         : protected cds::intrusive::MultiLevelHashSet< cds::urcu::gc< RCU >, std::pair<Key const, T>, Traits >
  57 #else
  58         : protected cds::container::details::make_multilevel_hashmap< cds::urcu::gc< RCU >, Key, T, Traits >::type
  59 #endif
  60     {
  61         //@cond
  62         typedef cds::container::details::make_multilevel_hashmap< cds::urcu::gc< RCU >, Key, T, Traits > maker;
  63         typedef typename maker::type base_class;
  64         //@endcond
  65     public:
  66         typedef cds::urcu::gc< RCU > gc; ///< RCU garbage collector
  67         typedef Key     key_type;    ///< Key type
  68         typedef T       mapped_type; ///< Mapped type
  69         typedef std::pair< key_type const, mapped_type> value_type;   ///< Key-value pair to be stored in the map
  70         typedef Traits  traits;      ///< Map traits
  71 #ifdef CDS_DOXYGEN_INVOKED
  72         typedef typename traits::hash hasher; ///< Hash functor, see \p multilevel_hashmap::traits::hash
  73 #else
  74         typedef typename maker::hasher hasher;
  75 #endif
  76
  77         typedef typename maker::hash_type hash_type; ///< Hash type deduced from \p hasher return type
  78         typedef typename base_class::hash_comparator hash_comparator; ///< hash compare functor based on \p Traits::compare and \p Traits::less
  79         typedef typename traits::item_counter   item_counter;   ///< Item counter type
  80         typedef typename traits::allocator      allocator;      ///< Element allocator
  81         typedef typename traits::node_allocator node_allocator; ///< Array node allocator
  82         typedef typename traits::memory_model   memory_model;   ///< Memory model
  83         typedef typename traits::back_off       back_off;       ///< Backoff strategy
  84         typedef typename traits::stat           stat;           ///< Internal statistics type
  85         typedef typename traits::rcu_check_deadlock rcu_check_deadlock; ///< Deadlock checking policy
  86         typedef typename gc::scoped_lock       rcu_lock;        ///< RCU scoped lock
  87         static CDS_CONSTEXPR const bool c_bExtractLockExternal = false; ///< Group of \p extract_xxx functions does not require external locking
  88
  89     protected:
  90         //@cond
  91         typedef typename maker::node_type node_type;
  92         typedef typename maker::cxx_node_allocator cxx_node_allocator;
  93         typedef std::unique_ptr< node_type, typename maker::node_disposer > scoped_node_ptr;
  94
  95         struct node_cast
  96         {
  97             value_type * operator()(node_type * p) const
  98             {
  99                 return p ? &p->m_Value : nullptr;
 100             }
 101         };
 102
 103     public:
 104         /// pointer to extracted node
 105         using exempt_ptr = cds::urcu::exempt_ptr< gc, node_type, value_type, typename base_class::disposer, node_cast >;
 106
 107     protected:
 108         template <bool IsConst>
 109         class bidirectional_iterator: public base_class::iterator_base
 110         {
 111             friend class MultiLevelHashMap;
 112             typedef typename base_class::iterator_base iterator_base;
 113
 114         protected:
 115             static CDS_CONSTEXPR bool const c_bConstantIterator = IsConst;
 116
 117         public:
 118             typedef typename std::conditional< IsConst, value_type const*, value_type*>::type value_ptr; ///< Value pointer
 119             typedef typename std::conditional< IsConst, value_type const&, value_type&>::type value_ref; ///< Value reference
 120
 121         public:
 122             bidirectional_iterator() CDS_NOEXCEPT
 123             {}
 124
 125             bidirectional_iterator( bidirectional_iterator const& rhs ) CDS_NOEXCEPT
 126                 : iterator_base( rhs )
 127             {}
 128
 129             bidirectional_iterator& operator=(bidirectional_iterator const& rhs) CDS_NOEXCEPT
 130             {
 131                 iterator_base::operator=( rhs );
 132                 return *this;
 133             }
 134
 135             bidirectional_iterator& operator++()
 136             {
 137                 iterator_base::operator++();
 138                 return *this;
 139             }
 140
 141             bidirectional_iterator& operator--()
 142             {
 143                 iterator_base::operator--();
 144                 return *this;
 145             }
 146
 147             value_ptr operator ->() const CDS_NOEXCEPT
 148             {
 149                 node_type * p = iterator_base::pointer();
 150                 return p ? &p->m_Value : nullptr;
 151             }
 152
 153             value_ref operator *() const CDS_NOEXCEPT
 154             {
 155                 node_type * p = iterator_base::pointer();
 156                 assert( p );
 157                 return p->m_Value;
 158             }
 159
 160             void release()
 161             {
 162                 iterator_base::release();
 163             }
 164
 165             template <bool IsConst2>
 166             bool operator ==(bidirectional_iterator<IsConst2> const& rhs) const CDS_NOEXCEPT
 167             {
 168                 return iterator_base::operator==( rhs );
 169             }
 170
 171             template <bool IsConst2>
 172             bool operator !=(bidirectional_iterator<IsConst2> const& rhs) const CDS_NOEXCEPT
 173             {
 174                 return !( *this == rhs );
 175             }
 176
 177         public: // for internal use only!
 178             bidirectional_iterator( base_class const& set, typename base_class::array_node * pNode, size_t idx, bool )
 179                 : iterator_base( set, pNode, idx, false )
 180             {}
 181
 182             bidirectional_iterator( base_class const& set, typename base_class::array_node * pNode, size_t idx )
 183                 : iterator_base( set, pNode, idx )
 184             {}
 185         };
 186
 187         /// Reverse bidirectional iterator
 188         template <bool IsConst>
 189         class reverse_bidirectional_iterator : public base_class::iterator_base
 190         {
 191             friend class MultiLevelHashMap;
 192             typedef typename base_class::iterator_base iterator_base;
 193
 194         public:
 195             typedef typename std::conditional< IsConst, value_type const*, value_type*>::type value_ptr; ///< Value pointer
 196             typedef typename std::conditional< IsConst, value_type const&, value_type&>::type value_ref; ///< Value reference
 197
 198         public:
 199             reverse_bidirectional_iterator() CDS_NOEXCEPT
 200                 : iterator_base()
 201             {}
 202
 203             reverse_bidirectional_iterator( reverse_bidirectional_iterator const& rhs ) CDS_NOEXCEPT
 204                 : iterator_base( rhs )
 205             {}
 206
 207             reverse_bidirectional_iterator& operator=( reverse_bidirectional_iterator const& rhs) CDS_NOEXCEPT
 208             {
 209                 iterator_base::operator=( rhs );
 210                 return *this;
 211             }
 212
 213             reverse_bidirectional_iterator& operator++()
 214             {
 215                 iterator_base::operator--();
 216                 return *this;
 217             }
 218
 219             reverse_bidirectional_iterator& operator--()
 220             {
 221                 iterator_base::operator++();
 222                 return *this;
 223             }
 224
 225             value_ptr operator ->() const CDS_NOEXCEPT
 226             {
 227                 node_type * p = iterator_base::pointer();
 228                 return p ? &p->m_Value : nullptr;
 229             }
 230
 231             value_ref operator *() const CDS_NOEXCEPT
 232             {
 233                 node_type * p = iterator_base::pointer();
 234                 assert( p );
 235                 return p->m_Value;
 236             }
 237
 238             void release()
 239             {
 240                 iterator_base::release();
 241             }
 242
 243             template <bool IsConst2>
 244             bool operator ==(reverse_bidirectional_iterator<IsConst2> const& rhs) const
 245             {
 246                 return iterator_base::operator==( rhs );
 247             }
 248
 249             template <bool IsConst2>
 250             bool operator !=(reverse_bidirectional_iterator<IsConst2> const& rhs)
 251             {
 252                 return !( *this == rhs );
 253             }
 254
 255         public: // for internal use only!
 256             reverse_bidirectional_iterator( base_class const& set, typename base_class::array_node * pNode, size_t idx, bool )
 257                 : iterator_base( set, pNode, idx, false )
 258             {}
 259
 260             reverse_bidirectional_iterator( base_class const& set, typename base_class::array_node * pNode, size_t idx )
 261                 : iterator_base( set, pNode, idx, false )
 262             {
 263                 iterator_base::backward();
 264             }
 265         };
 266         //@endcond
 267
 268     public:
 269 #ifdef CDS_DOXYGEN_INVOKED
 270         typedef implementation_defined iterator;            ///< @ref cds_container_MultilevelHashMap_rcu_iterators "bidirectional iterator" type
 271         typedef implementation_defined const_iterator;      ///< @ref cds_container_MultilevelHashMap_rcu_iterators "bidirectional const iterator" type
 272         typedef implementation_defined reverse_iterator;    ///< @ref cds_container_MultilevelHashMap_rcu_iterators "bidirectional reverse iterator" type
 273         typedef implementation_defined const_reverse_iterator; ///< @ref cds_container_MultilevelHashMap_rcu_iterators "bidirectional reverse const iterator" type
 274 #else
 275         typedef bidirectional_iterator<false> iterator;
 276         typedef bidirectional_iterator<true>  const_iterator;
 277         typedef reverse_bidirectional_iterator<false> reverse_iterator;
 278         typedef reverse_bidirectional_iterator<true>  const_reverse_iterator;
 279 #endif
 280
 281     protected:
 282         //@cond
 283         hasher  m_Hasher;
 284         //@endcond
 285
 286     public:
 287         /// Creates empty map
 288         /**
 289             @param head_bits: 2<sup>head_bits</sup> specifies the size of head array, minimum is 4.
 290             @param array_bits: 2<sup>array_bits</sup> specifies the size of array node, minimum is 2.
 291
 292             Equation for \p head_bits and \p array_bits:
 293             \code
 294             sizeof(hash_type) * 8 == head_bits + N * array_bits
 295             \endcode
 296             where \p N is multi-level array depth.
 297         */
 298         MultiLevelHashMap( size_t head_bits = 8, size_t array_bits = 4 )
 299             : base_class( head_bits, array_bits )
 300         {}
 301
 302         /// Destructs the map and frees all data
 303         ~MultiLevelHashMap()
 304         {}
 305
 306         /// Inserts new element with key and default value
 307         /**
 308             The function creates an element with \p key and default value, and then inserts the node created into the map.
 309
 310             Preconditions:
 311             - The \p key_type should be constructible from a value of type \p K.
 312                 In trivial case, \p K is equal to \p key_type.
 313             - The \p mapped_type should be default-constructible.
 314
 315             Returns \p true if inserting successful, \p false otherwise.
 316
 317             The function locks RCU internally.
 318         */
 319         template <typename K>
 320         bool insert( K&& key )
 321         {
 322             scoped_node_ptr sp( cxx_node_allocator().MoveNew( m_Hasher, std::forward<K>(key) ));
 323             if ( base_class::insert( *sp )) {
 324                 sp.release();
 325                 return true;
 326             }
 327             return false;
 328         }
 329
 330         /// Inserts new element
 331         /**
 332             The function creates a node with copy of \p val value
 333             and then inserts the node created into the map.
 334
 335             Preconditions:
 336             - The \p key_type should be constructible from \p key of type \p K.
 337             - The \p value_type should be constructible from \p val of type \p V.
 338
 339             Returns \p true if \p val is inserted into the map, \p false otherwise.
 340
 341             The function locks RCU internally.
 342         */
 343         template <typename K, typename V>
 344         bool insert( K&& key, V&& val )
 345         {
 346             scoped_node_ptr sp( cxx_node_allocator().MoveNew( m_Hasher, std::forward<K>(key), std::forward<V>(val)));
 347             if ( base_class::insert( *sp )) {
 348                 sp.release();
 349                 return true;
 350             }
 351             return false;
 352         }
 353
 354         /// Inserts new element and initialize it by a functor
 355         /**
 356             This function inserts new element with key \p key and if inserting is successful then it calls
 357             \p func functor with signature
 358             \code
 359                 struct functor {
 360                     void operator()( value_type& item );
 361                 };
 362             \endcode
 363
 364             The argument \p item of user-defined functor \p func is the reference
 365             to the map's item inserted:
 366                 - <tt>item.first</tt> is a const reference to item's key that cannot be changed.
 367                 - <tt>item.second</tt> is a reference to item's value that may be changed.
 368
 369             \p key_type should be constructible from value of type \p K.
 370
 371             The function allows to split creating of new item into two part:
 372             - create item from \p key;
 373             - insert new item into the map;
 374             - if inserting is successful, initialize the value of item by calling \p func functor
 375
 376             This can be useful if complete initialization of object of \p value_type is heavyweight and
 377             it is preferable that the initialization should be completed only if inserting is successful.
 378
 379             The function locks RCU internally.
 380         */
 381         template <typename K, typename Func>
 382         bool insert_with( K&& key, Func func )
 383         {
 384             scoped_node_ptr sp( cxx_node_allocator().MoveNew( m_Hasher, std::forward<K>(key)));
 385             if ( base_class::insert( *sp, [&func]( node_type& item ) { func( item.m_Value ); } )) {
 386                 sp.release();
 387                 return true;
 388             }
 389             return false;
 390         }
 391
 392         /// For key \p key inserts data of type \p value_type created in-place from <tt>std::forward<Args>(args)...</tt>
 393         /**
 394             Returns \p true if inserting successful, \p false otherwise.
 395
 396             The function locks RCU internally.
 397         */
 398         template <typename K, typename... Args>
 399         bool emplace( K&& key, Args&&... args )
 400         {
 401             scoped_node_ptr sp( cxx_node_allocator().MoveNew( m_Hasher, std::forward<K>(key), std::forward<Args>(args)... ));
 402             if ( base_class::insert( *sp )) {
 403                 sp.release();
 404                 return true;
 405             }
 406             return false;
 407         }
 408
 409         /// Updates data by \p key
 410         /**
 411             The operation performs inserting or replacing the element with lock-free manner.
 412
 413             If the \p key not found in the map, then the new item created from \p key
 414             will be inserted into the map iff \p bInsert is \p true
 415             (note that in this case the \ref key_type should be constructible from type \p K).
 416             Otherwise, if \p key is found, it is replaced with a new item created from
 417             \p key.
 418             The functor \p Func signature:
 419             \code
 420                 struct my_functor {
 421                     void operator()( value_type& item, value_type * old );
 422                 };
 423             \endcode
 424             where:
 425             - \p item - item of the map
 426             - \p old - old item of the map, if \p nullptr - the new item was inserted
 427
 428             The functor may change any fields of the \p item.second.
 429
 430             Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successfull,
 431             \p second is \p true if new item has been added or \p false if \p key already exists.
 432
 433             The function locks RCU internally.
 434
 435             @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
 436         */
 437         template <typename K, typename Func>
 438         std::pair<bool, bool> update( K&& key, Func func, bool bInsert = true )
 439         {
 440             scoped_node_ptr sp( cxx_node_allocator().MoveNew( m_Hasher, std::forward<K>(key)));
 441             std::pair<bool, bool> result = base_class::do_update( *sp,
 442                 [&func]( node_type& node, node_type * old ) { func( node.m_Value, old ? &old->m_Value : nullptr );},
 443                 bInsert );
 444             if ( result.first )
 445                 sp.release();
 446             return result;
 447         }
 448
 449         /// Delete \p key from the map
 450         /**
 451             \p key_type must be constructible from value of type \p K.
 452             The function deeltes the element with hash value equal to <tt>hash( key_type( key ))</tt>
 453
 454             Return \p true if \p key is found and deleted, \p false otherwise.
 455
 456             RCU should not be locked. The function locks RCU internally.
 457         */
 458         template <typename K>
 459         bool erase( K const& key )
 460         {
 461             hash_type h = m_Hasher( key_type( key ));
 462             return base_class::erase( h );
 463         }
 464
 465         /// Delete \p key from the map
 466         /**
 467             The function searches an item with hash value equal to <tt>hash( key_type( key ))</tt>,
 468             calls \p f functor and deletes the item. If \p key is not found, the functor is not called.
 469
 470             The functor \p Func interface:
 471             \code
 472             struct extractor {
 473                 void operator()(value_type& item) { ... }
 474             };
 475             \endcode
 476             where \p item is the element found.
 477
 478             \p key_type must be constructible from value of type \p K.
 479
 480             Return \p true if key is found and deleted, \p false otherwise
 481
 482             RCU should not be locked. The function locks RCU internally.
 483         */
 484         template <typename K, typename Func>
 485         bool erase( K const& key, Func f )
 486         {
 487             hash_type h = m_Hasher( key_type( key ));
 488             return base_class::erase( h, [&f]( node_type& node) { f( node.m_Value ); } );
 489         }
 490
 491         /// Extracts the item from the map with specified \p key
 492         /**
 493             The function searches an item with key equal to <tt>hash( key_type( key ))</tt> in the map,
 494             unlinks it from the map, and returns a guarded pointer to the item found.
 495             If \p key is not found the function returns an empty guarded pointer.
 496
 497             RCU \p synchronize method can be called. RCU should NOT be locked.
 498             The function does not call the disposer for the item found.
 499             The disposer will be implicitly invoked when the returned object is destroyed or when
 500             its \p release() member function is called.
 501             Example:
 502             \code
 503             typedef cds::container::MultiLevelHashMap< cds::urcu::gc< cds::urcu::general_buffered<>>, int, foo, my_traits > map_type;
 504             map_type theMap;
 505             // ...
 506
 507             typename map_type::exempt_ptr ep( theMap.extract( 5 ));
 508             if ( ep ) {
 509                 // Deal with ep
 510                 //...
 511
 512                 // Dispose returned item.
 513                 ep.release();
 514             }
 515             \endcode
 516         */
 517         template <typename K>
 518         exempt_ptr extract( K const& key )
 519         {
 520             check_deadlock_policy::check();
 521
 522             node_type * p;
 523             {
 524                 rcu_lock rcuLock;
 525                 p = base_class::do_erase( m_Hasher( key_type(key)), [](node_type const&) -> bool {return true;});
 526             }
 527             return exempt_ptr(p);
 528         }
 529
 530         /// Checks whether the map contains \p key
 531         /**
 532             The function searches the item by its hash that is equal to <tt>hash( key_type( key ))</tt>
 533             and returns \p true if it is found, or \p false otherwise.
 534         */
 535         template <typename K>
 536         bool contains( K const& key )
 537         {
 538             return base_class::contains( m_Hasher( key_type( key )) );
 539         }
 540
 541         /// Find the key \p key
 542         /**
 543
 544             The function searches the item by its hash that is equal to <tt>hash( key_type( key ))</tt>
 545             and calls the functor \p f for item found.
 546             The interface of \p Func functor is:
 547             \code
 548             struct functor {
 549                 void operator()( value_type& item );
 550             };
 551             \endcode
 552             where \p item is the item found.
 553
 554             The functor may change \p item.second.
 555
 556             The function returns \p true if \p key is found, \p false otherwise.
 557         */
 558         template <typename K, typename Func>
 559         bool find( K const& key, Func f )
 560         {
 561             return base_class::find( m_Hasher( key_type( key )), [&f](node_type& node) { f( node.m_Value );});
 562         }
 563
 564         /// Finds the key \p key and return the item found
 565         /**
 566             The function searches the item by its \p hash
 567             and returns the pointer to the item found.
 568             If \p hash is not found the function returns \p nullptr.
 569
 570             RCU should be locked before the function invocation.
 571             Returned pointer is valid only while RCU is locked.
 572
 573             Usage:
 574             \code
 575             typedef cds::container::MultiLevelHashMap< your_template_params >  my_map;
 576             my_map theMap;
 577             // ...
 578             {
 579                 // lock RCU
 580                 my_map::rcu_lock;
 581
 582                 foo * p = theMap.get( 5 );
 583                 if ( p ) {
 584                     // Deal with p
 585                     //...
 586                 }
 587             }
 588             \endcode
 589         */
 590         template <typename K>
 591         value_type * get( K const& key )
 592         {
 593             node_type * p = base_class::get( m_Hasher( key_type( key )));
 594             return p ? &p->m_Value : nullptr;
 595         }
 596
 597         /// Clears the map (non-atomic)
 598         /**
 599             The function unlink all data node from the map.
 600             The function is not atomic but is thread-safe.
 601             After \p %clear() the map may not be empty because another threads may insert items.
 602         */
 603         void clear()
 604         {
 605             base_class::clear();
 606         }
 607
 608         /// Checks if the map is empty
 609         /**
 610             Emptiness is checked by item counting: if item count is zero then the map is empty.
 611             Thus, the correct item counting feature is an important part of the map implementation.
 612         */
 613         bool empty() const
 614         {
 615             return base_class::empty();
 616         }
 617
 618         /// Returns item count in the map
 619         size_t size() const
 620         {
 621             return base_class::size();
 622         }
 623
 624         /// Returns const reference to internal statistics
 625         stat const& statistics() const
 626         {
 627             return base_class::statistics();
 628         }
 629
 630         /// Returns the size of head node
 631         size_t head_size() const
 632         {
 633             return base_class::head_size();
 634         }
 635
 636         /// Returns the size of the array node
 637         size_t array_node_size() const
 638         {
 639             return base_class::array_node_size();
 640         }
 641
 642     public:
 643     ///@name Thread-safe iterators
 644         /** @anchor cds_container_MultilevelHashMap_rcu_iterators
 645             The map supports thread-safe iterators: you may iterate over the map in multi-threaded environment
 646             under explicit RCU lock.
 647             RCU lock requirement means that inserting or searching is allowed but you must not erase the items from the map
 648             since erasing under RCU lock can lead to a deadlock. However, another thread can call \p erase() safely
 649             while your thread is iterating.
 650
 651             A typical example is:
 652             \code
 653             struct foo {
 654                 // ... other fields
 655                 uint32_t    payload; // only for example
 656             };
 657             typedef cds::urcu::gc< cds::urcu::general_buffered<>> rcu;
 658             typedef cds::container::MultiLevelHashMap< rcu, std::string, foo> map_type;
 659
 660             map_type m;
 661
 662             // ...
 663
 664             // iterate over the map
 665             {
 666                 // lock the RCU.
 667                 typename set_type::rcu_lock l; // scoped RCU lock
 668
 669                 // traverse the map
 670                 for ( auto i = m.begin(); i != s.end(); ++i ) {
 671                     // deal with i. Remember, erasing is prohibited here!
 672                     i->second.payload++;
 673                 }
 674             } // at this point RCU lock is released
 675             /endcode
 676
 677             Each iterator object supports the common interface:
 678             - dereference operators:
 679                 @code
 680                 value_type [const] * operator ->() noexcept
 681                 value_type [const] & operator *() noexcept
 682                 @endcode
 683             - pre-increment and pre-decrement. Post-operators is not supported
 684             - equality operators <tt>==</tt> and <tt>!=</tt>.
 685                 Iterators are equal iff they point to the same cell of the same array node.
 686                 Note that for two iterators \p it1 and \p it2 the condition <tt> it1 == it2 </tt>
 687                 does not entail <tt> &(*it1) == &(*it2) </tt>: welcome to concurrent containers
 688
 689             @note It is possible the item can be iterated more that once, for example, if an iterator points to the item
 690             in an array node that is being splitted.
 691         */
 692     ///@{
 693         /// Returns an iterator to the beginning of the map
 694         iterator begin()
 695         {
 696             return base_class::template init_begin<iterator>();
 697         }
 698
 699         /// Returns an const iterator to the beginning of the map
 700         const_iterator begin() const
 701         {
 702             return base_class::template init_begin<const_iterator>();
 703         }
 704
 705         /// Returns an const iterator to the beginning of the map
 706         const_iterator cbegin()
 707         {
 708             return base_class::template init_begin<const_iterator>();
 709         }
 710
 711         /// Returns an iterator to the element following the last element of the map. This element acts as a placeholder; attempting to access it results in undefined behavior.
 712         iterator end()
 713         {
 714             return base_class::template init_end<iterator>();
 715         }
 716
 717         /// Returns a const iterator to the element following the last element of the map. This element acts as a placeholder; attempting to access it results in undefined behavior.
 718         const_iterator end() const
 719         {
 720             return base_class::template init_end<const_iterator>();
 721         }
 722
 723         /// Returns a const iterator to the element following the last element of the map. This element acts as a placeholder; attempting to access it results in undefined behavior.
 724         const_iterator cend()
 725         {
 726             return base_class::template init_end<const_iterator>();
 727         }
 728
 729         /// Returns a reverse iterator to the first element of the reversed map
 730         reverse_iterator rbegin()
 731         {
 732             return base_class::template init_rbegin<reverse_iterator>();
 733         }
 734
 735         /// Returns a const reverse iterator to the first element of the reversed map
 736         const_reverse_iterator rbegin() const
 737         {
 738             return base_class::template init_rbegin<const_reverse_iterator>();
 739         }
 740
 741         /// Returns a const reverse iterator to the first element of the reversed map
 742         const_reverse_iterator crbegin()
 743         {
 744             return base_class::template init_rbegin<const_reverse_iterator>();
 745         }
 746
 747         /// Returns a reverse iterator to the element following the last element of the reversed map
 748         /**
 749             It corresponds to the element preceding the first element of the non-reversed container.
 750             This element acts as a placeholder, attempting to access it results in undefined behavior.
 751         */
 752         reverse_iterator rend()
 753         {
 754             return base_class::template init_rend<reverse_iterator>();
 755         }
 756
 757         /// Returns a const reverse iterator to the element following the last element of the reversed map
 758         /**
 759             It corresponds to the element preceding the first element of the non-reversed container.
 760             This element acts as a placeholder, attempting to access it results in undefined behavior.
 761         */
 762         const_reverse_iterator rend() const
 763         {
 764             return base_class::template init_rend<const_reverse_iterator>();
 765         }
 766
 767         /// Returns a const reverse iterator to the element following the last element of the reversed map
 768         /**
 769             It corresponds to the element preceding the first element of the non-reversed container.
 770             This element acts as a placeholder, attempting to access it results in undefined behavior.
 771         */
 772         const_reverse_iterator crend()
 773         {
 774             return base_class::template init_rend<const_reverse_iterator>();
 775         }
 776     ///@}
 777     };
 778 }} // namespace cds::container
 779
 780 #endif // #ifndef CDSLIB_CONTAINER_MULTILEVEL_HASHMAP_RCU_H