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