cds/intrusive/cuckoo_set.h

   1 //$$CDS-header$$
   2
   3 #ifndef CDSLIB_INTRUSIVE_CUCKOO_SET_H
   4 #define CDSLIB_INTRUSIVE_CUCKOO_SET_H
   5
   6 #include <memory>
   7 #include <type_traits>
   8 #include <mutex>
   9 #include <functional>   // ref
  10 #include <cds/intrusive/details/base.h>
  11 #include <cds/opt/compare.h>
  12 #include <cds/opt/hash.h>
  13 #include <cds/sync/lock_array.h>
  14 #include <cds/os/thread.h>
  15 #include <cds/sync/spinlock.h>
  16
  17
  18 namespace cds { namespace intrusive {
  19
  20     /// CuckooSet-related definitions
  21     namespace cuckoo {
  22         /// Option to define probeset type
  23         /**
  24             The option specifies probeset type for the CuckooSet.
  25             Available values:
  26             - \p cds::intrusive::cuckoo::list - the probeset is a single-linked list.
  27                 The node contains pointer to next node in probeset.
  28             - \p cds::intrusive::cuckoo::vector<Capacity> - the probeset is a vector
  29                 with constant-size \p Capacity where \p Capacity is an <tt>unsigned int</tt> constant.
  30                 The node does not contain any auxiliary data.
  31         */
  32         template <typename Type>
  33         struct probeset_type
  34         {
  35             //@cond
  36             template <typename Base>
  37             struct pack: public Base {
  38                 typedef Type    probeset_type;
  39             };
  40             //@endcond
  41         };
  42
  43         /// Option specifying whether to store hash values in the node
  44         /**
  45              This option reserves additional space in the hook to store the hash value of the object once it's introduced in the container.
  46              When this option is used, the unordered container will store the calculated hash value in the hook and rehashing operations won't need
  47              to recalculate the hash of the value. This option will improve the performance of unordered containers
  48              when rehashing is frequent or hashing the value is a slow operation
  49
  50              The \p Count template parameter defines the size of hash array. Remember that cuckoo hashing implies at least two
  51              hash values per item.
  52
  53              Possible values of \p Count:
  54              - 0 - no hash storing in the node
  55              - greater that 1 - store hash values.
  56
  57              Value 1 is deprecated.
  58         */
  59         template <unsigned int Count>
  60         struct store_hash
  61         {
  62             //@cond
  63             template <typename Base>
  64             struct pack: public Base {
  65                 static unsigned int const store_hash = Count;
  66             };
  67             //@endcond
  68         };
  69
  70
  71         //@cond
  72         // Probeset type placeholders
  73         struct list_probeset_class;
  74         struct vector_probeset_class;
  75         //@endcond
  76
  77         //@cond
  78         /// List probeset type
  79         struct list;
  80         //@endcond
  81
  82         /// Vector probeset type
  83         template <unsigned int Capacity>
  84         struct vector
  85         {
  86             /// Vector capacity
  87             static unsigned int const c_nCapacity = Capacity;
  88         };
  89
  90         /// CuckooSet node
  91         /**
  92             Template arguments:
  93             - \p ProbesetType - type of probeset. Can be \p cds::intrusive::cuckoo::list
  94                 or \p cds::intrusive::cuckoo::vector<Capacity>.
  95             - \p StoreHashCount - constant that defines whether to store node hash values.
  96                 See cuckoo::store_hash option for explanation
  97             - \p Tag - a \ref cds_intrusive_hook_tag "tag"
  98         */
  99         template <typename ProbesetType = cuckoo::list, unsigned int StoreHashCount = 0, typename Tag = opt::none>
 100         struct node
 101 #ifdef CDS_DOXYGEN_INVOKED
 102         {
 103             typedef ProbesetType    probeset_type   ;   ///< Probeset type
 104             typedef Tag             tag             ;   ///< Tag
 105             static unsigned int const hash_array_size = StoreHashCount ;    ///< The size of hash array
 106         }
 107 #endif
 108 ;
 109
 110         //@cond
 111         template <typename Tag>
 112         struct node< cuckoo::list, 0, Tag>
 113         {
 114             typedef list_probeset_class probeset_class;
 115             typedef cuckoo::list        probeset_type;
 116             typedef Tag                 tag;
 117             static unsigned int const hash_array_size = 0;
 118             static unsigned int const probeset_size = 0;
 119
 120             node *  m_pNext;
 121
 122             CDS_CONSTEXPR node() CDS_NOEXCEPT
 123                 : m_pNext( nullptr )
 124             {}
 125
 126             void store_hash( size_t * )
 127             {}
 128
 129             size_t * get_hash() const
 130             {
 131                 // This node type does not store hash values!!!
 132                 assert(false);
 133                 return nullptr;
 134             }
 135
 136             void clear()
 137             {
 138                 m_pNext = nullptr;
 139             }
 140         };
 141
 142         template <unsigned int StoreHashCount, typename Tag>
 143         struct node< cuckoo::list, StoreHashCount, Tag>
 144         {
 145             typedef list_probeset_class probeset_class;
 146             typedef cuckoo::list        probeset_type;
 147             typedef Tag                 tag;
 148             static unsigned int const hash_array_size = StoreHashCount;
 149             static unsigned int const probeset_size = 0;
 150
 151             node *  m_pNext;
 152             size_t  m_arrHash[ hash_array_size ];
 153
 154             node() CDS_NOEXCEPT
 155                 : m_pNext( nullptr )
 156             {
 157                 memset( m_arrHash, 0, sizeof(m_arrHash));
 158             }
 159
 160             void store_hash( size_t * pHashes )
 161             {
 162                 memcpy( m_arrHash, pHashes, hash_array_size );
 163             }
 164
 165             size_t * get_hash() const
 166             {
 167                 return const_cast<size_t *>( m_arrHash );
 168             }
 169
 170             void clear()
 171             {
 172                 m_pNext = nullptr;
 173             }
 174         };
 175
 176         template <unsigned int VectorSize, typename Tag>
 177         struct node< cuckoo::vector<VectorSize>, 0, Tag>
 178         {
 179             typedef vector_probeset_class       probeset_class;
 180             typedef cuckoo::vector<VectorSize>  probeset_type;
 181             typedef Tag                         tag;
 182             static unsigned int const hash_array_size = 0;
 183             static unsigned int const probeset_size = probeset_type::c_nCapacity;
 184
 185             node() CDS_NOEXCEPT
 186             {}
 187
 188             void store_hash( size_t * )
 189             {}
 190
 191             size_t * get_hash() const
 192             {
 193                 // This node type does not store hash values!!!
 194                 assert(false);
 195                 return nullptr;
 196             }
 197
 198             void clear()
 199             {}
 200         };
 201
 202         template <unsigned int VectorSize, unsigned int StoreHashCount, typename Tag>
 203         struct node< cuckoo::vector<VectorSize>, StoreHashCount, Tag>
 204         {
 205             typedef vector_probeset_class       probeset_class;
 206             typedef cuckoo::vector<VectorSize>  probeset_type;
 207             typedef Tag                         tag;
 208             static unsigned int const hash_array_size = StoreHashCount;
 209             static unsigned int const probeset_size = probeset_type::c_nCapacity;
 210
 211             size_t  m_arrHash[ hash_array_size ];
 212
 213             node() CDS_NOEXCEPT
 214             {
 215                 memset( m_arrHash, 0, sizeof(m_arrHash));
 216             }
 217
 218             void store_hash( size_t * pHashes )
 219             {
 220                 memcpy( m_arrHash, pHashes, hash_array_size );
 221             }
 222
 223             size_t * get_hash() const
 224             {
 225                 return const_cast<size_t *>( m_arrHash );
 226             }
 227
 228             void clear()
 229             {}
 230         };
 231         //@endcond
 232
 233
 234         //@cond
 235         struct default_hook {
 236             typedef cuckoo::list probeset_type;
 237             static unsigned int const store_hash = 0;
 238             typedef opt::none   tag;
 239         };
 240
 241         template < typename HookType, typename... Options>
 242         struct hook
 243         {
 244             typedef typename opt::make_options< default_hook, Options...>::type  traits;
 245
 246             typedef typename traits::probeset_type probeset_type;
 247             typedef typename traits::tag tag;
 248             static unsigned int const store_hash = traits::store_hash;
 249
 250             typedef node<probeset_type, store_hash, tag>   node_type;
 251
 252             typedef HookType        hook_type;
 253         };
 254         //@endcond
 255
 256         /// Base hook
 257         /**
 258             \p Options are:
 259             - \p cuckoo::probeset_type - probeset type. Defaul is \p cuckoo::list
 260             - \p cuckoo::store_hash - store hash values in the node or not. Default is 0 (no storing)
 261             - \p opt::tag - a \ref cds_intrusive_hook_tag "tag"
 262         */
 263         template < typename... Options >
 264         struct base_hook: public hook< opt::base_hook_tag, Options... >
 265         {};
 266
 267         /// Member hook
 268         /**
 269             \p MemberOffset defines offset in bytes of \ref node member into your structure.
 270             Use \p offsetof macro to define \p MemberOffset
 271
 272             \p Options are:
 273             - \p cuckoo::probeset_type - probeset type. Defaul is \p cuckoo::list
 274             - \p cuckoo::store_hash - store hash values in the node or not. Default is 0 (no storing)
 275             - \p opt::tag - a \ref cds_intrusive_hook_tag "tag"
 276         */
 277         template < size_t MemberOffset, typename... Options >
 278         struct member_hook: public hook< opt::member_hook_tag, Options... >
 279         {
 280             //@cond
 281             static const size_t c_nMemberOffset = MemberOffset;
 282             //@endcond
 283         };
 284
 285         /// Traits hook
 286         /**
 287             \p NodeTraits defines type traits for node.
 288             See \ref node_traits for \p NodeTraits interface description
 289
 290             \p Options are:
 291             - \p cuckoo::probeset_type - probeset type. Defaul is \p cuckoo::list
 292             - \p cuckoo::store_hash - store hash values in the node or not. Default is 0 (no storing)
 293             - \p opt::tag - a \ref cds_intrusive_hook_tag "tag"
 294         */
 295         template <typename NodeTraits, typename... Options >
 296         struct traits_hook: public hook< opt::traits_hook_tag, Options... >
 297         {
 298             //@cond
 299             typedef NodeTraits node_traits;
 300             //@endcond
 301         };
 302
 303         /// Internal statistics for \ref striping mutex policy
 304         struct striping_stat {
 305             typedef cds::atomicity::event_counter   counter_type;   ///< Counter type
 306
 307             counter_type   m_nCellLockCount    ;  ///< Count of obtaining cell lock
 308             counter_type   m_nCellTryLockCount ;  ///< Count of cell \p try_lock attempts
 309             counter_type   m_nFullLockCount    ;  ///< Count of obtaining full lock
 310             counter_type   m_nResizeLockCount  ;  ///< Count of obtaining resize lock
 311             counter_type   m_nResizeCount      ;  ///< Count of resize event
 312
 313             //@cond
 314             void    onCellLock()    { ++m_nCellLockCount; }
 315             void    onCellTryLock() { ++m_nCellTryLockCount; }
 316             void    onFullLock()    { ++m_nFullLockCount; }
 317             void    onResizeLock()  { ++m_nResizeLockCount;   }
 318             void    onResize()      { ++m_nResizeCount; }
 319             //@endcond
 320         };
 321
 322         /// Dummy internal statistics for \ref striping mutex policy
 323         struct empty_striping_stat {
 324             //@cond
 325             void    onCellLock()    const {}
 326             void    onCellTryLock() const {}
 327             void    onFullLock()    const {}
 328             void    onResizeLock()  const {}
 329             void    onResize()      const {}
 330             //@endcond
 331         };
 332
 333         /// Lock striping concurrent access policy
 334         /**
 335             This is one of available opt::mutex_policy option type for CuckooSet
 336
 337             Lock striping is very simple technique.
 338             The cuckoo set consists of the bucket tables and the array of locks.
 339             There is single lock array for each bucket table, at least, the count of bucket table is 2.
 340             Initially, the capacity of lock array and each bucket table is the same.
 341             When set is resized, bucket table capacity will be doubled but lock array will not.
 342             The lock \p i protects each bucket \p j, where <tt> j = i mod L </tt>,
 343             where \p L - the size of lock array.
 344
 345             The policy contains an internal array of \p RecursiveLock locks.
 346
 347             Template arguments:
 348             - \p RecursiveLock - the type of recursive mutex. The default is \p std::recursive_mutex. The mutex type should be default-constructible.
 349                 Note that a recursive spin-lock is not suitable for lock striping for performance reason.
 350             - \p Arity - unsigned int constant that specifies an arity. The arity is the count of hash functors, i.e., the
 351                 count of lock arrays. Default value is 2.
 352             - \p Alloc - allocator type used for lock array memory allocation. Default is \p CDS_DEFAULT_ALLOCATOR.
 353             - \p Stat - internal statistics type. Note that this template argument is automatically selected by \ref CuckooSet
 354                 class according to its \p opt::stat option.
 355         */
 356         template <
 357             class RecursiveLock = std::recursive_mutex,
 358             unsigned int Arity = 2,
 359             class Alloc = CDS_DEFAULT_ALLOCATOR,
 360             class Stat = empty_striping_stat
 361         >
 362         class striping
 363         {
 364         public:
 365             typedef RecursiveLock   lock_type       ;   ///< lock type
 366             typedef Alloc           allocator_type  ;   ///< allocator type
 367             static unsigned int const c_nArity = Arity ;    ///< the arity
 368             typedef Stat            statistics_type ;   ///< Internal statistics type (\ref striping_stat or \ref empty_striping_stat)
 369
 370             //@cond
 371             typedef striping_stat       real_stat;
 372             typedef empty_striping_stat empty_stat;
 373
 374             template <typename Stat2>
 375             struct rebind_statistics {
 376                 typedef striping<lock_type, c_nArity, allocator_type, Stat2> other;
 377             };
 378             //@endcond
 379
 380             typedef cds::sync::lock_array< lock_type, cds::sync::pow2_select_policy, allocator_type >    lock_array_type ;   ///< lock array type
 381
 382         protected:
 383             //@cond
 384             class lock_array: public lock_array_type
 385             {
 386             public:
 387                 // placeholder ctor
 388                 lock_array(): lock_array_type( typename lock_array_type::select_cell_policy(2) ) {}
 389
 390                 // real ctor
 391                 lock_array( size_t nCapacity ): lock_array_type( nCapacity, typename lock_array_type::select_cell_policy(nCapacity) ) {}
 392             };
 393
 394             class scoped_lock: public std::unique_lock< lock_array_type >
 395             {
 396                 typedef std::unique_lock< lock_array_type > base_class;
 397             public:
 398                 scoped_lock( lock_array& arrLock, size_t nHash ): base_class( arrLock, nHash ) {}
 399             };
 400             //@endcond
 401
 402         protected:
 403             //@cond
 404             lock_array      m_Locks[c_nArity] ;   ///< array of \p lock_array_type
 405             statistics_type m_Stat              ; ///< internal statistics
 406             //@endcond
 407
 408         public:
 409             //@cond
 410             class scoped_cell_lock {
 411                 lock_type * m_guard[c_nArity];
 412
 413             public:
 414                 scoped_cell_lock( striping& policy, size_t const* arrHash )
 415                 {
 416                     for ( unsigned int i = 0; i < c_nArity; ++i ) {
 417                         m_guard[i] = &( policy.m_Locks[i].at( policy.m_Locks[i].lock( arrHash[i] )));
 418                     }
 419                     policy.m_Stat.onCellLock();
 420                 }
 421
 422                 ~scoped_cell_lock()
 423                 {
 424                     for ( unsigned int i = 0; i < c_nArity; ++i )
 425                         m_guard[i]->unlock();
 426                 }
 427             };
 428
 429             class scoped_cell_trylock
 430             {
 431                 typedef typename lock_array_type::lock_type lock_type;
 432
 433                 lock_type * m_guard[c_nArity];
 434                 bool        m_bLocked;
 435
 436             public:
 437                 scoped_cell_trylock( striping& policy, size_t const* arrHash )
 438                 {
 439                     size_t nCell = policy.m_Locks[0].try_lock( arrHash[0] );
 440                     m_bLocked = nCell != lock_array_type::c_nUnspecifiedCell;
 441                     if ( m_bLocked ) {
 442                         m_guard[0] = &(policy.m_Locks[0].at(nCell));
 443                         for ( unsigned int i = 1; i < c_nArity; ++i ) {
 444                             m_guard[i] = &( policy.m_Locks[i].at( policy.m_Locks[i].lock( arrHash[i] )) );
 445                         }
 446                     }
 447                     else {
 448                         std::fill( m_guard, m_guard + c_nArity, nullptr );
 449                     }
 450                     policy.m_Stat.onCellTryLock();
 451                 }
 452                 ~scoped_cell_trylock()
 453                 {
 454                     if ( m_bLocked ) {
 455                         for ( unsigned int i = 0; i < c_nArity; ++i )
 456                             m_guard[i]->unlock();
 457                     }
 458                 }
 459
 460                 bool locked() const
 461                 {
 462                     return m_bLocked;
 463                 }
 464             };
 465
 466             class scoped_full_lock {
 467                 std::unique_lock< lock_array_type >   m_guard;
 468             public:
 469                 scoped_full_lock( striping& policy )
 470                     : m_guard( policy.m_Locks[0] )
 471                 {
 472                     policy.m_Stat.onFullLock();
 473                 }
 474
 475                 /// Ctor for scoped_resize_lock - no statistics is incremented
 476                 scoped_full_lock( striping& policy, bool )
 477                     : m_guard( policy.m_Locks[0] )
 478                 {}
 479             };
 480
 481             class scoped_resize_lock: public scoped_full_lock {
 482             public:
 483                 scoped_resize_lock( striping& policy )
 484                     : scoped_full_lock( policy, false )
 485                 {
 486                     policy.m_Stat.onResizeLock();
 487                 }
 488             };
 489             //@endcond
 490
 491         public:
 492             /// Constructor
 493             striping(
 494                 size_t nLockCount          ///< The size of lock array. Must be power of two.
 495             )
 496             {
 497                 // Trick: initialize the array of locks
 498                 for ( unsigned int i = 0; i < c_nArity; ++i ) {
 499                     lock_array * pArr = m_Locks + i;
 500                     pArr->lock_array::~lock_array();
 501                     new ( pArr ) lock_array( nLockCount );
 502                 }
 503             }
 504
 505             /// Returns lock array size
 506             /**
 507                 Lock array size is unchanged during \p striping object lifetime
 508             */
 509             size_t lock_count() const
 510             {
 511                 return m_Locks[0].size();
 512             }
 513
 514             //@cond
 515             void resize( size_t )
 516             {
 517                 m_Stat.onResize();
 518             }
 519             //@endcond
 520
 521             /// Returns the arity of striping mutex policy
 522             CDS_CONSTEXPR unsigned int arity() const CDS_NOEXCEPT
 523             {
 524                 return c_nArity;
 525             }
 526
 527             /// Returns internal statistics
 528             statistics_type const& statistics() const
 529             {
 530                 return m_Stat;
 531             }
 532         };
 533
 534         /// Internal statistics for \ref refinable mutex policy
 535         struct refinable_stat {
 536             typedef cds::atomicity::event_counter   counter_type    ;   ///< Counter type
 537
 538             counter_type   m_nCellLockCount         ;   ///< Count of obtaining cell lock
 539             counter_type   m_nCellLockWaitResizing  ;   ///< Count of loop iteration to wait for resizing
 540             counter_type   m_nCellLockArrayChanged  ;   ///< Count of event "Lock array has been changed when obtaining cell lock"
 541             counter_type   m_nCellLockFailed        ;   ///< Count of event "Cell lock failed because of the array is owned by other thread"
 542
 543             counter_type   m_nSecondCellLockCount   ;   ///< Count of obtaining cell lock when another cell is already locked
 544             counter_type   m_nSecondCellLockFailed  ;   ///< Count of unsuccess obtaining cell lock when another cell is already locked
 545
 546             counter_type   m_nFullLockCount         ;   ///< Count of obtaining full lock
 547             counter_type   m_nFullLockIter          ;   ///< Count of unsuccessfull iteration to obtain full lock
 548
 549             counter_type   m_nResizeLockCount       ;   ///< Count of obtaining resize lock
 550             counter_type   m_nResizeLockIter        ;   ///< Count of unsuccessfull iteration to obtain resize lock
 551             counter_type   m_nResizeLockArrayChanged;   ///< Count of event "Lock array has been changed when obtaining resize lock"
 552             counter_type   m_nResizeCount           ;   ///< Count of resize event
 553
 554             //@cond
 555             void    onCellLock()    { ++m_nCellLockCount; }
 556             void    onCellWaitResizing() { ++m_nCellLockWaitResizing; }
 557             void    onCellArrayChanged() { ++m_nCellLockArrayChanged; }
 558             void    onCellLockFailed()   { ++m_nCellLockFailed; }
 559             void    onSecondCellLock()   { ++m_nSecondCellLockCount; }
 560             void    onSecondCellLockFailed() { ++m_nSecondCellLockFailed; }
 561             void    onFullLock()         { ++m_nFullLockCount; }
 562             void    onFullLockIter()     { ++m_nFullLockIter; }
 563             void    onResizeLock()       { ++m_nResizeLockCount;   }
 564             void    onResizeLockIter()   { ++m_nResizeLockIter; }
 565             void    onResizeLockArrayChanged() { ++m_nResizeLockArrayChanged; }
 566             void    onResize()           { ++m_nResizeCount; }
 567             //@endcond
 568         };
 569
 570         /// Dummy internal statistics for \ref refinable mutex policy
 571         struct empty_refinable_stat {
 572             //@cond
 573             void    onCellLock()            const {}
 574             void    onCellWaitResizing()    const {}
 575             void    onCellArrayChanged()    const {}
 576             void    onCellLockFailed()      const {}
 577             void    onSecondCellLock()      const {}
 578             void    onSecondCellLockFailed() const {}
 579             void    onFullLock()            const {}
 580             void    onFullLockIter()        const {}
 581             void    onResizeLock()          const {}
 582             void    onResizeLockIter()      const {}
 583             void    onResizeLockArrayChanged() const {}
 584             void    onResize()              const {}
 585             //@endcond
 586         };
 587
 588         /// Refinable concurrent access policy
 589         /**
 590             This is one of available opt::mutex_policy option type for CuckooSet
 591
 592             Refining is like a striping technique (see cuckoo::striping)
 593             but it allows growing the size of lock array when resizing the hash table.
 594             So, the sizes of hash table and lock array are equal.
 595
 596             Template arguments:
 597             - \p RecursiveLock - the type of mutex. Reentrant (recursive) mutex is required.
 598                 The default is \p std::recursive_mutex. The mutex type should be default-constructible.
 599             - \p Arity - unsigned int constant that specifies an arity. The arity is the count of hash functors, i.e., the
 600                 count of lock arrays. Default value is 2.
 601             - \p BackOff - back-off strategy. Default is cds::backoff::yield
 602             - \p Alloc - allocator type used for lock array memory allocation. Default is \p CDS_DEFAULT_ALLOCATOR.
 603             - \p Stat - internal statistics type. Note that this template argument is automatically selected by \ref CuckooSet
 604                 class according to its \p opt::stat option.
 605         */
 606         template <
 607             class RecursiveLock = std::recursive_mutex,
 608             unsigned int Arity = 2,
 609             typename BackOff = cds::backoff::yield,
 610             class Alloc = CDS_DEFAULT_ALLOCATOR,
 611             class Stat = empty_refinable_stat
 612         >
 613         class refinable
 614         {
 615         public:
 616             typedef RecursiveLock   lock_type       ;   ///< lock type
 617             typedef Alloc           allocator_type  ;   ///< allocator type
 618             typedef BackOff         back_off        ;   ///< back-off strategy
 619             typedef Stat            statistics_type ;   ///< internal statistics type
 620             static unsigned int const c_nArity = Arity; ///< the arity
 621
 622             //@cond
 623             typedef refinable_stat          real_stat;
 624             typedef empty_refinable_stat    empty_stat;
 625
 626             template <typename Stat2>
 627             struct rebind_statistics {
 628                 typedef refinable< lock_type, c_nArity, back_off, allocator_type, Stat2>    other;
 629             };
 630             //@endcond
 631
 632         protected:
 633             //@cond
 634             typedef cds::sync::trivial_select_policy  lock_selection_policy;
 635
 636             class lock_array_type
 637                 : public cds::sync::lock_array< lock_type, lock_selection_policy, allocator_type >
 638                 , public std::enable_shared_from_this< lock_array_type >
 639             {
 640                 typedef cds::sync::lock_array< lock_type, lock_selection_policy, allocator_type >    lock_array_base;
 641             public:
 642                 lock_array_type( size_t nCapacity )
 643                     : lock_array_base( nCapacity )
 644                 {}
 645             };
 646             typedef std::shared_ptr< lock_array_type >  lock_array_ptr;
 647             typedef cds::details::Allocator< lock_array_type, allocator_type >  lock_array_allocator;
 648
 649             typedef unsigned long long  owner_t;
 650             typedef cds::OS::ThreadId   threadId_t;
 651
 652             typedef cds::sync::spin     spinlock_type;
 653             typedef std::unique_lock< spinlock_type > scoped_spinlock;
 654             //@endcond
 655
 656         protected:
 657             //@cond
 658             static owner_t const c_nOwnerMask = (((owner_t) 1) << (sizeof(owner_t) * 8 - 1)) - 1;
 659
 660             atomics::atomic< owner_t >   m_Owner     ;   ///< owner mark (thread id + boolean flag)
 661             atomics::atomic<size_t>      m_nCapacity ;   ///< lock array capacity
 662             lock_array_ptr                  m_arrLocks[ c_nArity ]  ; ///< Lock array. The capacity of array is specified in constructor.
 663             spinlock_type                   m_access    ;   ///< access to m_arrLocks
 664             statistics_type                 m_Stat      ;   ///< internal statistics
 665             //@endcond
 666
 667         protected:
 668             //@cond
 669             struct lock_array_disposer {
 670                 void operator()( lock_array_type * pArr )
 671                 {
 672                     lock_array_allocator().Delete( pArr );
 673                 }
 674             };
 675
 676             lock_array_ptr create_lock_array( size_t nCapacity )
 677             {
 678                 return lock_array_ptr( lock_array_allocator().New( nCapacity ), lock_array_disposer() );
 679             }
 680
 681             void acquire( size_t const * arrHash, lock_array_ptr * pLockArr, lock_type ** parrLock )
 682             {
 683                 owner_t me = (owner_t) cds::OS::get_current_thread_id();
 684                 owner_t who;
 685
 686                 back_off bkoff;
 687                 while ( true ) {
 688
 689                     {
 690                         scoped_spinlock sl(m_access);
 691                         for ( unsigned int i = 0; i < c_nArity; ++i )
 692                             pLockArr[i] = m_arrLocks[i];
 693                     }
 694
 695                     // wait while resizing
 696                     while ( true ) {
 697                         who = m_Owner.load( atomics::memory_order_acquire );
 698                         if ( !( who & 1 ) || (who >> 1) == (me & c_nOwnerMask) )
 699                             break;
 700                         bkoff();
 701                         m_Stat.onCellWaitResizing();
 702                     }
 703
 704                     if ( pLockArr[0] != m_arrLocks[0] ) {
 705                         m_Stat.onCellArrayChanged();
 706                     }
 707                     else {
 708
 709                         size_t const nMask = pLockArr[0]->size() - 1;
 710                         assert( cds::beans::is_power2( nMask + 1 ));
 711
 712                         for ( unsigned int i = 0; i < c_nArity; ++i ) {
 713                             parrLock[i] = &( pLockArr[i]->at( arrHash[i] & nMask ));
 714                             parrLock[i]->lock();
 715                         }
 716
 717                         who = m_Owner.load( atomics::memory_order_acquire );
 718                         if ( ( !(who & 1) || (who >> 1) == (me & c_nOwnerMask) ) && m_arrLocks[0] == pLockArr[0] ) {
 719                             m_Stat.onCellLock();
 720                             return;
 721                         }
 722
 723                         for ( unsigned int i = 0; i < c_nArity; ++i ) {
 724                             parrLock[i]->unlock();
 725                         }
 726
 727                         m_Stat.onCellLockFailed();
 728                     }
 729
 730                     // clears pLockArr can lead to calling dtor for each item of pLockArr[i] that may be a heavy-weighted operation
 731                     // (each pLockArr[i] is a shared pointer to array of a ton of mutexes)
 732                     // It is better to do this before the next loop iteration where we will use spin-locked assignment to pLockArr
 733                     // Destructing a lot of mutexes under spin-lock is a bad solution
 734                     for ( unsigned int i = 0; i < c_nArity; ++i )
 735                         pLockArr[i].reset();
 736                 }
 737             }
 738
 739             bool try_second_acquire( size_t const * arrHash, lock_type ** parrLock )
 740             {
 741                 // It is assumed that the current thread already has a lock
 742                 // and requires a second lock for other hash
 743
 744                 size_t const nMask = m_nCapacity.load(atomics::memory_order_acquire) - 1;
 745                 size_t nCell = m_arrLocks[0]->try_lock( arrHash[0] & nMask);
 746                 if ( nCell == lock_array_type::c_nUnspecifiedCell ) {
 747                     m_Stat.onSecondCellLockFailed();
 748                     return false;
 749                 }
 750                 parrLock[0] = &(m_arrLocks[0]->at(nCell));
 751
 752                 for ( unsigned int i = 1; i < c_nArity; ++i ) {
 753                     parrLock[i] = &( m_arrLocks[i]->at( m_arrLocks[i]->lock( arrHash[i] & nMask)) );
 754                 }
 755
 756                 m_Stat.onSecondCellLock();
 757                 return true;
 758             }
 759
 760             void acquire_all()
 761             {
 762                 owner_t me = (owner_t) cds::OS::get_current_thread_id();
 763
 764                 back_off bkoff;
 765                 while ( true ) {
 766                     owner_t ownNull = 0;
 767                     if ( m_Owner.compare_exchange_strong( ownNull, (me << 1) | 1, atomics::memory_order_acq_rel, atomics::memory_order_relaxed )) {
 768                         m_arrLocks[0]->lock_all();
 769
 770                         m_Stat.onFullLock();
 771                         return;
 772                     }
 773                     bkoff();
 774                     m_Stat.onFullLockIter();
 775                 }
 776             }
 777
 778             void release_all()
 779             {
 780                 m_arrLocks[0]->unlock_all();
 781                 m_Owner.store( 0, atomics::memory_order_release );
 782             }
 783
 784             void acquire_resize( lock_array_ptr * pOldLocks )
 785             {
 786                 owner_t me = (owner_t) cds::OS::get_current_thread_id();
 787
 788                 while ( true ) {
 789                     {
 790                         scoped_spinlock sl(m_access);
 791                         for ( unsigned int i = 0; i < c_nArity; ++i )
 792                             pOldLocks[i] = m_arrLocks[i];
 793                     }
 794
 795                     // global lock
 796                     owner_t ownNull = 0;
 797                     if ( m_Owner.compare_exchange_strong( ownNull, (me << 1) | 1, atomics::memory_order_acq_rel, atomics::memory_order_relaxed )) {
 798                         if ( pOldLocks[0] != m_arrLocks[0] ) {
 799                             m_Owner.store( 0, atomics::memory_order_release );
 800                             m_Stat.onResizeLockArrayChanged();
 801                         }
 802                         else {
 803                             pOldLocks[0]->lock_all();
 804                             m_Stat.onResizeLock();
 805                             return;
 806                         }
 807                     }
 808                     else
 809                         m_Stat.onResizeLockIter();
 810
 811                     // clears pOldLocks can lead to calling dtor for each item of pOldLocks[i] that may be a heavy-weighted operation
 812                     // (each pOldLocks[i] is a shared pointer to array of a ton of mutexes)
 813                     // It is better to do this before the next loop iteration where we will use spin-locked assignment to pOldLocks
 814                     // Destructing a lot of mutexes under spin-lock is a bad solution
 815                     for ( unsigned int i = 0; i < c_nArity; ++i )
 816                         pOldLocks[i].reset();
 817                 }
 818             }
 819
 820             void release_resize( lock_array_ptr * pOldLocks )
 821             {
 822                 m_Owner.store( 0, atomics::memory_order_release );
 823                 pOldLocks[0]->unlock_all();
 824             }
 825             //@endcond
 826
 827         public:
 828             //@cond
 829             class scoped_cell_lock {
 830                 lock_type * m_arrLock[ c_nArity ];
 831                 lock_array_ptr  m_arrLockArr[ c_nArity ];
 832
 833             public:
 834                 scoped_cell_lock( refinable& policy, size_t const* arrHash )
 835                 {
 836                     policy.acquire( arrHash, m_arrLockArr, m_arrLock );
 837                 }
 838
 839                 ~scoped_cell_lock()
 840                 {
 841                     for ( unsigned int i = 0; i < c_nArity; ++i )
 842                         m_arrLock[i]->unlock();
 843                 }
 844             };
 845
 846             class scoped_cell_trylock {
 847                 lock_type * m_arrLock[ c_nArity ];
 848                 bool        m_bLocked;
 849
 850             public:
 851                 scoped_cell_trylock( refinable& policy, size_t const* arrHash )
 852                 {
 853                     m_bLocked = policy.try_second_acquire( arrHash, m_arrLock );
 854                 }
 855
 856                 ~scoped_cell_trylock()
 857                 {
 858                     if ( m_bLocked ) {
 859                         for ( unsigned int i = 0; i < c_nArity; ++i )
 860                             m_arrLock[i]->unlock();
 861                     }
 862                 }
 863
 864                 bool locked() const
 865                 {
 866                     return m_bLocked;
 867                 }
 868             };
 869
 870             class scoped_full_lock {
 871                 refinable& m_policy;
 872             public:
 873                 scoped_full_lock( refinable& policy )
 874                     : m_policy( policy )
 875                 {
 876                     policy.acquire_all();
 877                 }
 878                 ~scoped_full_lock()
 879                 {
 880                     m_policy.release_all();
 881                 }
 882             };
 883
 884             class scoped_resize_lock
 885             {
 886                 refinable&      m_policy;
 887                 lock_array_ptr  m_arrLocks[ c_nArity ];
 888             public:
 889                 scoped_resize_lock( refinable& policy )
 890                     : m_policy(policy)
 891                 {
 892                     policy.acquire_resize( m_arrLocks );
 893                 }
 894                 ~scoped_resize_lock()
 895                 {
 896                     m_policy.release_resize( m_arrLocks );
 897                 }
 898             };
 899             //@endcond
 900
 901         public:
 902             /// Constructor
 903             refinable(
 904                 size_t nLockCount   ///< The size of lock array. Must be power of two.
 905             )   : m_Owner(0)
 906                 , m_nCapacity( nLockCount )
 907             {
 908                 assert( cds::beans::is_power2( nLockCount ));
 909                 for ( unsigned int i = 0; i < c_nArity; ++i )
 910                     m_arrLocks[i] = create_lock_array( nLockCount );
 911             }
 912
 913             //@cond
 914             void resize( size_t nCapacity )
 915             {
 916                 lock_array_ptr pNew[ c_nArity ];
 917                 for ( unsigned int i = 0; i < c_nArity; ++i )
 918                     pNew[i] = create_lock_array( nCapacity );
 919
 920                 {
 921                     scoped_spinlock sl(m_access);
 922                     for ( unsigned int i = 0; i < c_nArity; ++i )
 923                         m_arrLocks[i] = pNew[i];
 924                 }
 925                 m_nCapacity.store( nCapacity, atomics::memory_order_release );
 926
 927                 m_Stat.onResize();
 928             }
 929             //@endcond
 930
 931             /// Returns lock array size
 932             /**
 933                 Lock array size is not a constant for \p refinable policy and can be changed when the set is resized.
 934             */
 935             size_t lock_count() const
 936             {
 937                 return m_nCapacity.load(atomics::memory_order_relaxed);
 938             }
 939
 940             /// Returns the arity of \p refinable mutex policy
 941             CDS_CONSTEXPR unsigned int arity() const CDS_NOEXCEPT
 942             {
 943                 return c_nArity;
 944             }
 945
 946             /// Returns internal statistics
 947             statistics_type const& statistics() const
 948             {
 949                 return m_Stat;
 950             }
 951         };
 952
 953         /// CuckooSet internal statistics
 954         struct stat {
 955             typedef cds::atomicity::event_counter   counter_type ;  ///< Counter type
 956
 957             counter_type    m_nRelocateCallCount    ; ///< Count of \p relocate function call
 958             counter_type    m_nRelocateRoundCount   ; ///< Count of attempts to relocate items
 959             counter_type    m_nFalseRelocateCount   ; ///< Count of unneeded attempts of \p relocate call
 960             counter_type    m_nSuccessRelocateCount ; ///< Count of successfull item relocating
 961             counter_type    m_nRelocateAboveThresholdCount; ///< Count of item relocating above probeset threshold
 962             counter_type    m_nFailedRelocateCount  ;   ///< Count of failed relocation attemp (when all probeset is full)
 963
 964             counter_type    m_nResizeCallCount      ;   ///< Count of \p resize function call
 965             counter_type    m_nFalseResizeCount     ;   ///< Count of false \p resize function call (when other thread has been resized the set)
 966             counter_type    m_nResizeSuccessNodeMove;   ///< Count of successfull node moving when resizing
 967             counter_type    m_nResizeRelocateCall   ;   ///< Count of \p relocate function call from \p resize function
 968
 969             counter_type    m_nInsertSuccess        ;   ///< Count of successfull \p insert function call
 970             counter_type    m_nInsertFailed         ;   ///< Count of failed \p insert function call
 971             counter_type    m_nInsertResizeCount    ;   ///< Count of \p resize function call from \p insert
 972             counter_type    m_nInsertRelocateCount  ;   ///< Count of \p relocate function call from \p insert
 973             counter_type    m_nInsertRelocateFault  ;   ///< Count of failed \p relocate function call from \p insert
 974
 975             counter_type    m_nUpdateExistCount     ;   ///< Count of call \p update() function for existing node
 976             counter_type    m_nUpdateSuccessCount   ;   ///< Count of successfull \p insert function call for new node
 977             counter_type    m_nUpdateResizeCount    ;   ///< Count of \p resize function call from \p update()
 978             counter_type    m_nUpdateRelocateCount  ;   ///< Count of \p relocate function call from \p update()
 979             counter_type    m_nUpdateRelocateFault  ;   ///< Count of failed \p relocate function call from \p update()
 980
 981             counter_type    m_nUnlinkSuccess        ;   ///< Count of success \p unlink function call
 982             counter_type    m_nUnlinkFailed         ;   ///< Count of failed \p unlink function call
 983
 984             counter_type    m_nEraseSuccess         ;   ///< Count of success \p erase function call
 985             counter_type    m_nEraseFailed          ;   ///< Count of failed \p erase function call
 986
 987             counter_type    m_nFindSuccess         ;   ///< Count of success \p find function call
 988             counter_type    m_nFindFailed          ;   ///< Count of failed \p find function call
 989
 990             counter_type    m_nFindEqualSuccess         ;   ///< Count of success \p find_equal function call
 991             counter_type    m_nFindEqualFailed          ;   ///< Count of failed \p find_equal function call
 992
 993             counter_type    m_nFindWithSuccess         ;   ///< Count of success \p find_with function call
 994             counter_type    m_nFindWithFailed          ;   ///< Count of failed \p find_with function call
 995
 996             //@cond
 997             void    onRelocateCall()        { ++m_nRelocateCallCount; }
 998             void    onRelocateRound()       { ++m_nRelocateRoundCount; }
 999             void    onFalseRelocateRound()  { ++m_nFalseRelocateCount; }
1000             void    onSuccessRelocateRound(){ ++m_nSuccessRelocateCount; }
1001             void    onRelocateAboveThresholdRound() { ++m_nRelocateAboveThresholdCount; }
1002             void    onFailedRelocate()      { ++m_nFailedRelocateCount; }
1003
1004             void    onResizeCall()          { ++m_nResizeCallCount; }
1005             void    onFalseResizeCall()     { ++m_nFalseResizeCount; }
1006             void    onResizeSuccessMove()   { ++m_nResizeSuccessNodeMove; }
1007             void    onResizeRelocateCall()  { ++m_nResizeRelocateCall; }
1008
1009             void    onInsertSuccess()       { ++m_nInsertSuccess; }
1010             void    onInsertFailed()        { ++m_nInsertFailed; }
1011             void    onInsertResize()        { ++m_nInsertResizeCount; }
1012             void    onInsertRelocate()      { ++m_nInsertRelocateCount; }
1013             void    onInsertRelocateFault() { ++m_nInsertRelocateFault; }
1014
1015             void    onUpdateExist()         { ++m_nUpdateExistCount; }
1016             void    onUpdateSuccess()       { ++m_nUpdateSuccessCount; }
1017             void    onUpdateResize()        { ++m_nUpdateResizeCount; }
1018             void    onUpdateRelocate()      { ++m_nUpdateRelocateCount; }
1019             void    onUpdateRelocateFault() { ++m_nUpdateRelocateFault; }
1020
1021             void    onUnlinkSuccess()       { ++m_nUnlinkSuccess; }
1022             void    onUnlinkFailed()        { ++m_nUnlinkFailed; }
1023
1024             void    onEraseSuccess()        { ++m_nEraseSuccess; }
1025             void    onEraseFailed()         { ++m_nEraseFailed; }
1026
1027             void    onFindSuccess()         { ++m_nFindSuccess; }
1028             void    onFindFailed()          { ++m_nFindFailed; }
1029
1030             void    onFindWithSuccess()     { ++m_nFindWithSuccess; }
1031             void    onFindWithFailed()      { ++m_nFindWithFailed; }
1032             //@endcond
1033         };
1034
1035         /// CuckooSet empty internal statistics
1036         struct empty_stat {
1037             //@cond
1038             void    onRelocateCall()        const {}
1039             void    onRelocateRound()       const {}
1040             void    onFalseRelocateRound()  const {}
1041             void    onSuccessRelocateRound()const {}
1042             void    onRelocateAboveThresholdRound() const {}
1043             void    onFailedRelocate()      const {}
1044
1045             void    onResizeCall()          const {}
1046             void    onFalseResizeCall()     const {}
1047             void    onResizeSuccessMove()   const {}
1048             void    onResizeRelocateCall()  const {}
1049
1050             void    onInsertSuccess()       const {}
1051             void    onInsertFailed()        const {}
1052             void    onInsertResize()        const {}
1053             void    onInsertRelocate()      const {}
1054             void    onInsertRelocateFault() const {}
1055
1056             void    onUpdateExist()         const {}
1057             void    onUpdateSuccess()       const {}
1058             void    onUpdateResize()        const {}
1059             void    onUpdateRelocate()      const {}
1060             void    onUpdateRelocateFault() const {}
1061
1062             void    onUnlinkSuccess()       const {}
1063             void    onUnlinkFailed()        const {}
1064
1065             void    onEraseSuccess()        const {}
1066             void    onEraseFailed()         const {}
1067
1068             void    onFindSuccess()         const {}
1069             void    onFindFailed()          const {}
1070
1071             void    onFindWithSuccess()     const {}
1072             void    onFindWithFailed()      const {}
1073             //@endcond
1074         };
1075
1076         /// Type traits for CuckooSet class
1077         struct traits
1078         {
1079             /// Hook used
1080             /**
1081                 Possible values are: cuckoo::base_hook, cuckoo::member_hook, cuckoo::traits_hook.
1082             */
1083             typedef base_hook<>         hook;
1084
1085             /// Hash functors tuple
1086             /**
1087                 This is mandatory type and has no predefined one.
1088
1089                 At least, two hash functors should be provided. All hash functor
1090                 should be orthogonal (different): for each <tt> i,j: i != j => h[i](x) != h[j](x) </tt>.
1091                 The hash functors are defined as <tt> std::tuple< H1, H2, ... Hn > </tt>:
1092                 \@code cds::opt::hash< std::tuple< h1, h2 > > \@endcode
1093                 The number of hash functors specifies the number \p k - the count of hash tables in cuckoo hashing.
1094
1095                 To specify hash tuple in traits you should use \p cds::opt::hash_tuple:
1096                 \code
1097                 struct my_traits: public cds::intrusive::cuckoo::traits {
1098                     typedef cds::opt::hash_tuple< hash1, hash2 > hash;
1099                 };
1100                 \endcode
1101             */
1102             typedef cds::opt::none      hash;
1103
1104             /// Concurrent access policy
1105             /**
1106                 Available opt::mutex_policy types:
1107                 - \p cuckoo::striping - simple, but the lock array is not resizable
1108                 - \p cuckoo::refinable - resizable lock array, but more complex access to set data.
1109
1110                 Default is \p cuckoo::striping.
1111             */
1112             typedef cuckoo::striping<>               mutex_policy;
1113
1114             /// Key equality functor
1115             /**
1116                 Default is <tt>std::equal_to<T></tt>
1117             */
1118             typedef opt::none                       equal_to;
1119
1120             /// Key comparing functor
1121             /**
1122                 No default functor is provided. If the option is not specified, the \p less is used.
1123             */
1124             typedef opt::none                       compare;
1125
1126             /// specifies binary predicate used for key comparison.
1127             /**
1128                 Default is \p std::less<T>.
1129             */
1130             typedef opt::none                       less;
1131
1132             /// Item counter
1133             /**
1134                 The type for item counting feature.
1135                 Default is \p cds::atomicity::item_counter
1136
1137                 Only atomic item counter type is allowed.
1138             */
1139             typedef atomicity::item_counter             item_counter;
1140
1141             /// Allocator type
1142             /**
1143                 The allocator type for allocating bucket tables.
1144             */
1145             typedef CDS_DEFAULT_ALLOCATOR       allocator;
1146
1147             /// Disposer
1148             /**
1149                 The disposer functor is used in \p CuckooSet::clear() member function
1150                 to free set's node.
1151             */
1152             typedef intrusive::opt::v::empty_disposer   disposer;
1153
1154             /// Internal statistics. Available statistics: \p cuckoo::stat, \p cuckoo::empty_stat
1155             typedef empty_stat                  stat;
1156         };
1157
1158         /// Metafunction converting option list to \p CuckooSet traits
1159         /**
1160             Template argument list \p Options... are:
1161             - \p intrusive::opt::hook - hook used. Possible values are: \p cuckoo::base_hook, \p cuckoo::member_hook,
1162                 \p cuckoo::traits_hook.
1163                 If the option is not specified, <tt>%cuckoo::base_hook<></tt> is used.
1164             - \p opt::hash - hash functor tuple, mandatory option. At least, two hash functors should be provided. All hash functor
1165                 should be orthogonal (different): for each <tt> i,j: i != j => h[i](x) != h[j](x) </tt>.
1166                 The hash functors are passed as <tt> std::tuple< H1, H2, ... Hn > </tt>. The number of hash functors specifies
1167                 the number \p k - the count of hash tables in cuckoo hashing.
1168             - \p opt::mutex_policy - concurrent access policy.
1169                 Available policies: \p cuckoo::striping, \p cuckoo::refinable.
1170                 Default is \p %cuckoo::striping.
1171             - \p opt::equal_to - key equality functor like \p std::equal_to.
1172                 If this functor is defined then the probe-set will be unordered.
1173                 If \p %opt::compare or \p %opt::less option is specified too, then the probe-set will be ordered
1174                 and \p %opt::equal_to will be ignored.
1175             - \p opt::compare - key comparison functor. No default functor is provided.
1176                 If the option is not specified, the \p %opt::less is used.
1177                 If \p %opt::compare or \p %opt::less option is specified, then the probe-set will be ordered.
1178             - \p opt::less - specifies binary predicate used for key comparison. Default is \p std::less<T>.
1179                 If \p %opt::compare or \p %opt::less option is specified, then the probe-set will be ordered.
1180             - \p opt::item_counter - the type of item counting feature. Default is \p atomicity::item_counter
1181                 The item counter should be atomic.
1182             - \p opt::allocator - the allocator type using for allocating bucket tables.
1183                 Default is \ref CDS_DEFAULT_ALLOCATOR
1184             - \p intrusive::opt::disposer - the disposer type used in \p clear() member function for
1185                 freeing nodes. Default is \p intrusive::opt::v::empty_disposer
1186             - \p opt::stat - internal statistics. Possibly types: \p cuckoo::stat, \p cuckoo::empty_stat.
1187                 Default is \p %cuckoo::empty_stat
1188
1189             The probe set traits \p cuckoo::probeset_type and \p cuckoo::store_hash are taken from \p node type
1190             specified by \p opt::hook option.
1191         */
1192         template <typename... Options>
1193         struct make_traits {
1194             typedef typename cds::opt::make_options<
1195                 typename cds::opt::find_type_traits< cuckoo::traits, Options... >::type
1196                 ,Options...
1197             >::type   type ;    ///< Result of metafunction
1198         };
1199
1200         //@cond
1201         namespace details {
1202             template <typename Node, typename Probeset>
1203             class bucket_entry;
1204
1205             template <typename Node>
1206             class bucket_entry<Node, cuckoo::list>
1207             {
1208             public:
1209                 typedef Node                        node_type;
1210                 typedef cuckoo::list_probeset_class probeset_class;
1211                 typedef cuckoo::list                probeset_type;
1212
1213             protected:
1214                 node_type *     pHead;
1215                 unsigned int    nSize;
1216
1217             public:
1218                 class iterator
1219                 {
1220                     node_type * pNode;
1221                     friend class bucket_entry;
1222
1223                 public:
1224                     iterator()
1225                         : pNode( nullptr )
1226                     {}
1227                     iterator( node_type * p )
1228                         : pNode( p )
1229                     {}
1230                     iterator( iterator const& it)
1231                         : pNode( it.pNode )
1232                     {}
1233
1234                     iterator& operator=( iterator const& it )
1235                     {
1236                         pNode = it.pNode;
1237                         return *this;
1238                     }
1239
1240                     iterator& operator=( node_type * p )
1241                     {
1242                         pNode = p;
1243                         return *this;
1244                     }
1245
1246                     node_type * operator->()
1247                     {
1248                         return pNode;
1249                     }
1250                     node_type& operator*()
1251                     {
1252                         assert( pNode != nullptr );
1253                         return *pNode;
1254                     }
1255
1256                     // preinc
1257                     iterator& operator ++()
1258                     {
1259                         if ( pNode )
1260                             pNode = pNode->m_pNext;
1261                         return *this;
1262                     }
1263
1264                     bool operator==(iterator const& it ) const
1265                     {
1266                         return pNode == it.pNode;
1267                     }
1268                     bool operator!=(iterator const& it ) const
1269                     {
1270                         return !( *this == it );
1271                     }
1272                 };
1273
1274             public:
1275                 bucket_entry()
1276                     : pHead( nullptr )
1277                     , nSize(0)
1278                 {
1279                     static_assert(( std::is_same<typename node_type::probeset_type, probeset_type>::value ), "Incompatible node type" );
1280                 }
1281
1282                 iterator begin()
1283                 {
1284                     return iterator(pHead);
1285                 }
1286                 iterator end()
1287                 {
1288                     return iterator();
1289                 }
1290
1291                 void insert_after( iterator it, node_type * p )
1292                 {
1293                     node_type * pPrev = it.pNode;
1294                     if ( pPrev ) {
1295                         p->m_pNext = pPrev->m_pNext;
1296                         pPrev->m_pNext = p;
1297                     }
1298                     else {
1299                         // insert as head
1300                         p->m_pNext = pHead;
1301                         pHead = p;
1302                     }
1303                     ++nSize;
1304                 }
1305
1306                 void remove( iterator itPrev, iterator itWhat )
1307                 {
1308                     node_type * pPrev = itPrev.pNode;
1309                     node_type * pWhat = itWhat.pNode;
1310                     assert( (!pPrev && pWhat == pHead) || (pPrev && pPrev->m_pNext == pWhat) );
1311
1312                     if ( pPrev )
1313                         pPrev->m_pNext = pWhat->m_pNext;
1314                     else {
1315                         assert( pWhat == pHead );
1316                         pHead = pHead->m_pNext;
1317                     }
1318                     pWhat->clear();
1319                     --nSize;
1320                 }
1321
1322                 void clear()
1323                 {
1324                     node_type * pNext;
1325                     for ( node_type * pNode = pHead; pNode; pNode = pNext ) {
1326                         pNext = pNode->m_pNext;
1327                         pNode->clear();
1328                     }
1329
1330                     nSize = 0;
1331                     pHead = nullptr;
1332                 }
1333
1334                 template <typename Disposer>
1335                 void clear( Disposer disp )
1336                 {
1337                     node_type * pNext;
1338                     for ( node_type * pNode = pHead; pNode; pNode = pNext ) {
1339                         pNext = pNode->m_pNext;
1340                         pNode->clear();
1341                         disp( pNode );
1342                     }
1343
1344                     nSize = 0;
1345                     pHead = nullptr;
1346                 }
1347
1348                 unsigned int size() const
1349                 {
1350                     return nSize;
1351                 }
1352             };
1353
1354             template <typename Node, unsigned int Capacity>
1355             class bucket_entry<Node, cuckoo::vector<Capacity>>
1356             {
1357             public:
1358                 typedef Node                            node_type;
1359                 typedef cuckoo::vector_probeset_class   probeset_class;
1360                 typedef cuckoo::vector<Capacity>        probeset_type;
1361
1362                 static unsigned int const c_nCapacity = probeset_type::c_nCapacity;
1363
1364             protected:
1365                 node_type *     m_arrNode[c_nCapacity];
1366                 unsigned int    m_nSize;
1367
1368                 void shift_up( unsigned int nFrom )
1369                 {
1370                     assert( m_nSize < c_nCapacity );
1371
1372                     if ( nFrom < m_nSize )
1373                         std::copy_backward( m_arrNode + nFrom, m_arrNode + m_nSize, m_arrNode + m_nSize + 1 );
1374                 }
1375
1376                 void shift_down( node_type ** pFrom )
1377                 {
1378                     assert( m_arrNode <= pFrom && pFrom < m_arrNode + m_nSize);
1379                     std::copy( pFrom + 1, m_arrNode + m_nSize, pFrom );
1380                 }
1381             public:
1382                 class iterator
1383                 {
1384                     node_type **    pArr;
1385                     friend class bucket_entry;
1386
1387                 public:
1388                     iterator()
1389                         : pArr( nullptr )
1390                     {}
1391                     iterator( node_type ** p )
1392                         : pArr(p)
1393                     {}
1394                     iterator( iterator const& it)
1395                         : pArr( it.pArr )
1396                     {}
1397
1398                     iterator& operator=( iterator const& it )
1399                     {
1400                         pArr = it.pArr;
1401                         return *this;
1402                     }
1403
1404                     node_type * operator->()
1405                     {
1406                         assert( pArr != nullptr );
1407                         return *pArr;
1408                     }
1409                     node_type& operator*()
1410                     {
1411                         assert( pArr != nullptr );
1412                         assert( *pArr != nullptr );
1413                         return *(*pArr);
1414                     }
1415
1416                     // preinc
1417                     iterator& operator ++()
1418                     {
1419                         ++pArr;
1420                         return *this;
1421                     }
1422
1423                     bool operator==(iterator const& it ) const
1424                     {
1425                         return pArr == it.pArr;
1426                     }
1427                     bool operator!=(iterator const& it ) const
1428                     {
1429                         return !( *this == it );
1430                     }
1431                 };
1432
1433             public:
1434                 bucket_entry()
1435                     : m_nSize(0)
1436                 {
1437                     memset( m_arrNode, 0, sizeof(m_arrNode));
1438                     static_assert(( std::is_same<typename node_type::probeset_type, probeset_type>::value ), "Incompatible node type" );
1439                 }
1440
1441                 iterator begin()
1442                 {
1443                     return iterator(m_arrNode);
1444                 }
1445                 iterator end()
1446                 {
1447                     return iterator(m_arrNode + size());
1448                 }
1449
1450                 void insert_after( iterator it, node_type * p )
1451                 {
1452                     assert( m_nSize < c_nCapacity );
1453                     assert( !it.pArr || (m_arrNode <= it.pArr && it.pArr <= m_arrNode + m_nSize));
1454
1455                     if ( it.pArr ) {
1456                         shift_up( static_cast<unsigned int>(it.pArr - m_arrNode) + 1 );
1457                         it.pArr[1] = p;
1458                     }
1459                     else {
1460                         shift_up(0);
1461                         m_arrNode[0] = p;
1462                     }
1463                     ++m_nSize;
1464                 }
1465
1466                 void remove( iterator /*itPrev*/, iterator itWhat )
1467                 {
1468                     itWhat->clear();
1469                     shift_down( itWhat.pArr );
1470                     --m_nSize;
1471                 }
1472
1473                 void clear()
1474                 {
1475                     m_nSize = 0;
1476                 }
1477
1478                 template <typename Disposer>
1479                 void clear( Disposer disp )
1480                 {
1481                     for ( unsigned int i = 0; i < m_nSize; ++i ) {
1482                         disp( m_arrNode[i] );
1483                     }
1484                     m_nSize = 0;
1485                 }
1486
1487                 unsigned int size() const
1488                 {
1489                     return m_nSize;
1490                 }
1491             };
1492
1493             template <typename Node, unsigned int ArraySize>
1494             struct hash_ops {
1495                 static void store( Node * pNode, size_t * pHashes )
1496                 {
1497                     memcpy( pNode->m_arrHash, pHashes, sizeof(pHashes[0]) * ArraySize );
1498                 }
1499                 static bool equal_to( Node& node, unsigned int nTable, size_t nHash )
1500                 {
1501                     return node.m_arrHash[nTable] == nHash;
1502                 }
1503             };
1504             template <typename Node>
1505             struct hash_ops<Node, 0>
1506             {
1507                 static void store( Node * /*pNode*/, size_t * /*pHashes*/ )
1508                 {}
1509                 static bool equal_to( Node& /*node*/, unsigned int /*nTable*/, size_t /*nHash*/ )
1510                 {
1511                     return true;
1512                 }
1513             };
1514
1515             template <typename NodeTraits, bool Ordered>
1516             struct contains;
1517
1518             template <typename NodeTraits>
1519             struct contains<NodeTraits, true>
1520             {
1521                 template <typename BucketEntry, typename Position, typename Q, typename Compare>
1522                 static bool find( BucketEntry& probeset, Position& pos, unsigned int /*nTable*/, size_t /*nHash*/, Q const& val, Compare cmp )
1523                 {
1524                     // Ordered version
1525                     typedef typename BucketEntry::iterator bucket_iterator;
1526
1527                     bucket_iterator itPrev;
1528
1529                     for ( bucket_iterator it = probeset.begin(), itEnd = probeset.end(); it != itEnd; ++it ) {
1530                         int cmpRes = cmp( *NodeTraits::to_value_ptr(*it), val );
1531                         if ( cmpRes >= 0 ) {
1532                             pos.itFound = it;
1533                             pos.itPrev = itPrev;
1534                             return cmpRes == 0;
1535                         }
1536
1537                         itPrev = it;
1538                     }
1539
1540                     pos.itPrev = itPrev;
1541                     pos.itFound = probeset.end();
1542                     return false;
1543                 }
1544             };
1545
1546             template <typename NodeTraits>
1547             struct contains<NodeTraits, false>
1548             {
1549                 template <typename BucketEntry, typename Position, typename Q, typename EqualTo>
1550                 static bool find( BucketEntry& probeset, Position& pos, unsigned int nTable, size_t nHash, Q const& val, EqualTo eq )
1551                 {
1552                     // Unordered version
1553                     typedef typename BucketEntry::iterator  bucket_iterator;
1554                     typedef typename BucketEntry::node_type node_type;
1555
1556                     bucket_iterator itPrev;
1557
1558                     for ( bucket_iterator it = probeset.begin(), itEnd = probeset.end(); it != itEnd; ++it ) {
1559                         if ( hash_ops<node_type, node_type::hash_array_size>::equal_to( *it, nTable, nHash ) && eq( *NodeTraits::to_value_ptr(*it), val )) {
1560                             pos.itFound = it;
1561                             pos.itPrev = itPrev;
1562                             return true;
1563                         }
1564                         itPrev = it;
1565                     }
1566
1567                     pos.itPrev = itPrev;
1568                     pos.itFound = probeset.end();
1569                     return false;
1570                 }
1571             };
1572
1573         }   // namespace details
1574         //@endcond
1575
1576     } // namespace cuckoo
1577
1578     /// Cuckoo hash set
1579     /** @ingroup cds_intrusive_map
1580
1581         Source
1582             - [2007] M.Herlihy, N.Shavit, M.Tzafrir "Concurrent Cuckoo Hashing. Technical report"
1583             - [2008] Maurice Herlihy, Nir Shavit "The Art of Multiprocessor Programming"
1584
1585         <b>About Cuckoo hashing</b>
1586
1587             [From <i>"The Art of Multiprocessor Programming"</i>]
1588             Cuckoo hashing is a hashing algorithm in which a newly added item displaces any earlier item
1589             occupying the same slot. For brevity, a table is a k-entry array of items. For a hash set f size
1590             N = 2k we use a two-entry array of tables, and two independent hash functions,
1591             <tt> h0, h1: KeyRange -> 0,...,k-1</tt>
1592             mapping the set of possible keys to entries in he array. To test whether a value \p x is in the set,
1593             <tt>find(x)</tt> tests whether either <tt>table[0][h0(x)]</tt> or <tt>table[1][h1(x)]</tt> is
1594             equal to \p x. Similarly, <tt>erase(x)</tt>checks whether \p x is in either <tt>table[0][h0(x)]</tt>
1595             or <tt>table[1][h1(x)]</tt>, ad removes it if found.
1596
1597             The <tt>insert(x)</tt> successively "kicks out" conflicting items until every key has a slot.
1598             To add \p x, the method swaps \p x with \p y, the current occupant of <tt>table[0][h0(x)]</tt>.
1599             If the prior value was \p nullptr, it is done. Otherwise, it swaps the newly nest-less value \p y
1600             for the current occupant of <tt>table[1][h1(y)]</tt> in the same way. As before, if the prior value
1601             was \p nullptr, it is done. Otherwise, the method continues swapping entries (alternating tables)
1602             until it finds an empty slot. We might not find an empty slot, either because the table is full,
1603             or because the sequence of displacement forms a cycle. We therefore need an upper limit on the
1604             number of successive displacements we are willing to undertake. When this limit is exceeded,
1605             we resize the hash table, choose new hash functions and start over.
1606
1607             For concurrent cuckoo hashing, rather than organizing the set as a two-dimensional table of
1608             items, we use two-dimensional table of probe sets, where a probe set is a constant-sized set
1609             of items with the same hash code. Each probe set holds at most \p PROBE_SIZE items, but the algorithm
1610             tries to ensure that when the set is quiescent (i.e no method call in progress) each probe set
1611             holds no more than <tt>THRESHOLD < PROBE_SET</tt> items. While method calls are in-flight, a probe
1612             set may temporarily hold more than \p THRESHOLD but never more than \p PROBE_SET items.
1613
1614             In current implementation, a probe set can be defined either as a (single-linked) list
1615             or as a fixed-sized vector, optionally ordered.
1616
1617             In description above two-table cuckoo hashing (<tt>k = 2</tt>) has been considered.
1618             We can generalize this approach for <tt>k >= 2</tt> when we have \p k hash functions
1619             <tt>h[0], ... h[k-1]</tt> and \p k tables <tt>table[0], ... table[k-1]</tt>.
1620
1621             The search in probe set is linear, the complexity is <tt> O(PROBE_SET) </tt>.
1622             The probe set may be ordered or not. Ordered probe set can be more efficient since
1623             the average search complexity is <tt>O(PROBE_SET/2)</tt>.
1624             However, the overhead of sorting can eliminate a gain of ordered search.
1625
1626             The probe set is ordered if opt::compare or opt::less is specified in \p Traits template
1627             parameter. Otherwise, the probe set is unordered and \p Traits must contain
1628             opt::equal_to option.
1629
1630             The cds::intrusive::cuckoo namespace contains \p %CuckooSet-related declarations.
1631
1632         Template arguments:
1633         - \p T - the type stored in the set.  The type must be based on cuckoo::node (for cuckoo::base_hook)
1634             or it must have a member of type %cuckoo::node (for cuckoo::member_hook),
1635             or it must be convertible to \p %cuckoo::node (for cuckoo::traits_hook)
1636         - \p Traits - type traits, default is  cuckoo::traits. It is possible to declare option-based
1637             set with \p cuckoo::make_traits metafunction result as \p Traits template argument.
1638
1639         <b>How to use</b>
1640
1641         You should incorporate \p cuckoo::node into your struct \p T and provide
1642         appropriate \p cuckoo::traits::hook in your \p Traits template parameters.
1643         Usually, for \p Traits you define a struct based on \p cuckoo::traits.
1644
1645         Example for base hook and list-based probe-set:
1646         \code
1647         #include <cds/intrusive/cuckoo_set.h>
1648
1649         // Data stored in cuckoo set
1650         // We use list as probe-set container and store hash values in the node
1651         // (since we use two hash functions we should store 2 hash values per node)
1652         struct my_data: public cds::intrusive::cuckoo::node< cds::intrusive::cuckoo::list, 2 >
1653         {
1654             // key field
1655             std::string     strKey;
1656
1657             // other data
1658             // ...
1659         };
1660
1661         // Provide equal_to functor for my_data since we will use unordered probe-set
1662         struct my_data_equal_to {
1663             bool operator()( const my_data& d1, const my_data& d2 ) const
1664             {
1665                 return d1.strKey.compare( d2.strKey ) == 0;
1666             }
1667
1668             bool operator()( const my_data& d, const std::string& s ) const
1669             {
1670                 return d.strKey.compare(s) == 0;
1671             }
1672
1673             bool operator()( const std::string& s, const my_data& d ) const
1674             {
1675                 return s.compare( d.strKey ) == 0;
1676             }
1677         };
1678
1679         // Provide two hash functor for my_data
1680         struct hash1 {
1681             size_t operator()(std::string const& s) const
1682             {
1683                 return cds::opt::v::hash<std::string>( s );
1684             }
1685             size_t operator()( my_data const& d ) const
1686             {
1687                 return (*this)( d.strKey );
1688             }
1689         };
1690
1691         struct hash2: private hash1 {
1692             size_t operator()(std::string const& s) const
1693             {
1694                 size_t h = ~( hash1::operator()(s));
1695                 return ~h + 0x9e3779b9 + (h << 6) + (h >> 2);
1696             }
1697             size_t operator()( my_data const& d ) const
1698             {
1699                 return (*this)( d.strKey );
1700             }
1701         };
1702
1703         // Declare type traits
1704         struct my_traits: public cds::intrusive::cuckoo::traits
1705         {
1706             typedef cds::intrusive::cuckoo::base_hook<
1707                 cds::intrusive::cuckoo::probeset_type< my_data::probeset_type >
1708                 ,cds::intrusive::cuckoo::store_hash< my_data::hash_array_size >
1709             >   hook;
1710             typedef my_data_equa_to equal_to;
1711             typedef cds::opt::hash_tuple< hash1, hash2 > hash;
1712         };
1713
1714         // Declare CuckooSet type
1715         typedef cds::intrusive::CuckooSet< my_data, my_traits > my_cuckoo_set;
1716
1717         // Equal option-based declaration
1718         typedef cds::intrusive::CuckooSet< my_data,
1719             cds::intrusive::cuckoo::make_traits<
1720                 cds::intrusive::opt::hook< cds::intrusive::cuckoo::base_hook<
1721                     cds::intrusive::cuckoo::probeset_type< my_data::probeset_type >
1722                     ,cds::intrusive::cuckoo::store_hash< my_data::hash_array_size >
1723                 > >
1724                 ,cds::opt::hash< std::tuple< hash1, hash2 > >
1725                 ,cds::opt::equal_to< my_data_equal_to >
1726             >::type
1727         > opt_cuckoo_set;
1728         \endcode
1729
1730         If we provide \p compare function instead of \p equal_to for \p my_data
1731         we get as a result a cuckoo set with ordered probe set that may improve
1732         performance.
1733         Example for base hook and ordered vector-based probe-set:
1734
1735         \code
1736         #include <cds/intrusive/cuckoo_set.h>
1737
1738         // Data stored in cuckoo set
1739         // We use a vector of capacity 4 as probe-set container and store hash values in the node
1740         // (since we use two hash functions we should store 2 hash values per node)
1741         struct my_data: public cds::intrusive::cuckoo::node< cds::intrusive::cuckoo::vector<4>, 2 >
1742         {
1743             // key field
1744             std::string     strKey;
1745
1746             // other data
1747             // ...
1748         };
1749
1750         // Provide compare functor for my_data since we want to use ordered probe-set
1751         struct my_data_compare {
1752             int operator()( const my_data& d1, const my_data& d2 ) const
1753             {
1754                 return d1.strKey.compare( d2.strKey );
1755             }
1756
1757             int operator()( const my_data& d, const std::string& s ) const
1758             {
1759                 return d.strKey.compare(s);
1760             }
1761
1762             int operator()( const std::string& s, const my_data& d ) const
1763             {
1764                 return s.compare( d.strKey );
1765             }
1766         };
1767
1768         // Provide two hash functor for my_data
1769         struct hash1 {
1770             size_t operator()(std::string const& s) const
1771             {
1772                 return cds::opt::v::hash<std::string>( s );
1773             }
1774             size_t operator()( my_data const& d ) const
1775             {
1776                 return (*this)( d.strKey );
1777             }
1778         };
1779
1780         struct hash2: private hash1 {
1781             size_t operator()(std::string const& s) const
1782             {
1783                 size_t h = ~( hash1::operator()(s));
1784                 return ~h + 0x9e3779b9 + (h << 6) + (h >> 2);
1785             }
1786             size_t operator()( my_data const& d ) const
1787             {
1788                 return (*this)( d.strKey );
1789             }
1790         };
1791
1792         // Declare type traits
1793         struct my_traits: public cds::intrusive::cuckoo::traits
1794         {
1795             typedef cds::intrusive::cuckoo::base_hook<
1796                 cds::intrusive::cuckoo::probeset_type< my_data::probeset_type >
1797                 ,cds::intrusive::cuckoo::store_hash< my_data::hash_array_size >
1798             >   hook;
1799             typedef my_data_compare compare;
1800             typedef cds::opt::hash_tuple< hash1, hash2 > hash;
1801         };
1802
1803         // Declare CuckooSet type
1804         typedef cds::intrusive::CuckooSet< my_data, my_traits > my_cuckoo_set;
1805
1806         // Equal option-based declaration
1807         typedef cds::intrusive::CuckooSet< my_data,
1808             cds::intrusive::cuckoo::make_traits<
1809                 cds::intrusive::opt::hook< cds::intrusive::cuckoo::base_hook<
1810                     cds::intrusive::cuckoo::probeset_type< my_data::probeset_type >
1811                     ,cds::intrusive::cuckoo::store_hash< my_data::hash_array_size >
1812                 > >
1813                 ,cds::opt::hash< std::tuple< hash1, hash2 > >
1814                 ,cds::opt::compare< my_data_compare >
1815             >::type
1816         > opt_cuckoo_set;
1817         \endcode
1818
1819     */
1820     template <typename T, typename Traits = cuckoo::traits>
1821     class CuckooSet
1822     {
1823     public:
1824         typedef T   value_type;   ///< The value type stored in the set
1825         typedef Traits traits;    ///< Set traits
1826
1827         typedef typename traits::hook       hook;        ///< hook type
1828         typedef typename hook::node_type    node_type;   ///< node type
1829         typedef typename get_node_traits< value_type, node_type, hook>::type node_traits;    ///< node traits
1830
1831         typedef typename traits::hash          hash;   ///< hash functor tuple wrapped for internal use
1832         typedef typename hash::hash_tuple_type hash_tuple_type; ///< Type of hash tuple
1833
1834         typedef typename traits::stat          stat;   ///< internal statistics type
1835
1836         typedef typename traits::mutex_policy  original_mutex_policy; ///< Concurrent access policy, see \p cuckoo::traits::mutex_policy
1837
1838         /// Actual mutex policy
1839         /**
1840             Actual mutex policy is built from mutex policy type provided by \p Traits template argument (see \p cuckoo::traits::mutex_policy)
1841             but mutex policy internal statistics is conformed with \p cukoo::traits::stat type provided by \p Traits:
1842             - if \p %cuckoo::traits::stat is \p cuckoo::empty_stat then mutex policy statistics is already empty
1843             - otherwise real mutex policy statistics is used
1844         */
1845         typedef typename original_mutex_policy::template rebind_statistics<
1846             typename std::conditional<
1847                 std::is_same< stat, cuckoo::empty_stat >::value
1848                 ,typename original_mutex_policy::empty_stat
1849                 ,typename original_mutex_policy::real_stat
1850             >::type
1851         >::other    mutex_policy;
1852
1853         static bool const c_isSorted = !( std::is_same< typename traits::compare, opt::none >::value
1854                 && std::is_same< typename traits::less, opt::none >::value ) ; ///< whether the probe set should be ordered
1855         static size_t const c_nArity = hash::size ; ///< the arity of cuckoo hashing: the number of hash functors provided; minimum 2.
1856
1857         /// Key equality functor; used only for unordered probe-set
1858         typedef typename opt::details::make_equal_to< value_type, traits, !c_isSorted>::type key_equal_to;
1859
1860         /// key comparing functor based on opt::compare and opt::less option setter. Used only for ordered probe set
1861         typedef typename opt::details::make_comparator< value_type, traits >::type key_comparator;
1862
1863         /// allocator type
1864         typedef typename traits::allocator     allocator;
1865
1866         /// item counter type
1867         typedef typename traits::item_counter  item_counter;
1868
1869         /// node disposer
1870         typedef typename traits::disposer      disposer;
1871
1872     protected:
1873         //@cond
1874         typedef typename node_type::probeset_class  probeset_class;
1875         typedef typename node_type::probeset_type   probeset_type;
1876         static unsigned int const c_nNodeHashArraySize = node_type::hash_array_size;
1877
1878         typedef typename mutex_policy::scoped_cell_lock     scoped_cell_lock;
1879         typedef typename mutex_policy::scoped_cell_trylock  scoped_cell_trylock;
1880         typedef typename mutex_policy::scoped_full_lock     scoped_full_lock;
1881         typedef typename mutex_policy::scoped_resize_lock   scoped_resize_lock;
1882
1883         typedef cuckoo::details::bucket_entry< node_type, probeset_type >   bucket_entry;
1884         typedef typename bucket_entry::iterator                     bucket_iterator;
1885         typedef cds::details::Allocator< bucket_entry, allocator >  bucket_table_allocator;
1886
1887         typedef size_t  hash_array[c_nArity]    ;   ///< hash array
1888
1889         struct position {
1890             bucket_iterator     itPrev;
1891             bucket_iterator     itFound;
1892         };
1893
1894         typedef cuckoo::details::contains< node_traits, c_isSorted > contains_action;
1895
1896         template <typename Predicate>
1897         struct predicate_wrapper {
1898             typedef typename std::conditional< c_isSorted, cds::opt::details::make_comparator_from_less<Predicate>, Predicate>::type   type;
1899         };
1900
1901         typedef typename std::conditional< c_isSorted, key_comparator, key_equal_to >::type key_predicate;
1902         //@endcond
1903
1904     public:
1905         static unsigned int const   c_nDefaultProbesetSize = 4;   ///< default probeset size
1906         static size_t const         c_nDefaultInitialSize = 16;   ///< default initial size
1907         static unsigned int const   c_nRelocateLimit = c_nArity * 2 - 1; ///< Count of attempts to relocate before giving up
1908
1909     protected:
1910         bucket_entry *      m_BucketTable[ c_nArity ] ; ///< Bucket tables
1911
1912         size_t              m_nBucketMask           ;   ///< Hash bitmask; bucket table size minus 1.
1913         unsigned int const  m_nProbesetSize         ;   ///< Probe set size
1914         unsigned int const  m_nProbesetThreshold    ;   ///< Probe set threshold
1915
1916         hash            m_Hash              ;   ///< Hash functor tuple
1917         mutex_policy    m_MutexPolicy       ;   ///< concurrent access policy
1918         item_counter    m_ItemCounter       ;   ///< item counter
1919         mutable stat    m_Stat              ;   ///< internal statistics
1920
1921     protected:
1922         //@cond
1923         static void check_common_constraints()
1924         {
1925             static_assert( (c_nArity == mutex_policy::c_nArity), "The count of hash functors must be equal to mutex_policy arity" );
1926         }
1927
1928         void check_probeset_properties() const
1929         {
1930             assert( m_nProbesetThreshold < m_nProbesetSize );
1931
1932             // if probe set type is cuckoo::vector<N> then m_nProbesetSize == N
1933             assert( node_type::probeset_size == 0 || node_type::probeset_size == m_nProbesetSize );
1934         }
1935
1936         template <typename Q>
1937         void hashing( size_t * pHashes, Q const& v ) const
1938         {
1939             m_Hash( pHashes, v );
1940         }
1941
1942         void copy_hash( size_t * pHashes, value_type const& v ) const
1943         {
1944             if ( c_nNodeHashArraySize )
1945                 memcpy( pHashes, node_traits::to_node_ptr( v )->get_hash(), sizeof(pHashes[0]) * c_nNodeHashArraySize );
1946             else
1947                 hashing( pHashes, v );
1948         }
1949
1950         bucket_entry& bucket( unsigned int nTable, size_t nHash )
1951         {
1952             assert( nTable < c_nArity );
1953             return m_BucketTable[nTable][nHash & m_nBucketMask];
1954         }
1955
1956         static void store_hash( node_type * pNode, size_t * pHashes )
1957         {
1958             cuckoo::details::hash_ops< node_type, c_nNodeHashArraySize >::store( pNode, pHashes );
1959         }
1960
1961         static bool equal_hash( node_type& node, unsigned int nTable, size_t nHash )
1962         {
1963             return cuckoo::details::hash_ops< node_type, c_nNodeHashArraySize >::equal_to( node, nTable, nHash );
1964         }
1965
1966         void allocate_bucket_tables( size_t nSize )
1967         {
1968             assert( cds::beans::is_power2( nSize ) );
1969
1970             m_nBucketMask = nSize - 1;
1971             bucket_table_allocator alloc;
1972             for ( unsigned int i = 0; i < c_nArity; ++i )
1973                 m_BucketTable[i] = alloc.NewArray( nSize );
1974         }
1975
1976         static void free_bucket_tables( bucket_entry ** pTable, size_t nCapacity )
1977         {
1978             bucket_table_allocator alloc;
1979             for ( unsigned int i = 0; i < c_nArity; ++i ) {
1980                 alloc.Delete( pTable[i], nCapacity );
1981                 pTable[i] = nullptr;
1982             }
1983         }
1984         void free_bucket_tables()
1985         {
1986             free_bucket_tables( m_BucketTable, m_nBucketMask + 1 );
1987         }
1988
1989         static CDS_CONSTEXPR unsigned int const c_nUndefTable = (unsigned int) -1;
1990         template <typename Q, typename Predicate >
1991         unsigned int contains( position * arrPos, size_t * arrHash, Q const& val, Predicate pred )
1992         {
1993             // Buckets must be locked
1994
1995             for ( unsigned int i = 0; i < c_nArity; ++i ) {
1996                 bucket_entry& probeset = bucket( i, arrHash[i] );
1997                 if ( contains_action::find( probeset, arrPos[i], i, arrHash[i], val, pred ))
1998                     return i;
1999             }
2000             return c_nUndefTable;
2001         }
2002
2003         template <typename Q, typename Predicate, typename Func>
2004         value_type * erase_( Q const& val, Predicate pred, Func f )
2005         {
2006             hash_array arrHash;
2007             hashing( arrHash, val );
2008             position arrPos[ c_nArity ];
2009
2010             {
2011                 scoped_cell_lock guard( m_MutexPolicy, arrHash );
2012
2013                 unsigned int nTable = contains( arrPos, arrHash, val, pred );
2014                 if ( nTable != c_nUndefTable ) {
2015                     node_type& node = *arrPos[nTable].itFound;
2016                     f( *node_traits::to_value_ptr(node) );
2017                     bucket( nTable, arrHash[nTable]).remove( arrPos[nTable].itPrev, arrPos[nTable].itFound );
2018                     --m_ItemCounter;
2019                     m_Stat.onEraseSuccess();
2020                     return node_traits::to_value_ptr( node );
2021                 }
2022             }
2023
2024             m_Stat.onEraseFailed();
2025             return nullptr;
2026         }
2027
2028         template <typename Q, typename Predicate, typename Func>
2029         bool find_( Q& val, Predicate pred, Func f )
2030         {
2031             hash_array arrHash;
2032             position arrPos[ c_nArity ];
2033             hashing( arrHash, val );
2034             scoped_cell_lock sl( m_MutexPolicy, arrHash );
2035
2036             unsigned int nTable = contains( arrPos, arrHash, val, pred );
2037             if ( nTable != c_nUndefTable ) {
2038                 f( *node_traits::to_value_ptr( *arrPos[nTable].itFound ), val );
2039                 m_Stat.onFindSuccess();
2040                 return true;
2041             }
2042
2043             m_Stat.onFindFailed();
2044             return false;
2045         }
2046
2047         bool relocate( unsigned int nTable, size_t * arrGoalHash )
2048         {
2049             // arrGoalHash contains hash values for relocating element
2050             // Relocating element is first one from bucket( nTable, arrGoalHash[nTable] ) probeset
2051
2052             m_Stat.onRelocateCall();
2053
2054             hash_array arrHash;
2055             value_type * pVal;
2056             for ( unsigned int nRound = 0; nRound < c_nRelocateLimit; ++nRound ) {
2057                 m_Stat.onRelocateRound();
2058
2059                 while ( true ) {
2060                     scoped_cell_lock guard( m_MutexPolicy, arrGoalHash );
2061
2062                     bucket_entry& refBucket = bucket( nTable, arrGoalHash[nTable] );
2063                     if ( refBucket.size() < m_nProbesetThreshold ) {
2064                         // probeset is not above the threshold
2065                         m_Stat.onFalseRelocateRound();
2066                         return true;
2067                     }
2068
2069                     pVal = node_traits::to_value_ptr( *refBucket.begin() );
2070                     copy_hash( arrHash, *pVal );
2071
2072                     scoped_cell_trylock guard2( m_MutexPolicy, arrHash );
2073                     if ( !guard2.locked() )
2074                         continue ;  // try one more time
2075
2076                     refBucket.remove( typename bucket_entry::iterator(), refBucket.begin() );
2077
2078                     unsigned int i = (nTable + 1) % c_nArity;
2079
2080                     // try insert into free probeset
2081                     while ( i != nTable ) {
2082                         bucket_entry& bkt = bucket( i, arrHash[i] );
2083                         if ( bkt.size() < m_nProbesetThreshold ) {
2084                             position pos;
2085                             contains_action::find( bkt, pos, i, arrHash[i], *pVal, key_predicate() ) ; // must return false!
2086                             bkt.insert_after( pos.itPrev, node_traits::to_node_ptr( pVal ));
2087                             m_Stat.onSuccessRelocateRound();
2088                             return true;
2089                         }
2090                         i = ( i + 1 ) % c_nArity;
2091                     }
2092
2093                     // try insert into partial probeset
2094                     i = (nTable + 1) % c_nArity;
2095                     while ( i != nTable ) {
2096                         bucket_entry& bkt = bucket( i, arrHash[i] );
2097                         if ( bkt.size() < m_nProbesetSize ) {
2098                             position pos;
2099                             contains_action::find( bkt, pos, i, arrHash[i], *pVal, key_predicate() ) ; // must return false!
2100                             bkt.insert_after( pos.itPrev, node_traits::to_node_ptr( pVal ));
2101                             nTable = i;
2102                             memcpy( arrGoalHash, arrHash, sizeof(arrHash));
2103                             m_Stat.onRelocateAboveThresholdRound();
2104                             goto next_iteration;
2105                         }
2106                         i = (i + 1) % c_nArity;
2107                     }
2108
2109                     // all probeset is full, relocating fault
2110                     refBucket.insert_after( typename bucket_entry::iterator(), node_traits::to_node_ptr( pVal ));
2111                     m_Stat.onFailedRelocate();
2112                     return false;
2113                 }
2114
2115             next_iteration:;
2116             }
2117             return false;
2118         }
2119
2120         void resize()
2121         {
2122             m_Stat.onResizeCall();
2123
2124             size_t nOldCapacity = bucket_count();
2125             bucket_entry *      pOldTable[ c_nArity ];
2126             {
2127                 scoped_resize_lock guard( m_MutexPolicy );
2128
2129                 if ( nOldCapacity != bucket_count() ) {
2130                     m_Stat.onFalseResizeCall();
2131                     return;
2132                 }
2133
2134                 size_t nCapacity = nOldCapacity * 2;
2135
2136                 m_MutexPolicy.resize( nCapacity );
2137                 memcpy( pOldTable, m_BucketTable, sizeof(pOldTable));
2138                 allocate_bucket_tables( nCapacity );
2139
2140                 typedef typename bucket_entry::iterator bucket_iterator;
2141                 hash_array arrHash;
2142                 position arrPos[ c_nArity ];
2143
2144                 for ( unsigned int nTable = 0; nTable < c_nArity; ++nTable ) {
2145                     bucket_entry * pTable = pOldTable[nTable];
2146                     for ( size_t k = 0; k < nOldCapacity; ++k ) {
2147                         bucket_iterator itNext;
2148                         for ( bucket_iterator it = pTable[k].begin(), itEnd = pTable[k].end(); it != itEnd; it = itNext ) {
2149                             itNext = it;
2150                             ++itNext;
2151
2152                             value_type& val = *node_traits::to_value_ptr( *it );
2153                             copy_hash( arrHash, val );
2154                             contains( arrPos, arrHash, val, key_predicate() ) ; // must return c_nUndefTable
2155
2156                             for ( unsigned int i = 0; i < c_nArity; ++i ) {
2157                                 bucket_entry& refBucket = bucket( i, arrHash[i] );
2158                                 if ( refBucket.size() < m_nProbesetThreshold ) {
2159                                     refBucket.insert_after( arrPos[i].itPrev, &*it );
2160                                     m_Stat.onResizeSuccessMove();
2161                                     goto do_next;
2162                                 }
2163                             }
2164
2165                             for ( unsigned int i = 0; i < c_nArity; ++i ) {
2166                                 bucket_entry& refBucket = bucket( i, arrHash[i] );
2167                                 if ( refBucket.size() < m_nProbesetSize ) {
2168                                     refBucket.insert_after( arrPos[i].itPrev, &*it );
2169                                     assert( refBucket.size() > 1 );
2170                                     copy_hash( arrHash, *node_traits::to_value_ptr( *refBucket.begin()) );
2171                                     m_Stat.onResizeRelocateCall();
2172                                     relocate( i, arrHash );
2173                                     break;
2174                                 }
2175                             }
2176                         do_next:;
2177                         }
2178                     }
2179                 }
2180             }
2181             free_bucket_tables( pOldTable, nOldCapacity );
2182         }
2183
2184         CDS_CONSTEXPR static unsigned int calc_probeset_size( unsigned int nProbesetSize ) CDS_NOEXCEPT
2185         {
2186             return std::is_same< probeset_class, cuckoo::vector_probeset_class >::value
2187                 ? node_type::probeset_size
2188                 : (nProbesetSize
2189                     ? nProbesetSize
2190                     : ( node_type::probeset_size ? node_type::probeset_size : c_nDefaultProbesetSize ));
2191         }
2192         //@endcond
2193
2194     public:
2195         /// Default constructor
2196         /**
2197             Initial size = \ref c_nDefaultInitialSize
2198
2199             Probe set size:
2200             - \p c_nDefaultProbesetSize if \p probeset_type is \p cuckoo::list
2201             - \p Capacity if \p probeset_type is <tt> cuckoo::vector<Capacity> </tt>
2202
2203             Probe set threshold = probe set size - 1
2204         */
2205         CuckooSet()
2206             : m_nProbesetSize( calc_probeset_size(0) )
2207             , m_nProbesetThreshold( m_nProbesetSize - 1 )
2208             , m_MutexPolicy( c_nDefaultInitialSize )
2209         {
2210             check_common_constraints();
2211             check_probeset_properties();
2212
2213             allocate_bucket_tables( c_nDefaultInitialSize );
2214         }
2215
2216         /// Constructs the set object with given probe set size and threshold
2217         /**
2218             If probe set type is <tt> cuckoo::vector<Capacity> </tt> vector
2219             then \p nProbesetSize is ignored since it should be equal to vector's \p Capacity.
2220         */
2221         CuckooSet(
2222             size_t nInitialSize                 ///< Initial set size; if 0 - use default initial size \ref c_nDefaultInitialSize
2223             , unsigned int nProbesetSize        ///< probe set size
2224             , unsigned int nProbesetThreshold = 0   ///< probe set threshold, <tt>nProbesetThreshold < nProbesetSize</tt>. If 0, nProbesetThreshold = nProbesetSize - 1
2225         )
2226             : m_nProbesetSize( calc_probeset_size(nProbesetSize) )
2227             , m_nProbesetThreshold( nProbesetThreshold ? nProbesetThreshold : m_nProbesetSize - 1 )
2228             , m_MutexPolicy( cds::beans::ceil2(nInitialSize ? nInitialSize : c_nDefaultInitialSize ))
2229         {
2230             check_common_constraints();
2231             check_probeset_properties();
2232
2233             allocate_bucket_tables( nInitialSize ? cds::beans::ceil2( nInitialSize ) : c_nDefaultInitialSize );
2234         }
2235
2236         /// Constructs the set object with given hash functor tuple
2237         /**
2238             The probe set size and threshold are set as default, see CuckooSet()
2239         */
2240         CuckooSet(
2241             hash_tuple_type const& h    ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
2242         )
2243             : m_nProbesetSize( calc_probeset_size(0) )
2244             , m_nProbesetThreshold( m_nProbesetSize -1 )
2245             , m_Hash( h )
2246             , m_MutexPolicy( c_nDefaultInitialSize )
2247         {
2248             check_common_constraints();
2249             check_probeset_properties();
2250
2251             allocate_bucket_tables( c_nDefaultInitialSize );
2252         }
2253
2254         /// Constructs the set object with given probe set properties and hash functor tuple
2255         /**
2256             If probe set type is <tt> cuckoo::vector<Capacity> </tt> vector
2257             then \p nProbesetSize should be equal to vector's \p Capacity.
2258         */
2259         CuckooSet(
2260             size_t nInitialSize                 ///< Initial set size; if 0 - use default initial size \ref c_nDefaultInitialSize
2261             , unsigned int nProbesetSize        ///< probe set size, positive integer
2262             , unsigned int nProbesetThreshold   ///< probe set threshold, <tt>nProbesetThreshold < nProbesetSize</tt>. If 0, nProbesetThreshold = nProbesetSize - 1
2263             , hash_tuple_type const& h    ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
2264         )
2265             : m_nProbesetSize( calc_probeset_size(nProbesetSize) )
2266             , m_nProbesetThreshold( nProbesetThreshold ? nProbesetThreshold : m_nProbesetSize - 1)
2267             , m_Hash( h )
2268             , m_MutexPolicy( cds::beans::ceil2(nInitialSize ? nInitialSize : c_nDefaultInitialSize ))
2269         {
2270             check_common_constraints();
2271             check_probeset_properties();
2272
2273             allocate_bucket_tables( nInitialSize ? cds::beans::ceil2( nInitialSize ) : c_nDefaultInitialSize );
2274         }
2275
2276         /// Constructs the set object with given hash functor tuple (move semantics)
2277         /**
2278             The probe set size and threshold are set as default, see CuckooSet()
2279         */
2280         CuckooSet(
2281             hash_tuple_type&& h     ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
2282         )
2283             : m_nProbesetSize( calc_probeset_size(0) )
2284             , m_nProbesetThreshold( m_nProbesetSize / 2 )
2285             , m_Hash( std::forward<hash_tuple_type>(h) )
2286             , m_MutexPolicy( c_nDefaultInitialSize )
2287         {
2288             check_common_constraints();
2289             check_probeset_properties();
2290
2291             allocate_bucket_tables( c_nDefaultInitialSize );
2292         }
2293
2294         /// Constructs the set object with given probe set properties and hash functor tuple (move semantics)
2295         /**
2296             If probe set type is <tt> cuckoo::vector<Capacity> </tt> vector
2297             then \p nProbesetSize should be equal to vector's \p Capacity.
2298         */
2299         CuckooSet(
2300             size_t nInitialSize                 ///< Initial set size; if 0 - use default initial size \ref c_nDefaultInitialSize
2301             , unsigned int nProbesetSize        ///< probe set size, positive integer
2302             , unsigned int nProbesetThreshold   ///< probe set threshold, <tt>nProbesetThreshold < nProbesetSize</tt>. If 0, nProbesetThreshold = nProbesetSize - 1
2303             , hash_tuple_type&& h    ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
2304         )
2305             : m_nProbesetSize( calc_probeset_size(nProbesetSize) )
2306             , m_nProbesetThreshold( nProbesetThreshold ? nProbesetThreshold : m_nProbesetSize - 1)
2307             , m_Hash( std::forward<hash_tuple_type>(h) )
2308             , m_MutexPolicy( cds::beans::ceil2(nInitialSize ? nInitialSize : c_nDefaultInitialSize ))
2309         {
2310             check_common_constraints();
2311             check_probeset_properties();
2312
2313             allocate_bucket_tables( nInitialSize ? cds::beans::ceil2( nInitialSize ) : c_nDefaultInitialSize );
2314         }
2315
2316         /// Destructor
2317         ~CuckooSet()
2318         {
2319             free_bucket_tables();
2320         }
2321
2322     public:
2323         /// Inserts new node
2324         /**
2325             The function inserts \p val in the set if it does not contain
2326             an item with key equal to \p val.
2327
2328             Returns \p true if \p val is placed into the set, \p false otherwise.
2329         */
2330         bool insert( value_type& val )
2331         {
2332             return insert( val, []( value_type& ) {} );
2333         }
2334
2335         /// Inserts new node
2336         /**
2337             The function allows to split creating of new item into two part:
2338             - create item with key only
2339             - insert new item into the set
2340             - if inserting is success, calls  \p f functor to initialize value-field of \p val.
2341
2342             The functor signature is:
2343             \code
2344                 void func( value_type& val );
2345             \endcode
2346             where \p val is the item inserted.
2347
2348             The user-defined functor is called only if the inserting is success.
2349         */
2350         template <typename Func>
2351         bool insert( value_type& val, Func f )
2352         {
2353             hash_array arrHash;
2354             position arrPos[ c_nArity ];
2355             unsigned int nGoalTable;
2356
2357             hashing( arrHash, val );
2358             node_type * pNode = node_traits::to_node_ptr( val );
2359             store_hash( pNode, arrHash );
2360
2361             while (true) {
2362                 {
2363                     scoped_cell_lock guard( m_MutexPolicy, arrHash );
2364
2365                     if ( contains( arrPos, arrHash, val, key_predicate() ) != c_nUndefTable ) {
2366                         m_Stat.onInsertFailed();
2367                         return false;
2368                     }
2369
2370                     for ( unsigned int i = 0; i < c_nArity; ++i ) {
2371                         bucket_entry& refBucket = bucket( i, arrHash[i] );
2372                         if ( refBucket.size() < m_nProbesetThreshold ) {
2373                             refBucket.insert_after( arrPos[i].itPrev, pNode );
2374                             f( val );
2375                             ++m_ItemCounter;
2376                             m_Stat.onInsertSuccess();
2377                             return true;
2378                         }
2379                     }
2380
2381                     for ( unsigned int i = 0; i < c_nArity; ++i ) {
2382                         bucket_entry& refBucket = bucket( i, arrHash[i] );
2383                         if ( refBucket.size() < m_nProbesetSize ) {
2384                             refBucket.insert_after( arrPos[i].itPrev, pNode );
2385                             f( val );
2386                             ++m_ItemCounter;
2387                             nGoalTable = i;
2388                             assert( refBucket.size() > 1 );
2389                             copy_hash( arrHash, *node_traits::to_value_ptr( *refBucket.begin()) );
2390                             goto do_relocate;
2391                         }
2392                     }
2393                 }
2394
2395                 m_Stat.onInsertResize();
2396                 resize();
2397             }
2398
2399         do_relocate:
2400             m_Stat.onInsertRelocate();
2401             if ( !relocate( nGoalTable, arrHash )) {
2402                 m_Stat.onInsertRelocateFault();
2403                 m_Stat.onInsertResize();
2404                 resize();
2405             }
2406
2407             m_Stat.onInsertSuccess();
2408             return true;
2409         }
2410
2411         /// Updates the node
2412         /**
2413             The operation performs inserting or changing data with lock-free manner.
2414
2415             If the item \p val is not found in the set, then \p val is inserted into the set
2416             iff \p bAllowInsert is \p true.
2417             Otherwise, the functor \p func is called with item found.
2418             The functor \p func signature is:
2419             \code
2420                 void func( bool bNew, value_type& item, value_type& val );
2421             \endcode
2422             with arguments:
2423             - \p bNew - \p true if the item has been inserted, \p false otherwise
2424             - \p item - item of the set
2425             - \p val - argument \p val passed into the \p %update() function
2426             If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
2427             refer to the same thing.
2428
2429             The functor may change non-key fields of the \p item.
2430
2431             Returns std::pair<bool, bool> where \p first is \p true if operation is successfull,
2432             i.e. the node has been inserted or updated,
2433             \p second is \p true if new item has been added or \p false if the item with \p key
2434             already exists.
2435         */
2436         template <typename Func>
2437         std::pair<bool, bool> update( value_type& val, Func func, bool bAllowInsert = true )
2438         {
2439             hash_array arrHash;
2440             position arrPos[ c_nArity ];
2441             unsigned int nGoalTable;
2442
2443             hashing( arrHash, val );
2444             node_type * pNode = node_traits::to_node_ptr( val );
2445             store_hash( pNode, arrHash );
2446
2447             while (true) {
2448                 {
2449                     scoped_cell_lock guard( m_MutexPolicy, arrHash );
2450
2451                     unsigned int nTable = contains( arrPos, arrHash, val, key_predicate() );
2452                     if ( nTable != c_nUndefTable ) {
2453                         func( false, *node_traits::to_value_ptr( *arrPos[nTable].itFound ), val );
2454                         m_Stat.onUpdateExist();
2455                         return std::make_pair( true, false );
2456                     }
2457
2458                     if ( !bAllowInsert )
2459                         return std::make_pair( false, false );
2460
2461                     //node_type * pNode = node_traits::to_node_ptr( val );
2462                     //store_hash( pNode, arrHash );
2463
2464                     for ( unsigned int i = 0; i < c_nArity; ++i ) {
2465                         bucket_entry& refBucket = bucket( i, arrHash[i] );
2466                         if ( refBucket.size() < m_nProbesetThreshold ) {
2467                             refBucket.insert_after( arrPos[i].itPrev, pNode );
2468                             func( true, val, val );
2469                             ++m_ItemCounter;
2470                             m_Stat.onUpdateSuccess();
2471                             return std::make_pair( true, true );
2472                         }
2473                     }
2474
2475                     for ( unsigned int i = 0; i < c_nArity; ++i ) {
2476                         bucket_entry& refBucket = bucket( i, arrHash[i] );
2477                         if ( refBucket.size() < m_nProbesetSize ) {
2478                             refBucket.insert_after( arrPos[i].itPrev, pNode );
2479                             func( true, val, val );
2480                             ++m_ItemCounter;
2481                             nGoalTable = i;
2482                             assert( refBucket.size() > 1 );
2483                             copy_hash( arrHash, *node_traits::to_value_ptr( *refBucket.begin()) );
2484                             goto do_relocate;
2485                         }
2486                     }
2487                 }
2488
2489                 m_Stat.onUpdateResize();
2490                 resize();
2491             }
2492
2493         do_relocate:
2494             m_Stat.onUpdateRelocate();
2495             if ( !relocate( nGoalTable, arrHash )) {
2496                 m_Stat.onUpdateRelocateFault();
2497                 m_Stat.onUpdateResize();
2498                 resize();
2499             }
2500
2501             m_Stat.onUpdateSuccess();
2502             return std::make_pair( true, true );
2503         }
2504         //@cond
2505         template <typename Func>
2506         CDS_DEPRECATED("ensure() is deprecated, use update()")
2507         std::pair<bool, bool> ensure( value_type& val, Func func )
2508         {
2509             return update( val, func, true );
2510         }
2511         //@endcond
2512
2513         /// Unlink the item \p val from the set
2514         /**
2515             The function searches the item \p val in the set and unlink it
2516             if it is found and is equal to \p val (here, the equality means that
2517             \p val belongs to the set: if \p item is an item found then
2518             unlink is successful iif <tt>&val == &item</tt>)
2519
2520             The function returns \p true if success and \p false otherwise.
2521         */
2522         bool unlink( value_type& val )
2523         {
2524             hash_array arrHash;
2525             hashing( arrHash, val );
2526             position arrPos[ c_nArity ];
2527
2528             {
2529                 scoped_cell_lock guard( m_MutexPolicy, arrHash );
2530
2531                 unsigned int nTable = contains( arrPos, arrHash, val, key_predicate() );
2532                 if ( nTable != c_nUndefTable && node_traits::to_value_ptr(*arrPos[nTable].itFound) == &val ) {
2533                     bucket( nTable, arrHash[nTable]).remove( arrPos[nTable].itPrev, arrPos[nTable].itFound );
2534                     --m_ItemCounter;
2535                     m_Stat.onUnlinkSuccess();
2536                     return true;
2537                 }
2538             }
2539
2540             m_Stat.onUnlinkFailed();
2541             return false;
2542         }
2543
2544         /// Deletes the item from the set
2545         /** \anchor cds_intrusive_CuckooSet_erase
2546             The function searches an item with key equal to \p val in the set,
2547             unlinks it from the set, and returns a pointer to unlinked item.
2548
2549             If the item with key equal to \p val is not found the function return \p nullptr.
2550
2551             Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
2552         */
2553         template <typename Q>
2554         value_type * erase( Q const& val )
2555         {
2556             return erase( val, [](value_type const&) {} );
2557         }
2558
2559         /// Deletes the item from the set using \p pred predicate for searching
2560         /**
2561             The function is an analog of \ref cds_intrusive_CuckooSet_erase "erase(Q const&)"
2562             but \p pred is used for key comparing.
2563             If cuckoo set is ordered, then \p Predicate should have the interface and semantics like \p std::less.
2564             If cuckoo set is unordered, then \p Predicate should have the interface and semantics like \p std::equal_to.
2565             \p Predicate must imply the same element order as the comparator used for building the set.
2566         */
2567         template <typename Q, typename Predicate>
2568         value_type * erase_with( Q const& val, Predicate pred )
2569         {
2570             CDS_UNUSED( pred );
2571             return erase_( val, typename predicate_wrapper<Predicate>::type(), [](value_type const&) {} );
2572         }
2573
2574         /// Delete the item from the set
2575         /** \anchor cds_intrusive_CuckooSet_erase_func
2576             The function searches an item with key equal to \p val in the set,
2577             call \p f functor with item found, unlinks it from the set, and returns a pointer to unlinked item.
2578
2579             The \p Func interface is
2580             \code
2581             struct functor {
2582                 void operator()( value_type const& item );
2583             };
2584             \endcode
2585
2586             If the item with key equal to \p val is not found the function return \p nullptr.
2587
2588             Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
2589         */
2590         template <typename Q, typename Func>
2591         value_type * erase( Q const& val, Func f )
2592         {
2593             return erase_( val, key_predicate(), f );
2594         }
2595
2596         /// Deletes the item from the set using \p pred predicate for searching
2597         /**
2598             The function is an analog of \ref cds_intrusive_CuckooSet_erase_func "erase(Q const&, Func)"
2599             but \p pred is used for key comparing.
2600             If you use ordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::less.
2601             If you use unordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::equal_to.
2602             \p Predicate must imply the same element order as the comparator used for building the set.
2603         */
2604         template <typename Q, typename Predicate, typename Func>
2605         value_type * erase_with( Q const& val, Predicate pred, Func f )
2606         {
2607             CDS_UNUSED( pred );
2608             return erase_( val, typename predicate_wrapper<Predicate>::type(), f );
2609         }
2610
2611         /// Find the key \p val
2612         /** \anchor cds_intrusive_CuckooSet_find_func
2613             The function searches the item with key equal to \p val and calls the functor \p f for item found.
2614             The interface of \p Func functor is:
2615             \code
2616             struct functor {
2617                 void operator()( value_type& item, Q& val );
2618             };
2619             \endcode
2620             where \p item is the item found, \p val is the <tt>find</tt> function argument.
2621
2622             The functor may change non-key fields of \p item.
2623
2624             The \p val argument is non-const since it can be used as \p f functor destination i.e., the functor
2625             may modify both arguments.
2626
2627             Note the hash functor specified for class \p Traits template parameter
2628             should accept a parameter of type \p Q that can be not the same as \p value_type.
2629
2630             The function returns \p true if \p val is found, \p false otherwise.
2631         */
2632         template <typename Q, typename Func>
2633         bool find( Q& val, Func f )
2634         {
2635             return find_( val, key_predicate(), f );
2636         }
2637         //@cond
2638         template <typename Q, typename Func>
2639         bool find( Q const& val, Func f )
2640         {
2641             return find_( val, key_predicate(), f );
2642         }
2643         //@endcond
2644
2645         /// Find the key \p val using \p pred predicate for comparing
2646         /**
2647             The function is an analog of \ref cds_intrusive_CuckooSet_find_func "find(Q&, Func)"
2648             but \p pred is used for key comparison.
2649             If you use ordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::less.
2650             If you use unordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::equal_to.
2651             \p pred must imply the same element order as the comparator used for building the set.
2652         */
2653         template <typename Q, typename Predicate, typename Func>
2654         bool find_with( Q& val, Predicate pred, Func f )
2655         {
2656             CDS_UNUSED( pred );
2657             return find_( val, typename predicate_wrapper<Predicate>::type(), f );
2658         }
2659         //@cond
2660         template <typename Q, typename Predicate, typename Func>
2661         bool find_with( Q const& val, Predicate pred, Func f )
2662         {
2663             CDS_UNUSED( pred );
2664             return find_( val, typename predicate_wrapper<Predicate>::type(), f );
2665         }
2666         //@endcond
2667
2668         /// Checks whether the set contains \p key
2669         /**
2670             The function searches the item with key equal to \p key
2671             and returns \p true if it is found, and \p false otherwise.
2672         */
2673         template <typename Q>
2674         bool contains( Q const& key )
2675         {
2676             return find( key, [](value_type&, Q const& ) {} );
2677         }
2678         //@cond
2679         template <typename Q>
2680         CDS_DEPRECATED("deprecated, use contains()")
2681         bool find( Q const& key )
2682         {
2683             return contains( key );
2684         }
2685         //@endcond
2686
2687         /// Checks whether the set contains \p key using \p pred predicate for searching
2688         /**
2689             The function is similar to <tt>contains( key )</tt> but \p pred is used for key comparing.
2690             \p Less functor has the interface like \p std::less.
2691             \p Less must imply the same element order as the comparator used for building the set.
2692         */
2693         template <typename Q, typename Predicate>
2694         bool contains( Q const& key, Predicate pred )
2695         {
2696             CDS_UNUSED( pred );
2697             return find_with( key, typename predicate_wrapper<Predicate>::type(), [](value_type& , Q const& ) {} );
2698         }
2699         //@cond
2700         template <typename Q, typename Predicate>
2701         CDS_DEPRECATED("deprecated, use contains()")
2702         bool find_with( Q const& key, Predicate pred )
2703         {
2704             return contains( key, pred );
2705         }
2706         //@endcond
2707
2708         /// Clears the set
2709         /**
2710             The function unlinks all items from the set.
2711             For any item \ref disposer is called
2712         */
2713         void clear()
2714         {
2715             clear_and_dispose( disposer() );
2716         }
2717
2718         /// Clears the set and calls \p disposer for each item
2719         /**
2720             The function unlinks all items from the set calling \p disposer for each item.
2721             \p Disposer functor interface is:
2722             \code
2723             struct Disposer{
2724                 void operator()( value_type * p );
2725             };
2726             \endcode
2727
2728             The \ref disposer specified in \p Traits traits is not called.
2729         */
2730         template <typename Disposer>
2731         void clear_and_dispose( Disposer oDisposer )
2732         {
2733             // locks entire array
2734             scoped_full_lock sl( m_MutexPolicy );
2735
2736             for ( unsigned int i = 0; i < c_nArity; ++i ) {
2737                 bucket_entry * pEntry = m_BucketTable[i];
2738                 bucket_entry * pEnd = pEntry + m_nBucketMask + 1;
2739                 for ( ; pEntry != pEnd ; ++pEntry ) {
2740                     pEntry->clear( [&oDisposer]( node_type * pNode ){ oDisposer( node_traits::to_value_ptr( pNode )) ; } );
2741                 }
2742             }
2743             m_ItemCounter.reset();
2744         }
2745
2746         /// Checks if the set is empty
2747         /**
2748             Emptiness is checked by item counting: if item count is zero then the set is empty.
2749         */
2750         bool empty() const
2751         {
2752             return size() == 0;
2753         }
2754
2755         /// Returns item count in the set
2756         size_t size() const
2757         {
2758             return m_ItemCounter;
2759         }
2760
2761         /// Returns the size of hash table
2762         /**
2763             The hash table size is non-constant and can be increased via resizing.
2764         */
2765         size_t bucket_count() const
2766         {
2767             return m_nBucketMask + 1;
2768         }
2769
2770         /// Returns lock array size
2771         size_t lock_count() const
2772         {
2773             return m_MutexPolicy.lock_count();
2774         }
2775
2776         /// Returns const reference to internal statistics
2777         stat const& statistics() const
2778         {
2779             return m_Stat;
2780         }
2781
2782         /// Returns const reference to mutex policy internal statistics
2783         typename mutex_policy::statistics_type const& mutex_policy_statistics() const
2784         {
2785             return m_MutexPolicy.statistics();
2786         }
2787     };
2788 }} // namespace cds::intrusive
2789
2790 #endif // #ifndef CDSLIB_INTRUSIVE_CUCKOO_SET_H