cds/container/feldman_hashmap_rcu.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-2017
   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_FELDMAN_HASHMAP_RCU_H
  32 #define CDSLIB_CONTAINER_FELDMAN_HASHMAP_RCU_H
  33
  34 #include <cds/intrusive/feldman_hashset_rcu.h>
  35 #include <cds/container/details/feldman_hashmap_base.h>
  36
  37 namespace cds { namespace container {
  38
  39     /// Hash map based on multi-level array
  40     /** @ingroup cds_nonintrusive_map
  41         @anchor cds_container_FeldmanHashMap_rcu
  42
  43         Source:
  44         - [2013] Steven Feldman, Pierre LaBorde, Damian Dechev "Concurrent Multi-level Arrays:
  45                  Wait-free Extensible Hash Maps"
  46
  47         See algorithm short description @ref cds_container_FeldmanHashMap_hp "here"
  48
  49         @note Two important things you should keep in mind when you're using \p %FeldmanHashMap:
  50         - all keys is converted to fixed-size bit-string by hash functor provided.
  51           You can use variable-length keys, for example, \p std::string as a key for \p %FeldmanHashMap,
  52           but real key in the map will be fixed-size hash values of your keys.
  53           For the strings you may use well-known hashing algorithms like <a href="https://en.wikipedia.org/wiki/Secure_Hash_Algorithm">SHA1, SHA2</a>,
  54           <a href="https://en.wikipedia.org/wiki/MurmurHash">MurmurHash</a>, <a href="https://en.wikipedia.org/wiki/CityHash">CityHash</a>
  55           or its successor <a href="https://code.google.com/p/farmhash/">FarmHash</a> and so on, which
  56           converts variable-length strings to fixed-length bit-strings, and such hash values will be the keys in \p %FeldmanHashMap.
  57           If your key is fixed-sized the hash functor is optional, see \p feldman_hashmap::traits::hash for explanation and examples.
  58         - \p %FeldmanHashMap uses a perfect hashing. It means that if two different keys, for example, of type \p std::string,
  59           have identical hash then you cannot insert both that keys in the map. \p %FeldmanHashMap does not maintain the key,
  60           it maintains its fixed-size hash value.
  61
  62         The map supports @ref cds_container_FeldmanHashMap_rcu_iterators "bidirectional thread-safe iterators".
  63
  64         Template parameters:
  65         - \p RCU - one of \ref cds_urcu_gc "RCU type"
  66         - \p Key - a key type to be stored in the map
  67         - \p T - a value type to be stored in the map
  68         - \p Traits - type traits, the structure based on \p feldman_hashmap::traits or result of \p feldman_hashmap::make_traits metafunction.
  69
  70         @note Before including <tt><cds/intrusive/feldman_hashset_rcu.h></tt> you should include appropriate RCU header file,
  71         see \ref cds_urcu_gc "RCU type" for list of existing RCU class and corresponding header files.
  72     */
  73     template <
  74         class RCU
  75         ,typename Key
  76         ,typename T
  77 #ifdef CDS_DOXYGEN_INVOKED
  78         ,class Traits = feldman_hashmap::traits
  79 #else
  80         ,class Traits
  81 #endif
  82     >
  83     class FeldmanHashMap< cds::urcu::gc< RCU >, Key, T, Traits >
  84 #ifdef CDS_DOXYGEN_INVOKED
  85         : protected cds::intrusive::FeldmanHashSet< cds::urcu::gc< RCU >, std::pair<Key const, T>, Traits >
  86 #else
  87         : protected cds::container::details::make_feldman_hashmap< cds::urcu::gc< RCU >, Key, T, Traits >::type
  88 #endif
  89     {
  90         //@cond
  91         typedef cds::container::details::make_feldman_hashmap< cds::urcu::gc< RCU >, Key, T, Traits > maker;
  92         typedef typename maker::type base_class;
  93         //@endcond
  94     public:
  95         typedef cds::urcu::gc< RCU > gc; ///< RCU garbage collector
  96         typedef Key     key_type;    ///< Key type
  97         typedef T       mapped_type; ///< Mapped type
  98         typedef std::pair< key_type const, mapped_type> value_type;   ///< Key-value pair to be stored in the map
  99         typedef Traits  traits;      ///< Map traits
 100 #ifdef CDS_DOXYGEN_INVOKED
 101         typedef typename traits::hash hasher; ///< Hash functor, see \p feldman_hashmap::traits::hash
 102 #else
 103         typedef typename maker::hasher hasher;
 104 #endif
 105
 106         typedef typename maker::hash_type hash_type; ///< Hash type deduced from \p hasher return type
 107         typedef typename base_class::hash_comparator hash_comparator; ///< hash compare functor based on \p Traits::compare and \p Traits::less
 108         typedef typename traits::item_counter   item_counter;   ///< Item counter type
 109         typedef typename traits::allocator      allocator;      ///< Element allocator
 110         typedef typename traits::node_allocator node_allocator; ///< Array node allocator
 111         typedef typename traits::memory_model   memory_model;   ///< Memory model
 112         typedef typename traits::back_off       back_off;       ///< Back-off strategy
 113         typedef typename traits::stat           stat;           ///< Internal statistics type
 114         typedef typename traits::rcu_check_deadlock rcu_check_deadlock; ///< Deadlock checking policy
 115         typedef typename gc::scoped_lock       rcu_lock;        ///< RCU scoped lock
 116         static CDS_CONSTEXPR const bool c_bExtractLockExternal = false; ///< Group of \p extract_xxx functions does not require external locking
 117
 118         /// Level statistics
 119         typedef feldman_hashmap::level_statistics level_statistics;
 120
 121     protected:
 122         //@cond
 123         typedef typename maker::node_type node_type;
 124         typedef typename maker::cxx_node_allocator cxx_node_allocator;
 125         typedef std::unique_ptr< node_type, typename maker::node_disposer > scoped_node_ptr;
 126         typedef typename base_class::check_deadlock_policy check_deadlock_policy;
 127
 128         struct node_cast
 129         {
 130             value_type * operator()(node_type * p) const
 131             {
 132                 return p ? &p->m_Value : nullptr;
 133             }
 134         };
 135
 136     public:
 137         /// pointer to extracted node
 138         using exempt_ptr = cds::urcu::exempt_ptr< gc, node_type, value_type, typename base_class::disposer, node_cast >;
 139
 140     protected:
 141         template <bool IsConst>
 142         class bidirectional_iterator: public base_class::iterator_base
 143         {
 144             friend class FeldmanHashMap;
 145             typedef typename base_class::iterator_base iterator_base;
 146
 147         protected:
 148             static CDS_CONSTEXPR bool const c_bConstantIterator = IsConst;
 149
 150         public:
 151             typedef typename std::conditional< IsConst, value_type const*, value_type*>::type value_ptr; ///< Value pointer
 152             typedef typename std::conditional< IsConst, value_type const&, value_type&>::type value_ref; ///< Value reference
 153
 154         public:
 155             bidirectional_iterator() CDS_NOEXCEPT
 156             {}
 157
 158             bidirectional_iterator( bidirectional_iterator const& rhs ) CDS_NOEXCEPT
 159                 : iterator_base( rhs )
 160             {}
 161
 162             bidirectional_iterator& operator=(bidirectional_iterator const& rhs) CDS_NOEXCEPT
 163             {
 164                 iterator_base::operator=( rhs );
 165                 return *this;
 166             }
 167
 168             bidirectional_iterator& operator++()
 169             {
 170                 iterator_base::operator++();
 171                 return *this;
 172             }
 173
 174             bidirectional_iterator& operator--()
 175             {
 176                 iterator_base::operator--();
 177                 return *this;
 178             }
 179
 180             value_ptr operator ->() const CDS_NOEXCEPT
 181             {
 182                 node_type * p = iterator_base::pointer();
 183                 return p ? &p->m_Value : nullptr;
 184             }
 185
 186             value_ref operator *() const CDS_NOEXCEPT
 187             {
 188                 node_type * p = iterator_base::pointer();
 189                 assert( p );
 190                 return p->m_Value;
 191             }
 192
 193             void release()
 194             {
 195                 iterator_base::release();
 196             }
 197
 198             template <bool IsConst2>
 199             bool operator ==(bidirectional_iterator<IsConst2> const& rhs) const CDS_NOEXCEPT
 200             {
 201                 return iterator_base::operator==( rhs );
 202             }
 203
 204             template <bool IsConst2>
 205             bool operator !=(bidirectional_iterator<IsConst2> const& rhs) const CDS_NOEXCEPT
 206             {
 207                 return !( *this == rhs );
 208             }
 209
 210         public: // for internal use only!
 211             bidirectional_iterator( base_class const& set, typename base_class::array_node * pNode, size_t idx, bool )
 212                 : iterator_base( set, pNode, idx, false )
 213             {}
 214
 215             bidirectional_iterator( base_class const& set, typename base_class::array_node * pNode, size_t idx )
 216                 : iterator_base( set, pNode, idx )
 217             {}
 218         };
 219
 220         /// Reverse bidirectional iterator
 221         template <bool IsConst>
 222         class reverse_bidirectional_iterator : public base_class::iterator_base
 223         {
 224             friend class FeldmanHashMap;
 225             typedef typename base_class::iterator_base iterator_base;
 226
 227         public:
 228             typedef typename std::conditional< IsConst, value_type const*, value_type*>::type value_ptr; ///< Value pointer
 229             typedef typename std::conditional< IsConst, value_type const&, value_type&>::type value_ref; ///< Value reference
 230
 231         public:
 232             reverse_bidirectional_iterator() CDS_NOEXCEPT
 233                 : iterator_base()
 234             {}
 235
 236             reverse_bidirectional_iterator( reverse_bidirectional_iterator const& rhs ) CDS_NOEXCEPT
 237                 : iterator_base( rhs )
 238             {}
 239
 240             reverse_bidirectional_iterator& operator=( reverse_bidirectional_iterator const& rhs) CDS_NOEXCEPT
 241             {
 242                 iterator_base::operator=( rhs );
 243                 return *this;
 244             }
 245
 246             reverse_bidirectional_iterator& operator++()
 247             {
 248                 iterator_base::operator--();
 249                 return *this;
 250             }
 251
 252             reverse_bidirectional_iterator& operator--()
 253             {
 254                 iterator_base::operator++();
 255                 return *this;
 256             }
 257
 258             value_ptr operator ->() const CDS_NOEXCEPT
 259             {
 260                 node_type * p = iterator_base::pointer();
 261                 return p ? &p->m_Value : nullptr;
 262             }
 263
 264             value_ref operator *() const CDS_NOEXCEPT
 265             {
 266                 node_type * p = iterator_base::pointer();
 267                 assert( p );
 268                 return p->m_Value;
 269             }
 270
 271             void release()
 272             {
 273                 iterator_base::release();
 274             }
 275
 276             template <bool IsConst2>
 277             bool operator ==(reverse_bidirectional_iterator<IsConst2> const& rhs) const
 278             {
 279                 return iterator_base::operator==( rhs );
 280             }
 281
 282             template <bool IsConst2>
 283             bool operator !=(reverse_bidirectional_iterator<IsConst2> const& rhs)
 284             {
 285                 return !( *this == rhs );
 286             }
 287
 288         public: // for internal use only!
 289             reverse_bidirectional_iterator( base_class const& set, typename base_class::array_node * pNode, size_t idx, bool )
 290                 : iterator_base( set, pNode, idx, false )
 291             {}
 292
 293             reverse_bidirectional_iterator( base_class const& set, typename base_class::array_node * pNode, size_t idx )
 294                 : iterator_base( set, pNode, idx, false )
 295             {
 296                 iterator_base::backward();
 297             }
 298         };
 299         //@endcond
 300
 301     public:
 302 #ifdef CDS_DOXYGEN_INVOKED
 303         typedef implementation_defined iterator;            ///< @ref cds_container_FeldmanHashMap_rcu_iterators "bidirectional iterator" type
 304         typedef implementation_defined const_iterator;      ///< @ref cds_container_FeldmanHashMap_rcu_iterators "bidirectional const iterator" type
 305         typedef implementation_defined reverse_iterator;    ///< @ref cds_container_FeldmanHashMap_rcu_iterators "bidirectional reverse iterator" type
 306         typedef implementation_defined const_reverse_iterator; ///< @ref cds_container_FeldmanHashMap_rcu_iterators "bidirectional reverse const iterator" type
 307 #else
 308         typedef bidirectional_iterator<false> iterator;
 309         typedef bidirectional_iterator<true>  const_iterator;
 310         typedef reverse_bidirectional_iterator<false> reverse_iterator;
 311         typedef reverse_bidirectional_iterator<true>  const_reverse_iterator;
 312 #endif
 313
 314     protected:
 315         //@cond
 316         hasher  m_Hasher;
 317         //@endcond
 318
 319     public:
 320         /// Creates empty map
 321         /**
 322             @param head_bits - 2<sup>head_bits</sup> specifies the size of head array, minimum is 4.
 323             @param array_bits - 2<sup>array_bits</sup> specifies the size of array node, minimum is 2.
 324
 325             Equation for \p head_bits and \p array_bits:
 326             \code
 327             sizeof(hash_type) * 8 == head_bits + N * array_bits
 328             \endcode
 329             where \p N is multi-level array depth.
 330         */
 331         FeldmanHashMap( size_t head_bits = 8, size_t array_bits = 4 )
 332             : base_class( head_bits, array_bits )
 333         {}
 334
 335         /// Destructs the map and frees all data
 336         ~FeldmanHashMap()
 337         {}
 338
 339         /// Inserts new element with key and default value
 340         /**
 341             The function creates an element with \p key and default value, and then inserts the node created into the map.
 342
 343             Preconditions:
 344             - The \p key_type should be constructible from a value of type \p K.
 345                 In trivial case, \p K is equal to \p key_type.
 346             - The \p mapped_type should be default-constructible.
 347
 348             Returns \p true if inserting successful, \p false otherwise.
 349
 350             The function locks RCU internally.
 351         */
 352         template <typename K>
 353         bool insert( K&& key )
 354         {
 355             scoped_node_ptr sp( cxx_node_allocator().MoveNew( m_Hasher, std::forward<K>(key)));
 356             if ( base_class::insert( *sp )) {
 357                 sp.release();
 358                 return true;
 359             }
 360             return false;
 361         }
 362
 363         /// Inserts new element
 364         /**
 365             The function creates a node with copy of \p val value
 366             and then inserts the node created into the map.
 367
 368             Preconditions:
 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.
 371
 372             Returns \p true if \p val is inserted into the map, \p false otherwise.
 373
 374             The function locks RCU internally.
 375         */
 376         template <typename K, typename V>
 377         bool insert( K&& key, V&& val )
 378         {
 379             scoped_node_ptr sp( cxx_node_allocator().MoveNew( m_Hasher, std::forward<K>(key), std::forward<V>(val)));
 380             if ( base_class::insert( *sp )) {
 381                 sp.release();
 382                 return true;
 383             }
 384             return false;
 385         }
 386
 387         /// Inserts new element and initialize it by a functor
 388         /**
 389             This function inserts new element with key \p key and if inserting is successful then it calls
 390             \p func functor with signature
 391             \code
 392                 struct functor {
 393                     void operator()( value_type& item );
 394                 };
 395             \endcode
 396
 397             The argument \p item of user-defined functor \p func is the reference
 398             to the map's item inserted:
 399                 - <tt>item.first</tt> is a const reference to item's key that cannot be changed.
 400                 - <tt>item.second</tt> is a reference to item's value that may be changed.
 401
 402             \p key_type should be constructible from value of type \p K.
 403
 404             The function allows to split creating of new item into two part:
 405             - create item from \p key;
 406             - insert new item into the map;
 407             - if inserting is successful, initialize the value of item by calling \p func functor
 408
 409             This can be useful if complete initialization of object of \p value_type is heavyweight and
 410             it is preferable that the initialization should be completed only if inserting is successful.
 411
 412             The function locks RCU internally.
 413         */
 414         template <typename K, typename Func>
 415         bool insert_with( K&& key, Func func )
 416         {
 417             scoped_node_ptr sp( cxx_node_allocator().MoveNew( m_Hasher, std::forward<K>(key)));
 418             if ( base_class::insert( *sp, [&func]( node_type& item ) { func( item.m_Value ); } )) {
 419                 sp.release();
 420                 return true;
 421             }
 422             return false;
 423         }
 424
 425         /// For key \p key inserts data of type \p value_type created in-place from <tt>std::forward<Args>(args)...</tt>
 426         /**
 427             Returns \p true if inserting successful, \p false otherwise.
 428
 429             The function locks RCU internally.
 430         */
 431         template <typename K, typename... Args>
 432         bool emplace( K&& key, Args&&... args )
 433         {
 434             scoped_node_ptr sp( cxx_node_allocator().MoveNew( m_Hasher, std::forward<K>(key), std::forward<Args>(args)... ));
 435             if ( base_class::insert( *sp )) {
 436                 sp.release();
 437                 return true;
 438             }
 439             return false;
 440         }
 441
 442         /// Updates data by \p key
 443         /**
 444             The operation performs inserting or replacing the element with lock-free manner.
 445
 446             If the \p key not found in the map, then the new item created from \p key
 447             will be inserted into the map iff \p bInsert is \p true
 448             (note that in this case the \ref key_type should be constructible from type \p K).
 449             Otherwise, if \p key is found, it is replaced with a new item created from
 450             \p key.
 451             The functor \p Func signature:
 452             \code
 453                 struct my_functor {
 454                     void operator()( value_type& item, value_type * old );
 455                 };
 456             \endcode
 457             where:
 458             - \p item - item of the map
 459             - \p old - old item of the map, if \p nullptr - the new item was inserted
 460
 461             The functor may change any fields of the \p item.second.
 462
 463             Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successful,
 464             \p second is \p true if new item has been added or \p false if \p key already exists.
 465
 466             The function locks RCU internally.
 467
 468             @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
 469         */
 470         template <typename K, typename Func>
 471         std::pair<bool, bool> update( K&& key, Func func, bool bInsert = true )
 472         {
 473             scoped_node_ptr sp( cxx_node_allocator().MoveNew( m_Hasher, std::forward<K>(key)));
 474             std::pair<bool, bool> result = base_class::do_update( *sp,
 475                 [&func]( node_type& node, node_type * old ) { func( node.m_Value, old ? &old->m_Value : nullptr );},
 476                 bInsert );
 477             if ( result.first )
 478                 sp.release();
 479             return result;
 480         }
 481
 482         /// Delete \p key from the map
 483         /**
 484             \p key_type must be constructible from value of type \p K.
 485             The function deletes the element with hash value equal to <tt>hash( key_type( key ))</tt>
 486
 487             Return \p true if \p key is found and deleted, \p false otherwise.
 488
 489             RCU should not be locked. The function locks RCU internally.
 490         */
 491         template <typename K>
 492         bool erase( K const& key )
 493         {
 494             return base_class::erase(m_Hasher(key_type(key)));
 495         }
 496
 497         /// Delete \p key from the map
 498         /**
 499             The function searches an item with hash value equal to <tt>hash( key_type( key ))</tt>,
 500             calls \p f functor and deletes the item. If \p key is not found, the functor is not called.
 501
 502             The functor \p Func interface:
 503             \code
 504             struct extractor {
 505                 void operator()(value_type& item) { ... }
 506             };
 507             \endcode
 508             where \p item is the element found.
 509
 510             \p key_type must be constructible from value of type \p K.
 511
 512             Return \p true if key is found and deleted, \p false otherwise
 513
 514             RCU should not be locked. The function locks RCU internally.
 515         */
 516         template <typename K, typename Func>
 517         bool erase( K const& key, Func f )
 518         {
 519             return base_class::erase(m_Hasher(key_type(key)), [&f]( node_type& node) { f( node.m_Value ); });
 520         }
 521
 522         /// Extracts the item from the map with specified \p key
 523         /**
 524             The function searches an item with key equal to <tt>hash( key_type( key ))</tt> in the map,
 525             unlinks it from the map, and returns a guarded pointer to the item found.
 526             If \p key is not found the function returns an empty guarded pointer.
 527
 528             RCU \p synchronize method can be called. RCU should NOT be locked.
 529             The function does not call the disposer for the item found.
 530             The disposer will be implicitly invoked when the returned object is destroyed or when
 531             its \p release() member function is called.
 532             Example:
 533             \code
 534             typedef cds::container::FeldmanHashMap< cds::urcu::gc< cds::urcu::general_buffered<>>, int, foo, my_traits > map_type;
 535             map_type theMap;
 536             // ...
 537
 538             typename map_type::exempt_ptr ep( theMap.extract( 5 ));
 539             if ( ep ) {
 540                 // Deal with ep
 541                 //...
 542
 543                 // Dispose returned item.
 544                 ep.release();
 545             }
 546             \endcode
 547         */
 548         template <typename K>
 549         exempt_ptr extract( K const& key )
 550         {
 551             check_deadlock_policy::check();
 552
 553             node_type * p;
 554             {
 555                 rcu_lock rcuLock;
 556                 p = base_class::do_erase( m_Hasher( key_type(key)), [](node_type const&) -> bool {return true;});
 557             }
 558             return exempt_ptr(p);
 559         }
 560
 561         /// Checks whether the map contains \p key
 562         /**
 563             The function searches the item by its hash that is equal to <tt>hash( key_type( key ))</tt>
 564             and returns \p true if it is found, or \p false otherwise.
 565         */
 566         template <typename K>
 567         bool contains( K const& key )
 568         {
 569             return base_class::contains( m_Hasher( key_type( key )));
 570         }
 571
 572         /// Find the key \p key
 573         /**
 574
 575             The function searches the item by its hash that is equal to <tt>hash( key_type( key ))</tt>
 576             and calls the functor \p f for item found.
 577             The interface of \p Func functor is:
 578             \code
 579             struct functor {
 580                 void operator()( value_type& item );
 581             };
 582             \endcode
 583             where \p item is the item found.
 584
 585             The functor may change \p item.second.
 586
 587             The function returns \p true if \p key is found, \p false otherwise.
 588         */
 589         template <typename K, typename Func>
 590         bool find( K const& key, Func f )
 591         {
 592             return base_class::find( m_Hasher( key_type( key )), [&f](node_type& node) { f( node.m_Value );});
 593         }
 594
 595         /// Finds the key \p key and return the item found
 596         /**
 597             The function searches the item by its \p hash
 598             and returns the pointer to the item found.
 599             If \p hash is not found the function returns \p nullptr.
 600
 601             RCU should be locked before the function invocation.
 602             Returned pointer is valid only while RCU is locked.
 603
 604             Usage:
 605             \code
 606             typedef cds::container::FeldmanHashMap< your_template_params >  my_map;
 607             my_map theMap;
 608             // ...
 609             {
 610                 // lock RCU
 611                 my_map::rcu_lock;
 612
 613                 foo * p = theMap.get( 5 );
 614                 if ( p ) {
 615                     // Deal with p
 616                     //...
 617                 }
 618             }
 619             \endcode
 620         */
 621         template <typename K>
 622         value_type * get( K const& key )
 623         {
 624             node_type * p = base_class::get( m_Hasher( key_type( key )));
 625             return p ? &p->m_Value : nullptr;
 626         }
 627
 628         /// Clears the map (non-atomic)
 629         /**
 630             The function unlink all data node from the map.
 631             The function is not atomic but is thread-safe.
 632             After \p %clear() the map may not be empty because another threads may insert items.
 633         */
 634         void clear()
 635         {
 636             base_class::clear();
 637         }
 638
 639         /// Checks if the map is empty
 640         /**
 641             Emptiness is checked by item counting: if item count is zero then the map is empty.
 642             Thus, the correct item counting feature is an important part of the map implementation.
 643         */
 644         bool empty() const
 645         {
 646             return base_class::empty();
 647         }
 648
 649         /// Returns item count in the map
 650         size_t size() const
 651         {
 652             return base_class::size();
 653         }
 654
 655         /// Returns const reference to internal statistics
 656         stat const& statistics() const
 657         {
 658             return base_class::statistics();
 659         }
 660
 661         /// Returns the size of head node
 662         size_t head_size() const
 663         {
 664             return base_class::head_size();
 665         }
 666
 667         /// Returns the size of the array node
 668         size_t array_node_size() const
 669         {
 670             return base_class::array_node_size();
 671         }
 672
 673         /// Collects tree level statistics into \p stat
 674         /**
 675             The function traverses the set and collects statistics for each level of the tree
 676             into \p feldman_hashset::level_statistics struct. The element of \p stat[i]
 677             represents statistics for level \p i, level 0 is head array.
 678             The function is thread-safe and may be called in multi-threaded environment.
 679
 680             Result can be useful for estimating efficiency of hash functor you use.
 681         */
 682         void get_level_statistics(std::vector< feldman_hashmap::level_statistics>& stat) const
 683         {
 684             base_class::get_level_statistics(stat);
 685         }
 686
 687     public:
 688     ///@name Thread-safe iterators
 689         /** @anchor cds_container_FeldmanHashMap_rcu_iterators
 690             The map supports thread-safe iterators: you may iterate over the map in multi-threaded environment
 691             under explicit RCU lock.
 692             RCU lock requirement means that inserting or searching is allowed but you must not erase the items from the map
 693             since erasing under RCU lock can lead to a deadlock. However, another thread can call \p erase() safely
 694             while your thread is iterating.
 695
 696             A typical example is:
 697             \code
 698             struct foo {
 699                 // ... other fields
 700                 uint32_t    payload; // only for example
 701             };
 702             typedef cds::urcu::gc< cds::urcu::general_buffered<>> rcu;
 703             typedef cds::container::FeldmanHashMap< rcu, std::string, foo> map_type;
 704
 705             map_type m;
 706
 707             // ...
 708
 709             // iterate over the map
 710             {
 711                 // lock the RCU.
 712                 typename set_type::rcu_lock l; // scoped RCU lock
 713
 714                 // traverse the map
 715                 for ( auto i = m.begin(); i != s.end(); ++i ) {
 716                     // deal with i. Remember, erasing is prohibited here!
 717                     i->second.payload++;
 718                 }
 719             } // at this point RCU lock is released
 720             \endcode
 721
 722             Each iterator object supports the common interface:
 723             - dereference operators:
 724                 @code
 725                 value_type [const] * operator ->() noexcept
 726                 value_type [const] & operator *() noexcept
 727                 @endcode
 728             - pre-increment and pre-decrement. Post-operators is not supported
 729             - equality operators <tt>==</tt> and <tt>!=</tt>.
 730                 Iterators are equal iff they point to the same cell of the same array node.
 731                 Note that for two iterators \p it1 and \p it2 the condition <tt> it1 == it2 </tt>
 732                 does not entail <tt> &(*it1) == &(*it2) </tt>: welcome to concurrent containers
 733
 734             @note It is possible the item can be iterated more that once, for example, if an iterator points to the item
 735             in an array node that is being splitted.
 736         */
 737     ///@{
 738         /// Returns an iterator to the beginning of the map
 739         iterator begin()
 740         {
 741             return base_class::template init_begin<iterator>();
 742         }
 743
 744         /// Returns an const iterator to the beginning of the map
 745         const_iterator begin() const
 746         {
 747             return base_class::template init_begin<const_iterator>();
 748         }
 749
 750         /// Returns an const iterator to the beginning of the map
 751         const_iterator cbegin()
 752         {
 753             return base_class::template init_begin<const_iterator>();
 754         }
 755
 756         /// 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.
 757         iterator end()
 758         {
 759             return base_class::template init_end<iterator>();
 760         }
 761
 762         /// 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.
 763         const_iterator end() const
 764         {
 765             return base_class::template init_end<const_iterator>();
 766         }
 767
 768         /// 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.
 769         const_iterator cend()
 770         {
 771             return base_class::template init_end<const_iterator>();
 772         }
 773
 774         /// Returns a reverse iterator to the first element of the reversed map
 775         reverse_iterator rbegin()
 776         {
 777             return base_class::template init_rbegin<reverse_iterator>();
 778         }
 779
 780         /// Returns a const reverse iterator to the first element of the reversed map
 781         const_reverse_iterator rbegin() const
 782         {
 783             return base_class::template init_rbegin<const_reverse_iterator>();
 784         }
 785
 786         /// Returns a const reverse iterator to the first element of the reversed map
 787         const_reverse_iterator crbegin()
 788         {
 789             return base_class::template init_rbegin<const_reverse_iterator>();
 790         }
 791
 792         /// Returns a reverse iterator to the element following the last element of the reversed map
 793         /**
 794             It corresponds to the element preceding the first element of the non-reversed container.
 795             This element acts as a placeholder, attempting to access it results in undefined behavior.
 796         */
 797         reverse_iterator rend()
 798         {
 799             return base_class::template init_rend<reverse_iterator>();
 800         }
 801
 802         /// Returns a const reverse iterator to the element following the last element of the reversed map
 803         /**
 804             It corresponds to the element preceding the first element of the non-reversed container.
 805             This element acts as a placeholder, attempting to access it results in undefined behavior.
 806         */
 807         const_reverse_iterator rend() const
 808         {
 809             return base_class::template init_rend<const_reverse_iterator>();
 810         }
 811
 812         /// Returns a const reverse iterator to the element following the last element of the reversed map
 813         /**
 814             It corresponds to the element preceding the first element of the non-reversed container.
 815             This element acts as a placeholder, attempting to access it results in undefined behavior.
 816         */
 817         const_reverse_iterator crend()
 818         {
 819             return base_class::template init_rend<const_reverse_iterator>();
 820         }
 821     ///@}
 822     };
 823 }} // namespace cds::container
 824
 825 #endif // #ifndef CDSLIB_CONTAINER_FELDMAN_HASHMAP_RCU_H