cds/intrusive/impl/feldman_hashset.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_INTRUSIVE_IMPL_FELDMAN_HASHSET_H
  32 #define CDSLIB_INTRUSIVE_IMPL_FELDMAN_HASHSET_H
  33
  34 #include <functional>   // std::ref
  35 #include <iterator>     // std::iterator_traits
  36 #include <vector>
  37
  38 #include <cds/intrusive/details/feldman_hashset_base.h>
  39 #include <cds/details/allocator.h>
  40
  41 namespace cds { namespace intrusive {
  42     /// Intrusive hash set based on multi-level array
  43     /** @ingroup cds_intrusive_map
  44         @anchor cds_intrusive_FeldmanHashSet_hp
  45
  46         Source:
  47         - [2013] Steven Feldman, Pierre LaBorde, Damian Dechev "Concurrent Multi-level Arrays:
  48                  Wait-free Extensible Hash Maps"
  49
  50         [From the paper] The hardest problem encountered while developing a parallel hash map is how to perform
  51         a global resize, the process of redistributing the elements in a hash map that occurs when adding new
  52         buckets. The negative impact of blocking synchronization is multiplied during a global resize, because all
  53         threads will be forced to wait on the thread that is performing the involved process of resizing the hash map
  54         and redistributing the elements. \p %FeldmanHashSet implementation avoids global resizes through new array
  55         allocation. By allowing concurrent expansion this structure is free from the overhead of an explicit resize,
  56         which facilitates concurrent operations.
  57
  58         The presented design includes dynamic hashing, the use of sub-arrays within the hash map data structure;
  59         which, in combination with <b>perfect hashing</b>, means that each element has a unique final, as well as current, position.
  60         It is important to note that the perfect hash function required by our hash map is trivial to realize as
  61         any hash function that permutes the bits of the key is suitable. This is possible because of our approach
  62         to the hash function; we require that it produces hash values that are equal in size to that of the key.
  63         We know that if we expand the hash map a fixed number of times there can be no collision as duplicate keys
  64         are not provided for in the standard semantics of a hash map.
  65
  66         \p %FeldmanHashSet is a multi-level array which has a structure similar to a tree:
  67         @image html feldman_hashset.png
  68         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.
  69         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
  70         with that key; it is a simple struct holding two variables. A \p dataNode in the multi-level array could be marked.
  71         A \p markedDataNode refers to a pointer to a \p dataNode that has been bitmarked at the least significant bit (LSB)
  72         of the pointer to the node. This signifies that this \p dataNode is contended. An expansion must occur at this node;
  73         any thread that sees this \p markedDataNode will try to replace it with an \p arrayNode; which is a position that holds
  74         an array of nodes. The pointer to an \p arrayNode is differentiated from that of a pointer to a \p dataNode by a bitmark
  75         on the second-least significant bit.
  76
  77         \p %FeldmanHashSet multi-level array is similar to a tree in that we keep a pointer to the root, which is a memory array
  78         called \p head. The length of the \p head memory array is unique, whereas every other \p arrayNode has a uniform length;
  79         a normal \p arrayNode has a fixed power-of-two length equal to the binary logarithm of a variable called \p arrayLength.
  80         The maximum depth of the tree, \p maxDepth, is the maximum number of pointers that must be followed to reach any node.
  81         We define \p currentDepth as the number of memory arrays that we need to traverse to reach the \p arrayNode on which
  82         we need to operate; this is initially one, because of \p head.
  83
  84         That approach to the structure of the hash set uses an extensible hashing scheme; <b> the hash value is treated as a bit
  85         string</b> and rehash incrementally.
  86
  87         @note Two important things you should keep in mind when you're using \p %FeldmanHashSet:
  88         - all keys must be fixed-size. It means that you cannot use \p std::string as a key for \p %FeldmanHashSet.
  89           Instead, for the strings you should 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 use that hash as a key in \p %FeldmanHashSet.
  93         - \p %FeldmanHashSet uses a perfect hashing. It means that if two different keys, for example, of type \p std::string,
  94           have identical hash then you cannot insert both that keys in the set. \p %FeldmanHashSet does not maintain the key,
  95           it maintains its fixed-size hash value.
  96
  97         The set supports @ref cds_intrusive_FeldmanHashSet_iterators "bidirectional thread-safe iterators".
  98
  99         Template parameters:
 100         - \p GC - safe memory reclamation schema. Can be \p gc::HP, \p gc::DHP or one of \ref cds_urcu_type "RCU type"
 101         - \p T - a value type to be stored in the set
 102         - \p Traits - type traits, the structure based on \p feldman_hashset::traits or result of \p feldman_hashset::make_traits metafunction.
 103             \p Traits is the mandatory argument because it has one mandatory type - an @ref feldman_hashset::traits::hash_accessor "accessor"
 104             to hash value of \p T. The set algorithm does not calculate that hash value.
 105
 106         There are several specializations of \p %FeldmanHashSet for each \p GC. You should include:
 107         - <tt><cds/intrusive/feldman_hashset_hp.h></tt> for \p gc::HP garbage collector
 108         - <tt><cds/intrusive/feldman_hashset_dhp.h></tt> for \p gc::DHP garbage collector
 109         - <tt><cds/intrusive/feldman_hashset_rcu.h></tt> for \ref cds_intrusive_FeldmanHashSet_rcu "RCU type". RCU specialization
 110             has a slightly different interface.
 111     */
 112     template <
 113         class GC
 114         ,typename T
 115 #ifdef CDS_DOXYGEN_INVOKED
 116        ,typename Traits = feldman_hashset::traits
 117 #else
 118        ,typename Traits
 119 #endif
 120     >
 121     class FeldmanHashSet: protected feldman_hashset::multilevel_array<T, Traits>
 122     {
 123         //@cond
 124         typedef feldman_hashset::multilevel_array<T, Traits> base_class;
 125         //@endcond
 126
 127     public:
 128         typedef GC      gc;         ///< Garbage collector
 129         typedef T       value_type; ///< type of value stored in the set
 130         typedef Traits  traits;     ///< Traits template parameter, see \p feldman_hashset::traits
 131
 132         typedef typename traits::hash_accessor hash_accessor;   ///< Hash accessor functor
 133         typedef typename base_class::hash_type hash_type;       ///< Hash type deduced from \p hash_accessor return type
 134         typedef typename traits::disposer disposer;             ///< data node disposer
 135         typedef typename base_class::hash_comparator hash_comparator; ///< hash compare functor based on \p traits::compare and \p traits::less options
 136
 137         typedef typename traits::item_counter   item_counter;   ///< Item counter type
 138         typedef typename traits::node_allocator node_allocator; ///< Array node allocator
 139         typedef typename traits::memory_model   memory_model;   ///< Memory model
 140         typedef typename traits::back_off       back_off;       ///< Backoff strategy
 141         typedef typename traits::stat           stat;           ///< Internal statistics type
 142
 143         typedef typename gc::template guarded_ptr< value_type > guarded_ptr; ///< Guarded pointer
 144
 145         /// Count of hazard pointers required
 146         static CDS_CONSTEXPR size_t const c_nHazardPtrCount = 2;
 147
 148         /// The size of hash_type in bytes, see \p feldman_hashset::traits::hash_size for explanation
 149         static CDS_CONSTEXPR size_t const c_hash_size = base_class::c_hash_size;
 150
 151         /// Level statistics
 152         typedef feldman_hashset::level_statistics level_statistics;
 153
 154     protected:
 155         //@cond
 156         typedef typename base_class::node_ptr node_ptr;
 157         typedef typename base_class::atomic_node_ptr atomic_node_ptr;
 158         typedef typename base_class::array_node array_node;
 159         typedef typename base_class::traverse_data traverse_data;
 160
 161         using base_class::to_array;
 162         using base_class::to_node;
 163         using base_class::stats;
 164         using base_class::head;
 165         using base_class::metrics;
 166         //@endcond
 167
 168     protected:
 169         //@cond
 170         class iterator_base
 171         {
 172             friend class FeldmanHashSet;
 173
 174         protected:
 175             array_node *        m_pNode;    ///< current array node
 176             size_t              m_idx;      ///< current position in m_pNode
 177             typename gc::Guard  m_guard;    ///< HP guard
 178             FeldmanHashSet const*  m_set;    ///< Hash set
 179
 180         public:
 181             iterator_base() CDS_NOEXCEPT
 182                 : m_pNode( nullptr )
 183                 , m_idx( 0 )
 184                 , m_set( nullptr )
 185             {}
 186
 187             iterator_base( iterator_base const& rhs ) CDS_NOEXCEPT
 188                 : m_pNode( rhs.m_pNode )
 189                 , m_idx( rhs.m_idx )
 190                 , m_set( rhs.m_set )
 191             {
 192                 m_guard.copy( rhs.m_guard );
 193             }
 194
 195             iterator_base& operator=( iterator_base const& rhs ) CDS_NOEXCEPT
 196             {
 197                 m_pNode = rhs.m_pNode;
 198                 m_idx = rhs.m_idx;
 199                 m_set = rhs.m_set;
 200                 m_guard.copy( rhs.m_guard );
 201                 return *this;
 202             }
 203
 204             iterator_base& operator++()
 205             {
 206                 forward();
 207                 return *this;
 208             }
 209
 210             iterator_base& operator--()
 211             {
 212                 backward();
 213                 return *this;
 214             }
 215
 216             void release()
 217             {
 218                 m_guard.clear();
 219             }
 220
 221             bool operator ==( iterator_base const& rhs ) const CDS_NOEXCEPT
 222             {
 223                 return m_pNode == rhs.m_pNode && m_idx == rhs.m_idx && m_set == rhs.m_set;
 224             }
 225
 226             bool operator !=( iterator_base const& rhs ) const CDS_NOEXCEPT
 227             {
 228                 return !( *this == rhs );
 229             }
 230
 231         protected:
 232             iterator_base( FeldmanHashSet const& set, array_node * pNode, size_t idx, bool )
 233                 : m_pNode( pNode )
 234                 , m_idx( idx )
 235                 , m_set( &set )
 236             {}
 237
 238             iterator_base( FeldmanHashSet const& set, array_node * pNode, size_t idx )
 239                 : m_pNode( pNode )
 240                 , m_idx( idx )
 241                 , m_set( &set )
 242             {
 243                 forward();
 244             }
 245
 246             value_type * pointer() const CDS_NOEXCEPT
 247             {
 248                 return m_guard.template get<value_type>();
 249             }
 250
 251             void forward()
 252             {
 253                 assert( m_set != nullptr );
 254                 assert( m_pNode != nullptr );
 255
 256                 size_t const arrayNodeSize = m_set->array_node_size();
 257                 size_t const headSize = m_set->head_size();
 258                 array_node * pNode = m_pNode;
 259                 size_t idx = m_idx + 1;
 260                 size_t nodeSize = m_pNode->pParent? arrayNodeSize : headSize;
 261
 262                 for ( ;; ) {
 263                     if ( idx < nodeSize ) {
 264                         node_ptr slot = pNode->nodes[idx].load( memory_model::memory_order_acquire );
 265                         if ( slot.bits() == base_class::flag_array_node ) {
 266                             // array node, go down the tree
 267                             assert( slot.ptr() != nullptr );
 268                             pNode = to_array( slot.ptr());
 269                             idx = 0;
 270                             nodeSize = arrayNodeSize;
 271                         }
 272                         else if ( slot.bits() == base_class::flag_array_converting ) {
 273                             // the slot is converting to array node right now - skip the node
 274                             ++idx;
 275                         }
 276                         else {
 277                             if ( slot.ptr()) {
 278                                 // data node
 279                                 if ( m_guard.protect( pNode->nodes[idx], []( node_ptr p ) -> value_type* { return p.ptr(); }) == slot ) {
 280                                     m_pNode = pNode;
 281                                     m_idx = idx;
 282                                     return;
 283                                 }
 284                             }
 285                             ++idx;
 286                         }
 287                     }
 288                     else {
 289                         // up to parent node
 290                         if ( pNode->pParent ) {
 291                             idx = pNode->idxParent + 1;
 292                             pNode = pNode->pParent;
 293                             nodeSize = pNode->pParent ? arrayNodeSize : headSize;
 294                         }
 295                         else {
 296                             // end()
 297                             assert( pNode == m_set->head());
 298                             assert( idx == headSize );
 299                             m_pNode = pNode;
 300                             m_idx = idx;
 301                             return;
 302                         }
 303                     }
 304                 }
 305             }
 306
 307             void backward()
 308             {
 309                 assert( m_set != nullptr );
 310                 assert( m_pNode != nullptr );
 311
 312                 size_t const arrayNodeSize = m_set->array_node_size();
 313                 size_t const headSize = m_set->head_size();
 314                 size_t const endIdx = size_t(0) - 1;
 315
 316                 array_node * pNode = m_pNode;
 317                 size_t idx = m_idx - 1;
 318                 size_t nodeSize = m_pNode->pParent? arrayNodeSize : headSize;
 319
 320                 for ( ;; ) {
 321                     if ( idx != endIdx ) {
 322                         node_ptr slot = pNode->nodes[idx].load( memory_model::memory_order_acquire );
 323                         if ( slot.bits() == base_class::flag_array_node ) {
 324                             // array node, go down the tree
 325                             assert( slot.ptr() != nullptr );
 326                             pNode = to_array( slot.ptr());
 327                             nodeSize = arrayNodeSize;
 328                             idx = nodeSize - 1;
 329                         }
 330                         else if ( slot.bits() == base_class::flag_array_converting ) {
 331                             // the slot is converting to array node right now - skip the node
 332                             --idx;
 333                         }
 334                         else {
 335                             if ( slot.ptr()) {
 336                                 // data node
 337                                 if ( m_guard.protect( pNode->nodes[idx], []( node_ptr p ) -> value_type* { return p.ptr(); }) == slot ) {
 338                                     m_pNode = pNode;
 339                                     m_idx = idx;
 340                                     return;
 341                                 }
 342                             }
 343                             --idx;
 344                         }
 345                     }
 346                     else {
 347                         // up to parent node
 348                         if ( pNode->pParent ) {
 349                             idx = pNode->idxParent - 1;
 350                             pNode = pNode->pParent;
 351                             nodeSize = pNode->pParent ? arrayNodeSize : headSize;
 352                         }
 353                         else {
 354                             // rend()
 355                             assert( pNode == m_set->head());
 356                             assert( idx == endIdx );
 357                             m_pNode = pNode;
 358                             m_idx = idx;
 359                             return;
 360                         }
 361                     }
 362                 }
 363             }
 364         };
 365
 366         template <class Iterator>
 367         Iterator init_begin() const
 368         {
 369             return Iterator( *this, head(), size_t(0) - 1 );
 370         }
 371
 372         template <class Iterator>
 373         Iterator init_end() const
 374         {
 375             return Iterator( *this, head(), head_size(), false );
 376         }
 377
 378         template <class Iterator>
 379         Iterator init_rbegin() const
 380         {
 381             return Iterator( *this, head(), head_size());
 382         }
 383
 384         template <class Iterator>
 385         Iterator init_rend() const
 386         {
 387             return Iterator( *this, head(), size_t(0) - 1, false );
 388         }
 389
 390         /// Bidirectional iterator class
 391         template <bool IsConst>
 392         class bidirectional_iterator: protected iterator_base
 393         {
 394             friend class FeldmanHashSet;
 395
 396         protected:
 397             static CDS_CONSTEXPR bool const c_bConstantIterator = IsConst;
 398
 399         public:
 400             typedef typename std::conditional< IsConst, value_type const*, value_type*>::type value_ptr; ///< Value pointer
 401             typedef typename std::conditional< IsConst, value_type const&, value_type&>::type value_ref; ///< Value reference
 402
 403         public:
 404             bidirectional_iterator() CDS_NOEXCEPT
 405             {}
 406
 407             bidirectional_iterator( bidirectional_iterator const& rhs ) CDS_NOEXCEPT
 408                 : iterator_base( rhs )
 409             {}
 410
 411             bidirectional_iterator& operator=( bidirectional_iterator const& rhs ) CDS_NOEXCEPT
 412             {
 413                 iterator_base::operator=( rhs );
 414                 return *this;
 415             }
 416
 417             bidirectional_iterator& operator++()
 418             {
 419                 iterator_base::operator++();
 420                 return *this;
 421             }
 422
 423             bidirectional_iterator& operator--()
 424             {
 425                 iterator_base::operator--();
 426                 return *this;
 427             }
 428
 429             value_ptr operator ->() const CDS_NOEXCEPT
 430             {
 431                 return iterator_base::pointer();
 432             }
 433
 434             value_ref operator *() const CDS_NOEXCEPT
 435             {
 436                 value_ptr p = iterator_base::pointer();
 437                 assert( p );
 438                 return *p;
 439             }
 440
 441             void release()
 442             {
 443                 iterator_base::release();
 444             }
 445
 446             template <bool IsConst2>
 447             bool operator ==( bidirectional_iterator<IsConst2> const& rhs ) const CDS_NOEXCEPT
 448             {
 449                 return iterator_base::operator==( rhs );
 450             }
 451
 452             template <bool IsConst2>
 453             bool operator !=( bidirectional_iterator<IsConst2> const& rhs ) const CDS_NOEXCEPT
 454             {
 455                 return !( *this == rhs );
 456             }
 457
 458         protected:
 459             bidirectional_iterator( FeldmanHashSet& set, array_node * pNode, size_t idx, bool )
 460                 : iterator_base( set, pNode, idx, false )
 461             {}
 462
 463             bidirectional_iterator( FeldmanHashSet& set, array_node * pNode, size_t idx )
 464                 : iterator_base( set, pNode, idx )
 465             {}
 466         };
 467
 468         /// Reverse bidirectional iterator
 469         template <bool IsConst>
 470         class reverse_bidirectional_iterator : public iterator_base
 471         {
 472             friend class FeldmanHashSet;
 473
 474         public:
 475             typedef typename std::conditional< IsConst, value_type const*, value_type*>::type value_ptr; ///< Value pointer
 476             typedef typename std::conditional< IsConst, value_type const&, value_type&>::type value_ref; ///< Value reference
 477
 478         public:
 479             reverse_bidirectional_iterator() CDS_NOEXCEPT
 480                 : iterator_base()
 481             {}
 482
 483             reverse_bidirectional_iterator( reverse_bidirectional_iterator const& rhs ) CDS_NOEXCEPT
 484                 : iterator_base( rhs )
 485             {}
 486
 487             reverse_bidirectional_iterator& operator=( reverse_bidirectional_iterator const& rhs) CDS_NOEXCEPT
 488             {
 489                 iterator_base::operator=( rhs );
 490                 return *this;
 491             }
 492
 493             reverse_bidirectional_iterator& operator++()
 494             {
 495                 iterator_base::operator--();
 496                 return *this;
 497             }
 498
 499             reverse_bidirectional_iterator& operator--()
 500             {
 501                 iterator_base::operator++();
 502                 return *this;
 503             }
 504
 505             value_ptr operator ->() const CDS_NOEXCEPT
 506             {
 507                 return iterator_base::pointer();
 508             }
 509
 510             value_ref operator *() const CDS_NOEXCEPT
 511             {
 512                 value_ptr p = iterator_base::pointer();
 513                 assert( p );
 514                 return *p;
 515             }
 516
 517             void release()
 518             {
 519                 iterator_base::release();
 520             }
 521
 522             template <bool IsConst2>
 523             bool operator ==( reverse_bidirectional_iterator<IsConst2> const& rhs ) const
 524             {
 525                 return iterator_base::operator==( rhs );
 526             }
 527
 528             template <bool IsConst2>
 529             bool operator !=( reverse_bidirectional_iterator<IsConst2> const& rhs )
 530             {
 531                 return !( *this == rhs );
 532             }
 533
 534         private:
 535             reverse_bidirectional_iterator( FeldmanHashSet& set, array_node * pNode, size_t idx, bool )
 536                 : iterator_base( set, pNode, idx, false )
 537             {}
 538
 539             reverse_bidirectional_iterator( FeldmanHashSet& set, array_node * pNode, size_t idx )
 540                 : iterator_base( set, pNode, idx, false )
 541             {
 542                 iterator_base::backward();
 543             }
 544         };
 545         //@endcond
 546
 547     public:
 548 #ifdef CDS_DOXYGEN_INVOKED
 549         typedef implementation_defined iterator;            ///< @ref cds_intrusive_FeldmanHashSet_iterators "bidirectional iterator" type
 550         typedef implementation_defined const_iterator;      ///< @ref cds_intrusive_FeldmanHashSet_iterators "bidirectional const iterator" type
 551         typedef implementation_defined reverse_iterator;    ///< @ref cds_intrusive_FeldmanHashSet_iterators "bidirectional reverse iterator" type
 552         typedef implementation_defined const_reverse_iterator; ///< @ref cds_intrusive_FeldmanHashSet_iterators "bidirectional reverse const iterator" type
 553 #else
 554         typedef bidirectional_iterator<false>   iterator;
 555         typedef bidirectional_iterator<true>    const_iterator;
 556         typedef reverse_bidirectional_iterator<false>   reverse_iterator;
 557         typedef reverse_bidirectional_iterator<true>    const_reverse_iterator;
 558 #endif
 559
 560     private:
 561         //@cond
 562         item_counter      m_ItemCounter; ///< Item counter
 563         //@endcond
 564
 565     public:
 566         /// Creates empty set
 567         /**
 568             @param head_bits - 2<sup>head_bits</sup> specifies the size of head array, minimum is 4.
 569             @param array_bits - 2<sup>array_bits</sup> specifies the size of array node, minimum is 2.
 570
 571             Equation for \p head_bits and \p array_bits:
 572             \code
 573             sizeof( hash_type ) * 8 == head_bits + N * array_bits
 574             \endcode
 575             where \p N is multi-level array depth.
 576         */
 577         FeldmanHashSet( size_t head_bits = 8, size_t array_bits = 4 )
 578             : base_class( head_bits, array_bits )
 579         {}
 580
 581         /// Destructs the set and frees all data
 582         ~FeldmanHashSet()
 583         {
 584             clear();
 585         }
 586
 587         /// Inserts new node
 588         /**
 589             The function inserts \p val in the set if it does not contain
 590             an item with that hash.
 591
 592             Returns \p true if \p val is placed into the set, \p false otherwise.
 593         */
 594         bool insert( value_type& val )
 595         {
 596             return insert( val, []( value_type& ) {} );
 597         }
 598
 599         /// Inserts new node
 600         /**
 601             This function is intended for derived non-intrusive containers.
 602
 603             The function allows to split creating of new item into two part:
 604             - create item with key only
 605             - insert new item into the set
 606             - if inserting is success, calls \p f functor to initialize \p val.
 607
 608             The functor signature is:
 609             \code
 610                 void func( value_type& val );
 611             \endcode
 612             where \p val is the item inserted.
 613
 614             The user-defined functor is called only if the inserting is success.
 615
 616             @warning See \ref cds_intrusive_item_creating "insert item troubleshooting".
 617         */
 618         template <typename Func>
 619         bool insert( value_type& val, Func f )
 620         {
 621             hash_type const& hash = hash_accessor()( val );
 622             traverse_data pos( hash, *this );
 623             hash_comparator cmp;
 624             typename gc::template GuardArray<2> guards;
 625
 626             guards.assign( 1, &val );
 627             while ( true ) {
 628                 node_ptr slot = base_class::traverse( pos );
 629                 assert( slot.bits() == 0 );
 630
 631                 // protect data node by hazard pointer
 632                 if ( guards.protect( 0, pos.pArr->nodes[pos.nSlot], []( node_ptr p ) -> value_type* { return p.ptr(); }) != slot ) {
 633                     // slot value has been changed - retry
 634                     stats().onSlotChanged();
 635                 }
 636                 else if ( slot.ptr()) {
 637                     if ( cmp( hash, hash_accessor()( *slot.ptr())) == 0 ) {
 638                         // the item with that hash value already exists
 639                         stats().onInsertFailed();
 640                         return false;
 641                     }
 642
 643                     if ( !pos.splitter.eos() ) {
 644                         // the slot must be expanded
 645                         base_class::expand_slot( pos, slot );
 646                     }
 647                     else
 648                         return false;
 649                 }
 650                 else {
 651                     // the slot is empty, try to insert data node
 652                     node_ptr pNull;
 653                     if ( pos.pArr->nodes[pos.nSlot].compare_exchange_strong( pNull, node_ptr( &val ), memory_model::memory_order_release, atomics::memory_order_relaxed ))
 654                     {
 655                         // the new data node has been inserted
 656                         f( val );
 657                         ++m_ItemCounter;
 658                         stats().onInsertSuccess();
 659                         stats().height( pos.nHeight );
 660                         return true;
 661                     }
 662
 663                     // insert failed - slot has been changed by another thread
 664                     // retry inserting
 665                     stats().onInsertRetry();
 666                 }
 667             }
 668         }
 669
 670         /// Updates the node
 671         /**
 672             Performs inserting or updating the item with hash value equal to \p val.
 673             - If hash value is found then existing item is replaced with \p val, old item is disposed
 674               with \p Traits::disposer. Note that the disposer is called by \p GC asynchronously.
 675               The function returns <tt> std::pair<true, false> </tt>
 676             - If hash value is not found and \p bInsert is \p true then \p val is inserted,
 677               the function returns <tt> std::pair<true, true> </tt>
 678             - If hash value is not found and \p bInsert is \p false then the set is unchanged,
 679               the function returns <tt> std::pair<false, false> </tt>
 680
 681             Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successful
 682             (i.e. the item has been inserted or updated),
 683             \p second is \p true if new item has been added or \p false if the set contains that hash.
 684         */
 685         std::pair<bool, bool> update( value_type& val, bool bInsert = true )
 686         {
 687             return do_update( val, []( value_type&, value_type* ) {}, bInsert );
 688         }
 689
 690         /// Unlinks the item \p val from the set
 691         /**
 692             The function searches the item \p val in the set and unlink it
 693             if it is found and its address is equal to <tt>&val</tt>.
 694
 695             The function returns \p true if success and \p false otherwise.
 696         */
 697         bool unlink( value_type const& val )
 698         {
 699             typename gc::Guard guard;
 700             auto pred = [&val]( value_type const& item ) -> bool { return &item == &val; };
 701             value_type * p = do_erase( hash_accessor()( val ), guard, std::ref( pred ));
 702             return p != nullptr;
 703         }
 704
 705         /// Deletes the item from the set
 706         /**
 707             The function searches \p hash in the set,
 708             unlinks the item found, and returns \p true.
 709             If that item is not found the function returns \p false.
 710
 711             The \ref disposer specified in \p Traits is called by garbage collector \p GC asynchronously.
 712         */
 713         bool erase( hash_type const& hash )
 714         {
 715             return erase( hash, []( value_type const& ) {} );
 716         }
 717
 718         /// Deletes the item from the set
 719         /**
 720             The function searches \p hash in the set,
 721             call \p f functor with item found, and unlinks it from the set.
 722             The \ref disposer specified in \p Traits is called
 723             by garbage collector \p GC asynchronously.
 724
 725             The \p Func interface is
 726             \code
 727             struct functor {
 728                 void operator()( value_type& item );
 729             };
 730             \endcode
 731
 732             If \p hash is not found the function returns \p false.
 733         */
 734         template <typename Func>
 735         bool erase( hash_type const& hash, Func f )
 736         {
 737             typename gc::Guard guard;
 738             value_type * p = do_erase( hash, guard, []( value_type const&) -> bool {return true; } );
 739
 740             // p is guarded by HP
 741             if ( p ) {
 742                 f( *p );
 743                 return true;
 744             }
 745             return false;
 746         }
 747
 748         /// Deletes the item pointed by iterator \p iter
 749         /**
 750             Returns \p true if the operation is successful, \p false otherwise.
 751
 752             The function does not invalidate the iterator, it remains valid and can be used for further traversing.
 753         */
 754         bool erase_at( iterator const& iter )
 755         {
 756             return do_erase_at( iter );
 757         }
 758         //@cond
 759         bool erase_at( reverse_iterator const& iter )
 760         {
 761             return do_erase_at( iter );
 762         }
 763         //@endcond
 764
 765         /// Extracts the item with specified \p hash
 766         /**
 767             The function searches \p hash in the set,
 768             unlinks it from the set, and returns an guarded pointer to the item extracted.
 769             If \p hash is not found the function returns an empty guarded pointer.
 770
 771             The \p disposer specified in \p Traits class' template parameter is called automatically
 772             by garbage collector \p GC when returned \ref guarded_ptr object to be destroyed or released.
 773             @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
 774
 775             Usage:
 776             \code
 777             typedef cds::intrusive::FeldmanHashSet< your_template_args > my_set;
 778             my_set theSet;
 779             // ...
 780             {
 781                 my_set::guarded_ptr gp( theSet.extract( 5 ));
 782                 if ( gp ) {
 783                     // Deal with gp
 784                     // ...
 785                 }
 786                 // Destructor of gp releases internal HP guard
 787             }
 788             \endcode
 789         */
 790         guarded_ptr extract( hash_type const& hash )
 791         {
 792             typename gc::Guard guard;
 793             if ( do_erase( hash, guard, []( value_type const&) -> bool {return true;} ))
 794                 return guarded_ptr( std::move( guard ));
 795             return guarded_ptr();
 796         }
 797
 798         /// Finds an item by it's \p hash
 799         /**
 800             The function searches the item by \p hash and calls the functor \p f for item found.
 801             The interface of \p Func functor is:
 802             \code
 803             struct functor {
 804                 void operator()( value_type& item );
 805             };
 806             \endcode
 807             where \p item is the item found.
 808
 809             The functor may change non-key fields of \p item. Note that the functor is only guarantee
 810             that \p item cannot be disposed during the functor is executing.
 811             The functor does not serialize simultaneous access to the set's \p item. If such access is
 812             possible you must provide your own synchronization schema on item level to prevent unsafe item modifications.
 813
 814             The function returns \p true if \p hash is found, \p false otherwise.
 815         */
 816         template <typename Func>
 817         bool find( hash_type const& hash, Func f )
 818         {
 819             typename gc::Guard guard;
 820             value_type * p = search( hash, guard );
 821
 822             // p is guarded by HP
 823             if ( p ) {
 824                 f( *p );
 825                 return true;
 826             }
 827             return false;
 828         }
 829
 830         /// Checks whether the set contains \p hash
 831         /**
 832             The function searches the item by its \p hash
 833             and returns \p true if it is found, or \p false otherwise.
 834         */
 835         bool contains( hash_type const& hash )
 836         {
 837             return find( hash, []( value_type& ) {} );
 838         }
 839
 840         /// Finds an item by it's \p hash and returns the item found
 841         /**
 842             The function searches the item by its \p hash
 843             and returns the guarded pointer to the item found.
 844             If \p hash is not found the function returns an empty \p guarded_ptr.
 845
 846             @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
 847
 848             Usage:
 849             \code
 850             typedef cds::intrusive::FeldmanHashSet< your_template_params >  my_set;
 851             my_set theSet;
 852             // ...
 853             {
 854                 my_set::guarded_ptr gp( theSet.get( 5 ));
 855                 if ( theSet.get( 5 )) {
 856                     // Deal with gp
 857                     //...
 858                 }
 859                 // Destructor of guarded_ptr releases internal HP guard
 860             }
 861             \endcode
 862         */
 863         guarded_ptr get( hash_type const& hash )
 864         {
 865             typename gc::Guard guard;
 866             if ( search( hash, guard ))
 867                 return guarded_ptr( std::move( guard ));
 868             return guarded_ptr();
 869         }
 870
 871         /// Clears the set (non-atomic)
 872         /**
 873             The function unlink all data node from the set.
 874             The function is not atomic but is thread-safe.
 875             After \p %clear() the set may not be empty because another threads may insert items.
 876
 877             For each item the \p disposer is called after unlinking.
 878         */
 879         void clear()
 880         {
 881             clear_array( head(), head_size());
 882         }
 883
 884         /// Checks if the set is empty
 885         /**
 886             Emptiness is checked by item counting: if item count is zero then the set is empty.
 887             Thus, the correct item counting feature is an important part of the set implementation.
 888         */
 889         bool empty() const
 890         {
 891             return size() == 0;
 892         }
 893
 894         /// Returns item count in the set
 895         size_t size() const
 896         {
 897             return m_ItemCounter;
 898         }
 899
 900         /// Returns const reference to internal statistics
 901         stat const& statistics() const
 902         {
 903             return stats();
 904         }
 905
 906         /// Returns the size of head node
 907         using base_class::head_size;
 908
 909         /// Returns the size of the array node
 910         using base_class::array_node_size;
 911
 912         /// Collects tree level statistics into \p stat
 913         /**
 914             The function traverses the set and collects statistics for each level of the tree
 915             into \p feldman_hashset::level_statistics struct. The element of \p stat[i]
 916             represents statistics for level \p i, level 0 is head array.
 917             The function is thread-safe and may be called in multi-threaded environment.
 918
 919             Result can be useful for estimating efficiency of hash functor you use.
 920         */
 921         void get_level_statistics( std::vector< feldman_hashset::level_statistics>& stat ) const
 922         {
 923             base_class::get_level_statistics( stat );
 924         }
 925
 926     public:
 927     ///@name Thread-safe iterators
 928         /** @anchor cds_intrusive_FeldmanHashSet_iterators
 929             The set supports thread-safe iterators: you may iterate over the set in multi-threaded environment.
 930             It is guaranteed that the iterators will remain valid even if another thread deletes the node the iterator points to:
 931             Hazard Pointer embedded into the iterator object protects the node from physical reclamation.
 932
 933             @note Since the iterator object contains hazard pointer that is a thread-local resource,
 934             the iterator should not be passed to another thread.
 935
 936             Each iterator object supports the common interface:
 937             - dereference operators:
 938                 @code
 939                 value_type [const] * operator ->() noexcept
 940                 value_type [const] & operator *() noexcept
 941                 @endcode
 942             - pre-increment and pre-decrement. Post-operators is not supported
 943             - equality operators <tt>==</tt> and <tt>!=</tt>.
 944                 Iterators are equal iff they point to the same cell of the same array node.
 945                 Note that for two iterators \p it1 and \p it2, the conditon <tt> it1 == it2 </tt>
 946                 does not entail <tt> &(*it1) == &(*it2) </tt>: welcome to concurrent containers
 947             - helper member function \p release() that clears internal hazard pointer.
 948                 After \p release() the iterator points to \p nullptr but it still remain valid: further iterating is possible.
 949
 950             During iteration you may safely erase any item from the set;
 951             @ref erase_at() function call doesn't invalidate any iterator.
 952             If some iterator points to the item to be erased, that item is not deleted immediately
 953             but only after that iterator will be advanced forward or backward.
 954
 955             @note It is possible the item can be iterated more that once, for example, if an iterator points to the item
 956             in array node that is being splitted.
 957         */
 958     ///@{
 959
 960         /// Returns an iterator to the beginning of the set
 961         iterator begin()
 962         {
 963             return iterator( *this, head(), size_t(0) - 1 );
 964         }
 965
 966         /// Returns an const iterator to the beginning of the set
 967         const_iterator begin() const
 968         {
 969             return const_iterator( *this, head(), size_t(0) - 1 );
 970         }
 971
 972         /// Returns an const iterator to the beginning of the set
 973         const_iterator cbegin()
 974         {
 975             return const_iterator( *this, head(), size_t(0) - 1 );
 976         }
 977
 978         /// Returns an iterator to the element following the last element of the set. This element acts as a placeholder; attempting to access it results in undefined behavior.
 979         iterator end()
 980         {
 981             return iterator( *this, head(), head_size(), false );
 982         }
 983
 984         /// Returns a const iterator to the element following the last element of the set. This element acts as a placeholder; attempting to access it results in undefined behavior.
 985         const_iterator end() const
 986         {
 987             return const_iterator( *this, head(), head_size(), false );
 988         }
 989
 990         /// Returns a const iterator to the element following the last element of the set. This element acts as a placeholder; attempting to access it results in undefined behavior.
 991         const_iterator cend()
 992         {
 993             return const_iterator( *this, head(), head_size(), false );
 994         }
 995
 996         /// Returns a reverse iterator to the first element of the reversed set
 997         reverse_iterator rbegin()
 998         {
 999             return reverse_iterator( *this, head(), head_size());
1000         }
1001
1002         /// Returns a const reverse iterator to the first element of the reversed set
1003         const_reverse_iterator rbegin() const
1004         {
1005             return const_reverse_iterator( *this, head(), head_size());
1006         }
1007
1008         /// Returns a const reverse iterator to the first element of the reversed set
1009         const_reverse_iterator crbegin()
1010         {
1011             return const_reverse_iterator( *this, head(), head_size());
1012         }
1013
1014         /// Returns a reverse iterator to the element following the last element of the reversed set
1015         /**
1016             It corresponds to the element preceding the first element of the non-reversed container.
1017             This element acts as a placeholder, attempting to access it results in undefined behavior.
1018         */
1019         reverse_iterator rend()
1020         {
1021             return reverse_iterator( *this, head(), size_t(0) - 1, false );
1022         }
1023
1024         /// Returns a const reverse iterator to the element following the last element of the reversed set
1025         /**
1026             It corresponds to the element preceding the first element of the non-reversed container.
1027             This element acts as a placeholder, attempting to access it results in undefined behavior.
1028         */
1029         const_reverse_iterator rend() const
1030         {
1031             return const_reverse_iterator( *this, head(), size_t(0) - 1, false );
1032         }
1033
1034         /// Returns a const reverse iterator to the element following the last element of the reversed set
1035         /**
1036             It corresponds to the element preceding the first element of the non-reversed container.
1037             This element acts as a placeholder, attempting to access it results in undefined behavior.
1038         */
1039         const_reverse_iterator crend()
1040         {
1041             return const_reverse_iterator( *this, head(), size_t(0) - 1, false );
1042         }
1043     ///@}
1044
1045     private:
1046         //@cond
1047         void clear_array( array_node * pArrNode, size_t nSize )
1048         {
1049             back_off bkoff;
1050
1051             for ( atomic_node_ptr * pArr = pArrNode->nodes, *pLast = pArr + nSize; pArr != pLast; ++pArr ) {
1052                 while ( true ) {
1053                     node_ptr slot = pArr->load( memory_model::memory_order_acquire );
1054                     if ( slot.bits() == base_class::flag_array_node ) {
1055                         // array node, go down the tree
1056                         assert( slot.ptr() != nullptr );
1057                         clear_array( to_array( slot.ptr()), array_node_size());
1058                         break;
1059                     }
1060                     else if ( slot.bits() == base_class::flag_array_converting ) {
1061                         // the slot is converting to array node right now
1062                         while (( slot = pArr->load( memory_model::memory_order_acquire )).bits() == base_class::flag_array_converting ) {
1063                             bkoff();
1064                             stats().onSlotConverting();
1065                         }
1066                         bkoff.reset();
1067
1068                         assert( slot.ptr() != nullptr );
1069                         assert( slot.bits() == base_class::flag_array_node );
1070                         clear_array( to_array( slot.ptr()), array_node_size());
1071                         break;
1072                     }
1073                     else {
1074                         // data node
1075                         if ( pArr->compare_exchange_strong( slot, node_ptr(), memory_model::memory_order_acquire, atomics::memory_order_relaxed )) {
1076                             if ( slot.ptr()) {
1077                                 gc::template retire<disposer>( slot.ptr());
1078                                 --m_ItemCounter;
1079                                 stats().onEraseSuccess();
1080                             }
1081                             break;
1082                         }
1083                     }
1084                 }
1085             }
1086         }
1087         //@endcond
1088
1089     protected:
1090         //@cond
1091         value_type * search( hash_type const& hash, typename gc::Guard& guard )
1092         {
1093             traverse_data pos( hash, *this );
1094             hash_comparator cmp;
1095
1096             while ( true ) {
1097                 node_ptr slot = base_class::traverse( pos );
1098                 assert( slot.bits() == 0 );
1099
1100                 // protect data node by hazard pointer
1101                 if ( guard.protect( pos.pArr->nodes[pos.nSlot], []( node_ptr p ) -> value_type* { return p.ptr(); }) != slot) {
1102                     // slot value has been changed - retry
1103                     stats().onSlotChanged();
1104                     continue;
1105                 }
1106                 else if ( slot.ptr() && cmp( hash, hash_accessor()( *slot.ptr())) == 0 ) {
1107                     // item found
1108                     stats().onFindSuccess();
1109                     return slot.ptr();
1110                 }
1111                 stats().onFindFailed();
1112                 return nullptr;
1113             }
1114         }
1115
1116         template <typename Predicate>
1117         value_type * do_erase( hash_type const& hash, typename gc::Guard& guard, Predicate pred )
1118         {
1119             traverse_data pos( hash, *this );
1120             hash_comparator cmp;
1121             while ( true ) {
1122                 node_ptr slot = base_class::traverse( pos );
1123                 assert( slot.bits() == 0 );
1124
1125                 // protect data node by hazard pointer
1126                 if ( guard.protect( pos.pArr->nodes[pos.nSlot], []( node_ptr p ) -> value_type* { return p.ptr(); }) != slot ) {
1127                     // slot value has been changed - retry
1128                     stats().onSlotChanged();
1129                 }
1130                 else if ( slot.ptr()) {
1131                     if ( cmp( hash, hash_accessor()( *slot.ptr())) == 0 && pred( *slot.ptr())) {
1132                         // item found - replace it with nullptr
1133                         if ( pos.pArr->nodes[pos.nSlot].compare_exchange_strong( slot, node_ptr( nullptr ), memory_model::memory_order_acquire, atomics::memory_order_relaxed)) {
1134                             // slot is guarded by HP
1135                             gc::template retire<disposer>( slot.ptr());
1136                             --m_ItemCounter;
1137                             stats().onEraseSuccess();
1138
1139                             return slot.ptr();
1140                         }
1141                         stats().onEraseRetry();
1142                         continue;
1143                     }
1144                     stats().onEraseFailed();
1145                     return nullptr;
1146                 }
1147                 else {
1148                     // the slot is empty
1149                     stats().onEraseFailed();
1150                     return nullptr;
1151                 }
1152             }
1153         }
1154
1155         bool do_erase_at( iterator_base const& iter )
1156         {
1157             if ( iter.m_set != this )
1158                 return false;
1159             if ( iter.m_pNode == head()) {
1160                 if ( iter.m_idx >= head_size())
1161                     return false;
1162             }
1163             else if ( iter.m_idx >= array_node_size())
1164                 return false;
1165
1166             for (;;) {
1167                 node_ptr slot = iter.m_pNode->nodes[iter.m_idx].load( memory_model::memory_order_acquire );
1168                 if ( slot.bits() == 0 && slot.ptr() == iter.pointer()) {
1169                     if ( iter.m_pNode->nodes[iter.m_idx].compare_exchange_strong( slot, node_ptr( nullptr ), memory_model::memory_order_acquire, atomics::memory_order_relaxed )) {
1170                         // the item is guarded by iterator, so we may retire it safely
1171                         gc::template retire<disposer>( slot.ptr());
1172                         --m_ItemCounter;
1173                         stats().onEraseSuccess();
1174                         return true;
1175                     }
1176                 }
1177                 else
1178                     return false;
1179             }
1180         }
1181
1182         template <typename Func>
1183         std::pair<bool, bool> do_update( value_type& val, Func f, bool bInsert = true )
1184         {
1185             hash_type const& hash = hash_accessor()( val );
1186             traverse_data pos( hash, *this );
1187             hash_comparator cmp;
1188             typename gc::template GuardArray<2> guards;
1189
1190             guards.assign( 1, &val );
1191             while ( true ) {
1192                 node_ptr slot = base_class::traverse( pos );
1193                 assert( slot.bits() == 0 );
1194
1195                 // protect data node by hazard pointer
1196                 if ( guards.protect( 0, pos.pArr->nodes[pos.nSlot], []( node_ptr p ) -> value_type* { return p.ptr(); }) != slot ) {
1197                     // slot value has been changed - retry
1198                     stats().onSlotChanged();
1199                 }
1200                 else if ( slot.ptr()) {
1201                     if ( cmp( hash, hash_accessor()( *slot.ptr())) == 0 ) {
1202                         // the item with that hash value already exists
1203                         // Replace it with val
1204                         if ( slot.ptr() == &val ) {
1205                             stats().onUpdateExisting();
1206                             return std::make_pair( true, false );
1207                         }
1208
1209                         if ( pos.pArr->nodes[pos.nSlot].compare_exchange_strong( slot, node_ptr( &val ), memory_model::memory_order_release, atomics::memory_order_relaxed )) {
1210                             // slot can be disposed
1211                             f( val, slot.ptr());
1212                             gc::template retire<disposer>( slot.ptr());
1213                             stats().onUpdateExisting();
1214                             return std::make_pair( true, false );
1215                         }
1216
1217                         stats().onUpdateRetry();
1218                         continue;
1219                     }
1220
1221                     if ( bInsert ) {
1222                         if ( !pos.splitter.eos() ) {
1223                             // the slot must be expanded
1224                             base_class::expand_slot( pos, slot );
1225                         }
1226                         else
1227                             return std::make_pair( false, false );
1228                     }
1229                     else {
1230                         stats().onUpdateFailed();
1231                         return std::make_pair( false, false );
1232                     }
1233                 }
1234                 else {
1235                     // the slot is empty, try to insert data node
1236                     if ( bInsert ) {
1237                         node_ptr pNull;
1238                         if ( pos.pArr->nodes[pos.nSlot].compare_exchange_strong( pNull, node_ptr( &val ), memory_model::memory_order_release, atomics::memory_order_relaxed ))
1239                         {
1240                             // the new data node has been inserted
1241                             f( val, nullptr );
1242                             ++m_ItemCounter;
1243                             stats().onUpdateNew();
1244                             stats().height( pos.nHeight );
1245                             return std::make_pair( true, true );
1246                         }
1247                     }
1248                     else {
1249                         stats().onUpdateFailed();
1250                         return std::make_pair( false, false );
1251                     }
1252
1253                     // insert failed - slot has been changed by another thread
1254                     // retry updating
1255                     stats().onUpdateRetry();
1256                 }
1257             } // while
1258         }
1259         //@endcond
1260     };
1261 }} // namespace cds::intrusive
1262
1263 #endif // #ifndef CDSLIB_INTRUSIVE_IMPL_FELDMAN_HASHSET_H