cds/intrusive/details/feldman_hashset_base.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_DETAILS_FELDMAN_HASHSET_BASE_H
  32 #define CDSLIB_INTRUSIVE_DETAILS_FELDMAN_HASHSET_BASE_H
  33
  34 #include <memory.h> // memcmp, memcpy
  35 #include <type_traits>
  36
  37 #include <cds/intrusive/details/base.h>
  38 #include <cds/opt/compare.h>
  39 #include <cds/algo/atomic.h>
  40 #include <cds/algo/split_bitstring.h>
  41 #include <cds/details/marked_ptr.h>
  42 #include <cds/urcu/options.h>
  43
  44 namespace cds { namespace intrusive {
  45
  46     /// FeldmanHashSet related definitions
  47     /** @ingroup cds_intrusive_helper
  48     */
  49     namespace feldman_hashset {
  50         /// Hash accessor option
  51         /**
  52             @copydetails traits::hash_accessor
  53         */
  54         template <typename Accessor>
  55         struct hash_accessor {
  56             //@cond
  57             template <typename Base> struct pack: public Base
  58             {
  59                 typedef Accessor hash_accessor;
  60             };
  61             //@endcond
  62         };
  63
  64         /// \p FeldmanHashSet internal statistics
  65         template <typename EventCounter = cds::atomicity::event_counter>
  66         struct stat {
  67             typedef EventCounter event_counter ; ///< Event counter type
  68
  69             event_counter   m_nInsertSuccess;   ///< Number of success \p insert() operations
  70             event_counter   m_nInsertFailed;    ///< Number of failed \p insert() operations
  71             event_counter   m_nInsertRetry;     ///< Number of attempts to insert new item
  72             event_counter   m_nUpdateNew;       ///< Number of new item inserted for \p update()
  73             event_counter   m_nUpdateExisting;  ///< Number of existing item updates
  74             event_counter   m_nUpdateFailed;    ///< Number of failed \p update() call
  75             event_counter   m_nUpdateRetry;     ///< Number of attempts to update the item
  76             event_counter   m_nEraseSuccess;    ///< Number of successful \p erase(), \p unlink(), \p extract() operations
  77             event_counter   m_nEraseFailed;     ///< Number of failed \p erase(), \p unlink(), \p extract() operations
  78             event_counter   m_nEraseRetry;      ///< Number of attempts to \p erase() an item
  79             event_counter   m_nFindSuccess;     ///< Number of successful \p find() and \p get() operations
  80             event_counter   m_nFindFailed;      ///< Number of failed \p find() and \p get() operations
  81
  82             event_counter   m_nExpandNodeSuccess; ///< Number of succeeded attempts converting data node to array node
  83             event_counter   m_nExpandNodeFailed;  ///< Number of failed attempts converting data node to array node
  84             event_counter   m_nSlotChanged;     ///< Number of array node slot changing by other thread during an operation
  85             event_counter   m_nSlotConverting;  ///< Number of events when we encounter a slot while it is converting to array node
  86
  87             event_counter   m_nArrayNodeCount;  ///< Number of array nodes
  88             event_counter   m_nHeight;          ///< Current height of the tree
  89
  90             //@cond
  91             void onInsertSuccess()              { ++m_nInsertSuccess;       }
  92             void onInsertFailed()               { ++m_nInsertFailed;        }
  93             void onInsertRetry()                { ++m_nInsertRetry;         }
  94             void onUpdateNew()                  { ++m_nUpdateNew;           }
  95             void onUpdateExisting()             { ++m_nUpdateExisting;      }
  96             void onUpdateFailed()               { ++m_nUpdateFailed;        }
  97             void onUpdateRetry()                { ++m_nUpdateRetry;         }
  98             void onEraseSuccess()               { ++m_nEraseSuccess;        }
  99             void onEraseFailed()                { ++m_nEraseFailed;         }
 100             void onEraseRetry()                 { ++m_nEraseRetry;          }
 101             void onFindSuccess()                { ++m_nFindSuccess;         }
 102             void onFindFailed()                 { ++m_nFindFailed;          }
 103
 104             void onExpandNodeSuccess()          { ++m_nExpandNodeSuccess;   }
 105             void onExpandNodeFailed()           { ++m_nExpandNodeFailed;    }
 106             void onSlotChanged()                { ++m_nSlotChanged;         }
 107             void onSlotConverting()             { ++m_nSlotConverting;      }
 108             void onArrayNodeCreated()           { ++m_nArrayNodeCount;      }
 109             void height( size_t h )             { if (m_nHeight < h ) m_nHeight = h; }
 110             //@endcond
 111         };
 112
 113         /// \p FeldmanHashSet empty internal statistics
 114         struct empty_stat {
 115             //@cond
 116             void onInsertSuccess()              const {}
 117             void onInsertFailed()               const {}
 118             void onInsertRetry()                const {}
 119             void onUpdateNew()                  const {}
 120             void onUpdateExisting()             const {}
 121             void onUpdateFailed()               const {}
 122             void onUpdateRetry()                const {}
 123             void onEraseSuccess()               const {}
 124             void onEraseFailed()                const {}
 125             void onEraseRetry()                 const {}
 126             void onFindSuccess()                const {}
 127             void onFindFailed()                 const {}
 128
 129             void onExpandNodeSuccess()          const {}
 130             void onExpandNodeFailed()           const {}
 131             void onSlotChanged()                const {}
 132             void onSlotConverting()             const {}
 133             void onArrayNodeCreated()           const {}
 134             void height(size_t)                 const {}
 135             //@endcond
 136         };
 137
 138         /// \p FeldmanHashSet traits
 139         struct traits
 140         {
 141             /// Mandatory functor to get hash value from data node
 142             /**
 143                 It is most-important feature of \p FeldmanHashSet.
 144                 That functor must return a reference to fixed-sized hash value of data node.
 145                 The return value of that functor specifies the type of hash value.
 146
 147                 Example:
 148                 \code
 149                 typedef uint8_t hash_type[32]; // 256-bit hash type
 150                 struct foo {
 151                     hash_type  hash; // 256-bit hash value
 152                     // ... other fields
 153                 };
 154
 155                 // Hash accessor
 156                 struct foo_hash_accessor {
 157                     hash_type const& operator()( foo const& d ) const
 158                     {
 159                         return d.hash;
 160                     }
 161                 };
 162                 \endcode
 163             */
 164             typedef cds::opt::none hash_accessor;
 165
 166             /// Disposer for removing data nodes
 167             typedef cds::intrusive::opt::v::empty_disposer disposer;
 168
 169             /// Hash comparing functor
 170             /**
 171                 No default functor is provided.
 172                 If the option is not specified, the \p less option is used.
 173             */
 174             typedef cds::opt::none compare;
 175
 176             /// Specifies binary predicate used for hash compare.
 177             /**
 178                 If \p %less and \p %compare are not specified, \p memcmp() -like @ref bitwise_compare "bit-wise hash comparator" is used
 179                 because the hash value is treated as fixed-sized bit-string.
 180             */
 181             typedef cds::opt::none less;
 182
 183             /// Item counter
 184             /**
 185                 The item counting is an important part of \p FeldmanHashSet algorithm:
 186                 the \p empty() member function depends on correct item counting.
 187                 Therefore, \p atomicity::empty_item_counter is not allowed as a type of the option.
 188
 189                 Default is \p atomicity::item_counter.
 190             */
 191             typedef cds::atomicity::item_counter item_counter;
 192
 193             /// Array node allocator
 194             /**
 195                 Allocator for array nodes. That allocator is used for creating \p headNode and \p arrayNode when the set grows.
 196                 Default is \ref CDS_DEFAULT_ALLOCATOR
 197             */
 198             typedef CDS_DEFAULT_ALLOCATOR node_allocator;
 199
 200             /// C++ memory ordering model
 201             /**
 202                 Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
 203                 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
 204             */
 205             typedef cds::opt::v::relaxed_ordering memory_model;
 206
 207             /// Back-off strategy
 208             typedef cds::backoff::Default back_off;
 209
 210             /// Internal statistics
 211             /**
 212                 By default, internal statistics is disabled (\p feldman_hashset::empty_stat).
 213                 Use \p feldman_hashset::stat to enable it.
 214             */
 215             typedef empty_stat stat;
 216
 217             /// RCU deadlock checking policy (only for \ref cds_intrusive_FeldmanHashSet_rcu "RCU-based FeldmanHashSet")
 218             /**
 219                 List of available policy see \p opt::rcu_check_deadlock
 220             */
 221             typedef cds::opt::v::rcu_throw_deadlock rcu_check_deadlock;
 222         };
 223
 224         /// Metafunction converting option list to \p feldman_hashset::traits
 225         /**
 226             Supported \p Options are:
 227             - \p feldman_hashset::hash_accessor - mandatory option, hash accessor functor.
 228                 @copydetails traits::hash_accessor
 229             - \p opt::node_allocator - array node allocator.
 230                 @copydetails traits::node_allocator
 231             - \p opt::compare - hash comparison functor. No default functor is provided.
 232                 If the option is not specified, the \p opt::less is used.
 233             - \p opt::less - specifies binary predicate used for hash comparison.
 234                 If the option is not specified, \p memcmp() -like bit-wise hash comparator is used
 235                 because the hash value is treated as fixed-sized bit-string.
 236             - \p opt::back_off - back-off strategy used. If the option is not specified, the \p cds::backoff::Default is used.
 237             - \p opt::disposer - the functor used for disposing removed data node. Default is \p opt::v::empty_disposer. Due the nature
 238                 of GC schema the disposer may be called asynchronously.
 239             - \p opt::item_counter - the type of item counting feature.
 240                  The item counting is an important part of \p FeldmanHashSet algorithm:
 241                  the \p empty() member function depends on correct item counting.
 242                  Therefore, \p atomicity::empty_item_counter is not allowed as a type of the option.
 243                  Default is \p atomicity::item_counter.
 244             - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
 245                 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
 246             - \p opt::stat - internal statistics. By default, it is disabled (\p feldman_hashset::empty_stat).
 247                 To enable it use \p feldman_hashset::stat
 248             - \p opt::rcu_check_deadlock - a deadlock checking policy for \ref cds_intrusive_FeldmanHashSet_rcu "RCU-based FeldmanHashSet"
 249                 Default is \p opt::v::rcu_throw_deadlock
 250         */
 251         template <typename... Options>
 252         struct make_traits
 253         {
 254 #   ifdef CDS_DOXYGEN_INVOKED
 255             typedef implementation_defined type ;   ///< Metafunction result
 256 #   else
 257             typedef typename cds::opt::make_options<
 258                 typename cds::opt::find_type_traits< traits, Options... >::type
 259                 ,Options...
 260             >::type   type;
 261 #   endif
 262         };
 263
 264         /// Bit-wise memcmp-based comparator for hash value \p T
 265         template <typename T>
 266         struct bitwise_compare
 267         {
 268             /// Compares \p lhs and \p rhs
 269             /**
 270                 Returns:
 271                 - <tt> < 0</tt> if <tt>lhs < rhs</tt>
 272                 - <tt>0</tt> if <tt>lhs == rhs</tt>
 273                 - <tt> > 0</tt> if <tt>lhs > rhs</tt>
 274             */
 275             int operator()( T const& lhs, T const& rhs ) const
 276             {
 277                 return memcmp( &lhs, &rhs, sizeof(T));
 278             }
 279         };
 280
 281         /// One-level statistics, see \p FeldmanHashSet::get_level_statistics
 282         struct level_statistics
 283         {
 284             size_t array_node_count;    ///< Count of array node at the level
 285             size_t node_capacity;       ///< Array capacity
 286
 287             size_t data_cell_count;     ///< The number of data cells in all array node at this level
 288             size_t array_cell_count;    ///< The number of array cells in all array node at this level
 289             size_t empty_cell_count;    ///< The number of empty cells in all array node at this level
 290
 291             //@cond
 292             level_statistics()
 293                 : array_node_count(0)
 294                 , data_cell_count(0)
 295                 , array_cell_count(0)
 296                 , empty_cell_count(0)
 297             {}
 298             //@endcond
 299         };
 300
 301         //@cond
 302         namespace details {
 303             template <typename HashType >
 304             using hash_splitter = cds::algo::split_bitstring< HashType >;
 305
 306             struct metrics {
 307                 size_t  head_node_size;     // power-of-two
 308                 size_t  head_node_size_log; // log2( head_node_size )
 309                 size_t  array_node_size;    // power-of-two
 310                 size_t  array_node_size_log;// log2( array_node_size )
 311
 312                 static metrics make(size_t head_bits, size_t array_bits, size_t hash_size )
 313                 {
 314                     size_t const hash_bits = hash_size * 8;
 315
 316                     if (array_bits < 2)
 317                         array_bits = 2;
 318                     if (head_bits < 4)
 319                         head_bits = 4;
 320                     if (head_bits > hash_bits)
 321                         head_bits = hash_bits;
 322                     if ((hash_bits - head_bits) % array_bits != 0)
 323                         head_bits += (hash_bits - head_bits) % array_bits;
 324
 325                     assert((hash_bits - head_bits) % array_bits == 0);
 326
 327                     metrics m;
 328                     m.head_node_size_log = head_bits;
 329                     m.head_node_size = size_t(1) << head_bits;
 330                     m.array_node_size_log = array_bits;
 331                     m.array_node_size = size_t(1) << array_bits;
 332                     return m;
 333                 }
 334             };
 335
 336         } // namespace details
 337         //@endcond
 338
 339         //@cond
 340         template <typename T, typename Traits>
 341         class multilevel_array
 342         {
 343         public:
 344             typedef T value_type;
 345             typedef Traits traits;
 346             typedef typename Traits::node_allocator node_allocator;
 347             typedef typename traits::memory_model   memory_model;
 348             typedef typename traits::back_off       back_off;       ///< Backoff strategy
 349             typedef typename traits::stat           stat;           ///< Internal statistics type
 350
 351             typedef typename traits::hash_accessor hash_accessor;
 352             static_assert(!std::is_same< hash_accessor, cds::opt::none >::value, "hash_accessor functor must be specified");
 353
 354             /// Hash type deduced from \p hash_accessor return type
 355             typedef typename std::decay<
 356                 typename std::remove_reference<
 357                     decltype(hash_accessor()(std::declval<value_type>()))
 358                 >::type
 359             >::type hash_type;
 360             static_assert(!std::is_pointer<hash_type>::value, "hash_accessor should return a reference to hash value");
 361
 362             typedef typename cds::opt::details::make_comparator_from<
 363                 hash_type,
 364                 traits,
 365                 feldman_hashset::bitwise_compare< hash_type >
 366             >::type hash_comparator;
 367
 368             typedef feldman_hashset::details::hash_splitter< hash_type > hash_splitter;
 369
 370             enum node_flags {
 371                 flag_array_converting = 1,   ///< the cell is converting from data node to an array node
 372                 flag_array_node = 2          ///< the cell is a pointer to an array node
 373             };
 374
 375         protected:
 376
 377             typedef cds::details::marked_ptr< value_type, 3 > node_ptr;
 378             typedef atomics::atomic< node_ptr > atomic_node_ptr;
 379
 380             struct array_node {
 381                 array_node * const  pParent;    ///< parent array node
 382                 size_t const        idxParent;  ///< index in parent array node
 383                 atomic_node_ptr     nodes[1];   ///< node array
 384
 385                 array_node(array_node * parent, size_t idx)
 386                     : pParent(parent)
 387                     , idxParent(idx)
 388                 {}
 389
 390                 array_node() = delete;
 391                 array_node(array_node const&) = delete;
 392                 array_node(array_node&&) = delete;
 393             };
 394
 395             typedef cds::details::Allocator< array_node, node_allocator > cxx_array_node_allocator;
 396
 397             struct traverse_data {
 398                 hash_splitter splitter;
 399                 array_node * pArr;
 400                 size_t nSlot;
 401                 size_t nHeight;
 402
 403                 traverse_data( hash_type const& hash, multilevel_array& arr )
 404                     : splitter( hash )
 405                 {
 406                     reset( arr );
 407                 }
 408
 409                 void reset( multilevel_array& arr )
 410                 {
 411                     splitter.reset();
 412                     pArr = arr.head();
 413                     nSlot = splitter.cut( arr.metrics().head_node_size_log );
 414                     nHeight = 1;
 415                 }
 416             };
 417
 418         protected:
 419             feldman_hashset::details::metrics const m_Metrics;
 420             array_node *      m_Head;
 421             mutable stat      m_Stat;
 422
 423         public:
 424             multilevel_array(size_t head_bits, size_t array_bits )
 425                 : m_Metrics(feldman_hashset::details::metrics::make(head_bits, array_bits, sizeof(hash_type)))
 426                 , m_Head( alloc_head_node())
 427             {}
 428
 429             ~multilevel_array()
 430             {
 431                 destroy_tree();
 432                 free_array_node(m_Head);
 433             }
 434
 435             node_ptr traverse(traverse_data& pos)
 436             {
 437                 back_off bkoff;
 438                 while (true) {
 439                     node_ptr slot = pos.pArr->nodes[pos.nSlot].load(memory_model::memory_order_acquire);
 440                     if (slot.bits() == flag_array_node) {
 441                         // array node, go down the tree
 442                         assert(slot.ptr() != nullptr);
 443                         assert( !pos.splitter.eos());
 444                         pos.nSlot = pos.splitter.cut( metrics().array_node_size_log );
 445                         assert( pos.nSlot < metrics().array_node_size );
 446                         pos.pArr = to_array(slot.ptr());
 447                         ++pos.nHeight;
 448                     }
 449                     else if (slot.bits() == flag_array_converting) {
 450                         // the slot is converting to array node right now
 451                         bkoff();
 452                         stats().onSlotConverting();
 453                     }
 454                     else {
 455                         // data node
 456                         assert(slot.bits() == 0);
 457                         return slot;
 458                     }
 459                 } // while
 460             }
 461
 462             size_t head_size() const
 463             {
 464                 return m_Metrics.head_node_size;
 465             }
 466
 467             size_t array_node_size() const
 468             {
 469                 return m_Metrics.array_node_size;
 470             }
 471
 472             void get_level_statistics(std::vector< feldman_hashset::level_statistics>& stat) const
 473             {
 474                 stat.clear();
 475                 gather_level_statistics(stat, 0, m_Head, head_size());
 476             }
 477
 478         protected:
 479             array_node * head() const
 480             {
 481                 return m_Head;
 482             }
 483
 484             stat& stats() const
 485             {
 486                 return m_Stat;
 487             }
 488
 489             feldman_hashset::details::metrics const& metrics() const
 490             {
 491                 return m_Metrics;
 492             }
 493
 494             void destroy_tree()
 495             {
 496                 // The function is not thread-safe. For use in dtor only
 497                 // Destroy all array nodes
 498                 destroy_array_nodes(m_Head, head_size());
 499             }
 500
 501             void destroy_array_nodes(array_node * pArr, size_t nSize)
 502             {
 503                 for (atomic_node_ptr * p = pArr->nodes, *pLast = p + nSize; p != pLast; ++p) {
 504                     node_ptr slot = p->load(memory_model::memory_order_relaxed);
 505                     if (slot.bits() == flag_array_node) {
 506                         destroy_array_nodes(to_array(slot.ptr()), array_node_size());
 507                         free_array_node(to_array(slot.ptr()));
 508                         p->store(node_ptr(), memory_model::memory_order_relaxed);
 509                     }
 510                 }
 511             }
 512
 513             static array_node * alloc_array_node(size_t nSize, array_node * pParent, size_t idxParent)
 514             {
 515                 array_node * pNode = cxx_array_node_allocator().NewBlock(sizeof(array_node) + sizeof(atomic_node_ptr) * (nSize - 1), pParent, idxParent);
 516                 new (pNode->nodes) atomic_node_ptr[nSize];
 517                 return pNode;
 518             }
 519
 520             array_node * alloc_head_node() const
 521             {
 522                 return alloc_array_node(head_size(), nullptr, 0);
 523             }
 524
 525             array_node * alloc_array_node(array_node * pParent, size_t idxParent) const
 526             {
 527                 return alloc_array_node(array_node_size(), pParent, idxParent);
 528             }
 529
 530             static void free_array_node(array_node * parr)
 531             {
 532                 cxx_array_node_allocator().Delete(parr);
 533             }
 534
 535             union converter {
 536                 value_type * pData;
 537                 array_node * pArr;
 538
 539                 converter(value_type * p)
 540                     : pData(p)
 541                 {}
 542
 543                 converter(array_node * p)
 544                     : pArr(p)
 545                 {}
 546             };
 547
 548             static array_node * to_array(value_type * p)
 549             {
 550                 return converter(p).pArr;
 551             }
 552             static value_type * to_node(array_node * p)
 553             {
 554                 return converter(p).pData;
 555             }
 556
 557             void gather_level_statistics(std::vector<feldman_hashset::level_statistics>& stat, size_t nLevel, array_node * pArr, size_t nSize) const
 558             {
 559                 if (stat.size() <= nLevel) {
 560                     stat.resize(nLevel + 1);
 561                     stat[nLevel].node_capacity = nSize;
 562                 }
 563
 564                 ++stat[nLevel].array_node_count;
 565                 for (atomic_node_ptr * p = pArr->nodes, *pLast = p + nSize; p != pLast; ++p) {
 566                     node_ptr slot = p->load(memory_model::memory_order_relaxed);
 567                     if (slot.bits()) {
 568                         ++stat[nLevel].array_cell_count;
 569                         if (slot.bits() == flag_array_node)
 570                             gather_level_statistics(stat, nLevel + 1, to_array(slot.ptr()), array_node_size());
 571                     }
 572                     else if (slot.ptr())
 573                         ++stat[nLevel].data_cell_count;
 574                     else
 575                         ++stat[nLevel].empty_cell_count;
 576                 }
 577             }
 578
 579             bool expand_slot( traverse_data& pos, node_ptr current)
 580             {
 581                 return expand_slot( pos.pArr, pos.nSlot, current, pos.splitter.bit_offset());
 582             }
 583
 584         private:
 585             bool expand_slot(array_node * pParent, size_t idxParent, node_ptr current, size_t nOffset)
 586             {
 587                 assert(current.bits() == 0);
 588                 assert(current.ptr());
 589
 590                 array_node * pArr = alloc_array_node(pParent, idxParent);
 591
 592                 node_ptr cur(current.ptr());
 593                 atomic_node_ptr& slot = pParent->nodes[idxParent];
 594                 if (!slot.compare_exchange_strong(cur, cur | flag_array_converting, memory_model::memory_order_release, atomics::memory_order_relaxed))
 595                 {
 596                     stats().onExpandNodeFailed();
 597                     free_array_node(pArr);
 598                     return false;
 599                 }
 600
 601                 size_t idx = hash_splitter( hash_accessor()(*current.ptr()), nOffset ).cut( m_Metrics.array_node_size_log );
 602                 pArr->nodes[idx].store(current, memory_model::memory_order_release);
 603
 604                 cur = cur | flag_array_converting;
 605                 CDS_VERIFY(
 606                     slot.compare_exchange_strong(cur, node_ptr(to_node(pArr), flag_array_node), memory_model::memory_order_release, atomics::memory_order_relaxed)
 607                     );
 608
 609                 stats().onExpandNodeSuccess();
 610                 stats().onArrayNodeCreated();
 611                 return true;
 612             }
 613         };
 614         //@endcond
 615     } // namespace feldman_hashset
 616
 617     //@cond
 618     // Forward declaration
 619     template < class GC, typename T, class Traits = feldman_hashset::traits >
 620     class FeldmanHashSet;
 621     //@endcond
 622
 623 }} // namespace cds::intrusive
 624
 625 #endif // #ifndef CDSLIB_INTRUSIVE_DETAILS_FELDMAN_HASHSET_BASE_H