cc688f796cfd43a68d8ce36f6fb631b4dbcf3b1a
[libcds.git] / 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