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-ize 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 - \p %MultiLevelHashMap uses a perfect hashing. It means that if two different keys, for example, of type \p std::string,
66 have identical hash then you cannot insert both that keys in the map. \p %MultiLevelHashMap does not maintain the key,
67 it maintains its fixed-size hash value.
69 The map supports @ref cds_container_MultilevelHashMap_iterators "bidirectional thread-safe iterators".
72 - \p GC - safe memory reclamation schema. Can be \p gc::HP, \p gc::DHP or one of \ref cds_urcu_type "RCU type"
73 - \p Key - a key type to be stored in the map
74 - \p T - a value type to be stored in the map
75 - \p Traits - type traits, the structure based on \p multilevel_hashmap::traits or result of \p multilevel_hashmap::make_traits metafunction.
77 There are several specializations of \p %MultiLevelHashMap for each \p GC. You should include:
78 - <tt><cds/container/multilevel_hashmap_hp.h></tt> for \p gc::HP garbage collector
79 - <tt><cds/container/multilevel_hashmap_dhp.h></tt> for \p gc::DHP garbage collector
80 - <tt><cds/container/multilevel_hashmap_rcu.h></tt> for \ref cds_intrusive_MultiLevelHashMap_rcu "RCU type". RCU specialization
81 has a slightly different interface.
87 #ifdef CDS_DOXYGEN_INVOKED
88 ,class Traits = multilevel_hashmap::traits
93 class MultiLevelHashMap
94 #ifdef CDS_DOXYGEN_INVOKED
95 : protected cds::intrusive::MultiLevelHashSet< GC, std::pair<Key const, T>, Traits >
97 : protected cds::container::details::make_multilevel_hashmap< GC, Key, T, Traits >::type
101 typedef cds::container::details::make_multilevel_hashmap< GC, Key, T, Traits > maker;
102 typedef typename maker::type base_class;
105 typedef GC gc; ///< Garbage collector
106 typedef Key key_type; ///< Key type
107 typedef T mapped_type; ///< Mapped type
108 typedef std::pair< key_type const, mapped_type> value_type; ///< Key-value pair to be stored in the map
109 typedef Traits traits; ///< Map traits
110 #ifdef CDS_DOXYGEN_INVOKED
111 typedef typename traits::hash hasher; ///< Hash functor, see \p multilevel_hashmap::traits::hash
113 typedef typename maker::hasher hasher;
116 typedef typename maker::hash_type hash_type; ///< Hash type deduced from \p hasher return type
117 typedef typename base_class::hash_comparator hash_comparator; ///< hash compare functor based on \p Traits::compare and \p Traits::less
119 typedef typename traits::item_counter item_counter; ///< Item counter type
120 typedef typename traits::allocator allocator; ///< Element allocator
121 typedef typename traits::node_allocator node_allocator; ///< Array node allocator
122 typedef typename traits::memory_model memory_model; ///< Memory model
123 typedef typename traits::back_off back_off; ///< Backoff strategy
124 typedef typename traits::stat stat; ///< Internal statistics type
126 /// Count of hazard pointers required
127 static CDS_CONSTEXPR size_t const c_nHazardPtrCount = base_class::c_nHazardPtrCount;
131 typedef typename maker::node_type node_type;
132 typedef typename maker::cxx_node_allocator cxx_node_allocator;
133 typedef std::unique_ptr< node_type, typename maker::node_disposer > scoped_node_ptr;
135 template <bool IsConst>
136 class bidirectional_iterator: public base_class::iterator_base
138 friend class MultiLevelHashMap;
139 typedef typename base_class::iterator_base iterator_base;
142 static CDS_CONSTEXPR bool const c_bConstantIterator = IsConst;
145 typedef typename std::conditional< IsConst, value_type const*, value_type*>::type value_ptr; ///< Value pointer
146 typedef typename std::conditional< IsConst, value_type const&, value_type&>::type value_ref; ///< Value reference
149 bidirectional_iterator() CDS_NOEXCEPT
152 bidirectional_iterator( bidirectional_iterator const& rhs ) CDS_NOEXCEPT
153 : iterator_base( rhs )
156 bidirectional_iterator& operator=(bidirectional_iterator const& rhs) CDS_NOEXCEPT
158 iterator_base::operator=( rhs );
162 bidirectional_iterator& operator++()
164 iterator_base::operator++();
168 bidirectional_iterator& operator--()
170 iterator_base::operator--();
174 value_ptr operator ->() const CDS_NOEXCEPT
176 node_type * p = iterator_base::pointer();
177 return p ? &p->m_Value : nullptr;
180 value_ref operator *() const CDS_NOEXCEPT
182 node_type * p = iterator_base::pointer();
189 iterator_base::release();
192 template <bool IsConst2>
193 bool operator ==(bidirectional_iterator<IsConst2> const& rhs) const CDS_NOEXCEPT
195 return iterator_base::operator==( rhs );
198 template <bool IsConst2>
199 bool operator !=(bidirectional_iterator<IsConst2> const& rhs) const CDS_NOEXCEPT
201 return !( *this == rhs );
204 public: // for internal use only!
205 bidirectional_iterator( base_class const& set, typename base_class::array_node * pNode, size_t idx, bool )
206 : iterator_base( set, pNode, idx, false )
209 bidirectional_iterator( base_class const& set, typename base_class::array_node * pNode, size_t idx )
210 : iterator_base( set, pNode, idx )
214 /// Reverse bidirectional iterator
215 template <bool IsConst>
216 class reverse_bidirectional_iterator : public base_class::iterator_base
218 friend class MultiLevelHashMap;
219 typedef typename base_class::iterator_base iterator_base;
222 typedef typename std::conditional< IsConst, value_type const*, value_type*>::type value_ptr; ///< Value pointer
223 typedef typename std::conditional< IsConst, value_type const&, value_type&>::type value_ref; ///< Value reference
226 reverse_bidirectional_iterator() CDS_NOEXCEPT
230 reverse_bidirectional_iterator( reverse_bidirectional_iterator const& rhs ) CDS_NOEXCEPT
231 : iterator_base( rhs )
234 reverse_bidirectional_iterator& operator=( reverse_bidirectional_iterator const& rhs) CDS_NOEXCEPT
236 iterator_base::operator=( rhs );
240 reverse_bidirectional_iterator& operator++()
242 iterator_base::operator--();
246 reverse_bidirectional_iterator& operator--()
248 iterator_base::operator++();
252 value_ptr operator ->() const CDS_NOEXCEPT
254 node_type * p = iterator_base::pointer();
255 return p ? &p->m_Value : nullptr;
258 value_ref operator *() const CDS_NOEXCEPT
260 node_type * p = iterator_base::pointer();
267 iterator_base::release();
270 template <bool IsConst2>
271 bool operator ==(reverse_bidirectional_iterator<IsConst2> const& rhs) const
273 return iterator_base::operator==( rhs );
276 template <bool IsConst2>
277 bool operator !=(reverse_bidirectional_iterator<IsConst2> const& rhs)
279 return !( *this == rhs );
282 public: // for internal use only!
283 reverse_bidirectional_iterator( base_class const& set, typename base_class::array_node * pNode, size_t idx, bool )
284 : iterator_base( set, pNode, idx, false )
287 reverse_bidirectional_iterator( base_class const& set, typename base_class::array_node * pNode, size_t idx )
288 : iterator_base( set, pNode, idx, false )
290 iterator_base::backward();
297 #ifdef CDS_DOXYGEN_INVOKED
299 typedef typename gc::template guarded_ptr< value_type > guarded_ptr;
301 typedef typename gc::template guarded_ptr< node_type, value_type, cds::container::details::guarded_ptr_cast_set<node_type, value_type> > guarded_ptr;
304 #ifdef CDS_DOXYGEN_INVOKED
305 typedef implementation_defined iterator; ///< @ref cds_container_MultilevelHashMap_iterators "bidirectional iterator" type
306 typedef implementation_defined const_iterator; ///< @ref cds_container_MultilevelHashMap_iterators "bidirectional const iterator" type
307 typedef implementation_defined reverse_iterator; ///< @ref cds_container_MultilevelHashMap_iterators "bidirectional reverse iterator" type
308 typedef implementation_defined const_reverse_iterator; ///< @ref cds_container_MultilevelHashMap_iterators "bidirectional reverse const iterator" type
310 typedef bidirectional_iterator<false> iterator;
311 typedef bidirectional_iterator<true> const_iterator;
312 typedef reverse_bidirectional_iterator<false> reverse_iterator;
313 typedef reverse_bidirectional_iterator<true> const_reverse_iterator;
322 /// Creates empty map
324 @param head_bits: 2<sup>head_bits</sup> specifies the size of head array, minimum is 4.
325 @param array_bits: 2<sup>array_bits</sup> specifies the size of array node, minimum is 2.
327 Equation for \p head_bits and \p array_bits:
329 sizeof(hash_type) * 8 == head_bits + N * array_bits
331 where \p N is multi-level array depth.
333 MultiLevelHashMap( size_t head_bits = 8, size_t array_bits = 4 )
334 : base_class( head_bits, array_bits )
337 /// Destructs the map and frees all data
341 /// Inserts new element with key and default value
343 The function creates an element with \p key and default value, and then inserts the node created into the map.
346 - The \p key_type should be constructible from a value of type \p K.
347 In trivial case, \p K is equal to \p key_type.
348 - The \p mapped_type should be default-constructible.
350 Returns \p true if inserting successful, \p false otherwise.
352 template <typename K>
353 bool insert( K&& key )
355 scoped_node_ptr sp( cxx_node_allocator().MoveNew( m_Hasher, std::forward<K>(key) ));
356 if ( base_class::insert( *sp )) {
363 /// Inserts new element
365 The function creates a node with copy of \p val value
366 and then inserts the node created into the map.
369 - The \p key_type should be constructible from \p key of type \p K.
370 - The \p value_type should be constructible from \p val of type \p V.
372 Returns \p true if \p val is inserted into the map, \p false otherwise.
374 template <typename K, typename V>
375 bool insert( K&& key, V&& val )
377 scoped_node_ptr sp( cxx_node_allocator().MoveNew( m_Hasher, std::forward<K>(key), std::forward<V>(val)));
378 if ( base_class::insert( *sp )) {
385 /// Inserts new element and initialize it by a functor
387 This function inserts new element with key \p key and if inserting is successful then it calls
388 \p func functor with signature
391 void operator()( value_type& item );
395 The argument \p item of user-defined functor \p func is the reference
396 to the map's item inserted:
397 - <tt>item.first</tt> is a const reference to item's key that cannot be changed.
398 - <tt>item.second</tt> is a reference to item's value that may be changed.
400 \p key_type should be constructible from value of type \p K.
402 The function allows to split creating of new item into two part:
403 - create item from \p key;
404 - insert new item into the map;
405 - if inserting is successful, initialize the value of item by calling \p func functor
407 This can be useful if complete initialization of object of \p value_type is heavyweight and
408 it is preferable that the initialization should be completed only if inserting is successful.
410 template <typename K, typename Func>
411 bool insert_with( K&& key, Func func )
413 scoped_node_ptr sp( cxx_node_allocator().MoveNew( m_Hasher, std::forward<K>(key)));
414 if ( base_class::insert( *sp, [&func]( node_type& item ) { func( item.m_Value ); } )) {
421 /// For key \p key inserts data of type \p value_type created in-place from <tt>std::forward<Args>(args)...</tt>
423 Returns \p true if inserting successful, \p false otherwise.
425 template <typename K, typename... Args>
426 bool emplace( K&& key, Args&&... args )
428 scoped_node_ptr sp( cxx_node_allocator().MoveNew( m_Hasher, std::forward<K>(key), std::forward<Args>(args)... ));
429 if ( base_class::insert( *sp )) {
436 /// Updates data by \p key
438 The operation performs inserting or replacing the element with lock-free manner.
440 If the \p key not found in the map, then the new item created from \p key
441 will be inserted into the map iff \p bInsert is \p true
442 (note that in this case the \ref key_type should be constructible from type \p K).
443 Otherwise, if \p key is found, it is replaced with a new item created from
445 The functor \p Func signature:
448 void operator()( value_type& item, value_type * old );
452 - \p item - item of the map
453 - \p old - old item of the map, if \p nullptr - the new item was inserted
455 The functor may change any fields of the \p item.second.
457 Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successfull,
458 \p second is \p true if new item has been added or \p false if \p key already exists.
460 @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
462 template <typename K, typename Func>
463 std::pair<bool, bool> update( K&& key, Func func, bool bInsert = true )
465 scoped_node_ptr sp( cxx_node_allocator().MoveNew( m_Hasher, std::forward<K>(key)));
466 std::pair<bool, bool> result = base_class::do_update( *sp,
467 [&func]( node_type& node, node_type * old ) { func( node.m_Value, old ? &old->m_Value : nullptr );},
474 /// Delete \p key from the map
476 \p key_type must be constructible from value of type \p K.
477 The function deeltes the element with hash value equal to <tt>hash( key_type( key ))</tt>
479 Return \p true if \p key is found and deleted, \p false otherwise.
481 template <typename K>
482 bool erase( K const& key )
484 hash_type h = m_Hasher( key_type( key ));
485 return base_class::erase( h );
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 hash_type h = m_Hasher( key_type( key ));
509 return base_class::erase( h, [&f]( node_type& node) { f( node.m_Value ); } );
512 /// Deletes the element pointed by iterator \p iter
514 Returns \p true if the operation is successful, \p false otherwise.
516 The function does not invalidate the iterator, it remains valid and can be used for further traversing.
518 bool erase_at( iterator const& iter )
520 return base_class::do_erase_at( iter );
523 bool erase_at( reverse_iterator const& iter )
525 return base_class::do_erase_at( iter );
529 /// Extracts the item from the map with specified \p key
531 The function searches an item with key equal to <tt>hash( key_type( key ))</tt> in the map,
532 unlinks it from the map, and returns a guarded pointer to the item found.
533 If \p key is not found the function returns an empty guarded pointer.
535 The item extracted is freed automatically by garbage collector \p GC
536 when returned \p guarded_ptr object will be destroyed or released.
537 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
541 typedef cds::container::MultiLevelHashMap< cds::gc::HP, int, foo, my_traits > map_type;
545 map_type::guarded_ptr gp( theMap.extract( 5 ));
550 // Destructor of gp releases internal HP guard and frees the pointer
554 template <typename K>
555 guarded_ptr extract( K const& key )
558 typename gc::Guard guard;
559 node_type * p = base_class::do_erase( m_Hasher( key_type( key )), guard, []( node_type const&) -> bool {return true;} );
561 // p is guarded by HP
567 /// Checks whether the map contains \p key
569 The function searches the item by its hash that is equal to <tt>hash( key_type( key ))</tt>
570 and returns \p true if it is found, or \p false otherwise.
572 template <typename K>
573 bool contains( K const& key )
575 return base_class::contains( m_Hasher( key_type( key )) );
578 /// Find the key \p key
581 The function searches the item by its hash that is equal to <tt>hash( key_type( key ))</tt>
582 and calls the functor \p f for item found.
583 The interface of \p Func functor is:
586 void operator()( value_type& item );
589 where \p item is the item found.
591 The functor may change \p item.second.
593 The function returns \p true if \p key is found, \p false otherwise.
595 template <typename K, typename Func>
596 bool find( K const& key, Func f )
598 return base_class::find( m_Hasher( key_type( key )), [&f](node_type& node) { f( node.m_Value );});
601 /// Finds the key \p key and return the item found
603 The function searches the item with a hash equal to <tt>hash( key_type( key ))</tt>
604 and returns a guarded pointer to the item found.
605 If \p key is not found the function returns an empty guarded pointer.
607 It is safe when a concurrent thread erases the item returned as \p guarded_ptr.
608 In this case the item will be freed later by garbage collector \p GC automatically
609 when \p guarded_ptr object will be destroyed or released.
610 @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
614 typedef cds::container::MultiLevelHashMap< cds::gc::HP, int, foo, my_traits > map_type;
618 map_type::guarded_ptr gp( theMap.get( 5 ));
623 // Destructor of guarded_ptr releases internal HP guard
627 template <typename K>
628 guarded_ptr get( K const& key )
632 typename gc::Guard guard;
633 gp.reset( base_class::search( m_Hasher( key_type( key )), guard ));
638 /// Clears the map (non-atomic)
640 The function unlink all data node from the map.
641 The function is not atomic but is thread-safe.
642 After \p %clear() the map may not be empty because another threads may insert items.
649 /// Checks if the map is empty
651 Emptiness is checked by item counting: if item count is zero then the map is empty.
652 Thus, the correct item counting feature is an important part of the map implementation.
656 return base_class::empty();
659 /// Returns item count in the map
662 return base_class::size();
665 /// Returns const reference to internal statistics
666 stat const& statistics() const
668 return base_class::statistics();
671 /// Returns the size of head node
672 size_t head_size() const
674 return base_class::head_size();
677 /// Returns the size of the array node
678 size_t array_node_size() const
680 return base_class::array_node_size();
684 ///@name Thread-safe iterators
685 /** @anchor cds_container_MultilevelHashMap_iterators
686 The map supports thread-safe iterators: you may iterate over the map in multi-threaded environment.
687 It is guaranteed that the iterators will remain valid even if another thread deletes the node the iterator points to:
688 Hazard Pointer embedded into the iterator object protects the node from physical reclamation.
690 @note Since the iterator object contains hazard pointer that is a thread-local resource,
691 the iterator should not be passed to another thread.
693 Each iterator object supports the common interface:
694 - dereference operators:
696 value_type [const] * operator ->() noexcept
697 value_type [const] & operator *() noexcept
699 - pre-increment and pre-decrement. Post-operators is not supported
700 - equality operators <tt>==</tt> and <tt>!=</tt>.
701 Iterators are equal iff they point to the same cell of the same array node.
702 Note that for two iterators \p it1 and \p it2, the conditon <tt> it1 == it2 </tt>
703 does not entail <tt> &(*it1) == &(*it2) </tt>
704 - helper member function \p release() that clears internal hazard pointer.
705 After \p release() the iterator points to \p nullptr but it still remain valid: further iterating is possible.
707 During iteration you may safely erase any item from the set;
708 @ref erase_at() function call doesn't invalidate any iterator.
709 If some iterator points to the item to be erased, that item is not deleted immediately
710 but only after that iterator will be advanced forward or backward.
712 @note It is possible the item can be iterated more that once, for example, if an iterator points to the item
713 in array node that is being splitted.
716 /// Returns an iterator to the beginning of the map
719 return base_class::template init_begin<iterator>();
722 /// Returns an const iterator to the beginning of the map
723 const_iterator begin() const
725 return base_class::template init_begin<const_iterator>();
728 /// Returns an const iterator to the beginning of the map
729 const_iterator cbegin()
731 return base_class::template init_begin<const_iterator>();
734 /// 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.
737 return base_class::template init_end<iterator>();
740 /// 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.
741 const_iterator end() const
743 return base_class::template init_end<const_iterator>();
746 /// 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.
747 const_iterator cend()
749 return base_class::template init_end<const_iterator>();
752 /// Returns a reverse iterator to the first element of the reversed map
753 reverse_iterator rbegin()
755 return base_class::template init_rbegin<reverse_iterator>();
758 /// Returns a const reverse iterator to the first element of the reversed map
759 const_reverse_iterator rbegin() const
761 return base_class::template init_rbegin<const_reverse_iterator>();
764 /// Returns a const reverse iterator to the first element of the reversed map
765 const_reverse_iterator crbegin()
767 return base_class::template init_rbegin<const_reverse_iterator>();
770 /// Returns a reverse iterator to the element following the last element of the reversed map
772 It corresponds to the element preceding the first element of the non-reversed container.
773 This element acts as a placeholder, attempting to access it results in undefined behavior.
775 reverse_iterator rend()
777 return base_class::template init_rend<reverse_iterator>();
780 /// Returns a const reverse iterator to the element following the last element of the reversed map
782 It corresponds to the element preceding the first element of the non-reversed container.
783 This element acts as a placeholder, attempting to access it results in undefined behavior.
785 const_reverse_iterator rend() const
787 return base_class::template init_rend<const_reverse_iterator>();
790 /// Returns a const reverse iterator to the element following the last element of the reversed map
792 It corresponds to the element preceding the first element of the non-reversed container.
793 This element acts as a placeholder, attempting to access it results in undefined behavior.
795 const_reverse_iterator crend()
797 return base_class::template init_rend<const_reverse_iterator>();
802 }} // namespace cds::container
804 #endif // #ifndef CDSLIB_CONTAINER_IMPL_MULTILEVEL_HASHMAP_H