3 #ifndef CDSLIB_CONTAINER_IMPL_MULTILEVEL_HASHMAP_H
4 #define CDSLIB_CONTAINER_IMPL_MULTILEVEL_HASHMAP_H
6 #include <cds/intrusive/impl/multilevel_hashset.h>
7 #include <cds/container/details/multilevel_hashmap_base.h>
8 #include <cds/container/details/guarded_ptr_cast.h>
10 namespace cds { namespace container {
12 /// Hash map based on multi-level array
13 /** @ingroup cds_nonintrusive_map
14 @anchor cds_container_MultilevelHashMap_hp
17 - [2013] Steven Feldman, Pierre LaBorde, Damian Dechev "Concurrent Multi-level Arrays:
18 Wait-free Extensible Hash Maps"
20 [From the paper] The hardest problem encountered while developing a parallel hash map is how to perform
21 a global resize, the process of redistributing the elements in a hash map that occurs when adding new
22 buckets. The negative impact of blocking synchronization is multiplied during a global resize, because all
23 threads will be forced to wait on the thread that is performing the involved process of resizing the hash map
24 and redistributing the elements. \p %MultilevelHashSet implementation avoids global resizes through new array
25 allocation. By allowing concurrent expansion this structure is free from the overhead of an explicit resize,
26 which facilitates concurrent operations.
28 The presented design includes dynamic hashing, the use of sub-arrays within the hash map data structure;
29 which, in combination with <b>perfect hashing</b>, means that each element has a unique final, as well as current, position.
30 It is important to note that the perfect hash function required by our hash map is trivial to realize as
31 any hash function that permutes the bits of the key is suitable. This is possible because of our approach
32 to the hash function; we require that it produces hash values that are equal in size to that of the key.
33 We know that if we expand the hash map a fixed number of times there can be no collision as duplicate keys
34 are not provided for in the standard semantics of a hash map.
36 \p %MultiLevelHashMap is a multi-level array which has an internal structure similar to a tree:
37 @image html multilevel_hashset.png
38 The multi-level array differs from a tree in that each position on the tree could hold an array of nodes or a single node.
39 A position that holds a single node is a \p dataNode which holds the hash value of a key and the value that is associated
40 with that key; it is a simple struct holding two variables. A \p dataNode in the multi-level array could be marked.
41 A \p markedDataNode refers to a pointer to a \p dataNode that has been bitmarked at the least significant bit (LSB)
42 of the pointer to the node. This signifies that this \p dataNode is contended. An expansion must occur at this node;
43 any thread that sees this \p markedDataNode will try to replace it with an \p arrayNode; which is a position that holds
44 an array of nodes. The pointer to an \p arrayNode is differentiated from that of a pointer to a \p dataNode by a bitmark
45 on the second-least significant bit.
47 \p %MultiLevelHashMap multi-level array is similar to a tree in that we keep a pointer to the root, which is a memory array
48 called \p head. The length of the \p head memory array is unique, whereas every other \p arrayNode has a uniform length;
49 a normal \p arrayNode has a fixed power-of-two length equal to the binary logarithm of a variable called \p arrayLength.
50 The maximum depth of the tree, \p maxDepth, is the maximum number of pointers that must be followed to reach any node.
51 We define \p currentDepth as the number of memory arrays that we need to traverse to reach the \p arrayNode on which
52 we need to operate; this is initially one, because of \p head.
54 That approach to the structure of the hash map uses an extensible hashing scheme; <b> the hash value is treated as a bit
55 string</b> and rehash incrementally.
57 @note Two important things you should keep in mind when you're using \p %MultiLevelHashMap:
58 - all keys is converted to fixed-size bit-string by hash functor provided.
59 You can use variable-length keys, for example, \p std::string as a key for \p %MultiLevelHashMap,
60 but real key in the map will be fixed-size hash values of your keys.
61 For the strings you may use well-known hashing algorithms like <a href="https://en.wikipedia.org/wiki/Secure_Hash_Algorithm">SHA1, SHA2</a>,
62 <a href="https://en.wikipedia.org/wiki/MurmurHash">MurmurHash</a>, <a href="https://en.wikipedia.org/wiki/CityHash">CityHash</a>
63 or its successor <a href="https://code.google.com/p/farmhash/">FarmHash</a> and so on, which
64 converts variable-length strings to fixed-length bit-strings, and such hash values will be the keys in \p %MultiLevelHashMap.
65 If your key is fixed-sized the hash functor is optional, see \p multilevel_hashmap::traits::hash for explanation and examples.
66 - \p %MultiLevelHashMap uses a perfect hashing. It means that if two different keys, for example, of type \p std::string,
67 have identical hash then you cannot insert both that keys in the map. \p %MultiLevelHashMap does not maintain the key,
68 it maintains its fixed-size hash value.
70 The map supports @ref cds_container_MultilevelHashMap_iterators "bidirectional thread-safe iterators".
73 - \p GC - safe memory reclamation schema. Can be \p gc::HP, \p gc::DHP or one of \ref cds_urcu_type "RCU type"
74 - \p Key - a key type to be stored in the map
75 - \p T - a value type to be stored in the map
76 - \p Traits - type traits, the structure based on \p multilevel_hashmap::traits or result of \p multilevel_hashmap::make_traits metafunction.
78 There are several specializations of \p %MultiLevelHashMap for each \p GC. You should include:
79 - <tt><cds/container/multilevel_hashmap_hp.h></tt> for \p gc::HP garbage collector
80 - <tt><cds/container/multilevel_hashmap_dhp.h></tt> for \p gc::DHP garbage collector
81 - <tt><cds/container/multilevel_hashmap_rcu.h></tt> for \ref cds_intrusive_MultiLevelHashMap_rcu "RCU type". RCU specialization
82 has a slightly different interface.
88 #ifdef CDS_DOXYGEN_INVOKED
89 ,class Traits = multilevel_hashmap::traits
94 class MultiLevelHashMap
95 #ifdef CDS_DOXYGEN_INVOKED
96 : protected cds::intrusive::MultiLevelHashSet< GC, std::pair<Key const, T>, Traits >
98 : protected cds::container::details::make_multilevel_hashmap< GC, Key, T, Traits >::type
102 typedef cds::container::details::make_multilevel_hashmap< GC, Key, T, Traits > maker;
103 typedef typename maker::type base_class;
106 typedef GC gc; ///< Garbage collector
107 typedef Key key_type; ///< Key type
108 typedef T mapped_type; ///< Mapped type
109 typedef std::pair< key_type const, mapped_type> value_type; ///< Key-value pair to be stored in the map
110 typedef Traits traits; ///< Map traits
111 #ifdef CDS_DOXYGEN_INVOKED
112 typedef typename traits::hash hasher; ///< Hash functor, see \p multilevel_hashmap::traits::hash
114 typedef typename maker::hasher hasher;
117 typedef typename maker::hash_type hash_type; ///< Hash type deduced from \p hasher return type
118 typedef typename base_class::hash_comparator hash_comparator; ///< hash compare functor based on \p Traits::compare and \p Traits::less
120 typedef typename traits::item_counter item_counter; ///< Item counter type
121 typedef typename traits::allocator allocator; ///< Element allocator
122 typedef typename traits::node_allocator node_allocator; ///< Array node allocator
123 typedef typename traits::memory_model memory_model; ///< Memory model
124 typedef typename traits::back_off back_off; ///< Backoff strategy
125 typedef typename traits::stat stat; ///< Internal statistics type
127 /// Count of hazard pointers required
128 static CDS_CONSTEXPR size_t const c_nHazardPtrCount = base_class::c_nHazardPtrCount;
132 typedef typename maker::node_type node_type;
133 typedef typename maker::cxx_node_allocator cxx_node_allocator;
134 typedef std::unique_ptr< node_type, typename maker::node_disposer > scoped_node_ptr;
136 template <bool IsConst>
137 class bidirectional_iterator: public base_class::iterator_base
139 friend class MultiLevelHashMap;
140 typedef typename base_class::iterator_base iterator_base;
143 static CDS_CONSTEXPR bool const c_bConstantIterator = IsConst;
146 typedef typename std::conditional< IsConst, value_type const*, value_type*>::type value_ptr; ///< Value pointer
147 typedef typename std::conditional< IsConst, value_type const&, value_type&>::type value_ref; ///< Value reference
150 bidirectional_iterator() CDS_NOEXCEPT
153 bidirectional_iterator( bidirectional_iterator const& rhs ) CDS_NOEXCEPT
154 : iterator_base( rhs )
157 bidirectional_iterator& operator=(bidirectional_iterator const& rhs) CDS_NOEXCEPT
159 iterator_base::operator=( rhs );
163 bidirectional_iterator& operator++()
165 iterator_base::operator++();
169 bidirectional_iterator& operator--()
171 iterator_base::operator--();
175 value_ptr operator ->() const CDS_NOEXCEPT
177 node_type * p = iterator_base::pointer();
178 return p ? &p->m_Value : nullptr;
181 value_ref operator *() const CDS_NOEXCEPT
183 node_type * p = iterator_base::pointer();
190 iterator_base::release();
193 template <bool IsConst2>
194 bool operator ==(bidirectional_iterator<IsConst2> const& rhs) const CDS_NOEXCEPT
196 return iterator_base::operator==( rhs );
199 template <bool IsConst2>
200 bool operator !=(bidirectional_iterator<IsConst2> const& rhs) const CDS_NOEXCEPT
202 return !( *this == rhs );
205 public: // for internal use only!
206 bidirectional_iterator( base_class const& set, typename base_class::array_node * pNode, size_t idx, bool )
207 : iterator_base( set, pNode, idx, false )
210 bidirectional_iterator( base_class const& set, typename base_class::array_node * pNode, size_t idx )
211 : iterator_base( set, pNode, idx )
215 /// Reverse bidirectional iterator
216 template <bool IsConst>
217 class reverse_bidirectional_iterator : public base_class::iterator_base
219 friend class MultiLevelHashMap;
220 typedef typename base_class::iterator_base iterator_base;
223 typedef typename std::conditional< IsConst, value_type const*, value_type*>::type value_ptr; ///< Value pointer
224 typedef typename std::conditional< IsConst, value_type const&, value_type&>::type value_ref; ///< Value reference
227 reverse_bidirectional_iterator() CDS_NOEXCEPT
231 reverse_bidirectional_iterator( reverse_bidirectional_iterator const& rhs ) CDS_NOEXCEPT
232 : iterator_base( rhs )
235 reverse_bidirectional_iterator& operator=( reverse_bidirectional_iterator const& rhs) CDS_NOEXCEPT
237 iterator_base::operator=( rhs );
241 reverse_bidirectional_iterator& operator++()
243 iterator_base::operator--();
247 reverse_bidirectional_iterator& operator--()
249 iterator_base::operator++();
253 value_ptr operator ->() const CDS_NOEXCEPT
255 node_type * p = iterator_base::pointer();
256 return p ? &p->m_Value : nullptr;
259 value_ref operator *() const CDS_NOEXCEPT
261 node_type * p = iterator_base::pointer();
268 iterator_base::release();
271 template <bool IsConst2>
272 bool operator ==(reverse_bidirectional_iterator<IsConst2> const& rhs) const
274 return iterator_base::operator==( rhs );
277 template <bool IsConst2>
278 bool operator !=(reverse_bidirectional_iterator<IsConst2> const& rhs)
280 return !( *this == rhs );
283 public: // for internal use only!
284 reverse_bidirectional_iterator( base_class const& set, typename base_class::array_node * pNode, size_t idx, bool )
285 : iterator_base( set, pNode, idx, false )
288 reverse_bidirectional_iterator( base_class const& set, typename base_class::array_node * pNode, size_t idx )
289 : iterator_base( set, pNode, idx, false )
291 iterator_base::backward();
298 #ifdef CDS_DOXYGEN_INVOKED
300 typedef typename gc::template guarded_ptr< value_type > guarded_ptr;
302 typedef typename gc::template guarded_ptr< node_type, value_type, cds::container::details::guarded_ptr_cast_set<node_type, value_type> > guarded_ptr;
305 #ifdef CDS_DOXYGEN_INVOKED
306 typedef implementation_defined iterator; ///< @ref cds_container_MultilevelHashMap_iterators "bidirectional iterator" type
307 typedef implementation_defined const_iterator; ///< @ref cds_container_MultilevelHashMap_iterators "bidirectional const iterator" type
308 typedef implementation_defined reverse_iterator; ///< @ref cds_container_MultilevelHashMap_iterators "bidirectional reverse iterator" type
309 typedef implementation_defined const_reverse_iterator; ///< @ref cds_container_MultilevelHashMap_iterators "bidirectional reverse const iterator" type
311 typedef bidirectional_iterator<false> iterator;
312 typedef bidirectional_iterator<true> const_iterator;
313 typedef reverse_bidirectional_iterator<false> reverse_iterator;
314 typedef reverse_bidirectional_iterator<true> const_reverse_iterator;
323 /// Creates empty map
325 @param head_bits: 2<sup>head_bits</sup> specifies the size of head array, minimum is 4.
326 @param array_bits: 2<sup>array_bits</sup> specifies the size of array node, minimum is 2.
328 Equation for \p head_bits and \p array_bits:
330 sizeof(hash_type) * 8 == head_bits + N * array_bits
332 where \p N is multi-level array depth.
334 MultiLevelHashMap( size_t head_bits = 8, size_t array_bits = 4 )
335 : base_class( head_bits, array_bits )
338 /// Destructs the map and frees all data
342 /// Inserts new element with key and default value
344 The function creates an element with \p key and default value, and then inserts the node created into the map.
347 - The \p key_type should be constructible from a value of type \p K.
348 In trivial case, \p K is equal to \p key_type.
349 - The \p mapped_type should be default-constructible.
351 Returns \p true if inserting successful, \p false otherwise.
353 template <typename K>
354 bool insert( K&& key )
356 scoped_node_ptr sp( cxx_node_allocator().MoveNew( m_Hasher, std::forward<K>(key) ));
357 if ( base_class::insert( *sp )) {
364 /// Inserts new element
366 The function creates a node with copy of \p val value
367 and then inserts the node created into the map.
370 - The \p key_type should be constructible from \p key of type \p K.
371 - The \p value_type should be constructible from \p val of type \p V.
373 Returns \p true if \p val is inserted into the map, \p false otherwise.
375 template <typename K, typename V>
376 bool insert( K&& key, V&& val )
378 scoped_node_ptr sp( cxx_node_allocator().MoveNew( m_Hasher, std::forward<K>(key), std::forward<V>(val)));
379 if ( base_class::insert( *sp )) {
386 /// Inserts new element and initialize it by a functor
388 This function inserts new element with key \p key and if inserting is successful then it calls
389 \p func functor with signature
392 void operator()( value_type& item );
396 The argument \p item of user-defined functor \p func is the reference
397 to the map's item inserted:
398 - <tt>item.first</tt> is a const reference to item's key that cannot be changed.
399 - <tt>item.second</tt> is a reference to item's value that may be changed.
401 \p key_type should be constructible from value of type \p K.
403 The function allows to split creating of new item into two part:
404 - create item from \p key;
405 - insert new item into the map;
406 - if inserting is successful, initialize the value of item by calling \p func functor
408 This can be useful if complete initialization of object of \p value_type is heavyweight and
409 it is preferable that the initialization should be completed only if inserting is successful.
411 template <typename K, typename Func>
412 bool insert_with( K&& key, Func func )
414 scoped_node_ptr sp( cxx_node_allocator().MoveNew( m_Hasher, std::forward<K>(key)));
415 if ( base_class::insert( *sp, [&func]( node_type& item ) { func( item.m_Value ); } )) {
422 /// For key \p key inserts data of type \p value_type created in-place from <tt>std::forward<Args>(args)...</tt>
424 Returns \p true if inserting successful, \p false otherwise.
426 template <typename K, typename... Args>
427 bool emplace( K&& key, Args&&... args )
429 scoped_node_ptr sp( cxx_node_allocator().MoveNew( m_Hasher, std::forward<K>(key), std::forward<Args>(args)... ));
430 if ( base_class::insert( *sp )) {
437 /// Updates data by \p key
439 The operation performs inserting or replacing the element with lock-free manner.
441 If the \p key not found in the map, then the new item created from \p key
442 will be inserted into the map iff \p bInsert is \p true
443 (note that in this case the \ref key_type should be constructible from type \p K).
444 Otherwise, if \p key is found, it is replaced with a new item created from
446 The functor \p Func signature:
449 void operator()( value_type& item, value_type * old );
453 - \p item - item of the map
454 - \p old - old item of the map, if \p nullptr - the new item was inserted
456 The functor may change any fields of the \p item.second.
458 Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successfull,
459 \p second is \p true if new item has been added or \p false if \p key already exists.
461 @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
463 template <typename K, typename Func>
464 std::pair<bool, bool> update( K&& key, Func func, bool bInsert = true )
466 scoped_node_ptr sp( cxx_node_allocator().MoveNew( m_Hasher, std::forward<K>(key)));
467 std::pair<bool, bool> result = base_class::do_update( *sp,
468 [&func]( node_type& node, node_type * old ) { func( node.m_Value, old ? &old->m_Value : nullptr );},
475 /// Delete \p key from the map
477 \p key_type must be constructible from value of type \p K.
478 The function deeltes the element with hash value equal to <tt>hash( key_type( key ))</tt>
480 Return \p true if \p key is found and deleted, \p false otherwise.
482 template <typename K>
483 bool erase( K const& key )
485 return base_class::erase( m_Hasher( key_type( key )));
488 /// Delete \p key from the map
490 The function searches an item with hash value equal to <tt>hash( key_type( key ))</tt>,
491 calls \p f functor and deletes the item. If \p key is not found, the functor is not called.
493 The functor \p Func interface:
496 void operator()(value_type& item) { ... }
499 where \p item is the element found.
501 \p key_type must be constructible from value of type \p K.
503 Return \p true if key is found and deleted, \p false otherwise
505 template <typename K, typename Func>
506 bool erase( K const& key, Func f )
508 return base_class::erase( m_Hasher(key_type(key)), [&f]( node_type& node) { f( node.m_Value ); } );
511 /// Deletes the element pointed by iterator \p iter
513 Returns \p true if the operation is successful, \p false otherwise.
515 The function does not invalidate the iterator, it remains valid and can be used for further traversing.
517 bool erase_at( iterator const& iter )
519 return base_class::do_erase_at( iter );
522 bool erase_at( reverse_iterator const& iter )
524 return base_class::do_erase_at( iter );
528 /// Extracts the item from the map with specified \p key
530 The function searches an item with key equal to <tt>hash( key_type( key ))</tt> in the map,
531 unlinks it from the map, and returns a guarded pointer to the item found.
532 If \p key is not found the function returns an empty guarded pointer.
534 The item extracted is freed automatically by garbage collector \p GC
535 when returned \p guarded_ptr object will be destroyed or released.
536 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
540 typedef cds::container::MultiLevelHashMap< cds::gc::HP, int, foo, my_traits > map_type;
544 map_type::guarded_ptr gp( theMap.extract( 5 ));
549 // Destructor of gp releases internal HP guard and frees the pointer
553 template <typename K>
554 guarded_ptr extract( K const& key )
557 typename gc::Guard guard;
558 node_type * p = base_class::do_erase( m_Hasher( key_type( key )), guard, []( node_type const&) -> bool {return true;} );
560 // p is guarded by HP
566 /// Checks whether the map contains \p key
568 The function searches the item by its hash that is equal to <tt>hash( key_type( key ))</tt>
569 and returns \p true if it is found, or \p false otherwise.
571 template <typename K>
572 bool contains( K const& key )
574 return base_class::contains( m_Hasher( key_type( key )) );
577 /// Find the key \p key
580 The function searches the item by its hash that is equal to <tt>hash( key_type( key ))</tt>
581 and calls the functor \p f for item found.
582 The interface of \p Func functor is:
585 void operator()( value_type& item );
588 where \p item is the item found.
590 The functor may change \p item.second.
592 The function returns \p true if \p key is found, \p false otherwise.
594 template <typename K, typename Func>
595 bool find( K const& key, Func f )
597 return base_class::find( m_Hasher( key_type( key )), [&f](node_type& node) { f( node.m_Value );});
600 /// Finds the key \p key and return the item found
602 The function searches the item with a hash equal to <tt>hash( key_type( key ))</tt>
603 and returns a guarded pointer to the item found.
604 If \p key is not found the function returns an empty guarded pointer.
606 It is safe when a concurrent thread erases the item returned as \p guarded_ptr.
607 In this case the item will be freed later by garbage collector \p GC automatically
608 when \p guarded_ptr object will be destroyed or released.
609 @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
613 typedef cds::container::MultiLevelHashMap< cds::gc::HP, int, foo, my_traits > map_type;
617 map_type::guarded_ptr gp( theMap.get( 5 ));
622 // Destructor of guarded_ptr releases internal HP guard
626 template <typename K>
627 guarded_ptr get( K const& key )
631 typename gc::Guard guard;
632 gp.reset( base_class::search( m_Hasher( key_type( key )), guard ));
637 /// Clears the map (non-atomic)
639 The function unlink all data node from the map.
640 The function is not atomic but is thread-safe.
641 After \p %clear() the map may not be empty because another threads may insert items.
648 /// Checks if the map is empty
650 Emptiness is checked by item counting: if item count is zero then the map is empty.
651 Thus, the correct item counting feature is an important part of the map implementation.
655 return base_class::empty();
658 /// Returns item count in the map
661 return base_class::size();
664 /// Returns const reference to internal statistics
665 stat const& statistics() const
667 return base_class::statistics();
670 /// Returns the size of head node
671 size_t head_size() const
673 return base_class::head_size();
676 /// Returns the size of the array node
677 size_t array_node_size() const
679 return base_class::array_node_size();
683 ///@name Thread-safe iterators
684 /** @anchor cds_container_MultilevelHashMap_iterators
685 The map supports thread-safe iterators: you may iterate over the map in multi-threaded environment.
686 It is guaranteed that the iterators will remain valid even if another thread deletes the node the iterator points to:
687 Hazard Pointer embedded into the iterator object protects the node from physical reclamation.
689 @note Since the iterator object contains hazard pointer that is a thread-local resource,
690 the iterator should not be passed to another thread.
692 Each iterator object supports the common interface:
693 - dereference operators:
695 value_type [const] * operator ->() noexcept
696 value_type [const] & operator *() noexcept
698 - pre-increment and pre-decrement. Post-operators is not supported
699 - equality operators <tt>==</tt> and <tt>!=</tt>.
700 Iterators are equal iff they point to the same cell of the same array node.
701 Note that for two iterators \p it1 and \p it2, the conditon <tt> it1 == it2 </tt>
702 does not entail <tt> &(*it1) == &(*it2) </tt>
703 - helper member function \p release() that clears internal hazard pointer.
704 After \p release() the iterator points to \p nullptr but it still remain valid: further iterating is possible.
706 During iteration you may safely erase any item from the set;
707 @ref erase_at() function call doesn't invalidate any iterator.
708 If some iterator points to the item to be erased, that item is not deleted immediately
709 but only after that iterator will be advanced forward or backward.
711 @note It is possible the item can be iterated more that once, for example, if an iterator points to the item
712 in array node that is being splitted.
715 /// Returns an iterator to the beginning of the map
718 return base_class::template init_begin<iterator>();
721 /// Returns an const iterator to the beginning of the map
722 const_iterator begin() const
724 return base_class::template init_begin<const_iterator>();
727 /// Returns an const iterator to the beginning of the map
728 const_iterator cbegin()
730 return base_class::template init_begin<const_iterator>();
733 /// 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.
736 return base_class::template init_end<iterator>();
739 /// 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.
740 const_iterator end() const
742 return base_class::template init_end<const_iterator>();
745 /// 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.
746 const_iterator cend()
748 return base_class::template init_end<const_iterator>();
751 /// Returns a reverse iterator to the first element of the reversed map
752 reverse_iterator rbegin()
754 return base_class::template init_rbegin<reverse_iterator>();
757 /// Returns a const reverse iterator to the first element of the reversed map
758 const_reverse_iterator rbegin() const
760 return base_class::template init_rbegin<const_reverse_iterator>();
763 /// Returns a const reverse iterator to the first element of the reversed map
764 const_reverse_iterator crbegin()
766 return base_class::template init_rbegin<const_reverse_iterator>();
769 /// Returns a reverse iterator to the element following the last element of the reversed map
771 It corresponds to the element preceding the first element of the non-reversed container.
772 This element acts as a placeholder, attempting to access it results in undefined behavior.
774 reverse_iterator rend()
776 return base_class::template init_rend<reverse_iterator>();
779 /// Returns a const reverse iterator to the element following the last element of the reversed map
781 It corresponds to the element preceding the first element of the non-reversed container.
782 This element acts as a placeholder, attempting to access it results in undefined behavior.
784 const_reverse_iterator rend() const
786 return base_class::template init_rend<const_reverse_iterator>();
789 /// Returns a const reverse iterator to the element following the last element of the reversed map
791 It corresponds to the element preceding the first element of the non-reversed container.
792 This element acts as a placeholder, attempting to access it results in undefined behavior.
794 const_reverse_iterator crend()
796 return base_class::template init_rend<const_reverse_iterator>();
801 }} // namespace cds::container
803 #endif // #ifndef CDSLIB_CONTAINER_IMPL_MULTILEVEL_HASHMAP_H