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::split_bitstring< HashType, HashSize > is used
 219             */
 220             typedef cds::opt::none hash_splitter;
 221
 222             /// Disposer for removing data nodes
 223             typedef cds::intrusive::opt::v::empty_disposer disposer;
 224
 225             /// Hash comparing functor
 226             /**
 227                 No default functor is provided.
 228                 If the option is not specified, the \p less option is used.
 229             */
 230             typedef cds::opt::none compare;
 231
 232             /// Specifies binary predicate used for hash compare.
 233             /**
 234                 If \p %less and \p %compare are not specified, \p memcmp() -like @ref bitwise_compare "bit-wise hash comparator" is used
 235                 because the hash value is treated as fixed-sized bit-string.
 236             */
 237             typedef cds::opt::none less;
 238
 239             /// Item counter
 240             /**
 241                 The item counting is an important part of \p FeldmanHashSet algorithm:
 242                 the \p empty() member function depends on correct item counting.
 243                 Therefore, \p atomicity::empty_item_counter is not allowed as a type of the option.
 244
 245                 Default is \p atomicity::item_counter.
 246             */
 247             typedef cds::atomicity::item_counter item_counter;
 248
 249             /// Array node allocator
 250             /**
 251                 Allocator for array nodes. The allocator is used for creating \p headNode and \p arrayNode when the set grows.
 252                 Default is \ref CDS_DEFAULT_ALLOCATOR
 253             */
 254             typedef CDS_DEFAULT_ALLOCATOR node_allocator;
 255
 256             /// C++ memory ordering model
 257             /**
 258                 Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
 259                 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
 260             */
 261             typedef cds::opt::v::relaxed_ordering memory_model;
 262
 263             /// Back-off strategy
 264             typedef cds::backoff::Default back_off;
 265
 266             /// Internal statistics
 267             /**
 268                 By default, internal statistics is disabled (\p feldman_hashset::empty_stat).
 269                 Use \p feldman_hashset::stat to enable it.
 270             */
 271             typedef empty_stat stat;
 272
 273             /// RCU deadlock checking policy (only for \ref cds_intrusive_FeldmanHashSet_rcu "RCU-based FeldmanHashSet")
 274             /**
 275                 List of available policy see \p opt::rcu_check_deadlock
 276             */
 277             typedef cds::opt::v::rcu_throw_deadlock rcu_check_deadlock;
 278         };
 279
 280         /// Metafunction converting option list to \p feldman_hashset::traits
 281         /**
 282             Supported \p Options are:
 283             - \p feldman_hashset::hash_accessor - mandatory option, hash accessor functor.
 284                 @copydetails traits::hash_accessor
 285             - \p feldman_hashset::hash_size - the size of hash value in bytes.
 286                 @copydetails traits::hash_size
 287             - \p feldman_hashset::hash_splitter - a hash splitter algorithm
 288                 @copydetails traits::hash_splitter
 289             - \p opt::node_allocator - array node allocator.
 290                 @copydetails traits::node_allocator
 291             - \p opt::compare - hash comparison functor. No default functor is provided.
 292                 If the option is not specified, the \p opt::less is used.
 293             - \p opt::less - specifies binary predicate used for hash comparison.
 294                 If the option is not specified, \p memcmp() -like bit-wise hash comparator is used
 295                 because the hash value is treated as fixed-sized bit-string.
 296             - \p opt::back_off - back-off strategy used. If the option is not specified, the \p cds::backoff::Default is used.
 297             - \p opt::disposer - the functor used for disposing removed data node. Default is \p opt::v::empty_disposer. Due the nature
 298                 of GC schema the disposer may be called asynchronously.
 299             - \p opt::item_counter - the type of item counting feature.
 300                  The item counting is an important part of \p FeldmanHashSet algorithm:
 301                  the \p empty() member function depends on correct item counting.
 302                  Therefore, \p atomicity::empty_item_counter is not allowed as a type of the option.
 303                  Default is \p atomicity::item_counter.
 304             - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
 305                 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
 306             - \p opt::stat - internal statistics. By default, it is disabled (\p feldman_hashset::empty_stat).
 307                 To enable it use \p feldman_hashset::stat
 308             - \p opt::rcu_check_deadlock - a deadlock checking policy for \ref cds_intrusive_FeldmanHashSet_rcu "RCU-based FeldmanHashSet"
 309                 Default is \p opt::v::rcu_throw_deadlock
 310         */
 311         template <typename... Options>
 312         struct make_traits
 313         {
 314 #   ifdef CDS_DOXYGEN_INVOKED
 315             typedef implementation_defined type ;   ///< Metafunction result
 316 #   else
 317             typedef typename cds::opt::make_options<
 318                 typename cds::opt::find_type_traits< traits, Options... >::type
 319                 ,Options...
 320             >::type   type;
 321 #   endif
 322         };
 323
 324         /// Bit-wise memcmp-based comparator for hash value \p T
 325         template <typename T>
 326         struct bitwise_compare
 327         {
 328             /// Compares \p lhs and \p rhs
 329             /**
 330                 Returns:
 331                 - <tt> < 0</tt> if <tt>lhs < rhs</tt>
 332                 - <tt>0</tt> if <tt>lhs == rhs</tt>
 333                 - <tt> > 0</tt> if <tt>lhs > rhs</tt>
 334             */
 335             int operator()( T const& lhs, T const& rhs ) const
 336             {
 337                 return memcmp( &lhs, &rhs, sizeof(T));
 338             }
 339         };
 340
 341         /// One-level statistics, see \p FeldmanHashSet::get_level_statistics
 342         struct level_statistics
 343         {
 344             size_t array_node_count;    ///< Count of array node at the level
 345             size_t node_capacity;       ///< Array capacity
 346
 347             size_t data_cell_count;     ///< The number of data cells in all array node at this level
 348             size_t array_cell_count;    ///< The number of array cells in all array node at this level
 349             size_t empty_cell_count;    ///< The number of empty cells in all array node at this level
 350
 351             //@cond
 352             level_statistics()
 353                 : array_node_count(0)
 354                 , data_cell_count(0)
 355                 , array_cell_count(0)
 356                 , empty_cell_count(0)
 357             {}
 358             //@endcond
 359         };
 360
 361         //@cond
 362         namespace details {
 363             template <typename HashType, size_t HashSize >
 364             using hash_splitter = cds::algo::split_bitstring< HashType, HashSize >;
 365
 366             struct metrics {
 367                 size_t  head_node_size;     // power-of-two
 368                 size_t  head_node_size_log; // log2( head_node_size )
 369                 size_t  array_node_size;    // power-of-two
 370                 size_t  array_node_size_log;// log2( array_node_size )
 371
 372                 static metrics make(size_t head_bits, size_t array_bits, size_t hash_size )
 373                 {
 374                     size_t const hash_bits = hash_size * 8;
 375
 376                     if (array_bits < 2)
 377                         array_bits = 2;
 378                     if (head_bits < 4)
 379                         head_bits = 4;
 380                     if (head_bits > hash_bits)
 381                         head_bits = hash_bits;
 382                     if ((hash_bits - head_bits) % array_bits != 0)
 383                         head_bits += (hash_bits - head_bits) % array_bits;
 384
 385                     assert((hash_bits - head_bits) % array_bits == 0);
 386
 387                     metrics m;
 388                     m.head_node_size_log = head_bits;
 389                     m.head_node_size = size_t(1) << head_bits;
 390                     m.array_node_size_log = array_bits;
 391                     m.array_node_size = size_t(1) << array_bits;
 392                     return m;
 393                 }
 394             };
 395
 396         } // namespace details
 397         //@endcond
 398
 399         //@cond
 400         template <typename T, typename Traits>
 401         class multilevel_array
 402         {
 403         public:
 404             typedef T value_type;
 405             typedef Traits traits;
 406             typedef typename Traits::node_allocator node_allocator;
 407             typedef typename traits::memory_model   memory_model;
 408             typedef typename traits::back_off       back_off;       ///< Backoff strategy
 409             typedef typename traits::stat           stat;           ///< Internal statistics type
 410
 411             typedef typename traits::hash_accessor hash_accessor;
 412             static_assert(!std::is_same< hash_accessor, cds::opt::none >::value, "hash_accessor functor must be specified");
 413
 414             /// Hash type deduced from \p hash_accessor return type
 415             typedef typename std::decay<
 416                 typename std::remove_reference<
 417                     decltype(hash_accessor()(std::declval<value_type>()))
 418                 >::type
 419             >::type hash_type;
 420             static_assert(!std::is_pointer<hash_type>::value, "hash_accessor should return a reference to hash value");
 421
 422             typedef typename cds::opt::details::make_comparator_from<
 423                 hash_type,
 424                 traits,
 425                 feldman_hashset::bitwise_compare< hash_type >
 426             >::type hash_comparator;
 427
 428             /// The size of hash_type in bytes, see \p traits::hash_size for explanation
 429             static CDS_CONSTEXPR size_t const c_hash_size = traits::hash_size == 0 ? sizeof( hash_type ) : static_cast<size_t>( traits::hash_size );
 430
 431             typedef typename std::conditional<
 432                 std::is_same< typename traits::hash_splitter, cds::opt::none >::value,
 433                 feldman_hashset::details::hash_splitter< hash_type, c_hash_size >,
 434                 typename traits::hash_splitter
 435             >::type hash_splitter;
 436
 437             enum node_flags {
 438                 flag_array_converting = 1,   ///< the cell is converting from data node to an array node
 439                 flag_array_node = 2          ///< the cell is a pointer to an array node
 440             };
 441
 442         protected:
 443
 444             typedef cds::details::marked_ptr< value_type, 3 > node_ptr;
 445             typedef atomics::atomic< node_ptr > atomic_node_ptr;
 446
 447             struct array_node {
 448                 array_node * const  pParent;    ///< parent array node
 449                 size_t const        idxParent;  ///< index in parent array node
 450                 atomic_node_ptr     nodes[1];   ///< node array
 451
 452                 array_node(array_node * parent, size_t idx)
 453                     : pParent(parent)
 454                     , idxParent(idx)
 455                 {}
 456
 457                 array_node() = delete;
 458                 array_node(array_node const&) = delete;
 459                 array_node(array_node&&) = delete;
 460             };
 461
 462             typedef cds::details::Allocator< array_node, node_allocator > cxx_array_node_allocator;
 463
 464             struct traverse_data {
 465                 hash_splitter splitter;
 466                 array_node * pArr;
 467                 size_t nSlot;
 468                 size_t nHeight;
 469
 470                 traverse_data( hash_type const& hash, multilevel_array& arr )
 471                     : splitter( hash )
 472                 {
 473                     reset( arr );
 474                 }
 475
 476                 void reset( multilevel_array& arr )
 477                 {
 478                     splitter.reset();
 479                     pArr = arr.head();
 480                     nSlot = splitter.cut( arr.metrics().head_node_size_log );
 481                     nHeight = 1;
 482                 }
 483             };
 484
 485         protected:
 486             feldman_hashset::details::metrics const m_Metrics;
 487             array_node *      m_Head;
 488             mutable stat      m_Stat;
 489
 490         public:
 491             multilevel_array(size_t head_bits, size_t array_bits )
 492                 : m_Metrics(feldman_hashset::details::metrics::make( head_bits, array_bits, c_hash_size ))
 493                 , m_Head( alloc_head_node())
 494             {}
 495
 496             ~multilevel_array()
 497             {
 498                 destroy_tree();
 499                 free_array_node( m_Head, head_size());
 500             }
 501
 502             node_ptr traverse(traverse_data& pos)
 503             {
 504                 back_off bkoff;
 505                 while (true) {
 506                     node_ptr slot = pos.pArr->nodes[pos.nSlot].load(memory_model::memory_order_acquire);
 507                     if (slot.bits() == flag_array_node) {
 508                         // array node, go down the tree
 509                         assert(slot.ptr() != nullptr);
 510                         assert( !pos.splitter.eos());
 511                         pos.nSlot = pos.splitter.cut( metrics().array_node_size_log );
 512                         assert( pos.nSlot < metrics().array_node_size );
 513                         pos.pArr = to_array(slot.ptr());
 514                         ++pos.nHeight;
 515                     }
 516                     else if (slot.bits() == flag_array_converting) {
 517                         // the slot is converting to array node right now
 518                         bkoff();
 519                         stats().onSlotConverting();
 520                     }
 521                     else {
 522                         // data node
 523                         assert(slot.bits() == 0);
 524                         return slot;
 525                     }
 526                 } // while
 527             }
 528
 529             size_t head_size() const
 530             {
 531                 return m_Metrics.head_node_size;
 532             }
 533
 534             size_t array_node_size() const
 535             {
 536                 return m_Metrics.array_node_size;
 537             }
 538
 539             void get_level_statistics(std::vector< feldman_hashset::level_statistics>& stat) const
 540             {
 541                 stat.clear();
 542                 gather_level_statistics(stat, 0, m_Head, head_size());
 543             }
 544
 545         protected:
 546             array_node * head() const
 547             {
 548                 return m_Head;
 549             }
 550
 551             stat& stats() const
 552             {
 553                 return m_Stat;
 554             }
 555
 556             feldman_hashset::details::metrics const& metrics() const
 557             {
 558                 return m_Metrics;
 559             }
 560
 561             void destroy_tree()
 562             {
 563                 // The function is not thread-safe. For use in dtor only
 564                 // Destroy all array nodes
 565                 destroy_array_nodes(m_Head, head_size());
 566             }
 567
 568             void destroy_array_nodes(array_node * pArr, size_t nSize)
 569             {
 570                 for (atomic_node_ptr * p = pArr->nodes, *pLast = p + nSize; p != pLast; ++p) {
 571                     node_ptr slot = p->load(memory_model::memory_order_relaxed);
 572                     if (slot.bits() == flag_array_node) {
 573                         destroy_array_nodes( to_array(slot.ptr()), array_node_size());
 574                         free_array_node( to_array( slot.ptr()), array_node_size());
 575                         p->store(node_ptr(), memory_model::memory_order_relaxed);
 576                     }
 577                 }
 578             }
 579
 580             static array_node * alloc_array_node(size_t nSize, array_node * pParent, size_t idxParent)
 581             {
 582                 array_node * pNode = cxx_array_node_allocator().NewBlock(sizeof(array_node) + sizeof(atomic_node_ptr) * (nSize - 1), pParent, idxParent);
 583                 new (pNode->nodes) atomic_node_ptr[nSize];
 584                 return pNode;
 585             }
 586
 587             array_node * alloc_head_node() const
 588             {
 589                 return alloc_array_node(head_size(), nullptr, 0);
 590             }
 591
 592             array_node * alloc_array_node(array_node * pParent, size_t idxParent) const
 593             {
 594                 return alloc_array_node(array_node_size(), pParent, idxParent);
 595             }
 596
 597             static void free_array_node( array_node * parr, size_t nSize )
 598             {
 599                 cxx_array_node_allocator().Delete( parr, nSize );
 600             }
 601
 602             union converter {
 603                 value_type * pData;
 604                 array_node * pArr;
 605
 606                 converter(value_type * p)
 607                     : pData(p)
 608                 {}
 609
 610                 converter(array_node * p)
 611                     : pArr(p)
 612                 {}
 613             };
 614
 615             static array_node * to_array(value_type * p)
 616             {
 617                 return converter(p).pArr;
 618             }
 619             static value_type * to_node(array_node * p)
 620             {
 621                 return converter(p).pData;
 622             }
 623
 624             void gather_level_statistics(std::vector<feldman_hashset::level_statistics>& stat, size_t nLevel, array_node * pArr, size_t nSize) const
 625             {
 626                 if (stat.size() <= nLevel) {
 627                     stat.resize(nLevel + 1);
 628                     stat[nLevel].node_capacity = nSize;
 629                 }
 630
 631                 ++stat[nLevel].array_node_count;
 632                 for (atomic_node_ptr * p = pArr->nodes, *pLast = p + nSize; p != pLast; ++p) {
 633                     node_ptr slot = p->load(memory_model::memory_order_relaxed);
 634                     if (slot.bits()) {
 635                         ++stat[nLevel].array_cell_count;
 636                         if (slot.bits() == flag_array_node)
 637                             gather_level_statistics(stat, nLevel + 1, to_array(slot.ptr()), array_node_size());
 638                     }
 639                     else if (slot.ptr())
 640                         ++stat[nLevel].data_cell_count;
 641                     else
 642                         ++stat[nLevel].empty_cell_count;
 643                 }
 644             }
 645
 646             bool expand_slot( traverse_data& pos, node_ptr current)
 647             {
 648                 return expand_slot( pos.pArr, pos.nSlot, current, pos.splitter.bit_offset());
 649             }
 650
 651         private:
 652             bool expand_slot(array_node * pParent, size_t idxParent, node_ptr current, size_t nOffset)
 653             {
 654                 assert(current.bits() == 0);
 655                 assert(current.ptr());
 656
 657                 array_node * pArr = alloc_array_node(pParent, idxParent);
 658
 659                 node_ptr cur(current.ptr());
 660                 atomic_node_ptr& slot = pParent->nodes[idxParent];
 661                 if (!slot.compare_exchange_strong(cur, cur | flag_array_converting, memory_model::memory_order_release, atomics::memory_order_relaxed))
 662                 {
 663                     stats().onExpandNodeFailed();
 664                     free_array_node( pArr, array_node_size());
 665                     return false;
 666                 }
 667
 668                 size_t idx = hash_splitter( hash_accessor()(*current.ptr()), nOffset ).cut( m_Metrics.array_node_size_log );
 669                 pArr->nodes[idx].store(current, memory_model::memory_order_release);
 670
 671                 cur = cur | flag_array_converting;
 672                 CDS_VERIFY(
 673                     slot.compare_exchange_strong(cur, node_ptr(to_node(pArr), flag_array_node), memory_model::memory_order_release, atomics::memory_order_relaxed)
 674                     );
 675
 676                 stats().onExpandNodeSuccess();
 677                 stats().onArrayNodeCreated();
 678                 return true;
 679             }
 680         };
 681         //@endcond
 682     } // namespace feldman_hashset
 683
 684     //@cond
 685     // Forward declaration
 686     template < class GC, typename T, class Traits = feldman_hashset::traits >
 687     class FeldmanHashSet;
 688     //@endcond
 689
 690 }} // namespace cds::intrusive
 691
 692 #endif // #ifndef CDSLIB_INTRUSIVE_DETAILS_FELDMAN_HASHSET_BASE_H