Fixed Clang build

[libcds.git] / cds / intrusive / cuckoo_set.h

diff --git a/cds/intrusive/cuckoo_set.h b/cds/intrusive/cuckoo_set.h
index 6815bb7ac0993c575a705a2bda63f138eff8479b..2ebaf1ce1e67a3733106c6cddc56255924ce5ce9 100644 (file)
--- a/cds/intrusive/cuckoo_set.h
+++ b/cds/intrusive/cuckoo_set.h
@@ -1,7 +1,35 @@
-//$$CDS-header$$
-
-#ifndef __CDS_INTRUSIVE_CUCKOO_SET_H
-#define __CDS_INTRUSIVE_CUCKOO_SET_H
+/*
+    This file is a part of libcds - Concurrent Data Structures library
+
+    (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
+
+    Source code repo: http://github.com/khizmax/libcds/
+    Download: http://sourceforge.net/projects/libcds/files/
+    
+    Redistribution and use in source and binary forms, with or without
+    modification, are permitted provided that the following conditions are met:
+
+    * Redistributions of source code must retain the above copyright notice, this
+      list of conditions and the following disclaimer.
+
+    * Redistributions in binary form must reproduce the above copyright notice,
+      this list of conditions and the following disclaimer in the documentation
+      and/or other materials provided with the distribution.
+
+    THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+    AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+    IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+    DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+    FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+    DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+    SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+    CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
+    OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.     
+*/
+
+#ifndef CDSLIB_INTRUSIVE_CUCKOO_SET_H
+#define CDSLIB_INTRUSIVE_CUCKOO_SET_H

 
 #include <memory>
 #include <type_traits>
 
 #include <memory>
 #include <type_traits>


@@ -10,17 +38,15 @@
 #include <cds/intrusive/details/base.h>
 #include <cds/opt/compare.h>
 #include <cds/opt/hash.h>
 #include <cds/intrusive/details/base.h>
 #include <cds/opt/compare.h>
 #include <cds/opt/hash.h>

-#include <cds/lock/array.h>
+#include <cds/sync/lock_array.h>

 #include <cds/os/thread.h>
 #include <cds/os/thread.h>

-#include <cds/details/functor_wrapper.h>
-#include <cds/lock/spinlock.h>
+#include <cds/sync/spinlock.h>

 
 
 namespace cds { namespace intrusive {
 
     /// CuckooSet-related definitions
     namespace cuckoo {
 
 
 namespace cds { namespace intrusive {
 
     /// CuckooSet-related definitions
     namespace cuckoo {

-

         /// Option to define probeset type
         /**
             The option specifies probeset type for the CuckooSet.
         /// Option to define probeset type
         /**
             The option specifies probeset type for the CuckooSet.


@@ -77,14 +103,17 @@ namespace cds { namespace intrusive {
         //@endcond
 
         //@cond
         //@endcond
 
         //@cond

-        // Probeset type declarations.
+        /// List probeset type

         struct list;
         struct list;

+        //@endcond
+
+        /// Vector probeset type

         template <unsigned int Capacity>
         struct vector
         {
         template <unsigned int Capacity>
         struct vector
         {

+            /// Vector capacity

             static unsigned int const c_nCapacity = Capacity;
         };
             static unsigned int const c_nCapacity = Capacity;
         };

-        //@endcond

 
         /// CuckooSet node
         /**
 
         /// CuckooSet node
         /**


@@ -93,8 +122,7 @@ namespace cds { namespace intrusive {
                 or \p cds::intrusive::cuckoo::vector<Capacity>.
             - \p StoreHashCount - constant that defines whether to store node hash values.
                 See cuckoo::store_hash option for explanation
                 or \p cds::intrusive::cuckoo::vector<Capacity>.
             - \p StoreHashCount - constant that defines whether to store node hash values.
                 See cuckoo::store_hash option for explanation

-            - Tag - a tag used to distinguish between different implementation when two or more
-                \p node is needed in single struct.
+            - \p Tag - a \ref cds_intrusive_hook_tag "tag"

         */
         template <typename ProbesetType = cuckoo::list, unsigned int StoreHashCount = 0, typename Tag = opt::none>
         struct node
         */
         template <typename ProbesetType = cuckoo::list, unsigned int StoreHashCount = 0, typename Tag = opt::none>
         struct node


@@ -171,7 +199,6 @@ namespace cds { namespace intrusive {
             {
                 m_pNext = nullptr;
             }
             {
                 m_pNext = nullptr;
             }

-

         };
 
         template <unsigned int VectorSize, typename Tag>
         };
 
         template <unsigned int VectorSize, typename Tag>


@@ -242,11 +269,11 @@ namespace cds { namespace intrusive {
         template < typename HookType, typename... Options>
         struct hook
         {
         template < typename HookType, typename... Options>
         struct hook
         {

-            typedef typename opt::make_options< default_hook, Options...>::type  options;
+            typedef typename opt::make_options< default_hook, Options...>::type  traits;

 
 

-            typedef typename options::probeset_type probeset_type;
-            typedef typename options::tag tag;
-            static unsigned int const store_hash = options::store_hash;
+            typedef typename traits::probeset_type probeset_type;
+            typedef typename traits::tag tag;
+            static unsigned int const store_hash = traits::store_hash;

 
             typedef node<probeset_type, store_hash, tag>   node_type;
 
 
             typedef node<probeset_type, store_hash, tag>   node_type;
 


@@ -257,9 +284,9 @@ namespace cds { namespace intrusive {
         /// Base hook
         /**
             \p Options are:
         /// Base hook
         /**
             \p Options are:

-            - cuckoo::probeset_type - probeset type. Defaul is \p cuckoo::list
-            - cuckoo::store_hash - store hash values in the node or not. Default is 0 (no storing)
-            - opt::tag - tag to distinguish different nodes in one struct. Default is opt::none
+            - \p cuckoo::probeset_type - probeset type. Defaul is \p cuckoo::list
+            - \p cuckoo::store_hash - store hash values in the node or not. Default is 0 (no storing)
+            - \p opt::tag - a \ref cds_intrusive_hook_tag "tag"

         */
         template < typename... Options >
         struct base_hook: public hook< opt::base_hook_tag, Options... >
         */
         template < typename... Options >
         struct base_hook: public hook< opt::base_hook_tag, Options... >


@@ -271,9 +298,9 @@ namespace cds { namespace intrusive {
             Use \p offsetof macro to define \p MemberOffset
 
             \p Options are:
             Use \p offsetof macro to define \p MemberOffset
 
             \p Options are:

-            - cuckoo::probeset_type - probeset type. Defaul is \p cuckoo::list
-            - cuckoo::store_hash - store hash values in the node or not. Default is 0 (no storing)
-            - opt::tag - tag to distinguish different nodes in one struct. Default is opt::none
+            - \p cuckoo::probeset_type - probeset type. Defaul is \p cuckoo::list
+            - \p cuckoo::store_hash - store hash values in the node or not. Default is 0 (no storing)
+            - \p opt::tag - a \ref cds_intrusive_hook_tag "tag"

         */
         template < size_t MemberOffset, typename... Options >
         struct member_hook: public hook< opt::member_hook_tag, Options... >
         */
         template < size_t MemberOffset, typename... Options >
         struct member_hook: public hook< opt::member_hook_tag, Options... >


@@ -289,9 +316,9 @@ namespace cds { namespace intrusive {
             See \ref node_traits for \p NodeTraits interface description
 
             \p Options are:
             See \ref node_traits for \p NodeTraits interface description
 
             \p Options are:

-            - cuckoo::probeset_type - probeset type. Defaul is \p cuckoo::list
-            - cuckoo::store_hash - store hash values in the node or not. Default is 0 (no storing)
-            - opt::tag - tag to distinguish different nodes in one struct. Default is opt::none
+            - \p cuckoo::probeset_type - probeset type. Defaul is \p cuckoo::list
+            - \p cuckoo::store_hash - store hash values in the node or not. Default is 0 (no storing)
+            - \p opt::tag - a \ref cds_intrusive_hook_tag "tag"

         */
         template <typename NodeTraits, typename... Options >
         struct traits_hook: public hook< opt::traits_hook_tag, Options... >
         */
         template <typename NodeTraits, typename... Options >
         struct traits_hook: public hook< opt::traits_hook_tag, Options... >


@@ -378,7 +405,7 @@ namespace cds { namespace intrusive {
             };
             //@endcond
 
             };
             //@endcond
 

-            typedef cds::lock::array< lock_type, cds::lock::pow2_select_policy, allocator_type >    lock_array_type ;   ///< lock array type
+            typedef cds::sync::lock_array< lock_type, cds::sync::pow2_select_policy, allocator_type >    lock_array_type ;   ///< lock array type

 
         protected:
             //@cond
 
         protected:
             //@cond


@@ -392,9 +419,9 @@ namespace cds { namespace intrusive {
                 lock_array( size_t nCapacity ): lock_array_type( nCapacity, typename lock_array_type::select_cell_policy(nCapacity) ) {}
             };
 
                 lock_array( size_t nCapacity ): lock_array_type( nCapacity, typename lock_array_type::select_cell_policy(nCapacity) ) {}
             };
 

-            class scoped_lock: public cds::lock::scoped_lock< lock_array_type >
+            class scoped_lock: public std::unique_lock< lock_array_type >

             {
             {

-                typedef cds::lock::scoped_lock< lock_array_type > base_class;
+                typedef std::unique_lock< lock_array_type > base_class;

             public:
                 scoped_lock( lock_array& arrLock, size_t nHash ): base_class( arrLock, nHash ) {}
             };
             public:
                 scoped_lock( lock_array& arrLock, size_t nHash ): base_class( arrLock, nHash ) {}
             };


@@ -402,7 +429,7 @@ namespace cds { namespace intrusive {
 
         protected:
             //@cond
 
         protected:
             //@cond

-            lock_array      m_Locks[c_nArity] ;   ///< array of lock_array_type
+            lock_array      m_Locks[c_nArity] ;   ///< array of \p lock_array_type

             statistics_type m_Stat              ; ///< internal statistics
             //@endcond
 
             statistics_type m_Stat              ; ///< internal statistics
             //@endcond
 


@@ -465,7 +492,7 @@ namespace cds { namespace intrusive {
             };
 
             class scoped_full_lock {
             };
 
             class scoped_full_lock {

-                cds::lock::scoped_lock< lock_array_type >   m_guard;
+                std::unique_lock< lock_array_type >   m_guard;

             public:
                 scoped_full_lock( striping& policy )
                     : m_guard( policy.m_Locks[0] )
             public:
                 scoped_full_lock( striping& policy )
                     : m_guard( policy.m_Locks[0] )


@@ -632,13 +659,13 @@ namespace cds { namespace intrusive {
 
         protected:
             //@cond
 
         protected:
             //@cond

-            typedef cds::lock::trivial_select_policy  lock_selection_policy;
+            typedef cds::sync::trivial_select_policy  lock_selection_policy;

 
             class lock_array_type
 
             class lock_array_type

-                : public cds::lock::array< lock_type, lock_selection_policy, allocator_type >
+                : public cds::sync::lock_array< lock_type, lock_selection_policy, allocator_type >

                 , public std::enable_shared_from_this< lock_array_type >
             {
                 , public std::enable_shared_from_this< lock_array_type >
             {

-                typedef cds::lock::array< lock_type, lock_selection_policy, allocator_type >    lock_array_base;
+                typedef cds::sync::lock_array< lock_type, lock_selection_policy, allocator_type >    lock_array_base;

             public:
                 lock_array_type( size_t nCapacity )
                     : lock_array_base( nCapacity )
             public:
                 lock_array_type( size_t nCapacity )
                     : lock_array_base( nCapacity )


@@ -650,8 +677,8 @@ namespace cds { namespace intrusive {
             typedef unsigned long long  owner_t;
             typedef cds::OS::ThreadId   threadId_t;
 
             typedef unsigned long long  owner_t;
             typedef cds::OS::ThreadId   threadId_t;
 

-            typedef cds::lock::Spin     spinlock_type;
-            typedef cds::lock::scoped_lock< spinlock_type > scoped_spinlock;
+            typedef cds::sync::spin     spinlock_type;
+            typedef std::unique_lock< spinlock_type > scoped_spinlock;

             //@endcond
 
         protected:
             //@endcond
 
         protected:


@@ -681,7 +708,7 @@ namespace cds { namespace intrusive {
 
             void acquire( size_t const * arrHash, lock_array_ptr * pLockArr, lock_type ** parrLock )
             {
 
             void acquire( size_t const * arrHash, lock_array_ptr * pLockArr, lock_type ** parrLock )
             {

-                owner_t me = (owner_t) cds::OS::getCurrentThreadId();
+                owner_t me = (owner_t) cds::OS::get_current_thread_id();

                 owner_t who;
 
                 back_off bkoff;
                 owner_t who;
 
                 back_off bkoff;


@@ -760,7 +787,7 @@ namespace cds { namespace intrusive {
 
             void acquire_all()
             {
 
             void acquire_all()
             {

-                owner_t me = (owner_t) cds::OS::getCurrentThreadId();
+                owner_t me = (owner_t) cds::OS::get_current_thread_id();

 
                 back_off bkoff;
                 while ( true ) {
 
                 back_off bkoff;
                 while ( true ) {


@@ -784,7 +811,7 @@ namespace cds { namespace intrusive {
 
             void acquire_resize( lock_array_ptr * pOldLocks )
             {
 
             void acquire_resize( lock_array_ptr * pOldLocks )
             {

-                owner_t me = (owner_t) cds::OS::getCurrentThreadId();
+                owner_t me = (owner_t) cds::OS::get_current_thread_id();

 
                 while ( true ) {
                     {
 
                 while ( true ) {
                     {


@@ -918,18 +945,6 @@ namespace cds { namespace intrusive {
                 for ( unsigned int i = 0; i < c_nArity; ++i )
                     pNew[i] = create_lock_array( nCapacity );
 
                 for ( unsigned int i = 0; i < c_nArity; ++i )
                     pNew[i] = create_lock_array( nCapacity );
 

-                /*
-                // Assignment m_arrLocks[i] = pNew[i] may call heavy-weighted dtor for each item of m_arrLocks
-                // that is unacceptable under spin-lock
-                // So, we store copy of m_arrLocks in pOld
-                lock_array_ptr pOld[ c_nArity ];
-                for ( unsigned int i = 0; i < c_nArity; ++i )
-                    pOld[i] = m_arrLocks[i];
-
-                // m_arrLocks assignment will not lead to calling dtor of each item of m_arrLocks
-                // since copy of m_arrLocks locates in pOld and assignment will not be too painful for spin-lock
-                */
-

                 {
                     scoped_spinlock sl(m_access);
                     for ( unsigned int i = 0; i < c_nArity; ++i )
                 {
                     scoped_spinlock sl(m_access);
                     for ( unsigned int i = 0; i < c_nArity; ++i )


@@ -963,48 +978,48 @@ namespace cds { namespace intrusive {
             }
         };
 
             }
         };
 

-        /// CuckooSet internal statistics
+        /// \p CuckooSet internal statistics

         struct stat {
             typedef cds::atomicity::event_counter   counter_type ;  ///< Counter type
 
         struct stat {
             typedef cds::atomicity::event_counter   counter_type ;  ///< Counter type
 

-            counter_type    m_nRelocateCallCount    ; ///< Count of \p relocate function call
+            counter_type    m_nRelocateCallCount    ; ///< Count of \p relocate() function call

             counter_type    m_nRelocateRoundCount   ; ///< Count of attempts to relocate items
             counter_type    m_nFalseRelocateCount   ; ///< Count of unneeded attempts of \p relocate call
             counter_type    m_nRelocateRoundCount   ; ///< Count of attempts to relocate items
             counter_type    m_nFalseRelocateCount   ; ///< Count of unneeded attempts of \p relocate call

-            counter_type    m_nSuccessRelocateCount ; ///< Count of successfull item relocating
+            counter_type    m_nSuccessRelocateCount ; ///< Count of successful item relocating

             counter_type    m_nRelocateAboveThresholdCount; ///< Count of item relocating above probeset threshold
             counter_type    m_nFailedRelocateCount  ;   ///< Count of failed relocation attemp (when all probeset is full)
 
             counter_type    m_nRelocateAboveThresholdCount; ///< Count of item relocating above probeset threshold
             counter_type    m_nFailedRelocateCount  ;   ///< Count of failed relocation attemp (when all probeset is full)
 

-            counter_type    m_nResizeCallCount      ;   ///< Count of \p resize function call
-            counter_type    m_nFalseResizeCount     ;   ///< Count of false \p resize function call (when other thread has been resized the set)
-            counter_type    m_nResizeSuccessNodeMove;   ///< Count of successfull node moving when resizing
-            counter_type    m_nResizeRelocateCall   ;   ///< Count of \p relocate function call from \p resize function
+            counter_type    m_nResizeCallCount      ;   ///< Count of \p resize() function call
+            counter_type    m_nFalseResizeCount     ;   ///< Count of false \p resize() function call (when other thread has been resized the set)
+            counter_type    m_nResizeSuccessNodeMove;   ///< Count of successful node moving when resizing
+            counter_type    m_nResizeRelocateCall   ;   ///< Count of \p relocate() function call from \p resize function

 
 

-            counter_type    m_nInsertSuccess        ;   ///< Count of successfull \p insert function call
-            counter_type    m_nInsertFailed         ;   ///< Count of failed \p insert function call
-            counter_type    m_nInsertResizeCount    ;   ///< Count of \p resize function call from \p insert
-            counter_type    m_nInsertRelocateCount  ;   ///< Count of \p relocate function call from \p insert
-            counter_type    m_nInsertRelocateFault  ;   ///< Count of failed \p relocate function call from \p insert
+            counter_type    m_nInsertSuccess        ;   ///< Count of successful \p insert() function call
+            counter_type    m_nInsertFailed         ;   ///< Count of failed \p insert() function call
+            counter_type    m_nInsertResizeCount    ;   ///< Count of \p resize() function call from \p insert()
+            counter_type    m_nInsertRelocateCount  ;   ///< Count of \p relocate() function call from \p insert()
+            counter_type    m_nInsertRelocateFault  ;   ///< Count of failed \p relocate() function call from \p insert()

 
 

-            counter_type    m_nEnsureExistCount     ;   ///< Count of call \p ensure function for existing node
-            counter_type    m_nEnsureSuccessCount   ;   ///< Count of successfull \p insert function call for new node
-            counter_type    m_nEnsureResizeCount    ;   ///< Count of \p resize function call from \p ensure
-            counter_type    m_nEnsureRelocateCount  ;   ///< Count of \p relocate function call from \p ensure
-            counter_type    m_nEnsureRelocateFault  ;   ///< Count of failed \p relocate function call from \p ensure
+            counter_type    m_nUpdateExistCount     ;   ///< Count of call \p update() function for existing node
+            counter_type    m_nUpdateSuccessCount   ;   ///< Count of successful \p insert() function call for new node
+            counter_type    m_nUpdateResizeCount    ;   ///< Count of \p resize() function call from \p update()
+            counter_type    m_nUpdateRelocateCount  ;   ///< Count of \p relocate() function call from \p update()
+            counter_type    m_nUpdateRelocateFault  ;   ///< Count of failed \p relocate() function call from \p update()

 
 

-            counter_type    m_nUnlinkSuccess        ;   ///< Count of success \p unlink function call
-            counter_type    m_nUnlinkFailed         ;   ///< Count of failed \p unlink function call
+            counter_type    m_nUnlinkSuccess        ;   ///< Count of success \p unlink() function call
+            counter_type    m_nUnlinkFailed         ;   ///< Count of failed \p unlink() function call

 
 

-            counter_type    m_nEraseSuccess         ;   ///< Count of success \p erase function call
-            counter_type    m_nEraseFailed          ;   ///< Count of failed \p erase function call
+            counter_type    m_nEraseSuccess         ;   ///< Count of success \p erase() function call
+            counter_type    m_nEraseFailed          ;   ///< Count of failed \p erase() function call

 
 

-            counter_type    m_nFindSuccess         ;   ///< Count of success \p find function call
-            counter_type    m_nFindFailed          ;   ///< Count of failed \p find function call
+            counter_type    m_nFindSuccess         ;   ///< Count of success \p find() function call
+            counter_type    m_nFindFailed          ;   ///< Count of failed \p find() function call

 
 

-            counter_type    m_nFindEqualSuccess         ;   ///< Count of success \p find_equal function call
-            counter_type    m_nFindEqualFailed          ;   ///< Count of failed \p find_equal function call
+            counter_type    m_nFindEqualSuccess         ;   ///< Count of success \p find_equal() function call
+            counter_type    m_nFindEqualFailed          ;   ///< Count of failed \p find_equal() function call

 
 

-            counter_type    m_nFindWithSuccess         ;   ///< Count of success \p find_with function call
-            counter_type    m_nFindWithFailed          ;   ///< Count of failed \p find_with function call
+            counter_type    m_nFindWithSuccess         ;   ///< Count of success \p find_with() function call
+            counter_type    m_nFindWithFailed          ;   ///< Count of failed \p find_with() function call

 
             //@cond
             void    onRelocateCall()        { ++m_nRelocateCallCount; }
 
             //@cond
             void    onRelocateCall()        { ++m_nRelocateCallCount; }


@@ -1025,11 +1040,11 @@ namespace cds { namespace intrusive {
             void    onInsertRelocate()      { ++m_nInsertRelocateCount; }
             void    onInsertRelocateFault() { ++m_nInsertRelocateFault; }
 
             void    onInsertRelocate()      { ++m_nInsertRelocateCount; }
             void    onInsertRelocateFault() { ++m_nInsertRelocateFault; }
 

-            void    onEnsureExist()         { ++m_nEnsureExistCount; }
-            void    onEnsureSuccess()       { ++m_nEnsureSuccessCount; }
-            void    onEnsureResize()        { ++m_nEnsureResizeCount; }
-            void    onEnsureRelocate()      { ++m_nEnsureRelocateCount; }
-            void    onEnsureRelocateFault() { ++m_nEnsureRelocateFault; }
+            void    onUpdateExist()         { ++m_nUpdateExistCount; }
+            void    onUpdateSuccess()       { ++m_nUpdateSuccessCount; }
+            void    onUpdateResize()        { ++m_nUpdateResizeCount; }
+            void    onUpdateRelocate()      { ++m_nUpdateRelocateCount; }
+            void    onUpdateRelocateFault() { ++m_nUpdateRelocateFault; }

 
             void    onUnlinkSuccess()       { ++m_nUnlinkSuccess; }
             void    onUnlinkFailed()        { ++m_nUnlinkFailed; }
 
             void    onUnlinkSuccess()       { ++m_nUnlinkSuccess; }
             void    onUnlinkFailed()        { ++m_nUnlinkFailed; }


@@ -1066,11 +1081,11 @@ namespace cds { namespace intrusive {
             void    onInsertRelocate()      const {}
             void    onInsertRelocateFault() const {}
 
             void    onInsertRelocate()      const {}
             void    onInsertRelocateFault() const {}
 

-            void    onEnsureExist()         const {}
-            void    onEnsureSuccess()       const {}
-            void    onEnsureResize()        const {}
-            void    onEnsureRelocate()      const {}
-            void    onEnsureRelocateFault() const {}
+            void    onUpdateExist()         const {}
+            void    onUpdateSuccess()       const {}
+            void    onUpdateResize()        const {}
+            void    onUpdateRelocate()      const {}
+            void    onUpdateRelocateFault() const {}

 
             void    onUnlinkSuccess()       const {}
             void    onUnlinkFailed()        const {}
 
             void    onUnlinkSuccess()       const {}
             void    onUnlinkFailed()        const {}


@@ -1087,7 +1102,7 @@ namespace cds { namespace intrusive {
         };
 
         /// Type traits for CuckooSet class
         };
 
         /// Type traits for CuckooSet class

-        struct type_traits
+        struct traits

         {
             /// Hook used
             /**
         {
             /// Hook used
             /**


@@ -1104,17 +1119,23 @@ namespace cds { namespace intrusive {
                 The hash functors are defined as <tt> std::tuple< H1, H2, ... Hn > </tt>:
                 \@code cds::opt::hash< std::tuple< h1, h2 > > \@endcode
                 The number of hash functors specifies the number \p k - the count of hash tables in cuckoo hashing.
                 The hash functors are defined as <tt> std::tuple< H1, H2, ... Hn > </tt>:
                 \@code cds::opt::hash< std::tuple< h1, h2 > > \@endcode
                 The number of hash functors specifies the number \p k - the count of hash tables in cuckoo hashing.

-                Up to 10 different hash functors are supported.
+
+                To specify hash tuple in traits you should use \p cds::opt::hash_tuple:
+                \code
+                struct my_traits: public cds::intrusive::cuckoo::traits {
+                    typedef cds::opt::hash_tuple< hash1, hash2 > hash;
+                };
+                \endcode

             */
             typedef cds::opt::none      hash;
 
             /// Concurrent access policy
             /**
                 Available opt::mutex_policy types:
             */
             typedef cds::opt::none      hash;
 
             /// Concurrent access policy
             /**
                 Available opt::mutex_policy types:

-                - cuckoo::striping - simple, but the lock array is not resizable
-                - cuckoo::refinable - resizable lock array, but more complex access to set data.
+                - \p cuckoo::striping - simple, but the lock array is not resizable
+                - \p cuckoo::refinable - resizable lock array, but more complex access to set data.

 
 

-                Default is cuckoo::striping.
+                Default is \p cuckoo::striping.

             */
             typedef cuckoo::striping<>               mutex_policy;
 
             */
             typedef cuckoo::striping<>               mutex_policy;
 


@@ -1124,7 +1145,7 @@ namespace cds { namespace intrusive {
             */
             typedef opt::none                       equal_to;
 
             */
             typedef opt::none                       equal_to;
 

-            /// Key comparison functor
+            /// Key comparing functor

             /**
                 No default functor is provided. If the option is not specified, the \p less is used.
             */
             /**
                 No default functor is provided. If the option is not specified, the \p less is used.
             */


@@ -1139,7 +1160,7 @@ namespace cds { namespace intrusive {
             /// Item counter
             /**
                 The type for item counting feature.
             /// Item counter
             /**
                 The type for item counting feature.

-                Default is cds::atomicity::item_counter
+                Default is \p cds::atomicity::item_counter

 
                 Only atomic item counter type is allowed.
             */
 
                 Only atomic item counter type is allowed.
             */


@@ -1153,24 +1174,53 @@ namespace cds { namespace intrusive {
 
             /// Disposer
             /**
 
             /// Disposer
             /**

-                The disposer functor is used in CuckooSet::clear member function
+                The disposer functor is used in \p CuckooSet::clear() member function

                 to free set's node.
             */
             typedef intrusive::opt::v::empty_disposer   disposer;
 
                 to free set's node.
             */
             typedef intrusive::opt::v::empty_disposer   disposer;
 

-            /// Internal statistics. Available statistics: cuckoo::stat, cuckoo::empty_stat
+            /// Internal statistics. Available statistics: \p cuckoo::stat, \p cuckoo::empty_stat

             typedef empty_stat                  stat;
         };
 
             typedef empty_stat                  stat;
         };
 

-        /// Metafunction converting option list to CuckooSet traits
+        /// Metafunction converting option list to \p CuckooSet traits

         /**
         /**

-            This is a wrapper for <tt> cds::opt::make_options< type_traits, Options...> </tt>
-            \p Options list see \ref CuckooSet.
+            Template argument list \p Options... are:
+            - \p intrusive::opt::hook - hook used. Possible values are: \p cuckoo::base_hook, \p cuckoo::member_hook,
+                \p cuckoo::traits_hook.
+                If the option is not specified, <tt>%cuckoo::base_hook<></tt> is used.
+            - \p opt::hash - hash functor tuple, mandatory option. At least, two hash functors should be provided. All hash functor
+                should be orthogonal (different): for each <tt> i,j: i != j => h[i](x) != h[j](x) </tt>.
+                The hash functors are passed as <tt> std::tuple< H1, H2, ... Hn > </tt>. The number of hash functors specifies
+                the number \p k - the count of hash tables in cuckoo hashing.
+            - \p opt::mutex_policy - concurrent access policy.
+                Available policies: \p cuckoo::striping, \p cuckoo::refinable.
+                Default is \p %cuckoo::striping.
+            - \p opt::equal_to - key equality functor like \p std::equal_to.
+                If this functor is defined then the probe-set will be unordered.
+                If \p %opt::compare or \p %opt::less option is specified too, then the probe-set will be ordered
+                and \p %opt::equal_to will be ignored.
+            - \p opt::compare - key comparison functor. No default functor is provided.
+                If the option is not specified, the \p %opt::less is used.
+                If \p %opt::compare or \p %opt::less option is specified, then the probe-set will be ordered.
+            - \p opt::less - specifies binary predicate used for key comparison. Default is \p std::less<T>.
+                If \p %opt::compare or \p %opt::less option is specified, then the probe-set will be ordered.
+            - \p opt::item_counter - the type of item counting feature. Default is \p atomicity::item_counter
+                The item counter should be atomic.
+            - \p opt::allocator - the allocator type using for allocating bucket tables.
+                Default is \ref CDS_DEFAULT_ALLOCATOR
+            - \p intrusive::opt::disposer - the disposer type used in \p clear() member function for
+                freeing nodes. Default is \p intrusive::opt::v::empty_disposer
+            - \p opt::stat - internal statistics. Possibly types: \p cuckoo::stat, \p cuckoo::empty_stat.
+                Default is \p %cuckoo::empty_stat
+
+            The probe set traits \p cuckoo::probeset_type and \p cuckoo::store_hash are taken from \p node type
+            specified by \p opt::hook option.

         */
         template <typename... Options>
         struct make_traits {
             typedef typename cds::opt::make_options<
         */
         template <typename... Options>
         struct make_traits {
             typedef typename cds::opt::make_options<

-                typename cds::opt::find_type_traits< cuckoo::type_traits, Options... >::type
+                typename cds::opt::find_type_traits< cuckoo::traits, Options... >::type

                 ,Options...
             >::type   type ;    ///< Result of metafunction
         };
                 ,Options...
             >::type   type ;    ///< Result of metafunction
         };


@@ -1330,7 +1380,7 @@ namespace cds { namespace intrusive {
             };
 
             template <typename Node, unsigned int Capacity>
             };
 
             template <typename Node, unsigned int Capacity>

-            class bucket_entry<Node, cuckoo::vector<Capacity> >
+            class bucket_entry<Node, cuckoo::vector<Capacity>>

             {
             public:
                 typedef Node                            node_type;
             {
             public:
                 typedef Node                            node_type;


@@ -1347,22 +1397,14 @@ namespace cds { namespace intrusive {
                 {
                     assert( m_nSize < c_nCapacity );
 
                 {
                     assert( m_nSize < c_nCapacity );
 

-                    // std alorithm

                     if ( nFrom < m_nSize )
                         std::copy_backward( m_arrNode + nFrom, m_arrNode + m_nSize, m_arrNode + m_nSize + 1 );
                     if ( nFrom < m_nSize )
                         std::copy_backward( m_arrNode + nFrom, m_arrNode + m_nSize, m_arrNode + m_nSize + 1 );

-
-                    // alternative: low-level byte copying
-                    //memmove( m_arrNode + nFrom + 1, m_arrNode + nFrom, (m_nSize - nFrom) * sizeof(m_arrNode[0]) );

                 }
 
                 void shift_down( node_type ** pFrom )
                 {
                     assert( m_arrNode <= pFrom && pFrom < m_arrNode + m_nSize);
                 }
 
                 void shift_down( node_type ** pFrom )
                 {
                     assert( m_arrNode <= pFrom && pFrom < m_arrNode + m_nSize);

-                    // std algo
-                    std::copy( pFrom + 1, m_arrNode + m_nSize, pFrom  );
-
-                    // alternative: low-level byte copying
-                    //memmove( pFrom + 1, pFrom, (m_nSize - nFrom - 1) * sizeof(m_arrNode[0]));
+                    std::copy( pFrom + 1, m_arrNode + m_nSize, pFrom );

                 }
             public:
                 class iterator
                 }
             public:
                 class iterator


@@ -1439,8 +1481,8 @@ namespace cds { namespace intrusive {
                     assert( !it.pArr || (m_arrNode <= it.pArr && it.pArr <= m_arrNode + m_nSize));
 
                     if ( it.pArr ) {
                     assert( !it.pArr || (m_arrNode <= it.pArr && it.pArr <= m_arrNode + m_nSize));
 
                     if ( it.pArr ) {

-                        shift_up( (unsigned int)(it.pArr - m_arrNode) + 1 );
-                        *(it.pArr + 1) = p;
+                        shift_up( static_cast<unsigned int>(it.pArr - m_arrNode) + 1 );
+                        it.pArr[1] = p;

                     }
                     else {
                         shift_up(0);
                     }
                     else {
                         shift_up(0);


@@ -1480,7 +1522,7 @@ namespace cds { namespace intrusive {
             struct hash_ops {
                 static void store( Node * pNode, size_t * pHashes )
                 {
             struct hash_ops {
                 static void store( Node * pNode, size_t * pHashes )
                 {

-                    memcpy( pNode->m_arrHash, pHashes, sizeof(size_t) * ArraySize );
+                    memcpy( pNode->m_arrHash, pHashes, sizeof(pHashes[0]) * ArraySize );

                 }
                 static bool equal_to( Node& node, unsigned int nTable, size_t nHash )
                 {
                 }
                 static bool equal_to( Node& node, unsigned int nTable, size_t nHash )
                 {


@@ -1505,7 +1547,7 @@ namespace cds { namespace intrusive {
             struct contains<NodeTraits, true>
             {
                 template <typename BucketEntry, typename Position, typename Q, typename Compare>
             struct contains<NodeTraits, true>
             {
                 template <typename BucketEntry, typename Position, typename Q, typename Compare>

-                static bool find( BucketEntry& probeset, Position& pos, unsigned int nTable, size_t nHash, Q const& val, Compare cmp )
+                static bool find( BucketEntry& probeset, Position& pos, unsigned int /*nTable*/, size_t /*nHash*/, Q const& val, Compare cmp )

                 {
                     // Ordered version
                     typedef typename BucketEntry::iterator bucket_iterator;
                 {
                     // Ordered version
                     typedef typename BucketEntry::iterator bucket_iterator;


@@ -1571,7 +1613,7 @@ namespace cds { namespace intrusive {
         <b>About Cuckoo hashing</b>
 
             [From <i>"The Art of Multiprocessor Programming"</i>]
         <b>About Cuckoo hashing</b>
 
             [From <i>"The Art of Multiprocessor Programming"</i>]

-            Cuckoo hashing is a hashing algorithm in which a newly added item displaces any earlier item
+            <a href="https://en.wikipedia.org/wiki/Cuckoo_hashing">Cuckoo hashing</a> is a hashing algorithm in which a newly added item displaces any earlier item

             occupying the same slot. For brevity, a table is a k-entry array of items. For a hash set f size
             N = 2k we use a two-entry array of tables, and two independent hash functions,
             <tt> h0, h1: KeyRange -> 0,...,k-1</tt>
             occupying the same slot. For brevity, a table is a k-entry array of items. For a hash set f size
             N = 2k we use a two-entry array of tables, and two independent hash functions,
             <tt> h0, h1: KeyRange -> 0,...,k-1</tt>


@@ -1609,56 +1651,24 @@ namespace cds { namespace intrusive {
             the average search complexity is <tt>O(PROBE_SET/2)</tt>.
             However, the overhead of sorting can eliminate a gain of ordered search.
 
             the average search complexity is <tt>O(PROBE_SET/2)</tt>.
             However, the overhead of sorting can eliminate a gain of ordered search.
 

-            The probe set is ordered if opt::compare or opt::less is specified in \p Traits template
-            parameter. Otherwise, the probe set is unordered and \p Traits must contain
-            opt::equal_to option.
+            The probe set is ordered if \p compare or \p less is specified in \p Traits template
+            parameter. Otherwise, the probe set is unordered and \p Traits should provide
+            \p equal_to predicate.

 
 

-            The cds::intrusive::cuckoo namespace contains \p %CuckooSet-related declarations.
+            The \p cds::intrusive::cuckoo namespace contains \p %CuckooSet-related declarations.

 
         Template arguments:
 
         Template arguments:

-        - \p T - the type stored in the set.  The type must be based on cuckoo::node (for cuckoo::base_hook)
-            or it must have a member of type %cuckoo::node (for cuckoo::member_hook),
-            or it must be convertible to \p %cuckoo::node (for cuckoo::traits_hook)
-        - \p Traits - type traits. See cuckoo::type_traits for explanation. It is possible to declare option-based
-            set with cuckoo::make_traits metafunction result as \p Traits template argument.
-
-        Template argument list \p Options... of cuckoo::make_traits metafunction are:
-        - intrusive::opt::hook - hook used. Possible values are: cuckoo::base_hook, cuckoo::member_hook, cuckoo::traits_hook.
-            If the option is not specified, <tt>%cuckoo::base_hook<></tt> is used.
-        - opt::hash - hash functor tuple, mandatory option. At least, two hash functors should be provided. All hash functor
-            should be orthogonal (different): for each <tt> i,j: i != j => h[i](x) != h[j](x) </tt>.
-            The hash functors are passed as <tt> std::tuple< H1, H2, ... Hn > </tt>. The number of hash functors specifies
-            the number \p k - the count of hash tables in cuckoo hashing. If the compiler supports variadic templates
-            then k is unlimited, otherwise up to 10 different hash functors are supported.
-        - opt::mutex_policy - concurrent access policy.
-            Available policies: cuckoo::striping, cuckoo::refinable.
-            Default is cuckoo::striping.
-        - opt::equal_to - key equality functor like \p std::equal_to.
-            If this functor is defined then the probe-set will be unordered.
-            If opt::compare or opt::less option is specified too, then the probe-set will be ordered
-            and opt::equal_to will be ignored.
-        - opt::compare - key comparison functor. No default functor is provided.
-            If the option is not specified, the opt::less is used.
-            If opt::compare or opt::less option is specified, then the probe-set will be ordered.
-        - opt::less - specifies binary predicate used for key comparison. Default is \p std::less<T>.
-            If opt::compare or opt::less option is specified, then the probe-set will be ordered.
-        - opt::item_counter - the type of item counting feature. Default is \ref atomicity::item_counter
-            The item counter should be atomic.
-        - opt::allocator - the allocator type using for allocating bucket tables.
-            Default is \p CDS_DEFAULT_ALLOCATOR
-        - intrusive::opt::disposer - the disposer type used in \ref clear() member function for
-            freeing nodes. Default is intrusive::opt::v::empty_disposer
-        - opt::stat - internal statistics. Possibly types: cuckoo::stat, cuckoo::empty_stat.
-            Default is cuckoo::empty_stat
-
-        The probe set options cuckoo::probeset_type and cuckoo::store_hash are taken from \p node type
-        specified by \p opt::hook option.
+        - \p T - the type stored in the set. The type must be based on \p cuckoo::node (for \p cuckoo::base_hook)
+            or it must have a member of type %cuckoo::node (for \p cuckoo::member_hook),
+            or it must be convertible to \p %cuckoo::node (for \p cuckoo::traits_hook)
+        - \p Traits - type traits, default is \p cuckoo::traits. It is possible to declare option-based
+            set with \p cuckoo::make_traits metafunction result as \p Traits template argument.

 
         <b>How to use</b>
 
 
         <b>How to use</b>
 

-        You should incorporate cuckoo::node into your struct \p T and provide
-        appropriate cuckoo::type_traits::hook in your \p Traits template parameters. Usually, for \p Traits you
-        define a struct based on cuckoo::type_traits.
+        You should incorporate \p cuckoo::node into your struct \p T and provide
+        appropriate \p cuckoo::traits::hook in your \p Traits template parameters.
+        Usually, for \p Traits you define a struct based on \p cuckoo::traits.

 
         Example for base hook and list-based probe-set:
         \code
 
         Example for base hook and list-based probe-set:
         \code


@@ -1719,14 +1729,14 @@ namespace cds { namespace intrusive {
         };
 
         // Declare type traits
         };
 
         // Declare type traits

-        struct my_traits: public cds::intrusive::cuckoo::type_traits
+        struct my_traits: public cds::intrusive::cuckoo::traits

         {
             typedef cds::intrusive::cuckoo::base_hook<
                 cds::intrusive::cuckoo::probeset_type< my_data::probeset_type >
                 ,cds::intrusive::cuckoo::store_hash< my_data::hash_array_size >
             >   hook;
             typedef my_data_equa_to equal_to;
         {
             typedef cds::intrusive::cuckoo::base_hook<
                 cds::intrusive::cuckoo::probeset_type< my_data::probeset_type >
                 ,cds::intrusive::cuckoo::store_hash< my_data::hash_array_size >
             >   hook;
             typedef my_data_equa_to equal_to;

-            typedef std::tuple< hash1, hash2 >  hash;
+            typedef cds::opt::hash_tuple< hash1, hash2 > hash;

         };
 
         // Declare CuckooSet type
         };
 
         // Declare CuckooSet type


@@ -1808,14 +1818,14 @@ namespace cds { namespace intrusive {
         };
 
         // Declare type traits
         };
 
         // Declare type traits

-        struct my_traits: public cds::intrusive::cuckoo::type_traits
+        struct my_traits: public cds::intrusive::cuckoo::traits

         {
             typedef cds::intrusive::cuckoo::base_hook<
                 cds::intrusive::cuckoo::probeset_type< my_data::probeset_type >
                 ,cds::intrusive::cuckoo::store_hash< my_data::hash_array_size >
             >   hook;
             typedef my_data_compare compare;
         {
             typedef cds::intrusive::cuckoo::base_hook<
                 cds::intrusive::cuckoo::probeset_type< my_data::probeset_type >
                 ,cds::intrusive::cuckoo::store_hash< my_data::hash_array_size >
             >   hook;
             typedef my_data_compare compare;

-            typedef std::tuple< hash1, hash2 >  hash;
+            typedef cds::opt::hash_tuple< hash1, hash2 > hash;

         };
 
         // Declare CuckooSet type
         };
 
         // Declare CuckooSet type


@@ -1835,31 +1845,25 @@ namespace cds { namespace intrusive {
         \endcode
 
     */
         \endcode
 
     */

-    template <typename T, typename Traits = cuckoo::type_traits>
+    template <typename T, typename Traits = cuckoo::traits>

     class CuckooSet
     {
     public:
     class CuckooSet
     {
     public:

-        typedef T   value_type  ;   ///< The value type stored in the set
-        typedef Traits options  ;   ///< Set traits
+        typedef T   value_type;   ///< The value type stored in the set
+        typedef Traits traits;    ///< Set traits

 
 

-        typedef typename options::hook      hook        ;   ///< hook type
-        typedef typename hook::node_type    node_type   ;   ///< node type
-        typedef typename get_node_traits< value_type, node_type, hook>::type node_traits ;    ///< node traits
+        typedef typename traits::hook       hook;        ///< hook type
+        typedef typename hook::node_type    node_type;   ///< node type
+        typedef typename get_node_traits< value_type, node_type, hook>::type node_traits;    ///< node traits

 
 

-        typedef typename options::hash              hash ;   ///< hash functor tuple wrapped for internal use
-        typedef typename hash::hash_tuple_type      hash_tuple_type ; ///< Type of hash tuple
+        typedef typename traits::hash          hash;   ///< hash functor tuple wrapped for internal use
+        typedef typename hash::hash_tuple_type hash_tuple_type; ///< Type of hash tuple

 
 

-        typedef typename options::stat              stat    ;   ///< internal statistics type
+        typedef typename traits::stat          stat;   ///< internal statistics type

 
 

-        typedef typename options::mutex_policy      original_mutex_policy   ;   ///< Concurrent access policy, see cuckoo::type_traits::mutex_policy
+        typedef typename traits::mutex_policy  original_mutex_policy; ///< Concurrent access policy, see \p cuckoo::traits::mutex_policy

 
 

-        /// Actual mutex policy
-        /**
-            Actual mutex policy is built from mutex policy type provided by \p Traits template argument (see cuckoo::type_traits::mutex_policy)
-            but mutex policy internal statistics is conformed with cukoo::type_traits::stat type provided by \p Traits:
-            - if \p %cuckoo::type_traits::stat is cuckoo::empty_stat then mutex policy statistics is already empty one
-            - otherwise real mutex policy statistics is used
-        */
+        //@cond

         typedef typename original_mutex_policy::template rebind_statistics<
             typename std::conditional<
                 std::is_same< stat, cuckoo::empty_stat >::value
         typedef typename original_mutex_policy::template rebind_statistics<
             typename std::conditional<
                 std::is_same< stat, cuckoo::empty_stat >::value


@@ -1867,25 +1871,31 @@ namespace cds { namespace intrusive {
                 ,typename original_mutex_policy::real_stat
             >::type
         >::other    mutex_policy;
                 ,typename original_mutex_policy::real_stat
             >::type
         >::other    mutex_policy;

+        //@endcond

 
 

-        static bool const c_isSorted = !( std::is_same< typename options::compare, opt::none >::value
-                && std::is_same< typename options::less, opt::none >::value ) ; ///< whether the probe set should be ordered
+        /// Probe set should be ordered or not
+        /**
+            If \p Traits specifies \p cmpare or \p less functor then the set is ordered.
+            Otherwise, it is unordered and \p Traits should provide \p equal_to functor.
+        */
+        static bool const c_isSorted = !( std::is_same< typename traits::compare, opt::none >::value
+                && std::is_same< typename traits::less, opt::none >::value ) ;

         static size_t const c_nArity = hash::size ; ///< the arity of cuckoo hashing: the number of hash functors provided; minimum 2.
 
         /// Key equality functor; used only for unordered probe-set
         static size_t const c_nArity = hash::size ; ///< the arity of cuckoo hashing: the number of hash functors provided; minimum 2.
 
         /// Key equality functor; used only for unordered probe-set

-        typedef typename opt::details::make_equal_to< value_type, options, !c_isSorted>::type key_equal_to;
+        typedef typename opt::details::make_equal_to< value_type, traits, !c_isSorted>::type key_equal_to;

 
 

-        /// key comparing functor based on opt::compare and opt::less option setter. Used only for ordered probe set
-        typedef typename opt::details::make_comparator< value_type, options >::type key_comparator;
+        /// key comparing functor based on \p opt::compare and \p opt::less option setter. Used only for ordered probe set
+        typedef typename opt::details::make_comparator< value_type, traits >::type key_comparator;

 
         /// allocator type
 
         /// allocator type

-        typedef typename options::allocator     allocator;
+        typedef typename traits::allocator     allocator;

 
         /// item counter type
 
         /// item counter type

-        typedef typename options::item_counter  item_counter;
+        typedef typename traits::item_counter  item_counter;

 
         /// node disposer
 
         /// node disposer

-        typedef typename options::disposer      disposer;
+        typedef typename traits::disposer      disposer;

 
     protected:
         //@cond
 
     protected:
         //@cond


@@ -1909,10 +1919,7 @@ namespace cds { namespace intrusive {
             bucket_iterator     itFound;
         };
 
             bucket_iterator     itFound;
         };
 

-        typedef typename std::conditional< c_isSorted
-            , cuckoo::details::contains< node_traits, true >
-            , cuckoo::details::contains< node_traits, false >
-        >::type contains_action;
+        typedef cuckoo::details::contains< node_traits, c_isSorted > contains_action;

 
         template <typename Predicate>
         struct predicate_wrapper {
 
         template <typename Predicate>
         struct predicate_wrapper {


@@ -1923,9 +1930,9 @@ namespace cds { namespace intrusive {
         //@endcond
 
     public:
         //@endcond
 
     public:

-        static unsigned int const   c_nDefaultProbesetSize = 4  ;   ///< default probeset size
-        static size_t const         c_nDefaultInitialSize = 16  ;   ///< default initial size
-        static unsigned int const   c_nRelocateLimit = c_nArity * 2 - 1 ;   ///< Count of attempts to relocate before giving up
+        static unsigned int const   c_nDefaultProbesetSize = 4;   ///< default probeset size
+        static size_t const         c_nDefaultInitialSize = 16;   ///< default initial size
+        static unsigned int const   c_nRelocateLimit = c_nArity * 2 - 1; ///< Count of attempts to relocate before giving up

 
     protected:
         bucket_entry *      m_BucketTable[ c_nArity ] ; ///< Bucket tables
 
     protected:
         bucket_entry *      m_BucketTable[ c_nArity ] ; ///< Bucket tables


@@ -1977,7 +1984,6 @@ namespace cds { namespace intrusive {
         static void store_hash( node_type * pNode, size_t * pHashes )
         {
             cuckoo::details::hash_ops< node_type, c_nNodeHashArraySize >::store( pNode, pHashes );
         static void store_hash( node_type * pNode, size_t * pHashes )
         {
             cuckoo::details::hash_ops< node_type, c_nNodeHashArraySize >::store( pNode, pHashes );

-            //memcpy( pNode->m_arrHash, pHashes, sizeof(size_t) * c_nArity );

         }
 
         static bool equal_hash( node_type& node, unsigned int nTable, size_t nHash )
         }
 
         static bool equal_hash( node_type& node, unsigned int nTable, size_t nHash )


@@ -2008,7 +2014,7 @@ namespace cds { namespace intrusive {
             free_bucket_tables( m_BucketTable, m_nBucketMask + 1 );
         }
 
             free_bucket_tables( m_BucketTable, m_nBucketMask + 1 );
         }
 

-        static unsigned int const c_nUndefTable = (unsigned int) -1;
+        static CDS_CONSTEXPR unsigned int const c_nUndefTable = (unsigned int) -1;

         template <typename Q, typename Predicate >
         unsigned int contains( position * arrPos, size_t * arrHash, Q const& val, Predicate pred )
         {
         template <typename Q, typename Predicate >
         unsigned int contains( position * arrPos, size_t * arrHash, Q const& val, Predicate pred )
         {


@@ -2205,10 +2211,11 @@ namespace cds { namespace intrusive {
 
         CDS_CONSTEXPR static unsigned int calc_probeset_size( unsigned int nProbesetSize ) CDS_NOEXCEPT
         {
 
         CDS_CONSTEXPR static unsigned int calc_probeset_size( unsigned int nProbesetSize ) CDS_NOEXCEPT
         {

-            return nProbesetSize
-                ? nProbesetSize
-                : ( node_type::probeset_size ? node_type::probeset_size : c_nDefaultProbesetSize )
-;
+            return std::is_same< probeset_class, cuckoo::vector_probeset_class >::value
+                ? node_type::probeset_size
+                : (nProbesetSize
+                    ? nProbesetSize
+                    : ( node_type::probeset_size ? node_type::probeset_size : c_nDefaultProbesetSize ));

         }
         //@endcond
 
         }
         //@endcond
 


@@ -2237,12 +2244,12 @@ namespace cds { namespace intrusive {
         /// Constructs the set object with given probe set size and threshold
         /**
             If probe set type is <tt> cuckoo::vector<Capacity> </tt> vector
         /// Constructs the set object with given probe set size and threshold
         /**
             If probe set type is <tt> cuckoo::vector<Capacity> </tt> vector

-            then \p nProbesetSize should be equal to vector's \p Capacity.
+            then \p nProbesetSize is ignored since it should be equal to vector's \p Capacity.

         */
         CuckooSet(
         */
         CuckooSet(

-            size_t nInitialSize                 ///< Initial set size; if 0 - use default initial size \ref c_nDefaultInitialSize
+            size_t nInitialSize                 ///< Initial set size; if 0 - use default initial size \p c_nDefaultInitialSize

             , unsigned int nProbesetSize        ///< probe set size
             , unsigned int nProbesetSize        ///< probe set size

-            , unsigned int nProbesetThreshold = 0   ///< probe set threshold, <tt>nProbesetThreshold < nProbesetSize</tt>. If 0, nProbesetThreshold = nProbesetSize - 1
+            , unsigned int nProbesetThreshold = 0   ///< probe set threshold, <tt>nProbesetThreshold < nProbesetSize</tt>. If 0, <tt>nProbesetThreshold = nProbesetSize - 1</tt>

         )
             : m_nProbesetSize( calc_probeset_size(nProbesetSize) )
             , m_nProbesetThreshold( nProbesetThreshold ? nProbesetThreshold : m_nProbesetSize - 1 )
         )
             : m_nProbesetSize( calc_probeset_size(nProbesetSize) )
             , m_nProbesetThreshold( nProbesetThreshold ? nProbesetThreshold : m_nProbesetSize - 1 )


@@ -2256,7 +2263,7 @@ namespace cds { namespace intrusive {
 
         /// Constructs the set object with given hash functor tuple
         /**
 
         /// Constructs the set object with given hash functor tuple
         /**

-            The probe set size and threshold are set as default, see CuckooSet()
+            The probe set size and threshold are set as default, see \p CuckooSet()

         */
         CuckooSet(
             hash_tuple_type const& h    ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
         */
         CuckooSet(
             hash_tuple_type const& h    ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>


@@ -2278,9 +2285,9 @@ namespace cds { namespace intrusive {
             then \p nProbesetSize should be equal to vector's \p Capacity.
         */
         CuckooSet(
             then \p nProbesetSize should be equal to vector's \p Capacity.
         */
         CuckooSet(

-            size_t nInitialSize                 ///< Initial set size; if 0 - use default initial size \ref c_nDefaultInitialSize
+            size_t nInitialSize                 ///< Initial set size; if 0 - use default initial size \p c_nDefaultInitialSize

             , unsigned int nProbesetSize        ///< probe set size, positive integer
             , unsigned int nProbesetSize        ///< probe set size, positive integer

-            , unsigned int nProbesetThreshold   ///< probe set threshold, <tt>nProbesetThreshold < nProbesetSize</tt>. If 0, nProbesetThreshold = nProbesetSize - 1
+            , unsigned int nProbesetThreshold   ///< probe set threshold, <tt>nProbesetThreshold < nProbesetSize</tt>. If 0, <tt>nProbesetThreshold = nProbesetSize - 1</tt>

             , hash_tuple_type const& h    ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
         )
             : m_nProbesetSize( calc_probeset_size(nProbesetSize) )
             , hash_tuple_type const& h    ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
         )
             : m_nProbesetSize( calc_probeset_size(nProbesetSize) )


@@ -2296,7 +2303,7 @@ namespace cds { namespace intrusive {
 
         /// Constructs the set object with given hash functor tuple (move semantics)
         /**
 
         /// Constructs the set object with given hash functor tuple (move semantics)
         /**

-            The probe set size and threshold are set as default, see CuckooSet()
+            The probe set size and threshold are set as default, see \p CuckooSet()

         */
         CuckooSet(
             hash_tuple_type&& h     ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
         */
         CuckooSet(
             hash_tuple_type&& h     ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>


@@ -2318,9 +2325,9 @@ namespace cds { namespace intrusive {
             then \p nProbesetSize should be equal to vector's \p Capacity.
         */
         CuckooSet(
             then \p nProbesetSize should be equal to vector's \p Capacity.
         */
         CuckooSet(

-            size_t nInitialSize                 ///< Initial set size; if 0 - use default initial size \ref c_nDefaultInitialSize
+            size_t nInitialSize                 ///< Initial set size; if 0 - use default initial size \p c_nDefaultInitialSize

             , unsigned int nProbesetSize        ///< probe set size, positive integer
             , unsigned int nProbesetSize        ///< probe set size, positive integer

-            , unsigned int nProbesetThreshold   ///< probe set threshold, <tt>nProbesetThreshold < nProbesetSize</tt>. If 0, nProbesetThreshold = nProbesetSize - 1
+            , unsigned int nProbesetThreshold   ///< probe set threshold, <tt>nProbesetThreshold < nProbesetSize</tt>. If 0, <tt>nProbesetThreshold = nProbesetSize - 1</tt>

             , hash_tuple_type&& h    ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
         )
             : m_nProbesetSize( calc_probeset_size(nProbesetSize) )
             , hash_tuple_type&& h    ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
         )
             : m_nProbesetSize( calc_probeset_size(nProbesetSize) )


@@ -2343,10 +2350,9 @@ namespace cds { namespace intrusive {
     public:
         /// Inserts new node
         /**
     public:
         /// Inserts new node
         /**

-            The function inserts \p val in the set if it does not contain
-            an item with key equal to \p val.
+            The function inserts \p val in the set if it does not contain an item with key equal to \p val.

 
 

-            Returns \p true if \p val is placed into the set, \p false otherwise.
+            Returns \p true if \p val is inserted into the set, \p false otherwise.

         */
         bool insert( value_type& val )
         {
         */
         bool insert( value_type& val )
         {


@@ -2366,8 +2372,7 @@ namespace cds { namespace intrusive {
             \endcode
             where \p val is the item inserted.
 
             \endcode
             where \p val is the item inserted.
 

-            The user-defined functor is called only if the inserting is success and can be passed by reference
-            using \p std::ref
+            The user-defined functor is called only if the inserting is success.

         */
         template <typename Func>
         bool insert( value_type& val, Func f )
         */
         template <typename Func>
         bool insert( value_type& val, Func f )


@@ -2430,33 +2435,33 @@ namespace cds { namespace intrusive {
             return true;
         }
 
             return true;
         }
 

-        /// Ensures that the \p val exists in the set
+        /// Updates the node

         /**
             The operation performs inserting or changing data with lock-free manner.
 
         /**
             The operation performs inserting or changing data with lock-free manner.
 

-            If the item \p val not found in the set, then \p val is inserted into the set.
+            If the item \p val is not found in the set, then \p val is inserted into the set
+            iff \p bAllowInsert is \p true.

             Otherwise, the functor \p func is called with item found.
             Otherwise, the functor \p func is called with item found.

-            The functor signature is:
+            The functor \p func signature is:

             \code
                 void func( bool bNew, value_type& item, value_type& val );
             \endcode
             with arguments:
             - \p bNew - \p true if the item has been inserted, \p false otherwise
             - \p item - item of the set
             \code
                 void func( bool bNew, value_type& item, value_type& val );
             \endcode
             with arguments:
             - \p bNew - \p true if the item has been inserted, \p false otherwise
             - \p item - item of the set

-            - \p val - argument \p val passed into the \p ensure function
+            - \p val - argument \p val passed into the \p %update() function

             If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
             If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments

-            refers to the same thing.
+            refer to the same thing.

 
             The functor may change non-key fields of the \p item.
 
 
             The functor may change non-key fields of the \p item.
 

-            You may pass \p func argument by reference using \p std::ref.
-
-            Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successful,
+            Returns std::pair<bool, bool> where \p first is \p true if operation is successful,
+            i.e. the node has been inserted or updated,

             \p second is \p true if new item has been added or \p false if the item with \p key
             \p second is \p true if new item has been added or \p false if the item with \p key

-            already is in the set.
+            already exists.

         */
         template <typename Func>
         */
         template <typename Func>

-        std::pair<bool, bool> ensure( value_type& val, Func func )
+        std::pair<bool, bool> update( value_type& val, Func func, bool bAllowInsert = true )

         {
             hash_array arrHash;
             position arrPos[ c_nArity ];
         {
             hash_array arrHash;
             position arrPos[ c_nArity ];


@@ -2473,12 +2478,15 @@ namespace cds { namespace intrusive {
                     unsigned int nTable = contains( arrPos, arrHash, val, key_predicate() );
                     if ( nTable != c_nUndefTable ) {
                         func( false, *node_traits::to_value_ptr( *arrPos[nTable].itFound ), val );
                     unsigned int nTable = contains( arrPos, arrHash, val, key_predicate() );
                     if ( nTable != c_nUndefTable ) {
                         func( false, *node_traits::to_value_ptr( *arrPos[nTable].itFound ), val );

-                        m_Stat.onEnsureExist();
+                        m_Stat.onUpdateExist();

                         return std::make_pair( true, false );
                     }
 
                         return std::make_pair( true, false );
                     }
 

-                    node_type * pNode = node_traits::to_node_ptr( val );
-                    store_hash( pNode, arrHash );
+                    if ( !bAllowInsert )
+                        return std::make_pair( false, false );
+
+                    //node_type * pNode = node_traits::to_node_ptr( val );
+                    //store_hash( pNode, arrHash );

 
                     for ( unsigned int i = 0; i < c_nArity; ++i ) {
                         bucket_entry& refBucket = bucket( i, arrHash[i] );
 
                     for ( unsigned int i = 0; i < c_nArity; ++i ) {
                         bucket_entry& refBucket = bucket( i, arrHash[i] );


@@ -2486,7 +2494,7 @@ namespace cds { namespace intrusive {
                             refBucket.insert_after( arrPos[i].itPrev, pNode );
                             func( true, val, val );
                             ++m_ItemCounter;
                             refBucket.insert_after( arrPos[i].itPrev, pNode );
                             func( true, val, val );
                             ++m_ItemCounter;

-                            m_Stat.onEnsureSuccess();
+                            m_Stat.onUpdateSuccess();

                             return std::make_pair( true, true );
                         }
                     }
                             return std::make_pair( true, true );
                         }
                     }


@@ -2505,21 +2513,29 @@ namespace cds { namespace intrusive {
                     }
                 }
 
                     }
                 }
 

-                m_Stat.onEnsureResize();
+                m_Stat.onUpdateResize();

                 resize();
             }
 
         do_relocate:
                 resize();
             }
 
         do_relocate:

-            m_Stat.onEnsureRelocate();
+            m_Stat.onUpdateRelocate();

             if ( !relocate( nGoalTable, arrHash )) {
             if ( !relocate( nGoalTable, arrHash )) {

-                m_Stat.onEnsureRelocateFault();
-                m_Stat.onEnsureResize();
+                m_Stat.onUpdateRelocateFault();
+                m_Stat.onUpdateResize();

                 resize();
             }
 
                 resize();
             }
 

-            m_Stat.onEnsureSuccess();
+            m_Stat.onUpdateSuccess();

             return std::make_pair( true, true );
         }
             return std::make_pair( true, true );
         }

+        //@cond
+        template <typename Func>
+        CDS_DEPRECATED("ensure() is deprecated, use update()")
+        std::pair<bool, bool> ensure( value_type& val, Func func )
+        {
+            return update( val, func, true );
+        }
+        //@endcond

 
         /// Unlink the item \p val from the set
         /**
 
         /// Unlink the item \p val from the set
         /**


@@ -2578,6 +2594,7 @@ namespace cds { namespace intrusive {
         template <typename Q, typename Predicate>
         value_type * erase_with( Q const& val, Predicate pred )
         {
         template <typename Q, typename Predicate>
         value_type * erase_with( Q const& val, Predicate pred )
         {

+            CDS_UNUSED( pred );

             return erase_( val, typename predicate_wrapper<Predicate>::type(), [](value_type const&) {} );
         }
 
             return erase_( val, typename predicate_wrapper<Predicate>::type(), [](value_type const&) {} );
         }
 


@@ -2592,7 +2609,6 @@ namespace cds { namespace intrusive {
                 void operator()( value_type const& item );
             };
             \endcode
                 void operator()( value_type const& item );
             };
             \endcode

-            The functor may be passed by reference with <tt>boost:ref</tt>

 
             If the item with key equal to \p val is not found the function return \p nullptr.
 
 
             If the item with key equal to \p val is not found the function return \p nullptr.
 


@@ -2615,6 +2631,7 @@ namespace cds { namespace intrusive {
         template <typename Q, typename Predicate, typename Func>
         value_type * erase_with( Q const& val, Predicate pred, Func f )
         {
         template <typename Q, typename Predicate, typename Func>
         value_type * erase_with( Q const& val, Predicate pred, Func f )
         {

+            CDS_UNUSED( pred );

             return erase_( val, typename predicate_wrapper<Predicate>::type(), f );
         }
 
             return erase_( val, typename predicate_wrapper<Predicate>::type(), f );
         }
 


@@ -2629,8 +2646,6 @@ namespace cds { namespace intrusive {
             \endcode
             where \p item is the item found, \p val is the <tt>find</tt> function argument.
 
             \endcode
             where \p item is the item found, \p val is the <tt>find</tt> function argument.
 

-            You can pass \p f argument by reference using \p std::ref.
-

             The functor may change non-key fields of \p item.
 
             The \p val argument is non-const since it can be used as \p f functor destination i.e., the functor
             The functor may change non-key fields of \p item.
 
             The \p val argument is non-const since it can be used as \p f functor destination i.e., the functor


@@ -2646,6 +2661,13 @@ namespace cds { namespace intrusive {
         {
             return find_( val, key_predicate(), f );
         }
         {
             return find_( val, key_predicate(), f );
         }

+        //@cond
+        template <typename Q, typename Func>
+        bool find( Q const& val, Func f )
+        {
+            return find_( val, key_predicate(), f );
+        }
+        //@endcond

 
         /// Find the key \p val using \p pred predicate for comparing
         /**
 
         /// Find the key \p val using \p pred predicate for comparing
         /**


@@ -2658,81 +2680,63 @@ namespace cds { namespace intrusive {
         template <typename Q, typename Predicate, typename Func>
         bool find_with( Q& val, Predicate pred, Func f )
         {
         template <typename Q, typename Predicate, typename Func>
         bool find_with( Q& val, Predicate pred, Func f )
         {

+            CDS_UNUSED( pred );

             return find_( val, typename predicate_wrapper<Predicate>::type(), f );
         }
             return find_( val, typename predicate_wrapper<Predicate>::type(), f );
         }

-
-        /// Find the key \p val
-        /** \anchor cds_intrusive_CuckooSet_find_cfunc
-            The function searches the item with key equal to \p val and calls the functor \p f for item found.
-            The interface of \p Func functor is:
-            \code
-            struct functor {
-                void operator()( value_type& item, Q const& val );
-            };
-            \endcode
-            where \p item is the item found, \p val is the <tt>find</tt> function argument.
-
-            You can pass \p f argument by reference using \p std::ref.
-
-            The functor may change non-key fields of \p item.
-
-            The \p val argument is non-const since it can be used as \p f functor destination i.e., the functor
-            may modify both arguments.
-
-            The function returns \p true if \p val is found, \p false otherwise.
-        */
-        template <typename Q, typename Func>
-        bool find( Q const& val, Func f )
-        {
-            return find_( val, key_predicate(), f );
-        }
-
-        /// Find the key \p val using \p pred predicate for comparing
-        /**
-            The function is an analog of \ref cds_intrusive_CuckooSet_find_cfunc "find(Q const&, Func)"
-            but \p pred is used for key comparison.
-            If you use ordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::less.
-            If you use unordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::equal_to.
-            \p pred must imply the same element order as the comparator used for building the set.
-        */
+        //@cond

         template <typename Q, typename Predicate, typename Func>
         bool find_with( Q const& val, Predicate pred, Func f )
         {
         template <typename Q, typename Predicate, typename Func>
         bool find_with( Q const& val, Predicate pred, Func f )
         {

+            CDS_UNUSED( pred );

             return find_( val, typename predicate_wrapper<Predicate>::type(), f );
         }
             return find_( val, typename predicate_wrapper<Predicate>::type(), f );
         }

+        //@endcond

 
 

-        /// Find the key \p val
-        /** \anchor cds_intrusive_CuckooSet_find_val
-            The function searches the item with key equal to \p val
+        /// Checks whether the set contains \p key
+        /**
+            The function searches the item with key equal to \p key

             and returns \p true if it is found, and \p false otherwise.
             and returns \p true if it is found, and \p false otherwise.

-
-            Note the hash functor specified for class \p Traits template parameter
-            should accept a parameter of type \p Q that can be not the same as \p value_type.

         */
         template <typename Q>
         */
         template <typename Q>

-        bool find( Q const& val )
+        bool contains( Q const& key )
+        {
+            return find( key, [](value_type&, Q const& ) {} );
+        }
+        //@cond
+        template <typename Q>
+        CDS_DEPRECATED("deprecated, use contains()")
+        bool find( Q const& key )

         {
         {

-            return find( val, [](value_type&, Q const& ) {} );
+            return contains( key );

         }
         }

+        //@endcond

 
 

-        /// Find the key \p val using \p pred predicate for comparing
+        /// Checks whether the set contains \p key using \p pred predicate for searching

         /**
         /**

-            The function is an analog of \ref cds_intrusive_CuckooSet_find_val "find(Q const&)"
-            but \p pred is used for key comparison.
-            If you use ordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::less.
-            If you use unordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::equal_to.
-            \p pred must imply the same element order as the comparator used for building the set.
+            The function is similar to <tt>contains( key )</tt> but \p pred is used for key comparing.
+            If the set is unordered, \p Predicate has semantics like \p std::equal_to.
+            For ordered set \p Predicate has \p std::less semantics. In that case \p pred
+            must imply the same element order as the comparator used for building the set.

         */
         template <typename Q, typename Predicate>
         */
         template <typename Q, typename Predicate>

-        bool find_with( Q const& val, Predicate pred )
+        bool contains( Q const& key, Predicate pred )

         {
         {

-            return find_with( val, typename predicate_wrapper<Predicate>::type(), [](value_type& , Q const& ) {} );
+            CDS_UNUSED( pred );
+            return find_with( key, typename predicate_wrapper<Predicate>::type(), [](value_type& , Q const& ) {} );

         }
         }

+        //@cond
+        template <typename Q, typename Predicate>
+        CDS_DEPRECATED("deprecated, use contains()")
+        bool find_with( Q const& key, Predicate pred )
+        {
+            return contains( key, pred );
+        }
+        //@endcond

 
         /// Clears the set
         /**
             The function unlinks all items from the set.
 
         /// Clears the set
         /**
             The function unlinks all items from the set.

-            For any item \ref disposer is called
+            For any item <tt> @ref disposer</tt> is called

         */
         void clear()
         {
         */
         void clear()
         {


@@ -2741,7 +2745,7 @@ namespace cds { namespace intrusive {
 
         /// Clears the set and calls \p disposer for each item
         /**
 
         /// Clears the set and calls \p disposer for each item
         /**

-            The function unlinks all items from the set calling \p disposer for each item.
+            The function unlinks all items from the set calling \p oDisposer for each item.

             \p Disposer functor interface is:
             \code
             struct Disposer{
             \p Disposer functor interface is:
             \code
             struct Disposer{


@@ -2749,7 +2753,7 @@ namespace cds { namespace intrusive {
             };
             \endcode
 
             };
             \endcode
 

-            The \ref disposer specified in \p Traits options is not called.
+            The <tt> @ref disposer</tt> specified in \p Traits is not called.

         */
         template <typename Disposer>
         void clear_and_dispose( Disposer oDisposer )
         */
         template <typename Disposer>
         void clear_and_dispose( Disposer oDisposer )


@@ -2811,4 +2815,4 @@ namespace cds { namespace intrusive {
     };
 }} // namespace cds::intrusive
 
     };
 }} // namespace cds::intrusive
 

-#endif // #ifndef __CDS_INTRUSIVE_CUCKOO_SET_H
+#endif // #ifndef CDSLIB_INTRUSIVE_CUCKOO_SET_H