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                     // the slot must be expanded
 644                     base_class::expand_slot( pos, slot );
 645                 }
 646                 else {
 647                     // the slot is empty, try to insert data node
 648                     node_ptr pNull;
 649                     if ( pos.pArr->nodes[pos.nSlot].compare_exchange_strong( pNull, node_ptr( &val ), memory_model::memory_order_release, atomics::memory_order_relaxed ))
 650                     {
 651                         // the new data node has been inserted
 652                         f( val );
 653                         ++m_ItemCounter;
 654                         stats().onInsertSuccess();
 655                         stats().height( pos.nHeight );
 656                         return true;
 657                     }
 658
 659                     // insert failed - slot has been changed by another thread
 660                     // retry inserting
 661                     stats().onInsertRetry();
 662                 }
 663             }
 664         }
 665
 666         /// Updates the node
 667         /**
 668             Performs inserting or updating the item with hash value equal to \p val.
 669             - If hash value is found then existing item is replaced with \p val, old item is disposed
 670               with \p Traits::disposer. Note that the disposer is called by \p GC asynchronously.
 671               The function returns <tt> std::pair<true, false> </tt>
 672             - If hash value is not found and \p bInsert is \p true then \p val is inserted,
 673               the function returns <tt> std::pair<true, true> </tt>
 674             - If hash value is not found and \p bInsert is \p false then the set is unchanged,
 675               the function returns <tt> std::pair<false, false> </tt>
 676
 677             Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successful
 678             (i.e. the item has been inserted or updated),
 679             \p second is \p true if new item has been added or \p false if the set contains that hash.
 680         */
 681         std::pair<bool, bool> update( value_type& val, bool bInsert = true )
 682         {
 683             return do_update( val, []( value_type&, value_type* ) {}, bInsert );
 684         }
 685
 686         /// Unlinks the item \p val from the set
 687         /**
 688             The function searches the item \p val in the set and unlink it
 689             if it is found and its address is equal to <tt>&val</tt>.
 690
 691             The function returns \p true if success and \p false otherwise.
 692         */
 693         bool unlink( value_type const& val )
 694         {
 695             typename gc::Guard guard;
 696             auto pred = [&val]( value_type const& item ) -> bool { return &item == &val; };
 697             value_type * p = do_erase( hash_accessor()( val ), guard, std::ref( pred ));
 698             return p != nullptr;
 699         }
 700
 701         /// Deletes the item from the set
 702         /**
 703             The function searches \p hash in the set,
 704             unlinks the item found, and returns \p true.
 705             If that item is not found the function returns \p false.
 706
 707             The \ref disposer specified in \p Traits is called by garbage collector \p GC asynchronously.
 708         */
 709         bool erase( hash_type const& hash )
 710         {
 711             return erase( hash, []( value_type const& ) {} );
 712         }
 713
 714         /// Deletes the item from the set
 715         /**
 716             The function searches \p hash in the set,
 717             call \p f functor with item found, and unlinks it from the set.
 718             The \ref disposer specified in \p Traits is called
 719             by garbage collector \p GC asynchronously.
 720
 721             The \p Func interface is
 722             \code
 723             struct functor {
 724                 void operator()( value_type& item );
 725             };
 726             \endcode
 727
 728             If \p hash is not found the function returns \p false.
 729         */
 730         template <typename Func>
 731         bool erase( hash_type const& hash, Func f )
 732         {
 733             typename gc::Guard guard;
 734             value_type * p = do_erase( hash, guard, []( value_type const&) -> bool {return true; } );
 735
 736             // p is guarded by HP
 737             if ( p ) {
 738                 f( *p );
 739                 return true;
 740             }
 741             return false;
 742         }
 743
 744         /// Deletes the item pointed by iterator \p iter
 745         /**
 746             Returns \p true if the operation is successful, \p false otherwise.
 747
 748             The function does not invalidate the iterator, it remains valid and can be used for further traversing.
 749         */
 750         bool erase_at( iterator const& iter )
 751         {
 752             return do_erase_at( iter );
 753         }
 754         //@cond
 755         bool erase_at( reverse_iterator const& iter )
 756         {
 757             return do_erase_at( iter );
 758         }
 759         //@endcond
 760
 761         /// Extracts the item with specified \p hash
 762         /**
 763             The function searches \p hash in the set,
 764             unlinks it from the set, and returns an guarded pointer to the item extracted.
 765             If \p hash is not found the function returns an empty guarded pointer.
 766
 767             The \p disposer specified in \p Traits class' template parameter is called automatically
 768             by garbage collector \p GC when returned \ref guarded_ptr object to be destroyed or released.
 769             @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
 770
 771             Usage:
 772             \code
 773             typedef cds::intrusive::FeldmanHashSet< your_template_args > my_set;
 774             my_set theSet;
 775             // ...
 776             {
 777                 my_set::guarded_ptr gp( theSet.extract( 5 ));
 778                 if ( gp ) {
 779                     // Deal with gp
 780                     // ...
 781                 }
 782                 // Destructor of gp releases internal HP guard
 783             }
 784             \endcode
 785         */
 786         guarded_ptr extract( hash_type const& hash )
 787         {
 788             typename gc::Guard guard;
 789             if ( do_erase( hash, guard, []( value_type const&) -> bool {return true;} ))
 790                 return guarded_ptr( std::move( guard ));
 791             return guarded_ptr();
 792         }
 793
 794         /// Finds an item by it's \p hash
 795         /**
 796             The function searches the item by \p hash and calls the functor \p f for item found.
 797             The interface of \p Func functor is:
 798             \code
 799             struct functor {
 800                 void operator()( value_type& item );
 801             };
 802             \endcode
 803             where \p item is the item found.
 804
 805             The functor may change non-key fields of \p item. Note that the functor is only guarantee
 806             that \p item cannot be disposed during the functor is executing.
 807             The functor does not serialize simultaneous access to the set's \p item. If such access is
 808             possible you must provide your own synchronization schema on item level to prevent unsafe item modifications.
 809
 810             The function returns \p true if \p hash is found, \p false otherwise.
 811         */
 812         template <typename Func>
 813         bool find( hash_type const& hash, Func f )
 814         {
 815             typename gc::Guard guard;
 816             value_type * p = search( hash, guard );
 817
 818             // p is guarded by HP
 819             if ( p ) {
 820                 f( *p );
 821                 return true;
 822             }
 823             return false;
 824         }
 825
 826         /// Checks whether the set contains \p hash
 827         /**
 828             The function searches the item by its \p hash
 829             and returns \p true if it is found, or \p false otherwise.
 830         */
 831         bool contains( hash_type const& hash )
 832         {
 833             return find( hash, []( value_type& ) {} );
 834         }
 835
 836         /// Finds an item by it's \p hash and returns the item found
 837         /**
 838             The function searches the item by its \p hash
 839             and returns the guarded pointer to the item found.
 840             If \p hash is not found the function returns an empty \p guarded_ptr.
 841
 842             @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
 843
 844             Usage:
 845             \code
 846             typedef cds::intrusive::FeldmanHashSet< your_template_params >  my_set;
 847             my_set theSet;
 848             // ...
 849             {
 850                 my_set::guarded_ptr gp( theSet.get( 5 ));
 851                 if ( theSet.get( 5 )) {
 852                     // Deal with gp
 853                     //...
 854                 }
 855                 // Destructor of guarded_ptr releases internal HP guard
 856             }
 857             \endcode
 858         */
 859         guarded_ptr get( hash_type const& hash )
 860         {
 861             typename gc::Guard guard;
 862             if ( search( hash, guard ))
 863                 return guarded_ptr( std::move( guard ));
 864             return guarded_ptr();
 865         }
 866
 867         /// Clears the set (non-atomic)
 868         /**
 869             The function unlink all data node from the set.
 870             The function is not atomic but is thread-safe.
 871             After \p %clear() the set may not be empty because another threads may insert items.
 872
 873             For each item the \p disposer is called after unlinking.
 874         */
 875         void clear()
 876         {
 877             clear_array( head(), head_size());
 878         }
 879
 880         /// Checks if the set is empty
 881         /**
 882             Emptiness is checked by item counting: if item count is zero then the set is empty.
 883             Thus, the correct item counting feature is an important part of the set implementation.
 884         */
 885         bool empty() const
 886         {
 887             return size() == 0;
 888         }
 889
 890         /// Returns item count in the set
 891         size_t size() const
 892         {
 893             return m_ItemCounter;
 894         }
 895
 896         /// Returns const reference to internal statistics
 897         stat const& statistics() const
 898         {
 899             return stats();
 900         }
 901
 902         /// Returns the size of head node
 903         using base_class::head_size;
 904
 905         /// Returns the size of the array node
 906         using base_class::array_node_size;
 907
 908         /// Collects tree level statistics into \p stat
 909         /**
 910             The function traverses the set and collects statistics for each level of the tree
 911             into \p feldman_hashset::level_statistics struct. The element of \p stat[i]
 912             represents statistics for level \p i, level 0 is head array.
 913             The function is thread-safe and may be called in multi-threaded environment.
 914
 915             Result can be useful for estimating efficiency of hash functor you use.
 916         */
 917         void get_level_statistics( std::vector< feldman_hashset::level_statistics>& stat ) const
 918         {
 919             base_class::get_level_statistics( stat );
 920         }
 921
 922     public:
 923     ///@name Thread-safe iterators
 924         /** @anchor cds_intrusive_FeldmanHashSet_iterators
 925             The set supports thread-safe iterators: you may iterate over the set in multi-threaded environment.
 926             It is guaranteed that the iterators will remain valid even if another thread deletes the node the iterator points to:
 927             Hazard Pointer embedded into the iterator object protects the node from physical reclamation.
 928
 929             @note Since the iterator object contains hazard pointer that is a thread-local resource,
 930             the iterator should not be passed to another thread.
 931
 932             Each iterator object supports the common interface:
 933             - dereference operators:
 934                 @code
 935                 value_type [const] * operator ->() noexcept
 936                 value_type [const] & operator *() noexcept
 937                 @endcode
 938             - pre-increment and pre-decrement. Post-operators is not supported
 939             - equality operators <tt>==</tt> and <tt>!=</tt>.
 940                 Iterators are equal iff they point to the same cell of the same array node.
 941                 Note that for two iterators \p it1 and \p it2, the conditon <tt> it1 == it2 </tt>
 942                 does not entail <tt> &(*it1) == &(*it2) </tt>: welcome to concurrent containers
 943             - helper member function \p release() that clears internal hazard pointer.
 944                 After \p release() the iterator points to \p nullptr but it still remain valid: further iterating is possible.
 945
 946             During iteration you may safely erase any item from the set;
 947             @ref erase_at() function call doesn't invalidate any iterator.
 948             If some iterator points to the item to be erased, that item is not deleted immediately
 949             but only after that iterator will be advanced forward or backward.
 950
 951             @note It is possible the item can be iterated more that once, for example, if an iterator points to the item
 952             in array node that is being splitted.
 953         */
 954     ///@{
 955
 956         /// Returns an iterator to the beginning of the set
 957         iterator begin()
 958         {
 959             return iterator( *this, head(), size_t(0) - 1 );
 960         }
 961
 962         /// Returns an const iterator to the beginning of the set
 963         const_iterator begin() const
 964         {
 965             return const_iterator( *this, head(), size_t(0) - 1 );
 966         }
 967
 968         /// Returns an const iterator to the beginning of the set
 969         const_iterator cbegin()
 970         {
 971             return const_iterator( *this, head(), size_t(0) - 1 );
 972         }
 973
 974         /// 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.
 975         iterator end()
 976         {
 977             return iterator( *this, head(), head_size(), false );
 978         }
 979
 980         /// 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.
 981         const_iterator end() const
 982         {
 983             return const_iterator( *this, head(), head_size(), false );
 984         }
 985
 986         /// 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.
 987         const_iterator cend()
 988         {
 989             return const_iterator( *this, head(), head_size(), false );
 990         }
 991
 992         /// Returns a reverse iterator to the first element of the reversed set
 993         reverse_iterator rbegin()
 994         {
 995             return reverse_iterator( *this, head(), head_size());
 996         }
 997
 998         /// Returns a const reverse iterator to the first element of the reversed set
 999         const_reverse_iterator rbegin() const
1000         {
1001             return const_reverse_iterator( *this, head(), head_size());
1002         }
1003
1004         /// Returns a const reverse iterator to the first element of the reversed set
1005         const_reverse_iterator crbegin()
1006         {
1007             return const_reverse_iterator( *this, head(), head_size());
1008         }
1009
1010         /// Returns a reverse iterator to the element following the last element of the reversed set
1011         /**
1012             It corresponds to the element preceding the first element of the non-reversed container.
1013             This element acts as a placeholder, attempting to access it results in undefined behavior.
1014         */
1015         reverse_iterator rend()
1016         {
1017             return reverse_iterator( *this, head(), size_t(0) - 1, false );
1018         }
1019
1020         /// Returns a const reverse iterator to the element following the last element of the reversed set
1021         /**
1022             It corresponds to the element preceding the first element of the non-reversed container.
1023             This element acts as a placeholder, attempting to access it results in undefined behavior.
1024         */
1025         const_reverse_iterator rend() const
1026         {
1027             return const_reverse_iterator( *this, head(), size_t(0) - 1, false );
1028         }
1029
1030         /// Returns a const reverse iterator to the element following the last element of the reversed set
1031         /**
1032             It corresponds to the element preceding the first element of the non-reversed container.
1033             This element acts as a placeholder, attempting to access it results in undefined behavior.
1034         */
1035         const_reverse_iterator crend()
1036         {
1037             return const_reverse_iterator( *this, head(), size_t(0) - 1, false );
1038         }
1039     ///@}
1040
1041     private:
1042         //@cond
1043         void clear_array( array_node * pArrNode, size_t nSize )
1044         {
1045             back_off bkoff;
1046
1047             for ( atomic_node_ptr * pArr = pArrNode->nodes, *pLast = pArr + nSize; pArr != pLast; ++pArr ) {
1048                 while ( true ) {
1049                     node_ptr slot = pArr->load( memory_model::memory_order_acquire );
1050                     if ( slot.bits() == base_class::flag_array_node ) {
1051                         // array node, go down the tree
1052                         assert( slot.ptr() != nullptr );
1053                         clear_array( to_array( slot.ptr()), array_node_size());
1054                         break;
1055                     }
1056                     else if ( slot.bits() == base_class::flag_array_converting ) {
1057                         // the slot is converting to array node right now
1058                         while (( slot = pArr->load( memory_model::memory_order_acquire )).bits() == base_class::flag_array_converting ) {
1059                             bkoff();
1060                             stats().onSlotConverting();
1061                         }
1062                         bkoff.reset();
1063
1064                         assert( slot.ptr() != nullptr );
1065                         assert( slot.bits() == base_class::flag_array_node );
1066                         clear_array( to_array( slot.ptr()), array_node_size());
1067                         break;
1068                     }
1069                     else {
1070                         // data node
1071                         if ( pArr->compare_exchange_strong( slot, node_ptr(), memory_model::memory_order_acquire, atomics::memory_order_relaxed )) {
1072                             if ( slot.ptr()) {
1073                                 gc::template retire<disposer>( slot.ptr());
1074                                 --m_ItemCounter;
1075                                 stats().onEraseSuccess();
1076                             }
1077                             break;
1078                         }
1079                     }
1080                 }
1081             }
1082         }
1083         //@endcond
1084
1085     protected:
1086         //@cond
1087         value_type * search( hash_type const& hash, typename gc::Guard& guard )
1088         {
1089             traverse_data pos( hash, *this );
1090             hash_comparator cmp;
1091
1092             while ( true ) {
1093                 node_ptr slot = base_class::traverse( pos );
1094                 assert( slot.bits() == 0 );
1095
1096                 // protect data node by hazard pointer
1097                 if ( guard.protect( pos.pArr->nodes[pos.nSlot], []( node_ptr p ) -> value_type* { return p.ptr(); }) != slot) {
1098                     // slot value has been changed - retry
1099                     stats().onSlotChanged();
1100                     continue;
1101                 }
1102                 else if ( slot.ptr() && cmp( hash, hash_accessor()( *slot.ptr())) == 0 ) {
1103                     // item found
1104                     stats().onFindSuccess();
1105                     return slot.ptr();
1106                 }
1107                 stats().onFindFailed();
1108                 return nullptr;
1109             }
1110         }
1111
1112         template <typename Predicate>
1113         value_type * do_erase( hash_type const& hash, typename gc::Guard& guard, Predicate pred )
1114         {
1115             traverse_data pos( hash, *this );
1116             hash_comparator cmp;
1117             while ( true ) {
1118                 node_ptr slot = base_class::traverse( pos );
1119                 assert( slot.bits() == 0 );
1120
1121                 // protect data node by hazard pointer
1122                 if ( guard.protect( pos.pArr->nodes[pos.nSlot], []( node_ptr p ) -> value_type* { return p.ptr(); }) != slot ) {
1123                     // slot value has been changed - retry
1124                     stats().onSlotChanged();
1125                 }
1126                 else if ( slot.ptr()) {
1127                     if ( cmp( hash, hash_accessor()( *slot.ptr())) == 0 && pred( *slot.ptr())) {
1128                         // item found - replace it with nullptr
1129                         if ( pos.pArr->nodes[pos.nSlot].compare_exchange_strong( slot, node_ptr( nullptr ), memory_model::memory_order_acquire, atomics::memory_order_relaxed)) {
1130                             // slot is guarded by HP
1131                             gc::template retire<disposer>( slot.ptr());
1132                             --m_ItemCounter;
1133                             stats().onEraseSuccess();
1134
1135                             return slot.ptr();
1136                         }
1137                         stats().onEraseRetry();
1138                         continue;
1139                     }
1140                     stats().onEraseFailed();
1141                     return nullptr;
1142                 }
1143                 else {
1144                     // the slot is empty
1145                     stats().onEraseFailed();
1146                     return nullptr;
1147                 }
1148             }
1149         }
1150
1151         bool do_erase_at( iterator_base const& iter )
1152         {
1153             if ( iter.m_set != this )
1154                 return false;
1155             if ( iter.m_pNode == head()) {
1156                 if ( iter.m_idx >= head_size())
1157                     return false;
1158             }
1159             else if ( iter.m_idx >= array_node_size())
1160                 return false;
1161
1162             for (;;) {
1163                 node_ptr slot = iter.m_pNode->nodes[iter.m_idx].load( memory_model::memory_order_acquire );
1164                 if ( slot.bits() == 0 && slot.ptr() == iter.pointer()) {
1165                     if ( iter.m_pNode->nodes[iter.m_idx].compare_exchange_strong( slot, node_ptr( nullptr ), memory_model::memory_order_acquire, atomics::memory_order_relaxed )) {
1166                         // the item is guarded by iterator, so we may retire it safely
1167                         gc::template retire<disposer>( slot.ptr());
1168                         --m_ItemCounter;
1169                         stats().onEraseSuccess();
1170                         return true;
1171                     }
1172                 }
1173                 else
1174                     return false;
1175             }
1176         }
1177
1178         template <typename Func>
1179         std::pair<bool, bool> do_update( value_type& val, Func f, bool bInsert = true )
1180         {
1181             hash_type const& hash = hash_accessor()( val );
1182             traverse_data pos( hash, *this );
1183             hash_comparator cmp;
1184             typename gc::template GuardArray<2> guards;
1185
1186             guards.assign( 1, &val );
1187             while ( true ) {
1188                 node_ptr slot = base_class::traverse( pos );
1189                 assert( slot.bits() == 0 );
1190
1191                 // protect data node by hazard pointer
1192                 if ( guards.protect( 0, pos.pArr->nodes[pos.nSlot], []( node_ptr p ) -> value_type* { return p.ptr(); }) != slot ) {
1193                     // slot value has been changed - retry
1194                     stats().onSlotChanged();
1195                 }
1196                 else if ( slot.ptr()) {
1197                     if ( cmp( hash, hash_accessor()( *slot.ptr())) == 0 ) {
1198                         // the item with that hash value already exists
1199                         // Replace it with val
1200                         if ( slot.ptr() == &val ) {
1201                             stats().onUpdateExisting();
1202                             return std::make_pair( true, false );
1203                         }
1204
1205                         if ( pos.pArr->nodes[pos.nSlot].compare_exchange_strong( slot, node_ptr( &val ), memory_model::memory_order_release, atomics::memory_order_relaxed )) {
1206                             // slot can be disposed
1207                             f( val, slot.ptr());
1208                             gc::template retire<disposer>( slot.ptr());
1209                             stats().onUpdateExisting();
1210                             return std::make_pair( true, false );
1211                         }
1212
1213                         stats().onUpdateRetry();
1214                         continue;
1215                     }
1216
1217                     if ( bInsert ) {
1218                         // the slot must be expanded
1219                         base_class::expand_slot( pos, slot );
1220                     }
1221                     else {
1222                         stats().onUpdateFailed();
1223                         return std::make_pair( false, false );
1224                     }
1225                 }
1226                 else {
1227                     // the slot is empty, try to insert data node
1228                     if ( bInsert ) {
1229                         node_ptr pNull;
1230                         if ( pos.pArr->nodes[pos.nSlot].compare_exchange_strong( pNull, node_ptr( &val ), memory_model::memory_order_release, atomics::memory_order_relaxed ))
1231                         {
1232                             // the new data node has been inserted
1233                             f( val, nullptr );
1234                             ++m_ItemCounter;
1235                             stats().onUpdateNew();
1236                             stats().height( pos.nHeight );
1237                             return std::make_pair( true, true );
1238                         }
1239                     }
1240                     else {
1241                         stats().onUpdateFailed();
1242                         return std::make_pair( false, false );
1243                     }
1244
1245                     // insert failed - slot has been changed by another thread
1246                     // retry updating
1247                     stats().onUpdateRetry();
1248                 }
1249             } // while
1250         }
1251         //@endcond
1252     };
1253 }} // namespace cds::intrusive
1254
1255 #endif // #ifndef CDSLIB_INTRUSIVE_IMPL_FELDMAN_HASHSET_H