cds/intrusive/cuckoo_set.h

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