Docfix
[libcds.git] / cds / container / impl / feldman_hashmap.h
1 /*
2     This file is a part of libcds - Concurrent Data Structures library
3
4     (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
5
6     Source code repo: http://github.com/khizmax/libcds/
7     Download: http://sourceforge.net/projects/libcds/files/
8     
9     Redistribution and use in source and binary forms, with or without
10     modification, are permitted provided that the following conditions are met:
11
12     * Redistributions of source code must retain the above copyright notice, this
13       list of conditions and the following disclaimer.
14
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.
18
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.     
29 */
30
31 #ifndef CDSLIB_CONTAINER_IMPL_FELDMAN_HASHMAP_H
32 #define CDSLIB_CONTAINER_IMPL_FELDMAN_HASHMAP_H
33
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>
37
38 namespace cds { namespace container {
39
40     /// Hash map based on multi-level array
41     /** @ingroup cds_nonintrusive_map
42         @anchor cds_container_FeldmanHashMap_hp
43
44         Source:
45         - [2013] Steven Feldman, Pierre LaBorde, Damian Dechev "Concurrent Multi-level Arrays:
46                  Wait-free Extensible Hash Maps"
47
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.
55
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.
63
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.
74
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.
81
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.
84
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.
97
98         The map supports @ref cds_container_FeldmanHashMap_iterators "bidirectional thread-safe iterators".
99
100         Template parameters:
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.
105
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.
111     */
112     template <
113         class GC
114         ,typename Key
115         ,typename T
116 #ifdef CDS_DOXYGEN_INVOKED
117         ,class Traits = feldman_hashmap::traits
118 #else
119         ,class Traits
120 #endif
121     >
122     class FeldmanHashMap
123 #ifdef CDS_DOXYGEN_INVOKED
124         : protected cds::intrusive::FeldmanHashSet< GC, std::pair<Key const, T>, Traits >
125 #else
126         : protected cds::container::details::make_feldman_hashmap< GC, Key, T, Traits >::type
127 #endif
128     {
129         //@cond
130         typedef cds::container::details::make_feldman_hashmap< GC, Key, T, Traits > maker;
131         typedef typename maker::type base_class;
132         //@endcond
133     public:
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
141 #else
142         typedef typename maker::hasher hasher;
143 #endif
144
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
147
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
154
155         /// Count of hazard pointers required
156         static CDS_CONSTEXPR size_t const c_nHazardPtrCount = base_class::c_nHazardPtrCount;
157
158     protected:
159         //@cond
160         typedef typename maker::node_type node_type;
161         typedef typename maker::cxx_node_allocator cxx_node_allocator;
162         typedef std::unique_ptr< node_type, typename maker::node_disposer > scoped_node_ptr;
163
164         template <bool IsConst>
165         class bidirectional_iterator: public base_class::iterator_base
166         {
167             friend class FeldmanHashMap;
168             typedef typename base_class::iterator_base iterator_base;
169
170         protected:
171             static CDS_CONSTEXPR bool const c_bConstantIterator = IsConst;
172
173         public:
174             typedef typename std::conditional< IsConst, value_type const*, value_type*>::type value_ptr; ///< Value pointer
175             typedef typename std::conditional< IsConst, value_type const&, value_type&>::type value_ref; ///< Value reference
176
177         public:
178             bidirectional_iterator() CDS_NOEXCEPT
179             {}
180
181             bidirectional_iterator( bidirectional_iterator const& rhs ) CDS_NOEXCEPT
182                 : iterator_base( rhs )
183             {}
184
185             bidirectional_iterator& operator=(bidirectional_iterator const& rhs) CDS_NOEXCEPT
186             {
187                 iterator_base::operator=( rhs );
188                 return *this;
189             }
190
191             bidirectional_iterator& operator++()
192             {
193                 iterator_base::operator++();
194                 return *this;
195             }
196
197             bidirectional_iterator& operator--()
198             {
199                 iterator_base::operator--();
200                 return *this;
201             }
202
203             value_ptr operator ->() const CDS_NOEXCEPT
204             {
205                 node_type * p = iterator_base::pointer();
206                 return p ? &p->m_Value : nullptr;
207             }
208
209             value_ref operator *() const CDS_NOEXCEPT
210             {
211                 node_type * p = iterator_base::pointer();
212                 assert( p );
213                 return p->m_Value;
214             }
215
216             void release()
217             {
218                 iterator_base::release();
219             }
220
221             template <bool IsConst2>
222             bool operator ==(bidirectional_iterator<IsConst2> const& rhs) const CDS_NOEXCEPT
223             {
224                 return iterator_base::operator==( rhs );
225             }
226
227             template <bool IsConst2>
228             bool operator !=(bidirectional_iterator<IsConst2> const& rhs) const CDS_NOEXCEPT
229             {
230                 return !( *this == rhs );
231             }
232
233         public: // for internal use only!
234             bidirectional_iterator( base_class const& set, typename base_class::array_node * pNode, size_t idx, bool )
235                 : iterator_base( set, pNode, idx, false )
236             {}
237
238             bidirectional_iterator( base_class const& set, typename base_class::array_node * pNode, size_t idx )
239                 : iterator_base( set, pNode, idx )
240             {}
241         };
242
243         /// Reverse bidirectional iterator
244         template <bool IsConst>
245         class reverse_bidirectional_iterator : public base_class::iterator_base
246         {
247             friend class FeldmanHashMap;
248             typedef typename base_class::iterator_base iterator_base;
249
250         public:
251             typedef typename std::conditional< IsConst, value_type const*, value_type*>::type value_ptr; ///< Value pointer
252             typedef typename std::conditional< IsConst, value_type const&, value_type&>::type value_ref; ///< Value reference
253
254         public:
255             reverse_bidirectional_iterator() CDS_NOEXCEPT
256                 : iterator_base()
257             {}
258
259             reverse_bidirectional_iterator( reverse_bidirectional_iterator const& rhs ) CDS_NOEXCEPT
260                 : iterator_base( rhs )
261             {}
262
263             reverse_bidirectional_iterator& operator=( reverse_bidirectional_iterator const& rhs) CDS_NOEXCEPT
264             {
265                 iterator_base::operator=( rhs );
266                 return *this;
267             }
268
269             reverse_bidirectional_iterator& operator++()
270             {
271                 iterator_base::operator--();
272                 return *this;
273             }
274
275             reverse_bidirectional_iterator& operator--()
276             {
277                 iterator_base::operator++();
278                 return *this;
279             }
280
281             value_ptr operator ->() const CDS_NOEXCEPT
282             {
283                 node_type * p = iterator_base::pointer();
284                 return p ? &p->m_Value : nullptr;
285             }
286
287             value_ref operator *() const CDS_NOEXCEPT
288             {
289                 node_type * p = iterator_base::pointer();
290                 assert( p );
291                 return p->m_Value;
292             }
293
294             void release()
295             {
296                 iterator_base::release();
297             }
298
299             template <bool IsConst2>
300             bool operator ==(reverse_bidirectional_iterator<IsConst2> const& rhs) const
301             {
302                 return iterator_base::operator==( rhs );
303             }
304
305             template <bool IsConst2>
306             bool operator !=(reverse_bidirectional_iterator<IsConst2> const& rhs)
307             {
308                 return !( *this == rhs );
309             }
310
311         public: // for internal use only!
312             reverse_bidirectional_iterator( base_class const& set, typename base_class::array_node * pNode, size_t idx, bool )
313                 : iterator_base( set, pNode, idx, false )
314             {}
315
316             reverse_bidirectional_iterator( base_class const& set, typename base_class::array_node * pNode, size_t idx )
317                 : iterator_base( set, pNode, idx, false )
318             {
319                 iterator_base::backward();
320             }
321         };
322
323         //@endcond
324
325     public:
326 #ifdef CDS_DOXYGEN_INVOKED
327         /// Guarded pointer
328         typedef typename gc::template guarded_ptr< value_type > guarded_ptr;
329 #else
330         typedef typename gc::template guarded_ptr< node_type, value_type, cds::container::details::guarded_ptr_cast_set<node_type, value_type> > guarded_ptr;
331 #endif
332
333 #ifdef CDS_DOXYGEN_INVOKED
334         typedef implementation_defined iterator;            ///< @ref cds_container_FeldmanHashMap_iterators "bidirectional iterator" type
335         typedef implementation_defined const_iterator;      ///< @ref cds_container_FeldmanHashMap_iterators "bidirectional const iterator" type
336         typedef implementation_defined reverse_iterator;    ///< @ref cds_container_FeldmanHashMap_iterators "bidirectional reverse iterator" type
337         typedef implementation_defined const_reverse_iterator; ///< @ref cds_container_FeldmanHashMap_iterators "bidirectional reverse const iterator" type
338 #else
339         typedef bidirectional_iterator<false> iterator;
340         typedef bidirectional_iterator<true>  const_iterator;
341         typedef reverse_bidirectional_iterator<false> reverse_iterator;
342         typedef reverse_bidirectional_iterator<true>  const_reverse_iterator;
343 #endif
344
345     protected:
346         //@cond
347         hasher  m_Hasher;
348         //@endcond
349
350     public:
351         /// Creates empty map
352         /**
353             @param head_bits: 2<sup>head_bits</sup> specifies the size of head array, minimum is 4.
354             @param array_bits: 2<sup>array_bits</sup> specifies the size of array node, minimum is 2.
355
356             Equation for \p head_bits and \p array_bits:
357             \code
358             sizeof(hash_type) * 8 == head_bits + N * array_bits
359             \endcode
360             where \p N is multi-level array depth.
361         */
362         FeldmanHashMap( size_t head_bits = 8, size_t array_bits = 4 )
363             : base_class( head_bits, array_bits )
364         {}
365
366         /// Destructs the map and frees all data
367         ~FeldmanHashMap()
368         {}
369
370         /// Inserts new element with key and default value
371         /**
372             The function creates an element with \p key and default value, and then inserts the node created into the map.
373
374             Preconditions:
375             - The \p key_type should be constructible from a value of type \p K.
376                 In trivial case, \p K is equal to \p key_type.
377             - The \p mapped_type should be default-constructible.
378
379             Returns \p true if inserting successful, \p false otherwise.
380         */
381         template <typename K>
382         bool insert( K&& key )
383         {
384             scoped_node_ptr sp( cxx_node_allocator().MoveNew( m_Hasher, std::forward<K>(key) ));
385             if ( base_class::insert( *sp )) {
386                 sp.release();
387                 return true;
388             }
389             return false;
390         }
391
392         /// Inserts new element
393         /**
394             The function creates a node with copy of \p val value
395             and then inserts the node created into the map.
396
397             Preconditions:
398             - The \p key_type should be constructible from \p key of type \p K.
399             - The \p value_type should be constructible from \p val of type \p V.
400
401             Returns \p true if \p val is inserted into the map, \p false otherwise.
402         */
403         template <typename K, typename V>
404         bool insert( K&& key, V&& val )
405         {
406             scoped_node_ptr sp( cxx_node_allocator().MoveNew( m_Hasher, std::forward<K>(key), std::forward<V>(val)));
407             if ( base_class::insert( *sp )) {
408                 sp.release();
409                 return true;
410             }
411             return false;
412         }
413
414         /// Inserts new element and initialize it by a functor
415         /**
416             This function inserts new element with key \p key and if inserting is successful then it calls
417             \p func functor with signature
418             \code
419                 struct functor {
420                     void operator()( value_type& item );
421                 };
422             \endcode
423
424             The argument \p item of user-defined functor \p func is the reference
425             to the map's item inserted:
426                 - <tt>item.first</tt> is a const reference to item's key that cannot be changed.
427                 - <tt>item.second</tt> is a reference to item's value that may be changed.
428
429             \p key_type should be constructible from value of type \p K.
430
431             The function allows to split creating of new item into two part:
432             - create item from \p key;
433             - insert new item into the map;
434             - if inserting is successful, initialize the value of item by calling \p func functor
435
436             This can be useful if complete initialization of object of \p value_type is heavyweight and
437             it is preferable that the initialization should be completed only if inserting is successful.
438         */
439         template <typename K, typename Func>
440         bool insert_with( K&& key, Func func )
441         {
442             scoped_node_ptr sp( cxx_node_allocator().MoveNew( m_Hasher, std::forward<K>(key)));
443             if ( base_class::insert( *sp, [&func]( node_type& item ) { func( item.m_Value ); } )) {
444                 sp.release();
445                 return true;
446             }
447             return false;
448         }
449
450         /// For key \p key inserts data of type \p value_type created in-place from <tt>std::forward<Args>(args)...</tt>
451         /**
452             Returns \p true if inserting successful, \p false otherwise.
453         */
454         template <typename K, typename... Args>
455         bool emplace( K&& key, Args&&... args )
456         {
457             scoped_node_ptr sp( cxx_node_allocator().MoveNew( m_Hasher, std::forward<K>(key), std::forward<Args>(args)... ));
458             if ( base_class::insert( *sp )) {
459                 sp.release();
460                 return true;
461             }
462             return false;
463         }
464
465         /// Updates data by \p key
466         /**
467             The operation performs inserting or replacing the element with lock-free manner.
468
469             If the \p key not found in the map, then the new item created from \p key
470             will be inserted into the map iff \p bInsert is \p true
471             (note that in this case the \ref key_type should be constructible from type \p K).
472             Otherwise, if \p key is found, it is replaced with a new item created from
473             \p key.
474             The functor \p Func signature:
475             \code
476                 struct my_functor {
477                     void operator()( value_type& item, value_type * old );
478                 };
479             \endcode
480             where:
481             - \p item - item of the map
482             - \p old - old item of the map, if \p nullptr - the new item was inserted
483
484             The functor may change any fields of the \p item.second.
485
486             Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successfull,
487             \p second is \p true if new item has been added or \p false if \p key already exists.
488
489             @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
490         */
491         template <typename K, typename Func>
492         std::pair<bool, bool> update( K&& key, Func func, bool bInsert = true )
493         {
494             scoped_node_ptr sp( cxx_node_allocator().MoveNew( m_Hasher, std::forward<K>(key)));
495             std::pair<bool, bool> result = base_class::do_update( *sp,
496                 [&func]( node_type& node, node_type * old ) { func( node.m_Value, old ? &old->m_Value : nullptr );},
497                 bInsert );
498             if ( result.first )
499                 sp.release();
500             return result;
501         }
502
503         /// Delete \p key from the map
504         /**
505             \p key_type must be constructible from value of type \p K.
506             The function deletes the element with hash value equal to <tt>hash( key_type( key ))</tt>
507
508             Return \p true if \p key is found and deleted, \p false otherwise.
509         */
510         template <typename K>
511         bool erase( K const& key )
512         {
513             return base_class::erase( m_Hasher( key_type( key )));
514         }
515
516         /// Delete \p key from the map
517         /**
518             The function searches an item with hash value equal to <tt>hash( key_type( key ))</tt>,
519             calls \p f functor and deletes the item. If \p key is not found, the functor is not called.
520
521             The functor \p Func interface:
522             \code
523             struct extractor {
524                 void operator()(value_type& item) { ... }
525             };
526             \endcode
527             where \p item is the element found.
528
529             \p key_type must be constructible from value of type \p K.
530
531             Return \p true if key is found and deleted, \p false otherwise
532         */
533         template <typename K, typename Func>
534         bool erase( K const& key, Func f )
535         {
536             return base_class::erase( m_Hasher(key_type(key)), [&f]( node_type& node) { f( node.m_Value ); } );
537         }
538
539         /// Deletes the element pointed by iterator \p iter
540         /**
541             Returns \p true if the operation is successful, \p false otherwise.
542
543             The function does not invalidate the iterator, it remains valid and can be used for further traversing.
544         */
545         bool erase_at( iterator const& iter )
546         {
547             return base_class::do_erase_at( iter );
548         }
549         //@cond
550         bool erase_at( reverse_iterator const& iter )
551         {
552             return base_class::do_erase_at( iter );
553         }
554         //@endcond
555
556         /// Extracts the item from the map with specified \p key
557         /**
558             The function searches an item with key equal to <tt>hash( key_type( key ))</tt> in the map,
559             unlinks it from the map, and returns a guarded pointer to the item found.
560             If \p key is not found the function returns an empty guarded pointer.
561
562             The item extracted is freed automatically by garbage collector \p GC
563             when returned \p guarded_ptr object will be destroyed or released.
564             @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
565
566             Usage:
567             \code
568             typedef cds::container::FeldmanHashMap< cds::gc::HP, int, foo, my_traits > map_type;
569             map_type theMap;
570             // ...
571             {
572                 map_type::guarded_ptr gp( theMap.extract( 5 ));
573                 if ( gp ) {
574                     // Deal with gp
575                     // ...
576                 }
577                 // Destructor of gp releases internal HP guard and frees the pointer
578             }
579             \endcode
580         */
581         template <typename K>
582         guarded_ptr extract( K const& key )
583         {
584             guarded_ptr gp;
585             typename gc::Guard guard;
586             node_type * p = base_class::do_erase( m_Hasher( key_type( key )), guard, []( node_type const&) -> bool {return true;} );
587
588             // p is guarded by HP
589             if ( p )
590                 gp.reset( p );
591             return gp;
592         }
593
594         /// Checks whether the map contains \p key
595         /**
596             The function searches the item by its hash that is equal to <tt>hash( key_type( key ))</tt>
597             and returns \p true if it is found, or \p false otherwise.
598         */
599         template <typename K>
600         bool contains( K const& key )
601         {
602             return base_class::contains( m_Hasher( key_type( key )) );
603         }
604
605         /// Find the key \p key
606         /**
607
608             The function searches the item by its hash that is equal to <tt>hash( key_type( key ))</tt>
609             and calls the functor \p f for item found.
610             The interface of \p Func functor is:
611             \code
612             struct functor {
613                 void operator()( value_type& item );
614             };
615             \endcode
616             where \p item is the item found.
617
618             The functor may change \p item.second.
619
620             The function returns \p true if \p key is found, \p false otherwise.
621         */
622         template <typename K, typename Func>
623         bool find( K const& key, Func f )
624         {
625             return base_class::find( m_Hasher( key_type( key )), [&f](node_type& node) { f( node.m_Value );});
626         }
627
628         /// Finds the key \p key and return the item found
629         /**
630             The function searches the item with a hash equal to <tt>hash( key_type( key ))</tt>
631             and returns a guarded pointer to the item found.
632             If \p key is not found the function returns an empty guarded pointer.
633
634             It is safe when a concurrent thread erases the item returned as \p guarded_ptr.
635             In this case the item will be freed later by garbage collector \p GC automatically
636             when \p guarded_ptr object will be destroyed or released.
637             @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
638
639             Usage:
640             \code
641             typedef cds::container::FeldmanHashMap< cds::gc::HP, int, foo, my_traits >  map_type;
642             map_type theMap;
643             // ...
644             {
645                 map_type::guarded_ptr gp( theMap.get( 5 ));
646                 if ( gp ) {
647                     // Deal with gp
648                     //...
649                 }
650                 // Destructor of guarded_ptr releases internal HP guard
651             }
652             \endcode
653         */
654         template <typename K>
655         guarded_ptr get( K const& key )
656         {
657             guarded_ptr gp;
658             {
659                 typename gc::Guard guard;
660                 gp.reset( base_class::search( m_Hasher( key_type( key )), guard ));
661             }
662             return gp;
663         }
664
665         /// Clears the map (non-atomic)
666         /**
667             The function unlink all data node from the map.
668             The function is not atomic but is thread-safe.
669             After \p %clear() the map may not be empty because another threads may insert items.
670         */
671         void clear()
672         {
673             base_class::clear();
674         }
675
676         /// Checks if the map is empty
677         /**
678             Emptiness is checked by item counting: if item count is zero then the map is empty.
679             Thus, the correct item counting feature is an important part of the map implementation.
680         */
681         bool empty() const
682         {
683             return base_class::empty();
684         }
685
686         /// Returns item count in the map
687         size_t size() const
688         {
689             return base_class::size();
690         }
691
692         /// Returns const reference to internal statistics
693         stat const& statistics() const
694         {
695             return base_class::statistics();
696         }
697
698         /// Returns the size of head node
699         size_t head_size() const
700         {
701             return base_class::head_size();
702         }
703
704         /// Returns the size of the array node
705         size_t array_node_size() const
706         {
707             return base_class::array_node_size();
708         }
709
710         /// Collects tree level statistics into \p stat
711         /**
712             The function traverses the set and collects statistics for each level of the tree
713             into \p feldman_hashset::level_statistics struct. The element of \p stat[i]
714             represents statistics for level \p i, level 0 is head array.
715             The function is thread-safe and may be called in multi-threaded environment.
716
717             Result can be useful for estimating efficiency of hash functor you use.
718         */
719         void get_level_statistics(std::vector< feldman_hashmap::level_statistics>& stat) const
720         {
721             base_class::get_level_statistics( stat );
722         }
723
724     public:
725     ///@name Thread-safe iterators
726         /** @anchor cds_container_FeldmanHashMap_iterators
727             The map supports thread-safe iterators: you may iterate over the map in multi-threaded environment.
728             It is guaranteed that the iterators will remain valid even if another thread deletes the node the iterator points to:
729             Hazard Pointer embedded into the iterator object protects the node from physical reclamation.
730
731             @note Since the iterator object contains hazard pointer that is a thread-local resource,
732             the iterator should not be passed to another thread.
733
734             Each iterator object supports the common interface:
735             - dereference operators:
736                 @code
737                 value_type [const] * operator ->() noexcept
738                 value_type [const] & operator *() noexcept
739                 @endcode
740             - pre-increment and pre-decrement. Post-operators is not supported
741             - equality operators <tt>==</tt> and <tt>!=</tt>.
742                 Iterators are equal iff they point to the same cell of the same array node.
743                 Note that for two iterators \p it1 and \p it2, the conditon <tt> it1 == it2 </tt>
744                 does not entail <tt> &(*it1) == &(*it2) </tt>
745             - helper member function \p release() that clears internal hazard pointer.
746                 After \p release() the iterator points to \p nullptr but it still remain valid: further iterating is possible.
747
748             During iteration you may safely erase any item from the set;
749             @ref erase_at() function call doesn't invalidate any iterator.
750             If some iterator points to the item to be erased, that item is not deleted immediately
751             but only after that iterator will be advanced forward or backward.
752
753             @note It is possible the item can be iterated more that once, for example, if an iterator points to the item
754             in array node that is being splitted.
755         */
756     ///@{
757         /// Returns an iterator to the beginning of the map
758         iterator begin()
759         {
760             return base_class::template init_begin<iterator>();
761         }
762
763         /// Returns an const iterator to the beginning of the map
764         const_iterator begin() const
765         {
766             return base_class::template init_begin<const_iterator>();
767         }
768
769         /// Returns an const iterator to the beginning of the map
770         const_iterator cbegin()
771         {
772             return base_class::template init_begin<const_iterator>();
773         }
774
775         /// 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.
776         iterator end()
777         {
778             return base_class::template init_end<iterator>();
779         }
780
781         /// 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.
782         const_iterator end() const
783         {
784             return base_class::template init_end<const_iterator>();
785         }
786
787         /// 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.
788         const_iterator cend()
789         {
790             return base_class::template init_end<const_iterator>();
791         }
792
793         /// Returns a reverse iterator to the first element of the reversed map
794         reverse_iterator rbegin()
795         {
796             return base_class::template init_rbegin<reverse_iterator>();
797         }
798
799         /// Returns a const reverse iterator to the first element of the reversed map
800         const_reverse_iterator rbegin() const
801         {
802             return base_class::template init_rbegin<const_reverse_iterator>();
803         }
804
805         /// Returns a const reverse iterator to the first element of the reversed map
806         const_reverse_iterator crbegin()
807         {
808             return base_class::template init_rbegin<const_reverse_iterator>();
809         }
810
811         /// Returns a reverse iterator to the element following the last element of the reversed map
812         /**
813             It corresponds to the element preceding the first element of the non-reversed container.
814             This element acts as a placeholder, attempting to access it results in undefined behavior.
815         */
816         reverse_iterator rend()
817         {
818             return base_class::template init_rend<reverse_iterator>();
819         }
820
821         /// Returns a const reverse iterator to the element following the last element of the reversed map
822         /**
823             It corresponds to the element preceding the first element of the non-reversed container.
824             This element acts as a placeholder, attempting to access it results in undefined behavior.
825         */
826         const_reverse_iterator rend() const
827         {
828             return base_class::template init_rend<const_reverse_iterator>();
829         }
830
831         /// Returns a const reverse iterator to the element following the last element of the reversed map
832         /**
833             It corresponds to the element preceding the first element of the non-reversed container.
834             This element acts as a placeholder, attempting to access it results in undefined behavior.
835         */
836         const_reverse_iterator crend()
837         {
838             return base_class::template init_rend<const_reverse_iterator>();
839         }
840     ///@}
841     };
842
843 }} // namespace cds::container
844
845 #endif // #ifndef CDSLIB_CONTAINER_IMPL_FELDMAN_HASHMAP_H