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-2016
   5
   6     Source code repo: http://github.com/khizmax/libcds/
   7     Download: http://sourceforge.net/projects/libcds/files/
   8
   9     Redistribution and use in source and binary forms, with or without
  10     modification, are permitted provided that the following conditions are met:
  11
  12     * Redistributions of source code must retain the above copyright notice, this
  13       list of conditions and the following disclaimer.
  14
  15     * Redistributions in binary form must reproduce the above copyright notice,
  16       this list of conditions and the following disclaimer in the documentation
  17       and/or other materials provided with the distribution.
  18
  19     THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  20     AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  21     IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  22     DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
  23     FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  24     DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
  25     SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  26     CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  27     OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  28     OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  29 */
  30
  31 #ifndef CDSLIB_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     protected:
 149         //@cond
 150         typedef typename base_class::node_ptr node_ptr;
 151         typedef typename base_class::atomic_node_ptr atomic_node_ptr;
 152         typedef typename base_class::array_node array_node;
 153         typedef typename base_class::traverse_data traverse_data;
 154
 155         using base_class::to_array;
 156         using base_class::to_node;
 157         using base_class::stats;
 158         using base_class::head;
 159         using base_class::metrics;
 160         //@endcond
 161
 162     protected:
 163         //@cond
 164         class iterator_base
 165         {
 166             friend class FeldmanHashSet;
 167
 168         protected:
 169             array_node *        m_pNode;    ///< current array node
 170             size_t              m_idx;      ///< current position in m_pNode
 171             typename gc::Guard  m_guard;    ///< HP guard
 172             FeldmanHashSet const*  m_set;    ///< Hash set
 173
 174         public:
 175             iterator_base() CDS_NOEXCEPT
 176                 : m_pNode( nullptr )
 177                 , m_idx( 0 )
 178                 , m_set( nullptr )
 179             {}
 180
 181             iterator_base( iterator_base const& rhs ) CDS_NOEXCEPT
 182                 : m_pNode( rhs.m_pNode )
 183                 , m_idx( rhs.m_idx )
 184                 , m_set( rhs.m_set )
 185             {
 186                 m_guard.copy( rhs.m_guard );
 187             }
 188
 189             iterator_base& operator=(iterator_base const& rhs) CDS_NOEXCEPT
 190             {
 191                 m_pNode = rhs.m_pNode;
 192                 m_idx = rhs.m_idx;
 193                 m_set = rhs.m_set;
 194                 m_guard.copy( rhs.m_guard );
 195                 return *this;
 196             }
 197
 198             iterator_base& operator++()
 199             {
 200                 forward();
 201                 return *this;
 202             }
 203
 204             iterator_base& operator--()
 205             {
 206                 backward();
 207                 return *this;
 208             }
 209
 210             void release()
 211             {
 212                 m_guard.clear();
 213             }
 214
 215             bool operator ==(iterator_base const& rhs) const CDS_NOEXCEPT
 216             {
 217                 return m_pNode == rhs.m_pNode && m_idx == rhs.m_idx && m_set == rhs.m_set;
 218             }
 219
 220             bool operator !=(iterator_base const& rhs) const CDS_NOEXCEPT
 221             {
 222                 return !( *this == rhs );
 223             }
 224
 225         protected:
 226             iterator_base( FeldmanHashSet const& set, array_node * pNode, size_t idx, bool )
 227                 : m_pNode( pNode )
 228                 , m_idx( idx )
 229                 , m_set( &set )
 230             {}
 231
 232             iterator_base( FeldmanHashSet const& set, array_node * pNode, size_t idx )
 233                 : m_pNode( pNode )
 234                 , m_idx( idx )
 235                 , m_set( &set )
 236             {
 237                 forward();
 238             }
 239
 240             value_type * pointer() const CDS_NOEXCEPT
 241             {
 242                 return m_guard.template get<value_type>();
 243             }
 244
 245             void forward()
 246             {
 247                 assert( m_set != nullptr );
 248                 assert( m_pNode != nullptr );
 249
 250                 size_t const arrayNodeSize = m_set->array_node_size();
 251                 size_t const headSize = m_set->head_size();
 252                 array_node * pNode = m_pNode;
 253                 size_t idx = m_idx + 1;
 254                 size_t nodeSize = m_pNode->pParent? arrayNodeSize : headSize;
 255
 256                 for ( ;; ) {
 257                     if ( idx < nodeSize ) {
 258                         node_ptr slot = pNode->nodes[idx].load( memory_model::memory_order_acquire );
 259                         if ( slot.bits() == base_class::flag_array_node ) {
 260                             // array node, go down the tree
 261                             assert( slot.ptr() != nullptr );
 262                             pNode = to_array( slot.ptr());
 263                             idx = 0;
 264                             nodeSize = arrayNodeSize;
 265                         }
 266                         else if ( slot.bits() == base_class::flag_array_converting ) {
 267                             // the slot is converting to array node right now - skip the node
 268                             ++idx;
 269                         }
 270                         else {
 271                             if ( slot.ptr()) {
 272                                 // data node
 273                                 if ( m_guard.protect( pNode->nodes[idx], [](node_ptr p) -> value_type * { return p.ptr(); }) == slot ) {
 274                                     m_pNode = pNode;
 275                                     m_idx = idx;
 276                                     return;
 277                                 }
 278                             }
 279                             ++idx;
 280                         }
 281                     }
 282                     else {
 283                         // up to parent node
 284                         if ( pNode->pParent ) {
 285                             idx = pNode->idxParent + 1;
 286                             pNode = pNode->pParent;
 287                             nodeSize = pNode->pParent ? arrayNodeSize : headSize;
 288                         }
 289                         else {
 290                             // end()
 291                             assert( pNode == m_set->head());
 292                             assert( idx == headSize );
 293                             m_pNode = pNode;
 294                             m_idx = idx;
 295                             return;
 296                         }
 297                     }
 298                 }
 299             }
 300
 301             void backward()
 302             {
 303                 assert( m_set != nullptr );
 304                 assert( m_pNode != nullptr );
 305
 306                 size_t const arrayNodeSize = m_set->array_node_size();
 307                 size_t const headSize = m_set->head_size();
 308                 size_t const endIdx = size_t(0) - 1;
 309
 310                 array_node * pNode = m_pNode;
 311                 size_t idx = m_idx - 1;
 312                 size_t nodeSize = m_pNode->pParent? arrayNodeSize : headSize;
 313
 314                 for ( ;; ) {
 315                     if ( idx != endIdx ) {
 316                         node_ptr slot = pNode->nodes[idx].load( memory_model::memory_order_acquire );
 317                         if ( slot.bits() == base_class::flag_array_node ) {
 318                             // array node, go down the tree
 319                             assert( slot.ptr() != nullptr );
 320                             pNode = to_array( slot.ptr());
 321                             nodeSize = arrayNodeSize;
 322                             idx = nodeSize - 1;
 323                         }
 324                         else if ( slot.bits() == base_class::flag_array_converting ) {
 325                             // the slot is converting to array node right now - skip the node
 326                             --idx;
 327                         }
 328                         else {
 329                             if ( slot.ptr()) {
 330                                 // data node
 331                                 if ( m_guard.protect( pNode->nodes[idx], [](node_ptr p) -> value_type * { return p.ptr(); }) == slot ) {
 332                                     m_pNode = pNode;
 333                                     m_idx = idx;
 334                                     return;
 335                                 }
 336                             }
 337                             --idx;
 338                         }
 339                     }
 340                     else {
 341                         // up to parent node
 342                         if ( pNode->pParent ) {
 343                             idx = pNode->idxParent - 1;
 344                             pNode = pNode->pParent;
 345                             nodeSize = pNode->pParent ? arrayNodeSize : headSize;
 346                         }
 347                         else {
 348                             // rend()
 349                             assert( pNode == m_set->head());
 350                             assert( idx == endIdx );
 351                             m_pNode = pNode;
 352                             m_idx = idx;
 353                             return;
 354                         }
 355                     }
 356                 }
 357             }
 358         };
 359
 360         template <class Iterator>
 361         Iterator init_begin() const
 362         {
 363             return Iterator( *this, head(), size_t(0) - 1 );
 364         }
 365
 366         template <class Iterator>
 367         Iterator init_end() const
 368         {
 369             return Iterator( *this, head(), head_size(), false );
 370         }
 371
 372         template <class Iterator>
 373         Iterator init_rbegin() const
 374         {
 375             return Iterator( *this, head(), head_size());
 376         }
 377
 378         template <class Iterator>
 379         Iterator init_rend() const
 380         {
 381             return Iterator( *this, head(), size_t(0) - 1, false );
 382         }
 383
 384         /// Bidirectional iterator class
 385         template <bool IsConst>
 386         class bidirectional_iterator: protected iterator_base
 387         {
 388             friend class FeldmanHashSet;
 389
 390         protected:
 391             static CDS_CONSTEXPR bool const c_bConstantIterator = IsConst;
 392
 393         public:
 394             typedef typename std::conditional< IsConst, value_type const*, value_type*>::type value_ptr; ///< Value pointer
 395             typedef typename std::conditional< IsConst, value_type const&, value_type&>::type value_ref; ///< Value reference
 396
 397         public:
 398             bidirectional_iterator() CDS_NOEXCEPT
 399             {}
 400
 401             bidirectional_iterator( bidirectional_iterator const& rhs ) CDS_NOEXCEPT
 402                 : iterator_base( rhs )
 403             {}
 404
 405             bidirectional_iterator& operator=(bidirectional_iterator const& rhs) CDS_NOEXCEPT
 406             {
 407                 iterator_base::operator=( rhs );
 408                 return *this;
 409             }
 410
 411             bidirectional_iterator& operator++()
 412             {
 413                 iterator_base::operator++();
 414                 return *this;
 415             }
 416
 417             bidirectional_iterator& operator--()
 418             {
 419                 iterator_base::operator--();
 420                 return *this;
 421             }
 422
 423             value_ptr operator ->() const CDS_NOEXCEPT
 424             {
 425                 return iterator_base::pointer();
 426             }
 427
 428             value_ref operator *() const CDS_NOEXCEPT
 429             {
 430                 value_ptr p = iterator_base::pointer();
 431                 assert( p );
 432                 return *p;
 433             }
 434
 435             void release()
 436             {
 437                 iterator_base::release();
 438             }
 439
 440             template <bool IsConst2>
 441             bool operator ==(bidirectional_iterator<IsConst2> const& rhs) const CDS_NOEXCEPT
 442             {
 443                 return iterator_base::operator==( rhs );
 444             }
 445
 446             template <bool IsConst2>
 447             bool operator !=(bidirectional_iterator<IsConst2> const& rhs) const CDS_NOEXCEPT
 448             {
 449                 return !( *this == rhs );
 450             }
 451
 452         protected:
 453             bidirectional_iterator( FeldmanHashSet& set, array_node * pNode, size_t idx, bool )
 454                 : iterator_base( set, pNode, idx, false )
 455             {}
 456
 457             bidirectional_iterator( FeldmanHashSet& set, array_node * pNode, size_t idx )
 458                 : iterator_base( set, pNode, idx )
 459             {}
 460         };
 461
 462         /// Reverse bidirectional iterator
 463         template <bool IsConst>
 464         class reverse_bidirectional_iterator : public iterator_base
 465         {
 466             friend class FeldmanHashSet;
 467
 468         public:
 469             typedef typename std::conditional< IsConst, value_type const*, value_type*>::type value_ptr; ///< Value pointer
 470             typedef typename std::conditional< IsConst, value_type const&, value_type&>::type value_ref; ///< Value reference
 471
 472         public:
 473             reverse_bidirectional_iterator() CDS_NOEXCEPT
 474                 : iterator_base()
 475             {}
 476
 477             reverse_bidirectional_iterator( reverse_bidirectional_iterator const& rhs ) CDS_NOEXCEPT
 478                 : iterator_base( rhs )
 479             {}
 480
 481             reverse_bidirectional_iterator& operator=( reverse_bidirectional_iterator const& rhs) CDS_NOEXCEPT
 482             {
 483                 iterator_base::operator=( rhs );
 484                 return *this;
 485             }
 486
 487             reverse_bidirectional_iterator& operator++()
 488             {
 489                 iterator_base::operator--();
 490                 return *this;
 491             }
 492
 493             reverse_bidirectional_iterator& operator--()
 494             {
 495                 iterator_base::operator++();
 496                 return *this;
 497             }
 498
 499             value_ptr operator ->() const CDS_NOEXCEPT
 500             {
 501                 return iterator_base::pointer();
 502             }
 503
 504             value_ref operator *() const CDS_NOEXCEPT
 505             {
 506                 value_ptr p = iterator_base::pointer();
 507                 assert( p );
 508                 return *p;
 509             }
 510
 511             void release()
 512             {
 513                 iterator_base::release();
 514             }
 515
 516             template <bool IsConst2>
 517             bool operator ==(reverse_bidirectional_iterator<IsConst2> const& rhs) const
 518             {
 519                 return iterator_base::operator==( rhs );
 520             }
 521
 522             template <bool IsConst2>
 523             bool operator !=(reverse_bidirectional_iterator<IsConst2> const& rhs)
 524             {
 525                 return !( *this == rhs );
 526             }
 527
 528         private:
 529             reverse_bidirectional_iterator( FeldmanHashSet& set, array_node * pNode, size_t idx, bool )
 530                 : iterator_base( set, pNode, idx, false )
 531             {}
 532
 533             reverse_bidirectional_iterator( FeldmanHashSet& set, array_node * pNode, size_t idx )
 534                 : iterator_base( set, pNode, idx, false )
 535             {
 536                 iterator_base::backward();
 537             }
 538         };
 539         //@endcond
 540
 541     public:
 542 #ifdef CDS_DOXYGEN_INVOKED
 543         typedef implementation_defined iterator;            ///< @ref cds_intrusive_FeldmanHashSet_iterators "bidirectional iterator" type
 544         typedef implementation_defined const_iterator;      ///< @ref cds_intrusive_FeldmanHashSet_iterators "bidirectional const iterator" type
 545         typedef implementation_defined reverse_iterator;    ///< @ref cds_intrusive_FeldmanHashSet_iterators "bidirectional reverse iterator" type
 546         typedef implementation_defined const_reverse_iterator; ///< @ref cds_intrusive_FeldmanHashSet_iterators "bidirectional reverse const iterator" type
 547 #else
 548         typedef bidirectional_iterator<false>   iterator;
 549         typedef bidirectional_iterator<true>    const_iterator;
 550         typedef reverse_bidirectional_iterator<false>   reverse_iterator;
 551         typedef reverse_bidirectional_iterator<true>    const_reverse_iterator;
 552 #endif
 553
 554     private:
 555         //@cond
 556         item_counter      m_ItemCounter; ///< Item counter
 557         //@endcond
 558
 559     public:
 560         /// Creates empty set
 561         /**
 562             @param head_bits: 2<sup>head_bits</sup> specifies the size of head array, minimum is 4.
 563             @param array_bits: 2<sup>array_bits</sup> specifies the size of array node, minimum is 2.
 564
 565             Equation for \p head_bits and \p array_bits:
 566             \code
 567             sizeof(hash_type) * 8 == head_bits + N * array_bits
 568             \endcode
 569             where \p N is multi-level array depth.
 570         */
 571         FeldmanHashSet( size_t head_bits = 8, size_t array_bits = 4 )
 572             : base_class( head_bits, array_bits )
 573         {}
 574
 575         /// Destructs the set and frees all data
 576         ~FeldmanHashSet()
 577         {
 578             clear();
 579         }
 580
 581         /// Inserts new node
 582         /**
 583             The function inserts \p val in the set if it does not contain
 584             an item with that hash.
 585
 586             Returns \p true if \p val is placed into the set, \p false otherwise.
 587         */
 588         bool insert( value_type& val )
 589         {
 590             return insert( val, [](value_type&) {} );
 591         }
 592
 593         /// Inserts new node
 594         /**
 595             This function is intended for derived non-intrusive containers.
 596
 597             The function allows to split creating of new item into two part:
 598             - create item with key only
 599             - insert new item into the set
 600             - if inserting is success, calls \p f functor to initialize \p val.
 601
 602             The functor signature is:
 603             \code
 604                 void func( value_type& val );
 605             \endcode
 606             where \p val is the item inserted.
 607
 608             The user-defined functor is called only if the inserting is success.
 609
 610             @warning See \ref cds_intrusive_item_creating "insert item troubleshooting".
 611         */
 612         template <typename Func>
 613         bool insert( value_type& val, Func f )
 614         {
 615             hash_type const& hash = hash_accessor()(val);
 616             traverse_data pos( hash, *this );
 617             hash_comparator cmp;
 618             typename gc::template GuardArray<2> guards;
 619
 620             guards.assign( 1, &val );
 621             while ( true ) {
 622                 node_ptr slot = base_class::traverse( pos );
 623                 assert( slot.bits() == 0 );
 624
 625                 // protect data node by hazard pointer
 626                 if (guards.protect( 0, pos.pArr->nodes[pos.nSlot], [](node_ptr p) -> value_type * { return p.ptr(); }) != slot ) {
 627                     // slot value has been changed - retry
 628                     stats().onSlotChanged();
 629                 }
 630
 631                 if (slot.ptr()) {
 632                     if ( cmp( hash, hash_accessor()(*slot.ptr())) == 0 ) {
 633                         // the item with that hash value already exists
 634                         stats().onInsertFailed();
 635                         return false;
 636                     }
 637
 638                     // the slot must be expanded
 639                     base_class::expand_slot( pos, slot );
 640                 }
 641                 else {
 642                     // the slot is empty, try to insert data node
 643                     node_ptr pNull;
 644                     if ( pos.pArr->nodes[pos.nSlot].compare_exchange_strong( pNull, node_ptr(&val), memory_model::memory_order_release, atomics::memory_order_relaxed ))
 645                     {
 646                         // the new data node has been inserted
 647                         f(val);
 648                         ++m_ItemCounter;
 649                         stats().onInsertSuccess();
 650                         stats().height(pos.nHeight);
 651                         return true;
 652                     }
 653
 654                     // insert failed - slot has been changed by another thread
 655                     // retry inserting
 656                     stats().onInsertRetry();
 657                 }
 658             }
 659         }
 660
 661         /// Updates the node
 662         /**
 663             Performs inserting or updating the item with hash value equal to \p val.
 664             - If hash value is found then existing item is replaced with \p val, old item is disposed
 665               with \p Traits::disposer. Note that the disposer is called by \p GC asynchronously.
 666               The function returns <tt> std::pair<true, false> </tt>
 667             - If hash value is not found and \p bInsert is \p true then \p val is inserted,
 668               the function returns <tt> std::pair<true, true> </tt>
 669             - If hash value is not found and \p bInsert is \p false then the set is unchanged,
 670               the function returns <tt> std::pair<false, false> </tt>
 671
 672             Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successfull
 673             (i.e. the item has been inserted or updated),
 674             \p second is \p true if new item has been added or \p false if the set contains that hash.
 675         */
 676         std::pair<bool, bool> update( value_type& val, bool bInsert = true )
 677         {
 678             return do_update(val, [](value_type&, value_type *) {}, bInsert );
 679         }
 680
 681         /// Unlinks the item \p val from the set
 682         /**
 683             The function searches the item \p val in the set and unlink it
 684             if it is found and its address is equal to <tt>&val</tt>.
 685
 686             The function returns \p true if success and \p false otherwise.
 687         */
 688         bool unlink( value_type const& val )
 689         {
 690             typename gc::Guard guard;
 691             auto pred = [&val](value_type const& item) -> bool { return &item == &val; };
 692             value_type * p = do_erase( hash_accessor()( val ), guard, std::ref( pred ));
 693             return p != nullptr;
 694         }
 695
 696         /// Deletes the item from the set
 697         /**
 698             The function searches \p hash in the set,
 699             unlinks the item found, and returns \p true.
 700             If that item is not found the function returns \p false.
 701
 702             The \ref disposer specified in \p Traits is called by garbage collector \p GC asynchronously.
 703         */
 704         bool erase( hash_type const& hash )
 705         {
 706             return erase(hash, [](value_type const&) {} );
 707         }
 708
 709         /// Deletes the item from the set
 710         /**
 711             The function searches \p hash in the set,
 712             call \p f functor with item found, and unlinks it from the set.
 713             The \ref disposer specified in \p Traits is called
 714             by garbage collector \p GC asynchronously.
 715
 716             The \p Func interface is
 717             \code
 718             struct functor {
 719                 void operator()( value_type& item );
 720             };
 721             \endcode
 722
 723             If \p hash is not found the function returns \p false.
 724         */
 725         template <typename Func>
 726         bool erase( hash_type const& hash, Func f )
 727         {
 728             typename gc::Guard guard;
 729             value_type * p = do_erase( hash, guard, []( value_type const&) -> bool {return true; } );
 730
 731             // p is guarded by HP
 732             if ( p ) {
 733                 f( *p );
 734                 return true;
 735             }
 736             return false;
 737         }
 738
 739         /// Deletes the item pointed by iterator \p iter
 740         /**
 741             Returns \p true if the operation is successful, \p false otherwise.
 742
 743             The function does not invalidate the iterator, it remains valid and can be used for further traversing.
 744         */
 745         bool erase_at( iterator const& iter )
 746         {
 747             return do_erase_at( iter );
 748         }
 749         //@cond
 750         bool erase_at( reverse_iterator const& iter )
 751         {
 752             return do_erase_at( iter );
 753         }
 754         //@endcond
 755
 756         /// Extracts the item with specified \p hash
 757         /**
 758             The function searches \p hash in the set,
 759             unlinks it from the set, and returns an guarded pointer to the item extracted.
 760             If \p hash is not found the function returns an empty guarded pointer.
 761
 762             The \p disposer specified in \p Traits class' template parameter is called automatically
 763             by garbage collector \p GC when returned \ref guarded_ptr object to be destroyed or released.
 764             @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
 765
 766             Usage:
 767             \code
 768             typedef cds::intrusive::FeldmanHashSet< your_template_args > my_set;
 769             my_set theSet;
 770             // ...
 771             {
 772                 my_set::guarded_ptr gp( theSet.extract( 5 ));
 773                 if ( gp ) {
 774                     // Deal with gp
 775                     // ...
 776                 }
 777                 // Destructor of gp releases internal HP guard
 778             }
 779             \endcode
 780         */
 781         guarded_ptr extract( hash_type const& hash )
 782         {
 783             guarded_ptr gp;
 784             {
 785                 typename gc::Guard guard;
 786                 value_type * p = do_erase( hash, guard, []( value_type const&) -> bool {return true;} );
 787
 788                 // p is guarded by HP
 789                 if ( p )
 790                     gp.reset( p );
 791             }
 792             return gp;
 793         }
 794
 795         /// Finds an item by it's \p hash
 796         /**
 797             The function searches the item by \p hash and calls the functor \p f for item found.
 798             The interface of \p Func functor is:
 799             \code
 800             struct functor {
 801                 void operator()( value_type& item );
 802             };
 803             \endcode
 804             where \p item is the item found.
 805
 806             The functor may change non-key fields of \p item. Note that the functor is only guarantee
 807             that \p item cannot be disposed during the functor is executing.
 808             The functor does not serialize simultaneous access to the set's \p item. If such access is
 809             possible you must provide your own synchronization schema on item level to prevent unsafe item modifications.
 810
 811             The function returns \p true if \p hash is found, \p false otherwise.
 812         */
 813         template <typename Func>
 814         bool find( hash_type const& hash, Func f )
 815         {
 816             typename gc::Guard guard;
 817             value_type * p = search( hash, guard );
 818
 819             // p is guarded by HP
 820             if ( p ) {
 821                 f( *p );
 822                 return true;
 823             }
 824             return false;
 825         }
 826
 827         /// Checks whether the set contains \p hash
 828         /**
 829             The function searches the item by its \p hash
 830             and returns \p true if it is found, or \p false otherwise.
 831         */
 832         bool contains( hash_type const& hash )
 833         {
 834             return find( hash, [](value_type&) {} );
 835         }
 836
 837         /// Finds an item by it's \p hash and returns the item found
 838         /**
 839             The function searches the item by its \p hash
 840             and returns the guarded pointer to the item found.
 841             If \p hash is not found the function returns an empty \p guarded_ptr.
 842
 843             @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
 844
 845             Usage:
 846             \code
 847             typedef cds::intrusive::FeldmanHashSet< your_template_params >  my_set;
 848             my_set theSet;
 849             // ...
 850             {
 851                 my_set::guarded_ptr gp( theSet.get( 5 ));
 852                 if ( theSet.get( 5 )) {
 853                     // Deal with gp
 854                     //...
 855                 }
 856                 // Destructor of guarded_ptr releases internal HP guard
 857             }
 858             \endcode
 859         */
 860         guarded_ptr get( hash_type const& hash )
 861         {
 862             guarded_ptr gp;
 863             {
 864                 typename gc::Guard guard;
 865                 gp.reset( search( hash, guard ));
 866             }
 867             return gp;
 868         }
 869
 870         /// Clears the set (non-atomic)
 871         /**
 872             The function unlink all data node from the set.
 873             The function is not atomic but is thread-safe.
 874             After \p %clear() the set may not be empty because another threads may insert items.
 875
 876             For each item the \p disposer is called after unlinking.
 877         */
 878         void clear()
 879         {
 880             clear_array( head(), head_size());
 881         }
 882
 883         /// Checks if the set is empty
 884         /**
 885             Emptiness is checked by item counting: if item count is zero then the set is empty.
 886             Thus, the correct item counting feature is an important part of the set implementation.
 887         */
 888         bool empty() const
 889         {
 890             return size() == 0;
 891         }
 892
 893         /// Returns item count in the set
 894         size_t size() const
 895         {
 896             return m_ItemCounter;
 897         }
 898
 899         /// Returns const reference to internal statistics
 900         stat const& statistics() const
 901         {
 902             return stats();
 903         }
 904
 905         /// Returns the size of head node
 906         using base_class::head_size;
 907
 908         /// Returns the size of the array node
 909         using base_class::array_node_size;
 910
 911         /// Collects tree level statistics into \p stat
 912         /**
 913             The function traverses the set and collects statistics for each level of the tree
 914             into \p feldman_hashset::level_statistics struct. The element of \p stat[i]
 915             represents statistics for level \p i, level 0 is head array.
 916             The function is thread-safe and may be called in multi-threaded environment.
 917
 918             Result can be useful for estimating efficiency of hash functor you use.
 919         */
 920         void get_level_statistics(std::vector< feldman_hashset::level_statistics>& stat) const
 921         {
 922             base_class::get_level_statistics( stat );
 923         }
 924
 925     public:
 926     ///@name Thread-safe iterators
 927         /** @anchor cds_intrusive_FeldmanHashSet_iterators
 928             The set supports thread-safe iterators: you may iterate over the set in multi-threaded environment.
 929             It is guaranteed that the iterators will remain valid even if another thread deletes the node the iterator points to:
 930             Hazard Pointer embedded into the iterator object protects the node from physical reclamation.
 931
 932             @note Since the iterator object contains hazard pointer that is a thread-local resource,
 933             the iterator should not be passed to another thread.
 934
 935             Each iterator object supports the common interface:
 936             - dereference operators:
 937                 @code
 938                 value_type [const] * operator ->() noexcept
 939                 value_type [const] & operator *() noexcept
 940                 @endcode
 941             - pre-increment and pre-decrement. Post-operators is not supported
 942             - equality operators <tt>==</tt> and <tt>!=</tt>.
 943                 Iterators are equal iff they point to the same cell of the same array node.
 944                 Note that for two iterators \p it1 and \p it2, the conditon <tt> it1 == it2 </tt>
 945                 does not entail <tt> &(*it1) == &(*it2) </tt>: welcome to concurrent containers
 946             - helper member function \p release() that clears internal hazard pointer.
 947                 After \p release() the iterator points to \p nullptr but it still remain valid: further iterating is possible.
 948
 949             During iteration you may safely erase any item from the set;
 950             @ref erase_at() function call doesn't invalidate any iterator.
 951             If some iterator points to the item to be erased, that item is not deleted immediately
 952             but only after that iterator will be advanced forward or backward.
 953
 954             @note It is possible the item can be iterated more that once, for example, if an iterator points to the item
 955             in array node that is being splitted.
 956         */
 957     ///@{
 958
 959         /// Returns an iterator to the beginning of the set
 960         iterator begin()
 961         {
 962             return iterator( *this, head(), size_t(0) - 1 );
 963         }
 964
 965         /// Returns an const iterator to the beginning of the set
 966         const_iterator begin() const
 967         {
 968             return const_iterator( *this, head(), size_t(0) - 1 );
 969         }
 970
 971         /// Returns an const iterator to the beginning of the set
 972         const_iterator cbegin()
 973         {
 974             return const_iterator( *this, head(), size_t(0) - 1 );
 975         }
 976
 977         /// 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.
 978         iterator end()
 979         {
 980             return iterator( *this, head(), head_size(), false );
 981         }
 982
 983         /// 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.
 984         const_iterator end() const
 985         {
 986             return const_iterator( *this, head(), head_size(), false );
 987         }
 988
 989         /// 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.
 990         const_iterator cend()
 991         {
 992             return const_iterator( *this, head(), head_size(), false );
 993         }
 994
 995         /// Returns a reverse iterator to the first element of the reversed set
 996         reverse_iterator rbegin()
 997         {
 998             return reverse_iterator( *this, head(), head_size());
 999         }
1000
1001         /// Returns a const reverse iterator to the first element of the reversed set
1002         const_reverse_iterator rbegin() const
1003         {
1004             return const_reverse_iterator( *this, head(), head_size());
1005         }
1006
1007         /// Returns a const reverse iterator to the first element of the reversed set
1008         const_reverse_iterator crbegin()
1009         {
1010             return const_reverse_iterator( *this, head(), head_size());
1011         }
1012
1013         /// Returns a reverse iterator to the element following the last element of the reversed set
1014         /**
1015             It corresponds to the element preceding the first element of the non-reversed container.
1016             This element acts as a placeholder, attempting to access it results in undefined behavior.
1017         */
1018         reverse_iterator rend()
1019         {
1020             return reverse_iterator( *this, head(), size_t(0) - 1, false );
1021         }
1022
1023         /// Returns a const reverse iterator to the element following the last element of the reversed set
1024         /**
1025             It corresponds to the element preceding the first element of the non-reversed container.
1026             This element acts as a placeholder, attempting to access it results in undefined behavior.
1027         */
1028         const_reverse_iterator rend() const
1029         {
1030             return const_reverse_iterator( *this, head(), size_t(0) - 1, false );
1031         }
1032
1033         /// Returns a const reverse iterator to the element following the last element of the reversed set
1034         /**
1035             It corresponds to the element preceding the first element of the non-reversed container.
1036             This element acts as a placeholder, attempting to access it results in undefined behavior.
1037         */
1038         const_reverse_iterator crend()
1039         {
1040             return const_reverse_iterator( *this, head(), size_t(0) - 1, false );
1041         }
1042     ///@}
1043
1044     private:
1045         //@cond
1046         void clear_array( array_node * pArrNode, size_t nSize )
1047         {
1048             back_off bkoff;
1049
1050             for ( atomic_node_ptr * pArr = pArrNode->nodes, *pLast = pArr + nSize; pArr != pLast; ++pArr ) {
1051                 while ( true ) {
1052                     node_ptr slot = pArr->load( memory_model::memory_order_acquire );
1053                     if ( slot.bits() == base_class::flag_array_node ) {
1054                         // array node, go down the tree
1055                         assert( slot.ptr() != nullptr );
1056                         clear_array( to_array( slot.ptr()), array_node_size());
1057                         break;
1058                     }
1059                     else if ( slot.bits() == base_class::flag_array_converting ) {
1060                         // the slot is converting to array node right now
1061                         while ( (slot = pArr->load(memory_model::memory_order_acquire)).bits() == base_class::flag_array_converting ) {
1062                             bkoff();
1063                             stats().onSlotConverting();
1064                         }
1065                         bkoff.reset();
1066
1067                         assert( slot.ptr() != nullptr );
1068                         assert( slot.bits() == base_class::flag_array_node );
1069                         clear_array( to_array( slot.ptr()), array_node_size());
1070                         break;
1071                     }
1072                     else {
1073                         // data node
1074                         if ( pArr->compare_exchange_strong( slot, node_ptr(), memory_model::memory_order_acquire, atomics::memory_order_relaxed )) {
1075                             if ( slot.ptr()) {
1076                                 gc::template retire<disposer>( slot.ptr());
1077                                 --m_ItemCounter;
1078                                 stats().onEraseSuccess();
1079                             }
1080                             break;
1081                         }
1082                     }
1083                 }
1084             }
1085         }
1086         //@endcond
1087
1088     protected:
1089         //@cond
1090         value_type * search( hash_type const& hash, typename gc::Guard& guard )
1091         {
1092             traverse_data pos( hash, *this );
1093             hash_comparator cmp;
1094
1095             while (true) {
1096                 node_ptr slot = base_class::traverse( pos );
1097                 assert(slot.bits() == 0);
1098
1099                 // protect data node by hazard pointer
1100                 if (guard.protect( pos.pArr->nodes[pos.nSlot], [](node_ptr p) -> value_type * { return p.ptr(); }) != slot) {
1101                     // slot value has been changed - retry
1102                     stats().onSlotChanged();
1103                     continue;
1104                 }
1105                 else if (slot.ptr() && cmp(hash, hash_accessor()(*slot.ptr())) == 0) {
1106                     // item found
1107                     stats().onFindSuccess();
1108                     return slot.ptr();
1109                 }
1110                 stats().onFindFailed();
1111                 return nullptr;
1112             }
1113         }
1114
1115         template <typename Predicate>
1116         value_type * do_erase( hash_type const& hash, typename gc::Guard& guard, Predicate pred )
1117         {
1118             traverse_data pos( hash, *this );
1119             hash_comparator cmp;
1120             while (true) {
1121                 node_ptr slot = base_class::traverse( pos );
1122                 assert(slot.bits() == 0);
1123
1124                 // protect data node by hazard pointer
1125                 if (guard.protect( pos.pArr->nodes[pos.nSlot], [](node_ptr p) -> value_type * { return p.ptr(); }) != slot) {
1126                     // slot value has been changed - retry
1127                     stats().onSlotChanged();
1128                 }
1129                 else if (slot.ptr()) {
1130                     if ( cmp(hash, hash_accessor()(*slot.ptr())) == 0 && pred(*slot.ptr())) {
1131                         // item found - replace it with nullptr
1132                         if ( pos.pArr->nodes[pos.nSlot].compare_exchange_strong(slot, node_ptr(nullptr), memory_model::memory_order_acquire, atomics::memory_order_relaxed)) {
1133                             // slot is guarded by HP
1134                             gc::template retire<disposer>(slot.ptr());
1135                             --m_ItemCounter;
1136                             stats().onEraseSuccess();
1137
1138                             return slot.ptr();
1139                         }
1140                         stats().onEraseRetry();
1141                         continue;
1142                     }
1143                     stats().onEraseFailed();
1144                     return nullptr;
1145                 }
1146                 else {
1147                     // the slot is empty
1148                     stats().onEraseFailed();
1149                     return nullptr;
1150                 }
1151             }
1152         }
1153
1154         bool do_erase_at( iterator_base const& iter )
1155         {
1156             if ( iter.m_set != this )
1157                 return false;
1158             if ( iter.m_pNode == head()) {
1159                 if ( iter.m_idx >= head_size())
1160                     return false;
1161             }
1162             else if ( iter.m_idx >= array_node_size())
1163                 return false;
1164
1165             for (;;) {
1166                 node_ptr slot = iter.m_pNode->nodes[iter.m_idx].load( memory_model::memory_order_acquire );
1167                 if ( slot.bits() == 0 && slot.ptr() == iter.pointer()) {
1168                     if ( iter.m_pNode->nodes[iter.m_idx].compare_exchange_strong(slot, node_ptr(nullptr), memory_model::memory_order_acquire, atomics::memory_order_relaxed)) {
1169                         // the item is guarded by iterator, so we may retire it safely
1170                         gc::template retire<disposer>( slot.ptr());
1171                         --m_ItemCounter;
1172                         stats().onEraseSuccess();
1173                         return true;
1174                     }
1175                 }
1176                 else
1177                     return false;
1178             }
1179         }
1180
1181         template <typename Func>
1182         std::pair<bool, bool> do_update( value_type& val, Func f, bool bInsert = true )
1183         {
1184             hash_type const& hash = hash_accessor()( val );
1185             traverse_data pos( hash, *this );
1186             hash_comparator cmp;
1187             typename gc::template GuardArray<2> guards;
1188
1189             guards.assign( 1, &val );
1190             while (true) {
1191                 node_ptr slot = base_class::traverse( pos );
1192                 assert(slot.bits() == 0);
1193
1194                 // protect data node by hazard pointer
1195                 if ( guards.protect( 0, pos.pArr->nodes[pos.nSlot], [](node_ptr p) -> value_type * { return p.ptr(); }) != slot ) {
1196                     // slot value has been changed - retry
1197                     stats().onSlotChanged();
1198                 }
1199                 else if ( slot.ptr()) {
1200                     if ( cmp( hash, hash_accessor()(*slot.ptr())) == 0 ) {
1201                         // the item with that hash value already exists
1202                         // Replace it with val
1203                         if ( slot.ptr() == &val ) {
1204                             stats().onUpdateExisting();
1205                             return std::make_pair(true, false);
1206                         }
1207
1208                         if ( pos.pArr->nodes[pos.nSlot].compare_exchange_strong(slot, node_ptr(&val), memory_model::memory_order_release, atomics::memory_order_relaxed)) {
1209                             // slot can be disposed
1210                             f( val, slot.ptr());
1211                             gc::template retire<disposer>( slot.ptr());
1212                             stats().onUpdateExisting();
1213                             return std::make_pair(true, false);
1214                         }
1215
1216                         stats().onUpdateRetry();
1217                         continue;
1218                     }
1219
1220                     if ( bInsert ) {
1221                         // the slot must be expanded
1222                         base_class::expand_slot( pos, slot );
1223                     }
1224                     else {
1225                         stats().onUpdateFailed();
1226                         return std::make_pair(false, false);
1227                     }
1228                 }
1229                 else {
1230                     // the slot is empty, try to insert data node
1231                     if ( bInsert ) {
1232                         node_ptr pNull;
1233                         if ( pos.pArr->nodes[pos.nSlot].compare_exchange_strong(pNull, node_ptr(&val), memory_model::memory_order_release, atomics::memory_order_relaxed))
1234                         {
1235                             // the new data node has been inserted
1236                             f(val, nullptr);
1237                             ++m_ItemCounter;
1238                             stats().onUpdateNew();
1239                             stats().height( pos.nHeight );
1240                             return std::make_pair(true, true);
1241                         }
1242                     }
1243                     else {
1244                         stats().onUpdateFailed();
1245                         return std::make_pair(false, false);
1246                     }
1247
1248                     // insert failed - slot has been changed by another thread
1249                     // retry updating
1250                     stats().onUpdateRetry();
1251                 }
1252             } // while
1253         }
1254         //@endcond
1255     };
1256 }} // namespace cds::intrusive
1257
1258 #endif // #ifndef CDSLIB_INTRUSIVE_IMPL_FELDMAN_HASHSET_H