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