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           If your key is fixed-sized the hash functor is optional, see \p multilevel_hashmap::traits::hash for explanation and examples.
  30         - \p %MultiLevelHashMap uses a perfect hashing. It means that if two different keys, for example, of type \p std::string,
  31           have identical hash then you cannot insert both that keys in the map. \p %MultiLevelHashMap does not maintain the key,
  32           it maintains its fixed-size hash value.
  33
  34         The map supports @ref cds_container_MultilevelHashMap_rcu_iterators "bidirectional thread-safe iterators".
  35
  36         Template parameters:
  37         - \p RCU - one of \ref cds_urcu_gc "RCU type"
  38         - \p Key - a key type to be stored in the map
  39         - \p T - a value type to be stored in the map
  40         - \p Traits - type traits, the structure based on \p multilevel_hashmap::traits or result of \p multilevel_hashmap::make_traits metafunction.
  41
  42         @note Before including <tt><cds/intrusive/multilevel_hashset_rcu.h></tt> you should include appropriate RCU header file,
  43         see \ref cds_urcu_gc "RCU type" for list of existing RCU class and corresponding header files.
  44     */
  45     template <
  46         class RCU
  47         ,typename Key
  48         ,typename T
  49 #ifdef CDS_DOXYGEN_INVOKED
  50         ,class Traits = multilevel_hashmap::traits
  51 #else
  52         ,class Traits
  53 #endif
  54     >
  55     class MultiLevelHashMap< cds::urcu::gc< RCU >, Key, T, Traits >
  56 #ifdef CDS_DOXYGEN_INVOKED
  57         : protected cds::intrusive::MultiLevelHashSet< cds::urcu::gc< RCU >, std::pair<Key const, T>, Traits >
  58 #else
  59         : protected cds::container::details::make_multilevel_hashmap< cds::urcu::gc< RCU >, Key, T, Traits >::type
  60 #endif
  61     {
  62         //@cond
  63         typedef cds::container::details::make_multilevel_hashmap< cds::urcu::gc< RCU >, Key, T, Traits > maker;
  64         typedef typename maker::type base_class;
  65         //@endcond
  66     public:
  67         typedef cds::urcu::gc< RCU > gc; ///< RCU garbage collector
  68         typedef Key     key_type;    ///< Key type
  69         typedef T       mapped_type; ///< Mapped type
  70         typedef std::pair< key_type const, mapped_type> value_type;   ///< Key-value pair to be stored in the map
  71         typedef Traits  traits;      ///< Map traits
  72 #ifdef CDS_DOXYGEN_INVOKED
  73         typedef typename traits::hash hasher; ///< Hash functor, see \p multilevel_hashmap::traits::hash
  74 #else
  75         typedef typename maker::hasher hasher;
  76 #endif
  77
  78         typedef typename maker::hash_type hash_type; ///< Hash type deduced from \p hasher return type
  79         typedef typename base_class::hash_comparator hash_comparator; ///< hash compare functor based on \p Traits::compare and \p Traits::less
  80         typedef typename traits::item_counter   item_counter;   ///< Item counter type
  81         typedef typename traits::allocator      allocator;      ///< Element allocator
  82         typedef typename traits::node_allocator node_allocator; ///< Array node allocator
  83         typedef typename traits::memory_model   memory_model;   ///< Memory model
  84         typedef typename traits::back_off       back_off;       ///< Backoff strategy
  85         typedef typename traits::stat           stat;           ///< Internal statistics type
  86         typedef typename traits::rcu_check_deadlock rcu_check_deadlock; ///< Deadlock checking policy
  87         typedef typename gc::scoped_lock       rcu_lock;        ///< RCU scoped lock
  88         static CDS_CONSTEXPR const bool c_bExtractLockExternal = false; ///< Group of \p extract_xxx functions does not require external locking
  89
  90     protected:
  91         //@cond
  92         typedef typename maker::node_type node_type;
  93         typedef typename maker::cxx_node_allocator cxx_node_allocator;
  94         typedef std::unique_ptr< node_type, typename maker::node_disposer > scoped_node_ptr;
  95         typedef typename base_class::check_deadlock_policy check_deadlock_policy;
  96
  97         struct node_cast
  98         {
  99             value_type * operator()(node_type * p) const
 100             {
 101                 return p ? &p->m_Value : nullptr;
 102             }
 103         };
 104
 105     public:
 106         /// pointer to extracted node
 107         using exempt_ptr = cds::urcu::exempt_ptr< gc, node_type, value_type, typename base_class::disposer, node_cast >;
 108
 109     protected:
 110         template <bool IsConst>
 111         class bidirectional_iterator: public base_class::iterator_base
 112         {
 113             friend class MultiLevelHashMap;
 114             typedef typename base_class::iterator_base iterator_base;
 115
 116         protected:
 117             static CDS_CONSTEXPR bool const c_bConstantIterator = IsConst;
 118
 119         public:
 120             typedef typename std::conditional< IsConst, value_type const*, value_type*>::type value_ptr; ///< Value pointer
 121             typedef typename std::conditional< IsConst, value_type const&, value_type&>::type value_ref; ///< Value reference
 122
 123         public:
 124             bidirectional_iterator() CDS_NOEXCEPT
 125             {}
 126
 127             bidirectional_iterator( bidirectional_iterator const& rhs ) CDS_NOEXCEPT
 128                 : iterator_base( rhs )
 129             {}
 130
 131             bidirectional_iterator& operator=(bidirectional_iterator const& rhs) CDS_NOEXCEPT
 132             {
 133                 iterator_base::operator=( rhs );
 134                 return *this;
 135             }
 136
 137             bidirectional_iterator& operator++()
 138             {
 139                 iterator_base::operator++();
 140                 return *this;
 141             }
 142
 143             bidirectional_iterator& operator--()
 144             {
 145                 iterator_base::operator--();
 146                 return *this;
 147             }
 148
 149             value_ptr operator ->() const CDS_NOEXCEPT
 150             {
 151                 node_type * p = iterator_base::pointer();
 152                 return p ? &p->m_Value : nullptr;
 153             }
 154
 155             value_ref operator *() const CDS_NOEXCEPT
 156             {
 157                 node_type * p = iterator_base::pointer();
 158                 assert( p );
 159                 return p->m_Value;
 160             }
 161
 162             void release()
 163             {
 164                 iterator_base::release();
 165             }
 166
 167             template <bool IsConst2>
 168             bool operator ==(bidirectional_iterator<IsConst2> const& rhs) const CDS_NOEXCEPT
 169             {
 170                 return iterator_base::operator==( rhs );
 171             }
 172
 173             template <bool IsConst2>
 174             bool operator !=(bidirectional_iterator<IsConst2> const& rhs) const CDS_NOEXCEPT
 175             {
 176                 return !( *this == rhs );
 177             }
 178
 179         public: // for internal use only!
 180             bidirectional_iterator( base_class const& set, typename base_class::array_node * pNode, size_t idx, bool )
 181                 : iterator_base( set, pNode, idx, false )
 182             {}
 183
 184             bidirectional_iterator( base_class const& set, typename base_class::array_node * pNode, size_t idx )
 185                 : iterator_base( set, pNode, idx )
 186             {}
 187         };
 188
 189         /// Reverse bidirectional iterator
 190         template <bool IsConst>
 191         class reverse_bidirectional_iterator : public base_class::iterator_base
 192         {
 193             friend class MultiLevelHashMap;
 194             typedef typename base_class::iterator_base iterator_base;
 195
 196         public:
 197             typedef typename std::conditional< IsConst, value_type const*, value_type*>::type value_ptr; ///< Value pointer
 198             typedef typename std::conditional< IsConst, value_type const&, value_type&>::type value_ref; ///< Value reference
 199
 200         public:
 201             reverse_bidirectional_iterator() CDS_NOEXCEPT
 202                 : iterator_base()
 203             {}
 204
 205             reverse_bidirectional_iterator( reverse_bidirectional_iterator const& rhs ) CDS_NOEXCEPT
 206                 : iterator_base( rhs )
 207             {}
 208
 209             reverse_bidirectional_iterator& operator=( reverse_bidirectional_iterator const& rhs) CDS_NOEXCEPT
 210             {
 211                 iterator_base::operator=( rhs );
 212                 return *this;
 213             }
 214
 215             reverse_bidirectional_iterator& operator++()
 216             {
 217                 iterator_base::operator--();
 218                 return *this;
 219             }
 220
 221             reverse_bidirectional_iterator& operator--()
 222             {
 223                 iterator_base::operator++();
 224                 return *this;
 225             }
 226
 227             value_ptr operator ->() const CDS_NOEXCEPT
 228             {
 229                 node_type * p = iterator_base::pointer();
 230                 return p ? &p->m_Value : nullptr;
 231             }
 232
 233             value_ref operator *() const CDS_NOEXCEPT
 234             {
 235                 node_type * p = iterator_base::pointer();
 236                 assert( p );
 237                 return p->m_Value;
 238             }
 239
 240             void release()
 241             {
 242                 iterator_base::release();
 243             }
 244
 245             template <bool IsConst2>
 246             bool operator ==(reverse_bidirectional_iterator<IsConst2> const& rhs) const
 247             {
 248                 return iterator_base::operator==( rhs );
 249             }
 250
 251             template <bool IsConst2>
 252             bool operator !=(reverse_bidirectional_iterator<IsConst2> const& rhs)
 253             {
 254                 return !( *this == rhs );
 255             }
 256
 257         public: // for internal use only!
 258             reverse_bidirectional_iterator( base_class const& set, typename base_class::array_node * pNode, size_t idx, bool )
 259                 : iterator_base( set, pNode, idx, false )
 260             {}
 261
 262             reverse_bidirectional_iterator( base_class const& set, typename base_class::array_node * pNode, size_t idx )
 263                 : iterator_base( set, pNode, idx, false )
 264             {
 265                 iterator_base::backward();
 266             }
 267         };
 268         //@endcond
 269
 270     public:
 271 #ifdef CDS_DOXYGEN_INVOKED
 272         typedef implementation_defined iterator;            ///< @ref cds_container_MultilevelHashMap_rcu_iterators "bidirectional iterator" type
 273         typedef implementation_defined const_iterator;      ///< @ref cds_container_MultilevelHashMap_rcu_iterators "bidirectional const iterator" type
 274         typedef implementation_defined reverse_iterator;    ///< @ref cds_container_MultilevelHashMap_rcu_iterators "bidirectional reverse iterator" type
 275         typedef implementation_defined const_reverse_iterator; ///< @ref cds_container_MultilevelHashMap_rcu_iterators "bidirectional reverse const iterator" type
 276 #else
 277         typedef bidirectional_iterator<false> iterator;
 278         typedef bidirectional_iterator<true>  const_iterator;
 279         typedef reverse_bidirectional_iterator<false> reverse_iterator;
 280         typedef reverse_bidirectional_iterator<true>  const_reverse_iterator;
 281 #endif
 282
 283     protected:
 284         //@cond
 285         hasher  m_Hasher;
 286         //@endcond
 287
 288     public:
 289         /// Creates empty map
 290         /**
 291             @param head_bits: 2<sup>head_bits</sup> specifies the size of head array, minimum is 4.
 292             @param array_bits: 2<sup>array_bits</sup> specifies the size of array node, minimum is 2.
 293
 294             Equation for \p head_bits and \p array_bits:
 295             \code
 296             sizeof(hash_type) * 8 == head_bits + N * array_bits
 297             \endcode
 298             where \p N is multi-level array depth.
 299         */
 300         MultiLevelHashMap( size_t head_bits = 8, size_t array_bits = 4 )
 301             : base_class( head_bits, array_bits )
 302         {}
 303
 304         /// Destructs the map and frees all data
 305         ~MultiLevelHashMap()
 306         {}
 307
 308         /// Inserts new element with key and default value
 309         /**
 310             The function creates an element with \p key and default value, and then inserts the node created into the map.
 311
 312             Preconditions:
 313             - The \p key_type should be constructible from a value of type \p K.
 314                 In trivial case, \p K is equal to \p key_type.
 315             - The \p mapped_type should be default-constructible.
 316
 317             Returns \p true if inserting successful, \p false otherwise.
 318
 319             The function locks RCU internally.
 320         */
 321         template <typename K>
 322         bool insert( K&& key )
 323         {
 324             scoped_node_ptr sp( cxx_node_allocator().MoveNew( m_Hasher, std::forward<K>(key) ));
 325             if ( base_class::insert( *sp )) {
 326                 sp.release();
 327                 return true;
 328             }
 329             return false;
 330         }
 331
 332         /// Inserts new element
 333         /**
 334             The function creates a node with copy of \p val value
 335             and then inserts the node created into the map.
 336
 337             Preconditions:
 338             - The \p key_type should be constructible from \p key of type \p K.
 339             - The \p value_type should be constructible from \p val of type \p V.
 340
 341             Returns \p true if \p val is inserted into the map, \p false otherwise.
 342
 343             The function locks RCU internally.
 344         */
 345         template <typename K, typename V>
 346         bool insert( K&& key, V&& val )
 347         {
 348             scoped_node_ptr sp( cxx_node_allocator().MoveNew( m_Hasher, std::forward<K>(key), std::forward<V>(val)));
 349             if ( base_class::insert( *sp )) {
 350                 sp.release();
 351                 return true;
 352             }
 353             return false;
 354         }
 355
 356         /// Inserts new element and initialize it by a functor
 357         /**
 358             This function inserts new element with key \p key and if inserting is successful then it calls
 359             \p func functor with signature
 360             \code
 361                 struct functor {
 362                     void operator()( value_type& item );
 363                 };
 364             \endcode
 365
 366             The argument \p item of user-defined functor \p func is the reference
 367             to the map's item inserted:
 368                 - <tt>item.first</tt> is a const reference to item's key that cannot be changed.
 369                 - <tt>item.second</tt> is a reference to item's value that may be changed.
 370
 371             \p key_type should be constructible from value of type \p K.
 372
 373             The function allows to split creating of new item into two part:
 374             - create item from \p key;
 375             - insert new item into the map;
 376             - if inserting is successful, initialize the value of item by calling \p func functor
 377
 378             This can be useful if complete initialization of object of \p value_type is heavyweight and
 379             it is preferable that the initialization should be completed only if inserting is successful.
 380
 381             The function locks RCU internally.
 382         */
 383         template <typename K, typename Func>
 384         bool insert_with( K&& key, Func func )
 385         {
 386             scoped_node_ptr sp( cxx_node_allocator().MoveNew( m_Hasher, std::forward<K>(key)));
 387             if ( base_class::insert( *sp, [&func]( node_type& item ) { func( item.m_Value ); } )) {
 388                 sp.release();
 389                 return true;
 390             }
 391             return false;
 392         }
 393
 394         /// For key \p key inserts data of type \p value_type created in-place from <tt>std::forward<Args>(args)...</tt>
 395         /**
 396             Returns \p true if inserting successful, \p false otherwise.
 397
 398             The function locks RCU internally.
 399         */
 400         template <typename K, typename... Args>
 401         bool emplace( K&& key, Args&&... args )
 402         {
 403             scoped_node_ptr sp( cxx_node_allocator().MoveNew( m_Hasher, std::forward<K>(key), std::forward<Args>(args)... ));
 404             if ( base_class::insert( *sp )) {
 405                 sp.release();
 406                 return true;
 407             }
 408             return false;
 409         }
 410
 411         /// Updates data by \p key
 412         /**
 413             The operation performs inserting or replacing the element with lock-free manner.
 414
 415             If the \p key not found in the map, then the new item created from \p key
 416             will be inserted into the map iff \p bInsert is \p true
 417             (note that in this case the \ref key_type should be constructible from type \p K).
 418             Otherwise, if \p key is found, it is replaced with a new item created from
 419             \p key.
 420             The functor \p Func signature:
 421             \code
 422                 struct my_functor {
 423                     void operator()( value_type& item, value_type * old );
 424                 };
 425             \endcode
 426             where:
 427             - \p item - item of the map
 428             - \p old - old item of the map, if \p nullptr - the new item was inserted
 429
 430             The functor may change any fields of the \p item.second.
 431
 432             Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successfull,
 433             \p second is \p true if new item has been added or \p false if \p key already exists.
 434
 435             The function locks RCU internally.
 436
 437             @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
 438         */
 439         template <typename K, typename Func>
 440         std::pair<bool, bool> update( K&& key, Func func, bool bInsert = true )
 441         {
 442             scoped_node_ptr sp( cxx_node_allocator().MoveNew( m_Hasher, std::forward<K>(key)));
 443             std::pair<bool, bool> result = base_class::do_update( *sp,
 444                 [&func]( node_type& node, node_type * old ) { func( node.m_Value, old ? &old->m_Value : nullptr );},
 445                 bInsert );
 446             if ( result.first )
 447                 sp.release();
 448             return result;
 449         }
 450
 451         /// Delete \p key from the map
 452         /**
 453             \p key_type must be constructible from value of type \p K.
 454             The function deeltes the element with hash value equal to <tt>hash( key_type( key ))</tt>
 455
 456             Return \p true if \p key is found and deleted, \p false otherwise.
 457
 458             RCU should not be locked. The function locks RCU internally.
 459         */
 460         template <typename K>
 461         bool erase( K const& key )
 462         {
 463             return base_class::erase(m_Hasher(key_type(key)));
 464         }
 465
 466         /// Delete \p key from the map
 467         /**
 468             The function searches an item with hash value equal to <tt>hash( key_type( key ))</tt>,
 469             calls \p f functor and deletes the item. If \p key is not found, the functor is not called.
 470
 471             The functor \p Func interface:
 472             \code
 473             struct extractor {
 474                 void operator()(value_type& item) { ... }
 475             };
 476             \endcode
 477             where \p item is the element found.
 478
 479             \p key_type must be constructible from value of type \p K.
 480
 481             Return \p true if key is found and deleted, \p false otherwise
 482
 483             RCU should not be locked. The function locks RCU internally.
 484         */
 485         template <typename K, typename Func>
 486         bool erase( K const& key, Func f )
 487         {
 488             return base_class::erase(m_Hasher(key_type(key)), [&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