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