2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
6 Source code repo: http://github.com/khizmax/libcds/
7 Download: http://sourceforge.net/projects/libcds/files/
9 Redistribution and use in source and binary forms, with or without
10 modification, are permitted provided that the following conditions are met:
12 * Redistributions of source code must retain the above copyright notice, this
13 list of conditions and the following disclaimer.
15 * Redistributions in binary form must reproduce the above copyright notice,
16 this list of conditions and the following disclaimer in the documentation
17 and/or other materials provided with the distribution.
19 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
20 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
22 DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
23 FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
25 SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
26 CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
27 OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31 #ifndef CDSLIB_CONTAINER_IMPL_FELDMAN_HASHMAP_H
32 #define CDSLIB_CONTAINER_IMPL_FELDMAN_HASHMAP_H
34 #include <cds/intrusive/impl/feldman_hashset.h>
35 #include <cds/container/details/feldman_hashmap_base.h>
36 #include <cds/container/details/guarded_ptr_cast.h>
38 namespace cds { namespace container {
40 /// Hash map based on multi-level array
41 /** @ingroup cds_nonintrusive_map
42 @anchor cds_container_FeldmanHashMap_hp
45 - [2013] Steven Feldman, Pierre LaBorde, Damian Dechev "Concurrent Multi-level Arrays:
46 Wait-free Extensible Hash Maps"
48 [From the paper] The hardest problem encountered while developing a parallel hash map is how to perform
49 a global resize, the process of redistributing the elements in a hash map that occurs when adding new
50 buckets. The negative impact of blocking synchronization is multiplied during a global resize, because all
51 threads will be forced to wait on the thread that is performing the involved process of resizing the hash map
52 and redistributing the elements. \p %FeldmanHashSet implementation avoids global resizes through new array
53 allocation. By allowing concurrent expansion this structure is free from the overhead of an explicit resize,
54 which facilitates concurrent operations.
56 The presented design includes dynamic hashing, the use of sub-arrays within the hash map data structure;
57 which, in combination with <b>perfect hashing</b>, means that each element has a unique final, as well as current, position.
58 It is important to note that the perfect hash function required by our hash map is trivial to realize as
59 any hash function that permutes the bits of the key is suitable. This is possible because of our approach
60 to the hash function; we require that it produces hash values that are equal in size to that of the key.
61 We know that if we expand the hash map a fixed number of times there can be no collision as duplicate keys
62 are not provided for in the standard semantics of a hash map.
64 \p %FeldmanHashMap is a multi-level array which has an internal structure similar to a tree:
65 @image html feldman_hashset.png
66 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.
67 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
68 with that key; it is a simple struct holding two variables. A \p dataNode in the multi-level array could be marked.
69 A \p markedDataNode refers to a pointer to a \p dataNode that has been bitmarked at the least significant bit (LSB)
70 of the pointer to the node. This signifies that this \p dataNode is contended. An expansion must occur at this node;
71 any thread that sees this \p markedDataNode will try to replace it with an \p arrayNode; which is a position that holds
72 an array of nodes. The pointer to an \p arrayNode is differentiated from that of a pointer to a \p dataNode by a bitmark
73 on the second-least significant bit.
75 \p %FeldmanHashMap multi-level array is similar to a tree in that we keep a pointer to the root, which is a memory array
76 called \p head. The length of the \p head memory array is unique, whereas every other \p arrayNode has a uniform length;
77 a normal \p arrayNode has a fixed power-of-two length equal to the binary logarithm of a variable called \p arrayLength.
78 The maximum depth of the tree, \p maxDepth, is the maximum number of pointers that must be followed to reach any node.
79 We define \p currentDepth as the number of memory arrays that we need to traverse to reach the \p arrayNode on which
80 we need to operate; this is initially one, because of \p head.
82 That approach to the structure of the hash map uses an extensible hashing scheme; <b> the hash value is treated as a bit
83 string</b> and rehash incrementally.
85 @note Two important things you should keep in mind when you're using \p %FeldmanHashMap:
86 - all keys is converted to fixed-size bit-string by hash functor provided.
87 You can use variable-length keys, for example, \p std::string as a key for \p %FeldmanHashMap,
88 but real key in the map will be fixed-size hash values of your keys.
89 For the strings you may use well-known hashing algorithms like <a href="https://en.wikipedia.org/wiki/Secure_Hash_Algorithm">SHA1, SHA2</a>,
90 <a href="https://en.wikipedia.org/wiki/MurmurHash">MurmurHash</a>, <a href="https://en.wikipedia.org/wiki/CityHash">CityHash</a>
91 or its successor <a href="https://code.google.com/p/farmhash/">FarmHash</a> and so on, which
92 converts variable-length strings to fixed-length bit-strings, and such hash values will be the keys in \p %FeldmanHashMap.
93 If your key is fixed-sized the hash functor is optional, see \p feldman_hashmap::traits::hash for explanation and examples.
94 - \p %FeldmanHashMap uses a perfect hashing. It means that if two different keys, for example, of type \p std::string,
95 have identical hash then you cannot insert both that keys in the map. \p %FeldmanHashMap does not maintain the key,
96 it maintains its fixed-size hash value.
98 The map supports @ref cds_container_FeldmanHashMap_iterators "bidirectional thread-safe iterators".
101 - \p GC - safe memory reclamation schema. Can be \p gc::HP, \p gc::DHP or one of \ref cds_urcu_type "RCU type"
102 - \p Key - a key type to be stored in the map
103 - \p T - a value type to be stored in the map
104 - \p Traits - type traits, the structure based on \p feldman_hashmap::traits or result of \p feldman_hashmap::make_traits metafunction.
106 There are several specializations of \p %FeldmanHashMap for each \p GC. You should include:
107 - <tt><cds/container/feldman_hashmap_hp.h></tt> for \p gc::HP garbage collector
108 - <tt><cds/container/feldman_hashmap_dhp.h></tt> for \p gc::DHP garbage collector
109 - <tt><cds/container/feldman_hashmap_rcu.h></tt> for \ref cds_container_FeldmanHashMap_rcu "RCU type". RCU specialization
110 has a slightly different interface.
116 #ifdef CDS_DOXYGEN_INVOKED
117 ,class Traits = feldman_hashmap::traits
123 #ifdef CDS_DOXYGEN_INVOKED
124 : protected cds::intrusive::FeldmanHashSet< GC, std::pair<Key const, T>, Traits >
126 : protected cds::container::details::make_feldman_hashmap< GC, Key, T, Traits >::type
130 typedef cds::container::details::make_feldman_hashmap< GC, Key, T, Traits > maker;
131 typedef typename maker::type base_class;
134 typedef GC gc; ///< Garbage collector
135 typedef Key key_type; ///< Key type
136 typedef T mapped_type; ///< Mapped type
137 typedef std::pair< key_type const, mapped_type> value_type; ///< Key-value pair to be stored in the map
138 typedef Traits traits; ///< Map traits
139 #ifdef CDS_DOXYGEN_INVOKED
140 typedef typename traits::hash hasher; ///< Hash functor, see \p feldman_hashmap::traits::hash
142 typedef typename maker::hasher hasher;
145 typedef typename maker::hash_type hash_type; ///< Hash type deduced from \p hasher return type
146 typedef typename base_class::hash_comparator hash_comparator; ///< hash compare functor based on \p Traits::compare and \p Traits::less
148 typedef typename traits::item_counter item_counter; ///< Item counter type
149 typedef typename traits::allocator allocator; ///< Element allocator
150 typedef typename traits::node_allocator node_allocator; ///< Array node allocator
151 typedef typename traits::memory_model memory_model; ///< Memory model
152 typedef typename traits::back_off back_off; ///< Backoff strategy
153 typedef typename traits::stat stat; ///< Internal statistics type
155 /// Count of hazard pointers required
156 static CDS_CONSTEXPR size_t const c_nHazardPtrCount = base_class::c_nHazardPtrCount;
159 typedef feldman_hashmap::level_statistics level_statistics;
163 typedef typename maker::node_type node_type;
164 typedef typename maker::cxx_node_allocator cxx_node_allocator;
165 typedef std::unique_ptr< node_type, typename maker::node_disposer > scoped_node_ptr;
167 template <bool IsConst>
168 class bidirectional_iterator: public base_class::iterator_base
170 friend class FeldmanHashMap;
171 typedef typename base_class::iterator_base iterator_base;
174 static CDS_CONSTEXPR bool const c_bConstantIterator = IsConst;
177 typedef typename std::conditional< IsConst, value_type const*, value_type*>::type value_ptr; ///< Value pointer
178 typedef typename std::conditional< IsConst, value_type const&, value_type&>::type value_ref; ///< Value reference
181 bidirectional_iterator() CDS_NOEXCEPT
184 bidirectional_iterator( bidirectional_iterator const& rhs ) CDS_NOEXCEPT
185 : iterator_base( rhs )
188 bidirectional_iterator& operator=( bidirectional_iterator const& rhs ) CDS_NOEXCEPT
190 iterator_base::operator=( rhs );
194 bidirectional_iterator& operator++()
196 iterator_base::operator++();
200 bidirectional_iterator& operator--()
202 iterator_base::operator--();
206 value_ptr operator ->() const CDS_NOEXCEPT
208 node_type * p = iterator_base::pointer();
209 return p ? &p->m_Value : nullptr;
212 value_ref operator *() const CDS_NOEXCEPT
214 node_type * p = iterator_base::pointer();
221 iterator_base::release();
224 template <bool IsConst2>
225 bool operator ==( bidirectional_iterator<IsConst2> const& rhs ) const CDS_NOEXCEPT
227 return iterator_base::operator==( rhs );
230 template <bool IsConst2>
231 bool operator !=( bidirectional_iterator<IsConst2> const& rhs ) const CDS_NOEXCEPT
233 return !( *this == rhs );
236 public: // for internal use only!
237 bidirectional_iterator( base_class const& set, typename base_class::array_node * pNode, size_t idx, bool )
238 : iterator_base( set, pNode, idx, false )
241 bidirectional_iterator( base_class const& set, typename base_class::array_node * pNode, size_t idx )
242 : iterator_base( set, pNode, idx )
246 /// Reverse bidirectional iterator
247 template <bool IsConst>
248 class reverse_bidirectional_iterator : public base_class::iterator_base
250 friend class FeldmanHashMap;
251 typedef typename base_class::iterator_base iterator_base;
254 typedef typename std::conditional< IsConst, value_type const*, value_type*>::type value_ptr; ///< Value pointer
255 typedef typename std::conditional< IsConst, value_type const&, value_type&>::type value_ref; ///< Value reference
258 reverse_bidirectional_iterator() CDS_NOEXCEPT
262 reverse_bidirectional_iterator( reverse_bidirectional_iterator const& rhs ) CDS_NOEXCEPT
263 : iterator_base( rhs )
266 reverse_bidirectional_iterator& operator=( reverse_bidirectional_iterator const& rhs) CDS_NOEXCEPT
268 iterator_base::operator=( rhs );
272 reverse_bidirectional_iterator& operator++()
274 iterator_base::operator--();
278 reverse_bidirectional_iterator& operator--()
280 iterator_base::operator++();
284 value_ptr operator ->() const CDS_NOEXCEPT
286 node_type * p = iterator_base::pointer();
287 return p ? &p->m_Value : nullptr;
290 value_ref operator *() const CDS_NOEXCEPT
292 node_type * p = iterator_base::pointer();
299 iterator_base::release();
302 template <bool IsConst2>
303 bool operator ==( reverse_bidirectional_iterator<IsConst2> const& rhs ) const
305 return iterator_base::operator==( rhs );
308 template <bool IsConst2>
309 bool operator !=( reverse_bidirectional_iterator<IsConst2> const& rhs )
311 return !( *this == rhs );
314 public: // for internal use only!
315 reverse_bidirectional_iterator( base_class const& set, typename base_class::array_node * pNode, size_t idx, bool )
316 : iterator_base( set, pNode, idx, false )
319 reverse_bidirectional_iterator( base_class const& set, typename base_class::array_node * pNode, size_t idx )
320 : iterator_base( set, pNode, idx, false )
322 iterator_base::backward();
329 #ifdef CDS_DOXYGEN_INVOKED
331 typedef typename gc::template guarded_ptr< value_type > guarded_ptr;
333 typedef typename gc::template guarded_ptr< node_type, value_type, cds::container::details::guarded_ptr_cast_set<node_type, value_type> > guarded_ptr;
336 #ifdef CDS_DOXYGEN_INVOKED
337 typedef implementation_defined iterator; ///< @ref cds_container_FeldmanHashMap_iterators "bidirectional iterator" type
338 typedef implementation_defined const_iterator; ///< @ref cds_container_FeldmanHashMap_iterators "bidirectional const iterator" type
339 typedef implementation_defined reverse_iterator; ///< @ref cds_container_FeldmanHashMap_iterators "bidirectional reverse iterator" type
340 typedef implementation_defined const_reverse_iterator; ///< @ref cds_container_FeldmanHashMap_iterators "bidirectional reverse const iterator" type
342 typedef bidirectional_iterator<false> iterator;
343 typedef bidirectional_iterator<true> const_iterator;
344 typedef reverse_bidirectional_iterator<false> reverse_iterator;
345 typedef reverse_bidirectional_iterator<true> const_reverse_iterator;
354 /// Creates empty map
356 @param head_bits: 2<sup>head_bits</sup> specifies the size of head array, minimum is 4.
357 @param array_bits: 2<sup>array_bits</sup> specifies the size of array node, minimum is 2.
359 Equation for \p head_bits and \p array_bits:
361 sizeof( hash_type ) * 8 == head_bits + N * array_bits
363 where \p N is multi-level array depth.
365 FeldmanHashMap( size_t head_bits = 8, size_t array_bits = 4 )
366 : base_class( head_bits, array_bits )
369 /// Destructs the map and frees all data
373 /// Inserts new element with key and default value
375 The function creates an element with \p key and default value, and then inserts the node created into the map.
378 - The \p key_type should be constructible from a value of type \p K.
379 In trivial case, \p K is equal to \p key_type.
380 - The \p mapped_type should be default-constructible.
382 Returns \p true if inserting successful, \p false otherwise.
384 template <typename K>
385 bool insert( K&& key )
387 scoped_node_ptr sp( cxx_node_allocator().MoveNew( m_Hasher, std::forward<K>( key ) ));
388 if ( base_class::insert( *sp )) {
395 /// Inserts new element
397 The function creates a node with copy of \p val value
398 and then inserts the node created into the map.
401 - The \p key_type should be constructible from \p key of type \p K.
402 - The \p value_type should be constructible from \p val of type \p V.
404 Returns \p true if \p val is inserted into the map, \p false otherwise.
406 template <typename K, typename V>
407 bool insert( K&& key, V&& val )
409 scoped_node_ptr sp( cxx_node_allocator().MoveNew( m_Hasher, std::forward<K>( key ), std::forward<V>( val )));
410 if ( base_class::insert( *sp )) {
417 /// Inserts new element and initialize it by a functor
419 This function inserts new element with key \p key and if inserting is successful then it calls
420 \p func functor with signature
423 void operator()( value_type& item );
427 The argument \p item of user-defined functor \p func is the reference
428 to the map's item inserted:
429 - <tt>item.first</tt> is a const reference to item's key that cannot be changed.
430 - <tt>item.second</tt> is a reference to item's value that may be changed.
432 \p key_type should be constructible from value of type \p K.
434 The function allows to split creating of new item into two part:
435 - create item from \p key;
436 - insert new item into the map;
437 - if inserting is successful, initialize the value of item by calling \p func functor
439 This can be useful if complete initialization of object of \p value_type is heavyweight and
440 it is preferable that the initialization should be completed only if inserting is successful.
442 template <typename K, typename Func>
443 bool insert_with( K&& key, Func func )
445 scoped_node_ptr sp( cxx_node_allocator().MoveNew( m_Hasher, std::forward<K>( key )));
446 if ( base_class::insert( *sp, [&func]( node_type& item ) { func( item.m_Value ); } )) {
453 /// For key \p key inserts data of type \p value_type created in-place from <tt>std::forward<Args>(args)...</tt>
455 Returns \p true if inserting successful, \p false otherwise.
457 template <typename K, typename... Args>
458 bool emplace( K&& key, Args&&... args )
460 scoped_node_ptr sp( cxx_node_allocator().MoveNew( m_Hasher, std::forward<K>( key ), std::forward<Args>( args )... ));
461 if ( base_class::insert( *sp )) {
468 /// Updates data by \p key
470 The operation performs inserting or replacing the element with lock-free manner.
472 If the \p key not found in the map, then the new item created from \p key
473 will be inserted into the map iff \p bInsert is \p true
474 (note that in this case the \ref key_type should be constructible from type \p K).
475 Otherwise, if \p key is found, it is replaced with a new item created from
477 The functor \p Func signature:
480 void operator()( value_type& item, value_type * old );
484 - \p item - item of the map
485 - \p old - old item of the map, if \p nullptr - the new item was inserted
487 The functor may change any fields of the \p item.second.
489 Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successful,
490 \p second is \p true if new item has been added or \p false if \p key already exists.
492 @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
494 template <typename K, typename Func>
495 std::pair<bool, bool> update( K&& key, Func func, bool bInsert = true )
497 scoped_node_ptr sp( cxx_node_allocator().MoveNew( m_Hasher, std::forward<K>( key )));
498 std::pair<bool, bool> result = base_class::do_update( *sp,
499 [&func]( node_type& node, node_type * old ) { func( node.m_Value, old ? &old->m_Value : nullptr );},
506 /// Delete \p key from the map
508 \p key_type must be constructible from value of type \p K.
509 The function deletes the element with hash value equal to <tt>hash( key_type( key ))</tt>
511 Return \p true if \p key is found and deleted, \p false otherwise.
513 template <typename K>
514 bool erase( K const& key )
516 return base_class::erase( m_Hasher( key_type( key )));
519 /// Delete \p key from the map
521 The function searches an item with hash value equal to <tt>hash( key_type( key ))</tt>,
522 calls \p f functor and deletes the item. If \p key is not found, the functor is not called.
524 The functor \p Func interface:
527 void operator()( value_type& item ) { ... }
530 where \p item is the element found.
532 \p key_type must be constructible from value of type \p K.
534 Return \p true if key is found and deleted, \p false otherwise
536 template <typename K, typename Func>
537 bool erase( K const& key, Func f )
539 return base_class::erase( m_Hasher( key_type( key )), [&f]( node_type& node) { f( node.m_Value ); } );
542 /// Deletes the element pointed by iterator \p iter
544 Returns \p true if the operation is successful, \p false otherwise.
546 The function does not invalidate the iterator, it remains valid and can be used for further traversing.
548 bool erase_at( iterator const& iter )
550 return base_class::do_erase_at( iter );
553 bool erase_at( reverse_iterator const& iter )
555 return base_class::do_erase_at( iter );
557 bool erase_at( const_iterator const& iter )
559 return base_class::do_erase_at( iter );
561 bool erase_at( const_reverse_iterator const& iter )
563 return base_class::do_erase_at( iter );
567 /// Extracts the item from the map with specified \p key
569 The function searches an item with key equal to <tt>hash( key_type( key ))</tt> in the map,
570 unlinks it from the map, and returns a guarded pointer to the item found.
571 If \p key is not found the function returns an empty guarded pointer.
573 The item extracted is freed automatically by garbage collector \p GC
574 when returned \p guarded_ptr object will be destroyed or released.
575 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
579 typedef cds::container::FeldmanHashMap< cds::gc::HP, int, foo, my_traits > map_type;
583 map_type::guarded_ptr gp( theMap.extract( 5 ));
588 // Destructor of gp releases internal HP guard and frees the pointer
592 template <typename K>
593 guarded_ptr extract( K const& key )
596 typename gc::Guard guard;
597 node_type * p = base_class::do_erase( m_Hasher( key_type( key )), guard, []( node_type const&) -> bool {return true;} );
599 // p is guarded by HP
605 /// Checks whether the map contains \p key
607 The function searches the item by its hash that is equal to <tt>hash( key_type( key ))</tt>
608 and returns \p true if it is found, or \p false otherwise.
610 template <typename K>
611 bool contains( K const& key )
613 return base_class::contains( m_Hasher( key_type( key )) );
616 /// Find the key \p key
619 The function searches the item by its hash that is equal to <tt>hash( key_type( key ))</tt>
620 and calls the functor \p f for item found.
621 The interface of \p Func functor is:
624 void operator()( value_type& item );
627 where \p item is the item found.
629 The functor may change \p item.second.
631 The function returns \p true if \p key is found, \p false otherwise.
633 template <typename K, typename Func>
634 bool find( K const& key, Func f )
636 return base_class::find( m_Hasher( key_type( key )), [&f]( node_type& node ) { f( node.m_Value );});
639 /// Finds the key \p key and return the item found
641 The function searches the item with a hash equal to <tt>hash( key_type( key ))</tt>
642 and returns a guarded pointer to the item found.
643 If \p key is not found the function returns an empty guarded pointer.
645 It is safe when a concurrent thread erases the item returned as \p guarded_ptr.
646 In this case the item will be freed later by garbage collector \p GC automatically
647 when \p guarded_ptr object will be destroyed or released.
648 @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
652 typedef cds::container::FeldmanHashMap< cds::gc::HP, int, foo, my_traits > map_type;
656 map_type::guarded_ptr gp( theMap.get( 5 ));
661 // Destructor of guarded_ptr releases internal HP guard
665 template <typename K>
666 guarded_ptr get( K const& key )
670 typename gc::Guard guard;
671 gp.reset( base_class::search( m_Hasher( key_type( key )), guard ));
676 /// Clears the map (non-atomic)
678 The function unlink all data node from the map.
679 The function is not atomic but is thread-safe.
680 After \p %clear() the map may not be empty because another threads may insert items.
687 /// Checks if the map is empty
689 Emptiness is checked by item counting: if item count is zero then the map is empty.
690 Thus, the correct item counting feature is an important part of the map implementation.
694 return base_class::empty();
697 /// Returns item count in the map
700 return base_class::size();
703 /// Returns const reference to internal statistics
704 stat const& statistics() const
706 return base_class::statistics();
709 /// Returns the size of head node
710 size_t head_size() const
712 return base_class::head_size();
715 /// Returns the size of the array node
716 size_t array_node_size() const
718 return base_class::array_node_size();
721 /// Collects tree level statistics into \p stat
723 The function traverses the set and collects statistics for each level of the tree
724 into \p feldman_hashset::level_statistics struct. The element of \p stat[i]
725 represents statistics for level \p i, level 0 is head array.
726 The function is thread-safe and may be called in multi-threaded environment.
728 Result can be useful for estimating efficiency of hash functor you use.
730 void get_level_statistics( std::vector< feldman_hashmap::level_statistics>& stat) const
732 base_class::get_level_statistics( stat );
736 ///@name Thread-safe iterators
737 /** @anchor cds_container_FeldmanHashMap_iterators
738 The map supports thread-safe iterators: you may iterate over the map in multi-threaded environment.
739 It is guaranteed that the iterators will remain valid even if another thread deletes the node the iterator points to:
740 Hazard Pointer embedded into the iterator object protects the node from physical reclamation.
742 @note Since the iterator object contains hazard pointer that is a thread-local resource,
743 the iterator should not be passed to another thread.
745 Each iterator object supports the common interface:
746 - dereference operators:
748 value_type [const] * operator ->() noexcept
749 value_type [const] & operator *() noexcept
751 - pre-increment and pre-decrement. Post-operators is not supported
752 - equality operators <tt>==</tt> and <tt>!=</tt>.
753 Iterators are equal iff they point to the same cell of the same array node.
754 Note that for two iterators \p it1 and \p it2, the conditon <tt> it1 == it2 </tt>
755 does not entail <tt> &(*it1) == &(*it2) </tt>
756 - helper member function \p release() that clears internal hazard pointer.
757 After \p release() the iterator points to \p nullptr but it still remain valid: further iterating is possible.
759 During iteration you may safely erase any item from the set;
760 @ref erase_at() function call doesn't invalidate any iterator.
761 If some iterator points to the item to be erased, that item is not deleted immediately
762 but only after that iterator will be advanced forward or backward.
764 @note It is possible the item can be iterated more that once, for example, if an iterator points to the item
765 in array node that is being splitted.
768 /// Returns an iterator to the beginning of the map
771 return base_class::template init_begin<iterator>();
774 /// Returns an const iterator to the beginning of the map
775 const_iterator begin() const
777 return base_class::template init_begin<const_iterator>();
780 /// Returns an const iterator to the beginning of the map
781 const_iterator cbegin()
783 return base_class::template init_begin<const_iterator>();
786 /// 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.
789 return base_class::template init_end<iterator>();
792 /// 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.
793 const_iterator end() const
795 return base_class::template init_end<const_iterator>();
798 /// 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.
799 const_iterator cend()
801 return base_class::template init_end<const_iterator>();
804 /// Returns a reverse iterator to the first element of the reversed map
805 reverse_iterator rbegin()
807 return base_class::template init_rbegin<reverse_iterator>();
810 /// Returns a const reverse iterator to the first element of the reversed map
811 const_reverse_iterator rbegin() const
813 return base_class::template init_rbegin<const_reverse_iterator>();
816 /// Returns a const reverse iterator to the first element of the reversed map
817 const_reverse_iterator crbegin()
819 return base_class::template init_rbegin<const_reverse_iterator>();
822 /// Returns a reverse iterator to the element following the last element of the reversed map
824 It corresponds to the element preceding the first element of the non-reversed container.
825 This element acts as a placeholder, attempting to access it results in undefined behavior.
827 reverse_iterator rend()
829 return base_class::template init_rend<reverse_iterator>();
832 /// Returns a const reverse iterator to the element following the last element of the reversed map
834 It corresponds to the element preceding the first element of the non-reversed container.
835 This element acts as a placeholder, attempting to access it results in undefined behavior.
837 const_reverse_iterator rend() const
839 return base_class::template init_rend<const_reverse_iterator>();
842 /// Returns a const reverse iterator to the element following the last element of the reversed map
844 It corresponds to the element preceding the first element of the non-reversed container.
845 This element acts as a placeholder, attempting to access it results in undefined behavior.
847 const_reverse_iterator crend()
849 return base_class::template init_rend<const_reverse_iterator>();
854 }} // namespace cds::container
856 #endif // #ifndef CDSLIB_CONTAINER_IMPL_FELDMAN_HASHMAP_H