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